www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Clojure Protocols & expression problem

reply bearophile <bearophileHUGS lycos.com> writes:
A short video about Clojure 1.2 Protocols, created to solve the expression
problem (that D doesn't solve well yet), they are like fake multimetods because
they are like single dispatch :-) (So they need just a virtual table, that the
JavaVM can optimize well):

http://vimeo.com/11236603

By the way, you can see an example of the expression problem here, this is D
code that solves one case of it:
http://codepad.org/RPw6Kxu6

This is the same in Python with the multimethod (module inlined at the top),
it's similar to CLisp CLOS solution:
http://codepad.org/tWsYomoZ

Bye,
bearophile
Apr 28 2010
next sibling parent reply BCS <none anon.com> writes:
Hello bearophile,



 By the way, you can see an example of the expression problem here,


Could you elaborate on what exactly the expression problem is?


-- 
... <IXOYE><
Apr 28 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
BCS:


Could you elaborate on what exactly the expression problem is?<


I am far from being an expert on such matters, I will do what I can to answer.
It's not an esoteric problem, if you program with an OO language you have
probably faced it sometime.

I think it's one of the two most important OOP problems not yet solved by D.
And I think it deserves some thinking. But it can be work for the design of the
D3 language.

Curiously one of the original design goals of Scala was to "solve" the
expression problem.

(The other basic OO problem not currently solved by D2 is the
variance/covariance of collections that contain objects (like arrays). There is

syntax to face this problem, and recently I've sent Andrei the URL of an
article that shows how Scala faces and solves this problem in its collections.)

You can see a canonical example of this problem in the D and Python code I've
shown in my original post. In OO languages simpler than Scala and CLisp+CLOS
the expression problem is sometimes solved using this pattern, the same I've
used in the D code:
http://en.wikipedia.org/wiki/Visitor_pattern

The have discussed it a little here:
http://lambda-the-ultimate.org/node/2232

You can find some info relative to C++ solutions here too:
http://www.mpi-inf.mpg.de/~kettner/courses/lib_design_03/notes/advanced.html#DoubleDispatch

More on the same in C++:
http://lambda-the-ultimate.org/node/2590
It contains a paper from Bjarne Stroustrup too:
http://www.research.att.com/~bs/multimethods.pdf

In the Python code I have used multiple (double) dispatch to solve it,
hopefully better.

Bye,
bearophile
Apr 28 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Maybe it's better if I actually give a bit of answer too to your question.

If you take a look at my D code, you can see there are many kinds of car parts,
and two different kind of "visits" of them, that perform different operations
on them.

The problem is, what does it happen in the code if I want to define one (or
more) new car parts? What does it happen if I want to add one (or more) more
kind of visits? You can slice the design of all this program "vertically" or
"horizontally". One design makes it easy to add more car parts, the other
design makes it more easy to add "visits".

In the Python code you can see I have used double dispatch. I can define any
combination of car part and "visit", they are separated (and in Python there is
no need to recompile). CommonLisp has an OO system named CLOS that offers the
same power of that python solution.

Bye,
bearophile
Apr 28 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
According to the paper from Bjarne Stroustrup:
http://www.research.att.com/~bs/multimethods.pdf

this is a possible syntax D3 can use for the double dispatch:
void foo( virtual A a,  virtual B b) {}

Bye,
bearophile
Apr 28 2010
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
bearophile wrote:


 According to the paper from Bjarne Stroustrup:
 http://www.research.att.com/~bs/multimethods.pdf
 
 this is a possible syntax D3 can use for the double dispatch:
 void foo( virtual A a,  virtual B b) {}
 
 Bye,
 bearophile


I have studied this paper a bit once, it's good. It also shows that their 
multimethod implementation is faster than the visitor pattern. I would love 
to never see a visitor pattern again, it really sucks compared to 
multimethods. 

I think we can first try to make a multimethods library, and we need only one 
addition to __traits ( to get the overloads of free / static functions) for 
*open* multimethods. 

I tried it once but found it not that easy. It should be possible to have a 
(perhaps slow) proof of concept that rivals the python example you gave in 
conciseness.
Apr 28 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Lutger:


I would love to never see a visitor pattern again, it really sucks compared to
multimethods.<


You are probably more qualified than me to answer the original question by BCS
:-)
Multimethods are easy to use and understand (if you don't mix them with too
many other things).



I think we can first try to make a multimethods library,<


Seems a good idea.



and we need only one addition to __traits ( to get the overloads of free /
static functions) for *open* multimethods.<


So far I think DMD has progressed in mostly a linear way, but a temporary
experimental dmd branch with this change can be useful to test, try and
benchmark this feature. When possible I prefer true experiments.

Thank you for your answer,
bearophile
Apr 28 2010
prev sibling parent reply retard <re tard.com.invalid> writes:
Wed, 28 Apr 2010 13:22:53 -0400, bearophile wrote:


 BCS:
 

Could you elaborate on what exactly the expression problem is?<


 
 I am far from being an expert on such matters, I will do what I can to
 answer. It's not an esoteric problem, if you program with an OO language
 you have probably faced it sometime.


You failed to mention that the OOP solution is in many cases overly 
complex. When you don't need to subclass the car elements, a functional 
pattern matching happens to win - at least if the declarativeness of code 
matters. The implementation can also use jump tables so it becomes faster 
than double dispatch. Luckily D is never going to get algebraic data 
types so you can all stop reading this post right here.

data CarElement = Wheel Name
                | Engine
                | Body
                | Car [CarElement]

defaultCar = Car [ Wheel "front left"
                 , Wheel "front right"
                 , Wheel "back left"
                 , Wheel "back right"
                 , Body
                 , Engine
                 ]

makeVisitor f element = map f (case element of
   Car elements = element : elements
   _            = [element]
)


visitor element = case element of
   Wheel name = "Visiting " +++ name +++ " wheel"
   Engine     = "Visiting engine"
   Body       = "Visiting body"
   Car _      = "Visiting car"

doVisitor element = case element of
   Wheel name = "Kicking my " +++ name +++ " wheel"
   Engine     = "Starting my engine"
   Body       = "Moving my body"
   Car _      = "Starting my car"

-- an example of usage:

-- makeVisitor visitor default
-- makeVisitor doVisitor default
Apr 28 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/28/2010 06:28 PM, retard wrote:

 Wed, 28 Apr 2010 13:22:53 -0400, bearophile wrote:


 BCS:


 Could you elaborate on what exactly the expression problem is?<


 I am far from being an expert on such matters, I will do what I can to
 answer. It's not an esoteric problem, if you program with an OO language
 you have probably faced it sometime.


 You failed to mention that the OOP solution is in many cases overly
 complex. When you don't need to subclass the car elements, a functional
 pattern matching happens to win - at least if the declarativeness of code
 matters. The implementation can also use jump tables so it becomes faster
 than double dispatch. Luckily D is never going to get algebraic data
 types so you can all stop reading this post right here.


I'm having trouble picturing the following scenario for a day in life.

* Wake up

* Shave

* Eat

* Drink coffee

* Go to work

* Do cool stuff

* Spend time reading and posting one bitter remark after another on a 
newsgroup dedicated to a language that I hate, I'm not required to use, 
I have no interest to see succeed, and I strongly believe breaks just 
about every single principle of good language design

* Back home

* Fun with girlfriend, wife, kids, TV, pet projects, etc.

* Eat

* Beer

* Sleep

One of these things is unlike the others!


Andrei
Apr 28 2010
next sibling parent reply retard <re tard.com.invalid> writes:
Wed, 28 Apr 2010 18:34:44 -0500, Andrei Alexandrescu wrote:


 On 04/28/2010 06:28 PM, retard wrote:

 Wed, 28 Apr 2010 13:22:53 -0400, bearophile wrote:


 BCS:


 Could you elaborate on what exactly the expression problem is?<


 I am far from being an expert on such matters, I will do what I can to
 answer. It's not an esoteric problem, if you program with an OO
 language you have probably faced it sometime.


 You failed to mention that the OOP solution is in many cases overly
 complex. When you don't need to subclass the car elements, a functional
 pattern matching happens to win - at least if the declarativeness of
 code matters. The implementation can also use jump tables so it becomes
 faster than double dispatch. Luckily D is never going to get algebraic
 data types so you can all stop reading this post right here.


 
 I'm having trouble picturing the following scenario for a day in life.
 
 [snipped a very precise description of someone's life]
 
 One of these things is unlike the others!
 
 
 Andrei


:) Sorry, but I actually have to use D. We long ago started some D 
projects and have to maintain them now (ok, this sounds worse than it 
really is - it's a joy compared to the xml bloat of j2ee and terribly bad 
design of php!). I also often fire up dmd to test some more or less 
trivial piece of code since I need the native codegen capabilities of the 
language so I really do have use for it. So, tyvm for the work so far, it 
has been really useful.

I also try to keep the amount of factual information on my posts above 
the level of bitterness. (I should probably refrain from posting at all 
if it annoys too much.) After all, there might be some hope that it 
educates the community as a large and puts some pressure on you to stop 
breaking the principles of good language design. Fwiw, it would calm some 
of the most demanding users of the language if there was a well 
documented process behind design decisions. I haven't heard any good 
arguments e.g. against algebraic data types other than "it confuses some 
novice C users".
Apr 28 2010
parent reply Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:

 :) Sorry, but I actually have to use D.


I'm sorry you'd have to use D if you don't want to, but it is a positive sign 
that D is catching on in the business world.
Apr 29 2010
parent reply retard <re tard.com.invalid> writes:
Thu, 29 Apr 2010 10:21:15 -0700, Walter Bright wrote:


 retard wrote:

 :) Sorry, but I actually have to use D.


 
 I'm sorry you'd have to use D if you don't want to, but it is a positive
 sign that D is catching on in the business world.


It's positive that you sometimes write a reply. What saddens me is it's 
mostly about *my* personal issues.

I've always given at least two ways to continue the discussion. The posts 
also contain valid technical issues, much more than some of the most 
desperate bikeshedding here. It's sad that instead of improving the 
language and enriching the intellectual capacity of the active members, 
you concentrate on ad-hoc personal attacks and on the most irrelevant 
parts of the posts.

I wonder what is causing all this. Have you started to consider everyone 
with knowledge about programming languages a threat? Wanna hear my 
secret? After 8 hours of sleep, 8 hours of daily job, and 3 to 4 hours of 
other chores, I have a small amount of time to read reddit [1], 
wikipedia, blogspot [2], and sometimes the abstracts (and if it makes any 
sense, perhaps part of the discussion) from LtU [3]. Maybe also 2 to 3 
larger PL related books (e.g. [4]) per year. If I still have more spare 
time, I might read the newsgroup here or write some code. That's about it 
- a rather harmless hobby. If that places me to the ivory tower along 
with bearded, funny looking, smelly old men, I should probably take heed 
and spend more time lifting weights or something more useful.

Certainly I'm a bit bitter, but I didn't start the fight afaict. The 
community kind of lost its innocent blissful state long ago after some 
unfortunate events.

[1] for example, part of what I read today http://img88.imageshack.us/
img88/5559/redditposts.png

[2] mostly posts by some bright guys like james iry ( http://james-
iry.blogspot.com/ )

[3] http://lambda-the-ultimate.org/

[4] http://www.pragprog.com/titles/shcloj/programming-clojure
Apr 29 2010
next sibling parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
Walter, you shouldn't be apologizing to retard. These personal attacks 
are just not acceptable on a public forum and coming from an adult.

Instead, I think you should be more like him.

On 04/29/2010 03:25 PM, retard wrote:

 Thu, 29 Apr 2010 10:21:15 -0700, Walter Bright wrote:


 I'm sorry you'd have to use D if you don't want to, but it is a positive
 sign that D is catching on in the business world.


 It's positive that you sometimes write a reply. What saddens me is it's
 mostly about *my* personal issues.

 I've always given at least two ways to continue the discussion. The posts
 also contain valid technical issues, much more than some of the most
 desperate bikeshedding here. It's sad that instead of improving the
 language and enriching the intellectual capacity of the active members,
 you concentrate on ad-hoc personal attacks and on the most irrelevant
 parts of the posts.

 I wonder what is causing all this. Have you started to consider everyone
 with knowledge about programming languages a threat? Wanna hear my
 secret? After 8 hours of sleep, 8 hours of daily job, and 3 to 4 hours of
 other chores, I have a small amount of time to read reddit [1],
 wikipedia, blogspot [2], and sometimes the abstracts (and if it makes any
 sense, perhaps part of the discussion) from LtU [3]. Maybe also 2 to 3
 larger PL related books (e.g. [4]) per year. If I still have more spare
 time, I might read the newsgroup here or write some code. That's about it
 - a rather harmless hobby. If that places me to the ivory tower along
 with bearded, funny looking, smelly old men, I should probably take heed
 and spend more time lifting weights or something more useful.

 Certainly I'm a bit bitter, but I didn't start the fight afaict. The
 community kind of lost its innocent blissful state long ago after some
 unfortunate events.

 [1] for example, part of what I read today http://img88.imageshack.us/
 img88/5559/redditposts.png

 [2] mostly posts by some bright guys like james iry ( http://james-
 iry.blogspot.com/ )

 [3] http://lambda-the-ultimate.org/

 [4] http://www.pragprog.com/titles/shcloj/programming-clojure
Apr 29 2010
parent retard <re tard.com.invalid> writes:
Thu, 29 Apr 2010 15:34:15 -0500, Ellery Newcomer wrote:


 Walter, you shouldn't be apologizing to retard. These personal attacks
 are just not acceptable on a public forum and coming from an adult.
 
 Instead, I think you should be more like him.


I think this whole thing is seriously getting out of hand. My wish was to 
stop talking about me and concentrate more on D. After all, this 
newsgroup *is* about D. Yet, the first reply is yet another post about 
me. There seems to be no other way than to disappear. I thought the old 
dust would eventually settle, but it apparently never did.

As a side note, if the "be more like him" means more aggressive attitude 
against opinions you don't personally like, the advice is highly damaging 
to the social atmosphere. Even if I disagree with people, I never provoke 
hate. I think a community can tolerate one immature person every now and 
then - it might really be the case that he/she has some personal (mental) 
issues. To ease your pain, I've already deleted a large part of my 
previous posts. Unfortunately I have no access to the archiving system so 
the web interface still shows them.
Apr 29 2010
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:

 I wonder what is causing all this. Have you started to consider everyone 
 with knowledge about programming languages a threat?


There are several ideas posted here a day, far more than could ever be 
implemented in D, or even that could be thoroughly and fairly discussed by one 
person. It's just impossible.

What's gold, though, is actual quality code coming along with a proposal.

In other words, you're always welcome to come here and post your ideas, and
join 
in the discussions. A little good-natured ribbing is fine, too. If you want to 
put the effort into making a serious proposal, please do so and post it to 
bugzilla as an enhancement request. If you really want to help, posting an 
implementation along with it is even better!
Apr 29 2010
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 I'm having trouble picturing the following scenario for a day in life.


After your experience with Loki, what do you think about double dispatch in
external functions in D3?

Bye,
bearophile
Apr 28 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/28/2010 07:38 PM, bearophile wrote:

 Andrei Alexandrescu:

 I'm having trouble picturing the following scenario for a day in
 life.


 After your experience with Loki, what do you think about double
 dispatch in external functions in D3?


Good question. Statistically, I'd say very few people are interested in 
double dispatch. I've received reams of feedback from readers. Only a 
couple inquired or mentioned the double dispatch chapter at all. This is 
a bit odd because I think Loki's offering for double dispatch is 
comprehensive. It also had a few bugs in it that went unnoticed for a 
long time, which to me suggest very few actually needed that code.

Of course that's just a data point of sorts.

If we're to discuss double dispatch, I think we should first look at 
library solutions and at ways to improve the language to allow general 
solutions to categories of problems instead of cutesies like  virtual 
function parameters.

Above all, I think at this time we should go with improving the language 
definition and the quality of the compiler. There are quite a few 
strident notes in the current definition. Overloading is not taken care 
of properly, protection levels are underspecified and underimplemented, 
property syntax is broken, tuples are a mess. Also there's no 64-bit 
implementation. All that stuff is important and relatively urgent.


Andrei
Apr 28 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:


 Good question. Statistically, I'd say very few people are interested in 
 double dispatch.


I see. I'd like to know what CLOS (CLisp) users too think about this.

(Generally if a feature become syntactically clean and nice, and it's written
in the manual, surely more people can find the desire to use it. But this is
just speculation.)



 If we're to discuss double dispatch, I think we should first look at 
 library solutions and at ways to improve the language to allow general 
 solutions to categories of problems instead of cutesies like  virtual 
 function parameters.


In this case I agree that it's positive to first look for library solutions,
and eventually, if seen fitting, think about moving something to the built-in
features (see the answer I've written for Lutger).

Regarding the 'cutesies', I am irrevocably spoiled by Python and ShedSkin :-)
My work on ShedSkin has shown me once and for all that a fast language and a
very nice syntax are not incompatible things.

To give you a more focused answer, it's a matter of design balances. Tidy and
specialized solutions are often nicer syntax-wise, and simpler to use. Such
tidiness helps average-level programmers find the will to actually use them.
Too much general solutions become like Rubik cubes that need a little too much
assembly and brain to be used. But they can't be adapted to very different
situations, etc. So in designing the language you must be balanced. Python
shows that very well designed cutesies too can go a long way.



 Above all, I think at this time we should go with improving the language 
 definition and the quality of the compiler.


You have noticed I have asked this question regarding D3. I agree that now
there is enough work to do to produce a working D2 version.

You probably remember that recently I have shown in this newsgroup a list of
little/tiny breaking changes (from some of my Bugzilla reports) to be
discussed/addressed/fixed that I believe can be useful/necessary to create a
good D2 implementation. They are surely more urgent than double dispatch.
Despite this, I like to discuss here about all things.

Bye and thank you,
bearophile
Apr 28 2010
parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2010-04-28 21:39:41 -0400, bearophile <bearophileHUGS lycos.com> said:


 Andrei Alexandrescu:
 

 Good question. Statistically, I'd say very few people are interested in
 double dispatch.


 
 I see. I'd like to know what CLOS (CLisp) users too think about this.
 
 (Generally if a feature become syntactically clean and nice, and it's 
 written in the manual, surely more people can find the desire to use 
 it. But this is just speculation.)


I think you're correct on that.

I'll point out that categories in Objective-C are used all the time and 
basically solve the same group of problem double dispatch does, but 
also have other uses. I think being able to attach your own extension 
methods to an existing class (methods you can override in subclass, or 
extensions to subclasses) is a much easier concept to grasp than double 
dispatch. The feature being used a lot in the standard library surely 
helps too.


-- 
Michel Fortin
michel.fortin michelf.com
http://michelf.com/
Apr 28 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Michel Fortin:


is a much easier concept to grasp than double dispatch.<


It's not hard to think about double dispatch, you can see it like a special
case of function overload, where the language somehow allows you to overload on
the base of the dynamic type of two objects. Things gets less easy to
understand when you add inheritance into this mix.

Bye,
bearophile
Apr 29 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 04/29/2010 04:16 AM, bearophile wrote:

 Michel Fortin:


 is a much easier concept to grasp than double dispatch.<


 It's not hard to think about double dispatch, you can see it like a special
case of function overload, where the language somehow allows you to overload on
the base of the dynamic type of two objects. Things gets less easy to
understand when you add inheritance into this mix.


s/overload/override/g

Andrei
Apr 29 2010
prev sibling parent reply retard <re tard.com.invalid> writes:
Wed, 28 Apr 2010 16:44:07 +0000, BCS wrote:


 Hello bearophile,
 
 

 By the way, you can see an example of the expression problem here,


 
 Could you elaborate on what exactly the expression problem is?


Learning the use of a search engine would help you greatly in your life:

=> http://www.google.fi/search?q=expression+problem

=> http://en.wikipedia.org/wiki/Expression_Problem

Some academic discussion can also be found:

=> http://lambda-the-ultimate.org/node/2232

But you've probably all (at least nick) blocked the domain since it 
contains too much academic nonsense coming from the ivory towers.
Apr 28 2010
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
retard wrote:


 Wed, 28 Apr 2010 16:44:07 +0000, BCS wrote:
 

 Hello bearophile,
 
 

 By the way, you can see an example of the expression problem here,


 
 Could you elaborate on what exactly the expression problem is?


 
 Learning the use of a search engine would help you greatly in your life:
 
 => http://www.google.fi/search?q=expression+problem
 
 => http://en.wikipedia.org/wiki/Expression_Problem
 
 Some academic discussion can also be found:
 
 => http://lambda-the-ultimate.org/node/2232
 
 But you've probably all (at least nick) blocked the domain since it
 contains too much academic nonsense coming from the ivory towers.


=> http://en.wikipedia.org/wiki/Persecution_complex
Apr 28 2010
parent Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
On 04/28/2010 01:15 PM, Lutger wrote:

 retard wrote:


 Wed, 28 Apr 2010 16:44:07 +0000, BCS wrote:


 Hello bearophile,



 By the way, you can see an example of the expression problem here,


 Could you elaborate on what exactly the expression problem is?


 Learning the use of a search engine would help you greatly in your life:

 =>  http://www.google.fi/search?q=expression+problem

 =>  http://en.wikipedia.org/wiki/Expression_Problem

 Some academic discussion can also be found:

 =>  http://lambda-the-ultimate.org/node/2232

 But you've probably all (at least nick) blocked the domain since it
 contains too much academic nonsense coming from the ivory towers.


 =>  http://en.wikipedia.org/wiki/Persecution_complex


Good one
Apr 28 2010
prev sibling parent Don <nospam nospam.com> writes:
bearophile wrote:

 A short video about Clojure 1.2 Protocols, created to solve the expression
problem (that D doesn't solve well yet), they are like fake multimetods because
they are like single dispatch :-) (So they need just a virtual table, that the
JavaVM can optimize well):
 
 http://vimeo.com/11236603
 
 By the way, you can see an example of the expression problem here, this is D
code that solves one case of it:
 http://codepad.org/RPw6Kxu6
 
 This is the same in Python with the multimethod (module inlined at the top),
it's similar to CLisp CLOS solution:
 http://codepad.org/tWsYomoZ
 
 Bye,
 bearophile


Has anyone tried to solve the expression problem by using opDispatch?
Apr 29 2010