Gref: Generalized References for Racket🔗ℹ

Gref is a proof-of-concept implementation of generalized references for Racket. It is intended as a showcase for Racket’s language extension capabilities. For practical purposes, one is reminded of Racket’s general discouragement of assignments (see Guidelines for Using Assignment). For the alternative approach of functional references, also known as optics, see Lenses and Glass: Composable Optics.

1 Introduction🔗ℹ

What does it mean for something to be stored? To account for this, imperative languages have long adopted the concept of l-values since Strachey (2000). For example, consider the following Algol 60 program:

begin

integer array intbox[0:0];

intbox[0] := 1;

printnln(intbox[0])

end

Above, intbox[0] is an l-value that represents a location, and thus can be both read and write. The concept of locations is already defined in Racket (see Variables and Locations), so it is not difficult to imagine a concept similar to l-values. Indeed, generalized references, also known as places, are provided by Lisp Machine Lisp–inspired Lisps.

The concept of generalized references originates from Deutsch (1973), and has since been implemented for Lisp Machine Lisp, MacLisp, Common Lisp, and Emacs Lisp. For a detailed discussion on the history of generalized references, see Steele and Gabriel (1993). This section focuses on the technical aspects of generalized references.

The simplest implementation of generalized references is as in SRFI 17, resembling the original proposal by Deutsch (1973) to an extent. That is, a getter procedure can be associated with a setter procedure, where

(proc arg ...)

corresponds to

((setter proc) arg ... val)

such that setter maps the getter to setter. This is a simple yet elegant design. Unfortunately, this approach suffers from the fact that the setter must be dynamically resolved. Instead, Gref has adopted a full-blown macro approach similar to that of Lisp Machine Lisp, which allows for static resolution and more. In Gref, a fully-expanded generalized reference corresponding to some locations where some values are stored consists of four items:

1. An arity number for the number of values stored in the locations;

2. A getter procedure that accepts zero arguments and returns the values stored in the locations;

3. A setter procedure that accepts as many arguments as the arity and updates the locations;

4. A sequence of preamble forms that sets up the environment for the evaluation and validation of sub-expressions.

The preambles are supposed to precede any use of getter and setter within an internal-definition context, so that any introduced binding can be referred to. This way, the two modes of accesses, that is, reads and writes can be performed within the same context. In particular, multiple accesses can be performed at once while preserving the apparent left-to-right evaluation order (see Evaluation Order and Arity).

Another technical advantage is that a reference is allowed to represent multiple locations, including none. The arity determines the number of values stored in the locations. A well-behaved reference must arrange the getter and setter such that the former returns as many values as the arity, and the latter stores as many to the locations. The results of the setter are unspecified, but they should generally be #<void> following Racket’s convention (see Void and Undefined).

Before the accesses are performed, the outer box is unboxed exactly once and its content is validated to be box?. Then, the accesses are performed without unnecessary repeated evaluation. This capability further enables modify macros like shift! and rotate!.

2 The Base Module🔗ℹ

2.1 set! Expanders🔗ℹ

The provided set! expanders are defined through define-set!-syntax and make-set!-expander. All documented set! expanders preserve the apparent order of the sub-expressions and accordingly validate the results. When an inapproapriate result is detected, the exn:fail:contract exception is raised.

syntax (set! form vals)

vals   :   any

indicates that form is in a set! context, where the set! expander is invoked and produces a further expanded reference. A set! context is available in certain sub-form positions of set! expanders and modify macros where a reference is explicitly required. All documented set! expanders extend the base Racket procedures, and thus shadow the corresponding bindings in the default binding space as provided by racket/base.

2.2 Modify Macros🔗ℹ

Modify macros are macros that operate on references. They are defined as usual macros, that is, (-> syntax? syntax?) procedures. Unless otherwise stated, the result of a modify macro is always #<void>.

3 The Syntax Module🔗ℹ

Returns a fully-expanded number-valued reference. The first two by-position arguments are the getter procedure and setter procedure, and the remaining by-position arguments are the preamble forms. The resulting syntax object is given the source-location information of src.

A structure type property to identify structure types that act as set! expanders used by gref. The property value takes the structure instance that implements prop:set!-expander and results in a set! expander, which in turn takes the syntax object of a number-valued reference and results in another number-valued reference.

Returns #t if val implements prop:set!-expander, #f otherwise.

Returns an implementation of prop:set!-expander that uses proc as the set! expander.

Returns an implementation of prop:set!-expander that expands functional forms. A functional form with the shape (who arg ...) where who’s transformer binding is the resulting implementation will be expanded such that:

• Each expression in arg is evaluated in the apparent order and bound to arg-val;

• A sequence of number identifiers val ... is generated;

• The expressions (lambda () (getter arg-val ...)) and (lambda (val ...) (setter arg-val ... val ...)) are used as the getter and setter.

In other words, it works as a static alternative to SRFI 17, generalized to multiple values.

A flat contract that accepts an expected arity, where #f means any arity.

Equivalent to (or/c #f exact-nonnegative-integer?).

Matches a number-valued reference. If number is #f, matches any reference. The reference is recursively expanded until fully expanded as follows:

• If it is a valid set!-packed form, the expansion is complete;

• If it is an identifier with a transformer binding or a syntax-object pair whose first element is such an identifier, the transformer binding is used to continue;

• Otherwise, if it is an identifier, a set! expander for variables is used to continue.

Each transformer binding is resolved in the 'gref/set! binding space. Due to the way scope sets works, a transformer binding in the default binding space will be used unless another transformer binding in the 'gref/set! binding space shadows it.

If the transformer binding refers to a set!-expander? value, it is used to produce a set! expander, which in turn receives the syntax object of the reference expanded so far. Otherwise, the matching fails and no further expansion is done. During each expansion step, scopes and syntax properties are accoridingly manipulated.

From the resulting set!-packed form, the following attributes are bound:

attribute arity : exact-nonnegative-integer?

attribute getter : syntax?

attribute setter : syntax?

attribute preamble : (listof syntax?)

The arity number, getter procedure, setter procedure, and preamble forms.

An alias for gref.

The procedural interface for gref. Expands ref-stx as a (gref #:arity number) form and returns the bound attributes in the documented order.

If syntax-transforming? returns #f, the exn:fail:contract exception is raised and no expansion is done.

Bibliography🔗ℹ

Index🔗ℹ