I saw a video recently about function currying, and it triggered the realization that currying might solve a problem I’ve been pondering in the context of language parsing. The problem involves knowing how many arguments an operator expects, what’s called the arity of an operation or function. It can vary from zero to many.

But it occurred to me that, with currying, there could be a language where operations always take just one argument. And that would solve a challenge for a mathematical expression language I have in mind.

Let me start with exactly what currying is.

Generally speaking, functions and routines take multiple arguments, from zero to many. The number of arguments they take is called the arity of the function. Currying is a technique that allows all functions to have an arity of one.

We might not think of it, but common math operations, such as add, subtract, multiply, etc, are functions. Most of them, such as the ones just listed, have an arity of two.

For example, a+b can be expressed functionally as add(a,b).

The add operation is a function with an arity of two. Likewise can have functions sub(a,b), mul(a,b), div(a,b), and others.

We can curry these functions by doing something like this:

FUNCTION add PARAM a {
    FUNCTION f PARAM b {RETURN (a+b)}
    RETURN f
}

Which is to say we define a function, named add, that takes a parameter, named a. This function defines a new function, named f, with a parameter, named b. The function, f, returns the sum of a+b. The add function returns function f.

The source text uses the add function as just shown above, but the compiler turns it into something like add(a)(b). That is, the add function take a single parameter (a, in this case) and returns a function that takes a single parameter (b).

That returned function, which has a in context, and which took b as a parameter, does the actual adding and returns the sum.

This same protocol applies to sub(a,b), mul(a,b), etc. It applies to any function that takes two parameters. The first function takes the first parameter and returns a function that takes the second.

Which can return a function that takes a third parameter and so on, if necessary.

So that’s currying. Here’s an example in Python:

def Add (a):
    def f (b):
        return (a+b)
    return f

r = Add(42)(21)
f = Add(42)
r1 = f(21)
r2 = f(13)
r3 = f(42)

def Between (x):
    def f1 (a):
        def f2 (b):
            if x <= a: return False
            if b <= x: return False
            return True
        return f2
    return f1

r = Between(35)(21)(42)
f = Between(35)
r1 = f(21)(42)
r2 = f(42)(64)
r3 = f(50)(10)
#

One cute trick is that, having obtained the first function, you can apply it to different arguments to get different results. The first example adds 42 to 21, 13, and 42.

§

So that’s currying functions, and, as you can see, it can allow a compiler to assume any function it finds takes one, and only one, parameter. All functions, by fiat, have an arity of one.

This does disallow a function like today, which returns today’s date. There are other handy functions that don’t take parameters, they just return a useful value. Many languages have a random function, for example.

A possible way around these is to redefine how they work. For example, we might have a today(count) function that returns today’s date if count is zero, but returns a past or future date if count is non-zero (minus or plus, respectively).

It’s usually possible to redefine the functions to take some kind of parameter. (In many cases this makes them more useful. Who hasn’t wanted a today function that works like that?)

If all else fails such a function might take a NULL or other placeholder value. (In my BOOL language, I used the semi-colon as a placeholder for a missing argument.)

§ §

Here’s my problem: When compiling source code, the compiler needs to know the arity of called functions in order to associate the right number of parameters with the call.

In many languages, this isn’t a problem:

print(a, b, c);

Obviously the parameters are a, b, and c.

But there are languages where it is not so obvious:

$print $add a b c

If $print and $add are functions, how many parameters to assign to one and how many to the other? Are trying to print the sum of a+b+c, or do we want print both the sum of a+b and the value of c? (Or maybe we want to print the sum of a, plus the value of both b and c?)

Without knowing the arity of the the functions, the compiler doesn’t know how many arguments to associate with them.

The usual solution is that the compiler has to know the arity of any functions used in the code. Typically, this is because the compiler compiled those functions and has their signatures in a reference table. (Or because it imported those functions or read a definitions file. The point is, the compiler recognizes the function.)

But I’d like to consider a situation where the compiler doesn’t know and there is no syntax to bracket arguments.

Enter currying.

§

The basic idea is to free the compiler from caring about arity at all. Doing this requires deferring some behavior to run-time, so this technique depends on both the compiler and the run-time engine.

The compiler just needs to identify function names and arguments and compile them into tokens. It doesn’t pay any attention to binding arguments to functions. It does have to do some variable handling, assuming variables are implemented.

The target, for now, is a mathematical expression language, rather than a full-blown programming language, so a source text will mainly consist of a single expression to process.

That said, both variables and sub-routines are a possibility.

The run-time engine processes the list of token using the following algorithm:

Process_Token (Token):
    if Token.type == FUNCTION:
        Stack.push(Token.function)
        return Token
    if Token.type == PARAMETER:
        func = Stack.pop()
        new_tok = func(Token.argument)
        return Process_Token(new_tok)
    Error('Unknown Token Type')

Process_Token_List (Tokens):
    for Token in Tokens:
        a = Process_Token(Token)
    return a

Note the recursive nature of Process_Token().

The idea is to take each token in turn. If the token is a function, it’s pushed onto the stack until a parameter is available. If the token is an argument, the most recently encountered function is popped off the stack and given the argument.

The value returned by that function is recursed to Process_Token(), which repeats the process. Ultimately, the function returns value returned by the recursion.

When the final token is processed, the returned value is the result of the evaluation of the expression.

§

Here’s the actual Python code for the run-time engine:

def process_statement (expression):
    stack = []
    # Recursive node processor...
    def process_node (tok):
        # If token is a function, push it on the stack...
        if isinstance(tok, function):
            stack.append(tok)
            return tok
        # If token is a parameter, apply it to a function...
        if isinstance(tok, argument):
            # (Unless there aren't any; then we're done)...
            if len(stack) == 0:
                return tok
            f = stack.pop()
            # Execute the function!
            new_tok = f(tok())
            # And recurse on the result...
            return process_node(new_tok)
        # ERROR: Unknown node type...
        raise RuntimeError('Unknown nodetype!')

    # Execute the nodes of the statement...
    ret_val = argument('###ERR', None)
    for token in expression:
        ret_val = process_node(token)
    return ret_val
#

This requires a few classes to implement the function and parameter objects:

class node (object):
    def __init__ (self, name):
        self.n = name
    def __str__ (self):
        return self.n

class argument (node):
    def __init__ (self, name, value):
        super().__init__(name)
        self.v = value
    def __call__ (self):
        return self.v
    def __repr__ (self):
        return '{argument:{n:"%s", v:%s}}' % (self.n,self.v)

class function (node):
    def __init__ (self, name, function):
        super().__init__(name)
        self.f = function
    def __call__ (self, arg):
        return self.f(arg)
    def __repr__ (self):
        return '{function:{n:"%s", f:%s}}' % (self.n,self.f)
#

Note that we can call a function object to invoke its function. When we do, we pass the single parameter the function expects. We can also call the argument object to obtain its value.

We’ll need a run-time library of the actual functions the language handles. These are mostly mathematical functions, such as add, multiply, etc. Here I’ll just show you a handful (they all follow the same pattern):

def fSin (a):
    return argument('$sin', sin(radians(a)))

def fCos (a):
    return argument('$cos', cos(radians(a)))

def fAdd (a):
    def f (b):
        return argument('$add', a+b)
    return function('_Add', f)

def fSub (a):
    def f (b):
        return argument('$sub', a-b)
    return function('_Sub', f)

def fMul (a):
    def f (b):
        return argument('$mul', a*b)
    return function('_Mul', f)
#

Note the difference between monad functions that take just one parameter (such as cos and sin) versus binary functions that take two. The former don’t require currying, but the latter do.

The leading “f” in the name is just to put them in their own little namespace.

§

The next thing is the compiler that turns source text into the list of tokens. That’s complicated enough for a separate post.

But we have the machinery to execute an expression on the run-time engine if we hand-compile the expression. Let’s do that with this expression:

(cos x  * sin y) + ((a-b) / c)

Which we would express functionally as:

add(mul(cos(x), sin(y)), div(sub(a,b), c)))

If we remove the function parentheses and further assume we have no idea what the arity of the functions involved is, then we have an ambiguous expression (or so it would seem):

/add /mul /cos x /sin y /div /sub a b c

Here I’m using /name to indicate a function. Anything else is a parameter.

Without knowing that /cos and /sin take one parameter, while the rest all take two, it’s impossible to evaluate the expression (or so it would seem).

§

But currying saves the day.

The sequence of events, token by token, goes like this:

1. Token /add is a function, so push it on the stack.
2. Token /mul is a function, so push it on the stack.
3. Token /cos is a function, so push it on the stack.
4. Token x is a parameter, so pop function /cos and invoke it with the parameter.
5. Function /cos returns a parameter, so pop and invoke /mul with it.
6. Function /mul returns a function, so push it on the stack.
7. Token /sin is a function, so push it on the stack.
8. Token y is a parameter, so pop and invoke /sin with parameter.
9. Function /sin returns a parameter, so pop and invoke /mul2.
10. Function /mul2 returns a parameter, so pop and invoke /add.
11. Function /add returns a function, so push it on the stack.
12. Token /div is a function, so push it on the stack.
13. Token /sub is a function, so push it on the stack.
14. Token a is a parameter, so pop and invoke /sub.
15. Function /sub returns a function, so push it on the stack.
16. Token b is a parameter, so pop and invoke /sub2.
17. Function /sub2 returns a parameter, so pop and invoke /div.
18. Function /div returns a function, so push it on the stack.
19. Token c is a parameter, so pop and invoke /div2.
20. Function /div2 returns a parameter, so pop and invoke /add2.
21. Function /add2 returns a parameter; stack is empty so return it.

So it all works out rather nicely.

∅