3

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?

3

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.

1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.