HM extraction to C++, Rust


To make code more human-readable HN disallows lambdas and requires all functions to be named. So the actual abstract syntax of HN0 is more complex:

data LetIn a = Let (Definition a) (LetIn a) | In (Expression a) data Definition a = Definition a [a] (LetIn a) | Assign a (LetIn a) | While Expression LetIn | If Expression LetIn LetIn data Expression a = Application (Expression a) [Expression a] | Atom a | Constant Const data Const = ConstString String | ConstInt Int


Unlike many legacy-burdened compilers, HNC optimizer doesn't use peephole-style hand-ordered phases. Instead, it uses a novel algorithm of interleaved dataflow analysis and rewriting to make optimizer smaller, more modular and less fragile (Lerner et al — 2002).

The algebraic approach lets HNC perform common optimizations such as dead code elimination, inlining, copy propagation, arity reduction in less than 500 lines of code specific to HNC. For the subtle algorithms for forward and backward flow traversal, interleaving, speculative rewrites and fixed point computation HNC uses HOOPL — a reusable component of the mature GHC compiler (Ramsey et al — 2010).

Compiler Passes

  1. INF — Infinity Language
  2. BASELIB — Morte Library
  3. WEAK — Weaking (pending)
  4. AST — Implicitly Typed AST
  5. TYPE — Typechecking
  6. FLOW — Control Flow Graph
  7. SCOPE — Name and Scope Reconstruction
  8. INFER — Type Inference
  9. TARGET — Target AST
  10. LLVM — Clang/Rust Compiler
  11. NATIVE — Native Executable