HN

Language Intoduction

Motivation

HNC is an optimizing source-to-source translator in the spirit of PureScript. Like PureScript, it is a call-by-value functional language with type inference, generating human-readable code in another high-level language.

Unlike PureScript, it is designed to be used indirectly as a compiler backend to generate non-abstract non-functional loops with entirely stack-allocated temporaries from a more functional representation.

Damas Milner Core.HNC input language is a non-recursive dialect of ML with call by value reduction, assignment, loops and controlled effects. It is weak enough to be implemented without runtime boxing or heap-allocated closures.

Readable Extraction. As such it is suitable to translation into languages without automatic heap memory management or even without generics such as plain C. The type system is a bare minimum to infer a fixed runtime representation of every variable, annotate types everywhere C++ wants them and take advantage of C++ standard template library. The C++ backend is designed to be easily portable to both static and dynamic mainstream languages such as Java, C, C#, JavaScript or Python.

fold f x0 l = x = x0 p = l while *p != NULL x := f x *p p := p->next x x = fold (\x y -> x + y + 1) 0 l
int x = 0; list_int *p = l; while (*p != NULL) { x += y + 1; p = p->next; }

Refined Optimizer HNC key ingredients are an optimizer using a nameless scopeless untyped control flow graph and scope, name and type reconstruction phase. HNC tries as much as possible to preserve the documentary structure of human-supplied identifiers in its input to generate meaningful human-understandable output in the spirit of PureScript.

Minimal Codebase. The type inference algorithm should be as simple as possible and be ready for formal proof. HNC strive to escape from unneeded features relying on attribute grammars and generic programming.

Hackability. HNC should be considered as a framework or lightweight System F core useful in other projects as a library.

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.

Internal Language

There are expressions and types. Expressions are in essence the lamda caclulus enriched with Let construct. The types are function types, simple constant types, parametrised polymorphic container types and type schemes.

Inductive E := Var: name → E | App: E → E → E | Lambda: name → E → E | Let: name → E → E.Inductive T := Simple: name → T | Parametrized: name → list name → T | Var: name → T | Scheme: list name -> T -> T | Arrow: T → T → T.

Limitations

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.

Common Limitations: Type-safe but not memory-safe; Controlled effects; No recursion; No currying or partial applications; No currying or partial applications.

Unusual Limitations: FFI import is the only way to create data types; All functions must be named; Only stack-allocated variables and closures; Closures can't escape the scope; Explicit heap deallocations.

Code Generation Example

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) } #include <hn/lib.hpp> struct hnMain_impl { static int g(int x, int count) { return 0 == x % 5 || 0 == x % 3 ? count + x : count; }; }; ff::IO hnMain() { typedef hnMain_impl local; return ff::print(ff::natrec(&local::g, 0, 999)); };

AST Inspection

import Parser.Parser import Text.Parsec.ByteString main = parseFromFile program "hn_tests/euler1.hn" >>= 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))]