What is Classifier and Transformer in MIT Scheme?

Viewed 120

In the following scheme code, accumulate does right-fold. When I tried to run using mit scheme. I ran into following error:

Transformer may not be used as an expression: #[classifier-item 13]
Classifier may not be used as an expression: #[classifier-item 12]

I google searched but didn't find useful information. Is it related a macro?

; This function is copied from SICP chapter 2
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

; works as expected
(accumulate
   (lambda (x y) (or x y))  ; replace or with and also works
   #f
   '(#t #f #t #f #f)
))

; does not work
; error: Classifier may not be used as an expression: #[classifier-item 12]
(accumulate
   or
   #f
   '(#t #f #t #f #f)
))

; does not work
; error: Transformer may not be used as an expression: #[classifier-item 13]
(accumulate
   and
   #f
   '(#t #f #t #f #f)
))
2 Answers

Macros can be passed around in some languages, but not in Scheme and Common Lisp. The reason is that macros should be able to be expanded ahead of time. eg.

(define (cmp a b)
  (cond ((< a b) -1)
        ((> a b) 1)
        (else 0)))

Now a compiling Scheme will expand each node recursively replacing it with the expansion until it is no change:

(define (cmp a b)
  (if (< a b) 
      (begin -1)
      (cond ((> a b) 1)
            (else 0))))

(define (cmp a b)
  (if (< a b) 
      -1
      (cond ((> a b) 1)
            (else 0))))

(define (cmp a b)
  (if (< a b) 
      -1
      (if (> a b) 
          (begin 1)
          (cond (else 0)))))

(define (cmp a b)
  (if (< a b) 
      -1
      (if (> a b) 
          1
          (cond (else 0)))))

; end result
(define (cmp a b)
  (if (< a b) 
      -1
      (if (> a b) 
          1
          0)))

From this point of cond doesn't need to exist in the underlying language at all since you'll never ever use it, but how would this have to be implemented to work:

(define (test syntax a b)
  (syntax a b))

(test or #f #t)

For this to work the underlying language needs to know what or is even after expansion since syntax would need to be bound to or and then the transformation can happen. But when the code runs the macro expansion has already happened and in most implementations you would see something indicating that or is an unbound variable. It seems like MIT Scheme has added error checking for top level syntax syntax that will fire an error if you don't override it. Eg. if you add this you will not see any problems whatsoever:

(define (or a b) (if a a b)) (define (and a b) (if a b #f))

Now after those lines any reference to and and or are not the syntax, but these procedures. There are no reserved words in Scheme so if you do something crazy, like defining define you just cannot use it for the rest f that scope:

(define define display) ; defiens define as a top level variable
(define define)  ; prints the representation of the function display
(define test 10) ; fail since test is an undefined variable so it cannot be displayed. 

I created a interpreted lisp with macros that actually could be passed, but it isn't very useful and the chances of optimization is greatly reduced.

Yes it's related to the macros / special forms like and and or.

You can make it work simply by wrapping them as lambdas, (accumulate (lambda (a b) (or a b)) ...) -- the results will be correct but of course there won't be any short-circuiting then. The op is a function and functions receive their arguments already evaluated.

Either hide the arguments behind lambdas ((lambda () ...)) and evaluate them manually as needed, or define specific versions each for each macro op, like

(define (accumulate-or initial sequence)
  (if (null? sequence)
      initial
      (or (car sequence)
          (accumulate-or initial (cdr sequence)))))

Here sequence will still be evaluated in full before the call to accumulate-or, but at least the accumulate-or won't be working through it even after the result is already known.

If sequence contains some results of heavy computations which you want to avoid in case they aren't needed, look into using "lazy sequences" for that.

Related