Language Definition

HN Language

HN is an implicitly typed language. The type inference algorithm is complete, so there are no type annotations. The primitives are very similar to the original Milner's proposal for ML language: lexically scoped variables, functions, assignments, loops and conditionals.

However, HN is a compiler intermediate language for human-readable code generation, so there are many limitations compared to what you ususally expect from an ML dialect.



  1. Type-safe but not memory-safe
  2. Controlled effects
  3. No recursion
  4. No currying or partial applications


  1. import is the only way to create data types
  2. functions must be named
  3. stack-allocated variables and closures
  4. can't escape the scope
  5. heap deallocations

Concrete syntax is rigid. Whitespace is not flexible so there is only one way to format the code, you cannot even indent by spaces or put two spaces instead of one. There are no comments either.

hnMain = { g x count = { f xx = _or (eq 0 (mod xx 5)) (eq 0 (mod xx 3)) _if (f x) (sum count x) count } print (natrec g 0 999) }

The abstract syntax is defined in `Parser.AST` module by mutually recursive algebraic data types, nothing unusual or exotic here:

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

The AST has two forms: the parser returns `Definition String` but optimizer converts it into `Definition Label` with unambiguously resolved names.

The `Parser.Parser` module contains two parsers - `program` and `identifier` and Parsec library is the only dependency.

Put `min-parser.hs` to the project root:

import Parser.Parser import Text.Parsec.ByteString main = parseFromFile program "hn_tests/" >>= print $ cabal exec runhaskell -- -Wno-tabs min-parser.hs Right [Definition "hnMain" [] (Let (Definition "g" ["x","count"] (Let (Definition "f" ["xx"] (In "_or" "eq" 0 "mod" "xx" 5 "eq" 0 "mod" "xx" 3)) (In "_if" "f" "x" "sum" "count" "x" "count"))) ( In "print" "natrec" "g" 0 999))]