Talk:Evaluation strategy

From Wikipedia, the free encyclopedia

Contents 1 Evaluation order 2 Macros 3 call-by-value-result 4 call by name in SQL 5 scheme uses call-by-reference 6 Evaluation strategy vs parameter passing mechanism 7 Strict/Eager and Non-strict/Lazy 8 Conditional Statements 9 Content seems to cover only function calls... what about expressions in general?

[edit] Evaluation order

I've removed the following paragraph from the article:

Note that call-by-value does not necessarily mean left-to-right evaluation. While most programming languages that use call-by-value do evaluate function arguments left-to-right, some (such as O'Caml) evaluate functions and their arguments right-to-left.

Firstly, it's not clear what purpose this is supposed to serve. I don't see anything in what precedes it that might be taken to imply that evaluation is left-to-right. If this is considered an important point, it could be made in just two or three words by adding to the previous paragraph a statement that the order of evaluation may vary.

Secondly, it's partly unsourced and partly inaccurate. Unsourced: while it seems likely that "most" call-by-value languages evaluate left-to-right, it's not a claim we can make without providing evidence. And inaccurate: OCaml uses call-by-reference, with the exception that immutable int values are encoded as nonaligned pointers and can therefore be passed by value.

— Haeleth Talk 14:02, 7 February 2006 (UTC)

The purpose of the paragraph is to inform the reader that call-by-value evaluation is not one particular strategy, but rather a family of strategies.

O'Caml uses call-by-value, just like any other ML. If you want to pass a reference into a function, you pass an explicit reference by value, which brings me to another point.

Your removal of C++ bias in the article is appreciated; however, you've introduced some factual inaccuracies — for example, a pointer is not the same as a reference, and while many functional languages represent large heap values as boxed pointers, they are semantically call-by-value becasue the values pointed to do not change. We're not talking about calling conventions, we're talking about evaluation strategies. --bmills 14:49, 7 February 2006 (UTC)

Clem Baker-Finch is my Comp Lecturer! Go Clem! (he's a funny guy) 61.9.204.168 04:12, 5 June 2006 (UTC)

[edit] Macros

I'm wondering wether the section about call-by-macro-expansion is accurate: not all macros are text substitutions. To the best of my knwoledge, the very first macro system that ever existed in fact isn't textual, but has a call-by-name evaluation strategy (the Lisp macros). Some languages tried to catch up with the properties of such call-by-name macros, like Dylan and Perl6 (maybe others, and I can't be sure for Dylan, as I never touched this language). —The preceding unsigned comment was added by Nowhere man (talk • contribs) 19 August 2006.

[edit] call-by-value-result

The article currently says

Call-by-copy-restore or call-by-value-result is a special case of call-by-reference where the provided reference is unique to the caller.

Um, I'm fairly certain that call-by-value-result does not involve a reference, but instead copies the value in and out (ideally in registers, but compilers using a caller-restores-stack protocol can copy results off the stack). I know the Ada 83 spec had special rules for the interaction of in out parameters and exceptions to allow implementors to use call-by-reference for large types but require use of call-by-value for small types.

Is not a correction needed here? Cheers, CWC(talk) 19:19, 23 August 2006 (UTC)

[edit] call by name in SQL

Jet SQL uses a version of call-by-name/call by need. when used as arguments for a column, functions with no dynamic arguments are memoized, functions with dynamic arguments are call-by-name, which means that they are called multiple times. there is no protection against side affects, so a function may return different values for the same arguments. 218.214.148.10 00:10, 27 September 2006 (UTC)

[edit] scheme uses call-by-reference

According to the current draft for r6rs, scheme uses call-by-value, but not in contrast to call-by-reference, but in contrast to lazy evaluation. It also says that Scheme always uses call-by-reference. So in the terminology of this article it uses call-by-reference, not call-by-value. --MarSch 16:59, 20 October 2006 (UTC)

Here's the relevant paragraph, copy-and-pasted from page 5 of draft 91 of R6RS, with two words emphasised:

Arguments to Scheme procedures are always passed by value, which means that the actual argument expressions are evaluated before the procedure gains control, whether the procedure needs the result of the evaluation or not. C, C#, Common Lisp, Python, Ruby, and Smalltalk are other languages that always pass arguments by value. This is distinct from the lazy-evaluation semantics of Haskell, or the call-by-name semantics of Algol 60, where an argument expression is not evaluated unless its value is needed by the procedure. Note that call-by-value refers to a different distinction than the distinction between by-value and byreference passing in Pascal. In Scheme, all data structures are passed by-reference.

Remember that Scheme variables are bound to locations, which in turn contain values. In (say) Pascal, proc(x) can modify the variable x if proc uses call-by-reference (ie., a "var" parameter). In Scheme, (proc x) can never modify the contents of the location bound to x (assuming proc is a procedure). So, strictly speaking, Scheme uses call-by-value.

The complication is that Scheme has "pointer semantics": if x is a vector, the location bound to x holds a pointer to the vector, not the vector itself, and that pointer is copied into proc, which can use vector-set! on the vector. In this case, after proc returns, x is still bound to the same location, and that location still contains a pointer to the vector, but the contents of the vector have been changed. (In Pascal, if x has type (say) array [1..3] of real, using x as a value parameter means copying the whole array and can never modify x.) Similar arguments apply to the other non-atomic types: pairs, strings, records, etc. So (proc x) cannot modify the contents of x, but can indirectly modify the value of x by modifying the data structure to which x refers.

In short, because Scheme has a layer of indirection between variables and data structures, it is call-by-value as far as variables are concerned, but call-by-reference as far as non-atomic values are concerned.

I hope this helps. Cheers, CWC(talk) 10:30, 21 October 2006 (UTC)

The semantics of Scheme are identical to those for objects in Java. The only thing that you can manipulate or pass in Scheme are references. Variables are references, you can give a variable another value by changing where the reference "points to". So in that sense, yes, you pass the "value" of references, so it's pass-by-value. Data structures are structures of references. I usually like to think there are no data structures at all, since they are not fundamental, and can always be constructed using lambda's. If you take this perspective, then the "mutability" of elements of data structures corresponds to the ability to change variables (which are references). And it becomes very simple: you can only deal with references (all expressions are references), and the values those references point to are immutable. --Spoon! 05:58, 22 October 2006 (UTC)

I think I follow you. Since any object can be represented by a closure in which the components of the object are stored as variables, object-mutation primitives like set-car! are in a way special cases of good old set!. Hmm, I want to ponder that one a bit more, because I've been thinking of set! as the location-mutator and set-car! etc as conceptually distinct object-mutators (partly from reading the discussion of SRFI-17). CWC(talk) 13:37, 22 October 2006 (UTC)

[edit] Evaluation strategy vs parameter passing mechanism

Isn't there an important distinction between concepts like normal and applicative order reduction and concepts like call by reference, call by value and call by name? The former concern the rule(s) used for reducing an evaluation to a final result, while the latter concern how parameters are passed to a function. There's a clear relation, a particular evaluation strategy may restrict the kinds of parameter passing mechanisms that can be used; but the basic concepets are different. Abcarter 14:33, 14 December 2006 (UTC)

[edit] Strict/Eager and Non-strict/Lazy

In the reading that I've done, strict and eager are pretty much equivalent terms. I could easily be wrong, but I'm certainly confused why "Church encoding" is the determining fact here. The issue with non-strict and lazy is not as simple, but in most of the literature I've read lazy is a type of non-strict evaluation where every argument is never evaluated more than once. But the same confusion remains why Church encoding is particularly relevant here. Could someone please provide a citation. Abcarter 01:55, 19 December 2006 (UTC)

[edit] Conditional Statements

I deleted the sentence concerning conditional statements in the section on non-strict evaluation. As the definition itself mentions, non-strict evaluation is about how arguments to a function are processed. There is a fundamental distinction here: expressions can be passed to an argument, a command or statement cannot. Abcarter 02:10, 19 December 2006 (UTC)

"Statement" was probably the wrong word in "conditional statement", but the concept was sound; consider the conditional structure in Lisp (which is essentially a function with non-strict evaluation, though in Lisp all "functions" use strict evaluation, so instead it's a "macro"), the ternary operator in C/C++/Perl/etc. (which is an operator, not a function, and indeed not even overloadable in the C++ case so really not a function, but still an example of an operator with non-strict evaluation, unlike most C and C++ operators), and the conditional structure in ML (which is like the ternary operator as used in C and C++, except that ML is stricter about the whole boolean thing). —Ruakh_TALK 03:21, 19 December 2006 (UTC)

OK, "conditional expression" is a different matter. My own area of interest is functional programming so there's a world of difference between statements (bad) and expressions (good) :). But now consider a conditional expression that returns a list, something of the form:

IF <boolean list> THEN <list expression> ELSE <list expression>

The idea would be to return a list containing values from either the first or second list expression depending on the boolean values. In this case both expressions would be evaluated. —The preceding unsigned comment was added by Abcarter (talk • contribs) 11:48, 19 December 2006 (UTC).

Thought more about it and after some additional reading added back a reference to conditional expressions. Abcarter 16:42, 30 December 2006 (UTC)

I am not seeing an interesting difference between short-circuit evaluation and the use of lazy evaluation in conditional expressions. Isn't lazy evaluation in a conditional expression an instance of short-circuit evaluation? There are three sub-expressions in a conditional expression. If the first sub-expression is true then evaluate the second sub-expression, otherwise only evaluate the third. It's no different than evaluating the Boolean expression (p -> q) v (-p -> r). I've done a 360 on this question a couple of times, so I'm happy to hear a different opinion. Abcarter 04:07, 31 December 2006 (UTC)

Is your question a response to my recent edit? If so, here's my attempt at explaining my thought process: programmers sometimes use the short-circuiting of a language's AND and OR operators to effect conditional-like evaluation (e.g. in something like if(ptr != NULL && *ptr != 0) in C or C++, where &&'s short-circuiting effect prevents ptr from being dereferenced if it's the null pointer), but this isn't really the primary reason for the short-circuiting: the primary reason is to avoid needless computation when the ultimate value of a boolean expression is already known. (Well, in modern languages it can be hard to tell which is the primary reason, as the two are rather intertwined now, but I think a convincing argument can be made that laziness was the original reason, at least.) By contrast, the short-circuiting of a language's conditional operator is absolutely fundamental to its functioning, at least in a language where expressions can have side effects (which so far as I know is the case in every language that has a conditional operator; there are languages where really only complete statements have side effects, but I don't know of any that are of that type and that nonetheless have conditional operators that can be used in expressions). I hope that explanation makes some sense … —Ruakh_TALK 08:04, 31 December 2006 (UTC)

Yes this was a response. There are a couple of things I might want to say, but first I just want to be sure we're clear on one point. I originally deleted the statement that "Conditional statements" were an instance of non-strict evaluation, but after further consideration and further reading I put that statement back. However in doing so I changed "statement" to "expression", which for me was a fundamental change. Statements are imperative constructions and as such the notion of non-strict evaluation doesn't apply. The essential purpose of a conditional expression is, like any expression, to return a value. Note that my research interest is functional programming where in principle the entire language does not have side effects. Pure functional langauges contain no statements, only expressions, and the expressions never have side-effects. So when you say "at least in a language where expressions can have side effects" I'm a little puzzled. I'm thinking we are not quite talking about the same thing. Abcarter_TALK13:27, 31 December 2006 (UTC)

In any real language, there exist expressions with side effects, since real languages need to communicate with the outside world; at least, I've never seen a language without some kind of print statement. Even in a functional language, it would be very confusing, and it would greatly limit the language's expressiveness, if the equivalent of ML's if true then print "foo" else print "bar" printed something other than simply foo.

For that matter, if you'll let me take a broader view, every evaluated expression has the side effect of taking time to evaluate; this is something we make a point of ignoring most of the time, but we'd have difficulty ignoring it in a language where the equivalent of ML's fun fact(x : int) : int = if x <= 1 then 1 else x * fact(x - 1) produced a function that never terminated, because its recursive call was always evaluated, even when not needed.

(I'm using ML for my examples because it's the functional language I know best; if you're not an ML-ian, though, let me know, and I can try to rewrite my examples in ANSI Common Lisp.)

—Ruakh_TALK 17:14, 31 December 2006 (UTC)

There is lots to talk about here, but we should keep the focus of this thread on the relation between non-strict evaluation and conditionals (if you want to post your remarks about languages and side-effects to my talk page I would be happy to respond). I changed "conditional statement" to "conditional expression" exactly because I wanted to restrict the notion to a construct that used conditionals in a way that were no different than other more standard sub-expressions, something as simple as "2+4". The essential purpose of such conditional constructions is to return a value. In some languages conditional expressions can have side-effects, in others they cannot. These kinds of conditional expressions usually use a kind of lazy evaluation that I think is pretty much the same as what you see in short-circuited evaluation of a Boolean expression. In contrast a conditional statement is all about having side-effects, that is its purpose. And here I am in agreement with you, it would be kinda weird to view conditional statements as something like short-circuited evaluation. Abcarter TALK 19:54, 31 December 2006 (UTC)

I don't see what you're responding to. I thought you were talking about my last edit, which had only to do with the purpose of the various non-strict evaluations, but now it doesn't seem like that's what you're talking about at all. —Ruakh_TALK 22:27, 31 December 2006 (UTC)

I was trying to be clear about what I meant by a conditional expression. I was emphasizing that conditional expressions are no different from any other kind of expression, it's essential purpose is to return a value. If you take this view then the reason you use lazy evaluatons for conditional expressions is pretty much the same reason you use short-circuit evaluation for a Boolean expression. In particular the process is no different than how you would evaluate the Boolean expression (P→Q) & (~P→R). If P is True then you only have to evaluate Q and if P is False then you only have to evaluate R. Abcarter Talk 01:05, 1 January 2007 (UTC)

O.K., sorry, I see what you're saying now. I still disagree, though; with ANDs and ORs there's a minor efficiency gain by using non-strict evaluation, and shortcutting is really just a perk that people can do without (and that people in some languages do do without), whereas with IF-THENs non-strict evaluation is absolutely essential in any language that supports recursion and/or side effects. Maybe we should just remove any mention of the reason being the same or different? —Ruakh_TALK 09:27, 1 January 2007 (UTC)

So now you mention recursion! That's an entirely different matter since the sole purpose of a recursive function is to return a value. And you're right, the non-strict evaluation is essential for a recursive expression to terminate properly. I don't see any need for an immediate change. As I said at the start I keep going around and around on this topic. Well we've beaten this horse to a pulp, but it was good talking with you. Abcarter Talk 01:41, 2 January 2007 (UTC)

Yeah, it's been an interesting conversation. :-) —Ruakh_TALK 02:56, 2 January 2007 (UTC)

[edit] Content seems to cover only function calls... what about expressions in general?

Perhaps I'm ignorant... but when I clicked the link to here from the Expression page, and read the first sentence ... An evaluation strategy (or reduction strategy) for a programming language is a set of (usually deterministic) rules for defining the evaluation of expressions under β-reduction. ... I thought I found the page I was looking for. But there's nothing about expression evaluation, in general. Does anyone else see the need for an explanation of evaluation strategy relating to operators, not just the various forms and issues of function calls? Maybe the research just has not been done yet. Comments? AgentFriday 02:46, 28 December 2006 (UTC)

Question, at the level that we are talking about is there a real difference between how a function is handled and how an operator is handled? Isn't a primitive operator simply a built-in function with perhaps a different syntax? Abcarter 17:38, 28 December 2006 (UTC)

Two answers :) 1: Perhaps a majority of the visitors to this page are not thinking at, or expecting, such an academic discussion on expression evaluation. I personally find the discussion interesting, but feel the page is lacking in coverage of infix notation, and strategies for resolving it. 2: Yes, every operation in an expression can be written as a function call, and in fact that is more obvious as to order of evaluation. However, given an expression in a standard programming language, you must still apply the rules of precedence and associativity first in order to know how to group the function calls. ... After some more searching, I found the page Common operator notation, which at least touches the surface of what I was expecting to find here. Perhaps it would be beneficial for this page to have a link there. It also may be that the link to here from Expression (and others) is inappropriate, or at least could use qualification. I'll trust that the title is appropriate for the content, but the first paragraph makes several references to expressions, which in the classical sense (and even in the context in which they are referenced) are infix notation. An evaluation strategy is also needed for this type of expression, but the article makes no reference to such or why it is not covered. Looking over the articles that link to this one, about 1/3 seem to be from pages mentioning expression evaluation (with no hint of the function-specific discussion ahead), about 1/3 are links from function-related topics (appropriate), and the rest seem to be miscellaneous "see also" links, etc. To me, there seems to be a disconnect. Anyway, thanks for reading. I thought some change was in order, but decided I was not qualified to jump in and make changes in this case. Hope you can see my point. AgentFriday 00:56, 29 December 2006 (UTC)

Surprisingly enough I think we're talking about two entirely different concepts. Just to confirm this I'm assuming that you are concerned with expressions like 2 + 5 * 3 and whether this evaluates to 2 + (5 * 3) = 17 or to (2 + 5) * 3 = 30. In particular you're concerned with rules or precedence. If so then my initial remark stands. Evaluation strategy as referred to in this entry is in fact a technical topic dealing with the semantics of a programming language. In this sense an expression is simply a syntactic construct that can be reduced to a data value. Don't get confused by the examples that happen to use infix notation. It's just easier and more clear to write 2 + 3 than add(2, 3), but at this level of discussion there is no conceptual difference, they're both just expressions. None of this is to say that you're concerns don't deserve it's own entry and it may well make sense to mark this distinction and provide a link. Abcarter 13:58, 29 December 2006 (UTC)