December 12, 2020

Foxtrot

This is a study on programming language design, its name is given for my good friend Mr. Fox, without whom my life would be a lot less interesting.

Foxtrot is a high-level design for a programming language. The primary inspiration is a frequently encountered pattern that is deeply rooted in the L-Value idea underpinning assignment in many imperative programming languages.

I wondered: could you create a language without L-Values, in which data flows left to right and top to bottom?

L-Values: From which ugliness flows

Consider:

async function f(a,b,c,d,e) {
    return await (step2(a, await step1(b, c))
        .step3()
        .step4(async (z) => await step6(d, z)))
        .then(z => z.step5(e));
}

of course this could be made less horrible by storing intermediate values, consider the opposite extreme:

async function f(a,b,c,d,e) {
    const i1 = await step1(b,c)
    const i2 = step2(a, i1)
    const i3 = i2.step3()
    const i4 = await i3.step4(async z => await step6(d,z)
    return = i4.step5(e);
}

These acts of storage require L-Values, a two-fold problem.

  1. When you realize a value needs to be stored for later retrieval, you must go back and insert an L-Value before the expression whose value you want to capture.
  2. L-Values require that you read left to right, top to bottom, then back to top left, and then right again, and so on... it seems like a dance!

Foxtrot provides a syntax that allows you to express f as follows:

f as { -> [a,b,c,d,e],
    [b, c] step1 ...
    [a, @] step2 step3
    [@, {[d, @] step6 ...};]
    step4 ...
    [@, e] step5
}

If this intrigues you, then read on...

Foxtrot: Don't dance

In foxtrot computation almost always goes left to right and top to bottom. Consider these expressions:

-- this is a comment
1 negate      -- produces -1 (minus one)
2 invert      -- produces 0.5 (one half)
[1,2] sum     -- produces 3 (three)
[1,2] count   -- produces 2 (two)

In the above snippet, we call negate, invert, sum, and count operations. Although they are equivalent to functions in other languages, they have some constraints: each operation accepts exactly ONE input and produces exactly ONE output. The inputs and outputs may be structures containing multiple values, but that is incidental.

We can declare the operation average, which takes a collection of numbers and produces their linear average, as follows:

average is Collection Number ~> Number
    as {[count invert, sum] product}

There's a lot happening here, let's create an annotated version:

average           -- create an operation called 'average'
is                -- type constraint for the declared operation
    Collection Number    -- a collection of numbers
    ~>            -- an operation type
    Number        -- that produces a number
as                -- the actual definition of the operation
{                 -- begin a serial scope
                  -- it will get a 'Collection Number' as input
    [             -- begin a parallel scope
        count     -- count the items in the input
        invert    -- invert (1/x) the count of items
        ,         -- end the expression
        sum       -- sum the items in the input
    ]             -- end of the parallel scope
    product       -- multiply together the items in the tuple
}                 -- end of the serial scope, producing the average value

Foxtrot is strongly data-flow oriented. To this end it provides two powerful tools: the serial scope {} and the parallel scope []. Each scope encloses a sequence of comma separated expressions, every expression gets the scope's input as its input. The serial scope provides the final value of the final expression as output, and the parallel scope creates a structure containing all of the produced values.

An illustrative example:

5 {
    [increment, decrement],    -- produces [6,4]
    {increment, decrement},    -- produces 4
    [increment, decrement]
    [sum, count]               -- we have [10, 2] here
    product,                   -- produces 20
}                              -- the enclosing scope produces 20

The @ operator is bound to the current scope's input, and can be used as an identity operator:

5 [3, @, 7] -- produces [3, 5, 7]

The -> operator destructures and binds, allowing us to save a value produced in a serial scope for later use. Note that -> is not valid in parallel scopes.

Using these operators we can thread values through operations that expect inputs structured in specific ways.

string_replace is [Str, Str, Str] ~> Str
as { -> [body, remove, insert],
    [body, remove] split        -- Str.split takes the body first
    [insert, @] join            -- Str.join expects the joiner first
}

There is a third kind of scope: () which is used for tree expressions:

(1 + 2 - 3)           -- tree expression
[1, 2, 3 negate] sum  -- equivalent serial expression

because many computations are not easilly expressed using {} and []. Tree scopes support common unary and binary operators + - * / ^, comparison operators < > <= >= = and boolean operators ! & | ^. There is a special bitfield type that allows bitwise operations, Ints and UInts can be coerced into this type when necessary.

Other types can implement relevant interfaces in order to support all or some of the above operators, and custom operators can be defined using the relevant reserved characters.

Putting a semi-colon ; after a scope or operation turns it into an operation-value that can be passed around and invoked:

{[@, 5] sum}; -> add_five,
4 add_five,                 -- produces 9
invert; {4 @},             -- produces 0.25

In the last example the @ operator was used to get the value of the input, which was the operator invert!

Finally, ... is the await equivalent operator. It accepts any future as an input, and once that future resolves it will provide its output to the next operator in sequence.

===

You've seen enough to go back and read that first example. Maybe you will feel -as I do- that there is an elegance to this style of language... Maybe one day we'll implement it together.