Escribe un intérprete Haskell en Haskell
hackage (14)
Un ejercicio de programación clásico es escribir un intérprete de Lisp / Scheme en Lisp / Scheme. El poder del lenguaje completo se puede aprovechar para producir un intérprete para un subconjunto del idioma.
¿Hay algún 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 mirar?
Aquí está la historia de fondo.Estoy explorando la idea de usar Haskell como un 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 haga, pero Haskell hace aproximadamente el 2000%. :)
Así que mi idea es crear un lenguaje que tenga exactamente las características de Haskell que me gustaría y no permite todo lo demás. A medida que los estudiantes progresan, puedo activar selectivamente 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 peguen un tiro en el pie mientras aún dominan la sintaxis y los conceptos que intenta enseñar. Y puedes ofrecer mejores mensajes de error.
crear un lenguaje que tenga exactamente las características de Haskell que me gustaría y no permite todo lo demás. A medida que los estudiantes progresan, puedo activar selectivamente varias funciones una vez que dominan los conceptos básicos.
Sugiero una solución más simple (como en menos trabajo) a este problema. En lugar de crear una implementación de Haskell donde puede desactivar las funciones, ajuste un compilador Haskell con un programa que primero verifique que el código no use ninguna característica que no permita, y luego use el compilador listo para compilarlo.
Eso sería similar a HLint (y también algo así como lo contrario):
HLint (anteriormente el 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 sugerencias personalizadas.
- Implemente sus propias "sugerencias" HLint para no usar las funciones que no permite
- Deshabilite todas las sugerencias estándar de HLint.
- Haga que su envoltura ejecute su HLint modificado como primer paso
- Trate las sugerencias HLint como errores. Es decir, si HLint "se quejó", entonces el programa no pasa a la etapa de compilación
¿No crees que sería más fácil tomar las fuentes de GHC y quitar lo que no quieres, que escribir tu propio intérprete de Haskell desde cero? En términos generales, debe haber mucho menos esfuerzo involucrado en la eliminación de características en lugar de crear / agregar características.
GHC está escrito en Haskell de todos modos, por lo que técnicamente se queda con su pregunta sobre un intérprete de Haskell escrito en Haskell.
Probablemente no sea demasiado difícil hacer que todo esté vinculado de forma estática y luego solo distribuya su GHCi personalizado, para que los estudiantes no puedan cargar otros módulos fuente de Haskell. En cuanto a la cantidad de trabajo que tomaría para evitar que carguen otros archivos de objeto Haskell, no tengo ni idea. Es posible que desee deshabilitar FFI también, si tiene un montón de tramposos en sus clases :)
¿Quieres construir tu intérprete desde cero? Comience implementando un lenguaje funcional más fácil como el cálculo lambda o una variante de ceceo. Para este último hay un wikibook bastante bonito llamado Write yourself a Scheme 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á que lidiar con características altamente complejas como clases de tipos, un sistema de tipo extremadamente poderoso (¡tipo-inferencia!) Y evaluación diferida (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 Esquema-ejemplo 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 los analizadores sintácticos, los compiladores y, por supuesto, los intérpretes.
El paquete a usar es pista (Language.Haskell. *) . Desafortunadamente, ni encontré tutoriales en línea sobre esto ni lo probé por mi cuenta, pero parece bastante prometedor.
Baskell es una implementación de enseñanza, http://hackage.haskell.org/package/baskell
Puede comenzar eligiendo solo, digamos, el tipo de sistema para implementar. Eso es tan complicado como un intérprete para Scheme, http://hackage.haskell.org/package/thih
El Programming Language Zoo de Andrej Bauer tiene una pequeña implementación de un lenguaje de programación puramente funcional llamado algo descarado "minihaskell". Se trata de 700 líneas de OCaml, por lo que es muy fácil de digerir.
El sitio también contiene versiones de juguetes de estilo ML, estilo Prolog y lenguajes de programación OO.
Hay un analizador Haskell completo: http://hackage.haskell.org/package/haskell-src-exts
Una vez que lo haya analizado, es fácil quitar o rechazar ciertas cosas. Hice esto para tryhaskell.org para no permitir declaraciones de importación, para admitir definiciones de alto nivel, etc.
Solo analiza 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 de 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 necesita hacer es definir una lista blanca de declaraciones, importaciones, símbolos, sintaxis disponibles, luego recorrer el AST y lanzar un "error de análisis" sobre cualquier cosa que no quiera que ellos conozcan todavía. Puede usar el valor SrcLoc adjunto a cada nodo en el AST:
data SrcLoc = SrcLoc
{ srcFilename :: String
, srcLine :: Int
, srcColumn :: Int
}
No hay necesidad de volver a implementar Haskell. Si desea proporcionar más errores de compilación amigables, simplemente analice el código, filtéelo, envíelo al compilador y analice el resultado del compilador. Si se trata de un "no puede coincidir con el tipo esperado a contra inferido a -> b ", entonces sabrá que probablemente haya muy pocos argumentos para una función.
A menos que realmente quieras pasar el tiempo implementando Haskell desde cero o jugando con las partes internas de Hugs, o alguna implementación tonta, creo que deberías filtrar lo que pasa a GHC. De esa manera, si sus estudiantes quieren tomar su código base y llevarlo al siguiente paso y escribir un verdadero código Haskell completamente desarrollado, la transición es transparente.
La serie de compiladores EHC es probablemente la mejor opción: está desarrollada activamente y parece ser exactamente lo que usted desea: una serie de pequeños compiladores / intérpretes de cálculos lambda que culminan en Haskell ''98.
Pero también podría consultar los distintos idiomas desarrollados en los Tipos y lenguajes de programación de Pierce, o el intérprete de Helium (un Haskell mutilado destinado a estudiantes http://en.wikipedia.org/wiki/Helium_(Haskell) ).
Me encanta tu objetivo, pero es un gran trabajo. Un par de consejos:
He trabajado en GHC, y no quieres ninguna parte de las fuentes. Hugs es una implementación mucho más simple y más 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 parte delantera.
¡Buena suerte! Identificar niveles de lenguaje para Haskell, con evidencia de apoyo del aula, sería de gran beneficio para la comunidad y definitivamente un resultado publicable.
Me han dicho que Idris tiene un analizador bastante compacto, no estoy seguro si es realmente adecuado para la alteración, pero está escrito en Haskell.
Podrías mirar Happy (un analizador tipo yacc en Haskell) que tiene un analizador 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 tipo, no necesita una inferencia de tipo para evaluar el código de Haskell.
Escribí un compilador del subconjunto de Haskell auto compilado para un desafío Code Golf. Toma el código del subconjunto Haskell en la entrada y produce el 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 hacerlo autocompilar.
Para un estudiante interesado en implementar un intérprete para un subconjunto de Haskell, recomendaría comenzar con las siguientes características:
Evaluación floja. Si el intérprete está en Haskell, es posible que no tenga que hacer nada para esto.
Definiciones de funciones con argumentos y protecciones de patrones combinados. Solo preocúpese por los patrones variables, cons, nil y
_.Sintaxis de expresión simple:
Literales enteros
Literales de caracteres
[](nil)Aplicación de función (asociativa izquierda)
Infijo
:(contras, asociativo derecho)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 comprobació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 por escribir un intérprete para lo anterior, agregarle una verificación de tipo debería ser menos desalentador.
Uhc / Ehc es una serie de compiladores que habilitan / deshabilitan varias características de Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC
ver si el helium sería una mejor base para construir que el estándar Haskell.