Tuesday, April 18, 2023

Toyfl, finished at last

When I started this blog ten (!) years ago, I was creating a programming language called Toyl (Toy Language).

In the intervening years I have thrown away and rebuilt my language several times, and I now consider it essentially finished. It is now called Toyfl (Toy Functional Language).

Syntactically it is somewhat inspired by Javascript, with lambda expressions like the following:

(a, b, c) => a * b + c

And anonymous objects like this:

{a = 10; b = 32; c = 11; f = (x) => a}

And a dot operator for accessing members:

x = {a = 10; b = 32};

y = x.a

And lots of other familiar things.

There are only a few features of the language that are worth remarking on, but since the purpose of this blog was originally connected to developing the language, I'll remark on them here:

1) Extreme Laziness. If you have an expression like if(a == b, a + 37, b + 22), Toyfl will only evaluate the condition a == b. It will then return one of the two expressions in the then or else case without actually evaluating them. Nothing gets evaluated until it is really, really needed.

That's connected to a second weird feature of Toyfl:

2) Currying by Refactoring. Since Toyfl doesn't evaluate an expression until it is really, really needed, an expression returned from within a function needs to be context-independent. That is, it needs to be able to remember what relevant parameters were passed into the function when it was invoked. I handle that by creating a refactored copy of the body of the function. So, if you have a function like this:

f = (x, y) => x * y

and you invoke it like this:

g = f(a, b + c)

then what you get for g is actually a structure representing the expression a * (b + c).

Originally it rubbed me the wrong way to do this, because somewhere deep inside I have this feeling that code should remain static, but the effort required to carry out refactoring is actually pretty slight, and in a functional context it is very reliable.

However, this behavior means that recursive functions actually build large in-memory expressions. Memory is cheap these days, so I don't worry too much about that for ordinary use-cases, but I thought it would be interesting to solve the problem anyway. So I created:

3) Special syntax for tail recursion. I noticed that the simplest functional implementations of certain solutions required significantly more calculation than the simplest imperative implementation. I wanted a way to bring the efficiency of imperative solutions to my functional language, so I created the following syntax to bridge this gap.

fibonacci = (n) => (

    for {

        a = 1;

        b = 1;

        i = 1

    }

    let {

        nextA = b;

        b = a + b;

        a = nextA;

        i = i + 1

    }

    until i == n

).a

This looks like a loop in an imperative language, but effectively it turns into something like this:

fibonacci = (n) => innerFibonacci(1, 1, n)

    where innerFibonacci = (a, b, i) => if (i ==n, a, innerFibonacci(b, a + b, i + 1))

Normally Toyfl would build a huge structure out of this, but the special syntax tells Toyfl to fully evaluate each of the parameters a, b, i before the recursive invocation, so we can take advantage of tail recursion.

So that's Toyfl. It's been fun.