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?

hawkeye
  • 4,819
  • 3
  • 24
  • 35
  • Possibly the ongoing ["Write you a Haskell"](http://dev.stephendiehl.com/fun/) work can be of some interest. – 9000 Jan 22 '16 at 00:13

2 Answers2

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.

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125
Jules
  • 17,614
  • 2
  • 33
  • 63
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").

Heimdell
  • 111
  • 1