20 February 1998

Derived expression types
========================

This section gives macro definitions for the derived expression types in
terms of the primitive expression types (literal, variable, call,
`lambda', `if', `set!').  See section Control features for a
possible definition of `delay'.

     (define-syntax cond
       (syntax-rules (else =>)
         ((cond (else result1 result2 ...))
          (begin result1 result2 ...))
         ((cond (test => result))
          (let ((temp test))
            (if temp (result temp))))
         ((cond (test => result) clause1 clause2 ...)
          (let ((temp test))
            (if temp
                (result temp)
                (cond clause1 clause2 ...))))
         ((cond (test)) test)
         ((cond (test) clause1 clause2 ...)
          (let ((temp test))
            (if temp
                temp
                (cond clause1 clause2 ...))))
         ((cond (test result1 result2 ...))
          (if test (begin result1 result2 ...)))
         ((cond (test result1 result2 ...)
                clause1 clause2 ...)
          (if test
              (begin result1 result2 ...)
              (cond clause1 clause2 ...)))))

     (define-syntax case
       (syntax-rules (else)
         ((case (key ...)
            clauses ...)
          (let ((atom-key (key ...)))
            (case atom-key clauses ...)))
         ((case key
            (else result1 result2 ...))
          (begin result1 result2 ...))
         ((case key
            ((atoms ...) result1 result2 ...))
          (if (memv key '(atoms ...))
              (begin result1 result2 ...)))
         ((case key
            ((atoms ...) result1 result2 ...)
            clause clauses ...)
          (if (memv key '(atoms ...))
              (begin result1 result2 ...)
              (case key clause clauses ...)))))

     (define-syntax and
       (syntax-rules ()
         ((and) #t)
         ((and test) test)
         ((and test1 test2 ...)
          (if test1 (and test2 ...) #f))))

     (define-syntax or
       (syntax-rules ()
         ((or) #f)
         ((or test) test)
         ((or test1 test2 ...)
          (let ((x test1))
            (if x x (or test2 ...))))))

     (define-syntax let
       (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*
       (syntax-rules ()
         ((let* () body1 body2 ...)
          (let () body1 body2 ...))
         ((let* ((name1 val1) (name2 val2) ...)
            body1 body2 ...)
          (let ((name1 val1))
            (let* ((name2 val2) ...)
              body1 body2 ...)))))

The following `letrec' macro uses the symbol `<undefined>' in place of
an expression which returns something that when stored in a location
makes it an error to try to obtain the value stored in the location (no
such expression is defined in Scheme).  A trick is used to generate the
temporary names needed to avoid specifying the order in which the
values are evaluated.  This could also be accomplished by using an
auxiliary macro.

     (define-syntax letrec
       (syntax-rules ()
         ((letrec ((var1 init1) ...) body ...)
          (letrec "generate temp names"
            (var1 ...)
            ()
            ((var1 init1) ...)
            body ...))
         ((letrec "generate temp names"
            ()
            (temp1 ...)
            ((var1 init1) ...)
            body ...)
          (let ((var1 <undefined>) ...)
            (let ((temp1 init1) ...)
              (set! var1 temp1)
              ...
              body ...)))
         ((letrec "generate temp names"
            (x y ...)
            (temp ...)
            ((var1 init1) ...)
            body ...)
          (letrec "generate temp names"
            (y ...)
            (newtemp temp ...)
            ((var1 init1) ...)
            body ...))))

     (define-syntax begin
       (syntax-rules ()
         ((begin exp ...)
          ((lambda () exp ...)))))

The following alternative expansion for `begin' does not make use of
the ability to write more than one expression in the body of a lambda
expression.  In any case, note that these rules apply only if the body
of the `begin' contains no definitions.

     (define-syntax begin
       (syntax-rules ()
         ((begin exp)
          exp)
         ((begin exp1 exp2 ...)
          (let ((x exp1))
            (begin exp2 ...)))))

The following definition of `do' uses a trick to expand the variable
clauses.  As with `letrec' above, an auxiliary macro would also work.
The expression `(if #f #f)' is used to obtain an unspecific value.

     (define-syntax do
       (syntax-rules ()
         ((do ((var init step ...) ...)
              (test expr ...)
              command ...)
          (letrec
            ((loop
              (lambda (var ...)
                (if test
                    (begin
                      (if #f #f)
                      expr ...)
                    (begin
                      command
                      ...
                      (loop (do "step" var step ...)
                            ...))))))
            (loop init ...)))
         ((do "step" x)
          x)
         ((do "step" x y)
          y)))

Notes
*****

Language changes
================

This section enumerates the changes that have been made to Scheme since
the "Revised^4 report" [R4RS] was published.

   * The report is now a superset of the IEEE standard for Scheme
     [IEEEScheme]: implementations that conform to the report will also
     conform to the standard.  This required the following changes:

        * The empty list is now required to count as true.

        * The classification of features as essential or inessential
          has been removed.  There are now three classes of built-in
          procedures: primitive, library, and optional.  The optional
          procedures are `load', `with-input-from-file',
          `with-output-to-file', `transcript-on', `transcript-off', and
          `interaction-environment', and `-' and `/' with more than two
          arguments.  None of these are in the IEEE standard.

        * Programs are allowed to redefine built-in procedures.  Doing
          so will not change the behavior of other built-in procedures.

   * *Port* has been added to the list of disjoint types.

   * The macro appendix has been removed.  High-level macros are now
     part of the main body of the report.  The rewrite rules for
     derived expressions have been replaced with macro definitions.
     There are no reserved identifiers.

   * `Syntax-rules' now allows vector patterns.

   * Multiple-value returns, `eval', and `dynamic-wind' have been added.

   * The calls that are required to be implemented in a properly
     tail-recursive fashion are defined explicitly.

   * ``@'' can be used within identifiers. ``|'' is reserved for
     possible future extensions.

Additional material
*******************

The Internet Scheme Repository at

            `http://www.cs.indiana.edu/scheme-repository/'

contains an extensive Scheme bibliography, as well as papers, programs,
implementations, and other material related to Scheme.

Example
*******

`Integrate-system' integrates the system

           y_k^^ = f_k(y_1, y_2, ..., y_n),    k = 1, ..., n

of differential equations with the method of Runge-Kutta.

The parameter system-derivative is a function that takes a system state
(a vector of values for the state variables y_1, ..., y_n) and produces
a system derivative (the values y_1^^, ...,y_n^^).  The parameter
initial-state provides an initial system state, and h is an initial
guess for the length of the integration step.

The value returned by `integrate-system' is an infinite stream of
system states.

     (define integrate-system
       (lambda (system-derivative initial-state h)
         (let ((next (runge-kutta-4 system-derivative h)))
           (letrec ((states
                     (cons initial-state
                           (delay (map-streams next
                                               states)))))
             states))))

`Runge-Kutta-4' takes a function, f, that produces a system derivative
from a system state.  `Runge-Kutta-4' produces a function that takes a
system state and produces a new system state.

     (define runge-kutta-4
       (lambda (f h)
         (let ((*h (scale-vector h))
               (*2 (scale-vector 2))
               (*1/2 (scale-vector (/ 1 2)))
               (*1/6 (scale-vector (/ 1 6))))
           (lambda (y)
             ;; y is a system state
             (let* ((k0 (*h (f y)))
                    (k1 (*h (f (add-vectors y (*1/2 k0)))))
                    (k2 (*h (f (add-vectors y (*1/2 k1)))))
                    (k3 (*h (f (add-vectors y k2)))))
               (add-vectors y
                 (*1/6 (add-vectors k0
                                    (*2 k1)
                                    (*2 k2)
                                    k3))))))))

     (define elementwise
       (lambda (f)
         (lambda vectors
           (generate-vector
             (vector-length (car vectors))
             (lambda (i)
               (apply f
                      (map (lambda (v) (vector-ref  v i))
                           vectors)))))))

     (define generate-vector
       (lambda (size proc)
         (let ((ans (make-vector size)))
           (letrec ((loop
                     (lambda (i)
                       (cond ((= i size) ans)
                             (else
                              (vector-set! ans i (proc i))
                              (loop (+ i 1)))))))
             (loop 0)))))

     (define add-vectors (elementwise +))

     (define scale-vector
       (lambda (s)
         (elementwise (lambda (x) (* x s)))))

`Map-streams' is analogous to `map': it applies its first argument (a
procedure) to all the elements of its second argument (a stream).

     (define map-streams
       (lambda (f s)
         (cons (f (head s))
               (delay (map-streams f (tail s))))))

Infinite streams are implemented as pairs whose car holds the first
element of the stream and whose cdr holds a promise to deliver the rest
of the stream.

     (define head car)
     (define tail
       (lambda (stream) (force (cdr stream))))

The following illustrates the use of `integrate-system' in integrating
the system

                     C dv_C / dt = -i_L - v_C / R

                           L di_L / dt = v_C

which models a damped oscillator.

     (define damped-oscillator
       (lambda (R L C)
         (lambda (state)
           (let ((Vc (vector-ref state 0))
                 (Il (vector-ref state 1)))
             (vector (- 0 (+ (/ Vc (* R C)) (/ Il C)))
                     (/ Vc L))))))

     (define the-states
       (integrate-system
          (damped-oscillator 10000 1000 .001)
          '#(1 0)
          .01))

Bibliography
************

   * [SICP] Harold Abelson and Gerald Jay Sussman with Julie Sussman.
     *Structure and Interpretation of Computer Programs, second
     edition.* MIT Press, Cambridge, 1996.

   * [Bawden88] Alan Bawden and Jonathan Rees.  Syntactic closures.  In
     *Proceedings of the 1988 ACM Symposium on Lisp and   Functional
     Programming*, pages 86-95.

   * [howtoprint] Robert G. Burger and R. Kent Dybvig.  Printing
     floating-point numbers quickly and accurately.  In *Proceedings of
     the ACM SIGPLAN '96 Conference   on Programming Language Design
     and Implementation*, pages 108-116.

   * [RRRS] William Clinger, editor.  The revised revised report on
     Scheme, or an uncommon Lisp.  MIT Artificial Intelligence Memo
     848, August 1985.  Also published as Computer Science Department
     Technical Report 174,   Indiana University, June 1985.

   * [howtoread] William Clinger.  How to read floating point numbers
     accurately.  In *Proceedings of the ACM SIGPLAN '90 Conference
     on Programming Language Design and Implementation*, pages 92-101.
     Proceedings published as *SIGPLAN Notices* 25(6), June 1990.

   * [R4RS] William Clinger and Jonathan Rees, editors.  The revised^4
     report on the algorithmic language Scheme.  In *ACM Lisp Pointers*
     4(3), pages 1-55, 1991.

   * [macrosthatwork] William Clinger and Jonathan Rees.  Macros that
     work.  In *Proceedings of the 1991 ACM Conference on Principles of
      Programming Languages*, pages 155-162.

   * [propertailrecursion] William Clinger.  Proper Tail Recursion and
     Space Efficiency.  To appear in *Proceedings of the 1998 ACM
     Conference on Programming  Language Design and Implementation*,
     June 1998.

   * [syntacticabstraction] R. Kent Dybvig, Robert Hieb, and Carl
     Bruggeman.  Syntactic abstraction in Scheme.  *Lisp and Symbolic
     Computation* 5(4):295-326, 1993.

   * [Scheme311] Carol Fessenden, William Clinger, Daniel P. Friedman,
     and Christopher Haynes.  Scheme 311 version 4 reference manual.
     Indiana University Computer Science Technical Report 137, February
     1983.  Superseded by [Scheme84].

   * [Scheme84] D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand.
     Scheme 84 interim reference manual.  Indiana University Computer
     Science Technical Report 153, January 1985.

   * [IEEE] *IEEE Standard 754-1985.  IEEE Standard for Binary
     Floating-Point Arithmetic.*  IEEE, New York, 1985.

   * [IEEEScheme] *IEEE Standard 1178-1990.  IEEE Standard for the
     Scheme   Programming Language.*  IEEE, New York, 1991.

   * [Kohlbecker86] Eugene E. Kohlbecker Jr.  *Syntactic Extensions in
     the Programming Language Lisp.* PhD thesis, Indiana University,
     August 1986.

   * [hygienic] Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias
     Felleisen, and Bruce Duba.  Hygienic macro expansion.  In
     *Proceedings of the 1986 ACM Conference on Lisp   and Functional
     Programming*, pages 151-161.

   * [Landin65] Peter Landin.  A correspondence between Algol 60 and
     Church's lambda notation: Part I.  *Communications of the ACM*
     8(2):89-101, February 1965.

   * [MITScheme] MIT Department of Electrical Engineering and Computer
     Science.  Scheme manual, seventh edition.  September 1984.

   * [Naur63] Peter Naur et al.  Revised report on the algorithmic
     language Algol 60.  *Communications of the ACM* 6(1):1-17, January
     1963.

   * [Penfield81] Paul Penfield, Jr.  Principal values and branch cuts
     in complex APL.  In *APL '81 Conference Proceedings,* pages
     248-256.  ACM SIGAPL, San Francisco, September 1981.  Proceedings
     published as *APL Quote Quad* 12(1), ACM, September 1981.

   * [Pitman83] Kent M. Pitman.  The revised MacLisp manual (Saturday
     evening edition).  MIT Laboratory for Computer Science Technical
     Report 295, May 1983.

   * [Rees82] Jonathan A. Rees and Norman I. Adams IV.  T: A dialect of
     Lisp or, lambda: The ultimate software tool.  In *Conference
     Record of the 1982 ACM Symposium on Lisp and   Functional
     Programming*, pages 114-122.

   * [Rees84] Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan.
     The T manual, fourth edition.  Yale University Computer Science
     Department, January 1984.

   * [R3RS] Jonathan Rees and William Clinger, editors.  The revised^3
     report on the algorithmic language Scheme.  In *ACM SIGPLAN
     Notices* 21(12), pages 37-79, December 1986.

   * [Reynolds72] John Reynolds.  Definitional interpreters for higher
     order programming languages.  In *ACM Conference Proceedings*,
     pages 717-740.  ACM,  1972.

   * [Scheme78] Guy Lewis Steele Jr. and Gerald Jay Sussman.  The
     revised report on Scheme, a dialect of Lisp.  MIT Artificial
     Intelligence Memo 452, January 1978.

   * [Rabbit] Guy Lewis Steele Jr.  Rabbit: a compiler for Scheme.  MIT
     Artificial Intelligence Laboratory Technical Report 474, May 1978.

   * [CLtL] Guy Lewis Steele Jr.  *Common Lisp: The Language, second
     edition.* Digital Press, Burlington MA, 1990.

   * [Scheme75] Gerald Jay Sussman and Guy Lewis Steele Jr.  Scheme: an
     interpreter for extended lambda calculus.  MIT Artificial
     Intelligence Memo 349, December 1975.

   * [Stoy77] Joseph E. Stoy.  *Denotational Semantics: The
     Scott-Strachey Approach to   Programming Language Theory.* MIT
     Press, Cambridge, 1977.

   * [TImanual85] Texas Instruments, Inc.  TI Scheme Language Reference
     Manual.  Preliminary version 1.0, November 1985.

Alphabetic index of definitions of concepts, keywords, and procedures
*********************************************************************

The principal entry for each term, procedure, or keyword is listed
first, separated from the other entries by a semicolon.

Concepts
========

Procedures
==========

References
==========