Rodrigo Kumpera Weblog

Retomando a questão sobre como implementar Haskell em VMs tradicionais, vamos ver um dos aspectos mais complicados, thunking, de implementar de forma eficiente. Um dos aspectos que surpreende a maioria dos que usam Haskell pela primeira vez é o fato da linguagem ser lazy evaluated, isto é, o valor de uma expressão só é computado quando for usado, mesmo entre chamadas funções. Vejamos um exemplo simples:

square a = a * a
 
square_of_sum a b = square (a + b)

Nesse exemplo, quando square_of_sum chama square, o parâmetro passado não é o resultado de a + b, mas sim algo próximo a uma closure que irá calcular a + b. Quando square for avaliada, ela precisará do valor de ‘a’, então usará a closure que recebeu como parâmetro para tal. Ou melhor, funciona quase assim, Haskell implementa um mecanismo chamado call-by-need, que resolve o valor uma única vez na primeira vez que for necessário memorizando o resultado. Isso significa que no caso de square ‘a’ será avaliada uma única vez. Por conta da memorização, não usamos o termo closure, mais sim thunk para descrever o que uma função passa para outra.

Outro detalhe importante, chamadas de função também são lazy evaluated, então tanto square, quanto square_of_sum na verdade retornam thunks para os valores em questão. Essa coisa toda pode parecer extremamente ineficiente a primeira vista e de fato é. Tanto que o GHC gera código sem uso de thunk sempre que conseguir provar que um pedaço de código pode ser strict evaluated [1].

Antes de imaginar como implementar isso em uma VM como a CLR, vamos traduzir nosso exemplo para C# [2]:

 
class Thunk<T> {
	T value;
	Func<T> closure;
	bool resolved;
 
	public Thunk (Func<T> closure) {
		this.closure = closure;
	}
 
	public T Value {
		get {
			if (!resolved) {
				value = closure ();
				resolved = true;
				closure = null;
			}
			return value;
		}
	}
}
 
Thunk<int> square (Thunk <int> a) {
	return new Thunk<int> (() => a.Value * a.Value);
}
 
Thunk<int> square_of_sum (Thunk <int> a, Thunk<int> b) {
	Thunk<int> a_plus_b = new Thunk<int> (() => a.Value + b.Value);
	return square (a_plus_b); //Já que square produz um thunk, não precisamos criar outro.
}

Bem confuso, de certo. Primeiro a implementação de Thunk, simples e direta, já square_of_sum precisa de uma variável local para ficar minimamente legível. Uma coisa é fato, C# não foi feita para ser usada com lazy evaluation.

Existe alguns problema quanto a eficiencia de fazer dessa forma. O maior deles é como lidar quando alguns valores já estão resolvidos e temos ainda assim criar um thunk para satisfazer o função chamada. A forma como GHC lida isso é passando todos parâmetros boxed de forma que é possível misturar thunks e valores sem problema. A função square, do nosso exemplo anterior ficaria assim:

 
Thunk<int> square (object a) {
	return new Thunk<int> (() => {
		int val;
		if (a is int)
			val = (int)a;
		else
			val = ((Thunk<int>)a).Value;
		return val * val;
	});
}

Outra forma de também lidar com esse problema é criar duas versões da mesma função, uma que recebe valores resolvidos e outra apenas thunks. Fazer dessa forma é vantagem quando podemos provar o uso estrito dos valores em questão. Por fim, acho que o maior problema ser achar uma forma de representar um thunk usando o mínimo possível de memória.

No nosso exemplo, em uma plataforma 32bits, Trunk usa 20 bytes, Func usa mais 40 e outros 8 da closure[3]. Ou seja, começa usando 68, coisa pacas. Podemos fazer algumas mudanças nisso. Dado que não existe null em Haskell podemos remover o atributo resolved e simplesmente verificar se closure é ou não null. Segundo, em vez criar 1 delegate toda vez podemos fazer caching dele e armazenar as variáveis capturadas no próprio thunk. Algo como:

abstract class Thunk<T> {
	public abstract T Value { get; }
}
 
class ThunkWithVars<T,V> : Thunk<T> {
	T value;
	Func<V, T> closure;
	V vars;
 
	public ThunkWithVars (Func<V,T> closure, V vars) {
		this.closure = closure;
		this.vars = vars;
	}
 
	public override T Value {
		get {
			if (closure != null) {
				value = closure (vars);
				closure = null;
				vars = default (V);
			}
			return value;
		}
	}
}
 
static Func<Thunk<int>, int> square_resolve = (a) => a.Value * a.Value;
 
Thunk<int> square (Thunk <int> a) {
	return new ThunkWithVars<int, Thunk<int>> (square_resolve, a);
}

Usando essa codificação Thunk continua usando 20 bytes porém nos livramos dos demais objetos, um ganho de 70% no final das contas. Poderíamos economizar outros 4 se juntarmos as variáveis closure e value em uma só caso T fosse do tipo referência – ou manter o resultado boxed. Mesmo sem isso, 20 bytes já é um valor razoável, conseguir o mesmo em uma JVM é basicamente impossível sem muita ginástica.

Qual a performance dessa solução? Segundo o pessoal do GHC, em média 95%-98% dos thunks gerados são resolvidos. Com um generational GC, a maioria vira lixo efêmero. Ou seja, não existe muita razão para uma VM tradicional ser mais lenta que a do GHC, o principal fator nesse caso é, sem dúvida, o compilador, que pode gerar pedaços de código inteiros sem uso de thunk.

[1] É muito comum em Haskell gerar código que não funciona sem lazy evaluation, como geradores de listas infinitas.
[2] Nesse exemplo vou trapacear e tornar as funções mono-mórficas e usar int no lugar de Number para simplificar o código.
[3] Nesse caso estou ignorando quanto de memória as variáveis capturadas usam.