Напишите интерпретатор Haskell на Haskell

90

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

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


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

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

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

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

Барри Браун
источник
У меня есть диалект WIP Haskell, реализованный с использованием Typing Haskell в Haskell в качестве основы. Здесь есть его демонстрация chrisdone.com/toys/duet-delta. Он не готов к общедоступной версии с открытым исходным кодом, но я могу поделиться с вами исходным кодом, если вы заинтересованы.
Кристофер Сделано

Ответы:

76

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

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

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

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

Норман Рэмси
источник
2
Интересно, по-прежнему ли верен комментарий о GHC. GHC сложен, но достаточно хорошо задокументирован. В частности, внутренние Notesполезны для понимания низкоуровневых деталей, а глава о GHC в «Архитектуре приложений с открытым исходным кодом» дает отличный обзор высокого уровня.
sjy
37

Есть полный парсер 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, переход будет прозрачным.

Кристофер Сделано
источник
24

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

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

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

Дополнение:

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

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

Дарио
источник
12
Обратите внимание, что вывод типа на самом деле очень простой алгоритм из 20-30 строк. он прекрасен своей простотой. Ленивое вычисление также не так сложно закодировать. Я бы сказал, что трудность заключается в безумном синтаксисе, сопоставлении с образцом и просто в большом количестве материала в языке.
Claudiu
Интересно - можете ли вы разместить ссылки на алгоритмы вывода типов?
Дарио
5
Да, посмотрите эту бесплатную книгу - cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26 - она ​​находится на странице 273 (289 в pdf). Псевдокод alg находится на P296.
Claudiu
1
Также есть реализация (?) Алгоритма вывода / проверки типов в « Реализации языков функционального программирования ».
Фил Армстронг
1
Однако вывод типов с помощью классов непросто.
Кристофер Сделано
20

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

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

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

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

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

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

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

Gwern
источник
6

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

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

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

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

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

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

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

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

    • [] (ноль)

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

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

    • Скобки

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

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

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

-- 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 с проверкой типов очень сложно. Если вы начнете с написания интерпретатора для вышеперечисленного, добавление к нему проверки типов должно быть менее сложной задачей.

Джои Адамс
источник
«Ленивое вычисление. Если интерпретатор находится на Haskell, возможно, вам не придется ничего делать для этого». Это может быть неправдой. См. Статью Нейлора в haskell.org/wikiupload/0/0a/TMR-Issue10.pdf для получения дополнительной информации о реализации ленивого интерпретатора в Haskell.
Джаред Апдайк,
3

Вы можете посмотреть на Happy (yacc-подобный парсер в Haskell), у которого есть парсер Haskell.

Кэти Ван Стоун
источник
3

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

Клаудиу
источник
Ссылки мертвы. Есть ли шанс, что этот контент все еще существует где-то еще? Мне было бы любопытно ...
Николас Пайетт
хм, это была запись в блоге, и я понятия не имею, какие ключевые слова использовать для ее поиска. Хороший урок для включения более существенной информации при предоставлении ссылки ...
Клаудиу
1
Поиск Google по запросу "netlogo haskell" обнаруживает ... этот вопрос. Во всяком случае, ничего страшного. Благодарность!
Николя Пайетт,
2

Посмотрим, станет ли гелий лучшей базой для развития, чем стандартный haskell.

Мартин ДеМелло
источник
2

Мне сказали, что у Идриса довольно компактный парсер, не уверен, действительно ли он подходит для переделки, но он написан на Haskell.

Джефф Берджес
источник
2

Зоопарк языков программирования Андрея Бауэра есть небольшая реализация чисто функционального языка программирования, несколько дерзко названного «minihaskell». Это около 700 строк OCaml, поэтому его очень легко усвоить.

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

Никлас
источник
1

Вам не кажется, что было бы проще взять исходники GHC и вырезать то, что вам не нужно, чем написать свой собственный интерпретатор Haskell с нуля? Вообще говоря, удаление данных требует гораздо меньше усилий. функций чем создание / добавление функций.

В любом случае GHC написан на Haskell, так что технически это остается с вашим вопросом об интерпретаторе Haskell, написанном на Haskell.

Вероятно, не будет слишком сложно сделать все это статически связанным, а затем распространять только ваш настроенный GHCi, чтобы студенты не могли загружать другие исходные модули Haskell. Что касается того, сколько работы потребуется, чтобы предотвратить загрузку других объектных файлов Haskell, я понятия не имею. Вы можете также отключить FFI, если у вас в классах куча читеров :)

Марк Рушаков
источник
1
Это не так просто, как кажется, поскольку многие функции зависят от других. Но, возможно, ОП просто хочет не импортировать Prelude, а вместо этого предоставить свой собственный. Большая часть Haskell, который вы видите, - это обычные функции, а не специфические особенности среды выполнения. (Но, конечно, много есть .)
jrockway
0

Причина, по которой существует так много интерпретаторов LISP, заключается в том, что LISP по сути является предшественником JSON: простой формат для кодирования данных. Это делает интерфейсную часть довольно простой в использовании. По сравнению с этим Haskell, особенно с языковыми расширениями, не самый простой язык для синтаксического анализа. Вот некоторые синтаксические конструкции, которые сложно понять:

  • операторы с настраиваемым приоритетом, ассоциативностью и фиксацией,
  • вложенные комментарии
  • правило макета
  • синтаксис шаблона
  • do- блоки и десугарирование в монадический код

Каждый из них, за исключением, может быть, операторов, может быть изучен студентами после прохождения курса построения компилятора, но это отвлечет внимание от того, как на самом деле работает Haskell. В дополнение к этому вы можете не захотеть напрямую реализовывать все синтаксические конструкции Haskell, а вместо этого реализуете проходы, чтобы избавиться от них. Это подводит нас к сути проблемы, полностью задуманной игре слов.

Я предлагаю реализовать проверку типов и интерпретатор для Core вместо полноценного Haskell. Обе эти задачи уже сами по себе довольно сложные. Этот язык, хотя и является строго типизированным функциональным языком, гораздо менее сложен в плане оптимизации и генерации кода. Однако он по-прежнему не зависит от базовой машины. Поэтому GHC использует его как промежуточный язык и переводит на него большинство синтаксических конструкций Haskell.

Кроме того, вы не должны уклоняться от использования интерфейса GHC (или другого компилятора). Я бы не стал считать это обманом, поскольку пользовательские LISP используют синтаксический анализатор хост-системы LISP (по крайней мере, во время начальной загрузки). Очистка Coreфрагментов и представление их студентам вместе с исходным кодом должны позволить вам сделать обзор того, что делает интерфейс, и почему предпочтительнее не реализовывать его заново.

Вот несколько ссылок на документацию, Coreиспользуемую в GHC:

MauganRa
источник