Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
Some Background
Which explains a lot. . .
Assistant professor in computer science
I
Research on the performance and expressiveness of
Common Lisp
I
Teaching (amongst other things) functional
programming to imperative-biased students
Imperative-educated myself
I
But I resisted
Member of the XEmacs core maintainers team
I
11 years
2/77
Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
Why Lisp?
What else do you need ?
Functional, purely or not
Imperative
Object-Oriented / MOP
Aspect- / Context-Oriented
Declarative
Reflexive (introspection / intercession)
Macros
Forms of pattern-matching, currying
Strict evaluation, or not
Dynamically Typed, or not
Lexically scoped, or not
Interpreted / Byte-Compiled / Compiled, Embeddable
No real difference between run-time and compile-time
Regular expressions, web servers,
web clients, foreign-functions inter-
faces, GUIs, OpenGL, multi-threading
support etc. etc. etc.
3/77
Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
From Andreï’s keynote
Let’s be realistic, I can’t win
I’m a peaceful guy. . .
Please continue using your favorite language
Please continue wishing you could use your favorite
language
Please don’t feel aggressed
“This is cool” 6= “That is bad”
. . . BUT:
Don’t you dare complaining about the parens
Don’t you dare thinking that Lisp is dead
It doesn’t even smell funny
I
Old 6= dead
I
Old = mature
I
Please at least have the decency to mention it !
5/77
Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
Because if you can read this. . .
template <template <class> class M, typename T, typename V>
struct ch_value_<M<tag::value_<T>>, V>
{ typedef M<V> ret; };
template <template <class> class M, typename I, typename V>
struct ch_value_<M<tag::image_<I>>, V>
{ typedef M<mln_ch_value(I, V)> ret; };
template <template <class, class> class M, typename T, typename I, typename V>
struct ch_value_<M<tag::value_<T>, tag::image_<I>>, V>
{ typedef mln_ch_value(I, V) ret; };
template <template <class, class> class M, typename P, typename T, typename V>
struct ch_value_<M<tag::psite_<P>, tag::value_<T>>, V>
{ typedef M<P, V> ret; };
6/77
Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
. . . sure you can read that !
(template (template (class) (class M) (typename T) (typename V))
(struct (ch_value_ (M (tag::value_ T)) V)
(typedef (M V) ret)))
(template (template (class) (class M) (typename I) (typename V))
(struct (ch_value_ (M (tag::image_ I)) V)
(typedef (M (mln_ch_value I V)) ret)))
(template (template (class class) (class M) (typename T) (typename I) (typename V))
(struct (ch_value_ (M (tag::value_ T) (tag::image_ I)) V)
(typedef (mln_ch_value I V) ret)))
(template (template (class class) (class M) (typename P) (typename T) (typename V))
(struct (ch_value_ (M (tag::psite_ P) (tag::value_ T)) V)
(typedef (M P V) ret)))
7/77
Lisp
Didier Verna
General
Introduction
Part I: Performance
Part II: Genericity
Genericity
5 Binary Methods non-issues
Types, Classes, Inheritance
Corollary: method combinations
6 Enforcing the concept – usage level
Introspection
Binary function class
7 Enforcing the concept – implementation level
Misimplementations
Strong binary functions
11/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Introduction
False beliefs
Yobbo sez: “But Lisp is slow right ?”
Me: “How do you know that ?”
Yobbo replies (choose your favorite answer):
I
Huh, it’s a well known fact
I
Well, that’s what I was told
I
Hmmm, last time I checked. . . (yeah, in 84)
14/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Facts
Old ones actually
Lisp is not slow
I
It’s been 20 years
•
Smart compilers (⇒ native machine code)
•
Weak typing (types known at compile-time)
•
Safety levels (compiler optimizations)
•
Efficient data structures (arrays, hash tables etc.)
•
Today’s machines 6= 1960’s machines
We need rock solid evidence:
I
Comparative C and Lisp benchmarks
(part 1: full dedication)
I
4 simple image processing algorithms
I
Pixel storage and access / arithmetic operations
15/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Experimental conditions
The algorithms: the “point-wise” class
I
Pixel assignment / addition / multiplication / division
I
Soft parameters: image size / type / storage / access
I
Hard parameters: compilers / optimization level
I
⇒ More than 1000 individual test cases
The protocol
I
Debian GNU Linux / 2.4.27-2-686 packaged kernel
I
Pentium 4 / 3GHz / 1GB RAM / 1MB level 2 cache
I
Single user mode / SMP off (no hyperthreading)
I
Measures on 200 consecutive iterations
18/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
C code sample
The add function
void add ( image ∗ to , image ∗ from , f l o a t v a l )
{
i n t i ;
const i n t n = ima−>n ;
for ( i = 0 ; i < n ; ++ i )
to −>data [ i ] = from−>data [ i ] + v a l ;
}
Gcc 4.0.3 (Debian package)
Full optimization: -O3 -DNDEBUG plus inlining
Note: inlining should be almost negligible
20/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Results
In terms of behavior
1D implementation slightly better (10% ⇒ 20%)
Linear access faster (15 ⇒ 35 times)
I
Arithmetic overhead: only 4x – 6x
I
Main cause: hardware cache optimization
Optimized code faster (60%) in linear case, irrelevant
in pseudo-random access
Inlining negligible (2%)
21/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Results
In terms of performance
Fully optimized inlined C code
Algorithm Integer Image Float Image
Assignment 0.29 0.29
Addition 0.48 0.47
Multiplication 0.48 0.46
Division 0.58 1.93
Not much difference between pixel types
Surprise: integer division should be costly
I
“Constant Integer Optimization” (with inlining)
I
Do not neglect inlining !
22/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
First shot at Lisp code
The add function, take 1
( defun add ( t o from v a l )
( l e t ( ( s i ze ( array−dimension t o 0 ) ) )
( dotimes ( i s i z e )
( setf ( ar e f t o i ) ( + ( ar ef from i ) v a l ) ) ) ) )
Common Lisp’s standard simple-array type
Interpreted version: 2300x
Compiled version: 60x
Optimized version: 20x
Untyped source code ⇒ dynamic type checking !
24/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Typing mechanisms
Typing paradigm:
I
Type information (Common Lisp standard)
Declare the expected types of Lisp objects
I
Type information is optional
Declare only what you know; give hints to the compilers
I
Both a statically and dynamically typed language
Typing mechanisms:
I
Function arguments:
(make-array size :element-type ’single-float)
I
Type declarations:
Function parameter / freshly bound local variable
I
. . .
25/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Typed Lisp code sample
Declaring the types of function parameters
The add function, take 2
( defun add ( t o from v a l )
( de c lare ( type ( simple−array s i n g l e − f l o a t ( ∗ ) ) to from ) )
( de c lare ( type s i n g l e − f l o a t v a l ) )
( l e t ( ( s i ze ( array−dimension t o 0 ) ) )
( dotimes ( i s i z e )
( setf ( ar e f t o i ) ( + ( ar ef from i ) v a l ) ) ) ) )
simple-array’s . . .
of single-float’s . . .
uni-dimensional.
26/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Object representation
Why typing matters for performance
Dynamic typing ⇒ objects of any type (worse: any size)
Lisp variables don’t carry type information: objects do
The “boxed” representation of Lisp objects
Type information
Pointer to Lisp Object
Actual value
Dynamic type checking is costly !
27/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
The benefits of typing
2 examples
Array storage layout:
I
Homogeneous arrays of a known type
⇒ native representation usable
I
Specialization of the aref function
I
“Open Coding”
Immediate objects:
I
Short (less than a memory word)
I
Special “tag bits” (invalid as pointer values)
I
⇒ Encoded inline
Unboxed fixnum representation
00
0
1
Tag bits
Bits 1 ... 29 30 31 32
fixnum value (30 bits)
28/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Typed Lisp code sample
Declaring the types of function parameters
The add function, take 2
( defun add ( t o from v a l )
( de c lare ( type ( simple−array s i n g l e − f l o a t ( ∗ ) ) to from ) )
( de c lare ( type s i n g l e − f l o a t v a l ) )
( l e t ( ( s i ze ( array−dimension t o 0 ) ) )
( dotimes ( i s i z e )
( setf ( ar e f t o i ) ( + ( ar ef from i ) v a l ) ) ) ) )
simple-array’s . . .
of single-float’s . . .
uni-dimensional.
29/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Example: optimizing a loop index
(dotimes (i 100) ...)
Disassembly of a dotimes macro
58701478: .ENTRY FOO( )
90: POP DWORD PTR [EBP−8]
93: LEA ESP, [ EBP−32]
96: XOR EAX, EAX
98: JMP L1
9A: L0 : ADD EAX, 4
9D : L1 : CMP EAX, 400
A2 : JL L0
A4 : MOV EDX, #x2800000B
A9 : MOV ECX, [ EBP−8]
AC: MOV EAX, [ EBP−4]
AF: ADD ECX, 2
B2 : MOV ESP, EBP
B4 : MOV EBP, EAX
B6 : JMP ECX
30/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Activating optimization
“Qualities” (Common Lisp standard): between 0 and 3
safety, speed etc.
Global or local declarations in source code
(no compiler flag)
Global qualities declaration
(declaim (optimize (speed 3)
(compilation-speed 0)
(safety 0)
(debug 0)))
Safe code: declarations treated as assertions
Optimized code: declarations trusted
31/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Final Lisp code sample
The add function
( defun add ( t o from v a l )
( de c lare ( type ( simple−array s i n g l e − f l o a t ( ∗ ) ) to from ) )
( de c lare ( type s i n g l e − f l o a t v a l ) )
( l e t ( ( s i ze ( array−dimension t o 0 ) ) )
( dotimes ( i s i z e )
( setf ( ar e f t o i ) ( + ( ar ef from i ) v a l ) ) ) ) )
CMU-CL (19c), SBCL (0.9.9), ACL (7.0)
Full optimization: (speed 3), 0 elsewhere
Array type: 1D, 2D
Array access: aref, row-major-aref, svref
32/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Comparative results
In terms of behavior
6= Plain 2D implementation much slower (2.8x ⇒ 4.5x)
= Linear access faster (30 times)
I
Same reasons, same behavior. . .
= Optimized code faster in linear case, irrelevant in
pseudo-random access
6= Gain more important in Lisp (3x ⇒ 5x)
6= Gain more important on floating point numbers
⇒ In Lisp, safety is costly
= Inlining negligible
6= No “Constant Integer Optimization”
6= Negative impact on performance (-15%), if any
⇒ Inlining still a “hot” topic (register allocation policies ?)
33/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Comparative results
In terms of performance
Pseudo-random access
Assignment Addition Multiplication Division
0
5
10
15
20
25
30
Execution time (seconds)
Rear to Front: ACL / SBCL / CMU-CL / C
Integer
Floating Point
Assignment: Lisp 19% faster than C
Other: insignificant (5%)
Exception: integer division
34/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Comparative results
In terms of performance
Linear access
Assignment Addition Multiplication Division
0
1
2
Execution time (seconds)
Rear to Front: ACL / SBCL / CMU-CL / C
Integer
Floating Point
ACL: poor performance
CMU-CL, SBCL: strictly equivalent to C
C wins on integer division, loses on floating-point one
35/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Type inference
A weakness of Common Lisp . . .
Static typing cumbersome (source code annotations)
I
Can we provide minimal type declarations . . .
I
. . . and rely on type inference ?
Incremental typing by compilation log examination
Unfortunately:
I
Compiler messages not necessarily ergonomic
I
Type inference systems not necessarily clever
37/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Example of (missing) type inference
multiply excerpt
; ; . . .
( de c lare ( type ( simple−array fixnum ( ∗ ) ) t o from ) )
( de c lare ( type fi xnum v a l ) )
; ; . . .
( setf ( ar e f t o i ) ( the fixnum (∗ ( ar ef from i ) v a l ) ) ) ) ) )
(
*
fixnum fixnum) 6= fixnum in general, but. . .
I
to declared as an array of fixnum’s,
I
so the multiplication has to return a fixnum
CMU-CL and SBCL ok, ACL not ok.
I
Need for further explicit type information
I
worse in ACL:
declared-fixnums-remain-fixnums-switch
38/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Conclusion
In terms of behavior
I
External parameters: no surprise
I
Internal parameters: differences, attenuated by
optimization
In terms of performance
I
Comparable results in both languages
I
Very smart Lisp compilers (given language
expressiveness)
However:
I
Typing can be cumbersome
I
Difficult to provide both correct and minimal information
(weakness of the Common Lisp standard)
I
Inlining is still an issue
39/77
Lisp
Didier Verna
Experiments
The case of C
The case of
Lisp
Raw Lisp
Typed Lisp
Results
Type inference
Conclusion
Perspectives
Low level: try other compilers / architectures
(and compiler / architecture specific optimization
settings)
Medium level: try more sophisticated algorithms
(neighborhoods, front-propagation)
High level: try different levels of genericity
(dynamic object orientation, static meta-programming)
Do not restrict to image processing
40/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Introduction
What are binary methods?
Binary Operation: 2 arguments of the same type
Examples: arithmetic / ordering relations (=, +, > etc.)
OO Programming: 2 objects of the same class
Benefit from polymorphism etc.
⇒ Hence the term binary method
However: [Bruce et al., 1995]
I
problematic concept in traditional OO languages
I
type / class relationship in the context of inheritance
43/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Table of contents
5 Binary Methods non-issues
Types, Classes, Inheritance
Corollary: method combinations
6 Enforcing the concept – usage level
Introspection
Binary function class
7 Enforcing the concept – implementation level
Misimplementations
Strong binary functions
44/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Types, Classes, Inheritance
Problem #1
The Point class UML hierarchy
equal (ColorPoint) : Boolean
color : String
x, y : Integer
equal (Point) : Boolean
Point
ColorPoint
46/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
C++ implementation attempt #1
Details omitted
The C++ Point class hierarchy
class P o i n t
{
i n t x , y ;
bool e qual ( Point& p )
{ ret urn x == p . x && y == p . y ; }
} ;
class C o l o r P o int : publ ic P o i nt
{
std : : s t r i n g c o l o r ;
bool e qual ( Color P o i n t& cp )
{ ret urn c o l o r == cp . c o l o r && P o int : : equal ( cp ) ; }
} ;
47/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
But this doesn’t work. . .
Overloading is not what we want
Looking through base class references
i n t main ( i n t argc , char ∗ argv [ ] )
{
Point& p1 = ∗ new ColorPoint ( 1 , 2 , " red " ) ;
Point& p2 = ∗ new ColorPoint ( 1 , 2 , " green " ) ;
std : : cou t << p1 . equal ( p2 ) << s td : : e nd l ;
/ / => True . #### Wrong !
}
ColorPoint::equal only overloads Point::equal
in the derived class
From the base class, only Point::equal is seen
What we want is to use the definition from the exact
class
48/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
C++ implementation attempt #2
Details still omitted
The C++ Point class hierarchy
class P o i n t
{
i n t x , y ;
v i r t u a l bool equal ( Point& p )
{ ret urn x == p . x && y == p . y ; }
} ;
class C o l o r P o int : publ ic P o i nt
{
std : : s t r i n g c o l o r ;
v i r t u a l bool equal ( C olorPo i n t& cp )
{ ret urn c o l o r == cp . c o l o r && P o int : : equal ( cp ) ; }
} ;
49/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
But this doesn’t work either. . .
Still got overloading, still not what we want
The forbidden fruit
v i r t u a l bool equal ( Point& p ) ;
v i r t u a l bool equal ( ColorPoint& cp ) ; / / #### Forbidden !
Invariance required on virtual methods argument types
Worse: here, the virtual keyword is silently ignored
And we get an overloading behavior, as before
Why? To preserve type safety
50/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Why the typing would be unsafe
And lead to errors at run-time
Example of run-time typing error
{
return p1.equal (p2);
}
bool foo (Point& p1, Point& p2)
But gets only a Point !The ColorPoint implementation
expects a ColorPoint argument
(ex. accesses the color field)
In fact, a ColorPoint Just a Point
51/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Constraints for type safety
covariance, contravariance. . . invariance
When subtyping a polymorphic method, we must
I
supertype the arguments (contravariance)
I
subtype the return value (covariance)
Note: C++ is even more constrained
I
The argument types must be invariant
Note: Eiffel allows for arguments covariance
I
But this leads to possible run-time errors
Analysis: [Castagna, 1995].
I
Lack of expressiveness
subtyping (by subclassing) 6= specialization
I
Object model defect
single dispatch (not the record-based model)
52/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
CLOS: the Common Lisp Object System
A different model
Methods vs. Generic Functions
I
C++ methods belong to classes
I
CLOS generic functions look like ordinary functions
(outside classes)
Single dispatch vs. Multi-Methods
I
C++ dispatch based on the first (hidden) argument type
(this)
I
CLOS dispatch based on the type of any number of
arguments
Note: a CLOS “method” is a specialized
implementation of a generic function
53/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
CLOS implementation
No detail omitted
The CLOS Point class hierarchy
( defclass p o i n t ( )
( ( x : i n i t a r g : x : re ader po int−x )
( y : i n i t a r g : y : re ader po in t−y ) ) )
( defclass c o l o r − p o i n t ( p o i n t )
( ( c o l o r : i n i t a r g : c o l o r : reader p o int−color ) ) )
; ; o p t i o n a l
( defgeneric p o i n t = ( a b ) )
( defmethod p o i n t = ( ( a p o i n t ) ( b p o i n t ) )
( and (= ( point −x a ) ( po int−x b ) )
(= ( point− y a ) ( poin t− y b ) ) ) )
( defmethod p o i n t = ( ( a c o l o r − p o i nt ) ( b c o l o r − p o i n t ) )
( and ( s t r ing= ( poi n t − c o l o r a ) ( p o i n t − color b ) )
( call−next−method ) ) )
54/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
How to use it?
Just like ordinary function calls
Using the generic function
( l e t ( ( p1 ( make−point : x 1 : y 2 ) )
( p2 ( make−point : x 1 : y 2 ) )
( cp1 ( make−color−point : x 1 : y 2 : c o l o r " red " ) )
( cp2 ( make−color−point : x 1 : y 2 : c o l o r " green " ) ) )
( values ( p o i n t = p1 p2 )
( p o i n t = cp1 cp2 ) ) )
; ; => ( T NIL )
Proper method selected based on both arguments
(multiple dispatch)
Function call syntax, more pleasant aesthetically
(p1.equal(p2) or p2.equal(p1)?)
⇒ Hence the term binary function
55/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Applicable methods
There are more than one. . .
To avoid code duplication:
I
C++: Point::equal()
I
CLOS: (call-next-method)
Applicable methods:
I
All methods compatible with the arguments classes
I
Sorted by (decreasing) specificity order
I
call-next-method calls the next most specific
applicable method
Method combinations:
I
Ways of calling several (all) applicable methods
(not just the most specific one)
I
Predefined method combinations: and, or, progn etc.
I
User definable
56/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
C++ implementation attempt #1
Details omitted
The C++ Point class hierarchy
class P o i n t
{
i n t x , y ;
bool e qual ( Point& p )
{ ret urn x == p . x && y == p . y ; }
} ;
class C o l o r P o int : public P o i n t
{
std : : s t r i n g c o l o r ;
bool e qual ( Color P o i n t& cp )
{ ret urn c o l o r == cp . c o l o r && P o int : : equal ( cp ) ; }
} ;
57/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
CLOS implementation
No detail omitted
The CLOS Point class hierarchy
( defclass p o i n t ( )
( ( x : i n i t a r g : x : re ader po int−x )
( y : i n i t a r g : y : re ader po in t−y ) ) )
( defclass c o l o r − p o i n t ( p o i n t )
( ( c o l o r : i n i t a r g : c o l o r : reader p o int−color ) ) )
; ; o p t i o n a l
( defgeneric p o i n t = ( a b ) )
( defmethod p o i n t = ( ( a p o i n t ) ( b p o i n t ) )
( and (= ( point −x a ) ( po int−x b ) )
(= ( point− y a ) ( poin t− y b ) ) ) )
( defmethod p o i n t = ( ( a c o l o r − p o i nt ) ( b c o l o r − p o i n t ) )
( and ( s t r ing= ( poi n t − c o l o r a ) ( p o i n t − color b ) )
( call−next−method ) ) )
58/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Applicable methods
There are more than one. . .
To avoid code duplication:
I
C++: Point::equal()
I
CLOS: (call-next-method)
Applicable methods:
I
All methods compatible with the arguments classes
I
Sorted by (decreasing) specificity order
I
call-next-method calls the next most specific
applicable method
Method combinations:
I
Ways of calling several (all) applicable methods
(not just the most specific one)
I
Predefined method combinations: and, or, progn etc.
I
User definable
59/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Using the and method combination
Comes in handy for the equality concept
The and method combination
( defgeneric p o i n t = ( a b )
( : method−combination and )
)
( defmethod p o i n t = and ( ( a p o i n t ) ( b po i n t ) )
( and (= ( point −x a ) ( po int−x b ) )
(= ( point− y a ) ( poin t− y b ) ) ) )
( defmethod p o i n t = and ( ( a c o l o r − p o int ) ( b c o l o r − p o i n t ) )
( and ( call−next−method )
( st r i ng= ( point−c o l o r a ) ( po i n t − c o l o r b ) )
)
)
⇒ In CLOS, the generic dispatch is (re-)programmable
60/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Binary methods could be misused
Can we protect against it?
The point= function used incorrectly
( l e t ( ( p ( make−point : x 1 : y 2 ) )
( cp ( make−color−point : x 1 : y 2 : c o l o r " red " ) ) )
( p o i n t = p cp ) )
; ; => T #### Wron g !
(point= <point> <point>) is an applicable
method (because a color-point is a point)
⇒ The code above is valid
⇒ And the error goes unnoticed
62/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Introspection in CLOS
Inquiring the class of an object
Using the function class-of
( assert ( eq ( cla ss−of a ) ( class− of b ) ) )
When to perform the check?
I
In all methods: code duplication
I
In the basic method: not efficient
I
In a before-method: not available with the and
method combination
I
In a user-defined method combination: not the place
Where to perform the check? (a better question)
I
Nowhere near the code for point=
I
Part of the binary function concept, not point=
⇒ We should implement the binary function concept
I
A specialized class of generic function?
63/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
The CLOS Meta-Object Protocol
aka the CLOS MOP
CLOS itself is object-oriented
I
The CLOS MOP: a de facto implementation standard
I
The CLOS components (classes etc.) are
(meta-)objects of some (meta-)classes
I
Generic functions are meta-objects of the
standard-generic-function meta-class
⇒ We can subclass standard-generic-function
The binary-function meta-class
( defclass b i n a r y − f u n c t i o n ( stan dar d−g ene ric − fu nct ion )
( )
( : metaclas s f u ncal l able − stan d a rd− c l ass ) )
( defmacro d e f b i n a r y ( function−name lam bda − lis t &r est options )
‘ ( defgeneric , function−name , l a mbd a−l i st
( : g ener ic−f u nct i on−c lass b i n a r y − f u n c tion )
, @options ) )
64/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Back to introspection
Hooking the check
Calling a generic function involves:
I
Computing the list of applicable methods
I
Sorting and combining them
I
Calling the resulting effective method
compute-applicable-methods-using-classes
I
Does as its name suggests
I
Based on the classes of the arguments
I
A good place to hook
We can specialize it!
I
It is a generic function . . .
Specializing the c-a-m-u-c generic function
( defmethod c−a−m−u−c : bef ore ( ( b f b i n a r y − f u n c t i o n ) c las ses )
( assert ( equal ( ca r c l ass es ) ( ca dr cla sse s ) ) ) )
65/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Binary methods could be misimplemented
Can we protect against it?
We protected against calling
(point= <point> <color-point>)
Can we protect against implementing it?
add-method
I
Registers a new method (created with defmethod)
I
We can specialize it!
•
It is a generic function . . .
Specializing the add-method generic function
( defmethod add−method : befo re ( ( b f b i n a r y − f u n c t i o n ) method )
( assert ( apply # ’ equal ( m ethod −sp ecial izers method ) ) ) )
67/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Binary methods could be forgotten
Can we protect against it?
Strong binary functions:
I
Every subclass of point should specialize point=
I
Late checking: at generic function call time
(preserve interactive development)
Binary completeness:
1 There is a specialization on the arguments’ exact class
2 There are specializations for all super-classes
Introspection:
I
Binary completeness of the list of applicable methods
I
c-a-m-u-c returns this!
Hooking the check
( defmethod c−a−m−u−c ( ( b f b i n a r y − f u n c t i o n ) c las ses )
( m ult ipl e−v alu e−b ind ( methods ok ) ( call−next−method )
; ; . . .
( values methods ok ) ) )
68/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Is there a bottommost specialization?
Check #1
classes = ’(<exact> <exact>)
method-specializers returns the arguments
classes from the defmethod call
⇒ We should compare <exact> with the specialization
of the first applicable method
Check #1
( l e t ∗ ( ( method ( c ar methods ) )
( cl a s s ( car ( m ethod −spec ializ ers method ) ) ) )
( assert ( equal ( l i s t c l a s s c l a s s ) cla sse s ) )
; ; . . .
)
69/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Are there specializations for all super-classes?
Check #2
find-method retrieves a generic function’s method
given a set of qualifiers / specializers
method-qualifiers does as its name suggests
class-direct-superclasses as well
Check #2
( l a bel s ( ( check−binary−completeness ( clas s )
( find−method bf ( meth o d −qua l i fier s method )
( l i s t c l a s s c l a s s ) )
( d o l i s t
( c l s ( remove−if
# ’ ( lambda ( e l t )
( eq e l t ( find − c l a s s
’ s ta nda rd− ob jec t ) ) )
( cla s s−d i rec t −su p erc l ass es c lass ) ) )
( check−binary−completeness c l s ) ) ) )
( check−binary−completeness class ) )
70/77
Lisp
Didier Verna
Introduction
Non-issues
Types, Classes,
Inheritance
Method comb.
Usage
Introspection
Binary function class
Implementation
Misimplementations
Strong bin. functions
Conclusion
Conclusion
Binary methods problematic in traditional OOP
Multi-methods as in CLOS remove the problem
CLOS and the CLOS MOP let you support the concept:
I
make it available
I
ensure a correct usage
I
ensure a correct implementation
But the concept is implemented explicitly
I
CLOS is not just an object system
I
CLOS is not even just a customizable object system
CLOS is an object system designed to let you program
new object systems
71/77
Lisp
Didier Verna
Conclusion
Resources
Events
Lisp satisfies
Alive and kicking
Lisp is a truely multi-paradigm programming language
Probably the most versatile of them
Lisp is the language of freedom
PPP: Permissive Programming Paradigm
Freedom means more ways to shoot yourself in the foot
But also the ability to be extremely defensive if you
want to
72/77
Lisp
Didier Verna
Conclusion
Resources
Events
Articles
Bruce, K. B., Cardelli, L., Castagna, G., Eifrig, J., Smith, S. F.,
Trifonov, V., Leavens, G. T., and Pierce, B. C. (1995).
On binary methods.
Theory and Practice of Object Systems, 1(3):221–242.
Castagna, G. (1995).
Covariance and contravariance: conflict without a cause.
ACM Transactions on Programming Languages and
Systems, 17(3):431–447.
Verna, D. (2006).
Beating C in scientific computing applications.
In Third European Lisp Workshop at ECOOP, Nantes, France.
Verna, D. (2008).
Binary methods: the CLOS perspective.
To appear in First European Lisp Symposium, Bordeaux,
France.
74/77
Lisp
Didier Verna
Conclusion
Resources
Events
Next Events
1st European Lisp Symposium, May 22-23 2008,
Bordeaux, France.
http://prog.vub.ac.be/~pcostanza/els08/
5th European Lisp Workshop, July 7 2008, Cyprus,
co-located with ECOOP.
http://elw.bknr.net/2008
Next International Lisp Conference . . . 2009
MIT, Cambridge
76/77
