Appendix
C

Glossary

Brad A. Myers
and
David Maulsby

Introduction

• Brad Myers
• David C. Smith
• David Kurlander
• Richard Potter

Glossary

Terms in bold are cross-references to other terms in the glossary.

Abduction

Reasoning from an effect to its cause. If some theory states "if A then B" (A causes B) and you know B, then by abduction you infer A. Although logically invalid, abduction proves very useful in the real world, for instance when a doctor diagnoses a disease from symptoms. Generalization is a form of abduction, where he target concept is the diagnosis and the observed attributes of examples are the symptoms. From Ian Witten.

Active Values

Active values are variables that can hold values, but also call an associated action when the value changes. This action might update other values or graphics that depend on the value.

Application

A term used to refer to a commercially available program on a personal computer. For instance, WORD, HyperCard, and FrameMaker are "applications".

Application domain

Types of application programs. For instance, word processing, page layout, and spreadsheets are "application domains".

Automatic Programming

An old term for any software system that generates code from high-level specifications. This is a category of artificial intelligence (AI) research, and includes PBE interfaces that generate programs from examples of input and output or traces of an execution.

Bias

A machine learning term for the means by which a learning system chooses one generalization as opposed to others. A great many generalizations may cover a given set of examples. Trivial criteria such as choosing the most specific or most general description are useless by themselves (the most specific is just the list of positive examples already observed, and the most general is the complement of the negative examples observed), so additional biases are needed for effective learning. Bias may be implicit in a learning algorithm or explicitly stated in rules. Three kinds of bias are feature, syntactic, and preference-ordering. An important point about bias and PBD is that biases designed for data descriptions, actions and control flow help the system infer them more efficiently, but limit what can be learned. Nonetheless, PBD systems can learn procedures that implicitly define concepts they cannot learn explicitly.

Case-based learning

A kind of similarity-based learning in which new examples are matched against standard examples, called "cases" or "exemplars," rather than against abstract concepts. If a given example is not sufficiently like some stored case, it is remembered as a new case.

Comic-Strip Programs

see Graphical Histories.

Concept

The definition of a type of objects or events. A concept has an intensional definition (a generalization that states membership criteria), and an extension (the set of its instances).

Conjunctive form

Data descriptions comprising a conjunction of features (the most common form used in PBD). A system with a conjunctive bias generalizes by finding the features common to all examples.

Conjunctive normal form (CNF)

Data descriptions comprising a conjunction of disjunctions of features, such as "(red or blue) and (circle or triangle)."

Constraints

Relationships among objects that are declared once, and then maintained automatically by the system. For example, there might be a constraint that a line is attached to a circle, and then whenever either is moved, the system will move the other. In some systems, such as Peridot, constraints are guessed from examples.

Context

Information about the state of an application at a given time. For instance: The current event is "Copy Text". The current selection is "involvement in", which is words 5 and 6 of line 12 of paragraph 4 of the document "Management Principles". The word before the current selection is "maintain". The "Page Layout View" option is currently selected. The current font is 14 pt. Times. The current time is "16:22:08 11/28/92".

Data description

An intensional (descriptive) specification for a data object. A data description describes an object by its characteristics, such as its name, location, or contents; it does not refer to the object directly. In a direct manipulation system, most objects are referenced extensionally (directly), not descriptively. When a program is recorded by demonstration in a direct manipulation system, the user's reasons for choosing various data objects are not normally communicated to the system. However, if the system provides data descriptions, the user can use them to specify how the data objects were chosen. When the recorded program is run, its data descriptions are used to find objects that match the descriptions given by the user.

Demonstrational Interfaces

Demonstrational interfaces allow the user to perform actions on concrete example objects (often, by direct manipulation), while constructing an abstract program. As defined by Myers, this includes Programming by Example and Programming with Example, as well as interfaces that do not support programming.

Demonstrational Programming

Creating programs using demonstrational techniques. The title of this book uses "Demonstrational Programming" to mean any demonstrational interface, as defined above.

Disjunctive normal form (DNF)

Data descriptions comprising a disjunction of conjunctions of features, such as "all text with (pointsize=12 and font=Times) or (pointsize=10 and font=Helvetica)." Each conjunction (in parentheses) is called a "disjunct." This is the most general logical form of data description, because a DNF can describe any subset of the universe of objects implied by a given feature bias. The number of DNF's is exponential and so finding the simplest DNF is intractable, but greedy polynomial learning algorithms, such as ID3 [Quinlan 86], can efficiently learn descriptions having more disjuncts than necessary.

Dynamic bias

Being able to change the bias in response to the current context, as when the user gives sufficient examples to warrant looking for relations among them, or when the user does an action or gives a verbal hint that suggests a class of features not currently being tested.

End user

A user of an application program. Typically, the term means that the person is not a computer programmer. A person who uses a computer as part of their daily life or daily work, but is not interested in computers per se.

End-user Programming (EUP)

When end-users, who have not necessarily been taught how to write code in conventional programming languages, write computer programs. Examples include spreadsheet users who write formulas and macros. See also extension languages.

Example-based programming

Myers' term for systems that support programming through the use of example data. This is different from conventional testing and debugging because the examples are used during the development of the code, not just after the code is completed. Another distinction is that this does not include systems where example code is edited by the users, since essentially all programming is performed by editing existing code. Others use the term programming-by-example for all example-based-programming systems.

Examples

Data supplied to a program which the program operates on, but which also represents a wider class of data. Thus, the important features are that the program performs the operations on the examples, and that the examples can be generalized into variables.

Explanation-based learning

A single example is generalized by using background knowledge to identify the important features. Sometimes called "explanation-based generalization." Although the term was coined for systems with strong domain theories (from which the generalization can be deduced), some researchers use it when speaking of systems that have weak theories (i.e., the sort of generalization heuristics that many PBD systems use).

Extension Languages

The language used by users to change the actions and/or user interface of a system. For example, AutoCad has an embedded Lisp language for extensions, and Microsoft Word for Windows has an embedded Basic language. Some extension languages use programming by demonstration techniques so that users do not need to learn conventional programming languages.

Feature bias

Machine learning term for the vocabulary of attributes from which a system can construct generalized concepts; sometimes called "conceptual bias" or "lexical bias." For instance, a graphics PBD system might form generalizations that refer to touch relations between objects, but not to specific (x,y) coordinates of object parts, nor features derived from them, such as height and width. Its bias is object types and touch relations only. Other features (such as height) would have to be represented implicitly by procedures that test touch relations.

Feedback

The response of the system to the user's actions. In a demonstrational interface, feedback is often required to show the user the result of the system's inferences, so the user can check what the system is doing. Feedback can take many forms, including dialog boxes, questions and answers, program code, animation and sound.

Find-and-Do

Demonstrational interfaces where the primary mechanism is that the system finds an appropriate location through matching, and then does an operation there. From Maulsby and Potter.

Generalization

In demonstrational systems, the process of converting the code created using examples into an abstraction so the code can be used with different values. This includes replacing the specific example values with variables, finding loops and conditionals, etc. Generalization is the primary challenge of demonstrational systems, and it can be performed either by the user or automatically by the system using intelligence.

Graphical Histories

A pictorial technique for representing the previous actions of the user in a computer program, such as a graphical editor. Because these show changes from scene to scene, they are sometimes called comic-strip programs. The "prologue" is the scene before an action is taken, and the "epilogue" shows the result of the action. From Kurlander.

Guessing

When the system uses heuristics to choose an option, it may seem to users that the computer is guessing. Some people object to the use of the term "guess" for computers since computers always execute deterministic algorithms.

Heuristics

A problem-solving technique in which the most appropriate solution is selected using rules. Interfaces using heuristics may perform different actions on different data given the same command. All systems using heuristics are classified as intelligent.

Inferencing

When the computer tries to determine the appropriate generalization from examples. This uses heuristics, and is also called guessing.

Input-Output Example-based programming

Some kinds of example-based-programming only look at the input and output of an execution, and deduce a program from that, as opposed to trace-based example-based-programming which looks at the trace of the user's actions. Also called "Generalizing from input/output examples".

Instructible systems

Intelligent interfaces that generalize from demonstrations and other instructions (such as pointing and verbal hints) that help guide or eliminate inferencing.

Intelligent Interfaces

When the system uses heuristics or built-in knowledge to influence its response to user inputs. Includes natural language interfaces, expert systems, and programming-by-example systems that use inferencing.

Just-in-Time Programming

When users create programs as they need them while performing some other task. From Potter.

Learning from a single example

see Explanation-based learning.

Learning from multiple examples

see Case-based and Similarity-based learning.

Learning

Simon defined learning as changes in a system that result in improved performance over time on tasks similar to those done previously. A dictionary definition is that it is acquiring knowledge or skill through study, experience or teaching. Whether a computer system "learns" or merely "induces generalizations" is often a subject of debate, because typical generalization procedures and concept representations are simplistic and brittle. Simon's definition seems to suggest continuous, cumulative improvement as the acid test, and the dictionary hints at the breadth and depth of background knowledge applied and the ability learn from various kinds of input.

Macros

In the context of programming by demonstration, this usually refers to any procedure created by recording the user's actions as they are carried out. Unlike the conventional computer-science definition, the use here does not necessarily have any implications about how the procedure is executed (whether it is expanded in-line using textual substitution or called as a function).

Matching

Grouping examples under the same concept. "Clustering" is matching examples with other examples in order to form a new concept. "Classifying" is matching examples with a generalization to see if they are covered by it. "Generalizing" is modifying a concept so that it matches the new examples as well as previous ones. "Specializing" is modifying a concept so that it does not match negative examples.

Negative examples

Things that should not be covered by the target generalization.

New Beneficial Automation

When a task that was formerly done by a human is now performed by a computer. From Potter.

Positive examples

Members of the set (data type) whose description is being learned; things that should be covered by the target generalization.

Preference-ordering bias

Machine learning term for ordering alternative generalizations on the basis of heuristic rules, so that the most probably correct might be tried first. A simple form of preference ordering is to attach saliency or frequency measures to features observed in a given context; when inferencing, the system chooses features actually observed and having the highest measures. For instance, if the user's action is to change the style of the currently selected text to bold, then a highly probable reason for selecting that text is its style, so this feature should be given preference to others when proposing a generalization.

Program Visualization

Using graphics to make a program more understandable. Different from Visual Programming because in the latter the program is created graphically, but in program visualization, it is created in the normal, textual manner and the graphics are used afterwards to show how it works.

Program

A program is usually defined as "a sequence of instructions that are executed by a computer," so any system that executes the user's actions can be considered programmable. However, for the purposes of this book, it is useful to characterize how programmable the systems are. Therefore, Myers defines the term programmable to be systems that include the ability to handle variables, conditionals and iteration. Note that it is not sufficient for the interface to be used for entering or defining programs, since this would include all text editors. The interface itself must be programmable. This distinction is not particularly easy to make, and there can be arguments about whether a particular system should be called programmable or not.

Programming by Demonstration (PBD)

Synonymous with Programming by Example. In Myers' terminology, the same as example-based-programming.

Programming by Direct Manipulation

When the user can construct programs by directly manipulating on-screen (usually graphical) objects. Examples include interface builders that allow dialog boxes to be created, HyperCard when not using scripts, and most programming-by-example systems. The distinction between PDM and PBE is that in PDM, the objects being manipulated might be the actual components of the program, rather than examples that represent more general concepts. From D. C. Smith.

Programming by Example (PBE)

When programs are created through the use of examples. The examples serve as placeholders for abstractions. Myers would like to restrict this term to only systems with inferencing and that allow the end user to create real programs, but this would eliminate Pygmalion and SmallStar, which are often classified as PBE (including by their authors), so others prefer the more general definition.

Programming by Rehearsal

When programs are created by showing what the objects in it should do. Similar to example-based-programming. From Gould and Finzer.

Programming with Example

These are example-based-programs that do not use inferencing. From Myers.

Rehearsal

See programming by rehearsal.

Scripting Language

A programming language which is designed for a particular application domain. The language includes nouns for referring to objects in the domain, such as "button", "cell", and "author". Generally, a scripting language has simpler syntax and fewer programming constructs than a programming language like C.

Similarity-based learning

Inducing generalizations from multiple examples by finding features common to positive examples that distinguish them from negative examples.

Syntactic bias

Machine learning term for restricting the syntactic form or logical operators that can be used in a concept description; sometimes called "logical bias." Such restrictions limit the version space of generalizations that needs to be searched. The most important for data descriptions are conjunctive, conjunctive normal form and disjunctive normal form.

Target generalization

The correct (or nearly correct) description that the system is supposed to acquire.

Toolkits

A collection of procedures that can be used to create user interface software. A "demonstrational toolkit" would help in the creation of demonstrational interface software.

Trace-based example-based programming

A form of example-based programming where the program is created by saving a trace of the user's actions as an example is worked through, as opposed to input/output example-based programming. From Maulsby.

User Interface Development Environments

Software programs that help create the user interfaces of other software programs. Sometimes these use demonstrational techniques.

User Interface Management Systems (UIMSs)

Some people use this term to mean the same thing as User Interface Development Environments, but it really means a system that manages both the development and the run-time operations of user interfaces.

Version space

Machine learning term for all the alternative concept descriptions that cover the examples seen so far; that is, hold true of the positive examples and do not hold true of the negative ones.

Visual Programming

The creation of programs through the use of pictures. Example-based programs are sometimes represented using visual languages.

Visual Shell

A direct manipulation interface to an operating system. Examples include the Xerox Star interface and the Finder on the Apple Macintosh. Sometimes called the "desktop."