I'm Betting on Call-by-Push-Value
thunderseethe.dev
thunderseethe.dev
If you squint at CBPV, there is exactly one primitive that sequences computation, `M to x. N`. In Haskell this is just the monadic bind `M >>= \x -> N` or `do { x <- M; N}`. If I had to bet, I would place my bet on monads, not CBPV.
(see Fig. 6 p.21)
I believe that by applying ANF, you're baking in either CBN or CBV at the time of writing the compiler.
If I've read it right, the author is suggesting that CBPV evaluates (ordinary) values before passing them, but does not evaluate functions (even though they are also values!) before passing them.
That does remind of another thing that CBPV glosses over though - it is only a fusion of call-by-name and call-by-value. In particular it doesn't model call-by-need particularly well, there is no notion of sharing thunks that are duplicated during evaluation. Actually call-by-need is sort of arbitrary, generally one is better off using "an implementation-specific evaluation strategy somewhere between CBN and CBV", which again is not modeled well by CBPV, as the choice of CBN or CBV evaluation is encoded in the IR so cannot be easily changed by the compiler.
I believe the first happens at compile time, and the second happens after the function is passed.
1 f x =
2 let xx = x * x in
3 (\y -> y + xx)
4
5 main = do
6 let clo = f 2
7 let applied = clo 3
8 print applied
xx is known to be the captured variable at compile time. But in a lazy setting, it's fine for the closure to be passed around before the value of xx is known:
f x =
let xx = trace "Evaluating xx" (x * x) in
trace "Returning closure" (\y -> y + xx)
main = do
let clo = f 2
let applied = clo 3
print applied
> Evaluating xx
> 7
Juste like lambdas, fexprs are lexically binded closures. The difference is that a fexpr arguments are not evaluated before it's called, instead, the arguments syntax is passed to the fexpr (so it's not call-by-name either, more like a macro), except that the fexpr also receives the dynamic environment (the one from the call site) so that it can eval its arguments in this context if it wants to.
This makes fexpr a kind of all powerful form that can do both what macros and functions can do. Even primitives like lambda or quote can be written as fexprs. Quite fascinating.
See https://web.cs.wpi.edu/~jshutt/kernel.html about Kernel :).
(In fact, R isn’t just ‘extremely similar’: it does use fexprs, though without mentioning the term.)
8 months later.
“I regret this decision, and a thousand curses on anyone who chooses to use this in a code base I have to work on”
I’ve been at the receiving end of this particular “feature” and it was awful. Your logic is splayed all over the place, and you’ll often get mystery errors, because someone else’s code makes some undocumented, un-typed assumption about the availability of some magically named variables. This is not a feature, this is bugs and misery in disguise.
However, if you don't get an environment passed in, you can't get access to it. In addition, the environments in many ways are append-only, you can change what you see as "car" but you can't change what previous callers see as "car" unless you get a handle to their environment but that won't change previous calls.
It's really quite tricky. It's doubly tricky because there are some environment mutations that you need to do as the system that you need to prevent as the user once everything is bootstrapped.
I really wish Shutt had implemented a version in C/C++/Ada/anything systems language and not just a metacircular scheme implementation. The metacircularity obscures the management of the environments that is key to the implementation. It also obscures just how much garbage Kernel cons-es up in order to maintain all of the necessary housekeeping to pass all this stuff around.
Alas, he is no longer with us to request anything of. RIP.
I should study Kernel. Looks like it went even further than that. Simply passing the dynamic environment to the FEXPR is quite ingenious.
What's funny is that the actual lambda calculus allows multiple reduction strategies, including lazy evaluation. So I guess the only reason to introduce this distinction is to facilitate impure code, which cares about the difference.
A fexpr cannot do everything a macro can do.
A macro can be expanded upfront, so that even code that is not reached during execution is expanded.
The separate macro expansion pass can take place in a different host environment, such as a developer's build machine. The expanded code then executes elsewhere: a target machine different from the developer's machine.
A macro can, for instance, grab a text file on the build machine, massage it and turn it into a literal (or even code, obviously).
Macro expansion can perform basic checks on code. For instance, in TXR Lisp, unbound variables are reported by the macro expander, before the code is executed, and even if it isn't.
This error is caught during expansion. The function is still interpreted:
1> (defun foo () (list a (cons)))
** expr-1:1: warning: unbound variable a
foo
2> (fun foo)
#<interpreted fun: foo nil>
3> (compile 'foo)
** expr-1:1: warning: cons: too few arguments: needs 2, given 0
#<vm fun: 0 param>
4> (fun foo)
#<vm fun: 0 param>
For instance, in the awk macro provided the same Lisp dialect, it's possible to perpetrate a situation in which code that looks like it is scoped a certain way isn't. The macro diagnoses it:
5> (awk ((let ((x 1) (y 2)) (rng x y)) (prn)))
** expr-5:1: warning: rng: form x
is moved out of the apparent scope
and thus cannot refer to variables (x)
** expr-5:1: warning: rng: form y
is moved out of the apparent scope
and thus cannot refer to variables (y)
** expr-5:1: warning: unbound variable x
** expr-5:1: warning: unbound variable y
A fexpr could implement this check but (1) it would be expensive at run-time to be digging into scopes, and (2) it would have to be executed and (3) it would need some stateful hack to avoid diagnosing repeatedly.
Another thing fexprs cannot do is to be debuggable via inspecting an expansion. To debug the form which uses the fexpr we have to debug into the fexpr. To debug a form using a macro, we can inspect the expansion. We can understand what is wrong in terms of the behavior of the expansion, which can be very simple compared to the macro. Then work backwards to understand why the bad expansion was produced. At that point we can dig into the macro, and that is a different problem: a pure code generation problem we can likely debug in isolation in a development system.
Yet another thing fexprs cannot do is simply go away entirely in a software build. We can stage macros such that their definitions are available at compile time, but are not propagated into the compiled program.
https://github.com/gatlin/precursor-ts
https://github.com/gatlin/precursor-ts/blob/main/src/ceskm.t...
1. Evaluate it in the caller, pass the result. "Strict".
2. Build a thunk, pass the thunk, eval it on use. "Normal".
3. Build a thunk, pass the thunk, eval on first use, cache result. "Lazy".
4. Pass the value unchanged. "Macro?". Might be a better name.
5. Associate it with surrounding context, pass unchanged. "Hygienic macro".
6. Mangle things in a preprocessor, call the constructs "macro". Unrelated to the above but sometimes gets thrown in anyway.
In particular people are really prone to conflating lazy evaluation with macros. I think it's because the standard example of "if" only evaluating two of the three arguments happens to work with lazy evaluation or macros. Passing a thunk representing the evaluated form of an argument is a different thing to passing the unevaluated data. I see a lot of Haskell people saying they have no use for macros since the language is lazy - that might be true, but lazy is a subset of macro semantics so it's not immediate.
I'm not totally sure that being able to annotate a specific function as call-by-value or call-by-thunk (or call-by-name) is especially useful but you can certainly do it. It's a flag stored in the function that call dispatch checks, ideally at compile time. Annotating a function as either "strict" or "macro" works well in kernel (the lisp).
The other dimension is whether individual arguments should get specific calling conventions. For example, if would do well with the predicate given strict semantics while the consequent and antecedent have something else. Also interesting, not sure that's worth the bother either. I believe some prior art called this nlambda.
The other thought is you can annotate the call site instead of the function. That could give you a single function implementation used for strict or lazy evaluation, though that's probably syntactically confusing.
That's a rambling way to say I think the current setup of a language having a default calling convention and some way to choose a different one at function granularity seems fine.
For an article about efficiency, there seems to be a noticeable absence of actual instruction sequences for comparison.
.get() will evaluate the argument when the specific value is needed. It might be a literal wrapper.
.set() will be called when the argument value is set. It either does nothing in the case of a wrapper that is call-by-value, or back-persists the mutation if the set() actually does something.
I get that doesn't have the sexy lazy eval / late binding of functional langs, but in the imperative model, is that the basic idea?
------
as an aside, I've found that in my (I'm a groovy programmer preferentially) scripts, where I'm doing bash-ish things with a lot of CLI execution, I do things like this:
"cd somedir; ls -la". with { <look for and parse out a file and its date>} "df -k". with { <parse out some device we are interested in> }
and I find it very nice to structure the readability, since the meat of these scripts is the command: I define the data, then "push" it to the processing I want to do to it.
Is there any programming language name for this sort of "value first" model? I find it also flows well for chaining operations, whereas something like:
saveResults(parseOutput(runCommand("df -k")))
forces you to mentally pop the stack. As you read from right to left you have to push the operations in your mental model until you get to the core of what you're working on, while
"df -k". with{ runCommand(it) }. with{ parseOutput(it) }. with{ saveResult(it) }
is more like the natural order
What langs have it? I mean besides (shudder) bash? Because groovy with assigns it to an explicit car you name at each state, otle the implicit "it" of the closure scope.
https://pursuit.purescript.org/packages/purescript-lazy/3.0....
It changes how you think in a few very specific cases, but even a lot of situations where e.g. infinite series are helpful, expressing iterations over blocks that can terminate the iteration itself early removes any need for laziness.
It seems like it would end up quite cumbersome. C# has object properties that can be values or functions. Etiquette dictates you don't query a database in an object property but I've seen it happen. I'm not even sure what the etiquette here would be. The entire point is to lazily evaluate slow things, right?
But I guess its all just for IRs and the idea is a compiler is handling it all anyway?
I think the main point here would that a thunk is also a value. And most type system can already express "a computation which return Type X" by a value of type "() -> X". Adding side effect annotation, it seems to be that a pure function of type "() -> X" gives you very close to the same semantic.
It's also unclear to me that one should want to allow both value and computation producing values to be used interchangeably. If the goal of CBPV is about better performance, then being able to mix and match both "kind" of value is probably not wise (at least without good compiler error messages), same as mixing type of values would break a type system.
To have thunking only arise from single unit-arg functions kind of depletes the logic of useful structure. But it’s not wrong to see it as an approximation.
>> F: func [A][print type? :A print join "Arg: " A]
>> F "Foo"
string
Arg: Foo
>> F func [][return "Bar"]
function
Arg: Bar
Even knowing this though, that post really is really obtuse. Definitely could have been better written.
Basically in these languages, functions don't have a special syntax to be called, like F(), they just get called when used. So usage of a no-argument function is identical to a variable, and what happens depends on its datatype (function, string, whatever). The special :A syntax is to get the value without evaluating it if it is a function.
def int(i) = i.respond_to(:call) ? i.call : i.to_i
def f(i) = int(i) * 2
In practice we'd usually do this via any of the normal conversion methods like expecting the caller to support to_i etc., and bear the complexity for us as needed unless there's a really compelling reason to think the caller will often want to defer the evaluation past the call site and into the method itself.
That's usually very obvious when you come across it, like e.g. if the argument is expected to come from a remote source, but as long as the API for how the method uses the value is clear, substituting the value for a deferred calculation is easy.
But it really seemed like it was describing a language like C++ or Rust where a “computation” is a value that happens to be a callable function (std::function<int ()> or Fn() -> int, for example). A thunk is a value of callable (computable? is this really different?) type, and Return is the magic operation that wraps a value into a trivial closure, like:
[val]() { return val; }
Maybe there’s more to it than that.
Because I agree, if you take a statically typed call-by-value language and "introduce little spurts of lazy evaluation" then don't you get the same flexibility? And you'll also know the arity at all times.
There's something in the syntax I don't understand in the middle about unifying things, but then it later says you have to explicitly use "Return" on thunks in records to evaluate them, which sounds like the same thing a CBV language does.
Are there other benefits I'm not understanding?
Does the unification apply only to function parameters?
So the context of this is to solve a problem-in-practice with arguments in a lazy evaluation environment, which is that you don't know how many arguments you need to supply without doing the evaluation.
The OP uses a lisp-y syntax, fully parenthesized, for its code examples. But function arity isn’t so much an issue in these languages — you can infer it from the parentheses, and there’s no implicit currying. (The OP uses a Haskell-like syntax for its definitions, but I think it contains multiple mistakes, making it very hard to understand.)
A language with implicit currying and eager evaluation specifically of function arguments just seems overcomplicated to me. It sounds like a stack machine in which you pop an element off the stack, evaluate it enough to determine its arity, then pop that many more elements, evaluate them, and then apply the function. This sounds unpleasantly dynamic and quite hard to implement efficiently.
Am I missing something here?
I think it's important to note that the post is clearly written for someone working on the implementation of compilers/type systems. So for example, in a compiler IR, especially those based on an extended lambda calculus representation, functions/closures are often curried, i.e. only take a single argument. As a result it can be an issue at a given call site to know whether a function is "saturated", i.e. all of its arguments have been applied so it will do some work and return the actual result; or whether it is only partially saturated, in which case it returns a new function that needs one less argument than before. I gather that this interacts poorly with typing in some situations, but I'm not super familiar with the issues here as I haven't gone down the rabbit hole of building a compiler with this kind of IR.
That said, as someone who works as a compiler engineer, I do recognize the potential of call-by-push-value, namely that it reifies evaluation semantics in the IR, rather than it being implicitly eager or lazy, and thus having to hack around the lack of one or the other, i.e. implementing lazy evaluation on top of eager semantics or vice versa. Making it a first-class citizen enables optimizations that would otherwise be impossible or very difficult to implement. To be clear though, you can obviously implement lazy on top of eager, or eager on top of lazy, without call-by-push-value - but I think if you anticipate needing to do that, and you are building a new compiler, using a call-by-push-value IR might be a worthwhile approach to take.
There might be more to it that I'm not really seeing yet in my brief reading of it, but the post made sense to me, it's just assuming a lot about the reader (i.e. that you are deeply familiar with compiler implementation, type theory, etc.).