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.

Solution 1

I love your goal, but it's a big job. A couple of hints:

• I've worked on GHC, and you don't want any part of the sources. Hugs is a much simpler, cleaner implementation but unfortunately it's in C.

• It's a small piece of the puzzle, but Mark Jones wrote a beautiful paper called Typing Haskell in Haskell which would be a great starting point for your front end.

Good luck! Identifying language levels for Haskell, with supporting evidence from the classroom, would be of great benefit to the community and definitely a publishable result!

Solution 2

There is a complete Haskell parser: http://hackage.haskell.org/package/haskell-src-exts

Once you've parsed it, stripping out or disallowing certain things is easy. I did this for tryhaskell.org to disallow import statements, to support top-level definitions, etc.

Just parse the module:

parseModule :: String -> ParseResult Module

Then you have an AST for a module:

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

The Decl type is extensive: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

All you need to do is define a white-list -- of what declarations, imports, symbols, syntax is available, then walk the AST and throw a "parse error" on anything you don't want them to be aware of yet. You can use the SrcLoc value attached to every node in the AST:

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

There's no need to re-implement Haskell. If you want to provide more friendly compile errors, just parse the code, filter it, send it to the compiler, and parse the compiler output. If it's a "couldn't match expected type a against inferred a -> b" then you know it's probably too few arguments to a function.

Unless you really really want to spend time implementing Haskell from scratch or messing with the internals of Hugs, or some dumb implementation, I think you should just filter what gets passed to GHC. That way, if your students want to take their code-base and take it to the next step and write some real fully fledged Haskell code, the transition is transparent.

Solution 3

Do you want to build your interpreter from scratch? Begin with implementing an easier functional language like the lambda calculus or a lisp variant. For the latter there is a quite nice wikibook called Write yourself a Scheme in 48 hours giving a cool and pragmatic introduction into parsing and interpretation techniques.

Interpreting Haskell by hand will be much more complex since you'll have to deal with highly complex features like typeclasses, an extremely powerful type system (type-inference!) and lazy-evaluation (reduction techniques).

So you should define a quite little subset of Haskell to work with and then maybe start by extending the Scheme-example step by step.

Addition:

Note that in Haskell, you have full access to the interpreters API (at least under GHC) including parsers, compilers and of course interpreters.

The package to use is hint (Language.Haskell.*). I have unfortunately neither found online tutorials on this nor tried it out by myself but it looks quite promising.

Solution 4

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.

I suggest a simpler (as in less work involved) solution to this problem. Instead of creating a Haskell implementation where you can turn features off, wrap a Haskell compiler with a program that first checks that the code doesn't use any feature you disallow, and then uses the ready-made compiler to compile it.

That would be similar to HLint (and also kind of its opposite):

HLint (formerly Dr. Haskell) reads Haskell programs and suggests changes that hopefully make them easier to read. HLint also makes it easy to disable unwanted suggestions, and to add your own custom suggestions.

• Implement your own HLint "suggestions" to not use the features you don't allow
• Disable all the standard HLint suggestions.
• Make your wrapper run your modified HLint as a first step
• Treat HLint suggestions as errors. That is, if HLint "complained" then the program doesn't proceed to compilation stage

Solution 5

Baskell is a teaching implementation, http://hackage.haskell.org/package/baskell

You might start by picking just, say, the type system to implement. That's about as complicated as an interpreter for Scheme, http://hackage.haskell.org/package/thih

View more solutions

Comments

[jrockway]

This is not as easy as it sounds, as many features depend on others. But perhaps the OP just wants to not import Prelude and instead provide his own. Most of Haskell that you see are normal functions, not specific features of the runtime. (But of course, a lot are.)

[Claudiu]

Note that type-inference is actually a really easy, 20-30 line algorithm. it's beautiful in its simplicity. Lazy evaluation is also not so hard to encode. I'd say the difficulty lies in the insane syntax, the pattern matching, and just the large amount of stuff in the language.

[Hans-Kristian Norum Eidesen]

Interesting - Can you post links for the type-inference algos?

[Claudiu]

Yeah, check out this free book - cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26 - , it's on page 273 (289 of the pdf). The alg pseudocode is on P296.

[Phil Armstrong]

There's also an implementation of a (the?) type-inference / checking algorithm in "The Implementation of Functional Programming Languages".

[Nicolas Payette]

The links are dead. Any chance this content still exists somewhere else? I'd be curious...

[Claudiu]

hmm it was a blog post and I have no idea what keywords to use to search for it. A good lesson to include more substantial info when providing a link...

[Nicolas Payette]

A Google search for "netlogo haskell" turns up... this question. Anyway, no big deal. Thanks!

[Jared Updike]

"Lazy evaluation. If the interpreter is in Haskell, you might not have to do anything for this." This may not be true. See Naylor's article in haskell.org/wikiupload/0/0a/TMR-Issue10.pdf for more info on implementing a lazy interpreter in Haskell.

[sjy]

I wonder if the comment about GHC is still accurate. GHC is complex, but it is quite well-documented. In particular, the internal Notes are helpful in understanding low-level details, and the chapter on GHC in The Architecture of Open-Source Applications provides an excellent high-level overview.

[Christopher Done]

Type inference with type-classes isn't simple, though.