This material is based upon work supported by the National Science Foundation under Grant MCS75-06678 A01.
Author's address: Computer Science Department, Indiana University, Bloomington, IN 47401
The notion of a class, introduced in SIMULA 67 [1], has become a key concept in data structuring [2, 5, 11]. Interpretation of classes in the lambda calculus have been given by Sandewall [8], Steele and Sussman [10, inter alia], and Reynolds [7]. In this note we will give a particularly simple interpretation of classes† as syntactic sugar in SCHEME, an extended lambda calculus due to Steele and Sussman [9].
SCHEME is a LISP-like language with static scoping and full FUNARGS. The following samples give a flavor of the syntax:
(LET ((v1 e1)…(vn en)) exp)
is equivalent to
((LAMBDA (v1…vn) exp) (e1…en))
and
(LABELS ((v1 e1)…(vn en)) exp)
is equivalent to ISWIM's [4]
letrec v1=e1,…, vn=en in exp
where the ei are lambda expressions.
Here, as below, key words appear in upper case and metavariablies appear in italics.
Conditionals may be written as (IF pred then-part else-part).
An association-list, as in LISP [6]
may be searched by RASSOC,
defined as follows:
(DEFINE RASSOC (LAMBDA (KEY LIST)
(IF (NULL LIST) NIL
(IF (EQ KEY (CAAR LIST)) (CAR LIST)
(RASSOC KEY (CDR LIST)) ) ) ))
The semantics of the language allow the recursive call to be implemented iteratively.
A possible concrete syntax for classes is as follows:
(CLASS
((loc1 val1)…(locn valn))
((procname1 λ-exp1)
⋮
(procnamem λ-expm)))
An instance of the class defined in this manner
should have n local variables,
named loc1,…, locn
and initialized to val1,…, valn respectively.
Associated with the class
should be m class procedures,
named procname1,…, procnamem,
with procedure bodies λ1,…, λm.
These procedures may refer to the lcoal
and to each other
(possibly recursively),
but, in keeping with current thinking,
the locals should be accessible to the user of a class instance only through the class procedures.
To achieve this, the definition is expanded as follows:
(LET ((loc1 val1)…(locn valn))
(LABELS ((procname1 λ-exp1)…(procnamem λ-expm))
(LET
((D (LIST (CONS (QUOTE procname1) procname1)
⋮
(CONS (QUOTE procnamem) procnamem))))
(LAMBDA (Z) (RASSOC Z D)) )))
If X is an instance of a class
with a procedure named P,
a call written conventionally as
X.P(t1,…,tn)
is expanded as
((X (QUOTE P)) t1…tn)
Execution of the code for (CLASS locals procs) proceeds as follows:
This function is returned and is the class instance. Thus the procedure call above retrieves procedure P of class instance X, and invokes that procedure with arguments t1,…,tn. Since fresh closures are created for each class instance, this procedure work's on X's local variables.
This code is similar in its effect to the implementation of classes in SMALLTALK [3] and in its use of closures to Sandewall's code [8]. Our code extends Sandewall's by allowing multiple class procedures; this is the primary source of the complexity in the code. We differ from SIMULA and most implementation fo classes by making a class definition an expression, which can appear anywhere in a program. For example:
(DEFINE CELL (LAMBDA (X)
(CLASS (( CONTENTS X ))
(( CONT (LAMBDA () CONTENTS ))
(UPD (LAMBDA (VAL) (ASETQ CONTENTS VAL )))))))
A cell may then be created as:
(LET ((Z (CELL 3)))
(BLOCK
(PRINT ((Z (QUOTE CONT))))
((Z (QUOTE UPD)) 4)
(PRINT ((Z (QUOTE CONT)))) ))
which creates a cell initialized to 3, calls it Z, and changes its contents to 4, printing out 3 and 4.
Note that class parameters are introduced by creating a function
(LAMBDA (class-parameters) (CLASS locals procs))
which may be bound to a variable name of any lexical scope, and that procedure names (since they are quoted) need not be declared at all. Instances of the class, however, may be passed outside this scope; this makes the code more general than any special naming scheme. Steele and Sussman's transcription [10] requires the procedure names to be declared wherever a class instance is used; this prevents classes from sharing procedure names, a necessity for concatenated classes [1]. Unlike Reynolds [7], we also avoid major transformations in the program structure; imperative features are entirely optional.
At the expense of additional syntax, a variety of additional features could be added to the framework. Some functions could be hidden by suitable editing of the association list D. Direct access to some of the locals could be added similarly. Concatenated classes could be done by specifying one of the locals as an instance of the base class and changing the function returned so that if the desired procedure is not found locally, it is passed along to the base instance, i.e.,
(LET ((the-bases (base-class base-class-params)) …)
(LABELS (…)
(LET ((D…))
(LAMBDA (Z)
(IF (IS-PRESENT Z D) (RASSOC Z D)
(the-basis Z))))))
Since the locals are initialized, no class body is usually needed; one could easily be added if desired.
Operationally, classes are just syntactic sugar—their operational semantics requires no new concepts. We believe the significance of the notion of classes is as a syntactic structuring device. Structuring devices such as strong typing or good loop structures play an important role in ease of program writing and debugging, as shown by PASCAL, by turning run-time errors into compile-time errors. The significance of classes, we believe, is as a structuring device which allows better checking at compile time and verification time.
† except for resume and detach, which have not been adopted in the literature on data types. ↪