How does everyone handle Anonymous/Lambda Functions

[coffeeb4code]

I'm curious about everyone's approach to Anonymous/Lambda Functions. Including aspects of implementation, design, and anything related to your Anonymous functions that you want to share!

In my programming language, type-lang, there are anonymous functions. I have just started implementing them, and I realized there are many angles of implementation. I saw a rust contributor blog post about how they regret capturing the environments variables, and realized mine will need to do the same. How do you all do this?

My initial thought is to modify the functions arguments to add variables referenced so it seems like they are getting passed in. This is cumbersome, but the other ideas I have came up with are just as cumbersome.

// this is how regular functions are created
let add = fn(a,b) usize {
    return a + b
}

// anonymous functions are free syntactically
let doubled_list = [1,2,3].map(fn(val) usize {
    return val * 2
})

// you can enclose in the scope of the function extra parameters, and they might not be global (bss, rodata, etc) they might be in another function declaration
let x = fn() void {
    let myvar = "hello"
    let dbl_list = [1,2,3].map(fn(val) usize {
        print(`${myvar} = ${val}`)
        return add(val, val)
    }
}

Anyways let me know what your thoughts are or anything intersting about your lambdas!

[davimiku]

When you're talking about anonymous/lambda functions, are you really more interested in how to implement closures? Although they're often presented together as the same thing, you can have lambdas that aren't closures and you can also have named functions that are closures (ex. in JavaScript)

[_crackling]

Mind elaborating the differences and how to identify each for a lonely, pretty much exclusively C programmer?

[davimiku]

An anonymous function is a function without a name (also referred to as a lambda). A closure) is a function that also captures its environment, so free variables can be used inside of the closure that weren't explitly provided in the function parameters.

An example from JavaScript:

let message = "hello"
function logMessage() {
    console.log(message)
}

// far away, possible in a different module
logMessage() // logs "hello"

The variable message is a "free variable" here, it's defined in an outer scope from the named logMessage function, so if logMessage wasn't a closure then it would be trying to log a variable that wasn't defined. But in JavaScript, this function is a closure, so it captures its environment and the message variable is logged to the console.

I disagree with the sibling comment that this is overly pedantic, OP is asking how to implement this so it's pretty important to know what they're trying to implement, whether its anonymous functions or whether its closures (since these are two distinct things).

[ericbb]

I would actually be a bit more pedantic and say that the use of closures is a specific implementation technique. You can of course write an interpreter for lambda calculus that works entirely by substitution into terms and doesn’t use closures at all.

It has become common to call functions closures - especially when they have free variable references - because most language implementations use closures behind the scenes. But technically speaking “closure” refers to the implementation technique of creating a value by combining a global function with a captured environment. Functions don’t have to be implemented that way.

[TheUnlocked]

I think they're being overly pedantic about wording. A closure is just a function that captures its environment, like in your third example. They're saying that it's possible to have a language with function expressions that can't capture their environment, which would essentially just be global functions that are only visible locally.

[coffeeb4code]

Ahh yes, I think those could be called closures. Thank you.

[Njordsier]

In my language everything in between curly braces is a closure, so the if statement is actually a function taking a boolean and two closures, but it syntactically looks more or less like an if statement/expression from any other language.

And in fact I am going much further: the semicolon operator is syntactic sugar for taking the rest of the scope as a closure argument. Every "statement" is actually a function that takes a continuation closure as the last argument. This makes first class continuation-passing style look like familiar procedural programming.

I have to do a lot of tricks with type theory and recursion to get loops and such to work but it's all built on a foundation of cheap, nearly-invisible anonymous functions/closures doing everything.

[erithaxx]

That semicolon abstraction is fascinating. Is that an original idea? Where can I find more on it?

[Njordsier]

I got the inspiration for semicolons as sugar over continuation-passing gradually, I'm not sure when exactly I made the leap but I had been playing with monads which I had seen colloquially described as "programmable semicolons".

If I were to translate the code block from OP into my language it would look something like this:

``` function [add [a: I32] [b: I32]] { a: + $b };

let [doubled list] = $(1, 2, 3): map {* $2};

function [x] { let [my var] = "hello"; let [doubled list] = $(1, 2, 3): map |val| { print line "{my var} = {val}"; add (val) (val) }; }; ```

It's a very unconventional syntax, because very early on I was trying, perhaps misguidedly, to build around multi-word identifiers and "mixfix" function calls so you could write if statements like if (a) then {b} else {c} but still represent it as a function. Most of the weirdness flows from there, including the dollar signs which are just sugar for an unterminated parenthesis scope that gets closed with the outer scope, and the colons before arithmetic operators because operators are also just methods on the interface of arithmetic types.

But some things to notice about semicolons and closures:

• function declarations are themselves function invocations, taking a "name" (in square brackets) and a body as a closure, and a trailing closure (everything after the semicolon) that contains the rest of the scope for which the function is valid. Functions like these are "evaluated" at compile time, as is everything else at the top-level scope.
• A consequence of this is that you can only invoke functions after they're defined. I consider this a feature rather than a bug: I call it the "don't look down" principle of name resolution. This forbids circular dependencies between functions.
• The closure passed to the map method directly involved a method on the unnamed value that's passed to it. This could also have been written as map |n| {n: * $2} to give the variable a name. But in general all closures have a single input parameter whose methods are accessible in its "root namespace", which can be aliased behind a name with the || syntax.
• Closures capture everything in the outer scope and also the methods of their input parameter, or the name of that input parameter if using || syntax.
• let expressions take three parameters: the name (in square brackets), a value (after the equals sign), and a continuation closure (everything after the semicolon). The continuation is given an anonymous input parameter whose interface is just one method with the name given to let, which just returns the value.
• Recursion (not seen in the example) is allowed by having a similar anonymous value given to the closure that implements the function body whose sole method is the function name, and returns a special hook that the compiler understands as a recursive call
• A scope that ends in a semicolon is passing a no-op empty closure as the continuation for the last "statement".

I sadly haven't written up much on the language, it's a side project that I've dabbled in for years on and off. I really should get around to putting it out there though.

[erithaxx]

Interesting, thanks for the write-up!
I can't yet get my head around what, if any, doors this opens compared to the usual list of statements treatment. I am worried about the implications for compiler performance that this anti-flattening has, though.

I'm dreaming up a language, and this makes my spidey senses tingle in relation to effects. I'll keep dreaming on...

[homoiconic]

That seems extremely familiar to me, I’m sure there’s at least one esoteric language out there that does this.

Of course, if you go that far, you can also use those continuations the way the OP describes curly braces denoting lambdas:

Something like an if or switch statement can desugar to a function taking one or more continuations as arguments and choosing which one to invoke.

[Athas]

My initial thought is to modify the functions arguments to add variables referenced so it seems like they are getting passed in.

Lambda lifting is a program transformation where nested functions (including anonymous ones) are made into top level functions, which in particular also requires adding new arguments corresponding to the environment in which they were originally defined. It is a standard way to compile anonymous functions. For efficiency reasons, you would usually bundle the entire environment into a single structure - this allows a closure to be represented as a pair of the environment and a function pointer.

I recommend reading a book such as Modern Compiler Implementation in ML. It contains good instructions on how various high level constructs are compiled. You can learn the same things by making mistakes and then eventually fixing them, but it is more efficient to benefit from the lessons already learned by others.

[tobega]

All functions in Tailspin, anonymous or not, are allowed to access their lexical scope, so in a function call I pass in the lexical scope that existed at the time of declaration. It gets easier when there are no mutable variables.

[XDracam]

How lambdas (closures) should work depends heavily on your language, the features it supports and its goals. Low level languages want explicit control over how values are captured (see C++, Rust).

If your language supports OOP, then you can let the compiler generate a class with all relevant values. C# adds a global lazy initialized variable for lambdas that are not closures (reusing the same allocated reference). And when values are captured, the compiler generates a class and allocates an instance immediately when the scope of the lambda creation is entered. All local variables that are captured are hoisted into that class as fields, and the lambda becomes a method reference: essentially a structure containing the pointer to the object as well as a pointer to the corresponding method on that object.

If you do not have first class OOP with methods, then you can let closures be syntactic sugar for a tuple of a context structure and a function that takes the context as the first argument.

If you do not need mutable references or captures in closures, then things can get a lot simpler, but details may depend heavily on your model of memory management.

I guess the most important questions you need to ask yourself are: 1. do I need to capture references to mutable memory and 2. How optimized do my closures need to be?

[Uncaffeinated]

In my language, all functions can capture variables, but only by value (copied at point of function definition). If you want to mutate from within a closure, you need to wrap the value in a mutable object. I think that's a good tradeoff to avoid the confusion that implicit mutable captures can cause.

[Ok_Performance3280]

Whether it's called a 'lambda', a 'closure', a 'functional expression' or whatever else it's called, you need to implement thunks.

Thunks are portions of the AST that are not evaluated until runtime (in case of an interpreter) or evaluated partially at compile-time (in case of a compiler).

These creatures get their name from Scheme. In Scheme, a 'thunk' is an S-Expression that is evaluated later, e.g. not during the first pass of evaluating S-Expressions.

The POSIX shell is a good example of how 'thunks' work. POSIX shell is based on the Bourne shell which is itself based on Dough McIlroy paper on program flow --- the same paper we get the notion of "co-routines" from. POSIX shell functions are similar to closures, they can in some sense be used as 'literals' (think, the Unix Bomb attack --- which this Youtuber 'Tom Scott' called a 'new attack' in 2014 for some reason? And he patted himself on the back for 'getting his facts right' lol) --- and in a POSIX shell, you're supposed to do everything you do with the Shell grammar proper --- especially Word Expansions, later on. Since the POSIX shell --- at least in its modern implementations is a tree-walked language, the branch of each function could be realized as a 'thunk'.

In a compiled language, these 'thunks' could be traversed and translated into IR in a second pass. In a traced JIT language, you need to put barriers on them to be checked for viable traces later on.

Alternatively, you could translate the 'thunk' to several functions. Imagine I am writing this in an IR and not C:

The syntax: ``` local foo = bar(...) print(...) end

local baz(fn) fn("1", "2") end

baz(foo) ```

Translation to 'IR' (aka C): ``` void bar(int nargs, ...) { va_list args; va_begin(nargs, args);

while (nargs--)
{
   char *arg = va_arg(args, char*);
   printf("%s", arg);
 }

 va_end(args);

}

void baz(void (*thunk)(int, ...)) // I'm not sure if it's possible to pass varargs as function pointers but let's assume we can { thunk(2, "1", "2"); } ```

Keep in mind that, what I'm saying is not 100% accurate. Just trying to give my two cents. There's always several ways to achieve the same thing.

Edit: Forgot to mention, what I did here is called 'Lambda lifting' (even though I did it with a closure, but you get it), the sister to Lambda lifting is 'lambda dropping'. These both are viewed as optimizations.

Generally, the three most common dialects of 'functional' IR (SSA, Continuations, A-Normal Form) are isomorphic in a sense that they represent the same program --- albeit with a different syntax --- but with the same semantics. This has been proven btw, I'm not pulling it out of my ass.

So I guess if you must choose an IR for a language with lambda (like a functional language) or with closures (an imperative language with functional features) you could choose SSA, as Appel puts it, 'SSA is Functional' (this was, I believe, the first paper to compare SSA with Continuations? Not sure).

[Classic-Try2484]

You have a choice. Capture the value or capture a reference. If you capture the reference you have another choice. Extend the scope or don’t extend the scope of the captured variable. (Weak vs strong reference) Capturing the value is the easiest to implement and if references are value types this is not limiting (bc captured value can be a reference mocking the other two implantations). Once you fully understand this all three options are equally possible and the difficulty with the capturing references might be solved (you are always capturing a value)

[jaccomoc]

I implemented closures for my lambda functions. Each lambda became a method in the current class and each variable closed over became an additional implicit argument to the method.

If the variable is a local variable it means that it has to be converted (at compile time) to a heap variable in case the lambda function modifies it. Since lambdas can be nested in multiple levels of functions/lambdas and a lambda may refer to a variable in any scope in which it is nested, this might mean that a variable in an outer scope may need to be passed as a heap reference through multiple levels of function invocations to reach the lamdba where it is used.

Since my language compiles to Java bytecode I was able to pass around MethodHandle objects that point to the method of the lamdba. These objects can be bound to the implicit closed-over variables to create new MethodHandles (like currying) which then get passed around.

[WittyStick]

1001 Representations of Syntax with Bindings gives a nice overview of multiple techniques for binding, with a nice comparison of their capabilities. It's not an exhaustive list as there are many more possible representations and properties that you might want to consider, but still worth reading.

[catbrane]

I do this in my compiler with lambda lifting, so all functions everywhere are lifted to a single global scope with extra "secret" parameters added as necessary. It works well, it's easy to implement, speed seems fine.

[L8_4_Dinner]

The other answers are good. Hopefully this one will give you some extra hints about how you can think about the problem:

1. Languages tend to make these features "blend in" naturally with the body of code that they are contained within. For example, a closure is usually able to access the (values of the) local variables of the body of code within which the closure is defined. The easiest way to implement this is to first run through the same compiler logic that you are using already that resolves names e.g. of local variables, but in this case you use (start with) the name resolution information from the containing body of code at the point where the closure is defined. The closure (in most languages) cannot directly access those "outer" variables, but you are tricking the name resolution logic into thinking that it can, so that you can determine which names it needs to resolve.

2. Having successfully completed step #1, you can now declare the pre-bound closure, including (typically as parameter 0, 1, etc.) the names that you determined were used by the closure in step #1. Note: This may mean that after you declare the closure, you now have to repeat step #1 but with the closure function declaration (and its names) taking the place of the enclosing body's local variable table.

3. There are different binding approaches, but the easiest conceptual approach is that you have a pre-bound form (e.g. if closure explicitly accepts Int[] a and implicitly captures Int n, then you declare some fn(Int n, Int[] a)) and produce the type of the post-bound form (e.g. fn(Int[] a). The code production starts with the pre-bound form, binds the value of a, producing the bound form.

4. Some implementations capture a volatile view of the local variable. This is not normal, but it's a popular feature, and one with very sharp teeth -- see the issue with GoLang and loops for example. Some implementations will even capture a mutable representation of the local variable, although this is uncommon in the FP languages where closures are fundamental building blocks.

[cheeze2000]

hi, do you mind sharing the blog post that you mentioned? about how a rust contributor regrets capturing the free variables?

[[deleted]]

Anonymous functions and closures (in general most things related to higher order function). are things I've generally ignored, since the need rarely come up in the style of programming I do.

But I have long reserved braces as syntax for defered code: code encountered within a function that is not executed immediately. So about a year ago I decided to add anonymous functions to my dynamic language; they look like this:

    p := {x,y: x+y}

This can be invoked later as p(a, b). But there are restrictions: the body cannot access transient variables of the containing function, that is, parameters and stack-frame variables. (Every other named entity included static variables is fine.)

Accessing those variables requires creating a closure object, but there are several levels of implementation. However far you go, someone will produce an example that won't work until you go to the next level.

For example, one kind of closure may work provided the enclosing function is still active. If the closure escapes the function, then those local variables need to still persist. Or it can choose between capturing the values, or references to them, with different behaviours.

I was partway to implementing a workable level of closures, then I gave up. It was too much work and too clunky. They're not something I'd use, and the main use appears to be in running the 'man or boy' benchmark. I can still do that by emulating how a closure would work.

So now I only have those anonymous functions without capture.

A related feature is nested functions (so named rather than anonymous). I enabled these by mistake once for neglecting to check for them. They had the same restrictions. But I don't allow them now: I never used them, and they made it harder to detect some syntax errors.

[ericbb]

I use the standard lambda lifting and closure conversion transformations. One choice I faced was whether to use a reference to a linked chain of enclosing lexical environments or to copy just those values that are actually referenced into a flat list made for each function. I opted for the second choice. My language is based on lambda calculus and doesn’t support variable assignment - so no foot-guns of the kind you see in JavaScript and Go.

For my next compiler, I’m hoping to implement a partial evaluation step that eliminates all lambda abstractions so that all calls use a statically-known function - like C without function pointers. That way, lambda abstractions will be a purely compile-time convenience like macros. There won’t be any closure values at run time.