5 ms·
I'm Betting on Call-by-Push-Value
- ildjarn 3y ago[flagged]
- deleted 3y ago[deleted]
- falcor84 3y agoI really want to like this more, but need a better notation
- rezonant 3y agoCan someone TLDR this? It's pretty thick, and I can't help but think this is a solved problem with the ability to pass functions as arguments. What's the new insight here?
- deleted 3y ago[deleted]
- amluto 3y agoI can’t. I think it would have been nice if the article defined the terminology it used to describe its toy languages. 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; } in C++. Maybe there’s more to it than that.
- Dylan16807 3y agoIt feels like half the text is dealing with arity confusion that only comes up because of a particular way of implementing functions. 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?
- amluto 3y agoI found it almost impossible to understand. The syntax used for their examples was lisp-like, and the function arity seems unambiguous. There is no implicit currying in lisp as far as I know. Extra-confusingly, the definitions at the start were in a syntax resembling Haskell, but I think it has multiple mistakes.
- crq-yml 3y agoIf you're in eager evaluation land, everything evaluates as you come to it, so you can handle all arguments at runtime by using a stack and no problem is felt. Once we say, "actually we don't evaluate until it's used" ambiguity arises. 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.
- analognoise 3y agoIs that what they mean by “calculating the arity”?
- crq-yml 3y agoYes, arity is "number of arguments". I don't have expertise in lazy evaluation myself, I've just been exposed to enough of it to explain the motivations.
- amluto 3y agoI’m very far from an expert in these styles of programming languages, but I’m pretty sure I’m missing something, and it’s not well explained in the OP. 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?
- bitwalker 3y agoI wouldn't read too much into the syntax - the Haskell-like definitions are just a succinct way to describe the AST representation for the toy call-by-push-value language the post is talking about. Similarly, the syntax that resembles LISP, is actually (I believe) just shorthand for how the language would be represented in an extended lambda calculus with call-by-push-value semantics. 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.).
- charcircuit 3y agoImagine if functions were polymorphic over the ability to pass in a function as an argument. So both f(1) and f(() => 1) would be valid for a function that takes a number. It would also apply to variables and such too. So "const a = () => 1; const b = a + a;" would be possible to do.
- rezonant 3y agoThis is a good explanation. So effectively it's making the lazy/eager distinction controlled by the caller and not the callee.
- Izkata 3y agoAhh k. So like Rebol and Red have worked for decades: >> F: func [A][print type? :A print join "Arg: " A] >> F "Foo" string Arg: Foo >> F func [][return "Bar"] function Arg: Bar I really got spoiled learning Rebol as my first language, I'd already internalized a ton of concepts long before they were introduced during school and college. Higher-order functions were the first time I really realized it, I guess here's another to add to the pile. 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.
- vidarh 3y agoThat's already the case for any dynamic languages, and it's just down to whether you write your code to be flexible about inputs. E.g def int(i) = i.respond_to(:call) ? i.call : i.to_i def f(i) = int(i) * 2 f in this case can take both ints and lambdas or anything call-able. 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.
- burakemir 3y agoIt is nice to see CBPV on HN. It is a calculus that deal with a fundamental choice in PL of how to approach evaluation. For a different take, here is the first part of a mini series of posts on CBPV that aims at working out the connection to logic ("polarised natural deduction"): https://burakemir.ch/post/cbpv-pt1-small-steps/ https://burakemir.ch/post/cbpv-pt1-small-steps/
- zozbot234 3y agoInteresting to see (in the followup posts) that the structure of CBPV seems to lead to "lazy" records as a natural choice, contrasting with "strict" primitive values and sum types, and "lazy" function types. The connection to polarity and focusing is also worthy of note.
- p4bl0 3y agoThis made me think of Kernel, a programming language of the Lisp family where the main primitive is vau rather than lambda, defining a fexpr rather than a function. 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 https://web.cs.wpi.edu/~jshutt/kernel.html about Kernel :).
- dmux 3y agoI’m not familiar with the theoretical aspects, but what you’re describing reminds me of Tcl: arguments to procedures can be passed unevaluated (quoted, using Tcl terms) and the procedure itself can alter the caller’s environment via uplevel.
- bradrn 3y agoIt’s also extremely similar to R and Rebol. (In fact, R isn’t just ‘extremely similar’: it does use fexprs, though without mentioning the term.)
- Tyr42 3y agoIt's what let's the tidy data tools take arguments like .x where x is a column name, not a local varia le that's in scope.
- nerdponx 3y agoR is even more wild because you can access the entire definition of a function from the function object itself. You can literally make a new function that's a copy of an existing function with some lines of code injected.
- skybrian 3y agoI’m wondering what’s gained over writing your thunks as zero-argument functions (etc) in an eager language.
- p4bl0 3y agoIf I understand correctly, here it is transparent. In an eager language a function needs to know whether it is given a value or a thunk, but here it can be both interchangeably (the thunk only need to have a type that says it returns a value of the same type as what could have been passed directly).
- soulbadguy 3y agoIn theory, yes i would agree that they might be a different somewhere. But it's not clear (at least to me that) is this distinction maters in practice. 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.
- jayd16 3y agoIs it transparent? It seems like the goal is to be deliberate through explicit calls to thunk(). I guess you mean that a function parameter can be both a value or lambda.
- tel 3y agoThere are a few differences, depending on how you evolve from the CBPV core, but basically other types may be eager or lazy. Functions can be eager (and thus statically know to represent an eager call tree) and sum types can be lazy (deferring choice). These distinctions are all available at the type level. 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.
- erik_seaberg 3y agoNot sure I see a difference between thunks and futures.
- iso8859-1 3y agoThunk is a general concept of a small function which is used only to adapt the call or prepare/modify it in some way and then redirect to the proper function. Things like promises, futures, closures, wrappers, stubs or implementations of the concept of virtual function tables in some OO languages (like C++) are just special use cases of thunks (thunks are often used to implement them). Source: https://stackoverflow.com/a/22548372/309483 https://stackoverflow.com/a/22548372/309483
- soulbadguy 3y agoThe definition that the source is using seems wrong to me. Promise,futures and closures are not used to redirect to anything or wrapper around something else... They are proper compationational object with they own behaviors...
- Mathnerd314 3y agoI got really excited about call-by-push-value about 15 years ago, when I first encountered it, but at this point I think it is overhyped, particularly the presentation of "values" and "computations" as duals. For example see http://www.itu.dk/people/mogel/papers/eec.pdf http://www.itu.dk/people/mogel/papers/eec.pdf, it is a CBPV-style lambda calculus except computations are a subset of values and there is no duality. Similarly in Levy's book, he discusses "complex values" like 1+2 which allow pure computations to happen inside the "value" type, more evidence that they are not duals at all. 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.
- compressedgas 3y agoSo what they have made would be a more complicated version of https://en.wikipedia.org/wiki/A-normal_form https://en.wikipedia.org/wiki/A-normal_form
- Mathnerd314 3y agoI hadn't thought about it that way, but it makes sense. I would say the main difference is that ANF is type-preserving, whereas CBPV introduces new types. But they are similar in that they are IRs with accompanying translations from standard lambda calculus. You can see the translations of CBV/CBN on page 11 of https://www.cs.bham.ac.uk/~pbl/papers/tlca99.pdf https://www.cs.bham.ac.uk/~pbl/papers/tlca99.pdf
- 082349872349872 3y agoI was very relieved to discover from https://www.cs.bham.ac.uk/~pbl/papers/siglogcbpv2.pdf https://www.cs.bham.ac.uk/~pbl/papers/siglogcbpv2.pdf that PBL has learned how to explicitly number pages in the intervening decades. (see Fig. 6 p.21)
- mrkeen 3y agoI'm not so sure. 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.
- gatlin 3y agoShameless self promotion: I made a toy CBPV language in TypeScript. It's purely for pedagogy. The idea is that the implementation is essentially an executable small step semantics, and the interop between language and machine is real purdy. https://niltag.net/code/precursor https://niltag.net/code/precursor
- dfgdfg34545456 3y agoIs the toy language all self contained in that repo? I can see it pulls in some deps, wasn't sure if everything I need to see is in that precursor.controller.ts file or elsewhere.
- gatlin 3y agoNo, I'm annoying and split it up. https://github.com/gatlin/precursor-ts https://github.com/gatlin/precursor-ts https://github.com/gatlin/precursor-ts/blob/main/src/ceskm.ts https://github.com/gatlin/precursor-ts/blob/main/src/ceskm.t...
- dfgdfg34545456 3y agoCheers
- AtlasBarfed 3y agoSo you abstract a function argument behind an interface: .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
- Izkata 3y agoI don't know groovy, but it looks a bit like method chaining, except using an external object/method "with" to chain standalone functions?
- kaba0 3y agoI think what you are getting at is usually called piping. Some languages have it inbuilt (usually as a |> operator).
- AtlasBarfed 3y agoIt is! 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.
- jayd16 3y agoSo in practice using a parameter could be surprisingly very expensive? Are you supposed to thunk all your parameters before grabbing a resource? 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?
- userbinator 3y agoWho else looked at the title and thought "isn't that __cdecl?" and was expecting an article about calling conventions, but got something related yet completely different? For an article about efficiency, there seems to be a noticeable absence of actual instruction sequences for comparison.
- aranchelk 3y agoPersonally I like how PureScript has done it, as essentially an eager Haskell, they just implemented laziness in a library, you loose some of the elegance of laziness by default, but most of the time I want eager expressions anyway, and when I don’t it’s clear what I’m doing and easy enough to make stuff lazy. https://pursuit.purescript.org/packages/purescript-lazy/3.0.0/docs/Data.Lazy https://pursuit.purescript.org/packages/purescript-lazy/3.0....
- vidarh 3y agoOne of the things I realized from having support for lazy evaluation in Ruby's Enumerable is that while it's great on a very few occasions, as you say most of the time I want eager evaluation, and even most of the times where I don't care for any specific expression, it ends up being forced so close by anyway that it is in practice little different. 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.
- JonChesterfield 3y agoThe case analysis for this stuff often seems incomplete. Let's say you're going to "pass something to a function", what're the common options: 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.