The authors were formerly associated with the Laboratory for Applied Logic of the University of Idaho. Copyright (C) 1993, Laboratory for Application Logic, University of Idaho. All rights reserved.
Dylan, an object-oriented dynamic language developed by Apple Computer, is designed to replace existing static languages for the development of large software systems, yet remains small and efficient enough for the next generation of portable computers. Dylan was developed from the language Scheme, augmented with the Common-Lisp Object System (CLOS).
In this article, we will model Dylan's type system. In doing so, we will formally define the terms class, method, generic function, and instance. We will also discuss features Dylan provides for efficiency and security. Function descriptions have been written to resemble that of the Haskell programming language. For more information on Dylan, refer to Dylan: An Object-Oriented Dynamic Language, by the Apple Computer Eastern Research and Technology Group (1992) and "A Taste of Dylan," by David Betz (DDJ, October 1992).
Major Concepts
For the most part, Dylan can be characterized by two main concepts: objects and functions. The core of Dylan implements objects and functions, but omits many of the features you need to write useful programs. Dylan extends the core with ten required libraries that provide control flow, numbers, and abstract data types.
All data values in Dylan are considered "objects," organized by groups of "classes." All objects are "instances" of at least one class, where the classes are organized into a heterarchy (direct acyclic graph) and inherit the features of classes above themselves in the heterarchy. The top of the heterarchy is the class <object>, the most general class in Dylan.
Classes determine the structural characteristics of their instances by specifying "slots," which hold the object's local state. Each slot has a name which identifies it, and functions (called "getters" and "setters") are used to read and write the values stored in the slots.
Functions in Dylan are objects that perform actions corresponding to functions, procedures, methods, and messages in other languages. Dylan has two types of functions: methods and generic functions.
Methods are functions that contain a typed argument list and a body of code. Methods are defined with typed formal parameters and can be applied to arguments with either the same class as the defined parameters or to subclasses of the defined parameters. If functions are applied to incorrect argument types, an error is signaled. Note that this type checking is performed at run time even though static analysis is possible.
Generic functions are ways to group together zero or more methods (each having different types) under the same function name. The generic function examines the types of the arguments and chooses the most appropriate method to invoke. If no appropriate method can be found, an error is generated. Since generic functions can be created and modified at run time, all type checking is dynamic. Generic functions are by definition overloaded and give Dylan ad hoc polymorphic capabilities.
The Dylan reference manual is often vague in its description of how classes, methods, and generic functions work together. To better understand Dylan, we have formalized the relationship of these entities. This section contains an abstract syntax and description of the basic operations on classes and functions. No static validity functions are provided since Dylan performs no static analysis.
Table 1 provides a list of the abstract syntax of classes, methods, and generic functions--note that Symbol and Expr are not defined. Symbol is analogous to Char+, and Expr corresponds with function bodies in Scheme.
Classes
The acyclic directed graph of classes can be represented in many ways. Our representations will be a list of Class, where classname is the name of a class, sl is a list of that class's slots, and subclasses is a list of classes that directly inherit properties from classname. The basic operations on classes can be coded; see Example 1.
New classes are created in Dylan with the function make-class, which takes three parameters: the name of the new class, a list of the direct superclasses of the new class, and a list of the new class's slots. For new classes, Dylan defines functions to access and update the slots. These getter and setter functions are added to the generic-function space later. Example 2(a) provides code to define new classes. In Example 2(b), FixLinks and Update add the new class to the heterarchy and make sure subclasses' lists get modified to reflect the new class. NewClass adds new classes to the heterarchy by checking that the class doesn't already exist. If the class does exist, it is removed and then added to the heterarchy again. Otherwise, the new class is added to the old class list and the subclass pointers are updated accordingly. Example 2(c) presents another operation on classes--making new instances of them.
Generic Functions
Generic functions in Dylan are overloaded functions that examine the types of their parameters and invoke the most appropriate method based on those types. We represented the space of all generic functions as a list, where each element in this list is itself a list of parameter lists and a pointer to the corresponding method that takes that parameter list. All top-level function applications in Dylan take place through generic functions.
The operations on generic functions include defining new generic functions, removing generic functions, adding methods to existing generic functions, removing methods from generic functions, and applying generic functions to arguments; see Example 3. Note in Example 3(f) that SpecificMethod chooses the most specific method to apply based on the types of the supplied parameters and SchemeApply is the apply function in Scheme modified so that if a function cannot be found in the Scheme top-level namespace, then the function name is treated as a generic function.
Methods
Methods are Dylan's basic functional unit, taking a list of typed parameters and returning a typed value. Methods can be defined but not applied by the user. Defining a method automatically creates a new generic function with the same name, and the new method is attached to the new generic function. A new method is defined by creating a new, unique identifier, called a "key," for this method, having Scheme bind the new key to the method's equivalent lambda expression in the Scheme namespace, adding the parameter list and key to the appropriate generic function, and creating a new generic function if required. Defining a new method must then alter the generic function space and the Scheme environment.
In Example 4, NewMethod creates a new method by modifying the Scheme environment and the generic function space. MkUniqueKey generates a new, unique key in the generic function space, and bind binds the key and the lambda expression in the Scheme environment.
An Example
To further illustrate how Dylan works, we'll use an example which calculates the square root of a number using Newton's method (see Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Sussman, MIT Press, 1985).
In Example 5, the Dylan implementation's call to define-method creates a generic function called newtons-sqrt that has one method with a parameter of type <object> (since x wasn't given a more specific class, it defaults to the most general class <object>) and stores the lambda expression Scheme's top-level environment. The local functions created with bind-methods do not generate functions themselves--these functions are stored, like any other Scheme local functions, in nested environments.
Tracing the call (newtons-sqrt 4) illustrates how Dylan and Scheme work together: The generic function newtons-sqrt is found and the argument class <number> matches the method <object>, so the Scheme function associated with that method is invoked with parameter 4. In the Scheme environment, the call (sqrt 1) is evaluated, generating the call (close? 1) which, in turn, generates the call (* 1 1). Since the asterisk (*) is not found in the Scheme environment, it is reevaluated as a generic function in Dylan. Dylan matches the types, dispatches the proper method to multiply guess, and continues.
Conclusion
In this article, we've focused on what sets Dylan apart from other functional and object-oriented languages. In doing so, the features we haven't covered include:
- Slot options: Slots may initial values, initializing functions, and storage-allocation modifiers.
- Additional method functions: Methods can defer execution to more general methods.
- Security options: Methods, generic functions, and classes may be "sealed," which prevents any modifications to these items.
- Efficiency option: Classes may be declared as "abstract" or "instantiable," preventing instantiation of classes that are too general to be implemented efficiently. Abstract classes could be used as parents to more concrete, instantiable classes. Generic functions can still be defined to operate on the abstract classes since they can be overloaded to deal with all of the instantiable classes.
Dylan lacks type inference and static type checking. Type inference could help verify correctness in Example 5, for instance, by inferring the type for the parameter x as <number> instead of <object>. But inference is complicated by Dylan's dynamic nature, which allows functions such as abs, +, *, and the like to be overloaded at run time to operate on nonnumeric objects. This dynamic nature also limits the use of any static type checking.
Since Dylan can be readily built by adding two new namespaces on top of Scheme--a graph representing the class heterarchy and a list of generic functions, each with a list of specific methods. These new namespaces, combined with new functions (to support the namespaces and replace the Scheme functions) form the core of the Dylan language.
Example 1: Basic operations on classes. (a) IsClass returns True if cl is a valid class; (b) GetSlots returns the slot list for class cl; (c) GetKids returns a list of direct descendants of class cl; (d) GetSupers returns a list of all of superclasses for class cl; (e) GetSubs returns a list of all of the subclasses for class cl, where unique removes duplicate items from a list and element checks for membership in a list.
(a)
IsClass :: ClassName -> ClassList -> Boolean
IsClass (cl:ClassName) ([]:ClassList) = False
IsClass cl (c::cs) =
if cl = c.name then True else IsClass cl cs
(b)
GetSlots :: ClassName -> ClassList -> SlotList
GetSlots (cl:ClassName) ([]:ClassList) = error "class not found
GetSlots cl (c::cs) =
if cl = c.name then c.sl also GetSlots cl cs
(c)
GetKids :: ClassName -> ClassList -> ClassList
GetKids (cl:ClassName) ([]:ClassList) = error "class not found
GetKids cl (c::cs) =
if cl = c.name then c.subclasses else GetKids cl cs
(d)
GetSupers :: ClassName -> ClassList -> ClassList -> ClassList
GetSupers (cl:ClassName) ([]:ClassList) = (CC:ClassList) = []
GetSupers cl (c::cs) CC =
if element cl = c.subclasses
then unique ((cl.name::GetSupers cl cs CC)@(GetSupers c.name CC CC))
else GetSupers cl cs CC
(e)
GetSubs :: ClassName -> ClassList -> ClassList -> ClassList
GetSubs (cl:ClassName) ([]:ClassList) = (CC:ClassList) = []
GetSubs cl (c::cs) CC =
if cl = c.name
then unique (direct @ indirect)
else GetSupers cl cs CC
where direct = c.subclasses
and indirect = fold '@' (map (\x. GetSubs x CC CC) c.subclasses)
Example 2: (a) Defining new classes; (b) adding the new class to the heterarchy; (c) making new instances of classes where BuildRecord returns a record with field names identical to the SlotNames it is passed.
(a)
NewClass :: ClassName -> ClassList -> SlotList -> ClassList -> ClassList
NewClass (n:ClassName) (pl:ClassList) (sl:SlotsList) (C:ClassList) =
if IsClass n C
then NewClass n pl sl (remove n C)
else if fold and (map (\x. IsClass x C) pl)
then FixLinks n pl (n,pl,sl)::C
else error "superclass does not exist"
(b)
FixLinks :: ClassName -> ClassList -> ClassList -> ClassList
FixLinks (n:ClassName) ([]:ClassList) (CC:ClassList) = CC
FixLinks n (p::ps) CC = FixLinks n ps (Update n p CC)
Update :: ClassName -> ClassName -> ClassList -> ClassList
Update (n:ClassName) (p:ClassName) ([]:ClassList) = error
Update n p (c:cs) =
if p = c.name
then (c.name, c.sl, n::c.subclasses)::CS
else c::(Update n p cs)
(c)
Make :: ClassName -> ClassList -> Instance
Make (n:ClassName) (CL:ClassList) =
if IsClass n CL
then BuildRecord unique (localslots @ superslots)
else error "class not found
where localslots = GetSlots n CL
and superslots = fold '@' (map GetSlots (GetSupers n CL))
Table 1: Abstract syntax of Dylan classes, methods, and generic functions.
<I>Classlist</I> = <I>Class+</I>
<I>Class</I> = name:<I>ClassName</I>;sl:<I>SlotList</I>;subclasses:<I>ClassList</I>
<I>SlotList</I> = <I>EmptySlot</I>*
<I>ClassList</I> = <I>ClassName</I>+
<I>ClassName</I> = <I>Symbol</I>
<I>EmptySlot</I> = name:<I>SlotName</I>;pl:<I>ParamList</I>;body:<I>Expr</I>
<I>ParamList</I> = <I>Param</I>*
<I>Param</I> = name:<I>Symbol</I>;class:<I>ClassName</I>
<I>FunName</I> = Symbol
<I>Generic</I> = name:<I>GenName</I>;ml:<I>MethodList</I>
<I>MethodList</I> = <I>FunName</I>*
<I>GFList</I> = <I>Generic</I>*
<I>Instance</I> = name:<I>IName</I>;slots:<I>FullSlots</I>;class:<I>ClassName</I>
<I>FullSlots</I> = <I>FullSlot</I>*
<I>FullSlot</I> = name:<I>SlotName</I>;class:<I>ClassName</I>
<I>IName</I> = <I>Symbol</I>
<I>Key</I> = <I>Symbol</I>
Example 3: (a) IsGF returns True if n is a generic function; (b) AddMethod adds a new method to generic function n; (c) RemoveMethod and RMAux remove a method with parameters pl from a generic function n; (d) NewGF creates a new generic function, overriding any old methods that might be there; (e) RemoveGF removes a generic function n; (f) ApplyGF applys a generic function to an argument list.
(a)
IsGF :: FunNames -> GFList -> Boolean
IsGF (n:FunName) ([]:FGList) = False
IsGF n (g:gs) =
if n = g.name then True else IsGF n gs
(b)
AddMethod :: FunName -> ParamList -> Key -> GFList -> GFList
AddMethod (n:FunName) (pl:ParamList) (key:Key) ([]GFList) = []
AddMethod n pl key (g:gs) =
if n = g.name
then ((g.name),(pl.key)::(g.methods)) :: gs
else g :: AddMethod n pl key gs
(c)
RemoveMethod :: FunName -> ParamList -> GFList -> GFList
RemoveMethod (n:FunName) (pl:ParamList) ([]GFList) = error
RemoveMethod n pl key (g:gs) =
if n = g.name
then (g.name,(RMAux pl g.methods)) :: gs
else g :: RemoveMethod n pl key gs
RMAux :: ParamList -> MethodList -> MethodList
RMAux (n:ParamList) ([]:MethodList) = error
RMAux pl key (m:ms) =
if foreach i in pl (pl.i.type = m.pl.i.type)
then ms
else m :: RMAux pl ms
(d)
NewGF :: FunName -> GFList -> GFList
NewGF (n:FunName) (GF:GFList) =
if IsGF n GF
then NewGF n (RemoveGF n GF)
else (n,[]) :: GF
(e)
RemoveGF :: FunName -> GFList -> GFList
RemoveGF (n:FunName) ([]:GFList) = error
RemoveGF n (g:gs) =
if n = g.name then gs
else g:: RemoveGF n gs
(f)
ApplyGF :: FunName -> ParamList -> GFList -> Object
ApplyGF (n:FunName) (pl:ParamList) ([]:GFList) = error
ApplyGF n pl (g:gs) =
if n = g.name
then SchemeApply (SpecificMethod pl g.methods) pl
else ApplyGF n pl gs
Example 4: NewMethod creates a new method by modifying the Scheme environment and the generic function space.
NewMethod (n:FunName) (pl:ParamList) (l:Expr) (GF:GFList) (SE:Env) = let key = MkUniqueKey GF in if IsGF n GF then (AddMethod n pl key GF) , (bind key l SE) else NewMethod n pl l (AddMethod n [] Nil GF)
Example 5: Calculating the square root of a number using Newton's method.
(define-method newtons-sqrt (x)
(bind-methods ((sqrt1 (guess)
(if (close? guess)
guess
(sqrt1 (improve guess))))
(close? (guess)
(< (abs (- (* guess guess) x)) 0.0001))
(improve (guess)
(/ (+ guess (/ x guess)) 2)))
(sqrt1 1)))
Copyright © 1994, Dr. Dobb's Journal
