Anonymous recursive functions in Racket

Anonymous recursive functions in Racket

Context

Some languages, like PowerShell, have “anonymous recursive functions”. That is, normally, a function needs to use a name to refer to itself to recur. But “anonymous recursion” means the language has some special mechanism by which the function can refer to itself without having to explicitly introduce a name. In some contexts, this is called an anaphoric reference.

Code

Here we show how we can easily implement this feature in Racket. The file anon-rec.rkt implements a macro called lam/anon♻️ , short for "lambda with anonymous recursion". This specifically binds the name $MyInvocation , to mimic the syntax of PowerShell, though the $ here does not mean anything special.

Examples

The file client.rkt shows several uses of increasing and varying complexity:

fact shows a standard factorial definition.

How can we confirm that $MyInvocation is really bound to the right invocation? So lucas-or-fib is essentially a glorified version of the Fibonacci function, but the same body (which recurs using $MyInvocation ) can also be used for the Lucas sequence given different initial values. This shows that the recursive function is bound correctly.

grid shows that the correct binding occurs even in nested settings.

... continue reading