Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Revisiting the Visitor: the “Just Do It” Pattern

Didier Verna

didier@lrde.epita.fr

http://www.lrde.epita.fr/˜didier

ACCU 2009 – Friday, April 24th

1/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Introduction

Necessary literature

The GOF Book: Design Patterns, Elements of

Reusable Object-Oriented Software. Gamma, Helm,

Johnson, Vlissides.

The POSA Book: Pattern-Oriented Software

Architecture. Buschmann, Meunier, Rohnert,

Sommerlad, Stal.

What is a software design pattern ?



Context (POSA)



Problem



Solution



Consequences (GOF)

2/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

A constatation

Peter Norvig (Object World, 1996)

About the GOF book:

16 of 23 patterns are either invisible or simpler

[...] in Dylan or Lisp

Peter Norvig is right, so



is the GOF book (70%) wrong ?



are patterns (70%) useless ?

3/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Some clues from the GOF book itself

Although design patterns describe

object-oriented designs, they are based on

practical solutions that have been implemented in

mainstream object-oriented programming

languages [. . . ]

Similarly, some of our patterns are supported

directly by the less common object-oriented

languages.

 That’s what people usually miss

4/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Patterns descriptions / organizations

GOF: Creational, Structural, Behavioral



usage-oriented

POSA: Architectural, Design, Idioms



abstraction-oriented

Idioms according to POSA

An idiom is a low-level pattern speciﬁc to a

programming language. An idiom describes how to

implement particular aspects of components or the

relationships between them using the features of

the given language. [. . . ] They address aspects of

both design and implementation.

 GOF’s design patterns are closer to POSA’s idioms

5/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

The risk: blind pattern application

POSA’s advice:

[. . . ] sometimes, an idiom that is useful for one

programming language does not make sense into

another.

GOF’s Visitor example:

Use the Visitor pattern when [. . . ] many distinct

and unrelated operations need to be performed on

objects in an object structure, and you want to

avoid “polluting” their classes with these

operations.

 But who said operations belong to classes ?

6/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Table of contents

1 Visiting in C++

2 Visiting in LISP

Step 1: plain LISP

Step 2: brute force visiting

Step 3: ﬁrst class generic functions

Step 4: mapping

Step 5: generic mapping

3 Visiting with state

Step 6: objects

Step 7: lexical closures

Step 8: dynamic visitation schemes

7/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Visiting in C++

Problems:

Original hierarchy R/O

Abstract the visiting process away

Solution:

1 Equip original hierarchy for visits



A Visitable abstract class



An accept method in each visitable component

2 Write independent visitors



A Visitor abstract class



A visit method for each visitable component

9/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 1: plain LISP

Classes

( defclass cl a s s ( su perclass 1 supercla s s 2 . . . )

( ( s l o t : i n i t f o r m <form > : i n it a r g : sl ot : acces sor s lo t )

. . . )

o p t i on s . . . )

( make− instance ’ clas s : s l o t <value > . . . )

Generic functions, methods

( defg eneri c func ( arg1 arg2 . . . )

( : method ( ( arg1 cl ass1 ) arg2 . . . )

body )

o p t i on s . . . )

( defmethod func ( ( arg1 class1 ) arg2 . . . )

body )

 Methods are outside the classes (ordinary function calls)

 Multiple dispatch (multi-methods)

11/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Summary of step 1

1 Original hierarchy untouched



Generic function model (outside the classes)

2 Abstract the visiting process away



Still needs to be done

12/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 2: brute force visiting

Abstract the visiting process away



OK: the accept generic function

But what’s wrong with this picture ?

obj visitor

... ...

visit

obj

visitor

 One indirection too many

13/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 3: ﬁrst class (generic) functions

Notion of ﬁrst class / order

(Christopher Strachey, 1916–1975)

storage (in variables)

aggregation (in structures)

argument (to functions)

return value (from functions)

anonymous manipulation

dynamic creation

. . .

 Generic functions are ﬁrst class objects in LISP

14/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

The better picture

obj

...

obj

visitor

obj

Retrieving function objects in LISP

( f u nc t io n func ) ; ; => #<FUNCTION FUNC>

# ’ func ; ; => #<FUNCTION FUNC>

15/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 4: mapping

Prominent concept in functional programming



Along with folding (reduction), ﬁltering etc.

Thanks to ﬁrst class functions



Argument passing

Typical mapping example

( mapcar # ’ stri ng− u pcase ’ ("foo" "bar" "baz" ) )

; ; => ( "FOO" "BAR" " BAZ ")

 “visiting” is a form of structural mapping

16/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 5: generic mapping

Having to specialize mapobject is boring



Mapping over lists, vectors, arrays, even class slots

should be written only once

The CLOS Meta-Object Protocol (MOP)

CLOS itself is object-oriented



The CLOS MOP: a de facto implementation standard



The CLOS components (classes etc.) are

(meta-)objects of some (meta-)classes

 We have reﬂexive (introspective) access to class slots

17/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 6: objects

How about a component counter visitor ?

C++: left as an exercise. . .

LISP: how does that ﬁt with ﬁrst class functions ?



Global state (yuck !)



Behavior + state = objects !

So we’re back to visitor objects ?

 There has got to be a better way. . .

19/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 7: lexical closures

Behavior + State without the OO machinery

Typical functional example (with anonymous function)

( defun make−adder ( n)

( lambda ( x) (+ n x ) ) )

( fun c a l l (make− adder 3 ) 5) ; ; => 8

Closures with mutation (impure functional programming)

( l et ( ( count 0) )

( defun incr e m ent ( )

( inc f count ) ) )

( incr e m ent ) ; ; => 1

( incr e m ent ) ; ; => 2

; ; . . .

20/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Step 8: dynamic visitation schemes

How about a component nesting counter visitor ?

C++: left as an exercise. . .

LISP: modiﬁcation of the visit process required

1 increment nesting level before visiting an object

2 actual visit

3 decrement nesting level afterwards

Do we need a dedicated mapobject for that ?

 No ! We have the MOP’s generic function protocol

21/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

The generic function protocol

Generic function invocation

Return valuecall−next−method

Before Method

Primary Method

After Method

Around Method

Methods are CLOS meta-objects

Methods can be added/removed dynamically

22/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Summary

Decoupling from original hierarchy: n/a



Generic function model (outside the classes)

Visiting infrastructure:



First class generic functions (as argument)



CLOS MOP (introspection)

 Generic machinery in 10 lines of code

Visiting with state:



Lexical closures



First class functions (anonymous)



Generic function protocol (before/after)-methods

 5–10 more lines of code (original code untouched)

23/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

The “iceberg” metaphor

Programming Language

Programmer’s Application

DESIGN PATTERN

What you need to write

What’s already here

Lisp

Notice the difference ?

24/25

Visitor:

Just Do It

Didier Verna

Introduction

C++

LISP

Step 1: plain LIS P

Step 2: brute force

Step 3: ﬁrst class

Step 4: mapping

Step 5: generic map

State

Step 6: objects

Step 7: closures

step 8: visit schemes

Conclusion

Next LISP Events

ELS’09: 2nd European LISP Symposium

May 27-29 2009, Milan, Italy

http://www.european-lisp-symposium.org

ELW’09: 6th European LISP Workshop

July 6 2009, Genova, Italy

co-located with ECOOP.

http://elw.bknr.net/2009

25/25