Me gustaría aprender más sobre la programación concatenante a través de la creación de un lenguaje pequeño y simple, basado en la pila y siguiendo el paradigma de la concatenación.
Desafortunadamente, no he encontrado muchos recursos relacionados con los lenguajes concatenantes y su implementación, así que discúlpeme de antemano por mi posible ingenuidad.
Por lo tanto, definí mi lenguaje como una secuencia simple de concatenación de funciones, representada en el AST como una lista:
data Operation
= Concat [Operation]
| Quotation Operation
| Var String
| Lit Literal
| LitOp LiteralOperation
data Literal
= Int Int
| Float Float
data LiteralOperation
= Add | Sub | Mul | Div
El siguiente programa, 4 2 swap dup * +
(correspondiente a 2 * 2 + 4
) una vez analizado, proporcionará el siguiente AST:
Concat [Lit (Int 4), Lit (Int 2), Var "swap", Var "dup", LitOp Mul, LitOp Add]
Ahora tengo que inferir y verificar los tipos.
Escribí este tipo de sistema:
data Type
= TBasic BasicType -- 'Int' or 'Float'
| TVar String -- Variable type
| TQuoteE String -- Empty stack, noted 'A'
| TQuote String Type -- Non empty stack, noted 'A t'
| TConc Type Type -- A type for the concatenation
| TFun Type Type -- The type of functions
Ahí es donde entra mi pregunta, porque no sé qué tipo inferir de esa expresión. El tipo resultante es obvio, lo es Int
, pero no sé cómo verificar completamente este programa a nivel de tipo.
Al principio, como puede ver arriba, había pensado en un TConc
tipo que representa la concatenación de la misma manera que el TFun
tipo representa una función, porque al final la secuencia de concatenación forma una función única.
Otra opción, que aún no he explorado, sería aplicar la regla de inferencia de composición de funciones a cada elemento de esta secuencia de expresión. No sé cómo funcionaría con el basado en pila.
La pregunta es así: ¿cómo lo hacemos? ¿Qué algoritmo usar y qué enfoque a nivel de tipo debería preferirse?