Question

In the book The Little Lisper, you implement a minimal Scheme in 10 Chapters that is capable of interpreting any chapter in the book.

To me it seems you could do the same for a 'minimal subset of a typed language' to be self-bootstrapping. I'm trying to work out what is feasible.

To me the options are:

  • Simply Typed Lambda Calculus
  • System F
  • Miranda
  • Haskell subset

Assumptions:

  • Note that I'm ignoring the GHC runtime elements like spineless tagless graph-interpreter

My question is: What is the equivalent of the Little Lisper project in Haskell?

Was it helpful?

Solution

There's a quite useful tutorial by Oleg Kiselyov and Chung-chieh Shan, in which they build a very simple implementation of the simply-typed lambda calculus with Hindley-Milner type inference. IIRC they don't write a parser for their language (you write parse trees in Haskell to use it), but this would clearly be a very simple addition that could be based on a typical parsec tutorial.

OTHER TIPS

There is a article "Typing Haskell With Haskell*". It presents the most problematic part of the question - making the type checker/inferrer for the Haskell language (all code included). As far as I can tell, this makes 1-rank polymorphic language.

For 2+-rank poly you could google for "Boxy Types" (however, there is no code like in THIH, but only hellish type math in form of "modus ponens").

Licensed under: CC-BY-SA with attribution
scroll top