CS242: Vocabulary

Home Announce Handouts Slides Reading People Office Hours
 
activation record
Data structure created for each procedure call. It contains parameters, return address, return result address, local variables, and temporary storage.

alias
When two or more variables share the same location, or two or more pointers point to the same memory cell, they are aliases of each other. Essentially, it is one variable (pointer) but it is known under different names.

alpha-conversion
Renaming of bound variables in a lambda-term. For example, 
 lambda x. x + z
can be alpha-converted to 
 lambda y. y + z

beta-conversion 
 (lambda x. M) N = [ N / x ] M
Substitute N for every free occurrence of x in M, renaming bound variables of M as needed to avoid variable capture.

(beta) reduction
Modeling of program execution as directed beta-conversion. 
 (lambda x. M) N -> [ N / x ] M

bound and free variables
A bound variable is simply a place holder. The particular name of a bound variable is unimportant. For example, the functions 
 lambda x. x   and   lambda y. y
define exactly the same function (the identity function).

In contrast, the name of a free variable is important. Free variables cannot be renamed without potentially changing the value of an expression. For example, in the following code fragment (in which x appears as a free variable) , we cannot rename x to y without changing the value of the expression: 

 3 + x
(assume x is bound to 2 and y to 3).

class
A class defines the behavior of its instances. Usually the class contains definitions of all methods shared by its instances.

class template
In C++, templates are the mechanism for parameterizing a class with a type or a function. This allows the programmer to implement a class that operates on values of an arbitrary type (e.g., a general-purpose array class that may store elements of any type).

class variable
Class variables are shared by all instances of a class.

confluence
Property of lambda-calculus guaranteeing that if an expression has a normal form, the normal form is unique. This implies that the order in which reduction rules are applied is unimportant.

conformance
A relation between two types that serves as the basis of subtyping. Conformance relies on messages understood (i.e., the object's interface), not the internal representation or inheritance hierarchy.

constructor (in OOP sense)
A procedure that is used for creating and initializing objects. In C++, constructor is called after the object has been created and is used mainly to initialize the object's internal state.

dangling pointer
A pointer referring to an area of memory that has been deallocated. Dereferencing such a pointer usually produces garbage.

data type induction
A process of formal reasoning about properties of abstract data types.

denotational semantics
A technique of describing the ``meaning'' of programs as mathematical functions, allowing people to prove theorems and reason about programs as mathematical entities.

dynamic lookup
When a message is sent to an object at run-time, dynamic method lookup is performed to determine which method should be called.

dynamic scoping
The variable that is not defined in the current scope is looked for in the most recent activation record.

dynamic type checking
Checking for type errors when the program is executed.

encapsulation
Language mechanism for restricting access to some of the object's components.

exception
Exceptions are a control transfer mechanism, usually used to treat a special case or handle an error condition.

exception handler
When an exception-raising condition occurs, control is transferred to a special procedure called the exception handler.

fixed point
A fixed point of function f is a value x such that x = f(x)

funarg problem
The failure of traditional stack-based implementations of procedure calls in the presence of "first-class" functions (functions that can be passed as procedure parameters and returned as procedure results).

garbage
Memory allocated by a program that will not be accessed in any future execution of a given program.

garbage collection
An automatic process which attempts to free memory that is storing garbage.

Halting problem
The problem of determining whether a given program halts when executed on a given input.

higher-order function
Function that takes other functions as arguments or returns a function as its result.

implementation of an abstract type
Hidden internal representation of an abstract type.

inheritance
An object's definition may be given as an incremental modification to existing object definitions, in which case it is said that the object inherits from other objects.

instance variable
Local variable defined in each instance of the class. Instance variables of different instances are independent.

interface of an abstract type
Operations visible to the clients of an abstract type.

L-value
The L-value of variable x is the storage associated with x.

lambda calculus
Mathematical system for defining functions, proving equations between expressions, and calculating values of expressions.

lazy function
A lazy function only evaluates its arguments when it needs them. For example, a lazy implementation of OR will not evaluate its second argument if the first argument is true and thus the result can be determined without looking at the second argument. Compare with strict function.

mark and sweep garbage collection
A form of garbage collection that uses two phases: first, it marks all memory that can be possibly reached by the program from its current state; second, it frees (sweeps) all memory that has not been marked.

message
A name and a list of parameter values. Objects in Smalltalk communicate by sending messages to each other.

method
Code found in a class for responding to a message.

method dictionary
Method dictionary of a class contains all methods defined in the class.

multi-methods
In a language that uses multiple dispatch, more than one arguments to a message may be used to determine which method is called at run-time.

normal form
A lambda-term that cannot be reduced.

objects
Run-time entities that contain both data and operations.

overloading (ad-hoc polymorphism)
A function name is overloaded if it has two or more implementations associated with it. Different implementations are distinguished by type (e.g., function name "+" may have two implementations: one for adding integers, the other for adding real numbers).

parametric polymorphism
A function is parametrically polymorphic if it has one implementation that can be applied to arguments of different types.

pass-by-reference
Method of parameter passing: pass the L-value (address) of actual parameter. Allows to change the actual parameter.

pass-by-value
Method of parameter passing: pass the R-value (contents of address) of actual parameter. Does not allow to change the actual parameter.

private data
Private data can be accessed only by the methods of the class in which it is defined.

protected data
Protected data can be accessed by the methods of the class in which it is defined as well as by the subclasses.

public data
Public data can be accessed by the methods of the class in which it is defined, subclasses, and the clients.

R-value
The R-value of variable x is the contents of storage associated with x.

raising an exception
Raising an exception transfers control to an exception handler. Exception can be raised either implicitly if a certain condition occurs, or explicitly by executing an appropriate command.

representation independence
Property of a data type, according to which different computer representations of values of the data type do not affect behavior of any program that uses them (i.e., different underlying representations are indistinguishable by the type's clients).

selector
Name of a message.

static scoping
The variable that is not defined in the current scope is looked for in the closest lexically enclosing scope.

strict function
A function is strict if it always evaluates all of its arguments. Compare with lazy function.

subclass (derived class)
If class A inherits from class B, A is the subclass of B.

subtyping
A type A is a subtype of type B if any context expecting an expression of type B may take an expression of type A without introducing a type error.

superclass (base class)
If class A inherits from class B, B is the superclass of A.

static type checking
Checking for type errors at compile-time.

tail recursion
A function is tail recursive if it either All possible branches of the function must satisfy one of these conditions.

template (in Smalltalk)
Part of the object that stores pattern of instance variables.

type
A basic notion (like set in set theory). A type can also be described as a set of values defined by a type expression. The precise meaning of a type is provided by the type system, which includes type expressions, value expressions, rules for assigning types to expressions, and equations or evaluation rules for value expressions.

type error
A situation where execution of program is not faithful to the intended semantics, i.e., where the program interprets data in ways other than how it was intended to be used (e.g., machine representation of a floating point number interpreted as an integer).

type inferencing
Process of determining the type of an expression based on the known types of (some of) its subexpressions.

type tag
A tag attached to each value and containing information about its type. Used for dynamic type checking.

variable capture
This term is best explained by example. When an expression e is subtituted for a variable x in another expression lambda y.e', without any renaming of variables, then free occurences of y within e are "captured" (ie, bound) by the binding lambda y. For example, in 
 (lambda x.(lambda y. x))y = [y/x](lambda y. x) != lambda y. y
y should be free but accidentally becomes bound. To avoid variable capture, all bound variables should be renamed so that their names are different from those of all free variables and all other bound variables.

von Neumann bottleneck
Backus's term for the connection between CPU and main memory. Every computer program operating on the contents of main memory must send pieces of data back and forth through this connection, thus making it a bottleneck.

vtable
In C++, vtable is the virtual method table. It contains pointers to all virtual member functions defined in the class.

the Y combinator
When applied to a function, returns its fixed point. 
 Y = lambda f. (lambda x. f(xx))(lambda x. f(xx))

Last update: 10/18/97
Author: Vitaly Shmatikov