Scrivi un interprete Haskell in Haskell

StackOverflow https://stackoverflow.com/questions/1445827

Domanda

Un classico esercizio di programmazione è scrivere un interprete Lisp / Scheme in Lisp / Scheme. Il potere dell'intera lingua può essere sfruttato per produrre un interprete per un sottoinsieme della lingua.

Esiste un esercizio simile per Haskell? Vorrei implementare un sottoinsieme di Haskell usando Haskell come motore. Naturalmente può essere fatto, ma ci sono risorse online disponibili da guardare?

Ecco il retroscena.

Sto esplorando l'idea di usare Haskell come linguaggio per esplorare alcuni dei concetti in un Strutture discrete che sto insegnando. Per questo semestre ho optato per Miranda , un linguaggio più piccolo che ha ispirato Haskell. Miranda fa circa il 90% di quello che mi piacerebbe fare, ma Haskell fa circa il 2000%. :)

Quindi la mia idea è quella di creare un linguaggio che abbia esattamente le caratteristiche di Haskell che mi piacerebbe e non consentire tutto il resto. Man mano che gli studenti avanzano, posso selettivamente " attivare " varie funzioni una volta che hanno imparato le basi.

Livelli linguistici pedagogici " sono stati usati con successo per insegnare Java e Schema . Limitando ciò che possono fare, puoi impedire loro di spararsi nel piede mentre stanno ancora padroneggiando la sintassi e i concetti che stai cercando di insegnare. E puoi offrire messaggi di errore migliori.

È stato utile?

Soluzione

Adoro il tuo obiettivo, ma è un grande lavoro. Un paio di suggerimenti:

  • Ho lavorato su GHC e non vuoi alcuna parte delle fonti. Hugs è un'implementazione molto più semplice e pulita, ma sfortunatamente è in C.

  • È un piccolo pezzo del puzzle, ma Mark Jones ha scritto un bellissimo documento chiamato Digitando Haskell in Haskell che sarebbe un ottimo punto di partenza per il tuo front-end.

Buona fortuna! Identificare i livelli linguistici di Haskell, con prove a sostegno dell'aula, sarebbe di grande beneficio per la comunità e sicuramente un risultato pubblicabile!

Altri suggerimenti

Esiste un parser Haskell completo: http://hackage.haskell.org/package / Haskell-src-exts

Dopo averlo analizzato, eliminare o impedire determinate cose è facile. L'ho fatto per tryhaskell.org per non consentire dichiarazioni di importazione, per supportare definizioni di alto livello, ecc.

Basta analizzare il modulo: 

parseModule :: String -> ParseResult Module

Quindi hai un AST per un modulo: 

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

Il tipo di Decl è esteso: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html# t% 3ADecl

Tutto quello che devi fare è definire una lista bianca - di quali dichiarazioni, importazioni, simboli, sintassi è disponibile, quindi camminare sull'AST e lanciare un errore di "analisi" " su tutto ciò di cui non vuoi che siano ancora a conoscenza. È possibile utilizzare il valore SrcLoc associato a ciascun nodo nell'AST: 

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

Non è necessario implementare nuovamente Haskell. Se si desidera fornire errori di compilazione più intuitivi, basta analizzare il codice, filtrarlo, inviarlo al compilatore e analizzare l'output del compilatore. Se è un " impossibile trovare il tipo atteso a contro a - > b " allora sai che probabilmente sono troppo pochi gli argomenti per una funzione.

A meno che tu non voglia davvero passare il tempo a implementare Haskell da zero o a scherzare con gli interni di Hugs, o qualche stupida implementazione, penso che dovresti semplicemente filtrare ciò che viene passato a GHC. In questo modo, se i tuoi studenti vogliono prendere la loro base di codice e portarla al passaggio successivo e scrivere del vero codice Haskell a tutti gli effetti, la transizione è trasparente.

Vuoi costruire il tuo interprete da zero? Inizia con l'implementazione di un linguaggio funzionale più semplice come il calcolo lambda o una variante lisp. Per quest'ultimo c'è un bel wikibook chiamato Scriviti uno Schema in 48 ore dando una calma e introduzione pragmatica nelle tecniche di analisi e interpretazione.

L'interpretazione a mano di Haskell sarà molto più complessa poiché dovrai affrontare funzioni molto complesse come le macchine da scrivere, un sistema di tipo estremamente potente (inferenza di tipo!) e una valutazione pigra (tecniche di riduzione).

Quindi dovresti definire un piccolo sottoinsieme di Haskell con cui lavorare e poi forse iniziare estendendo l'esempio di Schema passo dopo passo.

Aggiunta:

Nota che in Haskell hai pieno accesso all'API degli interpreti (almeno sotto GHC) inclusi parser, compilatori e ovviamente interpreti.

Il pacchetto da utilizzare è hint (Language.Haskell. *) . Purtroppo non ho trovato tutorial online su questo né provato da solo, ma sembra abbastanza promettente.

  

crea un linguaggio che ha esattamente le caratteristiche di Haskell che mi piacerebbe e non consente tutto il resto. Man mano che gli studenti avanzano, posso selettivamente " attivare " varie funzioni una volta che hanno imparato le basi.

Suggerisco una soluzione più semplice (come in un lavoro minore) a questo problema. Invece di creare un'implementazione di Haskell in cui è possibile disattivare le funzionalità, avvolgere un compilatore Haskell con un programma che controlla innanzitutto che il codice non utilizzi alcuna funzionalità non consentita, quindi utilizza il compilatore pronto per compilarlo.

Sarebbe simile a HLint (e anche il suo opposto):

  

HLint (ex Dr. Haskell) legge i programmi Haskell e suggerisce cambiamenti che si spera li rendano più facili da leggere. HLint semplifica inoltre la disattivazione di suggerimenti indesiderati e l'aggiunta di suggerimenti personalizzati.

  • Implementa il tuo HLint " suggerimenti " per non utilizzare le funzionalità non consentite
  • Disabilita tutti i suggerimenti HLint standard.
  • Fai in modo che il tuo wrapper esegua il tuo HLint modificato come primo passo
  • Tratta i suggerimenti di HLint come errori. Cioè, se HLint "si è lamentato" quindi il programma non passa alla fase di compilazione

Baskell è un'implementazione didattica, http://hackage.haskell.org/package/baskell

Potresti iniziare selezionando, per esempio, il tipo di sistema da implementare. È complicato quanto un interprete per Scheme, http://hackage.haskell.org/package/thih

La serie di compilatori EHC è probabilmente la soluzione migliore: è attivamente sviluppata e sembra essere esattamente quello che vuoi - una serie di piccoli compilatori / interpreti di calcoli lambda che culminano in Haskell '98.

Ma potresti anche guardare i vari linguaggi sviluppati nei Tipi e linguaggi di programmazione di Pierce, o nell'interprete Helium (un Haskell paralizzato destinato agli studenti http://en.wikipedia.org/wiki/Helium_ (Haskell) ).

Se stai cercando un sottoinsieme di Haskell che sia facile da implementare, puoi eliminare le classi di tipi e il controllo dei tipi. Senza le classi di tipo, non è necessaria l'inferenza di tipo per valutare il codice Haskell.

Ho scritto un compilatore del sottoinsieme Haskell autocompilante per un Code Golf sfida. Prende il codice del sottoinsieme Haskell sull'input e produce il codice C sull'output. Mi dispiace che non sia disponibile una versione più leggibile; Ho sollevato manualmente le definizioni nidificate nel processo di compilazione automatica.

Per uno studente interessato a implementare un interprete per un sottoinsieme di Haskell, consiglierei di iniziare con le seguenti funzionalità:

  • Valutazione pigra. Se l'interprete è in Haskell, potresti non dover fare nulla per questo.

  • Definizioni delle funzioni con argomenti e protezioni corrispondenti al modello. Preoccupati solo di modelli variabili, contro, nulli e _ .

  • Sintassi dell'espressione semplice:

    • Letterali interi

    • Letterali dei personaggi

    • [] (zero)

    • Applicazione funzione (associativa sinistra)

    • Infix : (contro, associativo a destra)

    • Parentesi

    • Nomi delle variabili

    • Nomi delle funzioni

Più concretamente, scrivi un interprete che può eseguire questo: 

-- 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)

Il controllo del tipo è una caratteristica cruciale di Haskell. Tuttavia, passare dal nulla a un compilatore Haskell per il controllo del tipo è molto difficile. Se inizi scrivendo un interprete per quanto sopra, l'aggiunta del controllo del tipo ad esso dovrebbe essere meno scoraggiante.

Potresti guardare Happy (un parser yacc-like in Haskell) che ha un Haskell parser.

Questo potrebbe essere una buona idea: crea un versione minuscola di NetLogo in Haskell. Qui è il piccolo interprete.

verifica se elio costituirebbe una base migliore su cui basarsi rispetto all'hashell standard.

Uhc / Ehc è una serie di compilatori che abilitano / disabilitano varie funzionalità di Haskell.    http://www.cs.uu.nl/wiki/Ehc/WebHome# What_is_UHC_And_EHC

Mi è stato detto che Idris ha un parser abbastanza compatto, non sono sicuro che sia davvero adatto all'alterazione , ma è scritto in Haskell.

Programming Language Zoo di Andrej Bauer ha una piccola implementazione di linguaggio di programmazione funzionale in qualche modo sfacciato chiamato "minihaskell". Sono circa 700 linee di OCaml, quindi molto facili da digerire.

Il sito contiene anche versioni giocattolo di linguaggi di programmazione in stile ML, Prolog e OO.

Non pensi che sarebbe più facile prendere le fonti GHC e togliere quello che non vuoi, che scriverebbe il tuo interprete Haskell da zero? In generale, ci dovrebbe essere lotto meno sforzi coinvolti nella rimozione rispetto alla creazione / aggiunta di funzioni.

GHC è comunque scritto in Haskell, così tecnicamente che rimane con la tua domanda di un interprete Haskell scritto in Haskell.

Probabilmente non sarebbe troppo difficile rendere il tutto staticamente collegato e quindi distribuire solo il tuo GHCi personalizzato, in modo che gli studenti non possano caricare altri moduli sorgente Haskell. Quanto lavoro ci vorrebbe per impedire loro di caricare altri file di oggetti Haskell, non ne ho idea. Potresti voler disabilitare anche FFI, se hai un sacco di imbroglioni nelle tue classi :)

Il motivo per cui ci sono così tanti interpreti LISP è che LISP è fondamentalmente un predecessore di JSON: un formato semplice per codificare i dati. Questo rende la parte del frontend abbastanza facile da gestire. Rispetto a questo, Haskell, in particolare con le estensioni di lingua, non è il linguaggio più semplice da analizzare. Questi sono alcuni costrutti sintattici che sembrano difficili da ottenere nel modo giusto:

  • operatori con precedenza configurabile, associatività e fissità,
  • commenti nidificati
  • regola di layout
  • sintassi del modello
  • do : blocchi e desugaring al codice monadico

Ognuno di questi, ad eccezione forse degli operatori, potrebbe essere affrontato dagli studenti dopo il corso di costruzione del compilatore, ma distoglierebbe l'attenzione da come funziona effettivamente Haskell. Inoltre, potresti non voler implementare direttamente tutti i costrutti sintattici di Haskell, ma invece implementare passaggi per sbarazzartene. Il che ci porta al nocciolo letterale della questione, gioco di parole completamente inteso.

Il mio suggerimento è di implementare il typechecking e un interprete per Core invece di Haskell completo. Entrambi questi compiti sono già abbastanza complessi da soli. Questo linguaggio, pur essendo un linguaggio funzionale fortemente tipizzato, è molto meno complicato da gestire in termini di ottimizzazione e generazione di codice. Tuttavia, è ancora indipendente dalla macchina sottostante. Pertanto, GHC lo utilizza come linguaggio intermedio e traduce in esso la maggior parte dei costrutti sintattici di Haskell.

Inoltre, non dovresti evitare di usare il frontend di GHC (o di un altro compilatore). Non lo considero un imbroglio poiché i LISP personalizzati usano il parser del sistema LISP host (almeno durante il bootstrap). La pulizia dei frammenti di Core e la loro presentazione agli studenti, insieme al codice originale, dovrebbero consentire di fornire una panoramica di ciò che fa il frontend e del perché sia ??preferibile non reimplementarlo.

Ecco alcuni link alla documentazione di Core utilizzata in GHC:

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top