programming languages final

Binding

The association between a name and the entity it refers to (value, type, memory location), occurring at a specific time.

Leftmost derivation

A derivation where the leftmost nonterminal is replaced at each step.

Rightmost derivation

A derivation where the rightmost nonterminal is replaced at each step.

Grammar (formal)

A set of terminals, nonterminals, productions, and a start symbol that defines a language.

Lexeme

A sequence of characters forming a meaningful unit (e.g., "while", "x", "==").

Token

A category of lexemes (e.g., IDENTIFIER, INTEGER_LITERAL).

Ambiguous grammar

A grammar that produces more than one parse tree for the same string.

Slice (array)

A subset of an array selected by indexing without copying the data.

Free union

A union with no tag/discriminant, making type checking impossible and unsafe.

Discriminated union

A union with an explicit tag indicating the active type, enabling type checking.

Strong typing

A language property where all type errors are guaranteed to be detected.

Coercion

Implicit conversion of a value from one type to another.

Name type equivalence

Two types are equivalent only if they share the same type name.

Structural type equivalence

Two types are equivalent if they have identical structure.

L-value

A memory location that can appear on the left side of an assignment.

R-value

The value stored at an L-value's memory location.

Activation record

The data structure that holds everything that a subprogram needs

A stack frame containing locals, parameters, return address, static link, and dynamic link.

Static link

An activation record instance for subprogram A points to one of the activation record instances of A's static parent

Dynamic link

points to the top of an instance of the activation record of the caller

Closure

a subprogram and the referencing the environment where it was defined

Tail recursion

A recursive call that is the final action in a function, enabling optimization.

Referential transparency

An expression can be replaced by its value without changing program behavior.

Critical section

A code region that must be executed atomically to avoid race conditions.

Semaphore

A synchronization primitive with atomic wait() and signal() operations.

Monitor

A structure combining shared data and procedures with enforced mutual exclusion.

Exception propagation

The process where an exception is passed up the call chain until handled.

Dangling pointer

A pointer that references memory that has been deallocated.

Memory leak

Heap memory that is allocated but no longer accessible.

Mark-sweep

A garbage collection algorithm that marks reachable objects and frees the rest.

Reference counting

Garbage collection where each object tracks how many references point to it.

Static scope

Scope determined by program structure; the nearest lexical block defines the variable.

Dynamic scope

Scope determined by the call chain at runtime.

Pass-by-value (in mode)

The callee receives a copy of the argument; caller cannot be modified.

Pass-by-reference (inout mode)

The callee receives a reference; changes affect the caller.

Pass-by-result (out mode)

Value copied in, and the result copied back out after the call.

Pass-by-name

Arguments are substituted as an expression and re-evaluated each time used.

Static typing

Types determined at compile time; safer and faster.

Dynamic typing

Types determined at runtime; flexible but less safe.

Row-major order

Array elements stored row-by-row (C, Java).

Column-major order

Array elements stored column-by-column (Fortran).

Pointer

A variable storing a memory address; supports dereferencing and arithmetic.

Reference

A safe, restricted pointer used for objects; no arithmetic allowed.

Race condition

Incorrect behavior caused by unsynchronized concurrent access.

Deadlock

Processes wait indefinitely due to circular waiting and resource holding.

Deadlock conditions

Mutual exclusion, hold and wait, no preemption, circular wait.

Pure function

A function with no side effects and referential transparency.

Higher-order function

one that either takes functions as parameters or yields a function as its result, or both

Lazy evaluation

Expressions evaluated only when needed.

List comprehension

A concise syntax for generating lists from an expression and iterator.

Why separate lexical & syntax analysis?

Simplicity (regex-based), efficiency, and reduced grammar complexity.

Why ambiguous grammars are bad

Multiple parse trees cause unclear interpretation and inconsistent meaning.

When arrays are best

When data is homogeneous and indexed numerically.

When records are best

When data is heterogeneous and accessed by name.

Writeability

The ease with which a programmer can write correct, clear code.

What improves writeability?

Simplicity, orthogonality, and expressiveness.

Dangling pointer example

A pointer still pointing to freed heap storage.

Memory leak example

Heap memory lost because no pointer references it.

Closure example

A function returning another function that uses outer variables.

Static link purpose

Allows access to nonlocal variables in statically enclosing scopes.

Dynamic link purpose

Restores caller's activation record during subprogram return.

Critical section requirements

Mutual exclusion, progress, bounded waiting.

Semaphore wait

Sets process to block if semaphore value < 0.

Semaphore signal

Increments semaphore and wakes one waiting process.

Monitor advantage

Provides automatic mutual exclusion and condition variables.

Deadlock prevention

Prevent any one of the Coffman conditions from holding.

Referential transparency example

Replacing x+5 with its evaluated value produces no change in behavior.

Exception advantage

Separates normal code from error handling; avoids error-return clutter.

Prolog unification example

[l,a,n,g,u,a,g,e] = [_,_,_,_|[H|T]] → H = g, T = [u,a,g,e]

Scala closure example

A lambda that captures the variable "factor" from its environment.

Futures example

The program prints asynchronously; output order depends on completion time.

Array descriptor

A structure describing an array's bounds, element size, and addressing.

Slice implementation

A referencing mechanism selecting part of an array without copying.

Union safety issue

Free unions allow mismatched types and runtime errors.

Static vs dynamic binding of types

Static: compile-time binding. Dynamic: runtime binding.

Shallow vs deep binding

Shallow: use environment at call time. Deep: use environment at definition time.

Message passing

A concurrency model where processes communicate by sending messages.

Monitors vs semaphores

Monitors are high-level and safer; semaphores are low-level and error-prone.

Functional programming features

Emphasizes immutability and pure functions.

Tail-call optimization benefit

Prevents stack growth in recursive calls.

Future

A placeholder for a value produced by an asynchronous computation. Allows a program to start work in the background and continue executing until the result is needed.

union type

type whose variables are

allowed to store different type values at

different times during execution

optional type

A type that can hold either a normal value or a special “no value” marker (like Some/None), providing safe handling of missing or undefined values.

type checking

ensuring that the operands of

an operator are of compatible types

control structure

a control statement and the statements whose execution it controls

subprogram

describes an interface and the actions to be performed.

actual parameter

argument represents a value or address used in the subprogram call statement

formal parameter

a dummy variable listed in the subprogram header and used in the subprogram

procedures

collection of statements that define parameterized computations (do a task) typicallyl does not return a value

functions

structurally resemble procedures but are semantically modeled on mathematical functions, always return a value

two types of subprograms

functions and procedures

overloaded subprogram

one that has the same name as another subprogram in the same referencing environment

generic subprogram

takes parameters of different types on different activations

coroutine

a subprogram that has multiple entries and controls them itself – supported directly in Lua

subprogram linkage

The subprogram call and return operations of a language are linked together

“simple” subprograms

subprograms can't be nested

all local variables are static

OOP three major features

ADTs

inheritance

polymorphism

dynamic binding

a runtime mechanism in which the method (or function) to be invoked is determined based on the dynamic type of the object.

allows polymorphism to work

concurrency

the ability of a computer to handle more than one task at the same time, but not necessarily doing them at the exact same instant.

physical concurrency

when multiple processors are used to execute concurrent units

logical concurrency

concurrent united are executed on a single processor