Returning functions in scheme

Question

I have been playing about with The Little Schemer, and am trying ideas as i work through (not all of which are working out). Just now, i am in Chapter 6 (where they introduce helper functions) and i feel that a step is within reach -- i just don't know how to make that step.

The code from the book is as follows:

(define (^ b e) (expt b e))

(define (x a b) (* a b))

(define value-i
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (car (cdr nexp)) '+) (+ (car nexp) (value-i (caddr nexp))))
      ((eq? (car (cdr nexp)) 'x) (x (car nexp) (value-i (caddr nexp))))
      (else
        (^ (car nexp) (value-i (caddr nexp))))
      )))

The following helpers are defined:

(define (operator-i aexp) (car (cdr aexp)))
(define (firstSubExp-i aexp) (car aexp))
(define (secondSubExp aexp) (caddr aexp))

And this simplification is made:

(define value-i2
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      ((eq? (operator-i nexp) '+) (+ (firstSubExp-i nexp) 
                                     (value-i2 (secondSubExp nexp))))
      ((eq? (operator-i nexp) 'x) (x (firstSubExp-i nexp) 
                                     (value-i2 (secondSubExp nexp))))
      (else
        (eq? (operator-i nexp) '^) (^ (firstSubExp-i nexp) 
                                      (value-i2 (secondSubExp nexp))))
      )))

The simplification i think i can see is that as we assume all nexp are valid, we don't need to repeat the ((eq? (operator-i nexp) ... boilerplate.

Something like the following should work:

(define value-i3
  (lambda (nexp)
    (cond
      ((atom? nexp) nexp)
      (else
        ((operator-i nexp) 
         (firstSubExp-i nexp) 
         (value-i3 (secondSubExp nexp))))
      )))

... except that it does not. It errors out with Exception: attempt to apply non-procedure ... (one of +, x and ^).

I can see that the problem is that it does not recognise that i am trying to call a function with (operator-i nexp).

How do i make clear to the interpreter that i wish to apply the function i am returning from (operator-i nexp)?

Any other tips are also welcome (i am using petite chez scheme).

Answer 1

Unfortunately, value-i3 doesn't work because (operator-i nexp) returns a symbol, not a procedure object. Notice the difference between '+ and +?

There's not really an easy way to get around that (if we rule out eval, which is gross and disrecommended), other than using an alist to link the symbol with the procedure (or using case or cond as mentioned in Sylwester's answer):

(define symbol->procedure
  (let ((opmap `((+ ,+)
                 (x ,x)
                 (^ ,^))))
    (lambda (x)
      (cond ((assq x opmap) => cadr)
            (else #f)))))

Then use symbol->procedure the same way as Sylwester's answer.

If you find quasiquotes too difficult to read, you can use list and cons directly;

(define symbol->procedure
  (let ((opmap (list (cons '+ +)
                     (cons 'x x)
                     (cons '^ ^))))
    (lambda (x)
      (cond ((assq x opmap) => cdr)
            (else #f)))))

---

The OP asked for more information about assq and the like, so I thought I'd update the post directly. Basically, (assoc key alist) returns the first item in alist whose car is equal? to key, or #f otherwise; assq and assv are similar to assoc but use eq? and eqv? as the comparison operator. So, here's a sample implementation (with R7RS/SRFI-1 semantics):

(define (find pred lst)
  (cond ((null? lst) #f)
        ((pred (car lst)) (car lst))
        (else (find pred (cdr lst)))))

(define assoc
  (case-lambda
    ((key alist equal?)
     (find (lambda (x)
             (equal? key (car x)))
           alist))
    ((key alist)
     (assoc key alist equal?))))

(define (assq key alist)
  (assoc key alist eq?))

(define (assv key alist)
  (assoc key alist eqv?))

Answer 2

The problem with you assumnption is that operator-i returns a symbol. When you do (+ 1 2) the + gets evaluated to a procedure and that makes the form callable. However in the operator position in your code the result is the symbol '+. It then tries to apply a symbol instead of a procedure. Here is the minimal example of the two:

('+ 1 2) ; won't work
(+ 1 2)  ; works

You can make a lookup between them of course:

(define (symbol->procedure sym)
  (case sym
    ((+) +)
    ((x) x)
    ((^) ^)
    (else #f)))

((symbol->procedure '+) 2 3) ; ==> 5