December 12, 2020

Foxtrot

This is a study in 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 that I don't have time to implement. I draw inspiration primarily from languages I work with: SQL, Typescript, and Rust, I have toyed around in Haskell and Idris because I am fascinated by them, but I have not put any code in production with them, and finally I'm a YAML guy, I'm ambivalent about json, and I abhor TOML and XML (and its derivatives).

Foxtrot is partially an agglomeration of ideas from all these languages, with a completely different syntax (although in the grand scheme of things syntax is not that important). Foxtrot's main priorities are:

  1. Meta-programming
  2. Special syntax for common structures

Here's some reasoning:

  1. I spend so much time in schema-land, I really wish I got the benefits of strict typing all the way from the code out through persistence layers and protocols. There are some very clever frameworks for Rust and Typescript that accomplish this, but to my taste they are too much like working around the language than working through the language.
  2. It seems to me that the limits of syntax are always found by interacting with deep structures, and in the end most meaningful programming work is concerned with the transformation of one deep structure into another. An elegant example of structure oriented programming is given by array based languages, starting of course with APL!

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:

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 is (~> [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:

-- 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 the usual functional programming constraints: each operation accepts exactly ONE input and produces exactly ONE output. The inputs and outputs may be structures containing multiple values or operations, or transforms (see later), but that is incidental.

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

average as Collection Number -> Number
    is ([count invert, sum] product),

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

average

declare an object called 'average'

as 

this object satisfies the following type constraint

Collection Number -> Number

This is a Type declaration that describes an operation which accepts a collection of numbers (Collection Number) as input and provides a number (Number) as output.

In this type expression Collection is what is called a transform, and it 'consumes' the following term (Number). This might look like function application to someone with an FP background, and it is very much so, but it follows entirely different rules to those applied to normal operations which operate on data.

is

this is the actual definition of the object

(                 -- 

begin a serial scope, it will get a 'Collection Number' as input

[

begin a parallel scope, the outer scope's input is passed directly into this scope. The input to this scope is passed to every item in the scope as input.

count invert

take the input (Collection Number), count the items, and then invert the count (1/x).

,

next entry in the parallel scope

sum

take the input (Collection Number), and compute the sum of the items

]

end the parallel scope. This produces a tuple [Number, Number] which will be passed on to the next item in this entry of the outer serial scope.

product

multiply the items in the tuple

),

) ends the serial scope, and , ends the declaration of average.

Foxtrot is strongly data-flow oriented; 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 4 (the increment is discarded)
    [increment, decrement]     -- produces [6,4]
    [sum, count]               -- we have [10, 2] here
    product,                   -- produces 20
)                              -- the enclosing scope produces 20 (the 4 is discarded)

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 as [Str, Str, Str] -> Str
is (~ [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 called a branch scope. It is used for conditionals and pattern-matching:

string_contains as [Str, Str] -> Bool
is (~ [needle, haystack],
    haystack ~~ needle String.find
    { [@, 0] greater_or_equal ? true, ? false }

(given String.find is String -> String -> String and it returns -1 if needle is not found in haystack)

because most mathematical calculations are not easilly expressed using sequential operators, Foxtrot provides the arithmetic-expression marker =. when an expression starts with =, what remains is an arithmetic expression that supports common unary and binary operators + - * / ^, comparison operators < > <= >= = and boolean operators ! & | !| (XOR). There is a special bitfield type that allows bitwise operations, Ints and UInts can be converted into this type when necessary.

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

-- @TODO more examples

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 a 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 the syntax and semantics of this language... I hope to someday implement it.