C++ Haskell interpreter with GADTs + Type Families + Rank-n types
Hi all, I don't want to oversell this, but in case anyone is interested, I've been working on a Haskell interpreter that is written in C++. This isn't intended to compete with GHC. It doesn't generate machine code, and it is not fast. However, I had a reason to try and implement Haskell typechecking in C++. So if anyone is interested in how to write their own Haskell compiler, then this might possibly be of interest. Otherwise, probably not. So far I have: 1. Parser 2. Renamer - hacky. Infix handling is a separate pass. 3. Typechecker - standard constraints + rank n types + GADTS + type families. But no newtypes and no coercions. 4. Desugarer - the desugarer generates a language w/o type-level lambdas or coercions. 5. Optimizer - inlining, let-floating, case-of-case, etc. No SpecConstr. No Rules. 6. Translation to de-Bruijn notation prior to execution (See Sestoft 1997, "Deriving a lazy abstract machine") 7. Interpreter - a special-purpose dependency-tracking interpreter. The revelant code is here: https://github.com/bredelings/BAli-Phy/tree/master/src/computation After compiling the executable, you would run use it to run a Haskell program like this: bali-phy --run-module Main.hs Tests are in: https://github.com/bredelings/BAli-Phy/tree/master/tests/haskell -BenRI
On Thu, 19 Jan 2023, Benjamin Redelings wrote:
I don't want to oversell this, but in case anyone is interested, I've been working on a Haskell interpreter that is written in C++. This isn't intended to compete with GHC. It doesn't generate machine code, and it is not fast.
How does it compare to Hugs? Ok, Hugs does not support type families, only functional dependencies.
On 1/20/23 4:34 AM, Henning Thielemann wrote:
On Thu, 19 Jan 2023, Benjamin Redelings wrote:
I don't want to oversell this, but in case anyone is interested, I've been working on a Haskell interpreter that is written in C++. This isn't intended to compete with GHC. It doesn't generate machine code, and it is not fast.
How does it compare to Hugs? Ok, Hugs does not support type families, only functional dependencies.
I think this uses a different approach to solving constraints than Hugs. 1. Unifying types a and b results in recording a "wanted" constraint (a ~ n). You can manually write constraints like (a ~ F b). 2. Wanted constraints are deferred -- they are handled later in the "solver". 3. Typechecking now makes heavy use of nested "implication constraints": exists a b c. givens => wanteds 4. Defaulting is postponed until the whole program has been analyzed by the typechecker. 5. Error messages likewise postpone until after defaulting. Basically you look at wanted constraints, including looking into nested implication constraints, and complain about any constraints that remain. Much of this is described in the OutsideIn(X) paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/jfp-outs... I don't think this was around when Hugs was active.
participants (2)
-
Benjamin Redelings -
Henning Thielemann