2009-09-18 38 views
80

Un ejercicio clásico de programación consiste en escribir un intérprete Lisp/Scheme en Lisp/Scheme. El poder del lenguaje completo se puede aprovechar para producir un intérprete para un subconjunto del idioma.Escribir un intérprete Haskell en Haskell

¿Hay algún ejercicio similar para Haskell? Me gustaría implementar un subconjunto de Haskell usando Haskell como motor. Por supuesto, puede hacerse, 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 idioma para explorar algunos de los conceptos en un curso Discrete Structures que estoy enseñando. Para este semestre me he conformado con 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 idioma" 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.

+0

Tengo un dialecto de Haskell WIP implementado con Typing Haskell en Haskell como base. Hay una demostración aquí http://chrisdone.com/toys/duet-delta/ No está listo para el lanzamiento de código abierto público, pero podría compartir la fuente con usted si está interesado. –

Respuesta

70

Me encanta su objetivo, pero es un gran trabajo. Un par de consejos:

  • He trabajado en GHC, y no quiero ser parte de las fuentes. Hugs es una aplicación mucho más simple, más limpio, pero por desgracia es en C.

  • Es una pequeña pieza del rompecabezas, pero Mark Jones escribió un hermoso papel llamado Typing Haskell in Haskell lo que sería un gran punto de partida para su extremo delantero.

¡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.

+2

¡Siempre puedo contar contigo para tener una buena respuesta! –

+1

Me pregunto si el comentario sobre GHC sigue siendo exacto. GHC es complejo, pero está bastante bien documentado. En particular, las 'Notas' internas son útiles para comprender los detalles de bajo nivel, y el [capítulo sobre GHC en * La arquitectura de las aplicaciones de código abierto *] (http://www.aosabook.org/es/ghc.html) proporciona una excelente descripción general de alto nivel. – sjy

3

Puede consultar Happy (un analizador tipo yacc en Haskell) que tiene un analizador Haskell.

24

¿Desea construir su 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 bueno llamado Write yourself a Scheme in 48 hours que brinda 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 muy 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 para trabajar con él y luego quizás comenzar extendiendo el Esquema-ejemplo paso a paso.

Adición:

Tenga en cuenta que en Haskell, usted tiene acceso completo a la API de intérpretes (al menos bajo GHC) incluyendo analizadores, compiladores y los intérpretes del curso.

El paquete a usar es hint (Language.Haskell.*). Desafortunadamente, ni encontré tutoriales en línea sobre esto ni lo probé por mi cuenta, pero parece bastante prometedor.

+10

Tenga en cuenta que la inferencia de tipos es realmente un algoritmo de línea muy fácil, 20-30. es hermoso en su simplicidad. La evaluación diferida tampoco es tan difícil de codificar. Yo diría que la dificultad radica en la sintaxis insana, la coincidencia de patrones y la gran cantidad de cosas en el lenguaje. – Claudiu

+0

Interesante - ¿Puedes publicar enlaces para los algos de inferencia de tipos? – Dario

+5

Sí, echa un vistazo a este libro gratuito - http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/ -, está en la página 273 (289 del pdf). El pseudocódigo alg está en P296. – Claudiu

20

creo un lenguaje que tiene 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.

que sería similar a HLint (y también un poco de su opuesto):

HLint (anteriormente el Dr. Haskell) lee los programas Haskell y sugiere cambios que se espera que 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.

  • implementar su propio HLint "sugerencias" para no utilizar las características que no permiten
  • Desactivar todas las sugerencias HLint estándar.
  • Haga que su envoltura ejecute su HLint modificado como primer paso
  • Trate las sugerencias de HLint como errores. Es decir, si HLint "se quejó", entonces el programa no proceder a la etapa de compilación
2

ver si helium haría una mejor base para construir sobre lo Haskell estándar.

1

¿No crees que sería más fácil tomar the GHC sources y quitar lo que no quieres, que escribir tu propio intérprete Haskell desde cero? En general, debe haber un lote menos esfuerzo involucrado en eliminar las características en lugar de crear/agregar funciones.

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

Probablemente no sea demasiado difícil hacer todo el enlace estáticamente y luego solo distribuir su GHCi personalizado, para que los estudiantes no puedan cargar otros módulos de fuente 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 :)

+1

Esto no es tan fácil como parece, ya que muchas características dependen de otras. Pero tal vez el OP simplemente no quiere importar Preludio y en su lugar proporcionar el suyo.La mayoría de Haskell que ves son funciones normales, no características específicas del tiempo de ejecución. (Pero, por supuesto, muchos * son *.) – jrockway

3

This podría ser una buena idea - hacer una versión minúscula de NetLogo en Haskell. Here es el pequeño intérprete.

+0

Los enlaces están muertos. ¿Hay alguna posibilidad de que este contenido aún exista en otro lugar? Sería curioso ... –

+0

hmm era una publicación de blog y no tengo idea qué palabras clave usar para buscarla. Una buena lección para incluir información más sustancial al proporcionar un enlace ... – Claudiu

+1

Aparece una búsqueda en Google de "netlogo haskell" ... esta pregunta. De todos modos, no es gran cosa. ¡Gracias! –

5

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 se puede mirar en las diversas lenguas desarrolladas en Tipos de Pierce y Lenguajes de Programación, o el intérprete de helio (un Haskell paralizado dirigido a estudiantes http://en.wikipedia.org/wiki/Helium_(Haskell)).

35

No es un completo analizador Haskell: http://hackage.haskell.org/package/haskell-src-exts

Una vez que haya analizado sintácticamente que, excluyendo o no permitir ciertas cosas es fácil. Hice esto por tryhaskell.org para rechazar las declaraciones de importación, para apoyar las definiciones de alto nivel, etc.

Sólo analizar el módulo:

parseModule :: String -> ParseResult Module 

Entonces usted tiene un AST para un módulo:

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

El tipo Decl es extensa: 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 lo que las declaraciones, las importaciones, los símbolos, la sintaxis está disponible, entonces recorre el AST y lanza un "error de análisis" sobre cualquier cosa que aún no quieras que ellos conozcan. Usted puede utilizar el valor SrcLoc unido a todos los nodos del AST:

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

No hay necesidad de volver a aplicar 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 se pudo hacer coincidir 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 dedicar tiempo a implementar Haskell desde cero o jugar 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.

6

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í self-compiling Haskell subset compiler 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:

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

  • Definiciones de funciones con argumentos y protecciones coincidentes con patrones. Solo preocúpese por los patrones variables, cons, nil y _.

  • sintaxis de la expresión simple:

    • literales enteros

    • literales de carácter

    • [] (cero)

    • aplicación de función (asociativos por la izquierda)

    • Infijo : (contras, asociativa derecha)

    • Paréntesis

    • nombres de variables

    • Los nombres de funciones

Más concretamente, escribir un intérprete que puede funcionar 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.

+0

"Evaluación diferida. Si el intérprete está en Haskell, es posible que no tenga que hacer nada para esto". Esto puede que no sea verdad. Consulte el artículo de Naylor en http://www.haskell.org/wikiupload/0/0a/TMR-Issue10.pdf para obtener más información sobre la implementación de un intérprete perezoso en Haskell. –

1

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.

2

Andrej Bauer's Programming Language Zoo tiene una pequeña implementación de un lenguaje de programación puramente funcional llamado descaradamente "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.