tutorial - Implementando un intérprete de idiomas en Haskell

haskell tutorial

Question

Quiero implementar un intérprete de lenguaje obligatorio en Haskell (con fines educativos). Pero me resulta difícil crear la arquitectura correcta para mi intérprete: ¿Cómo debo almacenar las variables? ¿Cómo puedo implementar llamadas de función anidadas? ¿Cómo debo implementar el alcance variable? ¿Cómo puedo agregar posibilidades de depuración en mi idioma? ¿Debo usar mónadas / transformadores de mónada / otras técnicas? etc.

¿Alguien sabe buenos artículos / documentos / tutoriales / fuentes sobre este tema?

Answer 1

Si no está familiarizado con este tipo de procesadores, le recomiendo que deje de usar las mónadas por un tiempo y que primero se centre en obtener una implementación de barebones sin ningún problema.

Lo siguiente puede servir como un minitutorial.

Supongo que ya ha abordado el problema de analizar el texto de origen de los programas para los que desea escribir un intérprete y que tiene algunos tipos para capturar la sintaxis abstracta de su idioma. El lenguaje que uso aquí es muy simple y solo consiste en expresiones enteras y algunas declaraciones básicas.

Preliminares

Primero importemos algunos módulos que usaremos en un momento.

import Data.Function
import Data.List

La esencia de un lenguaje imperativo es que tiene alguna forma de variables mutables. Aquí, las variables simplemente representadas por cadenas:

type Var = String

Expresiones

A continuación, definimos expresiones. Las expresiones se construyen a partir de constantes enteras, referencias de variables y operaciones aritméticas.

infixl 6 :+:, :-:
infixl 7 :*:, :/:

data Exp
  = C Int        -- constant                                                     
  | V Var        -- variable                                                     
  | Exp :+: Exp  -- addition                                                     
  | Exp :-: Exp  -- subtraction                                                  
  | Exp :*: Exp  -- multiplication                                               
  | Exp :/: Exp  -- division

Por ejemplo, la expresión que agrega la constante 2 a la variable x está representada por V "x" :+: C 2 .

Declaraciones

El lenguaje de declaración es bastante mínimo. Tenemos tres formas de declaraciones: asignaciones de variables, bucles y secuencias.

infix 1 :=

data Stmt
  = Var := Exp      -- assignment                                                
  | While Exp Stmt  -- loop                                                      
  | Seq [Stmt]      -- sequence

Por ejemplo, una secuencia de sentencias para "intercambiar" los valores de las variables y puede representarse por Seq ["tmp" := V "x", "x" := V "y", "y" := V "tmp"] .

Los programas

Un programa es sólo una declaración.

type Prog = Stmt

Víveres

Ahora, pasemos al intérprete real. Mientras ejecutamos un programa, debemos realizar un seguimiento de los valores asignados a las diferentes variables en los programas. Estos valores son solo números enteros y como representación de nuestra "memoria" solo usamos listas de pares que consisten en una variable y un valor.

type Val = Int
type Store = [(Var, Val)]

Evaluando expresiones

Las expresiones se evalúan asignando constantes a su valor, buscando los valores de las variables en la tienda y asignando operaciones aritméticas a sus contrapartes de Haskell.

eval :: Exp -> Store -> Val
eval (C n) r       = n
eval (V x) r       = case lookup x r of
                       Nothing -> error ("unbound variable `" ++ x ++ "''")
                       Just v  -> v
eval (e1 :+: e2) r = eval e1 r + eval e2 r
eval (e1 :-: e2) r = eval e1 r - eval e2 r
eval (e1 :*: e2) r = eval e1 r * eval e2 r
eval (e1 :/: e2) r = eval e1 r `div` eval e2 r

Tenga en cuenta que si la tienda contiene varios enlaces para una variable, la lookup selecciona los enlaces que vienen primero en la tienda.

Declaraciones de ejecución

Si bien la evaluación de una expresión no puede alterar el contenido de la tienda, la ejecución de una declaración puede resultar en una actualización de la tienda. Por lo tanto, la función para ejecutar una declaración toma una tienda como un argumento y produce una tienda posiblemente actualizada.

exec :: Stmt -> Store -> Store
exec (x := e) r                    = (x, eval e r) : r
exec (While e s) r | eval e r /= 0 = exec (Seq [s, While e s]) r
                   | otherwise     = r
exec (Seq []) r                    = r
exec (Seq (s : ss)) r              = exec (Seq ss) (exec s r)

Tenga en cuenta que, en el caso de asignaciones, simplemente enviamos un nuevo enlace para la variable actualizada a la tienda, ocultando efectivamente cualquier enlace anterior para esa variable.

Intérprete de nivel superior

La ejecución de un programa se reduce a la ejecución de su declaración de nivel superior en el contexto de un almacén inicial.

run :: Prog -> Store -> Store
run p r = nubBy ((==) `on` fst) (exec p r)

Después de ejecutar la instrucción, limpiamos los enlaces sombreados, para que podamos leer fácilmente el contenido de la tienda final.

Ejemplo

Como ejemplo, considere el siguiente programa que calcula el número de Fibonacci del número almacenado en la variable n y almacena su resultado en la variable x .

fib :: Prog
fib = Seq
  [ "x" := C 0
  , "y" := C 1
  , While (V "n") $ Seq
      [ "z" := V "x" :+: V "y"
      , "x" := V "y"
      , "y" := V "z"
      , "n" := V "n" :-: C 1
      ]
  ]

Por ejemplo, en un entorno interactivo, ahora podemos usar nuestro intérprete para calcular el número 25 de Fibonacci:

> lookup "x" $ run fib [("n", 25)]
Just 75025

Interpretación monádica

Por supuesto, aquí estamos tratando con un lenguaje imperativo muy simple y minúsculo. A medida que su lenguaje se vuelva más complejo, también lo hará la implementación de su intérprete. Piense, por ejemplo, qué adiciones necesita cuando agrega procedimientos y necesita distinguir entre el almacenamiento local (basado en la pila) y el almacenamiento global (basado en el montón). Volviendo a esa parte de su pregunta, puede considerar la introducción de mónadas para simplificar un poco la implementación de su intérprete.

En el ejemplo de intérprete anterior, hay dos "efectos" que son candidatos para ser capturados por una estructura monádica:

1. El paso y la actualización de la tienda.
2. Anulando la ejecución del programa cuando se encuentra un error en tiempo de ejecución. (En la implementación anterior, el intérprete simplemente se bloquea cuando se produce un error de este tipo).

El primer efecto suele ser capturado por una mónada de estado, el segundo por una mónada de error. Investiguemos brevemente cómo hacer esto para nuestro intérprete.

Nos preparamos importando solo un módulo más de las bibliotecas estándar.

import Control.Monad

Podemos usar transformadores de mónada para construir una mónada compuesta para nuestros dos efectos combinando una mónada de estado básico y una mónada de error básica. Aquí, sin embargo, simplemente construimos la mónada compuesta de una sola vez.

newtype Interp a = Interp { runInterp :: Store -> Either String (a, Store) }

instance Monad Interp where
  return x = Interp $ /r -> Right (x, r)
  i >>= k  = Interp $ /r -> case runInterp i r of
               Left msg      -> Left msg
               Right (x, r'') -> runInterp (k x) r''
  fail msg = Interp $ /_ -> Left msg

Editar 2018: La propuesta de la mónada aplicativa

Desde la propuesta de la mónada aplicativa (AMP), cada mónada también debe ser una instancia de Functor y aplicativo. Para ello podemos añadir

import Control.Applicative -- Otherwise you can''t do the Applicative instance.

a las importaciones y hacer de Interp una instancia de Functor y Applicative como esta

instance Functor Interp where
  fmap = liftM -- imported from Control.Monad

instance Applicative Interp where
  pure  = return
  (<*>) = ap -- imported from Control.Monad

Editar 2018 final

Para leer y escribir en la tienda, introducimos las funciones efectivas rd y wr :

rd :: Var -> Interp Val
rd x = Interp $ /r -> case lookup x r of
         Nothing -> Left ("unbound variable `" ++ x ++ "''")
         Just v  -> Right (v, r)

wr :: Var -> Val -> Interp ()
wr x v = Interp $ /r -> Right ((), (x, v) : r)

Tenga en cuenta que rd produce un mensaje de error Envuelto en la Left si falla una búsqueda de variable.

La versión monádica del evaluador de expresiones ahora lee.

eval :: Exp -> Interp Val
eval (C n)       = do return n
eval (V x)       = do rd x
eval (e1 :+: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 + v2)
eval (e1 :-: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 - v2)
eval (e1 :*: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 * v2)
eval (e1 :/: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      if v2 == 0
                        then fail "division by zero"
                        else return (v1 `div` v2)

En el caso de :/: división por cero da como resultado que se produzca un mensaje de error a través de Interp fail , que, para Interp , se reduce a envolver el mensaje en un valor de Left .

Para la ejecución de sentencias tenemos

exec :: Stmt -> Interp ()
exec (x := e)       = do v <- eval e
                         wr x v
exec (While e s)    = do v <- eval e
                         when (v /= 0) (exec (Seq [s, While e s]))
exec (Seq [])       = do return ()
exec (Seq (s : ss)) = do exec s
                         exec (Seq ss)

El tipo de exec indica que las declaraciones no generan valores, sino que se ejecutan solo por sus efectos en la tienda o los errores de tiempo de ejecución que pueden desencadenar.

Finalmente, en la función run un cálculo monádico y procesamos sus efectos.

run :: Prog -> Store -> Either String Store
run p r = case runInterp (exec p) r of
            Left msg      -> Left msg
            Right (_, r'') -> Right (nubBy ((==) `on` fst) r'')

En el entorno interactivo, ahora podemos revisar la interpretación de nuestro programa de ejemplo:

> lookup "x" `fmap` run fib [("n", 25)]
Right (Just 75025)

> lookup "x" `fmap` run fib []
Left "unbound variable `n''"

Answer 2

Un par de buenos papeles que finalmente he encontrado:

• Construyendo intérpretes componiendo mónadas
• Transformadores de mónada paso a paso : cómo construir de forma incremental un pequeño intérprete utilizando transformadores de mónada
• Cómo construir un intérprete monádico en un día.
• Transformadores de mónada e intérpretes modulares