bkim::Blog

Aprendendo Forth -- e criando o próprio

Nessas últimas semanas decidi me dedicar a um projeto antigo: aprender Forth, uma linguagem não-convencional baseada em realizar operações sobre uma pilha de dados. Quem já programou uma calculadora HP tem alguma experiência com isso: números, vetores e matrizes são colocados em uma pilha - isto é, uma estrutura do tipo LIFO (last in, first out) - e as operações são executadas sobre os elementos do topo da pilha. Isto leva a descrever operações em notação polonesa reversa. Por exemplo, para calcular as raízes de uma equação quadrática $ax^2 + bx + c$, utilizamos a fórmula de Bháskara:

$$ x_ \pm = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} $$

Supondo que temos as constantes a, b, c disponíveis, podemos calcular a raiz $ x_ + $ em Forth com

b negate b b * 4 a c * * - sqrt + 2 a * /

Difícil entender? Vamos ver o que cada palavra faz:

Para deixar (um pouco) mais claro, vamos agrupar a operação e os operandos com parênteses:

((b negate) (((b b *) (4 (a c *) *) -) sqrt) +) (2 a *) /

Esta é apenas a maneira pós-fixa de se escrever a expressão infixa com que já estamos acostumados:

(-b + sqrt((b * b) - (4 * (a * c)))) / (2 * a)

Para facilitar ainda mais a compreensão, escrevi um interpretador (incompleto) da linguagem para mostrar como a pilha está a cada passo. A palavra .s imprime a pilha atual em uma linha no segundo campo de texto. Clique em ‘Run!’ para ver o resultado do programa acima para a equação $4x^2+5x+1$.

Por ser baseado em uma pilha, Forth inclui ainda comandos para manipular os elementos no topo de modo a executar operações repetidas com os mesmos argumentos. Dentre eles temos:

dup
Duplica o elemento do topo;
swap
Troca os dois elementos do topo;
rot
Rotaciona os três elementos do topo, colocando o 3º em 1º, o 1º em 2º, e o 2º em 3º;

Retornando ao exemplo anterior, vamos simplesmente colocar a, b, c na pilha nesta ordem, isto é, a no fundo, depois b, e no topo c. Podemos resolver a equação então com o seguinte programa:

Por fim, deixo um desafio para você também explorar a forma de pensar da linguagem: edite os programas acima para que, ao final, as duas raízes estejam presentes na pilha na ordem $( x_ -, x_ + )$. Você pode usar dup, swap e rot no primeiro campo de texto, mas não pode usar a, b e c no segundo.


  1. sqrt não está presente no padrão da linguagem, mas isso não nos impede de incluí-lo em nosso interpretador.
Published in .