3
$\begingroup$

There are three standard evaluation strategies for the lambda calculus:

There are two variants of CBV that differ on how they behave with respect to applications:

  • Left-to-right: Evaluates the function first
  • Right-to-left: Evaluates the argument first

These are described in greater detail in sections 6.1 and 6.2, respectively, of [1].

What are the advantages and disadvantages of each approach?


References:

  1. Distilling Abstract Machines (Long Version). Beniamino Accattoli, Pablo Barenbaum, Damiano Mazza. 2014-06-09.
$\endgroup$
2
  • 4
    $\begingroup$ The question should make clear if it is about functional languages or about parameter passing in general. If the focus is functional languages, it should make clear if it is only about pure semantics or about real world functional languages. $\endgroup$
    – feldentm
    Jul 27, 2023 at 18:29
  • $\begingroup$ The question seems to ask about subjective, practical assessment of consequences, but that might be a bit difficult to do in terms of pure lambda calculus. Most actually implemented, practical languages conceive of functions as potentially having more than one argument, or no arguments; and in a lot of them there isn't meaningful runtime "evaluation" of functions. I'm guessing you specifically have in mind Haskell-family languages, but already there's an answer talking about Java that's hard to relate to the apparent conceptual framework here. $\endgroup$ Jul 27, 2023 at 22:22

1 Answer 1

1
$\begingroup$

Java uses left to right because this is what most users seem to expect.

Actually, there is another approach: unspecified and let the compiler decide based on whatever it needs or wants to do and let it optimize.

If the question is about languages in general and not specifically about functional languages, the most obvious effect is that on side effects. I.e. f(++x, ++x) can increment either the left or the right first. You get similar effects if you pass two function results with global side effects like reading a file or calling a web server. It doesn't necessarily require mutable entities in your language.

$\endgroup$
2
  • $\begingroup$ The question is talking about 'pure' lambda calculus where functions can only have one argument, so there's no question of ordering between arguments. $\endgroup$
    – Chris Dodd
    Jul 27, 2023 at 22:51
  • $\begingroup$ @ChrisDodd By Currying, though, left-to-right evaluation of single-argument applications ((f (++x)) (++x)) and left-to-right evaluation of a list of arguments (f(++x, ++x)) practically coincide (and similar for right-to-left). $\endgroup$
    – James Wood
    Jul 29, 2023 at 11:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .