From: James Kang
Subject: Normal Order Evaluation Vs.Applicative Order Evaluation?
Date:
Message-ID: <36D2B0D5.114014E7@hotmail.com>
Hello everyone,
I'm having trouble understanding the differences between Normal order
and Applicative order evaluation. Could anyone please explain the
difference to me? I tried to evaluate this expression in order to test
out applicative order evaluation:
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
then i try evaluating the expression with (test 0 (p)). However, after
doing this, nothing happened. I am told that my interpreter uses
applicative order evaluation. I am also wondering what would happen if
normal ordered evaluation was used in this case?
Thanks in advance.
-James
From: cdm
Subject: Re: Normal Order Evaluation Vs.Applicative Order Evaluation?
Date:
Message-ID: <7av5mj$ke6$1@remarQ.com>
James Kang <·····@hotmail.com> wrote in message
······················@hotmail.com...
>Hello everyone,
> I'm having trouble understanding the differences between Normal order
>and Applicative order evaluation. Could anyone please explain the
>difference to me? I tried to evaluate this expression in order to test
>out applicative order evaluation:
>
>(define (p) (p))
>(define (test x y)
>(if (= x 0) 0 y))
>
>then i try evaluating the expression with (test 0 (p)). However, after
>doing this, nothing happened. I am told that my interpreter uses
>applicative order evaluation. I am also wondering what would happen if
>normal ordered evaluation was used in this case?
An applicative order interpreter would get stuck in an infinite loop
(recursively calling p). A normal order interpreter would return 0.
Informally, an applicative order interpreter evaluates all the arguments
before calling the function, a normal order interpreter only evaluates
arguments when it needs to. The result of calling (p) isn't needed by
test (when x is zero), so the normal order interpreter doesn't bother.
It is the case that if a
result is returned using applicative order, it will be the same as
if normal order were used (if side effects are left out of the picture).
It is generally believed that applicative order is easier to implement
and performs better (some might disagree), so applicative order is
more common than normal order since for any problem that terminates
they give the same answer.
~jrm
>
>Thanks in advance.
>
>-James
From: Felix Schroeter
Subject: Re: Normal Order Evaluation Vs.Applicative Order Evaluation?
Date:
Message-ID: <7auhun$3v9$1@c3po.schlund.de>
Hello!
In article <·················@hotmail.com>,
James Kang <·····@hotmail.com> wrote:
>[...]
>(define (p) (p))
>(define (test x y)
>(if (= x 0) 0 y))
>then i try evaluating the expression with (test 0 (p)). However, after
>doing this, nothing happened. I am told that my interpreter uses
>applicative order evaluation. I am also wondering what would happen if
>normal ordered evaluation was used in this case?
AOR: as long as there is a redex (reducable (sub)expression) in the
expression to be evaluated, reduce the leftmost innermost redex.
NOR: as long as there is a redex (reducable (sub)expression) in the
expression to be evaluated, reduce the leftmost outermost redex.
So:
AOR:
(test 0 (p)) -- redexes: (test 0 (p)) and (p)
^^^ (leftmost innermost)
per definition: (p) => (p)
(test 0 (p)) -- and so on, you have programmed an endless loop
NOR:
(test 0 (p)) -- redexes as above, but the whole expr is the leftmost
-- outermost redex, so that is reduced
from the definition:
(test x y) => (if (= x 0) 0 y))
apply definition
(if (= 0 0) 0 (p)) -- see: (p) isn't evaluated, but just copied to
-- the appearances of the formal argument 'y' in the
-- definition!
Now, the outermost expression is an application of the primitive "if",
which is strict in its first argument (i.e. needs the first argument
evaluated), so the evaluation continues
(= 0 0) => (primitive "=") #T
(if #T 0 (p)) -- now, the rule is (if #T x y) => x
0
Hope that helps.
Regards,
Felix.