egg Syntax 3

As promised, I've created a guide to the egg programming language based around its syntax.

Even though it doesn't go into the nitty-gritty of aspects such as type schema, built-in functions or attributes, it's still nearly thirty pages long and took considerably longer than expected to put together. Most of the space is take up with pretty railroad diagrams and example code. But some of the delay was due to the realisation that my thinking about the type system was somewhat muddled. I've tinkered with the EBNF quite a bit in the last few weeks and now feel a lot more comfortable with it.

Short email exchanges with Profs Barbara Liskov and Niklaus Wirth convinced me that the type system should only be prevalent at the interfaces between modules. Within modules it shouldn't get in the way. I've always thought that you spend far too long in languages like C++ fussing over the concrete types (classes) instead of the functionality (functions).

Some computer languages alleviate these pressures by having sophisticated type inference, but that can cause headaches for learners (and non-learners!) who can't grok the inference rules, which are usually fiendish. For example, consider:

  int c = 10;
  var fn = (a, b) => a + b + c;

To a human reader, "fn" is obviously a function that adds its two parameters to "c". But what are the types of its parameters and its return value? Integers? Floats? Strings? A mixture? The compiler could deduce additional information by looking at the later usages of "fn" but this would make the inference of its type "non-local" and therefore potentially confusing.

The egg language has "function expressions" which are like strongly-typed "lambda expressions" (e.g. C++ lambdas):

  int c = 10;
  var fn = float(int a, float b) { return a + b + c };

These are unambiguous, but are a little clumsy. So egg accepts lambda expressions (which it converts to function expressions) providing that the types can be trivially inferred. For example:

  type Adder = float(int, float);
  int c = 10;
  Adder fn = (a, b) => a + b + c;

This isn't much of a "win" in the example above, but if the type is inferred by matching function parameters, it leads to more fluent syntax:

  float process(float(int, float) fn) {
    ...
  }
  int c = 10;
  var result = process((a, b) => a + b + c);

When inferring function types this way, "trivial" means that only the arity (i.e. the number of parameters) of the function is considered. This is further simplified by the restriction that. in egg, lambdas cannot be variadic, only true functions can. For example:

  type Fn0 = void();
  type Fn1 = void(string);
  type Fn3 = void(int,string,int);
  void process(Fn0|Fn1|Fn3 fn, string s, int a, int b) {
    if (Fn0 fn0 = fn) {
      fn0();
    } else if (Fn1 fn1 = fn) {
      fn1(s);
    } else if (Fn3 fn3 = fn) {
      fn3(a, s, b);
    } else {
      throw "internal error";
    }
  }
  process((a, s, b) => { print(a, s, b, "\n"); }); // prints "1+2"

This is quite a sophisticated dispatch mechanism for a language that doesn't permit function overloading. It allows library implementers to support algorithmic optimisation based on lambda signatures without increasing the cognitive load for people not interested in this level of detail.

Oh, I've also updated the A3 poster.