Title

define-immutable: A Syntax to Define Identifiers With Immutable Values

Author

Andrew Wilcox
http://andrewwilcox.name/

Status

This SRFI is currently in withdrawn status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-65@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

The define-immutable form defines an identifier whose value never changes.

The expression part of the definition is evaluated lazily: it is not evaluated unless and until the identifier is evaluated. This permits an immutable definition to use other definitions in more ways than is possible when using define in internal definitions.

A series of immutable definitions have simple semantics, making them easy to program and understand.

    (let ()
      (define-immutable x (+ z 5))
      (define-immutable y (/ 100 4))
      (define-immutable z (add-10 y))
      (define-immutable add-10 (add-n 10))
      (define-immutable (add-n n)
        (lambda (x)
          (+ n x)))
      x)
  =>
    40

Issues

The specification is tight and is easily implemented using anonymous modules and identifier-syntax from the portable syntax-case expander. However it would be useful to see if define-immutable can be implemented in other macro and module systems. It might turn out that this SRFI is over-specified, and that changing or relaxing the specification might allow define-immutable to be implemented in a wider variety of Scheme implementations.

I welcome suggestions on the proper use of Scheme terminology such as "binding", "identifier", "define", "scope", etc.

In the reference implementation, binding an identifier to multiple values works perfectly fine:

    (let ()
      (define-immutable x (values 1 2 3))
      (call-with-values
        (lambda () x)
        (lambda (a b c)
          (+ a b c))))
  =>
    6

Should this behavior be included in the specification?

Rationale

In R5RS, the semantics of the standard define form when used in an internal definition are fairly complicated:

In turn, a letrec form first establishes locations (a lexical scope) for all the variables (with each bound to an undefined value), and then the expressions in all the definitions are evaluated and assigned to the variables.

While complicated, these semantics allow a variable created by a define to be later assigned a new value with set!, and, at the same time, provides for some ways in which one definition may use another. For example, defined functions may be mutually recursive, as seen in this code (adapted from the letrec example in R5RS):

    ; R5RS
    (let ()
      (define (even? n)
        (if (zero? n) #t (odd? (- n 1))))
      (define (odd? n)
        (if (zero? n) #f (even? (- n 1))))
      (even? 88))
  =>
    #t

However, other useful ways in which one definition may refer to another are not allowed by a letrec:

    ; in R5RS
    (let ()
      (define ten 10)
      (define twenty (+ ten 10))
      (+ ten twenty))
  =>
    Error

A Scheme implementation might choose to have internal definitions expand instead into a letrec* form [1]. This increases the ways in which one definition may refer to another: later definitions of simple values may use earlier ones. Thus,

    ; internal definitions expand into a letrec*
    (let ()
      (define ten 10)
      (define twenty (+ ten 10))
      (+ ten twenty))
  =>
    30

The programmer still needs to analyze the dependencies between definitions and place dependent definitions after the ones that are made use of.

    ; internal definitions expand into a letrec*
    (let ()
      (define twenty (+ ten 10))
      (define ten 10)
      (+ ten twenty))
  =>
    Error

If the value an identifier doesn't need to change because it is never assigned to a set! form, we have an opportunity to use simpler semantics for defining values, and to expand the ways that one definition may use another.

The define-immutable special form declares an identifier whose value never changes. To maximize the number of ways that immutable definitions can refer to each other, the definition's expression is evaluated lazily: it isn't evaluated unless and until the identifier itself is used in an expression.

    (let ()
      (define-immutable (add-n n)
        (lambda (x)
          (+ x n)))
      (define-immutable add-10 (add-n 10))
      (define-immutable add-20 (add-n 20))
      (list (add-10 5) (add-20 5)))
  =>
    (15 25)

Specification

The R5RS <definition> production is extended to include the define-immutable special form.

    <definition> -> ... | <immutable definition>
    <immutable definition> ->
      (define-immutable <identifier> <expression>) |
      (define-immutable (<identifier> . <def formals>) <body>)

The first form

    (define-immutable identifier expression)

is a binding construct which declares identifier to be an immutable value.

Evaluating the identifier causes the expression to be evaluated, and the value of the identifier is the result of evaluating the expression.

The expression is not evaluated unless and until the identifier is evaluated, and the expression is evaluated only once.

Bindings introduced by define-immutable are hygienic, as described in R5RS section 4.3.

The second form

    (define-immutable (identifier . formals) body ...)

is an abbreviation for:

    (define-immutable identifier (lambda formals body ...))

Immutable definitions may reference other immutable definitions within the same syntactic scope, and in any order:

    (let ()
      (define-immutable a (+ b 10))
      (define-immutable b (* 3 5))
      a)
  =>
    25

Both regular definitions (with define) and immutable definitions may shadow other definitions in an enclosing scope:

    (let ()
      (define-immutable a 10)
      (define-immutable b 20)
      (define c 30)
      (let ()
        (define-immutable a 40)
        (define b 50)
        (define-immutable c 60)
        (list a b c)))
  =>
    (40 50 60)

However, it is an error for an identifier to have an immutable definition when another definition of that same identifier exists in the same syntactic scope:

    (let ()
      (define a 10)
      (define-immutable a 20)
      a)
  =>
    Error


    (let ()
      (define-immutable a 10)
      (define a 10)
      a)
  =>
    Error


    (let ()
      (define-immutable a 10)
      (define-immutable a 20)
      a)
  =>
    Error

If a Scheme implementation provides modules, an identifier defined with define-immutable should be able to be exported as regular variables are.

Implementation

The reference implementation uses anonymous modules and identifier-syntax from the portable syntax-case expander, and delay, force, and syntax-rules from R5RS.

(define-syntax define-immutable
  (syntax-rules ()

    ((define-immutable (identifier . formals) body ...)
     (define-immutable identifier
       (lambda formals body ...)))

    ((define-immutable identifier expression)
     (module ((identifier promise))
       (define promise (delay expression))
       (define-syntax identifier (identifier-syntax (force promise)))))))

Test Cases

These tests check particular details of the the specification.

(define (test title result)
  (display (if result "yes: " " no: "))
  (display title)
  (newline))

(test "later definitions can reference earlier ones"
  (equal? '(10 20)
    (let ()
      (define-immutable a 10)
      (define-immutable b (+ a 10))
      (list a b))))

(test "earlier definitions can reference later ones"
  (equal? '(20 10)
    (let ()
      (define-immutable a (+ b 10))
      (define-immutable b 10)
      (list a b))))

(test "a definition can reference itself"
  (equal? 120
   (let ()
     (define-immutable factorial
       (lambda (n)
         (if (zero? n) 1
             (* n (factorial (- n 1))))))
     (factorial 5))))

(test "inner scope definitions shadow outer ones"
  (equal? '(40 50 60)
    (let ()
      (define-immutable a 10)
      (define-immutable b 20)
      (define c 30)
      (let ()
        (define-immutable a 40)
        (define b 50)
        (define-immutable c 60)
        (list a b c)))))


(test "immutable definitions are not evaluated unless used"
  (equal? 100
    (let ()
      (define-immutable a (/ 1 0))
      100)))

(test "immutable definitions are evaluated only once"
  (equal? 1
    (let ((count 0))
      (define-immutable a
        (let ()
          (set! count (+ count 1))
          100))
      a
      a
      a
      a
      count)))

(test "expansion into a lambda form"
  (equal? 112
    (let ()
      (define-immutable x (+ z 77))
      (define-immutable y (/ 100 4))
      (define-immutable z (add-10 y))
      (define-immutable add-10 (add-n 10))
      (define-immutable (add-n n)
        (lambda (x)
          (+ n x)))
      x)))

(test "bindings introduced by define-immutable are hygienic"
  (equal? 10
    (let ()
      (let-syntax ((define-a
                     (syntax-rules ()
                       ((define-a)
                        (define-immutable a 20)))))
        (let ((a 10))
          (define-a)
          a)))))

Error Test Cases

A Scheme implementation is not required to detect errors or provide a way of capturing them. However, for Scheme implementations which do detect these errors, the following tests check for some cases of invalid syntax.

; (erroneous? thunk) should return #t if calling thunk results in an
; error, and should return #f if calling thunk returns normally.

; an implementation of erroneous? which uses with-failure-continuation
(define (erroneous? thunk)
  (with-failure-continuation
   (lambda (error continuation)
     #t)
   (lambda ()
     (thunk)
     #f)))

; an implementation of erroneous? which uses error-handler
(define (erroneous? thunk)
  (call-with-current-continuation
   (lambda (return)
     (parameterize ((error-handler (lambda (who msg . args)
                                     (return #t))))
       (thunk)
       #f))))

(define (expect-error form)
  (erroneous? (lambda ()
                (eval form))))

(test "may not define-immutable the same identifier twice in the same scope"
  (expect-error
    '(let ()
      (define-immutable a 10)
      (define-immutable a 20)
      a)))

(test "may not define and define-immutable the same identifier in the same scope"
  (expect-error
    '(let ()
      (define a 10)
      (define-immutable a 20)
      a)))

Syntax-case Module Test Cases

These tests explore the interaction of define-immutable and modules from the portable syntax-case implementation. Naturally they are only relevant if the portable syntax-case module system is being used.

(test "a define-immutable identifier can be imported from another module"
  (equal? 123
    (let ()
      (module x (a)
        (define-immutable a 123))
      (let ()
        (import x)
        a))))

(test "a define-immutable identifier can be imported through several modules"
  (equal? 123
    (let ()
      (module x (a)
        (define-immutable a 123))
      (module y (a)
        (import x))
      (module z (a)
        (import y))
      (let ()
        (import z)
        a))))

(begin
  (module m (a b)
    (define-immutable a 10)
    (define-immutable b 20))
  (test "multiple define-immutable exports from a top-level module"
    (equal? '(10 20)
      (let ()
        (import m)
        (list a b)))))

Acknowledgments

My thanks to Jens Axel Søgaard and Marcin 'Qrczak' Kowalczyk for help with writing macros with the syntax case expander, and to Michael Sperber for explaining the portability issue with R5RS not specifying whether or not define is a binding form.

References

1. Oscar Waddell, Dipanwita Sarkar, R. Kent Dybvig. Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct. http://www.cs.indiana.edu/~dyb/pubs/fixing-letrec.pdf

Copyright

Copyright (C) Andrew Wilcox (2005). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Mike Sperber