Glossary (Programming Languages)

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search
Abstract (v.)
To determine the function value denoted by a lambda expression.
Abstract data type
A data type supporting specified operations whose representation is hidden.
Abstract syntax
A representation of the structure of an expression or program as a tree, or the data type of trees used to represent the structure of expressions or programs in a particular language.
Actual parameter
An expression that appears in a function call and determines the value of one of the function's arguments.
To determine the value of a function for specified arguments.
A value that is passed to a function when it is called.
A representation of a function in which the body of the function is paired with the environment that is used in evaluating calls to the function.
Concrete syntax
The set of valid expressions or programs in a language, considered as strings of characters.
A function that is passed as an argument to another function and captures the entire future of the execution.
Continuation-passing style (CPS)
In CPS, each serious function in a program receives a continuation as an argument, and invokes the continuation instead of returning in the usual way. This makes it possible for function calls to occur only in tail position. By adopting CPS, programs can be written in such a way that their meaning is independent of the evaluation strategy of the language in which they are written.
Curried function
A function that accepts multiple arguments through the device of accepting the arguments one at a time, and in each case but the last, returning a function that expects the remaining arguments. Thus a function f:: (α, β, γ) → δ of three arguments that would be called with f(x, y, z) is replaced by a function f:: α → (β → (γ → δ)) called with ((f x) y) z. The prevailing style in Haskell is to define all multi-argument functions in curried form; Haskell's syntactic conventions make it possible to omit the parentheses both in the type of f shown here and the application f x y z.
Defunctionalization (d17n)
A whole-program transformation that replaces higher-order functions with functions that accept concrete data structures.
Dynamic binding
A rule for binding variables that associates each use of a variable with its most recent definition, instead of the definition that is textually closest.
To determine the environment that is established by a declaration.
A data structure that represents a mapping from identifiers to the values they denote.
To determine the value of an expression.
Formal parameter
An identifier that is bound to an argument of a function during evaluation of its body.
Higher-order function
In a functional programming language, a function that either accepts another function as an argument or returns another function as its result. The standard function map is an example of a function that accepts another function as an argument, while the composition operator (.) both accepts functions as arguments and delivers a function as its result. (Strictly speaking, all curried functions are higher-order, though we do not treat them as such unless they are defined by equations where the left-hand sides do not match all arguments, or they are used in a context where not all arguments are supplied.)
A program (written in a metalanguage) that inputs another program (written in the object language) and outputs the results of that program.
Lambda expression
A form of expression that denotes a function. For example, in Haskell, the expression (λ xx * x) denotes the function that delivers the square of its argument.
The language in which an interpreter is written.
A data type that represents some concept of computational effect, memory access, failure or nondeterminism, together with operations that implement the null effect and sequencing of effects.
A function that maps strings in the source language to theirabstract syntax trees.
A function that is not written in the object language, but provided as part of the initial environment. Example: + is a primitive of Fun.
Syntactic sugar
A language feature that provides a more convenient notation for effects that can be achieved in other ways. Example: in Fun,
val f(x) = x + 1
is syntactic sugar for
val f = lambda (x) x + 1
Tail position
In the body of a function, a context in which the value of a sub-expression immediately becomes the value returned by the function.
In a parser, an atomic unit from the source text, such as an identifier, a keyword, or a punctuation character.