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 making new data structures, while leaving existing data structures unchanged. Think cons, which is always making something new.
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.
lhs left-hand side of an expression. In (+ A B), A is the lhs.
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
rhs right-hand side of an expression. In (+ A B), B is the rhs.
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.