Scheme-1

You've just taken your first step into a larger world.
- Obi-Wan Kenobi, Star Wars: A New Hope

Scheme-1 is a big step beyond the CALC program: it's our first example of a universal program, one that can in theory perform the same computation as any other program. You certainly wouldn't want to actually write something in Scheme-1 (no define, for one thing!), but it's pretty cool that we've been able to recreate a lot of Scheme's functionality using only a few pages of Scheme code.

Let's test your understanding of Scheme-1:

• What are the domain and range of eval-1? Of apply-1? And what will STk print for the following expressions?

  STk> (define x 'y)
  STk> (define y 'z)
  STk> (eval-1 x)
  
  _______
  
  STk> (eval-1 'x)
  
  _______
  
  STk> (eval-1 ''x)
  
  _______

  (show answer)

  eval-1 is pretty easy: it just takes a Scheme-1 expression and returns a Scheme-1 value. There are some things to watch out for, though: take a look at the examples to see why.

  Calling eval-1 directly	What eval-1 sees	Equivalent Scheme-1 input	Result
  (eval-1 x)	y	Scheme-1: y	z
  (eval-1 'x)	x	Scheme-1: x	y
  (eval-1 ''x)	(quote x)	Scheme-1: 'x	x

  How about apply-1? It takes two arguments, the first of which is a procedure (not the name of a procedure), and the second of which is a list of argument values (not expressions!). This is important! It means the code for apply-1 doesn't have to know anything about the syntax of Scheme-1. It just puts the arguments into the procedure, then evaluates the procedure body using eval-1. So the range is also Scheme-1 values

  Common mistakes in calling apply-1:

  ; Uses name of procedure instead of procedure itself.
  ; (apply-1 '+ '(2 3))
  
  ; Uses expressions instead of values.
  ; (apply-1 + '(2 (+ 1 2)))
  
  ; Good!
  > (apply-1 + '(2 3))
  5
  
  ; Using a lambda (note the quote)
  > (apply-1 (eval-1 '(lambda (x y) (+ x y))) '(2 3))
  5

  (hide answer)

• Does Scheme-1 use applicative or normal order for regular procedure calls?

  (show answer)

  We know STk uses applicative order, but there's no rule that says Scheme-1 has to be applicative too! The best way to answer this question is to look at the call to apply-1:

  (apply-1 (eval-1 (car exp))
           (map eval-1 (cdr exp)) )

  So, we're mapping eval-1 over the arguments before actually calling apply-1. That means Scheme-1 is using applicative order.

  (hide answer)

• Where are special forms handled: the REPL, eval-1, or apply-1?

  (show answer)

  Well, it can't be apply-1, because we said the call to apply-1 shows that Scheme-1 uses applicative order, and certain special forms like IF can't use applicative order. (There was a lab exercise on this.)

  It also really shouldn't be the REPL, whose entire job is supposed to be just reading, calling EVAL(-1), and printing the result, over and over.

  That leaves eval-1, and of course you remember the big COND in eval-1. Some of the clauses had conditions like (if-exp? exp) or (quote-exp? exp). This must be where special forms are handled! You've had both a lab exercise and a homework problem on adding special forms, so this shouldn't have been a hard question.

  (hide answer)

• What is substitute for? How is it different than the substitute you wrote for homework?

  (show answer)

  substitute is used by apply-1 to substitute argument values into a procedure body before it is evaluated. For the most part it's just like your homework substitute, but it has to be able to handle nested lambdas, like this:

  ((lambda (x)
     ((lambda (x) (* x x))
      (+ 1 x) ))
   3)

  Scheme-1's substitute does have an extra parameter bound, which is a list of variables not to substitute, because they're part of a nested lambda. That's the basic idea, anyway.

  There's a big comment explaining substitute in more detail, but don't worry about it too much—in two weeks or so you'll find out that even though this is how Scheme-1 does things, it's not how real Scheme works. Stay tuned for the true story!

  (hide answer)

Back to Jordy's home page | Course home page