CSE 341: Programming Languages, Winter 2008 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
- 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
- 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.
A binding's scope is the portion of the program in which the binding
is in the context/environment.
- 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".
- 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.
- 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.
- 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.
- 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
- 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.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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
- 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 static (compile-time) check is
sound if it never accepts a program that does violate
the property being checked. Contrast completeness.
- 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
- 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