A Tour of Morfa

Indexed symbols - proxy types again and higher-order functions

The most advanced part of the symbolic DSL is indexing support. The purpose of indexing is to be able to define and manipulate symbols in for loops and then aggregate them in one-liner expressions like sum(...). Here is how we do this:

The straightforward part is defining a simplest symbol with integer indices (leaving the implementation details out as usual):

public func $[](s: symbol, i: int[]...): symbol;

// now to use it
's[1,2] * 'y;

Things get a bit more complicated, when we want to express an indexing which is "open" in the sense, that we have a x[i] and i might stand for anything.

public func $[](s: symbol, placeholders: symbol[]...): LazyExpr;

// use it like this:
'x['i];

Here, LazyExpr is a structure which holds information about a "pending" expr waiting for some placeholders to have their values, like the i in x[i] above. Here are some details of how this works:

alias LazyExprF = func(placeholderValues: Dict<symbol, int>): expr;

public struct LazyExpr
{
    var f: LazyExprF;
}
func convert (f: LazyExprF): LazyExpr
{
    return LazyExpr(f);
}
func $()(le: LazyExpr, placeholderValues: Dict<symbol, int>): expr
{
    return le.f(placeholderValues);
}

Basically, a LazyExprF is just a function which is able to return a fully defined expr when given a set of symbol-int pairs that denote the actual values of the indices. So using the x[i] example, 'x['i] becomes 'x[5] when we provide a 'i -> 5 mapping.

The distinction between LazyExpr and LazyExprF is necessary due to some limitations of the conversion mechanism, but conceptually we could just forget this distinction and treat LazyExpr as a function type func(Dict<symbol, int>): expr.

Now it may become clear how to define the body of the $[] we have mentioned before:

public func $[](s: symbol, placeholders: symbol[]...): LazyExpr
{
    return  func(placeholderValue: Dict<symbol, int>): expr
            {
                // here we need to use placeholderValue to fill-out the placeholders
                // and return a regular expr
            };
}

This allows us now to write:

var indexed = 'x['i];
var mapping = ['i -> 5];
indexed(mapping); // same as 'x[5]

A more elaborate $[] is required to be able to index with both symbols and integer values, as in:

'x[5, 'j]

Here is the $[] definition outlined:

template<TIndices...>
public func $[](s: symbol, indices: TIndices): LazyExpr
{
    // here we need to act based on individual types of TIndices[0], TIndices[1], ...
}

Some additional edge-case handling is necessary like coercing simple symbols, values and expressions to LazyExpr and indexing into arrays:

template <T>
public func $[] (collection: T[], placeholders: symbol[]...): LazyExpr;

// and use it like this:
var constants = [1, 2, 3];
constants['i]; // a LazyExpr

template <T>
if (IsNumberType<T> or Is<T, expr> or Is<T, symbol>)
public func convert(t: T): LazyExpr
{
    return  func(placeholderValue: Dict<symbol, int>): expr
            {
                return t;
            };
}

To plug our LazyExpr into the arithmetic of expr, we need the func convert-s mentioned above and some function definitions:

template <ExprType1, ExprType2>
if(Is<ExprType1,LazyExpr> or Is<ExprType2,LazyExpr>)
public func *(a: ExprType1, b: ExprType2): LazyExpr
{
    return  func(placeholderValue: Dict<symbol, int>): expr
            {
                return a(placeholderValue) * b(placeholderValue);
            };
}

sum function

This all builds up to provide one very special functionality: summation (or any other aggregation) of an indexed expression over a range of values:

var my_sum = sum('x['j] + 'y * 'z['i, 'j] * constants['i], 'i in (0..3), 'j in (0..2)) + 42;

For this we need the sum function itself:

public func sum(summand: LazyExpr, symbolRanges: SymbolRange[]...): LazyExpr;

and a way to provide the ranges over which to iterate when adding:

public struct SymbolRange
{
    public var s: symbol;
    public var ids: Range;
}
public func in(s: symbol, ids: Range): SymbolRange
{
    return SymbolRange(s,ids);
}

in being a built-in operator used in for loops in Morfa.