** abstract syntax tree (AST):** a tree representation of a program
that is abstracted from the details of a particular programming
language and its surface syntax.

** alist** association list

** ambiguity** in understanding natural language, the
possibility of interpreting an input in more than one way.

** anaphora** (singular is * anaphor*)
words that refer to other words in a sentence, such as pronouns.

** association list**
in Lisp, a list composed of pairs of a symbolic name and associated value,
used to represent variable bindings, substitutions, and data sets.
** atom**
** 1.** in propositional or predicate calculus, a predicate symbol with
the appropriate number of arguments. For example, MORTAL(Socrates) is an
atom, where MORTAL is the predicate and Socrates is a constant term that is
its argument. Also, atomic formula.
** 2.** in Lisp, data that is not a ` cons` cell, such as a symbol
or a number.

** augmented transition network (ATN)**
a formalism for describing parsers, especially for natural language.
Similar to a finite automaton, but augmented in that arbitrary tests may be
attached to transition arcs, subgrammars may be called recursively, and
structure-building actions may be executed as an arc is traversed.

**backquote** in Lisp, a backward-quote character macro that quotes
everything inside a list, except items that are unquoted with a comma.

** backward chaining**
a proof that starts with the conclusion and searches for rules or
facts that support the conclusions, recursively.

**backtrack:** in a tree search, to move back from the node currently
being examined to its parent.

**base case:** a simple case that can be solved easily, without
recursion.

**Bayes' Theorem** P(A|B) = P(B|A) * P(A) / P(B)

**Bayesian network** representation of a joint probability distribution
by a network whose nodes are small partial distributions

**binary tree:** a tree in which each node has at most two children.

**binary search:** search of a binary tree or other structure,
in which the size of the set to be searched is cut in half at each step.

**binary search tree (BST):** a binary tree in which all elements
less than the current element are to its left and all elements
greater are to its right.

**binding:** an association of a name with a value.
** box**
in logic or resolution theorem proving, the empty clause; from its
mathematical symbol, &box;

** branching factor**
in a search tree, the number of children of a given node.
Usually, the branching factors of individual nodes will vary.

** certainty factor**
a numeric measure of the degree of belief in a proposition.
In EMYCIN, the CF ranges from -1 (false) to 1 (true).

**chain rule ** P(A ∧ B) = P(A|B) * P(B) and so on for longer chains

** Chomsky hierarchy**
a hierarchy of language types defined by Chomsky: Type 0 (no restrictions)
is the highest class, containing Type 1 (context sensitive), Type 2
(context free), and Type 3 (regular).

** combinatoric explosion**
the rapid growth of the number of possibilities to be explored in
a search, often exponential because it is the product of the number of
possible choices at each level of the search tree.

** combine** an operator that is used to combine elements in an accumulation

** conjunctive normal form (CNF)**
a canonical form of writing predicate calculus formulas as a conjunction (AND)
of clauses (disjunction (OR) of literals); used in resolution theorem proving.

** consistent** of a logical formula, having some interpretation that
makes it true.

** constant folding:** performing at compile time an operation whose
operands are constant, giving a new constant result.

** constructive proof** proving that a formula is consistent by constructing
an element that makes it true.

** decidable**
of a theorem proving or decision making task, able to be decided one
way or the other (e.g., proved or disproved) within a finite time bound
that can be determined from the size of the input problem.
* cf.* undecidable.

**deductive composition** proving a goal by constructing an element
(such as a composition of subroutines) that satisfies the goal

** depth** depth of a tree in number of links below the root.

** depth-first search**
a search in which children of a node are considered (recursively)
before siblings are considered.

**design pattern:** a pattern that describes a set of similar
programs.

**destructive:** describes a function that modifies its arguments.

**DFS** depth-first search.

**domain theory** logical formulas that express axioms about an
application domain

** ELIZA**
a program by Joseph Weizenbaum that simulated a Rogerian psychotherapist.

**eval** Lisp / Clojure function that evaluates an expression.

**exists** the logical quantifier ∃, pronounced "there exists"
or "for some".

**fixpoint** a value of a function where f(x) = x, i.e. applying a
function such as optimization to an expression no longer can do any more.

**for all** the logical quantifier ∀, describing something
that is true for all possible values of the quantified variable.

**functional program** a program in which all computation is performed
by functions and there are no side-effects.

** grammar:**
a formal specification of a language, consisting of a set of nonterminal
symbols, a set of terminal symbols or words, and production rules that specify
transformations of strings containing nonterminals into other strings.

**grammatical ambiguity** ambiguity due to the fact that a grammar
allows a sentence to be parsed in more than one way.

** ground literal**
a logical predicate containing no variables, or in which constants or
functions of constants have been substituted for all variables: Even(4)

**hidden Markov model** a model in which there is a graph of states
with probabilistic transitions between states, in which the state that
the system is in cannot be observed directly.

**homoiconic** describes a language such as Lisp where programs and data
are the same.

**Horn clause** a logical formula that is a disjunction (OR) of
literals and has at most one
positive literal. Viewed as a rule, a Horn clause is a rule from a
conjunction (AND) of positive literals to a single positive conclusion
literal, e.g. A ∧ B ∧ C → D

**identity element** for a given operation, an element that leaves
the value unchanged. E.g., for + the identity element is 0.

**immutable** a data structure whose value cannot be changed
once it is created.

**inconsistent** a logical formula that is contradictory or unsatisfiable

**inference** derivation of additional true statements from a given
set of true statements.

**interpretation** an assignment of values to variables in a logical
statement

**in-line** to expand a function as code at the point of call

**interior node** a node of a tree that has children

**interpreter** a program that reads an instruction, determines its
meaning, and executes it. Lisp has an interpreter (eval) that can
execute code constructed at runtime.

**invalid** not valid, i.e. not always true or possibly false

**leaf** a bottom node of a tree

** lexical ambiguity **
in natural language, ambiguity caused by multiple definitions or
parts of speech of words.

** lexicon **
in a natural language processing system, a table of words with their
parts of speech, root words, relationships to other words or phrases,
semantic features, definitions in machine-processable form, etc.

**linked list** a linear data structure where records are linked by pointers

**literal** a logical predicate or its negation: P or ¬P

**loop unrolling:** conversion of a loop into straight-line code by
repetition of the code inside the loop with successive values of the loop
index substituted into the code.

** low-pass filter**
a filter that allows low frequencies to pass through, while blocking
high frequencies. A low-pass filter reduces noise, blurs detail, and
introduces delay in the time domain. Low-pass operations include
summation, integration, and averaging.

**macro** a short amount of code that expands into a large amount
of in-line code. Lisp and Clojure allow macros.

**map:** a correspondence between elements of a domain and elements
of a range

**modus ponens** from P and P → Q, derive Q.

** morphological analyzer** a program that reduces words to root words
and affixes, e.g., ` running` becomes ` run + ing`.

** morphology**
study of the forms that natural language words can take,
e.g by addition of suffixes.

**n-gram** sequences of n words

** nonterminal**
a grammar symbol that denotes the name of a phrase in a context-free grammar.

**operand** a value on which an operator acts

**operator** an action such as + that produces new values from given values

**overfitting** the tendency of a machine learning system to produce
results that are too closely tuned to the training set but not true
in general.

**PageRank** Google's algorithm for determining which web pages are the best

** parsing**
the process of ascribing structure to a linear sequence of words or
symbols according to the rules of a grammar.

**partial evaluation** to evaluate an expression in which some operands
are known, e.g. x + 0 ⇒ x

** part of speech tagging** assigning parts of speech to words in a
sentence based on surrounding words

** pragmatics**
aspects of a natural language that are dependent on a particular
language, culture, or facts about the world.

**predicate** in predicate calculus, a symbol that is applied to zero or more
arguments and is assigned values of True or False in an interpretation;
a function that tests a condition and returns a value
of `true` or `false`.

**predicate calculus** a form of logical representation that includes:
quantification of variables, terms (including functions of terms),
and predicates whose arguments are terms.

** production**
in a grammar, a rule that specifies that a phrase name can be replaced by
a sequence of words or phrases.

**propositional calculus**
a logical representation in terms of propositional variables, each
of which is true or false and has no arguments.

** propositional database**
a database of facts, stored in the form of logical formulae, that allows
retrieval of facts that match (unify with) a query predicate.

**quote** a Lisp function that returns its argument, without evaluating it

**recursion** a function that calls itself as a subroutine

** reference** the task of determining
the thing referred to by a phrase in natural language.

**rewrite rule** a rule containing variables that tells how to rewrite
a given form of expression as another form

**ROC curve** (originally *receiver operating characteristic*)
a plot of true positives vs. false positives, as produced by a binary classifier
such as an expert system

**root** the top element of a tree

**SAT** testing whether a logical formula is satisfiable, i.e. true under
some interpretation

** SAT solver**
a program that can efficiently find solutions to problems expressed
as SAT problems, e.g. WalkSAT and CHAFF.

** satisfiable** consistent, i.e. true for some interpretation.

**scope** the region of program text over which a name can be referenced.

**search** to try sequences of operators to attempt to find a sequence
that satisfies a goal.

** semantic grammar **
a grammar in which the phrases have meaning in the domain of
application, e.g. * part-name*, as opposed to being general syntactic
units, e.g., * noun-phrase*.

** semantics **
the study of how statements in a language denote meanings.

** sentence symbol**
the top-level symbol in a grammar, often abbreviated S.

**shard** a smaller piece of a large collection of data

**side-effect** any effect of a function other than returning a value,
such as printing or changing the value of a global variable

**Skolem function** in mathematical logic, a function introduced as
a substitute for an existentially quantified variable that depends
on universally quantified variables.

**specialize** to make a version of a generic procedure that is
specialized for certain data types or constant values.

**state space search** a search for a sequence of operators that will
transform a given starting state into some goal state. Each operator
transforms a state into a different state.

**structure sharing** a case where two data structures share some
elements.

**symbol** a runtime data structure that represents an algebraic
or symbolic name

** syntax**
study of the ways in which language components can legally be combined
into sentences.

**tail recursion** a function whose value either does not involve
a recursive call, or is exactly the value of a recursive call.

**term** in logic, an algebraic variable that represents an object
in the application domain. Terms include variables,
constants, and functions applied to terms.

** terminal symbol**
a symbol or word that appears in sentences of a language.

**training-set phenomenon** see overfitting.

**unification** finding a substitution of terms for variables in a set of
predicate calculus literals that will make the literals the same.

**unsatisfiable** of a logical formula, false under every interpretation;
inconsistent or contradictory.

**valid** of a logical formula, true under every interpretation.

**variable capture** a problem of a macro including a variable from its
call in its generated code

**variable in pattern** a symbol that can be replaced
by a corresponding part of the matched input

**well-founded ordering** an ordering that can be guaranteed to
terminate, e.g. starting at a positive integer and counting down to 0.

** Zipf's law**
the principle that frequently used words are short. More precisely,
length is proportional to negative log of frequency.

Gordon S. Novak Jr.