CSE 341: Programming Languages, Fall 2004, Course Dictionary
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.
- binding
- 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
- 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".
- class
- 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.
- completeness
- 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.
- constructor
- 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.
- context
- 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.
- contravariant
- 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.
- covariant
- 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
- 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
- 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.
- environment
- An environment is a map from variables to values. Evaluating a
program uses an environment to evaluate variables. (Compare context.)
- equivalent
- 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.
- instance
- If object obj has class C, then obj is an instance of C.
- late-binding
- 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.
- macro
- A macro is a syntax transformer.
Macro-expansion (performing the synactic transformation) creates the
syntax that is actually evaluated.
- memoization
- 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.
- message
- Sending a message to an object is a synonym for invoking a method
on an object.
- module
- 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).
- multimethod
- 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
- 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.
- object
- 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.
- receiver
- The object to which a message is sent is the receiver.
- record
- 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.
- resend
- 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).
- scope
- See binding. (A scope is not a binding, but we define these
terms together.)
- side-effect
- 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.
- signature
- 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.
- soundness
- A static (compile-time) check is
sound if it never accepts a program that does violate
the property being checked. Contrast completeness.
- subsumption
- 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".
- stream
- 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.
- thunk
- A thunk is a function taking no arguments. The purpose of a thunk
is to delay evaluation.
- value
- 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.