Skip to main content
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link

Notice that the first quote contains a definition of normal-order evaluation, but the second one treats normal-order languages, i.e. languages that use normal-order evaluation.

The nice answernice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

Notice that the first quote contains a definition of normal-order evaluation, but the second one treats normal-order languages, i.e. languages that use normal-order evaluation.

The nice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

Notice that the first quote contains a definition of normal-order evaluation, but the second one treats normal-order languages, i.e. languages that use normal-order evaluation.

The nice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

fixed the answer, since the prev. version is based on misreading the question
Source Link
Anton Trunov
  • 3.5k
  • 1
  • 19
  • 26

The definitions do not contradictNotice that the first quote contains a definition of normal-order evaluation, but they are not equivalent. In fact, the second definition holds when the first is trueone treats normal-order languages, i. If you "fully expand"e. languages that use normal-order evaluation.

The nice answer by @Gilles explains in detail the input application, then you are definitely not going to evaluatedifference between the arguments immediatelyapplicative-order and normal-order evaluations, only whenand shows that normal-order evaluation delays evaluation of arguments until they are needed.

But deferringI also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the first definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

I guess the authors gave the first simplified definition with a didactic purpose in mind, since they were talking about the substitution model.

The definitions do not contradict, but they are not equivalent. In fact, the second definition holds when the first is true. If you "fully expand" the input application, then you are definitely not going to evaluate the arguments immediately, only when they are needed.

But deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the first definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

I guess the authors gave the first simplified definition with a didactic purpose in mind, since they were talking about the substitution model.

Notice that the first quote contains a definition of normal-order evaluation, but the second one treats normal-order languages, i.e. languages that use normal-order evaluation.

The nice answer by @Gilles explains in detail the difference between the applicative-order and normal-order evaluations, and shows that normal-order evaluation delays evaluation of arguments until they are needed.

I also want to note that normal-order evaluation is not the only way of delaying arguments' evaluation, as the book also mentions as lazy evaluation.

Deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary lazy interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

Post Undeleted by Anton Trunov
Post Deleted by Anton Trunov
Source Link
Anton Trunov
  • 3.5k
  • 1
  • 19
  • 26

The definitions do not contradict, but they are not equivalent. In fact, the second definition holds when the first is true. If you "fully expand" the input application, then you are definitely not going to evaluate the arguments immediately, only when they are needed.

But deferring evaluation of the arguments doesn't necessarily mean one has to "fully expand", since one can use a kind of memoization to avoid repeating evaluations (in case of programming without side effects).

Let's repeat the example just above the first definition for the normal-order evaluation. First the "fully expand" version:

(sum-of-squares (+ 5 1) (* 5 2))    
(+    (square (+ 5 1))      (square (* 5 2))   )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

In this case the interpreter has to evaluate (+ 5 1) and (* 5 2) twice.

Instead we can remember the expressions (+ 5 1) and (* 5 2) as thunks e1 = (lambda () (+ 5 1)) and e2 = (lambda () (* 5 2)). Please bear in mind that I'm relying on the built-in facilities (of our imaginary interpreter) to save the results of (e1) and (e2), after they evaluated the very first time to avoid recalculations. It's a nice exercise to actually realize that kind of behavior in plain Scheme.

(sum-of-squares (e1) (e2))
(+    (square (e1)    (square e2)  )
(+    (* (e1) (e1))   (* (e2) (e2)))

In this last expression the built-in memoization mechanism will evaluate (e1), remember its result (which is 6), so the second (e1) invocation won't redo the computation and will immediately return 6. The part with (e2) is handled in the same way. So the amount of operations is roughly the same as under applicative-order evaluation.

I guess the authors gave the first simplified definition with a didactic purpose in mind, since they were talking about the substitution model.