Escribir un intérprete de Haskell en Haskell

Un ejercicio de programación clásico es escribir un intérprete Lisp / Scheme en Lisp / Scheme. Se puede aprovechar el poder del idioma completo para producir un intérprete para un subconjunto del idioma.

¿Existe un ejercicio similar para Haskell? Me gustaría implementar un subconjunto de Haskell usando Haskell como motor. Por supuesto que se puede hacer, pero ¿hay algún recurso en línea disponible para consultar?

Estoy explorando la idea de usar Haskell como lenguaje para explorar algunos de los conceptos en un curso de estructuras discretas que estoy enseñando. Para este semestre me he decidido por Miranda , un lenguaje más pequeño que inspiró a Haskell. Miranda hace aproximadamente el 90% de lo que me gustaría que hiciera, pero Haskell hace aproximadamente el 2000%. :)

Entonces mi idea es crear un lenguaje que tenga exactamente las características de Haskell que me gustaría y no permita todo lo demás. A medida que los estudiantes progresan, puedo "activar" de forma selectiva varias funciones una vez que dominan los conceptos básicos.

Los "niveles de lenguaje" pedagógicos se han utilizado con éxito para enseñar Java y Scheme . Al limitar lo que pueden hacer, puede evitar que se disparen en el pie mientras todavía dominan la sintaxis y los conceptos que está tratando de enseñar. Y puede ofrecer mejores mensajes de error.

Amo tu objetivo, pero es un gran trabajo. Un par de pistas:

• He trabajado en GHC y no quieres ninguna parte de las fuentes. Hugs es una implementación mucho más simple y limpia, pero desafortunadamente está en C.

• Es una pequeña pieza del rompecabezas, pero Mark Jones escribió un hermoso artículo llamado Typing Haskell en Haskell, que sería un gran punto de partida para su interfaz.

¡Buena suerte! Identificar los niveles de idioma de Haskell, con evidencia de apoyo del aula, sería de gran beneficio para la comunidad y definitivamente un resultado publicable.

Hay un analizador de Haskell completo: http://hackage.haskell.org/package/haskell-src-exts

Una vez que lo haya analizado, eliminar o rechazar ciertas cosas es fácil. Hice esto para tryhaskell.org para no permitir declaraciones de importación, para admitir definiciones de nivel superior, etc.

Simplemente analice el módulo:

parseModule :: String -> ParseResult Module

Entonces tienes un AST para un módulo:

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

El tipo Decl es extenso: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

Todo lo que necesitas hacer es definir una lista blanca - de qué declaraciones, importaciones, símbolos, sintaxis están disponibles, luego recorrer el AST y lanzar un "error de análisis" en cualquier cosa que no quieras que ellos sepan todavía. Puede usar el valor SrcLoc adjunto a cada nodo en el AST:

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

No es necesario volver a implementar Haskell. Si desea proporcionar errores de compilación más amigables, simplemente analice el código, fíltrelo, envíelo al compilador y analice la salida del compilador. Si es un "no pudo coincidir el tipo esperado a contra el inferido a -> b", entonces sabrá que probablemente hay muy pocos argumentos para una función.

A menos que realmente quiera pasar tiempo implementando Haskell desde cero o jugando con los aspectos internos de Hugs, o alguna implementación tonta, creo que debería simplemente filtrar lo que se pasa a GHC. De esa manera, si sus estudiantes quieren tomar su base de código y pasar al siguiente paso y escribir un código Haskell real y completo, la transición es transparente.

¿Quieres construir tu intérprete desde cero? Empiece por implementar un lenguaje funcional más sencillo como el cálculo lambda o una variante lisp. Para este último, hay un wikilibro bastante agradable llamado Escribe un esquema en 48 horas que ofrece una introducción fresca y pragmática a las técnicas de análisis e interpretación.

Interpretar Haskell a mano será mucho más complejo, ya que tendrás que lidiar con características muy complejas como clases de tipos, un sistema de tipos extremadamente poderoso (¡inferencia de tipos!) Y evaluación perezosa (técnicas de reducción).

Por lo tanto, debe definir un subconjunto bastante pequeño de Haskell con el que trabajar y luego quizás comenzar extendiendo el ejemplo de esquema paso a paso.

Adición:

Tenga en cuenta que en Haskell, tiene acceso completo a la API de intérpretes (al menos en GHC), incluidos analizadores, compiladores y, por supuesto, intérpretes.

El paquete a utilizar es hint (Language.Haskell. *) . Desafortunadamente, no he encontrado tutoriales en línea sobre esto ni lo he probado yo mismo, pero parece bastante prometedor.

crear un lenguaje que tenga exactamente las características de Haskell que me gustaría y no permita todo lo demás. A medida que los estudiantes progresan, puedo "activar" de forma selectiva varias funciones una vez que dominan los conceptos básicos.

Sugiero una solución más simple (como en menos trabajo involucrado) a este problema. En lugar de crear una implementación de Haskell en la que pueda desactivar las funciones, envuelva un compilador de Haskell con un programa que primero verifique que el código no use ninguna función que usted no permita y luego use el compilador listo para usar para compilarlo.

Eso sería similar a HLint (y también algo opuesto):

HLint (anteriormente Dr. Haskell) lee los programas de Haskell y sugiere cambios que, con suerte, los hacen más fáciles de leer. HLint también facilita la desactivación de sugerencias no deseadas y la adición de sus propias sugerencias personalizadas.

• Implemente sus propias "sugerencias" de HLint para no utilizar las funciones que no permite
• Deshabilite todas las sugerencias estándar de HLint.
• Haga que su contenedor ejecute su HLint modificado como primer paso
• Trate las sugerencias de HLint como errores. Es decir, si HLint "se quejó", el programa no pasa a la etapa de compilación.

Baskell es una implementación de enseñanza, http://hackage.haskell.org/package/baskell

Puede comenzar eligiendo solo, digamos, el sistema de tipos a implementar. Eso es tan complicado como un intérprete de Scheme, http://hackage.haskell.org/package/thih

La serie de compiladores EHC es probablemente la mejor opción: está desarrollada activamente y parece ser exactamente lo que desea: una serie de pequeños compiladores / intérpretes de cálculos lambda que culminan en Haskell '98.

Pero también puede mirar los diversos lenguajes desarrollados en Tipos y lenguajes de programación de Pierce , o el intérprete de Helium (un Haskell lisiado destinado a estudiantes http://en.wikipedia.org/wiki/Helium_(Haskell) ).

Si está buscando un subconjunto de Haskell que sea fácil de implementar, puede eliminar las clases de tipos y la verificación de tipos. Sin clases de tipos, no necesita la inferencia de tipos para evaluar el código Haskell.

Escribí un compilador de subconjuntos Haskell autocompilable para un desafío de Code Golf. Toma el código de subconjunto de Haskell en la entrada y produce código C en la salida. Lamento que no haya una versión más legible disponible; Levanté las definiciones anidadas a mano en el proceso de compilarlas automáticamente.

Para un estudiante interesado en implementar un intérprete para un subconjunto de Haskell, recomendaría comenzar con las siguientes características:

• Evaluación perezosa. Si el intérprete está en Haskell, es posible que no tenga que hacer nada por esto.

• Definiciones de funciones con argumentos y protecciones de patrones coincidentes. Solo preocúpate por variables, contras, nulos y _patrones.

• Sintaxis de expresión simple:

  • Literales enteros

  • Literales de carácter

  • [] (nulo)

  • Aplicación de función (asociativa a la izquierda)

  • Infijo :(contras, asociativo a la derecha)

  • Paréntesis

  • Nombres de variables

  • Nombres de funciones

Más concretamente, escriba un intérprete que pueda ejecutar esto:

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

La verificación de tipos es una característica crucial de Haskell. Sin embargo, pasar de la nada a un compilador Haskell de verificación de tipos es muy difícil. Si comienza escribiendo un intérprete para lo anterior, agregarle la verificación de tipo debería ser menos abrumador.

Puede mirar a Happy (un analizador similar a yacc en Haskell) que tiene un analizador Haskell.

Esta podría ser una buena idea: cree una versión pequeña de NetLogo en Haskell. Aquí está el pequeño intérprete.

vea si el helio sería una mejor base para construir que el Haskell estándar.

Uhc / Ehc es una serie de compiladores que habilitan / deshabilitan varias funciones de Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

Me han dicho que Idris tiene un analizador bastante compacto, no estoy seguro de si es realmente adecuado para la alteración, pero está escrito en Haskell.

El Programming Language Zoo de Andrej Bauer tiene una pequeña implementación de un lenguaje de programación puramente funcional llamado un tanto descaradamente "minihaskell". Se trata de unas 700 líneas de OCaml, por lo que es muy fácil de digerir.

El sitio también contiene versiones de juguete de lenguajes de programación estilo ML, estilo Prolog y OO.

¿No crees que sería más fácil tomar las fuentes de GHC y eliminar lo que no quieres que escribir tu propio intérprete de Haskell desde cero? En términos generales, debería haber mucho menos esfuerzo involucrado en eliminar funciones en lugar de crear / agregar funciones.

GHC está escrito en Haskell de todos modos, así que técnicamente eso se queda con su pregunta de un intérprete de Haskell escrito en Haskell.

Probablemente no sería demasiado difícil vincular todo estáticamente y luego solo distribuir su GHCi personalizado, de modo que los estudiantes no puedan cargar otros módulos fuente de Haskell. En cuanto a cuánto trabajo se necesitaría para evitar que carguen otros archivos de objeto Haskell, no tengo idea. Es posible que también desee deshabilitar FFI, si tiene un grupo de tramposos en sus clases :)

La razón por la que hay tantos intérpretes LISP es que LISP es básicamente un predecesor de JSON: un formato simple para codificar datos. Esto hace que la parte de la interfaz sea bastante fácil de manejar. Comparado con eso, Haskell, especialmente con las extensiones de idioma, no es el idioma más fácil de analizar. Estas son algunas construcciones sintácticas que suenan difíciles de hacer bien:

• operadores con precedencia, asociatividad y fijeza configurables,
• comentarios anidados
• regla de diseño
• sintaxis del patrón
• do- bloques y desugaring a código monádico

Cada uno de estos, excepto quizás los operadores, podría ser abordado por los estudiantes después de su Curso de construcción de compiladores, pero quitaría el enfoque de cómo funciona Haskell en realidad. Además de eso, es posible que no desee implementar todas las construcciones sintácticas de Haskell directamente, sino implementar pases para deshacerse de ellas. Lo que nos lleva al núcleo literal del problema, juego de palabras totalmente intencionado.

Mi sugerencia es implementar la verificación de tipos y un intérprete para CoreHaskell completo en lugar de. Ambas tareas ya son bastante complejas por sí mismas. Este lenguaje, aunque sigue siendo un lenguaje funcional fuertemente tipado, es mucho menos complicado de manejar en términos de optimización y generación de código. Sin embargo, sigue siendo independiente de la máquina subyacente. Por lo tanto, GHC lo usa como lenguaje intermediario y traduce la mayoría de las construcciones sintácticas de Haskell en él.

Además, no debe rehuir el uso de la interfaz de GHC (u otro compilador). No lo consideraría una trampa, ya que los LISP personalizados utilizan el analizador del sistema LISP del host (al menos durante el arranque). Limpiar Corefragmentos y presentarlos a los estudiantes, junto con el código original, debería permitirle dar una descripción general de lo que hace la interfaz y por qué es preferible no volver a implementarla.

Aquí hay algunos enlaces a la documentación de Coretal como se usa en GHC:

• System FC: restricciones de igualdad y coacciones
• GHC / Como biblioteca
• El Coretipo