Programming Languages & Theory

internal fragmentation

allocated block larger than required

forward reference

an attempt to use a name before its declaration

dynamic scoping

bindings depend on flow of control at run-time

static scoping

bindings depend on text of program at compile-time

early binding time

bound before run time

shallow binding

choice made when reference finally used

deep binding

choice made when reference first created

binding lifetime

creation to destruction of a name-to-object association

elaboration

declarations become active when control first enters a scope

definition

describes object in sufficient detail for compiler to determine implementation

limited extent

destroyed at end of scope's execution

symbol table

dictionary mapping names to information the compiler knows about them

static

greater efficiency, compiler-based

late binding time

greater flexibility, interpreter-based

declaration

introduces a name and indicates its scope

information hiding

make objects and algorithms invisible to system portions that don't need them

first-class

passed as parameter, returned from subroutine, or assigned to variable

external fragmentation

space needed for request in multiple pieces

stack

storage region in which subblocks are allocated and deallocated in LIFO order

heap

storage region in which subblocks can be allocated and deallocated at arbitrary times

tail recursion

additional computation doesn't follow recursive call, so return value is what recursive call returns

nondeterminacy

allows the programmer to leave certain aspects of control flow deliberately unspecified

precedence

certain operators group more tightly by default than others

compound statement

delimited list of statements where a single statement is expected

normal-order evaluation

evaluating only when the value is actually needed

definite assignment

every possible control path to an expression must assign a value to every variable in that expression

enumeration-controlled

executed once for every value in a given finite set

statement

executed solely for side effects

logically controlled

executed until some Boolean condition changes value

speculation

executing a fragment of code optimistically, rolling back if needed

l-value

expressions that denote locations

r-value

expressions that denote values

initialization

give a value to a variable without a previous value

associativity

grouping direction for a sequence of equal-precedence operators

iterator

mechanism to loop through each element of a well-defined set

memoization

mechanism tracking which promises have already been evaluated

short-circuit

skips evaluation of second expression when overall Boolean value can be determined from first expression

goto

unstructured alternative to return, break, exit, exception

value model

variable is a named container for data

reference model

variable is a reference to a data object

strict name equivalence

aliased types considered distinct

loose name equivalence

aliased types considered equivalent

duck typing

an object has an acceptable type if it supports the requested method

universal reference type

arbitrary l-values can be assigned to this with no concern about type safety, but the compiler will not allow any operations to be performed on that object

conversion

changing a value of one type into a value of another

aggregate

composite literal

structural equivalence

consisting of the same components, put together in the same way

discrete

countable domain, well-defined notion of predecessor and successor

nonconverting type cast

interpret the bits of a value of one type as if they represented a value of some other type

type system

mechanism to define types and associate them with certain language constructs, and a set of rules for type equivalence, type compatibility, and type inference

coercion

performs a conversion automatically in certain contexts

strongly typed

prohibits the application of any operation to any object that is not intended to support that operation

abstraction-based view

regards types in terms of the operations they support

structural-based view

regards types in terms of their substructure

denotational-based view

regards types in terms of their values

enumeration

set of ordered named elements

ordinal value

small integer representing value of enumeration type

parametric polymorphism

taking a type (or set of types) as a parameter, either explicitly or implicitly

subrange

values compose a contiguous subset of some discrete base type's values

type clash

violation of the language's type compatibility rules

list comprehension

adapted from mathematical set notation; commonly with an expression, an enumerator, and one or more filters

persistent file

allows a program to read data that existed before the program began running, and to write data that will continue to exist after the program has ended

garbage

binding lifetime less than object lifetime

bit-vector representation

characteristic array; sometimes used to implement sets; doesn't work well for large base types

row-major

consecutive locations in memory hold elements that differ by one in the final subscript

column-major

consecutive locations in memory hold elements that differ by one in the initial subscript

conformant array

dynamic arrays as subroutine parameters, with shape fixed at subroutine call time

dope vector

holds shape information at run time

tracing collector

identifies useless blocks by recursively exploring all linked data in the program

reference count

keeps track of the number of pointers that refer to an object

dangling reference

object lifetime less than binding lifetime

packed

optimized for space instead of speed

smart pointer

program-level object (implemented on top of the language proper) that mimics the behavior of a pointer, but with additional semantics

slice

rectangular portion of an array

mark-and-sweep

recursively explores the heap, starting from external pointers, to determine what is useful

ragged array

rows with different lengths, without holes, enabled via row-pointer layout

stop-and-copy

technique performing storage compaction with overhead proportional to the number of nongarbage blocks

pointer reversal

technique used in heap exploration for garbage collection

generational collection

technique where garbage collector first examines the youngest region of the heap

temporary file

used for voluminous data within a single program run

closure

a reference to a subroutine, together with its referencing environment

caller

a subroutine performs its operation on behalf of this

display

allows access to objects in a scope k levels out in constant time

cactus stack

allows more than one coroutine to be declared in the same nonglobal scope, sharing access to objects in that scope

formal parameter

appears in the declaration of a subroutine; initialized by a variable or expression passed to the subroutine

prologue

code executed at the beginning of the subroutine itself

epilogue

code executed at the end of the subroutine itself

stack pointer

contains the address of either the last used location at the top of the stack, or the first unused location, depending on convention

context block

data structure representing a coroutine or thread

named

keyword-based correspondence between actual and formal parameters

static chain

maintained to access nonlocal variables in nested subroutines

leaf routine

makes no additional calls before returning

discrete event simulation

model naturally expressed in terms of interactions among various interesting objects that happen at specific times

default parameter

need not necessarily be provided by the caller; if missing, then a preestablished value will be used instead

positional

order-based correspondence between actual and formal parameters

control abstraction

principal purpose is to perform a well-defined operation

data abstraction

principal purpose is to represent information

frame pointer

register containing an address within the frame, used to access frame objects via displacement addressing

actual parameter

the caller passes this to influence subroutine's behavior, or provide it with data on which to operate

signal trampoline

used in typical implementation of spontaneous subroutine calls