From posting-system@google.com Mon Dec 29 00:05:48 2003
Date: Sun, 28 Dec 2003 16:05:43 -0800
From: oleg@pobox.com (oleg@pobox.com)
Newsgroups: comp.lang.scheme
X-Comment: added comments by Joe Marshall and Matthias Radestock
Subject: lambda as a _library_ syntax
Message-ID: <7eb8ac3e.0312281605.76c74f1c@posting.google.com>
Status: OR

R5RS differentiates between primitive and derived expression types,
see Sections 4 and 7.3. Derived forms such as 'let' or 'cond' can be
defined as macros, and are thus classified as 'library syntax'. At the
core of the primitive forms is the fundamental binding form, the
symbol of our faith -- lambda.

Or is it so fundamental? Can we implement lambda in terms of something
else? This article shows that we can, which gives us an ability to
overload the top-level lambda, for tracing or for mischief. Once
again, the R5RS macro system has exceeded our expectations.

The article falls within the gray area of R5RS. R5RS does not promise
that our lambda-overloading will work on every Scheme system.  On the
other hand, R5RS does not declare our method to be in error. Following
Niels Bohr, the lambda-overloading technique may then be called
'non-trivial'. As it stands, the technique works on Scheme48 and
Bigloo 2.4b. With some changes the examples below work on Petite Chez
Scheme as well (the change is made necessary by the failure of
(Petite) Chez Scheme to implement one R5RS requirement) [see comment
at the end].
[On the USENET discussion thread, Joe Marshall noted that
the technique also works on PLT Scheme. MIT Scheme, on the other hand,
behaves like Chez Scheme in our case.]


The ability to overload the top-level lambda considerably amplifies
one's potential for mischief. For example, the Dirty-Macros paper is
often criticized that "the DEFILE macro must be wrapped around the
victim's code or it has no effect....Redefining the top-level LAMBDA
form so that it wraps the body with DEFILE may be beyond the scope of
R5RS macros." For good or for ill, it is not beyond.

Keeping in mind the season, we give below a benign application
of the top-level lambda-overloading. We overload lambda to trace all
explicit and implicit lambda-applications. The implicit ones arise
from the use of let forms.


Our technique is surprisingly short:

(define-syntax make-lambda 
  (syntax-rules ()
    ((make-lambda bindings body ...)
      (let-syntax () (define (proc . bindings) body ...)
	proc))))

(define-syntax lambda
  (syntax-rules ()
    ((lambda bindings body1 body2 ...)
     (make-lambda bindings
       (display "Entering lambda: ") (display 'bindings)
       (display " of values ") (display (list . bindings))
       (display "Happy Holidays!") (newline)
       (begin body1 body2 ...)))))


We can now define let-forms, which will use the above definition of
lambda:

(define-syntax let		; let, straight out of R5RS
  (syntax-rules ()
    ((let ((name val) ...) body1 body2 ...)
     ((lambda (name ...) body1 body2 ...) val ...))
    ((let tag ((name val) ...) body1 body2 ...)
     ((letrec ((tag
		(lambda (name ...) body1 body2 ...))) tag) val ...))))

(define-syntax let*		; let*, straight out of R5RS
  (syntax-rules ()
    ((let* () body1 body2 ...)
     (let () body1 body2 ...))
    ((let* ((name1 val1) (name2 val2) ...) body1 body2 ...)
     (let ((name1 val1)) (let* ((name2 val2) ...) body1 body2 ...)))))

; A shorter implementations of letrec, see
; "Re: Widespread bug (arguably) in letrec when an initializer returns twice"
; comp.lang.scheme, 2001-05-21 10:30:34 PST and 2001-05-21 14:56:49 PST
;http://google.com/groups?selm=7eb8ac3e.0105210930.21542605%40posting.google.com
;http://google.com/groups?selm=87ae468j7x.fsf%40app.dial.idiom.com

(define-syntax letrec
  (syntax-rules ()
    ((letrec ((var init) ...) . body)
     (let ((var 'undefined) ...)
       (let* ((temp (list init ...))
	      (temp (begin (set! var (car temp)) (cdr temp)))
	       ...)
	 . body)))))

And now we are ready to run examples. At the top level!

(let ((p (lambda (x y z) (list x y z))))
  (display (p 1 2 3)))
(newline)

(display
  (let loop ((n 5))
    (if (zero? n) 1 (* n (loop (- n 1))))))
(newline)

(letrec
  ((if-even? (lambda (n) (or (zero? n) (if-odd? (- n 1)))))
   (if-odd?  (lambda (no) (and (> no 0) (if-even? (- no 1))))))
  (display (if-even? 10)))
(newline)


In particular, the second example prints:

Entering lambda: (loop) of values (undefined)Happy Holidays!
Entering lambda: (temp) of values ((#<procedure:8190c7c.1>))Happy Holidays!
Entering lambda: (temp) of values (())Happy Holidays!
Entering lambda: () of values ()Happy Holidays!
Entering lambda: (n) of values (5)Happy Holidays!
Entering lambda: (n) of values (4)Happy Holidays!
Entering lambda: (n) of values (3)Happy Holidays!
Entering lambda: (n) of values (2)Happy Holidays!
Entering lambda: (n) of values (1)Happy Holidays!
Entering lambda: (n) of values (0)Happy Holidays!
120


So, lambda is just a library syntax....


To make the examples work in Petite Chez Scheme, we have to forgo
tracing through let and replace (let-syntax () ...) with (let () ...)
so that make-lambda reads as follows.

(define-syntax make-lambda 
  (syntax-rules ()
    ((make-lambda bindings body ...)
      (let () (define (proc . bindings) body ...)
	proc))))

This change is necessary because Petite Chez Scheme does not fully comply
with R5RS. Given an expression

(foo (let-syntax () (define a 1) a))

petite says
> Error: invalid context for definition (define (a) 1).

in violation of Section 5.2.2 of R5RS:

"5.2.2 Internal definitions

Definitions may occur at the beginning of a <body> (that is, the body
of a lambda, let, let*, letrec, let-syntax, or letrec-syntax
expression or that of a definition of an appropriate form)."

Therefore, we can propose the following R5RS compliance test:

(let ((foo (lambda (x) x)))
  (list
    (foo ((lambda () (define a 1) a)))
    (foo (let ()  (define a 1) a))
    (foo (let* ()  (define a 1) a))
    (foo (letrec ()  (define a 1) a))
    (foo (letrec ()  (define (b) (define a 1) a) (b)))
    (foo (let-syntax () (define a 1) a))
    (foo (letrec-syntax () (define a 1) a))
))

According to R5RS, the test must evaluate without errors and yield
'(1 1 1 1 1 1 1).
It does so on Scheme48, Bigloo 2.4b, Gambit-C 3.0 (with
syntax-case.scm loaded), and SCM -- but fails on Petite Chez Scheme.


In a follow-up message posted on comp.lang.scheme on 2003-12-29 01:29:02 PST 
Matthias Radestock noted:

``psyntax, which Petite Chez Scheme uses, treats let-syntax and 
letrec-syntax as splicing constructs *by design*. This is pointed out in 
the introduction to psyntax. According to Kent Dybvig the general 
consensus among implementors in 1998 was that this is the right thing to 
do, but it is of course in violation of the letter of r5rs. To get the 
non-splicing behaviour, one has to wrap the construct in a (let () ...), 
as you did in your fix. AFAIK your code is the first example where this 
change is shown to result in a loss of expressiveness.''