News for hackers. Stuff that matters.
Re:I'm Betting on Call-by-Push-Value by compressedgas on Saturday March 09, 2024 @09:27PM (#39656269)
So what they have made would be a more complicated version of https://en.wikipedia.org/wiki/A-normal_form
Re:I'm Betting on Call-by-Push-Value by Mathnerd314 on Saturday March 09, 2024 @10:40PM (#39656555)
I 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
Re:I'm Betting on Call-by-Push-Value by 082349872349872 on Sunday March 10, 2024 @07:55AM (#39658437)
I was very relieved to discover from 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)

Re:I'm Betting on Call-by-Push-Value by mrkeen on Sunday March 10, 2024 @05:03AM (#39657730)
I'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.

Re:I'm Betting on Call-by-Push-Value by 082349872349872 on Sunday March 10, 2024 @07:47AM (#39658407)
If it doesn't evaluate functions, how do closures get their lexical environments?
Re:I'm Betting on Call-by-Push-Value by mrkeen on Monday March 11, 2024 @06:47AM (#39666489)
How do they figure out what goes into their environment, or how do their environments get populated?

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
The closure is defined on line 3, and instantiated on line 6.

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
> Returning closure

> Evaluating xx

> 7

Re:I'm Betting on Call-by-Push-Value by Mathnerd314 on Monday March 11, 2024 @01:03PM (#39670693)
Well, the transformation doesn't change semantics, so technically you aren't "baking in" any form of evaluation strategy. It is a bit obscure but ANF is achievable by a series of simple rewrite rules, Figure 1 in https://dl.acm.org/doi/pdf/10.1145/141471.141563 or Figure 7 in https://dl.acm.org/doi/pdf/10.1145/173262.155113. But the transformations are certainly biased towards CBV, the syntactic notion of "machine value" that ANF uses doesn't make much sense in call-by-need or call-by-name where any expression can be a thunk.

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.