order of evaluation?

Given the expression (foo (bar 3) baz (bing 8)), what is the order
of evaluation? I can see some interpreters that will parse the tree
to the lowest element/atom, start puting the values on some stack,
and work backwards:

8 <-
-> bing
baz <-
3 <-
-> foo

I can also see this expression:

(if (= foo 1) (bar 3) (baz 4))

that is is more efficient to evalute the '(=', then evaluate the
'(if', and let the if evaluate the selected expression.

Which way is it done?

Mike

Mike wrote:
> Given the expression (foo (bar 3) baz (bing 8)), what is the order
> of evaluation? I can see some interpreters that will parse the tree
> to the lowest element/atom, start puting the values on some stack,
> and work backwards:
>
> 8 <-
> -> bing
> baz <-
> 3 <-
> -> foo
>
> I can also see this expression:
>
> (if (= foo 1) (bar 3) (baz 4))
>
> that is is more efficient to evalute the '(=', then evaluate the
> '(if', and let the if evaluate the selected expression.
>
> Which way is it done?

There are a few related questions implicit above...

> (foo (bar 3) baz (bing 8))

Scheme calls ordinary functions using a call-by-value approach, in which all
a function's arguments are evaluated before a function is ever called, so if
foo is an ordinary function (as opposed to e.g. a macro), you know that (bar
3), baz, and (bing 8) will all be evaluated before foo is called.

However, the order in which these arguments are evaluated happens is not
specified in R5RS, and varies between Scheme implementations.  Some do it
left to right, some do it right to left, and other orders are possible.  A
parallel implementation of Scheme might even evaluate the arguments
concurrently.  This means that if you want to write Scheme code that's at
all portable, you should avoid depending on order of evalutation within
ordinary expressions.  If you need to specify an order of evaluation, you
should use an appropriate form such as LET* or BEGIN, which sequences its
contents.

> (if (= foo 1) (bar 3) (baz 4))
>
> that is is more efficient to evalute the '(=', then evaluate the
> '(if', and let the if evaluate the selected expression.

The IF construct in Scheme is not an ordinary function.  In a call-by-value
language like Scheme, using an ordinary function for IF would mean that both
its branches would have to be evaluated, even though the result of only one
is used.  Aside from performance issues, this could cause problems if the
unneeded branch has side effects.  To address this, IF is built-in syntax in
Scheme, and it works as you say: the condition is evaluated first, and then
either the consequent or the antecedent is evaluated, depending on the
result of the condition.

In general, if you need to define operations in Scheme which don't use call
by value, you can do it by defining a macro.  IF behaves like a macro,
although whether it's actually implemented as one depends on the Scheme
implementation.  (It's possible to implement IF as a macro in terms of COND,
or vice versa, but usually one or the other, or some other means of making a
choice, is needed at a primitive level.)

Anton

In article <Zi_6d.5610$ls6.1752@newsread3.news.atl.earthlink.net>, Anton van Straaten wrote
:
> Mike wrote: 
>
> There are a few related questions implicit above...
> 
>
> Scheme calls ordinary functions using a call-by-value approach, in which a
ll
> a function's arguments are evaluated before a function is ever called, so 
if
> foo is an ordinary function (as opposed to e.g. a macro), you know that (b
ar
> 3), baz, and (bing 8) will all be evaluated before foo is called.
>
> However, the order in which these arguments are evaluated happens is not
> specified in R5RS, and varies between Scheme implementations.  Some do it
> left to right, some do it right to left, and other orders are possible.  A
> parallel implementation of Scheme might even evaluate the arguments
> concurrently.  This means that if you want to write Scheme code that's at
> all portable, you should avoid depending on order of evalutation within
> ordinary expressions.  If you need to specify an order of evaluation, you
> should use an appropriate form such as LET* or BEGIN, which sequences its
> contents.
> 
>
> The IF construct in Scheme is not an ordinary function.  In a call-by-valu
e
> language like Scheme, using an ordinary function for IF would mean that bo
th
> its branches would have to be evaluated, even though the result of only on
e
> is used.  Aside from performance issues, this could cause problems if the
> unneeded branch has side effects.  To address this, IF is built-in syntax 
in
> Scheme, and it works as you say: the condition is evaluated first, and the
n
> either the consequent or the antecedent is evaluated, depending on the
> result of the condition.
>
> In general, if you need to define operations in Scheme which don't use cal
l
> by value, you can do it by defining a macro.  IF behaves like a macro,
> although whether it's actually implemented as one depends on the Scheme
> implementation.  (It's possible to implement IF as a macro in terms of CON
D,
> or vice versa, but usually one or the other, or some other means of making
 a
> choice, is needed at a primitive level.)
>
> Anton
>
>

Wonderful explanation and just what I was asking for.

Mike

Is there any utility to the order of evaluation being unspecified?
Is it :
a) that a fixed order would produce some unwanted theoretical effect?
b) to discourage some programming methods?
c) because the choice of the order of evaluation would be arbitrary?
d) because no consensus have been reached regarding this issue?
e) something else?

I'm no scheme expert, far from it, but I use it everyday, and I
wondered : is this ambiguity responsible for the only circumstances
where one can look at valid R5RS scheme code, and not be able to
predict the result of the evaluation ?

Thanks, M.P.

mathieu.paradis@logik3d.com (M. Paradis) writes:

> Is there any utility to the order of evaluation being unspecified?
> Is it :
>  a) that a fixed order would produce some unwanted theoretical effect?
>  b) to discourage some programming methods?
>  c) because the choice of the order of evaluation would be arbitrary?
>  d) because no consensus have been reached regarding this issue?
>  e) something else?
>
> I'm no scheme expert, far from it, but I use it everyday, and I
> wondered : is this ambiguity responsible for the only circumstances
> where one can look at valid R5RS scheme code, and not be able to
> predict the result of the evaluation ?

I think the point is that you are supposed to write code that does not
depend on any one order of evaluation, so your code will always
execute the same no matter what Scheme you're using.

This is quite a common requirement in high level languages, or at
least it used to be. Others that follow this are:

C, BCPL, Ada and Pascal I seem to remember

Maybe this is Algol's fault.


AFAIK the reason for this is that it frees compiler implementors to
pursue different compilation strategys. For example, with Scheme it
can be quite efficient to evaluate function call arguments from right
to left (ie: backwards to the way westerners read code).

Having said that, IMHO the time for such efficiencies is past and
Scheme should be speced as evaling from left to right.

One of the practical things that makes Java popular is that the order
of eval is speced left to right. It does make it simpler for the
programmer.


--
Nic Ferrier
http://www.tapsellferrier.co.uk

M. Paradis wrote:
> Is there any utility to the order of evaluation being unspecified?
> Is it :
>  a) that a fixed order would produce some unwanted theoretical effect?
>  b) to discourage some programming methods?
>  c) because the choice of the order of evaluation would be arbitrary?
>  d) because no consensus have been reached regarding this issue?
>  e) something else?

I think it's mostly (d), because there were right-to-left
and left-to-right schemes when that spec was first written,
and still are.  But it stays in the standard too, because

f) by choosing an arbitrary order of evaluation, a compiler
can often find optimizations that cut as much as 10% off the
time required to evaluate an expression.

Bear

Ray Dillinger wrote:

{stuff deleted}

still are.  But it stays in the standard too, because
>
> f) by choosing an arbitrary order of evaluation, a compiler
> can often find optimizations that cut as much as 10% off the
> time required to evaluate an expression.

Citation? I strongly suspect this really is no longer the case on modern
out-of order RISC machines with lots of registers.

Daniel C. Wang wrote:
> Ray Dillinger wrote:
>
> {stuff deleted}
>
> still are.  But it stays in the standard too, because
> 
>
>
> Citation? I strongly suspect this really is no longer the case on modern
> out-of order RISC machines with lots of registers.
>
>
Ack, I sense a repeated flame fest beginning.  Please read the thread
starting at:

[url]http://groups.google.com/groups?selm=br0fjn%245bl%245%40hood.uits.indiana.edu[/url
]

... before beginning.

Scott

* Nic Ferrier (nferrier@tapsellferrier.co.uk)
...
[Argument evaluation order]
>
> This is quite a common requirement in high level languages, or at
> least it used to be. Others that follow this are:
>
> C, BCPL, Ada and Pascal I seem to remember
>
Actually C does not even require the arguments to be evaluated
one at a time. In (the C equivalent of)

(e (d (a)) (c (b)))

the functions may be invoked in alphabetical order. Is that
allowed in Scheme, too?

Andreas

--
np: 4'33

mathieu.paradis@logik3d.com (M. Paradis) writes:

> Is there any utility to the order of evaluation being unspecified?
> Is it :
>  a) that a fixed order would produce some unwanted theoretical effect?

Depends on what you want.  (The answer is "yes" if, e.g., you don't
like unambiguous semantics.)

In any case, as I have said many times before: Every program that is
legal and correct under unspecified evaluation order is obviously
legal and correct under a specified order.  The opposite is not true,
and it is difficult to establish trough testing which programs are the
ones that make up the difference.  (That's because most
implementations actually do implement some fixed order, so it is
difficult to test other legal schedules which your compiler happens to
not use.)

>  b) to discourage some programming methods?

Supposedly, according to some.  I don't believe it one second, though.
(I'm NOT going to again about this again!  Bradd, did you hear me?)

>  c) because the choice of the order of evaluation would be arbitrary?

Many other things are "arbitrary", too.

>  d) because no consensus have been reached regarding this issue?

That's definitely a large part of the story.

>  e) something else?

Some compilers can squeeze out some extra performance from some
programs.

> I'm no scheme expert, far from it, but I use it everyday, and I
> wondered : is this ambiguity responsible for the only circumstances
> where one can look at valid R5RS scheme code, and not be able to
> predict the result of the evaluation ?

Note quite, but arguably it is the most serious reason.

Matthias