Beautiful Scheme – Macros

Macros are not covered in SICP. I didn’t know how to use macro in scheme until  I read Peter Norvig’s JScheme code. Only then I started to understand why “symbol” and “quote” are important to scheme.

Scheme macros is similar to C macro, both transform some pattern into another. Scheme macros are more powerful because expansion/transformation happens at run time, and input/output patterns are structured scheme data that represents scheme code.

how is macro used?

Let’s look at an example. We know that let-expression can be replaced by equivalent lambda expression application.

(let ((x 1)(y 2)) (+ x y))
; is the same as 
((lambda (x y) (+ x y)) 1 2)

That transformation can be easily defined as a macro.

(define my-let 
          (macro (bindings . body)
                 (append (list (append 
                                (list 'lambda (map car bindings))
                         (map cadr bindings))))

What the code does, is basically transform input like (my-let ((x 1)(y 2)) (+ x y))into ((lambda (x y) (+ x y)) 1 2).

Macro is very similar to functions, except that it’s parameter is quoted code, and it returns quoted code as well.

When scheme interpreter sees an macro application, it will

  1. expand macro by applying macro body with parameter bound to quoted parameter expressions (without evaluating them).
  2. evaluate result of macro expansion.
why is macro important to scheme?

One thing I like about macro is it makes scheme interpreter/compiler much easier to implement.

To write a scheme interpreter, you only need to implement very few core features (begin, define, lambda/macro, function call, quote, if expression, built-in functions). The rest of the language like let, cond, and, or can all be implemented in macros. JScheme source code uses this approach, and its source code contains a file that defines all these language features with macros. These definitions are reusable when writing scheme interpreter/compiler in the future.

It is amazing that that adding a language feature can make the language easier to implement.

What is quasiquotes, unquote and unquote-splicing?

Quasiquote is the same as quote except that you can “unquote” part of the expression.

(quote (1 (+ 2 3)))                
; usually written as '(1 (+ 2 3))
; => (1 (+ 2 3))

(quasiquote (1 (unquote (+ 2 3)))) 
; usually written as `(1 ,(+ 2 3))
; => (1 5)

Unquoted code is evaluated instead of being treated as data.

The best way to explain unquote-splicing is by example.

(quasiquote (1 (unquote-splicing (append (list 2) (list 3))) 4 ))
; usually written as `(1 ,@(append (list 2) (list 3)) 4)
; => (1 2 3 4)

; Compare to unquote
`(1 ,(append (list 2) (list 3)) 4)
; => (1 (2 3) 4)

These are utilities that make macro much easier to write.

“my-let” above can be written as

(define my-let 
          (macro (bindings . body)
                 `((lambda ,(map car bindings) . ,body)
                   ,@(map cadr bindings))))

It might be brain twisting when looking at these for the first time, but it will start to make more sense when started writing more macros.

Surprisingly, quasiquote, unquote, unquote-splicing can be implemented with macros. Following implementation is written by Darius Bacon, and I copied it from JScheme code.

(define quasiquote 
  (macro (x) 
    (define (constant? exp)
      (if (pair? exp) (eq? (car exp) 'quote) (not (symbol? exp))))
    (define (combine-skeletons left right exp)
       ((and (constant? left) (constant? right)) 
  (if (and (eqv? (eval left) (car exp))
     (eqv? (eval right) (cdr exp)))
      (list 'quote exp)
      (list 'quote (cons (eval left) (eval right)))))
       ((null? right) (list 'list left))
       ((and (pair? right) (eq? (car right) 'list))
  (cons 'list (cons left (cdr right))))
       (else (list 'cons left right))))
    (define (expand-quasiquote exp nesting)
       ((vector? exp)
  (list 'apply 'vector (expand-quasiquote (vector->list exp) nesting)))
       ((not (pair? exp)) 
  (if (constant? exp) exp (list 'quote exp)))
       ((and (eq? (car exp) 'unquote) (= (length exp) 2))
  (if (= nesting 0)
      (second exp)
      (combine-skeletons ''unquote 
             (expand-quasiquote (cdr exp) (- nesting 1))
       ((and (eq? (car exp) 'quasiquote) (= (length exp) 2))
  (combine-skeletons ''quasiquote 
         (expand-quasiquote (cdr exp) (+ nesting 1))
       ((and (pair? (car exp))
       (eq? (caar exp) 'unquote-splicing)
       (= (length (car exp)) 2))
  (if (= nesting 0)
      (list 'append (second (first exp))
      (expand-quasiquote (cdr exp) nesting))
      (combine-skeletons (expand-quasiquote (car exp) (- nesting 1))
             (expand-quasiquote (cdr exp) nesting)
       (else (combine-skeletons (expand-quasiquote (car exp) nesting)
        (expand-quasiquote (cdr exp) nesting)
    (expand-quasiquote x 0)))

To be honest I still don’t full understand the code, but I did some tests and was convinced it works.

What is hygiene macro?

Macros are powerful, but there is an issue when used in practice. Consider following example

(define plus-one
          (macro (x)
                 `(let ((one 1))
                    (+ ,x one))))

(plus-one (begin (set! one 2) 1))
; (let ((one 1)) (+ (begin (set! one 2) 1) one))

User code might modify variables defined in macro body and cause unexpected behavior. Hygiene macro addresses this problem by replacing variables defined in macro body with unique identifiers dynamically so that user don’t have to worry about naming collision.

R5RS scheme has syntax-rules syntax which supports hygiene macro and pattern matching features. There are many resources on web about syntax-rule like this, and I still don’t understand it’s pattern matching mechanism well. But surprisingly again, syntax-rules can be implemented with regular macro as well! I found this implementation in JScheme home page.

What else can macro do?

It is possible to extend scheme language feature with macro.

One example is stream (infinite length list) processing. Scheme does not  natively support stream processing, but it is easy to add steaming support using macro.

(define stream-cons (macro (a b) `(cons ,a (lambda () ,b))))
(define stream-car car)
(define stream-cdr (lambda (s) ((cdr s))))
(define stream-null? null?)

Here is a program that creates infinite stream of prime numbers using Sieve of Eratosthenes.

(define (stream-map f s)
  (if (stream-null? s)
      (stream-cons (f (stream-car s)) (stream-map f (stream-cdr s)))))

(define (stream-filter f s)
    ((stream-null? s) '())
    ((f (stream-car s)) (stream-cons (stream-car s) (stream-filter f (stream-cdr s))))
    (else (stream-filter f (stream-cdr s)))))

(define ones (stream-cons 1 ones))

(define ints (stream-cons 1 (stream-map (lambda (x) (+ x 1)) ints)))

(define evens (stream-filter (lambda (x) (= 0 (modulo x 2))) ints))

(define (sieve s)
  (let ((fst (stream-car s)))
    (stream-cons fst
                 (sieve (stream-filter (lambda (x) (not (= 0 (modulo x fst)))) (stream-cdr s))))))

(define prime (sieve (stream-cdr ints)))

Macro is such a simple yet powerful feature that makes scheme a beautiful languages. I am still learning and being surprised by what macro can do.






Beautiful Scheme – quote

Scheme is a beautiful language.

— prof Ben Leong

Recently I read some Scheme articles and I find myself start appreciating more about its beauty. I am going to start a series of posts to share my thoughts and problems I had in learning.

Code is data

Any technology sufficiently advanced is indistinguishable from magic.

— Arthur C. Clarke

Programming language interpreter is magic to beginners.

However, writing a scheme interpreter in scheme is surprisingly simple. There are many reasons, but the most important one is probably the fact that scheme code can be naturally represented in scheme list.

The boundary between code and data has been blurring since Von Neumann architecture, and many programming languages like Javascript supports evaluating code in string format at runtime. Scheme went one step further. Any scheme code can be converted to scheme data value with “quote” function.

“quote” function is something that confused me a lot when I learnt scheme. I listed some questions I had and my answers below.

why it is called “quote”?

Think about how you use javascript eval(). You write some JS code, quote them into a string and call eval on the string. It is the same for scheme, except that quoted scheme code is structured data, which is much easier to process.

what does “quote” exactly do?

Converts scheme code into data.

code data
‘123 [integer] 123
‘#t [boolean] #t
‘”hello” [string] “hello”
‘define [symbol] define
‘(1 (2 3)) [list] ([integer] 1, [list]([integer] 2, [integer] 3))
”(1 2) [list] ([symbol] quote, [list]([integer] 1, [integer] 2))

''(1 2) is actually (quote (quote (1 2))), which converts (quote (1 2))into data.

Unlike “” in javascript, you don’t need to escape “quote” inside your code because there is no ambiguity.

why does scheme need “quote”?

Scheme without “quote” is still Turing complete. I think the main reason for introducing “quote” is macros, which makes scheme flexible and extensible.

why do we need symbol?

Symbol seems to be the same as interned string. However, we cannot replace symbol with string because '"define"  and 'define will be not distinguishable.

To make 'define meaningful, a new first class type has to be introduced, and that is symbol. Note that introducing symbol data type does not add any syntax to scheme. 'define is just syntactical sugar for (quote define).

This may sounds hacky, but it worth it because it gives scheme the power to process code in the same way it process lists. We will see more about this in another post about macros.