Mini FORTH

Autor: Fernando Guirao Núñez

Aquest projecte és part de l'assignatura Llenguatges de Programació (LP) de la FIB-UPC, fet al Q1 2025-2026. Per a més detalls pots consultar l'enunciat.

FORTH és un llenguatge basat en pila desenvolupat per Charles H. Moore als anys 70.

Mini FORTH és un intèrpret d'una versió reduïda del llenguatge FORTH implementat amb ANTLR i Python. Aquesta versió té les funcionalitats essencials del llenguatge: podem afegir números a la pila, i executar words que operen sobre aquesta. Les words són subrutines amb comportaments predefinits, i l'usuari també pot definir-ne noves.

• Prerrequisits
• Ús
• Capacitats de l'intèrpret
• Decisions de disseny (apartat rellevant per la correcció)

Nota: Seguint la terminologia de FORTH, normalment ens referirem a les funcions com a words.

Prerrequisits

• Python 3.8 o superior
• ANTLR 4.13.2

Dependències a instal·lar:

pip install antlr4-tools
pip install antlr4-python3-runtime==4.13.2

Nota: Les versions d'antlr4 i antlr4-python3-runtime han de coincidir.

Ús

Comandes per executar l'intèrpret:

# Generar arxius de la gramàtica
make

# Provar intèrpret en mode REPL
python3 forth.py

# Executar script
python3 forth.py script.f

# Executar jocs de prova
python3 -m doctest test.txt -v -f

# Neteja
make clean

Capacitats de l'intèrpret

A continuació es descriuen breument les capacitats de l'intèrpret amb exemples pràctics.

1. Push, pop i veure la pila

FORTH utilitza una pila per avaluar expressions. En trobar números, els va afegint a la pila d'avaluació:

1 2 3
.s                  ( mostra el contingut de la pila: [1, 2, 3] )
.                   ( desempila un element i el mostra: 3 )

L'intèrpret també reconeix comentaris com els que es mostren entre parèntesis.

2. Operacions aritmètiques

Aquest intèrpret només treballa amb nombres enters. Es poden utilitzar els següents operadors aritmètics:

10 3 - .            ( 10 - 3 = 7 )
6 7 * .             ( 6 * 7 = 42 )
15 4 / .            ( 15 / 4 = 3 -> divisió entera )
15 4 mod .          ( 15 mod 4 = 3 )

3. Comparadors i operadors lògics

A FORTH els booleans es codifiquen com 0 (fals) i -1 (cert). Aquests són els operadors que reconeix l'intèrpret:

5 3 >  .            ( -1 -> true  )
5 3 <  .            (  0 -> false )
5 5 =  .            ( -1 -> true  )
5 5 >= .            ( -1 -> true  )
5 6 <= .            ( -1 -> true  )
5 6 <> .            ( -1 -> true  )

5 3 > 10 8 > and .  ( -1 -> true and true = true )
2 7 < 4 9 >  or  .  ( -1 -> true or false = true )
5 5 =        not .  (  0 -> not true = false )

4. Built-in words per manipular la pila

L'intèrpret reconeix les següents words (funcions) predefinides a FORTH per manipular la pila (considereu aquest exemple com si la pila fes reset a cada linia):

2 3 swap .s         ( Intercanvia els dos elements del cim: 3 2 )
2 3 4 2swap .s      ( Intercanvia les dues parelles del cim: 4 3 2 )
5 dup .s            ( Duplica l'element del cim: 5 5 )
5 6 2dup .s         ( Duplica la parella del cim: 5 6 5 6 )
1 2 3 drop .s       ( Elimina l'element del cim: 1 2 )
1 2 3 4 2drop .s    ( Elimina els dos elements del cim: 1 2 )
1 2 over .s         ( Copia el segon element al cim: 1 2 1 )
1 2 3 4 2over .s    ( Copia la segona parella al cim: 1 2 3 4 1 2 )
1 2 3 rot .s        ( Rota els tres elements del cim: 2 3 1 )

5. User-defined words (funcions)

Podem definir noves words. Es delimiten per : i ;:

: square dup * ;
5 square .          ( 25 ) 

6. Condicionals

Han d'anar dins d'una word amb l'estructura següent:

condició if codi_true else codi_false endif
         ↑              ↑                ↑
  consumeix pila     opcional          tanca

Un exemple pràctic:

: abs dup 0 < if 0 swap - endif ;
-5 abs .            ( 5 )

Explicació pas a pas de -5 abs .:

1. Posem -5 a la pila
   Pila: [-5]

2. dup duplica el cim de la pila
   Pila: [-5, -5]

3. Posem 0 a la pila
   Pila: [-5, -5, 0]

4. < comprova si -5 < 0 (cert), els consumeix i posa -1 a la pila
   Pila: [-5, -1]

5. if consumeix el cert del cim i executa el bloc
   Pila: [-5]

6. Posem 0 a la pila
   Pila: [-5, 0]

7. swap intercanvia els dos elements del cim
   Pila: [0, -5]

8. - fa la resta 0 - (-5) = 5
   Pila: [5]

9. Finalment, . desempila i mostra el resultat: 5

7. Recursivitat

Per fer recursivitat utilitzem la keyword recurse, que només pot utilitzar-se dins de words. Crida a la mateixa word on s'utilitza:

: factorial dup 2 < if drop 1 else dup 1 - recurse * endif ;
5 factorial .       ( 120 )

8. Gestió d'errors

Aquest intèrpret és capaç de detectar i distingir entre errors lèxics, sintàctics i semàntics segons la fase en què es troba. Per a més detalls vegeu la secció Gestió d'errors (extra).

Decisions de disseny

He dividit la implementació d'aquest projecte en fases; una per cadascuna de les capacitats de l'intèrpret, en ordre de complexitat. En aquesta secció detallo les decisions de disseny més rellevants preses durant la implementació. Un dels principals objectius ha estat l'escalabilitat, de manera que el codi permeti ampliar les capacitats de l'intèrpret fàcilment sense haver de reescriure'n.

Estructura del repositori

• forth.g4: conté les regles de la gramàtica.
• stack.py: defineix la classe ForthStack.
• visitor.py: defineix la lògica del visitor.
• errors.py: defineix les classes d'excepcions que s'utilitzen per a cada tipus d'error.
• forth.py: implementa el mètode interpret que rep un string amb el codi a implementar.
• Makefile: permet generar els arxius ANTLR necessaris amb make.

Amb aquesta estructura distribuim de forma modular la lògica de l'interpretació del codi.

Sobre la gramàtica

Donada la naturalesa de FORTH, totes les expressions són en notació postfixa i per tant no calen parèntesis ni ordres de preferència. L'avaluació és seqüencial i no hi ha ambigüitat.

Això simplifica bastant la gramàtica, l'intèrpret esperarà una d'aquestes dues construccions:

• Expressions (statements): que poden ser números que s'introduixen a la pila i/o crides a words que interactuen amb aquesta.
• Definicions de words.

Pel que fa als condicionals i l'ús de recurse, la gramàtica només permet que s'utilitzin dins de la definició d'una word.

Com es deia abans, en una expressió, tot el que no són números són words. Per tant, a nivell gramatical, els operadors aritmètics, relacionals, lògics, words predefinides i words definides per l'usuari comparteixen la mateixa regla. Sí que es fa una distinció a nivell lèxic entre operadors i la resta de words (built-in i user-defined), els operadors sí que són words "hardcoded" a la gramàtica, ja que les words predefinides són més mutables, i per tant utilitzen el mateix token lèxic que les words definides per l'usuari (el de ID).

La classe ForthStack

Tota la lògica directament relacionada amb la pila es troba al fitxer stack.py, que conté la classe ForthStack amb els mètodes que manipulen directament la pila. Aquests mètodes no són directament les words predefinides, sinó que serveixen d'interfície per tenir un codi més net a visitor.py, des d'on sí que es defineixen les words.

Des de la classe ForthStack es llencen les excepcions de pila buida.

El TreeVisitor

El fitxer visitor.py defineix la lògica que s'aplica en recórrer l'AST. Gràcies a la abstracció simplificada del llenguatge a la gramàtica, definim la lògica del visitor en uns pocs mètodes.

La classe TreeVisitor és el cor de l'intèrpret, en inicialitzar-se, aquest inicialitza al seu torn:

• Una instància de ForthStack.
• Un diccionari que guarda les built-in words.
• Un diccionari que guarda les user-defined words (inicialment buit).

La classe del visitor també compta amb un atribut (current_word) rellevant per a la recursivitat, s'explica a la secció sobre recursivitat.

Implementació de les built-in words

Segons el nom de la word, el visitor primer busca si la té al diccionari builtin_words, o a user_words; si no, llança una excepció dient que la word no està definida.

Al diccionari builtin_words es defineix el comportament de:

• Operadors aritmètics (+, -, ...), relacionals (>, <, =, ...) i lògics (and, or, not).
• Operacions de manipulació de la pila (swap, dup, over, ...).

Totes les built-in words es defineixen al propi diccionari amb l'ajuda de funcions lambda, funcions "interficie" de ForthStack i funcions helper que encapsulen codi repetitiu (com per exemple fer pop dos elements de la pila, operar-los i fer push del resultat). D'aquesta manera simplifiquem el codi i facilitem molt la implementació de noves words predefinides.

Implementació de les user-defined words (ús de clausures)

Quan l'usuari defineix una word al codi FORTH això passa a un node wordDef de l'AST. Quan es visita aquest node, s'agafa el nom (ctx.ID().getText()) i el cos (ctx.block()). Amb el cos de la word, definim una clausura on bàsicament es visita aquest cos. Amb el nom (clau) i la clausura (valor) afegim la nova word definida per l'usuari a user_words.

Recursivitat (gestió del context d'execució)

Quan es crida a una word definida per l'usuari s'executa la seva clausura. Quan es defineix la clausura no només s'encapsula l'acció de visitar el codi de la word, sinó que a més això es fa actualitzant el context, i això consisteix en posar a l'atribut current_word el nom de la word sobre la que farem la recursivitat, de manera que quan el visitor veu la paraula recurse, sap que ha de cridar al nom de la word que hi ha current_word.

La gestió de l'atribut current_word es fa amb el @contextmanager _word_context. És recomanable complementar aquesta explicació mirant el codi a visitor.py que s'encarrega d'això per una millor comprensió.

Condicionals

Per tractar els condicionals, el visitor simplement quan veu l'if consumeix la pila i segons si fa pop d'un cert o un fals executa (visita) el bloc de codi pertinent.

Gestió d'errors (extra)

A l'hora de programar la manera en que l'intèrpret detecta i comunica a l'usuari els possibles errors que poden donar-se, vaig voler classificar els errors segons en quina fase d'interpretació del codi per entendre millor el funcionament d'un intèrpret (i en part també dels compiladors, tot i que això no ho és).

El fitxer errors.py conté les classes que simplement serveixen per classificar les excepcions:

• ForthError: hereta d'Exception i és l'excepció base per tots els errors, és a dir, la resta de classes d'errors hereten de ForthError.

• ForthLexicalError: és l'excepció que es llança quan el lexer falla, és a dir, quan es troba un token no reconegut per la gramàtica (@, $, #, etc.).

• ForthSyntaxError: és l'excepció que es llança quan el parser falla (la construcció de l'AST), és a dir quan els tokens són reconeguts per la gramàtica però tenen una estructura sintàctica incorrecta, per exemple : ;.

• ForthSemanticError: és l'excepció que llança el visitor quan falla. En aquest cas els tokens són reconeguts, l'estructura sintàctica és correcta, però l'expressió és incorrecta semànticament:

  • Cridar a words no definides.
  • Redefinir built-in words (això gforth ho permet però he decidit no permetre-ho en aquest intèrpret).
  • Divisió per zero.
  • Pila buida (recorda que aquesta excepció es llança des de ForthStack).

Si això es tractés d'un compilador, errors com la crida a words no definides serien estàtics (en temps de compilació) mentre errors com la divisió per zero serien dinàmics (en temps d'execució).

Gràcies a aquesta gestió d'errors es pot entendre millor el funcionament de l'intèrpret. Per exemple, quan s'executa un script, si hi ha un error lèxic o sintàctic, per terminal veurem directament el missatge d'error, però si es tracta d'un error semàntic veurem que l'intèrpret ha pogut executar tot el codi fins l'error, on es para l'execució.

En aquesta pràctica el codi que fem és principalment per reescriure el comportament del visitor, per això al llançar les excepcions dels errors semàntics podem personalitzar fàcilment els missatges. Pel que fa a errors sintàctics, com nosaltres no toquem el codi del parser, simplement comprovem si parser.getNumberOfSyntaxErrors() > 0 i es mostra un missatge genèric. Per fer missatges d'errors més informatius s'haurien d'utilitzar error listeners d'ANTLR, però he considerat que això ja es surt massa de l'scope d'aquesta pràctica. En el cas dels errors lèxics sí que es mostra al missatge d'error el token no reconegut que ha causat l'error. Per aconseguir-ho, es força al lexer a fer una tokenització completa del codi, s'analitza l'stream de tots els tokens i es mostra aquell que sigui del tipus LEXICAL_ERROR.

Mode REPL (extra)

L'enunciat de la pràctica demana implementar el mètode interpret al fitxer forth.py, però també, si s'executa des de la terminal, aquest script actua com a REPL (Read Eval Print Loop) per provar l'intèrpret de forma més dinàmica. Es poden introduir expressions vàlides en FORTH i l'intèrpret ens retorna el resultat (si és que ho demanem amb les words . o .s). Es poden utilitzar les fletxes del teclat per moure el cursor i per veure l'historial d'expressions (no és persistent entre sessions). Per abandonar el mode REPL de l'intèrpret ho fem amb l'ordre bye tal com es fa a gforth.

A més del mode REPL, si a l'hora d'executar forth.py des de la línia de comandes especifiquem la ruta a un script FORTH, aquest serà executat directament i veurem el resultat per terminal.

Joc de proves

El fitxer test.txt conté un joc de proves en format doctest que validen el correcte funcionament de l'intèrpret. Les proves cobreixen totes les funcionalitats implementades: operacions bàsiques, definició de words, condicionals, recursivitat i gestió d'errors, prioritzant casos representatius i algorismes reals com factorial, Fibonacci i MCD.

Escalabilitat

L'intèrpret de Mini-FORTH implementa les funcionalitats bàsiques del llenguatge. Però està preparat per implementar fàcilment extensions del llenguatge FORTH complet. Per afegir noves built-in words no cal ni tan sols modificar la gramàtica, es podrien també afegir variables (funcionen mitjançant direccions de memòria a FORTH) fent una memòria virtual al visitor i ampliant la gramàtica, també es poden afegir noves estructures de control. Però en qualsevol cas no caldria reescriure el codi existent.