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