What is the equivalent of The Little Lisper project in Haskell?
https://softwareengineering.stackexchange.com/questions/307750
-
11-12-2020 - |
Pregunta
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?
Solución
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.
Otros consejos
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").