image University of Washington Computer Science & Engineering
  CSE 341Sp '06:  Dictionary
  CSE Home   About Us    Search    Contact Info 

Foreward: The material in 341 can often get obscured by a large amount of jargon, words with particular technical meaning that are unknown to most people. The purpose of this dictionary is to provide a repository for such words. While we will try to use words the same way they are generally used in computer science, there may be some discrepancy between what we mean and what other knowledgable people mean. This course is not about testing definitions; it is about communicately clearly and precisely.

This dictionary will grow and change as the course proceeds. Feedback on entries and/or the general usefulness of the dictionary is welcome.

abstract syntax
The abstract syntax of a programming language is the syntax without worrying about precedence (e.g., does x + y * z mean (x + y) * z) or x + (y * z)) or associativity (e.g., does x - y - z mean (x - y) - z or x - (y - z)). With abstract syntax, we just assume programs have enough parentheses to resolve these issues.

accumulator-style recursion
A recurisve function can take an argument (called the accumulator) that represents the "answer so far". Converting a recursive function to use an accumulator can sometimes make the function tail-recursive. In this conversion, the base case typically becomes the initial accumulator.

anonymous function
As the name suggests, an anonymous function is just a function without that doesn't have a name, that is, it is never bound to a variable in an environment. Because they do not have names, anonymous functions cannot be recursive.

A binding makes a bigger context/environment out of a smaller one by adding a variable (or variables). The bigger context/environment is used to typecheck/evaluate the expression in the binding's scope. The scope of a binding is part of a language's definition.

bounded quantification
A type system with bounded quantification allows types of the form (forall 'a<:t1. t2).

BNF (Backus-Naur Form) is a formal notation for describing the abstract syntax of a programming language. See lecture 8.

call-by-value, call-by-name, call-by-need
A language has call-by-value function application if function arguments are evaluated exactly once and bound to the function argument's variables prior to executing the function bodies. ML, Scheme, and Smalltalk all have call-by-value semantics, but thunking can simulate call-by-name. A language has call-by-name function application if function arguments are evaluated once every time (0, 1, or more times) the corresponding function-argument variable is evaluated in the function body. Call-by-need, or "lazy" evaluation is the "best of both worlds" semantics in which an argument is evaluated 0 or 1 times. It can be simulated with mutation and thunks.

call stack
A program's call stack holds the function calls that have not yet completed. Calling a function pushes a call onto the stack and evaluating a function body to a value pops a call from the stack. Although we may informally refer to a "function" on the stack, we really mean a "function call".

In class-based object-oriented languages, an object's class determines the objects behavior (i.e., how it responds to messages).

class method
In Smalltalk, an instance method of a class object is a class method. Class methods are like static methods in Java.

A static (compile-time) check is complete if it never rejects a program that does not violate the property being checked. Contrast soundness.

compound type
A compound type includes simpler types. Record types are one form of compound type. A non-compound type is a base type. Common examples include numbers and booleans.

An ML datatype constructor (often just called constructor) is two things: A function that creates values of the datatype and a form that can be used in pattern-matching to match against values built from the constructor.

A context is a map from variables to types. Type-checking a program uses a context to give types to variables. (Compare environment.)

contextual equivalence
Two expressions are contextually equivalent if we can replace one with the other anywhere in any program and get an equivalent program.

Function/method types are contravariant in their argument types, meaning t1->t2 is a subtype of t3->t2 if t1 is a supertype of t3.

Function/method types are covariant in their result types, meaning t1->t2 is a subtype of t1->t3 if t2 is a subtype of t3.

Currying is technique for simulating multiple-argument functions by having one-argument functions return functions that take the next argument. Partial application (calling a curried function with fewer arguments than the multiple-argument function it simulates) is a convenient way to produce functions.

Dynamic dispatch is the semantics of object-oriented message sends: The method invoked is chosen using the (run-time) class of the receiver object and that method's body is evaluated in an environment where self (a.k.a. this) is bound to the receiver.

dynamic scope
The semantics for a variable is "dynamic scope" if we look up the variable in the environment where the code containing the variable is called. In general "dynamic scope" refers to looking up things with respect to the current call-stack. ML uses dynamic scope for raising exception (transferring control to the nearest exception handler on the call-stack). See lexical scope.

An environment is a map from variables to values. Evaluating a program uses an environment to evaluate variables. (Compare context.)

Two programs are equivalent if they produce the same result and have the same effect. We typically ignore running time (i.e., not consider elapsed time an effect). Total equivalence means the two programs have the same termination behavior (they either both terminate or both do not). Partial equivalence means if both programs terminate, then they have the same result and effect.

extension (of a class)
A subclass extends a superclass when it adds fields or methods not present in the superclass.

fragile super-class (a.k.a. fragile base-class)
A class that has been subclassed and is subsequently modified.

free variable
A variable v is free in an expression e if evaluation of e requires an environment containing a binding for v. Specifically, A use of a variable in a function is "free" if it is not within a local-binding of the variable and it is not an argument to the function. (If the variable is not in the context, we cannot evaluate the variable. Otherwise, we need a closure to evaluate the variable when we apply the funtion.)

function closure
A function closure (or just closure) is a first-class value that can be applied to an argument. When applied (called), we evaluate the closure's function body in the environment where the function was defined (extended with the application's argument). You can think of a closure as a pair of code and environement, but the only way to "use" the pair is to apply it to an argument.

functional programming language
A functional language lets functions be first-class values and lets functions be defined within other functions. Most functional languages do not allow mutating variables in the environment. A pure functional programming language disallows all mutation.

hygienic macros
A macro system is hygienic if a macro's free variables are evaluated in the environment where the macros is defined and a macro use's free variables are evaluated in the environment where the macro is used.

If object obj has class C, then obj is an instance of C.

See dynamic-dispatch.

lexical scope
The semantics for a variable is "lexical scope" if we look up the variable in the environment where the code containing the variable was defined. In general "lexical scope" refers to looking up things with respect to their syntactic position in the program. ML uses lexial scope for variables. See dynamic scope.

A macro is a syntax transformer. Macro-expansion (performing the synactic transformation) creates the syntax that is actually evaluated.

Memoization is an idiom where a mutable table stores alreeady-computed results and evaluation consults the table to avoid repeating work. Memoization is inappropriate for non-functional code. It can make some algorithms much more efficient. Lazy (a.k.a. call-by-need) evaluation is a special case of memoization using thunks.

Sending a message to an object is a synonym for invoking a method on an object.

A module helps structure large programs by being a container for a collection of bindings. Module systems typically provide some combination of namespace management (giving different names to bindings in different modules), hiding (making bindings private to a module), and abstraction (restricting how bindings may be used outside a module).

Invoking a multimethod uses dynamic-dispatch on all its arguments, not just the receiver. Contrast static overloading.

multiple inheritance
Multiple inheritance allows a class to have more than one super-class.

Mutation of a variable imperatively changes the environment such that a variable maps to a different value. Mutation of a value changes one instance of a value to be a different value. Without mutation, structurally equivalent values are indistinguishable.

An object has private state and responds to messages.

overriding method
A subclass overrides a superclass's method when it replaces the method instead of inheriting it.

pattern, pattern-matching
"Algebraic" or "ML-style" pattern-matching is way to test and extract values from compound types. A pattern is not an expression even though it looks like one syntactically. The language semantics defines a notion of a pattern matching a value and how a successful match introduces environment bindings.
Note: "Regular-expression" pattern-matching is common in scripting languages and is a different concept.

parametric polymorphism
ML functions with type variables (types of the form 'a, 'b, ...) are polymorphic in the sense that they can be used for arguments and results of many (actually an infinite number) of types. The fact that all occurrences of a type variable must be instantiated with the same type makes this parametric polymorphism. In this class, polymorphism is short for parametric polymorphism, though in much of the world polymorphism is short for subtype polymorphism.

The object to which a message is sent is the receiver.

A record is a mapping from fields to values. Fields are just names: syntactically they may look like variables, but they are not variables nor are they even expressions.

A special object-oriented message send that invokes a different class's method. In Smalltalk and Java, the super keyword allows a resend to the receiver's class's superclass.

recursive function
A function is recursive if evaluating the body may include applying the function (presumably to different arguments).

See binding. (A scope is not a binding, but we define these terms together.)

A side-effect is a visible consequence of calling a function other than the function's return value. Side-effect sometimes refers only to mutating state or performing input/output, but a more general definition of "effect" includes raising exceptions or not terminating.

A signature is like a type for a module. It describes a module's contents. A module might match a signature, which is analogous to a value having a type. Other modules are type-checked, assuming a given module's signature.

A static (compile-time) check is sound if it never accepts a program that does violate the property being checked. Contrast completeness.

Giving an expression a super-type of another type the expression has.

subtype polymorphism
The fact that subsumption allows code to be used for many types.

super class
A (sub)class inherits fields and methods from its super class. A subclass can extend and override behavior.

static overloading
With static overloading, the "name" of a message-send or method includes the (compile-time) types of the arguments. When subsuming the arguments, there may be "no best match".

A stream is a data structure that behaves like an infinite list; a client can always ask for the next element. An elegant implementation of streams is a pair of an element and a thunk that returns a stream.

structurally equivalent
Informally, two values are structurally equivalent if any programs that read parts of the values get the same answers. Specifically, "object identity" does not determine structural equivalence: a tree and a directed acyclic graph could be structurally equivalent. Without mutation, structurally equivalent values are contextually equivalent.

tail-call, tail-position, tail-recursion
A tail-call is a function call appearing in a tail-position. A tail-position is a place where evaluation of the enclosing function body has "nothing more to do" after evaluating the expression at that position. A function is tail-recursive if all its calls to itself (or to functions that may cause itself to be called) are in tail-position.

A thunk is a function taking no arguments. The purpose of a thunk is to delay evaluation.

A value is an expression that is an "answer"; it cannot be further evaluated. What expressions are values is part of a language's definition.

virtual-method call
See dynamic-dispatch.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cary at]