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 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. 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 is used.

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 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 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 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.