Symbolic Programming: Vocabulary

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.