Evaluation strategies: authoritative reference?

The Wikipedia page on evaluation strategies conflates "pass by value" with "call by value". Is this authoritative? Does anyone know where "pass by value" and "pass by reference" were first defined?

"Pass by reference" is described as an evaluation strategy such as found in assembly with registers, where modifying a local in a child scope modifies the local seen in a parent scope, eg. updating a callee-save register changes the value seen by the caller after returning.

"Pass by value" describes the strategy where arguments of the parent scope cannot be modified in a child scope, even though the value itself can be modified. This is, rightly or wrongly, conflated with call-by-value. For instance, the following type in OCaml, type Foo = { mutable x:int }, is still "passed by value" even though mutations in the child scope are visible in the parent. This doesn't seem mutually exclusive with "pass by reference" though, since one cannot distinguish between mutating a Foo and mutating the local in the parent of Foo.

"Pass by sharing" seems like a useful distinction that would resolve a lot of this confusion, but isn't in common use.

Is this the authoritative meaning of these terms? Is there an original or authoritative source where these terms are defined more rigourously?

There seems to be great confusion surrounding this issue, particularly when you consider that "value types" and "reference types" are both considered to be "passed by value" in Java. In other words, the evaluation strategy terminology is inconsistent with the terminology used to describe a language's primitive values.

However, if the terms were used consistently, introducing side-effects to a type would change it from a value type into a reference type. Any pointers to authoritative references would be much appreciated.

References are values

A problem with your terminology is that "value" and "reference" are not very well defined. I assume it comes from languages where, for every type (a "value"), you have the type of pointers to this type (a "reference"). But the reference is itself a value (of the pointer type), and you could say "no, this isn't an integer passed by reference, it's a integer pointer passed by value".

Ultimately it all boils down to questions of data representations : are your structures always heap-allocated and denoted by pointers, or can you denote them directly, and flatten then into bigger structures ? I think that the "mutation inside the child scope" question is more a consequence of these representation issues; in particular, it's unrealistic to expect a deep copy of the parameters 'passed by value', so the mutability point of view is always shallow.

In lambda-calculus, people don't usually directly reason on mutability when describing evaluation strategies. They wonder wether a term is fully evaluated (it's a value, that's how values are defined) or not. If you requires your terms to be fully evaluated before substitution in the body of the function, it's call by value -- call by reference is call by value, where the value of some expressions is a location in the memory. If you don't evaluate anything and substitue the term at each occurence of the function variable, it's call by name. Call by need is an optimisation of call by name where you add memoization to ensure the arguments are evaluated at most once.

If you're more interested in describing the mutations over your parameters and return, maybe you should look at Ada parameters passing mode. They're quite nice and clearly defined; in particular, I think it's interesting to handle "mutation of an unitialized value as a way to produce output" (out parameters) differently than "mutation of an existing value".

By gasche at Thu, 2011-01-13 18:59 | login or register to post comments

If you requires your terms

If you requires your terms to be fully evaluated before substitution in the body of the function, it's call by value -- call by reference is call by value, where the value of some expressions is a location in the memory.

This is my understanding of call-by-value as well, and implies that conflating pass-by-value and call-by-value is a mistake. What then is the meaning of pass-by-value? And where did the distinction of "value types" and "reference types" come from, and why are they unrelated to to pass-by-value/reference? They seem very related to me, but the Wikipedia page implies otherwise.

The definition of pass-by-reference distinguishes itself from pass-by-value merely by a different handling of scope. It just conflates different issues unrelated to evaluation strategy. I agree this value/reference issue is also somewhat about representations, but the terminology used just seems inconsistent, so I was wondering where it came from, or if anyone had any pointers to explain the rationale behind them.

If you're more interested in describing the mutations over your parameters and return, maybe you should look at Ada parameters passing mode. They're quite nice and clearly defined; in particular, I think it's interesting to handle "mutation of an unitialized value as a way to produce output" (out parameters) differently than "mutation of an existing value".

Yes, Ada and C# share this semantics, ie. 'ref' and 'out' parameters.

By naasking at Thu, 2011-01-13 19:28 | login or register to post comments

1. Re Ada: Don't forget that

1. Re Ada: Don't forget that nice bug HB found, about limited types, which are now passed by reference ("How to steal from a limited private bank account").
2. Re the terminology: Seems to me that part of the problem, with this and with some of the terms related to typing discipline, is that the meaning of the terms is relative to the language semantics, though we tend to abstract this away and pretend they have a generally applicable meaing. The latter, however, is an intuitive notion, not a precise definition, which has to be relative to semantics.

By Ehud Lamm at Thu, 2011-01-13 19:53 | login or register to post comments

Ah, limited types, that

Ah, limited types, that takes me back a few years. :-)

I agree we infer some imprecise, generally applicable meaning to these terms, which is clearly why there's so much confusion. Rubyists call Ruby pass-by-reference and Java proponents call Java pass-by-value, even though they have the exact same semantics. It's ridiculous.

I suppose then my most general question is whether the nature of scope is a legitimate concern for an evaluation strategy. If not, then I will simply conclude that call-by-reference doesn't exist as an evaluation strategy, and that this distinction is simply conflating different issues scoping, representation, and evaluation strategy.

By naasking at Thu, 2011-01-13 20:11 | login or register to post comments

I am not sure I follow your

I am not sure I follow your argument about the role of scope, but generally I do think it matters. Clearly if you don't have nesting at all, things become rather different.

By Ehud Lamm at Thu, 2011-01-13 23:56 | login or register to post comments

The scope argument is

Call-by-reference is semantically equivalent to call-by-value + dynamically scoped variables. The dynamic scope is the only distinguishing property from call-by-value, and that property seems like a totally orthogonal concern from the evaluation strategy.

Thus, I was asking whether this distinction in scoping warrants call-by-ref being classified as a distinct evaluation strategy.

By naasking at Fri, 2011-01-14 00:28 | login or register to post comments

I would put it like this: in

I would put it like this: in a language with dynmically scoped variables, cab-by-ref and call-by-value are not distinct evaluation stratgies.

By Ehud Lamm at Fri, 2011-01-14 00:48 | login or register to post comments

Dragon book

I don't know how authoritative this is. The first (1979) edition of the Dragon book use

Call-by-Reference: (with synonyms: call-by-adrdress or call-by-location) when passing a pointer to the r-value of each actual parameter. Citing PL/I as one language where it is used. The description is similar to what C++ would provide for reference parameter if one was allowed to bind temporaries to non-const reference.
Call-by-Value: r-values are passed to the subroutine.
Call-by-Value-result: (copy-in copy-out, copy-restore) is presented as a generalization of Call-by-Value where the parameters are copied back to their source after the execution of the routine
Call-by-Name: is well known Algol method (passing two parameter-less functions, one for writing and one for reading) equivalent to in-line expansion of the parameters

I've not seen pointers to previous work in the bibliographic notes at the end of the chapter.

I don't remember having ever seen a difference between call-by-value and pass-by-value and I'm not sure I understand the one you are making (how far would I be if I reformulated this in C terms as passing a pointer to a constant and passing a pointer to something not constant?).

Trying to be cleared: here is how I see the operational effects of the different methods:

if you can use it for Jensen's Device, it is call-by-name,
if you can't give the side effects of a swap (t if modifications made to aliases aren't seen, it is call-by-copy-restore,
else it is call-by-reference

I don't see where a nuance between "call-by-value" and "pass-by-value" or "pass by sharing" would fit here. It seems to me that the confusion is between a reference/pointer and the objected pointed to (Algol 68 is among my first programming languages, that may explain my vision of the world).

By Jean-Marc Bourguet at Thu, 2011-01-13 20:31 | login or register to post comments

Thanks for the reference, I

Thanks for the reference, I hadn't considered the Dragon book as a source of these terms, though it's obvious in hindsight.

I don't remember having ever seen a difference between call-by-value and pass-by-value and I'm not sure I understand the one you are making (how far would I be if I reformulated this in C terms as passing a pointer to a constant and passing a pointer to something not constant?).

The distinction was a matter of representation of the values as they are passed as arguments. Passing "struct Foo" in C would be passing it by value, where passing "struct * Foo" would be by reference.

Re: call-by-ref, call-by-copy-restore, etc. these are semantically just dynamic scoping. My tentative conclusion now is that these classifications conflate too many separate issues, some of which are distinguished based on implementation details instead of the semantics.

I'll be sure to stick to discussing the more formal concepts of evaluation strategy (call-by-value/call-by-name/call-by-need/call-by-push-value), parameter data representation (value/reference), and scope (lexical/dynamic), which are unambiguous.

It seems to me that the confusion is between a reference/pointer and the objected pointed to

Yes, but these are in languages where such a distinction doesn't exist. There are only references, hence pass by reference.

By naasking at Thu, 2011-01-13 21:52 | login or register to post comments

My current guess is that

My current guess is that there are two ways of thinking about parameter passing. Neither is more ambiguous than the other but as they share at least part of the vocabulary, the vocabulary is ambiguous if the definition used isn't clear from the context.

When Ada mandates call-by-copy-restore for in out parameter of scalar types, when Fortran mandates call-by-ref, it isn't implementation which is specified, it is semantic. Those are perhaps a combination of an evaluation strategy with a parameter data representation and a scope, but I'm not sure it is the case for copy-restore. In lispy syntax,

(define foo (lambda (a b)
   (set! a 42)
   b))
(define x 36)
(foo x x)

For both reference and copy-restore, x would be 42 after the call to foo. But for copy-restore, the result of foo would be 36 and for reference it would be 42.

Re: call-by-ref, call-by-copy-restore, etc. these are semantically just dynamic scoping.

If in DrScheme I do:

(define foo (lambda (bar)
              (let ((qux 42))
                (eval bar))))
(define qux 36)
(foo 'qux)

I get 36. If in Emacs lisp (which is the dynamically scope lisp I've available) I do:

(defun foo (bar)
  (let ((qux 42))
    (eval bar)))
(setq qux 36)
(foo 'qux)

I get 42. The value I expect for

(defun foo (bar)
  (let ((qux 42))
    bar))
(setq qux 36)
(foo qux)

with pass-by-reference is 36. That seems more tied to static scoping than dynamic one (at least with the definition I know).

If you are still looking at old references, Jean Sammet in Programming Languages: History and Fundamental is using "call-by-location" and "call-by-simple name" for call-by-reference.

By Jean-Marc Bourguet at Sun, 2011-01-16 09:55 | login or register to post comments

If in DrScheme I do: [...] I

If in DrScheme I do: [...] I get 36. If in Emacs lisp (which is the dynamically scope lisp I've available) I do: [...] I get 42. The value I expect for [...] with pass-by-reference is 36

I've given this some thought, and I'm not convinced of the last example's equivalence to the preceding programs you listed because of the interaction of quoting/eval with the environment. These examples don't seem to isolate the specific behaviour of parameter passing only.

In any case, the correspondence is not so trivial as I originally stated here. There's actually a very small, local transform required to get it in exactly the right form, so it's quite not as trivial as call-by-ref = call-by-value + dynamic scoping.

Thanks to everyone for the references. There was certainly a richer history behind this question than I thought. The discussion definitely helped clarify my thinking, and it's unfortunate that terms in industry are so overloaded that they cause these kinds of confusion (and flame wars).

By naasking at Tue, 2011-02-15 01:42 | login or register to post comments

Call by Reference doesn't mean a C#, C++, or Java Reference

First of all, you must forget everything you know about the word "reference" in C#, Java, or C++. It has nothing to do with reference types from those language. Rather, the definition that applies here is simply "to refer to" or "to mention".

So the basic terms are:

Call by Value
Call by Reference
Call by Name

When passing variable

With call by value the function being called gets a copy of the value.

With call by reference the function being called gets a pointer to the variable containing the value. This allows you to write Swap functions.

With call by name the function being called gets the expression that refers to the variable. Depending on the language this may allow you to write a Swap function.

When passing expressions

With call by value the expression is fully evaluated before the function is called.

Generally speaking call by reference cannot be used with expressions. Some languages fake it by creating a temporary variable that is passed in.

With call by name the expression itself gets passed to the function. The function can decide to evaluate the expression once, many times, or not at all. This allows interesting tricks like Jensen's Device, where in the expression may return a different result with each evaluation.

Depending on the language, call by name may allow for examining the abstract syntax tree of the expression.

Examples using C#

By value:

void Foo(int x)


Foo(1);

Foo(x);

Foo(x+y);

By reference

void Foo(ref int x)


//constants are not allowed

Foo(ref x);

//x+y is not allowed

By name (which, as you can see, is somewhat clumsy in this language)

void Foo(Func x) OR void Foo(Expression x)


Foo(() => 1);

Foo(() => x);

Foo(() => x+y);

Others

Call by sharing seems to be another word for call by refernce.

Call by need is used by functional programming languages. Like call by name the function determines if and when to evaluate the expression. The main difference is that the result will be remembered so that there is never a reason to evaulate the same expression more than once.

"Pass by XXX" is just another way of saying "Call by XXX". They were both used since the 70's, with call by being slightly older.

By Jonathan Allen at Sat, 2011-01-15 21:43 | login or register to post comments

Is Jensen's Device really about evaluation strategies ?

This allows interesting tricks like Jensen's Device, where in the expression may return a different result with each evaluation.

I've always felt that the point of Jensen's Device is more about variable scopes that parameter passing per se. You write an expression with a free variable, knowing that it will only be evaluated in a context where the variable is actually bound. You would emulate it in a non-Jensen programming language by abstracting over the variable, and applying it at the use site, regardless of the evaluation strategy.
I also don't think formal definitions of call-by-name in lambda-calculi allow Jensen's Device.

By the way, it seems to me that the wikipedia page on evaluation strategies is contradictory, as it claims that call-by-name both perform a capture-avoiding substitution and allows Jensen's Device:

In call-by-name evaluation, the arguments to functions are not evaluated at all â€” rather, function arguments are substituted directly into the function body using capture-avoiding substitution. If the argument is not used in the evaluation of the function, it is never evaluated; if the argument is used several times, it is re-evaluated each time. (See Jensen's Device.)

By gasche at Sat, 2011-01-15 22:38 | login or register to post comments

I will admit my

I will admit my understanding of call-by-name is pretty rough. It is hard to truly understand it without access to a modern language that supports it.

As for wikipedia, the articles on any CS terminology coined prior to the late 90's is pretty bad. And the fact that we tend to reuse terms like reference to mean lots of different things only compounds the problem.

I've actually started to collect old CS books so that I can correct some of the more glaring errors, but I need lots of references before I can say with confidence that the wiki is truly wrong.

By Jonathan Allen at Sun, 2011-01-16 05:43 | login or register to post comments

it claims that call-by-name

it claims that call-by-name both perform a capture-avoiding substitution and allows Jensen's Device:

The names used in the callee have no influence on the result of the function.

By Jean-Marc Bourguet at Sun, 2011-01-16 09:59 | login or register to post comments

A paper about this

A paper about this can be found here. See section 7. I don't know if it is very authoritative, but is quite formal and comprehensive.

By Jorge García at Sun, 2011-01-16 09:55 | login or register to post comments

Algol 60

Traditional Algol 60 thunks actually returned a pointer to the result of the evaluated expression; if the expression was not an lvalue, this pointed to a scratch location on the stack. Consequently, taking the value of a CBN parameter was implemented by invoking the thunk and dereferencing the result, and assignment by invoking the thunk and assigning through the pointer. Assignment was therefore always safe, but had no effect outside the callee if the expression was not an lvalue.

By johnwcowan at Sun, 2011-01-16 18:42 | login or register to post comments

CTMCP of P. van Roy and S. Haridi

CTMCP of P. van Roy and S. Haridi has also definitions for call by reference, call by value, call by value-result, and call-by-name to which they add call-by-variable and call-by-need which aren't based on your structure evaluation strategy, parameter data representation, and scope.

By Jean-Marc Bourguet at Sun, 2011-01-16 19:01 | login or register to post comments

On pronouncing Niklaus Wirth's name

"You may call me by name, and call me Veert, or you may call me by value, and call me Worth."

By johnwcowan at Wed, 2011-02-16 02:55 | login or register to post comments

Lambda the Ultimate

User login

Navigation