Dubious with Predicate Dispatching (Güd)

User's Manual

Craig S. Kaplan (csk@cs.washington.edu)

Contents

  1. Introduction
  2. Getting Started
  3. Interaction with the Interpreter
  4. Built-in Names
  5. Abstract Syntax
  6. Examples
  7. Finding More Information

1. Introduction

This document introduces the implementation of Dubious With Predicate Dispatching, also known as Güd. Other documents give details about the underlying language Dubious and about predicate dispatching. This interpreter differs in several ways from those documents; see Section 7, Finding More Information, for details.

2. Getting Started

The distribution is available for download as ftp://ftp.cs.washington.edu/homes/chambers/gud-0.1.tar.gz. An online version of this manual is available at http://www.cs.washington.edu/research/projects/cecil/www/Gud/manual.html.

Güd is written in Java and requires a Java runtime which supports Java 1.1.1 or higher. The JavaSoft web site describes how to download a Java runtime. You must be able to run Java cleanly from the command line (as the program java). That may involve setting the PATH, CLASSPATH, and JAVA_HOME environment variables. See the Java documentation for more details.

Unzip and untar the Güd distribution ("%" is your command prompt):

% gunzip gud-0.1.tar.gz
% tar xf gud-0.1.tar
This produces a directory called gud-0.1 which contains all the files you'll need to run the interpreter.

To use the gud script, you must set the GUD_HOME environment variable to the location of the gud-0.1 directory. If you unpacked the archive into /home/fred/gud-0.1, you would execute something like

% setenv GUD_HOME /home/fred/gud-0.1
Now you are ready to run $GUD_HOME/gud. It will display a welcome message and a prompt ("-" is the Güd prompt), like
% $GUD_HOME/gud
This is Güd, version 1.0 (Thu Jul 9 1998)
Reading from "/home/fred/gud-0.1/prelude.gud"...
-
If you have difficulty or questions about installing or running Güd, please contact the authors and we will try to assist you.

3. Interaction with the Interpreter

This section demonstrates many of the features of the interpreter by way of a sample session. Text typed by the user appears in bold after the "-" prompt and should always end with a semicolon (;). Additional commentary appears on the right.

Part 1: Some simple values

- true;
val it = true 		true is bound at startup to a unique object in the system. Like most interpreters, this statement is a request to evaluate the expression and print the result.

For a complete listing of the built-in objects in the interpreter, see Section 4, Built-in Names.

- 568;
val it = 568 		Every integer literal is like a special predefined identifier bound to a unique object representing that integer value.
- 5.4;
File stdin: The identifier 5.4 is not bound. 		Floating point values are not currently supported.
- "Hello, World!";
val it = "Hello, World!" 		String literals are supported. Any special escape sequences inside string literals are not supported.

Part 2: Variables

- it;
val it = "Hello, World!" 		The result of the previous computation is always bound to the identifier it.
- def x = 19;
x = 19
- it;
val it = "Hello, World!" 		Bind the identifier x to the value 19. Like ML (and unlike Scheme), this definition hides any previous bindings to the identifier x, but does not destroy them. Earlier uses of x still refer to the previous binding.

A def statement does not change any existing binding to it.

Part 3: Method Invocations and Arithmetic

- toFormatted( 5 );
val it = "5" 		A simple example of a method invocation. toFormatted is a built-in function that returns a string representation of any object.
- 4 * 11 - 9 / (7 + 1) >= 99;
val it = false 		The usual arithmetic operators and their precedence relations are supported for integers. But these are all special cases of method invocations...
- operator "*"( 4, 11 );
val it = 44 		The operator keyword is special syntax. It causes the following string literal to be treated as an identifier. This allows you to refer to operators as values. You can use this to, e.g., add new cases to an operator.
- "Hello, " + "World!";
val it = "Hello, World!" 		The operator + is predefined on strings to do concatenation.
- toFormatted;
val it = toFormatted
- operator "+";
val it = + 		Methods are first-class objects in the system.

Part 4: Objects and Parents

- object;
val it = #[80cab32] 		The object keyword is an expression that constructs a fresh object in the system. Think of it as the expression new Object() in Java.

Because this new object has no specialized printed representation, the default is used, which is the object's hash code.

- object with parent number;
val it = #[80ca5fd] 		x with parent y clones x and adds an inheritance link from this clone to y. The value of the expression is the cloned object.

The inheritance links form the basis for predicate overriding.

- object with parent 6;
val it = #[80ca63e]
- object with parent operator "+";
val it = #[80ca690]
 Inheritance links can be established between any two non-locked objects (see below).
- 6 with parent true;
val it = 6; 		This expression returns a "new 6" which is also a child of true. Because with parent is side-effect free, this does not modify the "canonical" 6.
- operator "+" has parent true;
val it = + 		The has parent syntax is the destructive version of with parent. x has parent y adds an inheritance link from x to y and returns x.
- object with parent boolean with parent integer;
val it = #[80ca6a3] 		Multiple inheritance is supported.
- def inviolate = const object;
inviolate = #[1dc61295]
- inviolate has parent true;
File stdin: Can't add a parent to the locked object #[1dc61295].
- inviolate with parent true;
val it = #[1dc61342] 		constcreates a "locked" object which cannot be modified. However, the locked object can be cloned, and that copy can be modified.
- 6 has parent true;
File stdin: Can't add a parent to the locked object 6. 		Numbers are locked.

Part 5: Methods

- def f = object with method( b ) when b@true { 165 };
f = #[80ca5cb]
- f( true );
val it = 165 		with method is like with parent; it clones the source object and adds the given method case (or cases). This example creates a new object, clones it, and adds a new method case to the clone. The case takes a single argument. When the argument is equal to or a descendant of true, the method is applicable and the body executes, returning 165.
- f( false );
File stdin: #[80ca6ee] does not understand the arguments ( #[80c9de0] ): no applicable method 		f still has no applicable case for the argument false.
- f has method( b ) when b@false { -138 };
val it = #[80ca6ee]
- f( false );
val it = -138
- f( true );
val it = 165 		We can fix the above error by adding a case for false. The has method syntax is analogous to has parent. Note that this doesn't affect the b@true case.
- f has method( n@number ) { "number" };
val it = #[80ca6ee]
- f( 54 );
val it = "number" 		For convenience, class tests can be embedded inside the formal list of a method declaration.
- f has method( @150 ) { "special" };
val it = #[80ca6ee]
- f( 150 );
val it = "special"
- f( 149 );
val it = "number" 		For further convenience, the formal name can be omitted. This new case will dispatch on 150 or its descendants. Note that the previous case still applies to all other numbers.

For a complete description of the syntax for formals, see the abstract syntax.

- def op_and = object has method( a@boolean, b@boolean )
   when a@true and b@true { true }
   else { false };
op_and = #[80cb00d]
- op_and( true, false );
val it = false
- op_and( true, true );
val it = true 		This method declaration demonstrates several important features of the language:
  • Methods can have any number of arguments.
  • A with|has method expression can specify several method cases. Unlike ML, lexical order is irrelevant; the overriding/specificity ordering amongst the cases is determined through logical analysis of the predicates.
  • The extended formal syntax may be combined with predicates. The predicate implicitly given by the formal specifiers is distributed across all cases.
  • An optional else case catches all remaining arguments. else is a synonym for when true.
- defrec fact = object has method( n@number )
   when n@0 { 1 }
   else { n * fact( n - 1 ) };
fact = #[80cb487]
- fact( 5 );
val it = 120 		defrec is just like def, except that it makes the identifier being defined visible within (method bodies in) the initializing expression; this makes it easy to express recursion.
- method fact( n@number )
   when n@0 { 1 }
   else { n * fact( n - 1 ) };
fact = #[80cb7b9]
- fact( 6 );
val it = 720 		The method statement, which can be used only at the top level, defines an object of a given name and adds (recursive) method cases.
- def thunk7 = [ 3+4 ];
thunk7 = #[1dc61644]
- thunk7();
val it = 7 		This Smalltalk-like block [ expression ] is syntactic sugar for object with method() { expression }.

Part 6: Predicates

- method f( a )
   when a@=number { "`number' itself" }
   when a@number { "Any old number" }
   else { "The base case" };
f = #[80cbc5d]
- f( true );
val it = "The base case"
- f( 15 );
val it = "Any old number"
- f( number );
val it = "`number' itself" 		The two main class test predicates are given by the operators @ and @=. a@b holds if a is b or a descendant of b. a@=b holds only when a and b are identical.
- f has method( n@number )
   when test n % 7 == 0 { "multiple of 7" };
val it = #[80cd12e]
- f( 15 );
val it = "Any old number"
- f( 14 );
val it = "multiple of 7" 		To evaluate an arbitrary program expression, use the test base predicate. The expression must evaluate to true or false. All other values produce a runtime error.
- method g( m@number, n@number )
   when let sum := m + n and
    test sum % 7 == 0 { "yes: " + toFormatted( sum ) }
   else { "no" };
g = #[80cd7e6]
- g( 4, 16 );
val it = "no"
- g( 4, 17 );
val it = "yes: 21" 		A let base predicate binds an identifier to a value (possibly computed in terms of the method's formals). The bound identifier acts as a "pseudo-formal": further predicate testing is possible on it, and the binding is exported into the body of the method case.
- def blah = object;
blah = #[80ca581]
- method h( a )
   when a@number and not a@=number or a@=blah { true }
   else { false };
h = #[80ca6b7]
- h( integer );
val it = true
- h( blah );
val it = true
- h( number );
val it = false 		Any combination of the connectives and, or and not (and having higher precedence than or) is possible within a predicate.
- predicate even( n@number )
   when test n % 2 == 0;
even = n<38> @ number and test #[80c9f81]( #[80ca219]( n<38>, 2 ), 0 ) 		The predicate keyword constructs a predicate abstraction.
- method f( n )
   when even( n ) { true }
   else { false };
- f( 5 );
val it = false
- f( 6 );
val it = true 		This method uses a call to the even predicate abstraction defined above. Since the abstraction doesn't return any values, the call doesn't bind any pseudo-formals.
- method f( n ) when n@even { true }
   else { false };
f = #[80caa4d]
- f( 5 );
val it = false
- f( 6 );
val it = true 		A single value may be tested against a predicate abstraction using a syntax similar to that of class tests.
- predicate even2(n@number)
   when test n%2==0
   return (n/2);
even2 = n<44> @ number and test #[1dc60976]( #[1dc60c12]( n<44>, 2 ), 0 )
- method f(n)
   when even2( n ) => (h) { h }
   else { false };
f = #[1dc620df]
- f(22);
val it = 11
- f(3);
val it = false 		A predicate abstraction may return an array-like collection of values; those values may be bound to variables at the abstraction invocation site.

4. Built-in Names

This section lists the objects which are either built-in to the system or provided by the standard prelude.

Built-in to the Interpreter

def tao = object; A default object. tao denotes a meaningless value, like the unit object () in ML.
def boolean = object;
def true = object has parent boolean;
def false = object has parent boolean; 		The boolean type and its children (instances) true and false.
def string = object; The parent of all string literals.
def number = object;
def integer = object has parent number;
def 0 = object has parent integer;
def 1 = object has parent integer;
def 2 = object has parent integer;
def -1 = object has parent integer;
... 		The numeric types and integer literals.
+, -, *, /
==, !=, <, >, <=, >= 		The standard arithmetic and relational operators. The - operator supports both subtraction and unary negation.
method exit( n@integer ) {
   ...
} 		Exit with status n.
method load( s@string ) {
   ...
} 		When the argument is a file name, load that file name and execute it as a sequence of Güd statements. When the argument is a Java class name, load the class and call its initialization method.
def __name__ = ...;
def __author__ = ...;
def __version__ = ...;
def __date__ = ...; 		Some built-in objects that describe the interpreter.
method printString( s@string ) {
   ...
}
method newline() {
   ...
} 		printString prints an arbitrary string to the console. newline prints a newline to the console.
method toRaw( o ) {
   ...
}
method toFormatted( o ) {
   toRaw( o )
} 		Build printable representations of objects. toRaw constructs a representation that it used when printing the result of a computation. toFormatted is the representation used when explicitly printing an object. The default behaviour for toFormatted is to call toRaw.
method pp( o ) {
   ...
} 		Pretty-print the object o. This method doesn't work particularly well.
method debugPredicates( b@boolean ) {
   ...
} 		Turn the debugging of predicates on or off. When predicate debugging is on, adding a case to a method produces debugging information about static predicate comparison.

Defined in prelude.gud

method eq( a, b ) {
   ...
} 		A function that uses @= style dispatching to determine whether two objects are identical. This is pointer/object equivalence, not structural equivalence.
&&, ||, ! Boolean conjunction, disjunction, and negation. Although the syntax for these operators is built-in to the interpreter, their definitions are in the standard prelude.
method if( b@boolean, thunk1, thunk2 ) { ... } The if method invokes one of the two thunks, depending on whether the first argument is true. A two-argument version is also available.
method compose( f, g ) {
   ...
} 		Compose takes f and g, both methods of a single variable, and returns h such that h(x) = f(g(x)) for all x.
method print( x ) {
   ...
}
method println( x ) {
   ...
} 		These methods combine toFormatted and printString to do formatted output of arbitrary objects to the console. println is just like print except that it appends a newline.
list, nil, cons,
car, cdr,
foreach, map, reduce 		The usual list data definitions and operations. For more information, look at the comments inside prelude.gud.

5. Abstract Syntax

This section presents an abstract syntax for the Güd language. Details such as precedence and associativity are taken to be understood by the reader.

First, here's the metasyntax, the notation that will be used to present the abstract syntax:

expr, statement
Italic text represents non-terminals in the language.
when, let
Bold text in code font represents tokens in the language, which must be typed exactly as given.
[]
Square brackets denote an optional item.
{}
Curly braces denote zero or more repetitions of an item.
ID, STRLIT, INTLIT
Capitalized words represent general classes of identifiers.

And now, the complete abstract syntax for the language.

program ::= { statement ; }
statement
::= expression
  |   def ID = expression
  |   defrec ID = expression
  |   method ID cases
  |   predabs
predabs
::= predicate ID formals when predicate
  |   predicate ID formals when predicate return ()
  |   predicate ID formals when predicate return ( expression { , expression } )
expression
::= object
  |   ID
  |   STRLIT
  |   INTLIT

  |   ( expression )
  |   { expression { ; expression } }
  |   let ID = expression { , ID = expression } in expression end
  |   let* ID = expression { , ID = expression } in expression end

  |   expression()
  |   expression( expression { , expression } )

  |   expression with parent expression
  |   expression has parent expression
  |   expression with method cases
  |   expression has method cases

  |   -expression
  |   expression + expression
  |   expression - expression
  |   expression * expression
  |   expression / expression
  |   expression % expression
  |   expression == expression
  |   expression != expression
  |   expression < expression
  |   expression > expression
  |   expression <= expression
  |   expression >= expression
  |   expression && expression
  |   expression || expression
  |   ! expression

  |   const expression
  |   [ expression ]
cases
::= formals body
  |   formals caselist
formals
::= ()
  |   ( formal { , formal } )
formal
::= _
  |   ID
  |   @ expression
  |   ID @ expression
  |   @= expression
  |   ID @= expression
body
::= { expression { ; expression } }
caselist
::= when predicate body { when predicate body } [ else body ]
predicate
::= expression @ expression
  |   expression @= expression
  |   test expression
  |   let ID := expression
  |   ID( [ expression { , expression } ] ) [ => ( { ID } ) ]

  |   ( predicate )

  |   not predicate
  |   predicate and predicate
  |   predicate or predicate

6. Examples

To get more exposure to predicate dispatching, we have provided a small set of examples. We hope to expand this set in the future and welcome your contributions.

The examples come in two varieties: Güd input files and Java files. The Güd files are read directly by the interpreter. Use the load method, passing as an argument the path to the file:

% gud
This is Güd, version 1.0 (Thu Jul 9 1998)
Reading from "/home/fred/gud-0.1/prelude.gud"
- load( "/home/fred/gud-0.1/examples/goldbach.gud" );
Loading /home/fred/gud-0.1/examples/goldbach.gud
val it = true

The Java files can be linked in to the interpreter using an experimental dynamic linking facility. To compile the example Java files, make sure that your CLASSPATH variable contains at least $GUD_HOME and $GUD_HOME/gud.jar:

% cd $GUD_HOME/examples
% setenv CLASSPATH $GUD_HOME/gud.jar:$GUD_HOME
% javac test.java

Then, to install them into a running interpreter, use the load method, passing in the class name:

% $GUD_HOME/gud
This is Güd, version 1.0 (Thu Jul 9 1998)
Reading from "/home/fred/gud-0.1/prelude.gud"
- load( "examples.test" );
val it = true

If you would like more information about linking in native Java code, contact the authors.

7. Finding More Information

How to Contact Us
If you discover a bug in the implementation of Güd, please contact either Craig S. Kaplan or Michael Ernst.

Differences from Other Documents
The implementation supports most of the mechanisms presented in Predicate Dispatching: A Unified Theory of Dispatch, but only a subset of the syntactic sugars. Nevertheless, it is a good vehicle for exploring the usefulness and expressiveness of predicate dispatching.

Implementation details
Güd consists of approximately 6000 lines of Java. It relies on JLex and JavaCUP for lexical analysis and parsing (but users need not install those packages in order to run Güd).

References
Predicate Dispatching: A Unified Theory of Dispatch
by Michael D. Ernst, Craig Kaplan, and Craig Chambers
Published in ECOOP '98, the 12th European Conference on Object-Oriented Programming, Brussels, Belgium, July 20-24, 1998, pp. 186-211.

Dubious: A Modular, Statically Typed OO Core Language
by Todd D. Millstein
Ph.D. Qualifying Exam project report, Department of Computer Science and Engineering, University of Washington, January 1998.