Escreva um intérprete Haskell em Haskell

Um exercício de programação clássico é escrever um interpretador Lisp / Scheme em Lisp / Scheme. O poder da linguagem completa pode ser aproveitado para produzir um intérprete para um subconjunto da linguagem.

Existe um exercício semelhante para Haskell? Eu gostaria de implementar um subconjunto de Haskell usando Haskell como motor. Claro que isso pode ser feito, mas há algum recurso online disponível para análise?

Estou explorando a ideia de usar Haskell como uma linguagem para explorar alguns dos conceitos em um curso de Estruturas Discretas que estou ensinando. Para este semestre, escolhi Miranda , uma língua menor que inspirou Haskell. Miranda faz cerca de 90% do que eu gostaria que fizesse, mas Haskell faz cerca de 2000%. :)

Minha ideia é criar uma linguagem que tenha exatamente as características do Haskell que eu gostaria e não permita todo o resto. À medida que os alunos progridem, posso "ativar" seletivamente vários recursos, uma vez que tenham dominado o básico.

Os "níveis de linguagem" pedagógicos têm sido usados ​​com sucesso para ensinar Java e Scheme . Ao limitar o que eles podem fazer, você pode evitar que dêem um tiro no próprio pé enquanto ainda estão dominando a sintaxe e os conceitos que você está tentando ensinar. E você pode oferecer mensagens de erro melhores.

Eu amo seu objetivo, mas é um grande trabalho. Algumas dicas:

• Eu trabalhei no GHC, e você não quer nenhuma parte das fontes. Hugs é uma implementação muito mais simples e limpa, mas infelizmente está em C.

• É uma pequena peça do quebra-cabeça, mas Mark Jones escreveu um belo artigo chamado Typing Haskell em Haskell, que seria um ótimo ponto de partida para o seu front end.

Boa sorte! Identificar os níveis de idioma para Haskell, com evidências de apoio em sala de aula, seria de grande benefício para a comunidade e definitivamente um resultado publicável!

Existe um analisador Haskell completo: http://hackage.haskell.org/package/haskell-src-exts

Depois de analisado, eliminar ou proibir certas coisas é fácil. Eu fiz isso para tryhaskell.org para proibir declarações de importação, para oferecer suporte a definições de nível superior, etc.

Basta analisar o módulo:

parseModule :: String -> ParseResult Module

Então você tem um AST para um módulo:

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

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

Tudo que você precisa fazer é definir uma lista branca - de quais declarações, importações, símbolos, sintaxe estão disponíveis, então percorrer o AST e lançar um "erro de análise" em qualquer coisa que você não quer que eles saibam ainda. Você pode usar o valor SrcLoc anexado a cada nó no AST:

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

Não há necessidade de reimplementar Haskell. Se você quiser fornecer erros de compilação mais amigáveis, apenas analise o código, filtre-o, envie-o ao compilador e analise a saída do compilador. Se for um "não foi possível corresponder ao tipo esperado a com o inferido a -> b", você sabe que provavelmente há poucos argumentos para uma função.

A menos que você realmente queira gastar tempo implementando Haskell do zero ou mexendo com os detalhes internos do Hugs, ou alguma implementação idiota, acho que você deveria apenas filtrar o que é passado para o GHC. Dessa forma, se seus alunos quiserem pegar sua base de código e ir para a próxima etapa e escrever algum código Haskell real e totalmente desenvolvido, a transição é transparente.

Você quer construir seu intérprete do zero? Comece implementando uma linguagem funcional mais fácil como o cálculo lambda ou uma variante lisp. Para este último, há um wikibook muito bom chamado Escreva para você mesmo um esquema em 48 horas, que oferece uma introdução legal e pragmática às técnicas de análise e interpretação.

Interpretar Haskell manualmente será muito mais complexo, pois você terá que lidar com recursos altamente complexos como typeclasses, um sistema de tipos extremamente poderoso (inferência de tipos!) E avaliação preguiçosa (técnicas de redução).

Portanto, você deve definir um pequeno subconjunto de Haskell para trabalhar e talvez começar estendendo o exemplo do Scheme passo a passo.

Adição:

Observe que em Haskell, você tem acesso total à API de intérpretes (pelo menos no GHC), incluindo analisadores, compiladores e, claro, intérpretes.

O pacote a ser usado é a dica (Language.Haskell. *) . Infelizmente, não encontrei tutoriais on-line sobre isso nem experimentei sozinho, mas parece bastante promissor.

criar uma linguagem que tenha exatamente as características do Haskell que eu gostaria e não permita todo o resto. À medida que os alunos progridem, posso "ativar" seletivamente vários recursos, uma vez que tenham dominado o básico.

Eu sugiro uma solução mais simples (como com menos trabalho envolvido) para este problema. Em vez de criar uma implementação Haskell onde você pode desativar recursos, envolva um compilador Haskell com um programa que primeiro verifica se o código não usa nenhum recurso que você não permite e, em seguida, usa o compilador pronto para compilá-lo.

Isso seria semelhante ao HLint (e também meio oposto):

HLint (anteriormente Dr. Haskell) lê programas Haskell e sugere mudanças que, esperançosamente, os tornam mais fáceis de ler. O HLint também facilita a desativação de sugestões indesejadas e a adição de suas próprias sugestões personalizadas.

• Implemente suas próprias "sugestões" de HLint para não usar os recursos que você não permite
• Desative todas as sugestões HLint padrão.
• Faça seu wrapper executar seu HLint modificado como uma primeira etapa
• Trate as sugestões HLint como erros. Ou seja, se o HLint "reclamar", o programa não segue para o estágio de compilação

Baskell é uma implementação de ensino, http://hackage.haskell.org/package/baskell

Você pode começar escolhendo apenas, digamos, o sistema de tipos a ser implementado. Isso é tão complicado quanto um interpretador para Scheme, http://hackage.haskell.org/package/thih

A série de compiladores EHC é provavelmente a melhor aposta: está ativamente desenvolvida e parece ser exatamente o que você deseja - uma série de pequenos compiladores / interpretadores de cálculos lambda culminando em Haskell '98.

Mas você também pode olhar para as várias linguagens desenvolvidas em Tipos e Linguagens de Programação de Pierce , ou o interpretador Helium (um Haskell aleijado destinado a estudantes http://en.wikipedia.org/wiki/Helium_(Haskell) ).

Se estiver procurando por um subconjunto de Haskell que seja fácil de implementar, você pode acabar com as classes de tipo e verificação de tipo. Sem classes de tipo, você não precisa de inferência de tipo para avaliar o código Haskell.

Eu escrevi um compilador de subconjunto Haskell auto-compilável para um desafio Code Golf. Ele pega o código de subconjunto Haskell na entrada e produz código C na saída. Lamento não haver uma versão mais legível disponível; Eu levantei as definições aninhadas manualmente no processo de torná-lo autocompilável.

Para um aluno interessado em implementar um intérprete para um subconjunto de Haskell, eu recomendaria começar com os seguintes recursos:

• Avaliação preguiçosa. Se o intérprete estiver em Haskell, talvez você não precise fazer nada para isso.

• Definições de função com argumentos e protetores com correspondência de padrões. Se preocupe apenas com variáveis, contras, nulas e _padrões.

• Sintaxe de expressão simples:

  • Literais inteiros

  • Literais de caracteres

  • [] (nada)

  • Aplicativo de função (associativo à esquerda)

  • Infix :(contras, associativo à direita)

  • Parêntese

  • Nomes de variáveis

  • Nomes de funções

Mais concretamente, escreva um intérprete que possa executar isso:

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

A verificação de tipo é um recurso crucial do Haskell. No entanto, ir do nada para um compilador Haskell de verificação de tipo é muito difícil. Se você começar escrevendo um intérprete para os itens acima, adicionar verificação de tipo a ele deve ser menos assustador.

Você pode olhar para Happy (um analisador semelhante ao yacc em Haskell), que possui um analisador Haskell.

Isso pode ser uma boa ideia - faça uma versão minúscula do NetLogo em Haskell. Aqui está o pequeno intérprete.

veja se o hélio seria uma base melhor para construir do que o haskell padrão.

Uhc / Ehc é uma série de compiladores que habilitam / desabilitam vários recursos do Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

Disseram-me que o Idris tem um analisador bastante compacto, não tenho certeza se ele é realmente adequado para alteração, mas foi escrito em Haskell.

O Programming Language Zoo de Andrej Bauer tem uma pequena implementação de uma linguagem de programação puramente funcional, um tanto atrevidamente chamada "minihaskell". São cerca de 700 linhas de OCaml, muito fáceis de digerir.

O site também contém versões de brinquedo de linguagens de programação estilo ML, estilo Prolog e OO.

Você não acha que seria mais fácil pegar as fontes do GHC e retirar o que você não quer, do que escrever seu próprio intérprete Haskell do zero? De modo geral, deve haver muito menos esforço envolvido na remoção de recursos do que na criação / adição de recursos.

GHC é escrito em Haskell de qualquer maneira, então tecnicamente isso fica com sua pergunta sobre um intérprete de Haskell escrito em Haskell.

Provavelmente não seria muito difícil vincular tudo estaticamente e só então distribuir seu GHCi personalizado, para que os alunos não pudessem carregar outros módulos de origem do Haskell. Não tenho ideia de quanto trabalho seria necessário para impedi-los de carregar outros arquivos de objeto Haskell. Você pode querer desabilitar o FFI também, se você tiver um monte de trapaceiros em suas aulas :)

A razão pela qual existem tantos intérpretes LISP é que LISP é basicamente um predecessor do JSON: um formato simples para codificar dados. Isso torna a parte do frontend bastante fácil de manusear. Comparado a isso, Haskell, especialmente com extensões de linguagem, não é a linguagem mais fácil de analisar. Estas são algumas construções sintáticas que parecem difíceis de acertar:

• operadores com precedência configurável, associatividade e fixidez,
• comentários aninhados
• regra de layout
• sintaxe padrão
• do- bloqueia e desugar para o código monádico

Cada um deles, exceto talvez os operadores, poderia ser abordado por alunos após seu Curso de Construção de Compiladores, mas tiraria o foco de como Haskell realmente funciona. Além disso, você pode não querer implementar todas as construções sintáticas de Haskell diretamente, mas, em vez disso, implementar passes para se livrar delas. O que nos leva ao cerne literal da questão, trocadilho intencional.

Minha sugestão é implementar a verificação de tipos e um interpretador em Corevez de Haskell completo. Ambas as tarefas já são bastante complexas por si mesmas. Esta linguagem, embora ainda seja uma linguagem funcional fortemente tipada, é muito menos complicada de lidar em termos de otimização e geração de código. No entanto, ainda é independente da máquina subjacente. Portanto, o GHC a usa como uma linguagem intermediária e traduz a maioria das construções sintáticas de Haskell para ela.

Além disso, você não deve se esquivar de usar o front-end do GHC (ou de outro compilador). Eu não consideraria isso como trapaça, pois os LISPs personalizados usam o analisador do sistema LISP host (pelo menos durante a inicialização). Limpar Coresnippets e apresentá-los aos alunos, junto com o código original, deve permitir que você dê uma visão geral do que o frontend faz e por que é preferível não reimplementá-lo.

Aqui estão alguns links para a documentação de Corecomo usado no GHC:

• Sistema FC: restrições e coerções de igualdade
• GHC / Como uma biblioteca
• O Coretipo