Composite Functions

Very much in the style of ML, you can write factorial as

fn factorial {
    (0) { 1 }
    (n) { n * factorial(n - 1) }
}

and map as

fn map {
    (f, []) { [] }
    (f, h @ t) { f(h) @ map(f, t) }
}

(see Lists for details of [] and @)

Points to Note

• The function is defined with a name, but the alternative arguments and function bodies are in separate clauses within the composite function, like a case statement.
• The alternative arguments must agree in number and type.
• Formal arguments can be symbols, constants, or structures such as lists.
  • When the formal argument is a constant like 0, the actual argument must equal the formal argument.
  • When the formal argument is a symbol like f, it is bound to its actual argument in the normal way.
  • When the formal argument is a structure containing variables like h @ t, the actual argument must match the structure of the formal argument and the equivalent components of the actual argument are bound to the variables.

This can be very powerful. Here's an implementation of quicksort from the tests:

{
    define unsorted = ["hello", "goodbye", "here", "there", "everywhere"];

    fn qsort {
        ([]) { [] }
        (pivot @ rest) {
            lesser = filter(pivot >=, rest)
            greater = filter(pivot <, rest)
            qsort(lesser) @@ [pivot] @@ qsort(greater)
        }
    }

    fn filter {
        (f, []) { [] }
        (f, h @ t) {
            if (f(h)) {
                h @ filter(f, t)
            } else {
                filter(f, t)
            }
        }
    }
    
    qsort(unsorted); // ["everywhere", "goodbye", "hello", "here", "there"]
}

The original functional algorithm for quicksort was pilfered from here. I believe that is written in swift, and it's nice that our implementation is more succinct, readable and importantly more generic than that.

Note we're currying >= and < with the pivot and passing the curried function to filter, and that filter is just removing items from its argument list for which its argument function returns false.

Wildcard

Function arguments also admit the "wildcard" symbol _. This behaves as a constant which will match anything and, because it is a constant it doesn't get bound in the body of the function and so can be used multiple times in an argument list to signify values we aren't interested in, without risking a "symbol already defined" error.

For example here's an implementation of len over a list:

fn len {
    ([]) { 0 }
    (_ @ t) { 1 + len(t) }
}

This len ignores the value in the head of the list.

The structure in a formal argument to a composite function can be given an alias with =. This is only necessary if you want to both access the components and treat the structure as a whole (to avoid copying it.) For example:

fn foo {
    ([]) { [] }
    (x = h @ t) {
        // do stuff with h, t and x
    }
}

In the second function clause, h and t are bound to the head and tail of the list as usual, but additionally x is bound to the whole argument h @ t.

Pseudo-unification

Given the pattern matching done by composite functions, we can get a little extra functionality by allowing duplicate variables in the formal arguments. If a duplicate variable is seen, then the value must be the same for each equivalent actual argument or the match will fail. This becomes powerful in combination with the decomposition of structures, for example here's an implementation of member, making use of this feature.

fn member { // is x a member of a list
    (x, [])    { false }
    (x, x @ t) { true }
    (x, _ @ t) { member(x, t) }
}

In the second clause, if the value being searched for, x, matches the value at the head of the list, then the result is true.

Case Statements

A trivial addition to the language, the construct

switch(x) {
  (10) { foo() }
  (11) { bar() }
}

is rewritten internally to

fn {
  (10) { foo() }
  (11) { bar() }
}(x);

by the parser before evaluation. Note that this allows the full expressiveness of composite functions in case statements.

Implementation

This section won't make much sense if you are reading through the wiki for the first time. You can skip it for now and come back later.

Under the hood, the pattern matching of formal and actual arguments uses the control mechanisms of then between the alternative function applications, and back if a pattern match fails (see Then and Back). To avoid confusion with the normal behaviour of then and back an automatic green cut is inserted at the start of each function body in a composite, reached when the pattern matches. A later development iteration may make this behaviour optional per composite, opening the possibility for a limited form of logic programming.

This means that while composite functions can be curried, they can not be curried at the top level of the read eval print loop, because that would require backtracking beyond the current expression. TL;DR: wrap your currying and use of curried composite functions in a nest (between { and }.)

Up: Functions

Next: Typedef