CODEWITHSUNDEEP
schemelisp
babon
babon

Reputation: 3774

Scheme expression evaluation

I am going through the book - The Scheme Programming Language, 4th Edition. In an exercise, there is an expression ((car (list + - * /)) 2 3). Below are the steps in which I believe the expression will be evaluated. Please let me know if my understanding is correct.

  1. The expression (list + - * /) is evaluated to a list of procedures: (+ - * /). (I understand that list always produces a "proper list", could someone please state a few differences between using list and cons?)
  2. The expression (car (+ - * /)) is evaluated to the symbol + which evaluates to a procedure. (I don't really understand how (car (+ - * /)) is evaluated, typing (car (+ - * /)) at the REPL prompt produces an error).
  3. The expression (+ 2 3) is evaluated to 5.

I would like if I could get some other / in depth explanation.

Upvotes: 2

Views: 875

Answers (2)

soegaard
soegaard

Reputation: 31147

The stepper in DrRacket is the perfect tool for exploring evaluation order. The stepper allows you to see the effect of one evaluation step at a time. You can even step backwards.

enter image description here

The stepper however only works in the Beginner and Intermediate languages. The image is from the following program using the Intermediate language.

(car (list + - * /))
(+ 2 3)

Upvotes: 1

Sylwester
Sylwester

Reputation: 48745

  1. Yes! However the procedures doesn't have literal representation so when you evaluate + you get some crazy textual representation like #<primitive-procedure-+> and copying it and pasting it into the repl won't give you the same object back. The same with lists. When you evaluate (list 1 2 3) you get (1 2 3) but you cannot just write (1 2 3) since it will think it should call 1 as a procedure with two arguments. (list 1 2 3) makes (cons 1 (cons 2 (cons 3 '()))) a chain of nested pairs. That the last cdr is () is what makes it proper. Thus the primitive that allows list to do it's thing is cons.

  2. Wrong. You have an evaluated expression (list + - * /) to something like (#<primitive-procedure-+> #<...> #<...> #<...>). A list of evaluated variables and you now see their visual representations. Doing car on it gives you the first object #<primitive-procedure-+> which is the same you get when you evaluate the global variable +. There are no symbols involved in this step. The previous step didn't involve symbols either since bare symbols are variables. 'test becomes a symbol while test becomes whatever the variable pointed to. All procedures by name are just variables getting evaluated before application. It's the default behaviour in Scheme.

  3. Since the object is the same as the value + is it will add the rest of the operands together after they have been evaluated. Since they all are numbers the arguments passed to apply stay the same, but if you have expressions there like (+ (* 3 3) (* 4 4)) then the operands like (* 3 3) need to get evaluated and it's result is what is applied.

You can apply substitution rules. It's not what the Scheme interpreter does, but any variable can be replaced by the value it has and every expression can be replaced by its result as long as you do not mutate anything:

((car (list + - * /)) (- 5 2) (/ 4 2)) ; == (car (list + - * /)) evaluates to the same value as the variable +
(+ (- 5 2) (/ 4 2)) ; == (- 5 2) evaluates to 3, (/4 2) evaluates to  2
(+ 3 2)             ; == (+ 3 2) evaluates to 5
; ==> 5 (the result)

Notice I substitute (car (list + - * /)) with the variable + and not a symbol. They both are the same: (eq? (car (list + - * /)) +) ; ==> #t

Upvotes: 3

Related Questions