haskell - Write a Haskell interpreter in Haskell

Question

A classic programming exercise is to write a Lisp/Scheme interpreter in Lisp/Scheme. The power of the full language can be leveraged to produce an interpreter for a subset of the language.

Is there a similar exercise for Haskell? I'd like to implement a subset of Haskell using Haskell as the engine. Of course it can be done, but are there any online resources available to look at?

Here's the backstory.

I am exploring the idea of using Haskell as a language to explore some of the concepts in a Discrete Structures course I am teaching. For this semester I have settled on Miranda, a smaller language that inspired Haskell. Miranda does about 90% of what I'd like it to do, but Haskell does about 2000%. :)

So my idea is to create a language that has exactly the features of Haskell that I'd like and disallows everything else. As the students progress, I can selectively "turn on" various features once they've mastered the basics.

Pedagogical "language levels" have been used successfully to teach Java and Scheme. By limiting what they can do, you can prevent them from shooting themselves in the foot while they are still mastering the syntax and concepts you are trying to teach. And you can offer better error messages.

score 77 · Accepted Answer

私はあなたの目標が大好きですが、それは大きな仕事です. いくつかのヒント:

私は GHC に取り組んできましたが、ソースのどの部分も必要ありません。 Hugsははるかにシンプルでクリーンな実装ですが、残念ながら C で作成されています。
これはパズルの小さなピースですが、Mark Jones はTyping Haskell in Haskellという美しい論文を書きました。これはフロントエンドの素晴らしい出発点となるでしょう。

幸運を！Haskell の言語レベルを、教室での裏付けとなる証拠を使用して特定することは、コミュニティにとって非常に有益であり、間違いなく公開可能な結果になるでしょう!

score 39 · Accepted Answer

完全な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を歩き、あなたがまだ気づいてほしくないものに「解析エラー」を投げます。ASTのすべてのノードに付加されたSrcLoc値を使用できます。

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

Haskellを再実装する必要はありません。よりわかりやすいコンパイルエラーを提供する場合は、コードを解析してフィルタリングし、コンパイラに送信して、コンパイラの出力を解析するだけです。「予想されるタイプと推測されるタイプを一致させることができなかった」場合はa -> b、関数に対する引数が少なすぎる可能性があります。

Haskellを最初から実装したり、Hugsの内部をいじったり、あるいはいくつかのばかげた実装に本当に時間を費やしたいのでなければ、GHCに渡されるものをフィルタリングするだけでよいと思います。そうすれば、学生がコードベースを取得して次のステップに進み、本格的なHaskellコードを記述したい場合、移行は透過的です。

score 24 · Accepted Answer

インタープリターをゼロから構築しますか? ラムダ計算や Lisp バリアントなど、より簡単な関数型言語の実装から始めます。後者については、48 時間以内に自分でスキームを書くという非常に優れたウィキブックがあり、解析と解釈のテクニックをクールで実用的に紹介しています。

手で Haskell を解釈することは、型クラス、非常に強力な型システム (型推論!)、遅延評価 (リダクション手法) などの非常に複雑な機能を処理する必要があるため、はるかに複雑になります。

したがって、使用する Haskell のかなり小さなサブセットを定義してから、Scheme の例を段階的に拡張することから始める必要があります。

添加：

Haskell では、パーサー、コンパイラ、そしてもちろんインタープリターを含むインタープリター API (少なくとも GHC では) に完全にアクセスできることに注意してください。

使用するパッケージはHint (Language.Haskell.*)です。残念ながら、これに関するオンラインチュートリアルを見つけたり、自分で試したりしたことはありませんが、非常に有望に見えます.

score 20 · Accepted Answer

私が望む Haskell の機能を正確に備え、それ以外はすべて許可しない言語を作成します。生徒が進歩するにつれて、生徒が基本を習得したら、さまざまな機能を選択的に「オン」にすることができます。

この問題に対するより簡単な (より少ない作業で) 解決策を提案します。機能をオフにできる Haskell 実装を作成する代わりに、Haskell コンパイラを、許可しない機能をコードが使用していないことを最初にチェックし、次に既製のコンパイラを使用してコンパイルするプログラムでラップします。

これはHLintに似ています(また、その反対のようなものです):

HLint (以前の Dr. Haskell) は Haskell プログラムを読み取り、読みやすくするための変更を提案します。HLint を使用すると、不要な提案を無効にしたり、独自のカスタム提案を追加したりすることも簡単になります。

独自の HLint の「提案」を実装して、許可していない機能を使用しないようにする
標準の HLint 提案をすべて無効にします。
最初のステップとして、変更した HLint をラッパーに実行させる
HLint の提案をエラーとして扱います。つまり、HLint が「不平を言った」場合、プログラムはコンパイル段階に進みません。

score 16 · Accepted Answer

Baskell は教育用の実装です。http://hackage.haskell.org/package/baskell

たとえば、実装する型システムだけを選択することから始めることもできます。これは、Scheme のインタープリターと同じくらい複雑です。http://hackage.haskell.org/package/thih

score 6 · Accepted Answer

EHC シリーズのコンパイラーがおそらく最善の策です。これは積極的に開発されており、まさにあなたが望むものであると思われます。Haskell '98 で最高潮に達した一連の小さなラムダ計算コンパイラー/インタープリターです。

しかし、Pierce のTypes and Programming Languagesで開発されたさまざまな言語、または Helium インタープリター (学生向けの障害のある Haskell http://en.wikipedia.org/wiki/Helium_(Haskell) )を見ることもできます。

score 6 · Accepted Answer

実装が簡単な Haskell のサブセットを探している場合は、型クラスと型チェックを廃止できます。型クラスがなければ、Haskell コードを評価するための型推論は必要ありません。

Code Golf チャレンジ用に自己コンパイル Haskell サブセットコンパイラを作成しました。入力で Haskell サブセットコードを受け取り、出力で C コードを生成します。申し訳ありませんが、より読みやすいバージョンはありません。ネストされた定義は、自己コンパイルする過程で手動で持ち上げました。

Haskell のサブセット用のインタープリターの実装に関心のある学生には、次の機能から始めることをお勧めします。

遅延評価。インタプリタが Haskell にある場合は、このために何もする必要がないかもしれません。
パターンマッチの引数とガードを使用した関数定義。_変数、cons、nil、およびパターンについてのみ心配してください。
簡単な式の構文:
- 整数リテラル
- 文字リテラル
- [](なし)
- 関数適用（左連想）
- インフィックス:(短所、右結合)
- 括弧
- 変数名
- 関数名

より具体的には、これを実行できるインタープリターを作成します。

-- 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 コンパイラに移行するのは非常に困難です。上記のインタープリターを作成することから始めれば、それに型チェックを追加することはそれほど難しくありません。

score 3 · Accepted Answer

これは良い考えかもしれません-HaskellでNetLogoの小さなバージョンを作ってください。これが小さな通訳です。

score 3 · Accepted Answer

Haskell パーサーを備えたHappy (Haskell の yacc に似たパーサー) を見ることができます。

score 2 · Accepted Answer

Andrej Bauer のProgramming Language Zooには、「minihaskell」というやや生意気な名前の、純粋関数型プログラミング言語の小規模な実装があります。約700行のOCamlなので、とても消化しやすいです。

このサイトには、ML スタイル、Prolog スタイル、OO プログラミング言語の玩具バージョンも含まれています。

score 2 · Accepted Answer

Uhc/Ehc は、さまざまな Haskell 機能を有効/無効にする一連のコンパイラです。 http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

score 2 · Accepted Answer

Idrisにはかなりコンパクトなパーサーがあると言われましたが、それが本当に変更に適しているかどうかはわかりませんが、Haskell で書かれています。

score 2 · Accepted Answer

ヘリウムが標準のハスケルよりも優れたベースになるかどうかを確認してください。

score 1 · Accepted Answer

独自の Haskell インタープリタをゼロから作成するよりも、GHC ソースから不要なものを取り除く方が簡単だと思いませんか? 一般的に言えば、機能の作成/追加とは対照的に、機能の削除に伴う労力ははるかに少ないはずです。

とにかくGHCはHaskellで書かれているので、技術的には、Haskellで書かれたHaskellインタープリターの質問にとどまります。

全体を静的にリンクして、カスタマイズした GHCi のみを配布して、学生が他の Haskell ソースモジュールをロードできないようにすることは、おそらくそれほど難しいことではありません。彼らが他のHaskellオブジェクトファイルをロードするのを防ぐためにどれだけの作業が必要になるかについては、私にはわかりません. クラスに不正行為者がたくさんいる場合は、FFIも無効にすることをお勧めします:)

haskell - Write a Haskell interpreter in Haskell

15 に答える 15

Related

Reference