SmallForth: a Forth implementation over Pharo Smalltalk

Voltar ao índice.

Forth é uma linguagem a qual já dediquei muitas madrugadas “escovando bits” nos idos anos 80. Naquele tempo me metia com os “sinclairs” com teclados de membrana de borracha conectados a uma TV preto & branco.

Microsistemas

Forth apareceu certa vez num artigo da antiga revista Microsistemas.

Primeiro número
Nota: Na Wikipedia fala-se da extinção de revista. Procurando algum arquivo escaneado de número antigo encontrei o site World of Spectrum com alguns PDFs (citado na Wikipedia) mas que não funciona. Há o Datassette (também citado na Wikipedia) com arquivos da revista.

[Atualização] Inspecionando os arquivos da revista descobri no número 19 a primeira menção ao Forth.
Segundo número

Na revista com o artigo sobre o Forth (Veja acima) dizia que era usado principalmente para assestar telescópios. Com isso o artigo dava uma aguda impressão de especialização. Mas lendo mais percebia-se o grau de excelência da linguagem, principalmente na sua capacidade de ser estendida.

Na época o meu universo era o Basic, que vinha embutido nos microcomputadores. E alguma curiosidade, e uso bem modesto, do Assembly e conjunto de instruções do Z80, processador que era usado nos sinclairs (Tive um TK 85 e depois um TK 90) e MSXs (Tive um HotBit da Sharp).

Eu tive o primeiro contato com o Basic nos anos 70 num curso de férias quando fazia o básico do curso de engenharia elétrica na UFF. Aprendia FORTRAN no curso de engenharia. Depois, na fase profissional, alimentávamos programa nessa linguagem para calcular fluxos em sistemas de potência de alta tensão. Adorei no BASIC a sua simplicidade, em relação ao FORTRAN, que permitia uma experimentação menos dolorosa. Os FORMATs do FORTRAN eram terríveis. Voltei ao BASIC quando comprei o primeiro microcomputador numa loja de um meu futuro professor na graduação que fiz depois, começando em 1991, na UFS.

A atração pelo Forth, por causa do artigo na Microsistemas me levou a digitar instruções de máquina que eram publicadas em longas listas de códigos em hexadecimal para ter um interpretador do Forth (Veja imagem do trecho do artigo na Microsistemas de número 22). Tudo ia bem até que um erro no código ou na minha transcrição impediu-me de prosseguir. Não me lembro se tentei interagir com os editores da revista para corrigir o problema. Naquela época, sem Internet, era mais complicado e a necessidade de escrever para a revista uma carta deve ter me desanimado.

A minha experimentação com algumas ideias inspiradas no Forth continuaram em uma aplicação para cálculo de correntes de curto-circuito em redes de distribuição de energia elétrica para apoiar os trabalhos profissionais em projetos de proteção de redes elétricas contra surtos. Desenvolvi um programa em QuickBasic para descrever a topologia da rede e calcular as correntes. Mas, como uma espécie de backup, programei um calculadora programável da HP, que usavam a notação polonesa reversa similar ao que o Forth usa, para fazer os mesmos cálculos, é claro sem o poder do QuickBasic para persistir e carregar arquivos com dados da rede e imprimir relatórios. Tinha comprado dois livros de Forth e aprendi neles como acompanhar o stack do Forth. Isto facilitou enormemente a programação da calculadora.

Forth novamente

Recentemente, estimulado por um tweet (Ver abaixo) sobre o livro Thinking in Forth, voltei a olhar para o Forth na atualidade. E um artigo que encontrei sobre o Forth sugeria o desenvolvimento do Forth em vez de usar alguma implementação pronta. Parecia temerário mas me animei a fazer um protótipo bem tosco para experimentar um pouco com isso. No Pharo Smalltalk, é claro.

Comecei a ler também o livro Starting in Forth (online e PDF), do mesmo autor, para relembrar a sintaxe e capacidades do Forth.

Graças à fantástica produtividade do IDE do Pharo Smalltalk consegui um protótipo funcional de um interpreter para o Forth em poucas horas. Ele passa em uns poucos testes mas tem um bom potencial para ser estendido para incorporar mais funcionalidade.





Forth implementado em Smalltalk

Criamos a classe ForthInterpreter no pacote SmallForth-Core e um teste. O teste para passar vai precisar da implementação de ‘dup e *’ do ponto de vista do interpretador do Forth. O método #eval: é onde a interpretação se dará.

A história do desenvolvimento do protótipo (completamente guiado pelo uso da técnica test first) é o que passamos a contar.

Nota: Você pode baixar o file out do meu Google Drive.
Testando a word dup e a operação *

Interpretador

A primeira versão de #eval: apenas obtém as words da expressão em Forth numa stream.

Primeira versão de #eval:

Vamos escrever a primeira linha dentro do loop para cumprir a semântica do interpretador Forth que ao encontrar um número o coloca no stack.

Pushing number to stack

Stack

O stack, junto com o dictionary, são elementos importantes na estrutura de dados do interpretador Forth. No momento só precisamos do stack. O stack será referenciado por uma varíavel de instância que será atribuída no momento da criação da instância do interpreter.

Creating the stack

Inserimos uma linha para capturar a word ‘dup’, isto é, enviamos a mensagem #dup para o interpreter.

dup message
As palavras Forth neste post podem ser vistas em 1. Fundamental Forth e 2. How to Get Results.

dup

A semântica da word ‘dup’ no Forth é duplicar o conteúdo no topo do stack. Por isso implementamos o método #dup, para responder à mensagem #dup, como abaixo.

dup implementation

Vemos abaixo o efeito da execução de ‘dup’.

dup effect in stack

Você pode experimentar o Forth online para entender a semântica e a sintaxe.

Vamos fazer uma pequena correção em #eval: para que um número seja armazenado no stack e não uma string como está sendo feito agora.

Introduzimos #evalOperation: para processar o ‘*‘ (e também +, e /, por enquanto).

Com isso o nosso teste passa.

Implementar outras primitivas do Forth agora é trivial. Vamos implementar emit que transforma um número inteiro representando o código de uma caractere no caractere. E na tradição do Forth significa remover o número no topo do stack e colocar no lugar o caractere. Transferirmos também a criação do interpreter para #setUp.

emit

swap

Implementar swap, que troca o topo do stack com o elemento seguinte, é trivial.

Compilação

Vamos agora introduzir o nosso interpretador no mundo da “compilação” do Forth. O que é chamado de compilação no Forth é a criação de uma word num dicionário onde a definição é uma expressão do Forth que agora possuirá um nome para ser referida da mesma forma que as words dup, swap e emit que já criamos antes.

O interpretador entra no modo de compilação ao encontrar um “:” (colon). E volta ao modo de interpretação ao encontrar um “;” (semicolon). A primeira word após o colon será criada no dicionário e a sequência posterior até o semicolon, exceto ele, é armazenada para futura execução.

Para melhor lidar com os whitespaces introduzimos #getWordsFrom.

Introduzimos algumas modificações no método #eval: para que possa compilar e também executar código compilado. O método #compile: é acionado quando um colon (:) é encontrado. E só retorna quando encontra um semicolon (;). O efeito colateral é a criação de uma word no dicionário. Esta word pode ser executada no método #forthPerform:.

Dicionário

WordDictionary é uma class variable.

Usamos uma instância da classe ZnMultiValueDictionary como dicionário. O dicionário é criado quando a classe é carregada no IDE.

O método ForthInterpreter>>resetDictionary é usado em ForthInterpreterTest>>setUp. O dicionário contendo as words criadas pelo usuário é persistido junto com a imagem.

Vamos fazer um refactoring para evitar a repetição do trabalho feito por #getWordsFrom: quando #eval: é invocado em #evalWord:.

Primitivas

Existe um bug no nosso interpreter. Se ele encontrar a word ‘class’ ele usa o método #class herdado de ProtoObject como se fosse umas de suas primitivas. Vamos corrigir isto.

Repetimos abaixo a figura com o código do método #forthPerform: para facilitar.

Modificamos #forthRespondsTo: para verificar se a word é uma primitiva.

O método #primitiveWords deve retornar todas as primitivas válidas.

Após alguns refactorings para revelar a intenção de cada trecho do código #evalWords: ficou como abaixo:

Obtendo o topo da pilha

Vamos introduzir a operação dot (.). Optamos por mostrar o topo do stack no Transcript. No nosso caso o dot pode ser usado em qualquer ponto da expressão em Forth.

#openIfNone é uma extensão no Transcript. Veja o post Transcript openIfNone.

#evalWords: ao encontrar um dot (.) mostra o topo da pilha no Transcript usando a mensagem #transcriptShowTopOfStack.

O testDot passa.

Divisão

Havia um bug na operação de divisão (/). Para corrigir para que a divisão seja de inteiros e também para que a ordem dos argumentos esteja correta tivemos que modificar #evalOperation:.

Sinônimos

Implementamos mais algumas primitivas indicadas na lista: dup, emit, swap, drop, mod, slashMod. slashMod corresponde à /mod do Forth. Para permitir entrar /mod criamos uma tabela de sinônimos.

Por enquanto só há um sinônimo.

Revisão de emit e retorno de eval:

A implementação inicial de emit foi feita a partir de uma especificação errada. A implementação revisada de emit causou stack underflow no teste. O teste do emit revisado agora envolve o Transcript e uma resposta do usuário. E #evalWords: não retorna mais o stack top. Outros testes quebraram e tiveram que ser revisados para usar o novo método #top e #stack (Ver testSlashMod abaixo).

Revisão de dot(.)

Outra especificação errada a ser corrigida. Desta vez na semântica do dot (.). Antes de mostrar no Transcript o stack top deve ser removido.

Vamos a seguir remover a “deselegante” (na minha opinião) invocação do método transcriptShowTopOfStack. Ele é chamado quando um dot (.) aparece. Uma solução “natural” é criar o método primitivo dot e também uma sinonímia entre .(dot) e dot. Para isso começamos modificando evalWords: que agora não detecta o .(dot) explicitamente. O processamento do .(dot) acaba acontecendo em forthPerform:. dotS, que mostra o stack, também está incluído.

Mostrando toda a pilha

dotS(.s) mostra o tamanho e elementos na pilha sem removê-los.

Simplificando evalWords:

Vamos fazer mais algumas pequenas modificações. Queremos eliminar o trecho de evalWords: que contém as chamadas aos métodos isOperation: e evalOperation:. evalWords: ficará como abaixo.

Agora as operações serão executadas em forthPerform:. Para isso precisamos alterar a lista de primitivas e de sinônimos. Também vamos prefixar as primitivas que são sinônimos com underscore (_). Assim podemos criar uma word compilada minus sem que seja confundida com _minus, por exemplo.

O método abaixo cobre o operador +(plus), por exemplo.

E os testes quase todos passam. Exceto o que é objeto de nosso próximo desenvolvimento.

Desenvolvimento guiado por testes

Como podem já ter percebido a técnica de guiar o desenvolvimento através de testes faz com que a implementação e os testes evoluam em simbiose. Os testes e as implementações são duas faces da mesma moeda que é a especificação. O teste diz o “que” fazer e a implementação diz “como” fazer.

Outra técnica é evitar over engineering, isto é, não criar estruturas e/ou código prevendo desenvolvimento futuro ainda incerto ou pouco analisado/exercitado. É claro isto deve ser avaliado cum grano salis para também não exagerar muito no improviso.

SmallForth no GitHub

Você encontra o SmallForth no GitHub em https://github.com/chicoary/small-forth.

Voltar ao índice.

Continua na parte 2.

5 comentários

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s