Re: seeking ideas for short lecture on type classes
In a fit of madness, I have agreed to deliver a 50-minute lecture on type classes to an audience of undergraduate students. These students will have seen some simple typing rules for F2 and will have some exposure to Hindley-Milner type inference in the context of ML.
Will they have had exposure to more "traditional" OO programming? If so, it might be useful to note the difference between Haskell type classes and C++/Java/whatever classes, namely that Haskell decouples types and the interfaces that they support. The advantage is that you can extend a type with a new interface at any point, not just when you define the type.
Hmm --- you are talking about the `instance' declarations, right? A fact that I know but don't understand the implication of is that Haskell dispatches on the static type of a value, whereas OO languages dispatch on the dynamic type of a value. But I suspect I'll leave that out :-) N
On Sun, 26 Jan 2003, Norman Ramsey wrote:
In a fit of madness, I have agreed to deliver a 50-minute lecture on type classes to an audience of undergraduate students. These students will have seen some simple typing rules for F2 and will have some exposure to Hindley-Milner type inference in the context of ML.
Will they have had exposure to more "traditional" OO programming? If so, it might be useful to note the difference between Haskell type classes and C++/Java/whatever classes, namely that Haskell decouples types and the interfaces that they support. The advantage is that you can extend a type with a new interface at any point, not just when you define the type.
Hmm --- you are talking about the `instance' declarations, right?
A fact that I know but don't understand the implication of is that Haskell dispatches on the static type of a value, whereas OO languages dispatch on the dynamic type of a value. But I suspect I'll leave that out :-)
Perhaps I misunderstand, but I would suggest that "fact" is, if not incorrect, at least oversimplified. I would say Haskell dispatches on the dynamic type of a value, in the sense that a single polymorphic function varies its behavior based on the specific type(s) of its argument(s). What may distinguish Haskell from typical OO languages (I'm not an expert on them) is that in Haskell such polymorphic functions could (always or at least nearly so) be specialized statically for their uses at different types. Dean
On Sun, 26 Jan 2003 19:07:01 -0500 (EST) Dean Herington <heringto@cs.unc.edu> wrote:
What may distinguish Haskell from typical OO languages (I'm not an expert on them) is that in Haskell such polymorphic functions could (always or at least nearly so) be specialized statically for their uses at different types.
Without existential types, one big difference from an OO language and haskell is that in haskell you can't have a datastructure such as a list, made up of elements of a certain type class but of different types, whereas in an OO language (say eiffel) you can have a List[A] wich can contain any sublcass of A. In general, even with existential types, haskell lacks a subtype relation. I always wonder if there really is no need for subtypes (and would appreciate any pointer to a discussion on the topic). Vincenzo -- Fedeli alla linea, anche quando non c'è Quando l'imperatore è malato, quando muore,o è dubbioso, o è perplesso. Fedeli alla linea la linea non c'è. [CCCP]
On 26-Jan-2003, Dean Herington <heringto@cs.unc.edu> wrote:
On Sun, 26 Jan 2003, Norman Ramsey wrote:
A fact that I know but don't understand the implication of is that Haskell dispatches on the static type of a value, whereas OO languages dispatch on the dynamic type of a value. But I suspect I'll leave that out :-)
Perhaps I misunderstand, but I would suggest that "fact" is, if not incorrect, at least oversimplified.
I agree. The above characterization is highly misleading. It would be more accurate and informative to say that both Haskell and OO languages dispatch on the dynamic type of a value. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
On Mon, Jan 27, 2003 at 08:37:06PM +1100, Fergus Henderson wrote:
I agree. The above characterization is highly misleading. It would be more accurate and informative to say that both Haskell and OO languages dispatch on the dynamic type of a value.
What is the "dynamic type of a value" in Haskell, apart from existentials and Dynamic? Ordinary type class dispatch is all done based on the types of variables, not their values. All the dispatching could even be done at compile time by specializing everything... Lauri Alanko la@iki.fi
On Mon, Jan 27, 2003 at 12:25:52PM +0200, Lauri Alanko wrote:
On Mon, Jan 27, 2003 at 08:37:06PM +1100, Fergus Henderson wrote:
I agree. The above characterization is highly misleading. It would be more accurate and informative to say that both Haskell and OO languages dispatch on the dynamic type of a value.
What is the "dynamic type of a value" in Haskell, apart from existentials and Dynamic? Ordinary type class dispatch is all done based on the types of variables, not their values. All the dispatching could even be done at compile time by specializing everything...
I don't think this is true, even without existential types. Polymorphic recursion may involve building dictionaries at run time, which certainly approaches dynamic dispatch. (Polymorphic recursion is one of Chris Okasaki's favorite tricks. It involves definitions like data Tree a = Leaf a | Node (Tree [a]) (Tree [a]) in which the variable 'a' is used recursively at a different type.) Best, Dylan Thurston
On 26-Jan-2003, Norman Ramsey <nr@eecs.harvard.edu> wrote:
In a fit of madness, I have agreed to deliver a 50-minute lecture on type classes to an audience of undergraduate students. These students will have seen some simple typing rules for F2 and will have some exposure to Hindley-Milner type inference in the context of ML.
Will they have had exposure to more "traditional" OO programming? If so, it might be useful to note the difference between Haskell type classes and C++/Java/whatever classes, namely that Haskell decouples types and the interfaces that they support. The advantage is that you can extend a type with a new interface at any point, not just when you define the type.
Hmm --- you are talking about the `instance' declarations, right?
Yes -- the fact that Haskell has separate instance declarations, as opposed to making this information part of the `data' declaration. In most OO languages inheritence relations need to be specified in the type definition. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit The University of Melbourne | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
This is a somewhat older thread, but I ask you to enlighten me. Norman Ramsey wrote:
A fact that I know but don't understand the implication of is that Haskell dispatches on the static type of a value, whereas OO languages dispatch on the dynamic type of a value. But I suspect I'll leave that out :-)
Dean Herington:
Perhaps I misunderstand, but I would suggest that "fact" is, if not incorrect, at least oversimplified. I would say Haskell dispatches on the dynamic type of a value, in the sense that a single polymorphic function varies its behavior based on the specific type(s) of its argument(s). What may distinguish Haskell from typical OO languages (I'm not an expert on them) is that in Haskell such polymorphic functions could (always or at least nearly so) be specialized statically for their uses at different types.
Fergus Henderson wrote:
I agree. The above characterization is highly misleading. It would be more accurate and informative to say that both Haskell and OO languages dispatch on the dynamic type of a value.
================================ Now my brain ceased to understand... Are you sure that OO dispatch schemas are based on the *argument* type? I would say that - unless I am dead wrong, the OO languages such as Smalltalk do not dispatch on dynamic types of a value. The receiver is known, so its vir. f. table (belonging to the receiver's class) is known as well, the dispatching is based on the *message identifiers* independently of subsidiary arguments. Only after that - perhaps - some "reversions", message propagation depending on the arg(s) value(s), etc. may take place, but all this is irrelevant... Forgive me if I write stupidities. Jerzy Karczmarczuk
On Tuesday, February 4, 2003, at 03:46 PM, Jerzy Karczmarczuk wrote:
I would say that - unless I am dead wrong, the OO languages such as Smalltalk do not dispatch on dynamic types of a value. The receiver is known, so its vir. f. table (belonging to the receiver's class) is known as well, the dispatching is based on the *message identifiers* independently of subsidiary arguments.
Yes, normally only the receiver and "message identifier" matters. In languages like Java, where the type of the other arguments is considered, this is handled statically. For languages like Smalltalk, Objective-C, etc, all that you know at compile time is that the receiver is an object. You don't know what kind of object. Thus you cannot use a static dispatch style or vtables as you would in a language like C++. Even when the type is bounded, vtables are not enough because of "categories" and "method packages" that add methods to classes at run time. Dispatch is done on the "target" (receiver) and "selector" (message identifier). So if you consider an expression like: target_expr doSomething:arg_expr then you should break that up into v = target_expr f = lookup_method(v, "doSomething:") f(v, "doSomething:", argexpr). You dispatch on the dynamic type of the target (it's class) and on the dynamic state of its method tables. Note that you cannot assume that the receiver has a method that matches the selector! Dynamic method lookup is a fairly complicated and expensive process, and it's a barrier to many optimizations. This can be mitigated by program analysis and specialization or similar techniques; dynamic dispatch and the surrounding problems are getting fairly well researched. Languages with dynamic dispatch: * Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., 1986 * Apple Computer, Inc., The Objective-C Programming Language, 2002. http://developer.apple.com/techpubs/macosx/Cocoa/ObjectiveC/index.html * Pieter J. Schoenmaker, Supporting the Evolution of Software, Ph.D. thesis, Eindhoven University of Technology, July 1, 1999. Some research: * Zoran Budimlic, Ken Kennedy, and Jeff Piper, The cost of being object-oriented: A preliminary study, Scientific Computing 7(2), 1999 * David Detlefs and Ole Agesen, Inlining of Virtual Methods, Proc. of 13th ECOOP * A Diwan. Understanding and improving the performance of modern programming languages. Ph.D. thesis, University of Massachusetts at Amherst. 1997 * Peeter Laud, Analysis for Object Inlining in Java; http://citeseer.nj.nec.com/laud01analysis.html * Ole Agesen and Jens Palsberg and Michael I. Schwartzbach, Type Inference of {SELF}: Analysis of Objects with Dynamic and Multiple Inheritance, Lecture Notes in Computer Science, http://citeseer.nj.nec.com/agesen93type.html
Only after that - perhaps - some "reversions", message propagation depending on the arg(s) value(s), etc. may take place, but all this is irrelevant...
Well, "self" and the "selector" is usually an argument to the method, but otherwise I agree. Regards, John Hornkvist
participants (8)
-
Dean Herington -
Dylan Thurston -
Fergus Henderson -
Jerzy Karczmarczuk -
John Hörnkvist -
Lauri Alanko -
Nick Name -
Norman Ramsey