Order of evaluation, SICP exercise

Question

So, I'm working my way through SICP. First exercise of Chapter 4 is:

Exercise 4.1. Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to cons in list-of-values are evaluated from left to right, then list-of-values will evaluate operands from left to right; and if the arguments to cons are evaluated from right to left, then list-of-values will evaluate operands from right to left. Write a version of list-of-values that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version oflist-of-values that evaluates operands from right to left.

The original function is

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))

and my solution would be the following:

;;; left-to-right
(define (list-of-values-l2r exps env)
  (if (no-operands? exps)
      '()
      (let ((first-exp (eval (first-operand exps) env)))
        (cons first-exp
              (list-of-values-l2r (rest-operands exps) env)))))

;;; right-to-left
(define (list-of-values-r2l exps env)
  (list-of-values-l2r (reverse exps) env))

However, I'm not sure if what I'm doing is correct. My intuition is that the let statement forces the eval, can anybody confirm?

I'm not sure it's possible to answer this question without specifying a particular standard, which seems to be the point of the original quotation. Your evaluation order is shackled to the semantics of the host language, and if the host language doesn't guarantee any notion of "sequence points" (which can be valid in, for example, a completely lazy language), then evaluation order will be hard to define. Of course, if you specify Scheme, it becomes feasible, though I don't remember exactly what each Scheme standard says about this off the top of my head. — Alexis King
you forgot the 2nd reverse in your list-of-values-r2l. But you could also code it specifically, directly, like ... (let ((rest-exps ... (btw it's list of values you're producing, so better name your vars like first-val, rest-vals, etc. ). — Will Ness

WorBlux WorBlux · Accepted Answer · 2015-12-17T00:39:08

let is just syntactic sugar, a rewrite without let would look like

(define (list-of-values-l2r exps env)
  (if (no-operands? exps)
      '()
      ((lambda (first-exp)
          (cons first-exp
                (list-of-values-l2r (rest-operands exps) env)))
        (eval (first-operand exps) env))))

Because scheme is eager in it's evaluation the (eval (first-operand exps) env) is always evaluated before the function is applied.

Order of evaluation, SICP exercise

1 Answers