aa

Cliff Click Language Hacking

To-the-metal performance: every abstraction used can be peeled away, yielding code that you would expect from a tightly written low-level program. This is a primary driver for me, the guy who's been writing compilers for high performance computing (including Java) all my life. Ease-of-programming is a close second, but only after you've declared that performance is not your main goal. Hence I support syntactic sugar on expensive operations (e.g. accidental auto-boxing in a hot loop can cost you 10x in speed) but only if the type-system cannot remove it and you've not declared that you are programming for speed.

Modern: Statically typed. Functional programming with full-strength type inference - types are everywhere optional. Minimal syntax. REPL (i.e. incremental static typing) and separate compilation. Typed C-style macros: most syntax errors in dead code are typed.

My intent is a modern language that can be used where C or C++ is used: low-level high-performance work and a systems implementation language (e.g. OS's, device drivers, GC's), but bring in all the goodness of the last 20 years of language improvements.

The language is intended to "look like" C or Java, but with all types optional and all keywords removed. The whole no-keywords thing is an experiment I may back away from; a primary goal is to be readable - sometimes keywords feel like clutter and sometimes they are an code-anchor for your scanning eye.

I specifically intend to look at real-time constraints, and the notion of Time in a language.

Part of modern coding is the use of Garbage Collection, and the structured use of malloc/free - so I intend to add Rust-style memory management.

Part of modern coding is the use of multiple cores, so I intend to explore a couple of different concurrency models. A notion of a true 'final' field, made with a final-store (as opposed to declared as a final type) - you can make cyclic final structures, and once final all future reads will see the final value. No odd exceptions for "early publishing" a pointer.

And of course, this is a Work-In-Progress!!!!

GRAMMAR

SIMPLE EXAMPLES

LARGER EXAMPLES:

Build a list from tuples; first element is payload and second element is the rest of the list, with nil terminating the list:

  lst = (1,(2,(3,0)))

Find and return the first element of a list passing a predicate:

find = { list pred ->     // find is a 2-arg function
  !list ? ^0;             // if list is nil, return nil
  pred(list.0) ? ^list.0; // if the 0-element passes the predicate, return it
  find(list.1,pred);      // otherwise, recursively find on the rest of the list
}

Find the first odd element:

find(lst,{e -> e&1})

...which returns 1.

Here is a simple map call, mapping fun over the list elements:

map = { list fun ->                // map is a 2-arg function
  list                             // list is nil-checked
  ? (map(fun,list.1),fun(list.0))  // return a list (tuple) composed of apply map to the 1-element and fun to the 0-element
  : 0                              // return a nil
}

Double the list elements:

map(lst,{x -> x+x})

Returns (2,(4,(6,0))).

Both map and + calls are generic, so a list of strings work as well:

map( ("abc", ("def", 0)), {x -> x+x} )

Returns ("abcabc", ("defdef", 0)).

Full closures.

Here gen reduces a pair of functions to inspect or increment the private counter.

gen = {cnt:=0;({cnt++},{cnt})};

Calling gen twice makes two counters (and two sets of get/inc functions).

tmp:=gen(); incA=tmp.0;getA=tmp.1;
tmp:=gen(); incB=tmp.0;getB=tmp.1;

The two different sets of functions work on independent counters:

incA();incB();incA(); getA()*10+getB()

Returns: 2*10+1 or 21.

while and for are ordinary variables

while takes a pred predicate function and a body function. pred is tested on every iteration, and looping stops when false. body is executed for side-effects.

  while = { pred ->   // while is assigned to be a function which takes a predicate
    { body ->         // and a body
      pred() ?        // The predicate is evaluated; if false exit with 0
    (body();          // Else evalute the body for side effects
     while pred body) // And loop
    }
  };

Computing an array of squares:

ary=[100];
i:=0;
while {i++ < #ary} {
  ary[i]:=i*i
};
ary

Returns [int64], with the elements filled with the squares from 0 to 99.

for also takes a pred a body function. The predicate is executed and if it returns nil the for-loop returns nil. Then the body is executed, and if it returns a truthy value, that is the for-loop's result, otherwise the loop repeats. Early function exit works in the normal way for both pred and body. To continue, do an early return from the body with nil: ^. To break, do an early return from the body with not-nil: ^1.

  for = { pred->      // for is assigned to be a function which takes a predicate
    { body ->         // and a body
      pred() ?        // predicate is evaluated; if false, exit with 0
      // Else evaluate body.  If true, exit with that value
      ((tmp=body()) ? ^tmp; 
       for pred body) // Else loop
    }
  };

Return the index of the element matching e, or -1 if not found:

find = { ary e ->
  i:=0;
  idx = for { i++ < #ary } {
    ary[i]==e ? i+1     // if found, exit index+1 (so non-zero)
  };
  idx-1                 // if nil exit, then not-found so -1. 
}

This can be tightened by realizing that for is not a special form, but simply a function with a return value:

find = { ary e ->
  i:=0;
  for { i++ < #ary } {
    ary[i]==e ? i+1     // if found, exit index+1 (so non-zero)
  } -1                  // if nil exit, then not-found so -1. 
}

The AA Type System

AA uses a combined Hindley-Milner and Global Constant Propagation typing.

Extensions to Hindley-Milner

AA treats HM as a Monotone Analysis Framework; converted to a worklist style. The type variables are monotonically unified, gradually growing over time - and this is treated as the MAF lattice. Some normal Algo-W work gets done in a pre-pass; e.g. discovering identifier sources (SSA form), and building the non-generative set. Because of the non-local unification behavior type variables include a "dependent" set; a set of elements put back on the worklist if this type unifies, beyond the expected graph neighbors.

The normal HM unification steps are treated as the MAF transfer "functions", taking type variables as inputs and producing new, unified, type variables. Because unification happens in-place (normal Disjoint-set Union, the transfer "functions" are executed for side effects only, and return a progress flag. The transfer functions are virtual calls. Some steps are empty because of the pre-pass (Let,Con).

HM base (ground) types include anything from the GCP lattice, and are generally sharper than e.g. 'int'. Bases with values of '3' and the string "abc" are fine.

HM includes polymorphic structures and fields (structural typing not duck typing), polymorphic nil-checking and an error type variable. Both HM and GCP types fully support recursive types, e.g.{ f -> (f f) } is well typed with the recursive type A:{ A -> B }.

HM errors keep all the not-unifiable types, all at once. Further unifications with the error either add a new not-unifiable type, or unify with one of the prior types. These means that types can ALWAYS unify, including nonsensical unifications between e.g. the constant 5 and a struct @{ x,y }. The errors are reported when a type prints.

Because of the error handling, dead errors are not reported and not considered a typing error. It is OK to have type errors in dead code.

Unification typically makes many temporary type variables and immediately unifies them. For efficiency, this algorithm checks to see if unification requires an allocation first, instead of just "allocate and unify". The major place this happens is identifiers, which normally make a "fresh" copy of their type variable, then unify. I use a combined "make-fresh-and-unify" unification algorithm there. It is a structural clone of the normal unify, except that it lazily makes a fresh-copy of the left-hand-side on demand only; typically discovering that no fresh-copy is required.

To engineer and debug the algorithm, the unification step includes a flag to mean "actually unify, and report a progress flag" vs "report if progress". The report-only mode is aggressively asserted for in many places; all program points that can make progress are asserted as on the worklist.

Extensions to Global Constant Propagation

Global Constant Propagation (GCP) is an extension to the algorithm with the same name, applied to typing. GCP is another Monotone Analysis Framework with types from a Lattice. The lattice is a symmetric complete bounded (ranked) lattice, the meet is commutative and associative. The lattice has a dual (symmetric), and join is defined using meet and dual: ~(~x meet ~y).

The lattice contains the usual presentation for integers (a Top, constants, and a Bottom), extended with ranges (e.g. int1, int8, uint8, int32, int64). The lattice also contains a representation for IEEE754 numbers (flt32, flt64), for pointers and structures, and for functions. The lattice contains unique indices for each function (internally called a fidx), which are used to build a precise Call Graph at typing time. Similarly, the lattice contains unique indices for new allocation sites (internally called an alias) which are used to determine aliasing relationships up to equivalence-class precision. All types in the lattice understand nil exactly, e.g. there are nil-able and not-nil variants of all lattice elements. There are several other extensions not mentioned here.

Any value which can fit in a machine register (or a small count of them) is typed as a Scalar. This includes integers, floats, pointers and code pointers, and excludes structures and the code itself.

All types which contain other types (e.g. structures or functions) fully understand recursive types.

GCP is normally a forwards flow algorithm, flowing precise types forwards from the initial program point to the exit. This GCP also computes liveness, as a backwards flow algorithm with only slightly less precision than the forwards variant. As mentioned above in the HM presentation, errors in dead (not live) code are ignored.

GCP gets the normal MAF treatment, no surprises here. GCP may be run in two modes: optimistic vs pessimistic. In the pessimistic variant, the program always correct; the algorithm can be stopped at any point. However, locally correct transformations can be made (such as folding "3+5" into "8", or removing dead code). This pessimistic version is run as a pre-pass before the main combined algorithm to cleanup "easy" things. In the optimistic variant, the analysis must run to completion before the typing is correct, types are not incrementally correct. However, the optimistic variant delivers a more precise type (allows typing strictly more programs).

Combining Hindley-Milner and Global Constant Propagation

The combined algorithm includes transfer functions taking facts from both MAF lattices, producing results in the other lattice.

For the GCP → HM direction, the HM 'if' has a custom transfer function instead of the usual one. Unification looks at the GCP value, and unifies either the true arm, or the false arm, or both or neither. In this way GCP allows HM to avoid picking up constraints from dead code.

Also for GCP → HM, the HM ground terms or base terms include anything from the GCP lattice. E.g. both '3' and 'int64' are valid HM base terms.

For the HM → GCP direction, the 'apply' step has a customer GCP transfer function where the result from a call gets lifted (JOINed) based on the matching GCP inputs - and the match comes from using the same HM type variable on both inputs and outputs. This allows e.g. "map" calls which typically merge many GCP values at many applies (call sites) and thus end up being weakly typed as a Scalar to Scalar, to improve the GCP type on a per-call-site basis.

Test case aa/src/test/java/com/cliffc/aa/HM/TestHM.java:test45 demonstrates this combined algorithm, with a program which can only be typed using the combination of GCP and HM.

Since GCP is a forwards flow algorithm, functions that escape at the top level (e.g. module level or whole typing-event level) have to decide how they are called. GCP might assume they are not called (and uncalled functions are dead), or might assume they are called with the worst possible arguments (which would typically lead to type errors). Instead GCP uses the HM type variables, converted to the GCP lattice, to get initial types.

Core AA

There is a highly restricted subset of AA (really a plain lambda calculus) in aa/src/main/java/com/cliffc/aa/HM/HM.java to demonstrate this type system.

BNF for the "core AA" syntax:

   e  = number | string | primitives | (fe0 fe1*) | { id* -> fe0 } | id | id = fe0; fe1 | @{ (label = fe0)* }
   fe = e | fe.label                 // optional field after expression

BNF for the "core AA" pretty-printed types:

   T = base | { T* -> T } | @{ (label = T)* } | T? | X:T | X | (Error T+)
   base = any GCP lattice element, all are nilable
   Multiple stacked T????s collapse

Done Stuff

• Static typing; types optional & fully inferred at every place.
• Nil-ptr distinguished; nil/notnil types (e.g. Kotlin)
• Structural-typing (duck typing with strong types). Interfaces.
• Anonymous (and named) structure types.
• Functional; 1st class functions. All functions are anonymous.
• REPL
• Dynamic code-gen; no seperate compilation step. Load Source & Go.
• Limited overloads.
• Overloading ops. No ambiguity / easy-to-read rules.
• By default multi-arg ops are overloaded.
• Direct SSA style code writing; no 'let' keyword.
• default "x=1" makes a "val" until scope runs out (cannot re-assign)
• Reassignment "x:=1" for mutable variables
• Primitive values; int overflow OK;
• Sub-byte ranges. Julia-like math typing.
• Can type-name primitives, but no e.g. physical-unit-type math

Ideas, Desirables

• H-M style typing.
• JIT'ing.
• {GC,Ref-Counting}: Ponder both vs requiring e.g. lifetime management (easy by just raising scope).
• No exceptions?!!? Same as Elm: allow tagged union returns with an error return vs a non-error return. Force user to handle errors up&down the stack.
• Lexical scope destructors.
• Can ask for Int for BigInteger; unboxed arrays.
• Pattern-matching too handy looking, need to have it
• Parallel (and distributed) but also deterministic
• "eval"
• Monads? i/o, side-effect monads.
• "back tick" computing, meta-computing

lifetime:

• Distributed ref-cnting? (or Dist-GC?)
• Ref-Counting does NOT given "immediate" destructor execution, but "soon".
• Guaranteed to count down & release before the next instance of exact same constructor constructs?
• Guaranteed to count down & release before the next loop backedge? Before base of containing loop?
• Built-in "pools" for bulk-remove? Same as ref-counting.
• Rust-style memory lifetime management; linear logic owner; borrowing; guaranteed death

concurrency:

• Pony-style concurrency management
• CAS built-in lang primitive: 'res := atomic(old,new)'; JMM
• CPS for threads/concurrency;
• not really actors but spawn/fork worker threads, run until they 'join' with parent.
• Transactions-for-shared-memory-always (Clojure style)

types and name spaces and nils:

• OOP namespaces (distinguished "this"; classes; single-inheritance vs interfaces)
• Modules: independent shipping of code.
• Elm-style union types
• Single inheritance (or none; composition also works).
• physical-unit-types, esp for arrays; e.g. "fueltank_size:gallon", and "speed:mile/hour", with auto-conversions

performance types:

• performance types: "no autoboxing, no big-int, no dynamic dispatch, no serial loops?"
• also: No GC allocations (only ref-counting & rust-style lifetime management).
• Runs in "O(1) time"? Runs in "O(N) time"?
• associated affine-value types: "this int is equal to that int, plus or minus a constant".

`fun copyInt2Dbl( src:[]int32, dst:[src.len+0]d64 )...`

OR

`fun copyInt2Dbl( len:int32, src:[len]int32, dst:[len]d64 )...`

OR

`fun slide( len:int32, off:int32, src:[>=len]a, dst[>=len+off]a )...`

maps & parallel loops:

• maps-over-collections; default to parallel
• parallel/distributed collections; deterministic
• maps-with-folds require a associative fold op (and will run log-tree style)
• maps-without-assoc-folds are serial loops: code it as a loop
• user-spec'd iter types; for-loop syntax-sugar

serial loops:

• For-loops with early-exit and Python else-clause

for( foo in foos )
  if( isAcceptable(foo) )
    break;
  else return DidNotFindItError()

• To detect never-ran vs ran-but-not-exited:

    if( foos.empty() ) return foos_was_empty
    else
      for( foo in foos )
        if( isAcceptable(foo) )
          break;
      else return no_acceptable_in_foos()

misc:

• embed 'fact' in string: "milage=%(dist/gals) mph". The expression (dist/gals) is a standard paren-wrapped 'fact' from the grammar.
• multi-value-returns OK, sugar over returning a temp-tuple
• Extra "," in static struct makers OK: "{'hello','world',}"
• Tail-recursion optimization.
• "var" can be reassigned but requires type keyword: "x:= 1"

Getting started

Download dependencies:

make lib

Build:

make

Run checks:

make check

Launch the REPL:

java -jar build/aa.jar