April 19th, 2024

Procs and Higher-Order Functions


More on UCL yesterday evening.  Biggest change is the introduction of user functions, called "procs" (same name used in TCL):

proc greet {
    echo "Hello, world"

--> Hello, world

Naturally, like most languages, these can accept arguments, which use the same block variable binding as the foreach loop:

proc greet { |what|
    echo "Hello, " $what

greet "moon"
--> Hello, moon

The name is also optional, and if omitted, will actually make the function anonymous.  This allows functions to be set as variable values, and also be returned as results from other functions.

proc makeGreeter { |greeting|
    proc { |what|
        echo $greeting ", " $what

set helloGreater (makeGreeter "Hello")
call $helloGreater "world"
--> Hello, world

set goodbye (makeGreeter "Goodbye cruel")
call $goodbye "world"
--> Goodbye cruel, world

I've added procs as a separate object type. At first glance, this may seem a little unnecessary. After all, aren't blocks already a specific object type?

Well, yes, that's true, but there are some differences between a proc and a regular block. The big one being that the proc will have a defined scope. Blocks adapt to the scope to which they're invoked whereas a proc will close over and include the scope to which it was defined, a lot like closures in other languages.

It's not a perfect implementation at this stage, since the set command only sets variables within the immediate scope. This means that modifying closed over variables is currently not supported:

# This currently won't work
proc makeSetter {
    set bla "Hello, "
    proc appendToBla { |x|
        set bla (cat $bla $x)
        echo $bla

set er (makeSetter)
call $er "world"
# should be "Hello, world"

Higher-Order Functions

The next bit of work is finding out how best to invoke these procs in higher-order functions. There are some challenges here that deal with the language grammar.

Invoking a proc by name is fine, but since the grammar required the first token to be a command name, there was no way to invoke a proc stored in a variable. I quickly added a new call command — which takes the proc as the first argument — to work around it, but after a while, this got a little unwieldy to use (you can see it in the code sample above).

So I decided to modify the grammar to allow any arbitrary value to be the first token. If it's a variable that is bound to something "invokable" (i.e. a proc), and there exist at-least one other argument, it will be invoked. So the above can be written as follows:

set helloGreater (makeGreeter "Hello")
$helloGreater "world"
--> Hello, world

At-least one argument is required, otherwise the value will simply be returned. This is so that the value of variables and literal can be returned as is, but that does mean lambdas will simply be dereferenced:

"just, this"
--> just, this

set foo "bar"
--> bar

set bam (proc { echo "BAM!" })
--> (proc)

To get around this, I've added the notion of the "empty sub", which is just the construct (). It evaluates to nil, and since a function ignores any extra arguments not bound to variables, it allows for calling a lambda that takes no arguments:

set bam (proc { echo "BAM!" })
$bam ()
--> BAM!

It does allow for other niceties, such as using a falsey value:

if () { echo "True" } else { echo "False" }
--> False

With lambdas now in place, I'm hoping to work on some higher order functions. I've started working on map which accepts both a list or a stream. It's a buggy mess at the moment, but some basic constructs currently work:

map ["a" "b" "c"] (proc { |x| toUpper $x }) 
--> stream ["A" "B" "C"]

(Oh, by the way, when setting a variable to a stream using set, it will now collect the items as a list. Or at least that's the idea. It's currently not working at the moment.)

A more refined approach would be to treat commands as lambdas. The grammar supports this, but the evaluator doesn’t. For example, you cannot write the following:

# won't work
map ["a" "b" "c"] toUpper

This is because makeUpper will be treated as a string, and not a reference to an invokable command. It will work for variables. You can do this:

set makeUpper (proc { |x| toUpper $x })
map ["a" "b" "c"] $makeUpper

I'm not sure how I can improve this. I don't really want to add automatic dereferencing of identities: they're very useful as unquoted string arguments. I suppose I could add another construct that would support dereferencing, maybe by enclosing the identifier in parenthesis:

# might work?
map ["a" "b" "c"] (toUpper)

Anyway, more on this in the future I'm sure.