Functions

[Aloso]

Supporting functions are basically variables that you can pass arguments.

• The first tricky part is coming up with a good syntax, since f(x) already has a different meaning than a function call.

My idea: Use f~x (where f is a function and x a parameter) for function calls. Functions must have exactly 1 argument (to accept more, a group can be used; for 0 arguments, a variable is sufficient).

• The second tricky part is, how do we make functions useful, without adding a lot of new syntax (conditionals, loops, etc.) and types (number, boolean, array, closure...)?

My solution to this is pattern matching: A function can be defined multiple times with different patterns.

let permut~(a b) = a b | b a;
let permut~(a b c) = a b c | a c b | b a c | b c a | c a b | c b a;
let permut~(a b c d) =
    | a permut~(b c d)
    | b permut~(a c d)
    | c permut~(a b d)
    | d permut~(a b c);

Pattern matching works by parsing the pattern as an expression, and then checking if the provided argument has the same shape. While checking, variable names in the pattern introduce variables corresponding to the equivalent subexpression. These are called "bindings".

The patterns are tried from top to bottom. When no pattern matches, an error is produced.

Evaluation

Pattern matching is a complex algorithm. It should ensure expressions can be matched with multiple equivalent syntactic forms. For example,

• a* can be matched as a{0,}
• 'ab' can be matched as 'a' 'b'
• ('a') can be matched as 'a'

However, bindings can only match a single Atom or a group, since matching groups with multiple bindings would otherwise have polynomial runtime. Alternatively, we must special-case the situation where a group contains exactly one "wildcard" binding that can match an undelimited Or expression:

# recursively expand a list of expressions
let intersperse~(d first @rest) =
    first d intersperse~(d rest);
let intersperse~(d) = '';

An open question is when variables are expanded, and when normalizations/optimizations occur. I will need to make a more detailed design.