Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
69 Cards in this Set
- Front
- Back
|
language
|
A language is a means to communicate information.
|
|
|
syntax (Ch. 1)
|
The structure of a language is called its syntax.
|
|
|
semantics
|
The rules that define the meaning of a language are called semantics.
|
|
|
metaprogram
|
A metaprogram is any program whose input or output is a program.
|
|
|
expression (Ch. 1)
|
An expression is a syntactic category for syntax that produces a value, and possibly has other side effects.
|
|
|
statement
|
A statement is a syntactic category for syntax that has a side effect rather than producing a value.
|
|
|
side effect
|
A side effect is an effect on the program state. Examples of side effects include allocating memory, assigning to memory, input/output, or exceptions.
|
|
|
expression (Ch. 2)
|
An expression is a combination of variables, values and operations over these values. For example, the arithmetic expression 2+3 uses two numeric values 2 and 3 and an operation + that operates on numeric values.
|
|
|
syntax (Ch. 2)
|
The syntax of an expression prescribes how the various components of the expressions can be combined. In general it is not the case that the components of expressions can be combined arbitrarily: they must obey certain rules. For example 2 3 or + + are not valid arithmetic expressions.
|
|
|
abstract syntax
|
The conceptual structure is called the abstract syntax of the language.
|
|
|
concrete syntax
|
The particular details and rules for writing expressions as strings of characters is called the concrete syntax.
|
|
|
evaluation
|
Each expression has a meaning (or value), which is defined by the evaluation of that expression. Evaluation is a process where expressions composed of various components get simplified until eventually we get a value. For example evaluating 2 + 3 results in 5.
|
|
|
parser
|
A parser is a program that converts concrete syntax into abstract syntax. A parser typically inputs text and outputs the abstract syntax structure.
|
|
|
literal
|
A literal is a constant value that appears in a program. A literal can be a number, string, boolean, or other constant.
|
|
|
token
|
A token is the basic syntactic unit of a language. Tokens can be individual characters, or groups of characters. Token are often classified into kinds, for example integers, strings, identifiers.
|
|
|
identifier
|
An identifier is a string of characters that represents a name. Identifiers usually begin with an alphabetic character, then continue with one or more numeric digits or special symbols. Special symbols that may be used include underscore “_" and “$”, but others may be included.
|
|
|
grammar
|
A grammar is a set of rules that specify how tokens can be placed together to form valid expressions of a language.
|
|
|
syntactic category
|
The parts of a language are called syntactic categories. For example, in English there are many different parts, including verb, noun, gerund, prepositional phrase, declarative sentence, etc. In software languages, example syntactic categories include expressions, terms, functions, types, or classes.
|
|
|
production rule
|
A production rule defines how a non-terminal can be translated into a sequence of tokens and other syntactic categories.
|
|
|
terminal
|
A terminal is a token used in a grammar rule.
|
|
|
non-terminal
|
The non-terminals are the names of syntactic categories used in a grammar.
|
|
|
precedence
|
Precedence is an order on grammar rules that defines which rule should apply first in cases of ambiguity. Precedence rules are applied before associativity rules.
|
|
|
associativity
|
Associativity specifies whether binary operators are grouped from the left or the right in order to resolve ambiguity.
|
|
|
variable
|
A variable is a symbol that refers to a value.
|
|
|
binding
|
A binding is an association of a variable with its value.
|
|
|
mutation
|
Mutation refers to the ability of a variable or data structure to change over time.
|
|
|
environment
|
An environment is a mapping from variables to values.
|
|
|
unbound variable
|
An unbound variable is a variable that does not have a binding. Unbound variables are a common form of errors in programs.
|
|
|
scope
|
The scope of a variable is the portion of the text of a program in which a variable is defined.
|
|
|
static
|
A static property of a program can be determined by examining the text of the program but without executing or evaluating it.
|
|
|
dynamic
|
A dynamic property of a program can only be determined by evaluating the program.
|
|
|
first-class values
|
A first-class value is a value that can be used like any other value. A value is first class if it can be passed to functions, returned from functions, and stored in a variable binding.
|
|
|
lambda or function expression
|
A lambda expression is an expression that creates a function. The general form of a function expression is: λvariable. body
|
|
|
juxtaposition
|
Placing two expressions next to each other, such as in a function call: f(3) or f n
|
|
|
currying
|
The process of converting from a function taking a tuple to a chain of functions that take one argument at a time is called currying.
|
|
|
uncurrying
|
The process of converting from a chain of functions that take one argument at a time into a function that takes a single tuple argument is called uncurrying.
|
|
|
Church Boolean
|
A Church Boolean is a encoding of a boolean value as a function of two arguments, which returns the first argument for true, and the second argument for false.
|
|
|
lexical scope
|
Lexical scope means that a variable refers to the closest enclosing definition of that variable. (This is related to those scope ‘holes’ he kept bringing up in environment diagram discussions.)
|
|
|
dynamic binding
|
dynamic binding occurs when a symbol’s value is found by scanning the dynamic calls for the most recent binding of the symbol.
|
|
|
closure
|
A closure is a combination of a function expression and an environment.
|
|
|
call-by-value
|
In call-by-value interpretation, expressions, such as parameters of functions arguments or variable initialisers, are always evaluated before being added to the environment.
|
|
|
call-by-name
|
In call-by-name, an expression is not evaluated until it is needed.
|
|
|
call-by-need
|
In call-by-need, when the use of a variable forces the evaluation of an expression, the result of that evaluation is cached and next time the variable is needed the cached value is simply returned.
|
|
|
recursive function
|
A recursive function is a function that calls itself within its own definition.
|
|
|
infinite structure
|
An infinite structure is a structure that is conceptually infinite, but cannot be represented explicitly in its entirety.
|
|
|
fixed point
|
A fixed point of a function f is a value x where x = f(x).
|
|
|
generator
|
A function that is passed as an argument to the fixed-point function, with the intent of creating an infinite value.
|
|
|
self application
|
Self application is when a function is applied to itself.
|
|
|
diverge
|
A function diverges if it doesn’t return a value.
|
|
|
mutable state
|
Mutable state means that the state of a program changes or mutates: that a variable can be assigned a new value or a part of a data structure can be modified.
|
|
|
address
|
An address identifies a mutable container that stores a single value, but whose contents can change over time. Addresses are sometimes called locations.
|
|
|
dereferencing
|
A address is dereferenced when the contents of the cell associated with the address is looked up and returned.
|
|
|
memory
|
Memory is a map or association of addresses to values.
|
|
|
stateful computation
|
A stateful computation is represented functionally as a function that takes an initial state and returns a value and an updated state.
|
|
|
higher-order function
|
A function which takes a function as input or which returns a function as a result.
|
|
|
Checked
|
(>>=) :: Checked Value -> (Value -> Checked Value) -> Checked Value
|
|
|
Stateful
|
(>>=) :: Stateful Value -> (Value -> Stateful Value) -> Stateful Value
|
|
|
monad
|
A monad m is a computational structure that involves three parts: 1) A generic data type m, 2) A return function: return :: t -> m t, 3) A bind function: (>>=) :: m t -> (t -> m s) -> m s
|
|
|
return
|
The return function specifies how values are converted into m-computations.
|
|
|
bind
|
The bind function >>= specifies how m-computations are combined together.
|
|
|
type class
|
A type class is a Haskell mechanism for overloading functions based on their type.
|
|
|
abstract value
|
An abstract value is a value that represents a collection of concrete values.
|
|
|
concrete interpreter
|
A concrete interpreter is a normal interpreter that evaluates with normal values.
|
|
|
abstract interpreter
|
An abstract interpreter is an interpreter that operates over abstract values using abstract operations.
|
|
|
validity
|
An abstract interpreter is valid if the concrete value result is a member of the set of values of the abstract value evaluation result, for all evaluations.
|
|
|
type environment
|
A type environment is a mapping from variable names to types.
|
|
|
abstract data type
|
An abstract data type (ADT) has a public name, a hidden representation, and operations to create, combine, and observe values of the abstraction. In other words, an abstract data type is a structure that implements a new type by hiding the representation of the type and supplying operations to manipulate its values.
|
|
|
algebra
|
An algebra is comprised of a collection of abstract values (the “sort”) and operations to manipulate those values.
|
|
|
characteristic function
|
The characteristic function for a set maps a domain of values to a Boolean value, which indicates whether or not the value is included in the set.
|
