Написать переводчик Haskell в Haskell

Question

Классическим упражнением в программировании является написание интерпретатора Lisp / Scheme на Lisp / Scheme. Сила полного языка может быть использована для создания переводчика для подмножества языка.

Есть ли подобное упражнение для Haskell? Я хотел бы реализовать подмножество Haskell, используя Haskell в качестве движка. Конечно, можно сделать, но есть ли онлайн-ресурсы, на которые можно посмотреть?

---

Вот предыстория.

Я изучаю идею использования Haskell в качестве языка для изучения некоторых концепций в курсе Discrete Structures , который я преподаю. В этом семестре я остановился на Миранде , меньшем языке, вдохновлявшем Хаскелл. Миранда делает около 90% того, что я хотел бы сделать, но Хаскелл делает около 2000%. :)

Так что моя идея состоит в том, чтобы создать язык, обладающий именно теми характеристиками Haskell, которые мне нравятся, и запрещающий все остальное. По мере развития студентов я могу выборочно «включать» различные функции, когда они освоили основы.

Педагогические «языковые уровни» были успешно использованы для преподавания Java и Схема . Ограничивая то, что они могут делать, вы можете запретить им стрелять себе в ногу, пока они еще осваивают синтаксис и концепции, которым вы пытаетесь научить. И вы можете предложить лучшие сообщения об ошибках.

Answer 1

Мне нравится твоя цель, но это большая работа. Пара подсказок:

• Я работал над GHC, и вам не нужна какая-либо часть источников. Hugs - намного более простая и понятная реализация, но, к сожалению, она в C.

• Это небольшая часть головоломки, но Марк Джонс написал прекрасную статью под названием Печать на Haskell на Haskell , которая станет отличной отправной точкой для вашего переднего конца.

Удачи! Определение языковых уровней для Haskell, с подтверждающими данными из класса, принесло бы большую пользу сообществу и определенно публикуемый результат!

Answer 2

Существует полный анализатор Haskell: http://hackage.haskell.org/package/haskell-src-exts

После того, как вы его проанализировали, легко удалить или запретить некоторые вещи. Я сделал это для tryhaskell.org, чтобы запретить операторы импорта, поддерживать определения верхнего уровня и т. Д.

Просто разобрать модуль:

parseModule :: String -> ParseResult Module

Тогда у вас есть AST для модуля:

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

Обширный тип Decl: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

Все, что вам нужно сделать, это определить белый список - какие объявления, импорт, символы, синтаксис доступны, затем пройти AST и выдать «ошибку разбора» на все, что вы не хотите, чтобы они знали пока что. Вы можете использовать значение SrcLoc, прикрепленное к каждому узлу в AST:

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

Нет необходимости повторно реализовывать Haskell. Если вы хотите предоставить более дружественные ошибки компиляции, просто проанализируйте код, отфильтруйте его, отправьте его компилятору и проанализируйте выходные данные компилятора. Если это «не удалось сопоставить ожидаемый тип a с логическим выводом a -> b», то вы знаете, что для функции, вероятно, слишком мало аргументов.

Если вы действительно не хотите тратить время на реализацию Haskell с нуля или возиться с внутренностями Hugs или какой-то глупой реализацией, я думаю, вам следует просто отфильтровать то, что передается GHC. Таким образом, если ваши ученики захотят взять свою кодовую базу и перейти к следующему шагу и написать какой-то действительно полноценный код на Haskell, переход будет прозрачным.

Answer 3

Вы хотите построить свой переводчик с нуля? Начните с реализации более простого функционального языка, такого как лямбда-исчисление или вариант lisp. Для последнего есть довольно хороший викибук под названием Напишите себе схему за 48 часов , дающую прохладное и прагматичное введение в методы синтаксического анализа и интерпретации.

Интерпретация Haskell вручную будет намного более сложной, поскольку вам придется иметь дело с очень сложными функциями, такими как классы типов, чрезвычайно мощная система типов (вывод типов!) И ленивая оценка (методы сокращения).

Таким образом, вы должны определить довольно небольшое подмножество Haskell для работы, а затем, возможно, начать с пошагового расширения примера схемы.

Дополнительно:

Обратите внимание, что в Haskell у вас есть полный доступ к API интерпретаторов (по крайней мере, в GHC), включая парсеры, компиляторы и, конечно, интерпретаторы.

Используемый пакет: подсказка (Language.Haskell. *) . К сожалению, я не нашел онлайн-учебников по этому вопросу и не опробовал сам, но это выглядит довольно многообещающе.

Answer 4

создайте язык, который имеет именно те функции Haskell, которые мне нравятся, и запрещает все остальное. По мере развития учеников я могу выборочно «включать» различные функции, когда они освоили основы.

Я предлагаю более простое (с меньшими затратами труда) решение этой проблемы. Вместо создания реализации на Haskell, в которой вы можете отключить функции, оберните компилятор Haskell программой, которая сначала проверяет, не использует ли код какие-либо запрещенные вами функции, а затем использует готовый компилятор для его компиляции.

Это было бы похоже на HLint (а также вид его противоположности):

HLint (ранее Dr. Haskell) читает программы на Haskell и предлагает изменения, которые, надеюсь, облегчат их чтение. HLint также позволяет легко отключать нежелательные предложения и добавлять собственные настраиваемые предложения.

• Реализуйте свои собственные "предложения" HLint, чтобы не использовать функции, которые вы не разрешаете
• Отключить все стандартные предложения HLint.
• Заставьте свою оболочку запустить измененный HLint в качестве первого шага
• Рассматривать предложения HLint как ошибки. То есть, если HLint «пожаловался», то программа не переходит на этап компиляции

Answer 5

Баскелл - это учебная реализация, http://hackage.haskell.org/package/baskell

Вы можете начать с выбора, скажем, системы типов для реализации. Это примерно так же сложно, как интерпретатор Scheme, http://hackage.haskell.org/package/thih

Answer 6

Если вы ищете подмножество Haskell, которое легко реализовать, вы можете покончить с классами типов и проверкой типов. Без классов типов для вычисления кода на Haskell не требуется вывод типов.

Я написал самокомпилируемый компилятор подмножества Haskell для испытания Code Golf. Он принимает код подмножества Haskell на входе и создает код C на выходе. Мне жаль, что нет более читаемой версии; Я поднял вложенные определения вручную в процессе самостоятельной компиляции.

Для студента, заинтересованного во внедрении переводчика для подмножества Haskell, я бы рекомендовал начать со следующих функций:

• Ленивая оценка. Если переводчик находится на Хаскеле, вам, возможно, не нужно ничего делать для этого.

• Определения функций с сопоставленными с шаблоном аргументами и средствами защиты. Беспокойство касается только переменных, минусов, нулей и шаблонов _.

• Синтаксис простого выражения:

  • Целочисленные литералы

  • Символьные литералы

  • [] (ноль)

  • Применение функции (ассоциативно слева)

  • Инфикс : (минусы, ассоциативно справа)

  • Скобки

  • Имена переменных

  • Имена функций

Конкретнее, напишите интерпретатор, который может запустить это:

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

Проверка типов является важной особенностью Haskell. Однако перейти от ничего к проверке типов компилятора Haskell очень сложно. Если вы начнете с написания интерпретатора для вышеупомянутого, добавление проверки типов к нему должно быть менее пугающим.

Answer 7

Серия компиляторов EHC, вероятно, лучшая ставка: она активно развивается и, кажется, именно то, что вам нужно - серия небольших компиляторов / интерпретаторов лямбда-исчислений, кульминацией которых стал Haskell '98.

Но вы также можете взглянуть на различные языки, разработанные в Типах и языках программирования Пирса , или на интерпретатор Helium (искалеченный Haskell, предназначенный для студентов http://en.wikipedia.org/wiki/Helium_(Haskell)).

Answer 8

Это может быть хорошей идеей - сделать крошечную версию NetLogo в Haskell. Здесь - крошечный интерпретатор.

Answer 9

Вы можете посмотреть на Happy (похожий на yacc парсер в Haskell), который имеет парсер Haskell.

Answer 10

Andrej Bauer Язык программирования Zoo имеет небольшую реализацию чисто функционального языка программирования, который несколько назойливо называют "minihaskell". Это около 700 строк OCaml, поэтому очень легко усваивается.

Сайт также содержит игрушечные версии языков программирования в стиле ML, Prolog и OO.