Design Patterns in
Dynamic ProgrammingPeter Norvig
Chief Designer, Adaptive Systems
Harlequin Inc.
Peter Norvig, Harlequin, Inc.

1

Object World, May 5, 1996

Outline (1) What Are Design Patterns?

Templates that describe design alternatives
 (2) Design Patterns in Dynamic Languages
How to do classic patterns in dynamic languages
Escape from language limitations
 (3) New Dynamic Language Patterns
New patterns suggested by dynamic languages
 (4) Design Strategies
Thinking about all of software development

Peter Norvig, Harlequin, Inc.

2

Object World, May 5, 1996

(1) What Are Design Patterns?
 Problem: Represent a Rubik’s Cube as:

Cubies[3,3,3] ?
 Faces[6,3,3] ?
 Faces[54] ?
 Design Strategies:
 Most important things first (faces, moves) Reuse standard tools (1D), math (permutations) Design Patterns:
 Model/View
 Extension Language (define composed moves)Peter Norvig, Harlequin, Inc.

3

Object World, May 5, 1996

What Are Design Patterns?
 Descriptions of what experienced designers know(that isn’t written down in the Language Manual) Hints/reminders for choosing classes and methods
 Higher-order abstractions for program organization
 To discuss, weigh and record design tradeoffs
 To avoid limitations of implementation language(Design Strategies, on the other hand, are what guide
you to certain patterns, and certain implementations.
They are more like proverbs than like templates.)Peter Norvig, Harlequin, Inc.

4

Object World, May 5, 1996

What’s in a Pattern?
 Pattern Name Participants Intent / Purpose Collaborations

 Also Known As / Aliases

 Consequences/Constraints

 Motivation / Context

 Implementation

 Applicability / Problem

 Sample Code

 Solution

 Known Uses Structure Related Patterns/Compare

From Design Patterns andPattern Languages of Program DesignPeter Norvig, Harlequin, Inc.

5

Object World, May 5, 1996

Pattern: Abstract Factory Intent: Create related objects without specifying

concrete class at point of creation
 Motivation: Portable GUI (Motif, Windows, ...)Create a ScrollBar, get a MotifScrollBar;
Also for SmallBlueWindow, MyAppWindow Participants: AbstractFactory, ConcreteFactory,
AbstractProduct, ConcreteProduct, Client Sample Code: class MotifFactory ... ;factory = new MotifFactory;...
CreateWindow(factory, x, y);Peter Norvig, Harlequin, Inc.

6

Object World, May 5, 1996

Level of Implementation of a Pattern Invisible

So much a part of language that you don’t notice(e.g. when class replaced all uses of struct in C++, no more “Encapsulated Class” pattern) Informal
Design pattern in prose; refer to by name, but
Must be implemented from scratch for each use
 Formal
Implement pattern itself within the language
Instantiate/call it for each use
Usually implemented with macrosPeter Norvig, Harlequin, Inc.

7

Object World, May 5, 1996

Sources on Design Patterns
 Design Patterns

Gamma, Helm, Johnson & Vlissides, 1995
 Pattern Languages of Program Design
Coplien & Schmidt, 1995
 Advanced C++ Programming Styles and Idioms
Coplien, 1992
 Object Models
Coad, 1995
 A Pattern Language
Alexander, 1979
Peter Norvig, Harlequin, Inc.

8

Object World, May 5, 1996

(2) Design Patterns in Dynamic Languages
 Dynamic Languages have fewer language limitations

Less need for bookkeeping objects and classes
Less need to get around class-restricted design
 Study of the Design Patterns book:16 of 23 patterns have qualitatively simpler
implementation in Lisp or Dylan than in C++
for at least some uses of each pattern Dynamic Languages encourage new designs
We will see some in Part (3)Peter Norvig, Harlequin, Inc.

9

Object World, May 5, 1996

Design Patterns in Dylan or Lisp
16 of 23 patterns are either invisible or simpler, due to: First-class types (6): Abstract-Factory,
Flyweight, Factory-Method, State, Proxy,
Chain-Of-Responsibility
 First-class functions (4): Command, Strategy,

Template-Method, Visitor
 Macros (2): Interpreter, Iterator
 Method Combination (2): Mediator, Observer
 Multimethods (1): Builder
 Modules (1): FacadePeter Norvig, Harlequin, Inc.

10

Object World, May 5, 1996

First-Class Dynamic Types First-Class: can be used and operated on where anyother value or object can be used
 Types or Classes are objects at run-time(not just at compile-time) A variable can have a type as a value A type or class can be created/modified at run-time There are functions to manipulate types/classes(and expressions to create types without names) No need to build extra dynamic objects just to holdtypes, because the type objects themselves will doPeter Norvig, Harlequin, Inc.

11

Object World, May 5, 1996

Dynamic Pattern: Abstract Factory
 Types are runtime objects; serve as factories(No need for factory/product dual hierarchy)
 No need for special code; use is invisible:
window-type := <motif-window>;...
make(window-type, x, y); Still might want factory-like objects to bundle classes(window, scroll-bar, menu, border, tool-bar, ...)
 Works in Lisp or Dylan or Smalltalk or ...
 Dylan classes explicitly abstract or concretePeter Norvig, Harlequin, Inc.

12

Object World, May 5, 1996

Pattern: Abstract Factory Static version requires dual hierarchy of classes:

GUIFactory
NTFactory
MacOSFactory
XFactory
MotifFactory

Window
NTWindow
MacOSWindow
XWindow
MotifWindow

with objects instantiated on both sides
 Dynamic version needs only the Window classes
The classes themselves serve as factories
This works because classes are first-class values
We can say make(c)Peter Norvig, Harlequin, Inc.

13

Object World, May 5, 1996

First-Class Dynamic Functions
 Functions are objects too Functions are composed of methods
 There are operations on functions (compose, conjoin)
 Code is organized around functions as well as classes
 Function closures capture local state variables(Objects are state data with attached behavior;
Closures are behaviors with attached state data
and without the overhead of classes.)Peter Norvig, Harlequin, Inc.

14

Object World, May 5, 1996

Pattern: Strategy
 Intent: Define a family of interchangeable algorithms
 Motivation: Different line-breaking algorithms
 Participants: Strategy, ConcreteStrategy, Context
 Implementation:

class Compositor ...;
class TeXCompositor : public Compositor...;class Composition {public: Composition(Compositor*); ...};...
Composition* c =new Composition(new TeXCompositor);c.compositor->Compose();Peter Norvig, Harlequin, Inc.

15

Object World, May 5, 1996

Dynamic Pattern: Strategy
 The strategy is a variable whose value is a function(E.g., with first-class functions, pattern is invisible) Implementation:
compositor := TeXcompositor;
compositor(...); General principle: no need for separate classes thatdiffer in one (or a few) well-understood ways.
 May still want strategy objects:
make(<strategy>, fn: f, cost: 5, speed: 4)

but don’t need separate classes for each instancePeter Norvig, Harlequin, Inc.

16

Object World, May 5, 1996

Macros Macros provide syntactic abstraction

You build the language you want to program in Just as important as data or function abstraction
 Languages for Macros String substitution (cpp) Expression substitution (Dylan, extend-syntax)
 Expression computation (Lisp)
Provides the full power of the language while you
are writing code

Peter Norvig, Harlequin, Inc.

17

Object World, May 5, 1996

Pattern: Interpreter Intent: Given a language, interpret sentences Participants: Expressions, Context, Client Implementation: A class for each expression type

An Interpret method on each class
A class and object to store the global state (context)
 No support for the parsing process(Assumes strings have been parsed into exp trees)Peter Norvig, Harlequin, Inc.

18

Object World, May 5, 1996

Pattern: Interpreter with Macros Example: Definite Clause Grammars
 A language for writing parsers/interpreters
 Macros make it look like (almost) standard BNF

Command(move(D)) -> “go”, Direction(D).
 Built-in to Prolog; easy to implement in Dylan, Lisp
 Does parsing as well as interpretation
 Builds tree structure only as needed(Or, can automatically build complete trees) May or may not use expression classes

Peter Norvig, Harlequin, Inc.

19

Object World, May 5, 1996

Method Combination
 Build a method from components in different classes
 Primary methods: the “normal” methods; choose themost specific one Before/After methods: guaranteed to run;
No possibility of forgetting to call superCan be used to implement Active Value pattern Around methods: wrap around everything;
Used to add tracing information, etc.
 Is added complexity worth it?
Common Lisp: Yes; Most languages: No
Peter Norvig, Harlequin, Inc.

20

Object World, May 5, 1996

Pattern: Observer
 Intent: When an object changes, notify all interested
 Motivation: A spreadsheet and a bar chart are both

displaying the results of some process. Update both
displays when the process gets new numbers.
 Participants: Subject, Observer, ConcreteSubject,
ConcreteObserver
 Implementation:
Subject: methods for attach/detach observer, notify
Observer: method for update

Peter Norvig, Harlequin, Inc.

21

Object World, May 5, 1996

Observer with Method Combination
 Observer is just “notify after every change”(With more communication in complex cases) Implementation: Use :after methods
Can be turned on/off dynamically if needed
Allows the implementation to be localized:(mapc #’notify-after ‘(cut paste edit ...))(defun notify-after (fn)(eval `(defmethod ,fn :after (x)(mapc #‘notify (observers x)))))
 Note no implementation needed in Subject class See Relation pattern for observers implementation
Peter Norvig, Harlequin, Inc.

22

Object World, May 5, 1996

The Type/Operation Matrix
 Programs have types and operations:

Rectangle

CircleLinedraw
positionarea

Three types of programming fill cells in different order: Procedural: write entire row at a time
(Problems with case statements)
 Class-Oriented: write column at a time (inherit some) Literate: fill cells in any order for best expositionPeter Norvig, Harlequin, Inc.

23

Object World, May 5, 1996

Multimethods
 Operations often deal with multiple objects: f(x,y)
Rect Circle Line
Shape
Point
Windowdraw
move-todistance Class-oriented has a distinguished object: x.f(y)(May be unnatural, hard to extend) Multimethods allow literate programming
 Support Singleton and prototypes using == dispatch
Peter Norvig, Harlequin, Inc.

24

Object World, May 5, 1996

Pattern: Builder
 Intent: Separate construction of complex object fromits representation; so create different representations
 Participants: Builder, ConcreteBuilder, Director,
Product Motivation: Read text document in RTF format
 Convert to one of many formats
 One conversion algorithm Details differ depending on target format
 Implementation: Separate class for each type ofobject to build; another for the “director”
Peter Norvig, Harlequin, Inc.

25

Object World, May 5, 1996

Pattern: Builder
 Builder: TextConverter class with methods forConvertCharacter, ConvertParagraph, ...
 ConcreteBuilder: ASCIIConverter, TeXConverter, ...
 Director: Builder slot and algorithm for conversion
 Product: ASCIIText, TeXText, ...
 Total of 2n + 2 classes
 Implementation:
switch(t=GetToken().Type) {CHAR: builder->ConvertChar(t);FONT: builder->ConvertFont(t);PARA: builder->ConvertParagraph(t);}Peter Norvig, Harlequin, Inc.

26

Object World, May 5, 1996

Pattern: Builder with Multimethods
 No builder or director classes; n product classes
 One builder function (extensible: no switch) n methods for conversion (convert)
 Implementation:

target-class := <TeX-Text>;
target := make(target-class);...

token := get-token();convert(token, token.type, target);...

define method convert(token, type==#”font”, target::<TeX-Text>)
Peter Norvig, Harlequin, Inc.

27

Object World, May 5, 1996

Modules In C++, classes organize, implement object behavior

and define name spaces This leads to problems: Compromises between two purposes Need more selective access than public/private
 Friend classes don’t work well
 Separate modules relieve the class of double-duty Can have multiple modules for one library of code

Peter Norvig, Harlequin, Inc.

28

Object World, May 5, 1996

Pattern: Facade Intent: Provide a simple interface to a subsystem Motivation: A complex system may have manypieces that need to be exposed. But this is confusing.
Supply a simpler interface on top of the system.
 Participants: Facade, SubsystemClasses
 Example: A Compiler class that calls scanner, parser,
code generator in the right way
 Facade pattern with modules is invisible
 Don’t need any bookkeeping objects or classes
 Just export the names that make up the interface
Peter Norvig, Harlequin, Inc.

29

Object World, May 5, 1996

Other Invisible Patterns
 The following patterns are invisible in dynamic

languages, and usually implemented more efficiently
 Smart Pointers(Pointers that manage copy constructors)
 Reference Counting(Automatic memory management) Closures(Functions with bound variables) Wrapper Objects(Objects with one data member, a primitive type suchas a character or 32-bit integer)Peter Norvig, Harlequin, Inc.

30

Object World, May 5, 1996

(3) New Dynamic Language Patterns
 First-Class Patterns: make the design more explicit
 Iterators: a study of C++, Dylan, Smalltalk and Sather
 Mixing compile time and run time

(Memoization, Compiler, Run time loading,Partial Evaluation)
 Freedom of syntactic expression(Decision tables, Rule-based translator)
 Freedom from implementation details(Relation)Peter Norvig, Harlequin, Inc.

31

Object World, May 5, 1996

First-Class Design Patterns
 Define the pattern with code, not prose
 Use the pattern with function or macro call(s),not a comment
 Implement with classes, objects, functions, macros
 This is the second half of abstraction:
Assigning something to a name.
It works better when something is a real object.
(It is hard because many patterns are not localized.) It’s easier when code needn’t be organized by class
Then the call to the pattern can generate any code
Peter Norvig, Harlequin, Inc.

32

Object World, May 5, 1996

First Class Pattern: Subroutine
 Long ago, subroutine call was just a pattern Involves two parts: call and definitionload R1, xload R0, *+2branch SQRT

SQRT:
...
branch @R0

 Nowadays, made formal by the language

sqrt(x);function sqrt(x) ...

 Note there are still 2 parts in formal use of pattern Many patterns are harder to define formally because

their use is spread out over more than two placesPeter Norvig, Harlequin, Inc.

33

Object World, May 5, 1996

First Class Pattern Implementation
 As abstract class:define class <adapter> ()slot adaptee;end As generic function:

define generic iteration-protocol(object) As a macro:define grammar
Command(go(D)) -> “go”, Direction(D);
...
end;

Peter Norvig, Harlequin, Inc.

34

Object World, May 5, 1996

Pattern: Protocol Method
 Intent: Implement set of related operations
 Implementation: Define a protocol method that

returns the required functions. Arrange to call thefunctions as needed.
 Participants: Protocol generic function, Client(s) Example: Protocol returns 2 objects, 3 functions:
iteration-protocol(object) =>state, limit, next, done?, current
 Advantages: Doesn’t require unique parent class
Can be quicker to compute all at once
Often avoid allocating bookkeeping objects, classes
Peter Norvig, Harlequin, Inc.

35

Object World, May 5, 1996

Pattern: Protocol Method
 Interfaces have 3 potential users, those who want to:

Use existing code properly Extend an existing class Implement for a brand new base class Protocols can make this distinction
 Classes can also make it, via virtual functions(But don’t allow a new class not derived from base)Peter Norvig, Harlequin, Inc.

36

Object World, May 5, 1996

A Study in Patterns: Iterator
 Intent: allow access to each element of collection
 Motivation: separate interface/implementation,

allow multiple accesses to same collection
 Participants: Iterator, ConcreteIterator, Collection,
ConcreteCollection
 C++ Implementation: Problems: Creating, deleting
iterators; Need for dual hierarchy; Ugly syntax:
ListIter<Employee*>* i=employees->Iter();for (i.First(); !i.IsDone(); i.Next());
i.CurrentItem()->Print();
delete i;Peter Norvig, Harlequin, Inc.

37

Object World, May 5, 1996

C++ Pattern: Internal Iterator
 Intent: An iterator to which you provide an operationthat will be applied to each element of collection
 Example: print a list of employees
template <class Item> class List
template <class Item> class ListIter
public: bool Traverse();protected: virtual bool Do(Item&);class PrintNames : ListIter<Employee*>protected: bool Do(Employee* & e) {e->Print();}...
PrintNames p(employees); p.Traverse();Peter Norvig, Harlequin, Inc.

38

Object World, May 5, 1996

Smalltalk Pattern: Internal Iterator
 Closures eliminate the need for iterator classes(Replace 10 or so lines of code with 1)
 Pass a block (function of one arg) to the do: method
employees do: [ :x | x print ] Easy for single iteration
 Also used heavily in Lisp, Dylan
 Inconvenient for iteration over multiple collections
How do you compare two collections?
How do you do element-wise A := B + C?

Peter Norvig, Harlequin, Inc.

39

Object World, May 5, 1996

Dylan Pattern: Iteration Protocol
 Iteration protocol instead of iterator classes
 The protocol returns 2 objects, 3 functions:

iteration-protocol(object) =>state, limit, next, done?, current
 Designed for optimization (see Lazy Evaluation)
 No need for parallel class hierarchy of iterators
Do need to provide (or inherit) iteration protocol
 Capability to define operations on protocol results
More flexible algebra of iterators(reverse, first-n, lazy-map)
Peter Norvig, Harlequin, Inc.

40

Object World, May 5, 1996

Dylan Pattern: Iteration Protocol
 Simple syntax

for(i in collection) print(i) end; Multiple iteration allowed with more complex syntax
for(i in keys(A), x in B, y in C)
A[i] := x + y;end;
 Dylan also supports internal iteration:do(print, collection)
 Many internal iterators (higher-order functions):
always?(\=, A, B);
map-into(A, \+, B, C);
Peter Norvig, Harlequin, Inc.

41

Object World, May 5, 1996

Dylan: Iteration Protocol Algebra Add a class named <iterator> with slots

object and protocol such that:
iteration-protocol(i :: <iterator>) =>protocol(i.object) Add functions to make objects of this class:define function backward (collection)make(<iterator>, object: collection,
protocol: reverse-iteration-protocol); Use the functions to build <iterator>s:for (x in C.backward) ... end;
 This may soon be built-in to Dylan’s syntax:
for (x in C using reverse-iteration-protocol)
Peter Norvig, Harlequin, Inc.

42

Object World, May 5, 1996

Pattern: Lazy Mapper Iteration
 Adding a lazy mapper iterator
make(<iterator>,object: c, protocol: f.lazy-mapper)
 Implementing the lazy-mapper:

define function lazy-mapper (fn)method (coll)let (state, lim, next, done?, current) =iteration-protocol(coll);
let mapper = method (c, state)fn(current(c, state));end;
values(state, lim, next, done?, mapper)
end;
end;
Peter Norvig, Harlequin, Inc.

43

Object World, May 5, 1996

Sather Pattern: Coroutine Iterator
 Notion of iterators as coroutines. In ARRAY class:index!:INT isloop yield 0.to!(self.size-1) end
end;
elt!:T isloop yield self[self.index!] end
end; Anonymous iteration: no need for variable names:
loop
A[A.index!] := B.elt! + C.elt!
end;Peter Norvig, Harlequin, Inc.

44

Object World, May 5, 1996

Pattern: Coroutine Intent: separate out distinct kinds of processing; savestate easily from one iteration to the next
 Implementation: Most modern language
implementations support an interface to the OS’s
threads package. But that has drawbacks: No convenient syntax (e.g. yield, quit) May be too much overhead in switching Problems with locking threads
 Implementation: Controlled uses of coroutines canbe compiled out (Sather iters, Scheme call/cc)
Peter Norvig, Harlequin, Inc.

45

Object World, May 5, 1996

Pattern: Control Abstraction
 Most algorithms are characterized as one or more of:

Searching: (find, some, mismatch)
Sorting: (sort, merge, remove-duplicates)
Filtering: (remove, mapcan)
Mapping: (map, mapcar, mapc)
Combining: (reduce, mapcan, union, intersection)
Counting: (count) Code that uses these higher-order functions instead ofloops is concise, self-documenting, understandable,
reusable, usually efficient (via inlining) Inventing new control abstractions is a powerful ideaPeter Norvig, Harlequin, Inc.

46

Object World, May 5, 1996

Pattern: New Control Abstraction
 Intent: Replace loops with named function or macro Motivation: A control abstraction to find the bestvalue of a function over a domain, find-best
 Examples:find-best(score, players);
find-best(distance(x), numbers, test: \<);
where define function distance(x)method (y) abs(x - y) end; end; Implementation: A simple loop over the collection,

keeping track of best element and its value.
In some cases, a macro makes code easier to readPeter Norvig, Harlequin, Inc.

47

Object World, May 5, 1996

Pattern: Memoization
 Intent: Cache result after computing it, transparently
 Example:(defun-memo simplify (x) ...)
 Implementation: Expands into (roughly):(let ((table (make-hash-table)))(defun simplify (x)(or (gethash x table)(setf (gethash x table) ...))))
 Complications: Know when to empty table, howmany entries to cache, when they are invalidPeter Norvig, Harlequin, Inc.

48

Object World, May 5, 1996

Pattern: Singleton as Memoization
 Can use memoization to implement Singleton pattern Implementation:(defmethod-memo make ((class SINGLETON))...) Invisible Implementation: Don’t need singletons if

you can dispatch on constants:
define constant s1 = make(<class>, n: 1);
define method m (x == s1) ... end
define constant s2 = make(<class>, n: 2);
define method m (x == s2) ... end

Peter Norvig, Harlequin, Inc.

49

Object World, May 5, 1996

Pattern: Compiler Like the Interpreter pattern, but without the overhead A problem-specific language is translated into the hostprogramming language, and compiled as normal
 Requires complex Macro capabilities
May or may not require compiler at run time
 A major factor when Lisp is faster than C++
 In a sense, every macro definition is a use of theCompiler pattern (though most are trivial uses)
 Examples: Decision trees; Window, menu layout;
Definite Clause Grammar; Rule-Based Translator
Peter Norvig, Harlequin, Inc.

50

Object World, May 5, 1996

Pattern: Run-Time Loading Intent: Allow program to be updated while it isrunning by loading new classes/methods (either
patches or extensions). Good for programs thatcannot be brought down for upgrades.
 Alternative Intent: Keep working set small, start-up
time fast by only loading features as needed Implementation: DLLs, dynamic shared libraries.
Language must allow redefinition or extension

Peter Norvig, Harlequin, Inc.

51

Object World, May 5, 1996

Pattern: Partial Evaluation
 Intent: Write literate code, compile to efficient code Example:

define function eval-polynomial(x, coefs)
let sum = 0;
for (i from 0, c in coefs)
sum := sum + c * x ^ i;
end;
sum;
end;

such that eval-polynomial(x, #[1, 2, 3])compiles to 0 + 1 + 2 * x + 3 * x * xor better yet 1 + x * (2 + 3 * x)
Peter Norvig, Harlequin, Inc.

52

Object World, May 5, 1996

Pattern: Partial Evaluation
 Implementation: Mostly, at whim of compiler writer(Harlequin Dylan, CMU Lisp compilers good at it) Alternative Implementation: Define a problemspecific sublanguage, write a compiler for it withpartial evaluation semantics
 Example:
Macro call horner(1 + 2 * x + 3 * x ^ 2)
expands to 1 + x * (2 + 3 * x)

Peter Norvig, Harlequin, Inc.

53

Object World, May 5, 1996

Pattern: Rule-Based Translator
 Intent: For each pattern detected in input, apply atranslation rule
 Special case of Interpreter or Compiler Example:
define rule-based-translator simplify ()(x + 0) => x;(x * 1) => x;(x + x) => 2 * x;(x - x) => 0;
...
end;

Peter Norvig, Harlequin, Inc.

54

Object World, May 5, 1996

Pattern: Relation
 Intent: Represent that x is related to y by R
 Motivation: Often, this is done by making a R slot in

the class of x and filling it with y. Problems: May be no common superclass for x’s
 y may take less than a word (say, 1 bit)
 Don’t want to waste space if most y’s are void
 Don’t want to page if cycling over R’s
 Solution: Consider a range of implementations, fromslot to bit vector to table to data base. Provide acommon interface to the implementations.
Peter Norvig, Harlequin, Inc.

55

Object World, May 5, 1996

(4) Design Strategies
 What to Build(Class libraries, frameworks, metaphors, ...)
 How to Build(Programming in, into, and on a language)
 How to Write(Literate programming vs. class-oriented/obsessed)
 Specific Design Strategies(Open Implementation; English Translation)
 Metaphors: The Agent Metaphor(Is agent-oriented programming the next big thing?)
 Combining Agent Components
Peter Norvig, Harlequin, Inc.

56

Object World, May 5, 1996

What to Build Class Libraries / Toolkits

Generic (sets, lists, tables, matrices, I/O streams)
 Frameworks
Specialized (graphics), “Inside-Out” (callbacks)
 Languages
Generic or Specialized (Stratified Design) Design Process
Source control, QA, Design rationale capture, ...
 Metaphors
Agent-Oriented, Market-Oriented, Anytime
ProgrammingPeter Norvig, Harlequin, Inc.

57

Object World, May 5, 1996

How to Build Programming In a language

The design is constrained by what the language offers
 Programming Into a language
The design is done independently of language, thenthe design is implemented using features at hand
 Programming On a language
The design and language meet half way. This isprogramming into the language you wish you had; alanguage you build on the base language.
Sometimes called Stratified Design.
Peter Norvig, Harlequin, Inc.

58

Object World, May 5, 1996

How to Build: Abstraction
 Data abstraction: encapsulation, first-class types
 Functional abstraction: first-class functions, closures
 Syntactic abstraction: macros, overloading Control abstraction: macros and high-order functions
 Design process abstraction: abstract away files, deal

with phases of project, explicit development process Resource abstraction: separate what it takes to do it
from what is done (See Open Implementation)
 Storage abstraction: garbage collection, no new,slot access and function calls have same syntax
Peter Norvig, Harlequin, Inc.

59

Object World, May 5, 1996

How to Write: Literate Programming Literate Programming: allow programmer to decide

how best (in what order) to present the program Obsession: insisting on one’s favorite organization
 Class-Oriented Prog: Organize text around classes
 Class-Obsessed Prog: Doing this to an extreme C++: Oriented to class and copy, not pure objects
 Lisp, Dylan: Oriented to pure objects, modules,
literate programming, not class over functions
 Anti-Object-Obsessed: “I do not believe in things. I
believe only in their relationships” - George BraquePeter Norvig, Harlequin, Inc.

60

Object World, May 5, 1996

Class-Oriented or Class-Obsessed?
 Class-based textual organization good for elementary

abstract data types
 Good to have some organization guidelines C++ provides several escapes from class-obsession
 C++ encourages bookkeeping classes(Visitor pattern serves only to get around restriction)
 Need bookkeeping especially for n-ary relations
 friend and related accesses are complex
 Class-based names don’t replace a real module
system Class-oriented organization prevents certain macrosPeter Norvig, Harlequin, Inc.

61

Object World, May 5, 1996

Strategy: Open Implementation
 Intent: Open up the black box; performance counts
 Motivation: A spreadsheet could be implemented bymaking 100x100 small windows. The window
system’s interface allows this, but it would be
inefficient. Could we persuade the system to use an
efficient implementation just this once? Then we
don’t have to re-code all the stuff that already works.
 Idea: Complex interfaces are split in two: one for the
specification, and one for the implementation. Whenit matters, specify the implementation you need (See Programmable Programming Language)Peter Norvig, Harlequin, Inc.

62

Object World, May 5, 1996

Design Strategy: English Translation
 To insure that your program says what you mean:(1) Start with English description(2) Write code from description(3) Translate code back to English; compare to (1) Example: (1), (2) from a Lisp textbook(1) “Given a list of monsters, determine the numberthat are swarms.”(2) See next slide(3) “Given a list of monsters, produce a 1 for amonster whose type is swarm, and a 0 for others.
Then add up the numbers.”
Peter Norvig, Harlequin, Inc.

63

Object World, May 5, 1996

Design Strategy: English Translation
 Example, step (2):(defun count-swarms (monsters)(apply ‘+ (mapcar#’(lambda (monster)(if (eql (type-of monster)‘swarm)1 0))
monsters))) (Small changes not relevant to problem were made)Peter Norvig, Harlequin, Inc.

64

Object World, May 5, 1996

Design Strategy: English Translation
 Code taking the strategy into account: (1) “Given a list of monsters, determine the numberthat are swarms.”
 (2) A straight-forward implementation:(defun count-swarms (monsters)(count ‘swarm monsters :key #’type-of)) (3) “Given a list of monsters, count the number

whose type is swarm.”Peter Norvig, Harlequin, Inc.

65

Object World, May 5, 1996

Metaphor: Agent Programming
Traditional Program Function
 Input / output
 Logic-based Goal-based Sequential, single Hand Programmed
 Design trade-offs
 Fidelity to expert
Peter Norvig, Harlequin, Inc.

Agent Program Agent Percept / action
 Probability-based
 Utility-based Parallel, multi Trained (Learning) Run-time trade-offs
 Perform well in env.
66

Object World, May 5, 1996

Agent Programming Technology
Mathematics
 Decision Theory
 Control Theory
 Statistical Optimization
 Economic Theory
 Markov Decision
Processes

Peter Norvig, Harlequin, Inc.

Artificial Intelligence Machine Learning Neural Networks
 Reinforcement Learning Bayesian Networks
 Anytime Programming

67

Object World, May 5, 1996

Design for a Rational Agent Calculate P(current state)

Based on evidence, percept, last action
 Calculate P(Result(Act)) ,U(Result(Act)) Nondeterministic: many states, results
 Calculate expected utility EU for each action
 EU(Act) = Σi P(Resulti (Act))·U(Resulti (Act)) Choose the Action with highest expected utility
 Best Act = argmaxA EU(ActA ) Approximate if not enough resources to computePeter Norvig, Harlequin, Inc.

68

Object World, May 5, 1996

Rational Reasoning Obey Principle of Maximum Expected Utility
 Apply at design or run time as appropriate
 Not a new idea: “To judge what one must do to obtaina good or avoid an evil, it is necessary to consider not
only the good and the evil in itself, but also theprobability that it happens or does not happen; and toview geometrically the proportion that all these things
have together.” A. Arnauld, The Art of Thinking, 1662
 Has been the basis of most science since then(Economics, Medicine, Genetics, Biology, OR, ...)
Peter Norvig, Harlequin, Inc.

69

Object World, May 5, 1996

The Three Laws of Robotics
 (1) Don’t harm humans, through action or inaction
 (2) Obey humans, except when conflict with (1) (3) Protect self, except when conflict with (1, 2)
 Why Asimov was wrong

Too Boolean: need notions of utility, probability
 Problems with “cause,” “protect,” “harm,” etc.
 Laws can be seen as defining utility function only
 Still too absolute Actually, Asimov probably knew it (Roundabout)Peter Norvig, Harlequin, Inc.

70

Object World, May 5, 1996

Object-Oriented Programming
Lessons Learned:
 Abstraction: data (objects), procedural (interfaces) What, not how, it computes
 No global variables; no top level Any computation might be embedded
 Reuse through inherit and modify
 Composition through standard techniques: Conditional, sequential, loop/recursion
 P is closed under composition(But real programmers make finer distinctions)Peter Norvig, Harlequin, Inc.

71

Object World, May 5, 1996

Agent Programming
Lessons Learned:
 Plan abstraction
 What, not how, it acts Resource allocation optimized separately (MS) No top level goals
 Any agent can be retargetted
 Reuse through parameter-setting optimization
 Composition is not straightforward: Economic (Market-Oriented) Programming Anytime ProgrammingPeter Norvig, Harlequin, Inc.

72

Object World, May 5, 1996

Combining Agent Components
 Essential for modular, scaleable, reusable systems
 Reuse in new or changed environment

Machine learning/statistical optimization
 Reuse with retargeted goal or utility function
 Real advantage over traditional programming Allocating resources to agent components/tasks
 Anytime programming Scaling up to multiple cooperating agents
 Economic (Market-Oriented) Programming
Peter Norvig, Harlequin, Inc.

73

Object World, May 5, 1996

Real-Time Resource Allocation
 Sensing and planning as information sources

Manage based on value of information
 Assumes time-dependent utility function
 Value depends on quality, time, ease of use
 Trade-off value of information vs. resources Build out of anytime and contract components(Interrupt when results are good enough) Modularize construction vs. optimization
 Maintain conditional performance profiles
Peter Norvig, Harlequin, Inc.

74

Object World, May 5, 1996

Compilation of Anytime Algorithms
 Given: components with performance profiles, Q

Interpret(Data);
Q(Interpret, t) = ...
 PlanPath(A, B, S); Q(PlanPath, Qs, t) = ...
 Given: an abstract overall algorithm
 E.g. A = PlanPath(A, B, Interpret(Camera()))
 Q(A,t) = max Q(PlanPath, Q(Interpret, t1), t2)
where t = t1 + t2
 Find optimal allocation of resources
 Monitor and adapt at run-timePeter Norvig, Harlequin, Inc.

75

Object World, May 5, 1996

Technology for Multi-Agent Systems
 Market-Oriented Programming

Bid in a competitive market of resources The market optimizes the value of resources Protocol Engineering Make the market communication efficient Incentive Engineering Achieve good for community Natural Language (and other) Communication
 Communication among programs and humans
Peter Norvig, Harlequin, Inc.

76

Object World, May 5, 1996