Designing Function Constructs (LLO Archive)

Created 2025-12-11, last modified 2025-12-12. Visibility: public

Part of my archive of Layover Linux Official posts on Tumblr.

2025-11-02

While a lot of my recent work has been about optimization, especially the allocator system (which now offers very pluggable allocators that don't depend on the Vec code, so the Vec code could depend on the allocator system at some point instead of the other way round), a lot of it has felt like stalling for time trying to figure out how to represent functions. The first baby step was Blocks. But I've had to figure even just the terminology to take the next steps from there.

The first thing I want to make are functions that don't need to do any dispatch. I don't know if I want to call these direct functions, non-dispatched functions, I dunno. These closely match the expectations of most programmers: arguments usually have strict types, set in stone, and if you don't provide the right types you get an error.

prn> fn = |u8 first, u8 second| ~{ first + second }
fn|u8, u8|
prn> fn(1u8, 2u8)
u8(3)
prn> fn("hello")
#DISPATCH_FWD

This is just a sketch of what could be, not what's currently implemented, but I think there's a few key takeaways here, design wise.

  1. Argument types are treated very literally. Passing a literal number like 1 instead of u8(1) would be an error.
  2. Type checking should be an extensible library function. Something under the hood should be calling typecheck(t, v) before the block executes. This allows pattern matching against specific values, too.
  3. When the block executes, it gets its own scope where arguments are set. This scope inherits from the caller scope, although there are fine details I'll explain later about what does and doesn't get shared from caller scope.
  4. Not every argument is a type+name pair. We do want to support omitting a type for a particular argument (implicit #ANY as type), as well as ...splat arguments which might or might not have a type. So the arguments list needs to be somewhat open-ended in the format being stored per-argument.
  5. If the arguments don't match, you don't get a #DISPATCH_ERR. You get a #DISPATCH_FWD. Wait, what?

While eventually I'm going to make an Error type of construct and use those more often, a lot of stuff is best handled by the humble and quick little Atom. This is a good example. On their own, these simple strict functions are pretty limited. Mostly, they're used as the building blocks of multi-dispatch functions.

A multi-dispatch function is basically just a chain of the simple functions, tried one after another, which implicitly ends in "just return #DISPATCH_ERR". So for the fibonacci sequence, the underlying function might look something like this: 

prn> fib = dethunk([% #MDFN, [
    |u8(0)| ~{ 1 },
    |u8(1)| ~{ 1 },
    |u8 n| ~{ fib(n - 1u8) + fib(n - 2u8) }
  ] %])
fib|...|
prn> fib(5u8)
u8(8)

This works because non-matching legs of the dispatch "forward" on to the next possible option. This mean you can extend an existing function:

prn> fib_tmp = thunk(fib)[1]
prn> fib_tmp = unshift(fib_tmp, |u8(25)| ~{ #EASTER_EGG })
prn> fib = [% #MDFN %]:push(fib_tmp):dethunk()
prn> fib(5u8)
u8(8)
prn> fib(25u8)
#EASTER_EGG

This is kind of a dumb example, special casing the Fibonacci function to give a nonsense answer for inputs of 25, but it's a very practical example of what's going to happen under the hood with the def or superdef keyword sugar.

prn> def fib(0u8) ~{ 1u8 }
prn> def fib(1u8) ~{ 1u8 }
prn> def fib(u8 n) ~{ fib(n - 1u8) + fib(n - 2u8)) }
prn> superdef(25u8) ~{ #EASTER_EGG }

The only difference between def and superdef is whether new legs are added at the end or beginning respectively. I could have got the exact same internal representation by starting with a def for the 25 case. But sometimes you want to intercept and transform values before they go through an existing function, and superdef has your back. Remember, if the 25 case were to happen after the "any u8" case, it wouldn't be reachable.

You know, talking it through was helpful. I think the term I need for simple functions is Zero-Dispatch Functions, or ZDFNs, which are easily distinguished from MDFNs. Hopefully I can get this built before I have to confront some changes coming to the C native function interface, to support conditionally exporting things to callees.

...yeah I probably need to do that first actually.