Subtyping in functional programming
Jacob Wallstrom
the common object-oriented languages. When comparing these I have come
up with the following questions:
1. Does Haskell have dynamic binding?
In the article "FP + OOP = Haskell" the authour claims that Haskell
supports the object oriented paradigm. In my view that means that Haskell
should have dynamic binding, but I can't see how to achieve it.
2. Is Haskell's type system more powerful than ML's?
Assuming that the answer to the above question is "no", are there
any principial advantages of Haskell's types system vs. ML's? Aren't
both just different ways to achieve the same thing, i.e. constrained
genericity? (When talking about ML's type system I mean the whole
language, including the module language.)
3. Does OBJ3 have dynamic binding?
The OBJ3 language implements subtyping with coersion functions. It's
possible to achieve true dynamic binding with this approach?
4. Does dynamic typing violate referential transparency?
Since one identifier can refer to different functions at run-time
there seems to be a problem with dynamic typing. Is this correct?
Jacob
Laurent Dami
>I'm interested in the differences in the typing mechanisms in ML, Haskell and
>the common object-oriented languages. When comparing these I have come
>up with the following questions:
>
>1. Does Haskell have dynamic binding?
> In the article "FP + OOP = Haskell" the authour claims that Haskell
> supports the object oriented paradigm. In my view that means that Haskell
> should have dynamic binding, but I can't see how to achieve it.
The keywords "class" and "instance" in Haskell do not denote the
same concepts as in OOP. What they give you is a kind of operator
overloading, like what you find for example in C++ or ADA. This
is very useful, but I agree with you that it is not enough
to claim that Haskell is object-oriented.
>
>2. Is Haskell's type system more powerful than ML's?
As far as I understand, it is not, apart from a couple of "minor"
features (like operator overloading).
>3. Does OBJ3 have dynamic binding?
I don't know.
>4. Does dynamic typing violate referential transparency?
> Since one identifier can refer to different functions at run-time
> there seems to be a problem with dynamic typing. Is this correct?
I see no reason why this should be a problem, if the type system
is equipped with subtyping, so that you can check that any
implementation of a method is "compatible" with its type specification.
The problem is that this "compatibility" relationship only makes
sense (i.e., starts to be useful) if it is present not only at the
level of types, but also at the level of values, and in order to
get it you need something like records:
{x=1; y=7} is compatible with {y=7}
because it supports all the same operations on field y, and in addition
supports more operations on field x. Therefore all accounts of OOP
in a functional setting use some form of record operations (cf
Cardelli, Pierce, Mitchell, Ghelli, ...). Unfortunately, Haskell
does not have records.
Laurent Dami | tel: +41 (22) 705 76 61
Centre Universitaire d'Informatique | fax: +41 (22) 320 29 27
24, rue General-Dufour | email: da...@cui.unige.ch
1211 Geneve 4 Switzerland |
Dr. Kevin Hammond
>1. Does Haskell have dynamic binding?
No.
>2. Is Haskell's type system more powerful than ML's?
No. The intention was to get 90% of SML for much less effort.
The SML module system is extremely complicated; Haskell's is merely
very complicated :-(
Given fully general overloading, Haskell should have the same power as
SML minus sharing, I believe.
>3. Does OBJ3 have dynamic binding?
I believe not, but it's a long time since I used OBJ3 seriously.
>4. Does dynamic typing violate referential transparency?
No. See SASL for a counter-example.
Kevin
--
Dept. of Computing Science, Glasgow University. E-mail: k...@dcs.glasgow.ac.uk
Absolutely NO peanuts to be consumed during this email.
Vance Morrison
>In article <2t93pc$e...@euas20.eua.ericsson.se> tmp...@eua.ericsson.se (Jacob Wallstrom) writes:
>>1. Does Haskell have dynamic binding?
>No.
It seems to me that this is incorrect. It has been a while since I used
Haskell, but I recall that I can make a class called say TABLE which has
several abstract operators (say add, find, ...). This class can have
many instances (either directly or though inheritance), say they were
ASSOCIATION_TABLE, BINARY_TREE_TABLE ....
Now I can make up a function F that operats on TABLE using the abstraction
functions and call it with say BINARY_TREE_TABLE. Now you might still
be suspicious that this is still overloading, but I can also make up a
list of TABLE, which is NOT homogeous (that is it has ASSOCIATION_TABLE's
and BINARY_TREE_TABLE's in it) and apply F to each member of the list
using the map operator. That certainly is NOT simply overloading and
seems to me to be dynamic binding.
>>2. Is Haskell's type system more powerful than ML's?
>No. The intention was to get 90% of SML for much less effort.
>The SML module system is extremely complicated; Haskell's is merely
>very complicated :-(
Hmm, I guess it is just a matter of viewpoint, but I think that SML's
system is conceptually simpler than Haskell's. Part of the reason for
this conceptual simplicity is that SML is more explicit (that is verbose)
so I agree that where the two systems overlap, Haskells is easer for
the programmer to use. On the other hand, SML's system probably has
advantages for large scale reuse over Haskell.
Bottom line: it is very difficult to say anything briefly about the
relative `power' (whatever that is) of anything as complicated as
a programming language.
Vance
Darren J Moffat
>I'm interested in the differences in the typing mechanisms in ML, Haskell and
>the common object-oriented languages. When comparing these I have come
>up with the following questions:
>1. Does Haskell have dynamic binding?
> In the article "FP + OOP = Haskell" the authour claims that Haskell
> supports the object oriented paradigm. In my view that means that Haskell
> should have dynamic binding, but I can't see how to achieve it.
(OOP => Dynamic Binding) == False
Why does OOP have to mean dynamic binding?
Smalltalk is OOP and has dynamic binding but C++ is OOP and doesn't
have dynamic binding. So I don't see why it should mean that Haskell
should have dynamic binding (from my understanding it isn't)
--
Darren J Moffat 20 Southpark Ave
email: mof...@dcs.gla.ac.uk Glasgow
Konstantin Laufer
>
> (OOP => Dynamic Binding) == False
>
> Why does OOP have to mean dynamic binding?
>
> Smalltalk is OOP and has dynamic binding but C++ is OOP and doesn't
> have dynamic binding. So I don't see why it should mean that Haskell
> should have dynamic binding (from my understanding it isn't)
Incorrect. The following `equation' holds in C++:
(pointer || reference) && virtual function == dynamic (method) binding
Dynamic binding is generally considered a necessary condition for
object orientation [too many references to list].
--
-Konstantin Lau...@math.luc.edu
-URL http://www.math.luc.edu/~laufer/home.html
Wolfgang Grieskamp
>k...@dcs.gla.ac.uk (Dr. Kevin Hammond) writes:
>>In article <2t93pc$e...@euas20.eua.ericsson.se> tmp...@eua.ericsson.se (Jacob Wallstrom) writes:
>>>1. Does Haskell have dynamic binding?
>>No.
>It seems to me that this is incorrect.
Depends on the view you have.
Haskell has no dynamic binding in the sense that at link time all
applications to overloaded (i.e. undetermined) functions can be
theoretically resolved. This is similar to shallow polymorphism, where
all type variables can be instantiated.
>It has been a while since I used
>Haskell, but I recall that I can make a class called say TABLE which has
>several abstract operators (say add, find, ...). This class can have
>many instances (either directly or though inheritance), say they were
>ASSOCIATION_TABLE, BINARY_TREE_TABLE ....
>Now I can make up a function F that operats on TABLE using the abstraction
>functions and call it with say BINARY_TREE_TABLE.
Yes.
>Now you might still
>be suspicious that this is still overloading, but I can also make up a
>list of TABLE, which is NOT homogeous (that is it has ASSOCIATION_TABLE's
>and BINARY_TREE_TABLE's in it) and apply F to each member of the list
No, you can't. Unfortunately. This happens since the type variable
you use in the list-of-table declaration quantifies over the entire
declaration:
tableList = TABLE a => [a]
For a particular instance of tableList you must decide which
particular table to use. If you would have something like
"higher-order" typclasses resp. nested constraints:
tableList = [TABLE a => a]
... then you would have something like dynamic binding. You also have
a more complicated implementation model (function dictionaries must be
attached to data), and, I strongly guess, dynamic typing -- that is,
the possibility that your program crashes with a type error.
>>>2. Is Haskell's type system more powerful than ML's?
>>No. The intention was to get 90% of SML for much less effort.
>>The SML module system is extremely complicated; Haskell's is merely
>>very complicated :-(
>Hmm, I guess it is just a matter of viewpoint, but I think that SML's
>system is conceptually simpler than Haskell's. Part of the reason for
>this conceptual simplicity is that SML is more explicit (that is verbose)
>so I agree that where the two systems overlap, Haskells is easer for
>the programmer to use. On the other hand, SML's system probably has
>advantages for large scale reuse over Haskell.
I agree. Haskells implicitness has its place where basic well-known
properties of types are concerned -- equality, orderings, textual
representation and so on.
Having the "ideal" type class hierarchy for a particular application
would surely make the impliciteness even for large scaled software to
a benefit. But having a not so ideal type class hierarchy makes it
most probably hard to maintain such code. The question is which of the
both is more likely.
--
Inet: w...@cs.tu-berlin.de Tel: 030-314-21760 Fax: 030-314-73623
Post: Technische Universitaet Berlin, Institut fuer Angewandte Informatik,
Fachgebiet Uebersetzerbau und Programmiersprachen, Sekr. FR 5-13,
Franklinstr. 28-29, 10587 Berlin
Konstantin Laufer
> morr...@hal.cs.uiuc.edu (Vance Morrison) writes:
[...]
> >Now you might still
> >be suspicious that this is still overloading, but I can also make up a
> >list of TABLE, which is NOT homogeous (that is it has ASSOCIATION_TABLE's
> >and BINARY_TREE_TABLE's in it) and apply F to each member of the list
>
> No, you can't. Unfortunately. This happens since the type variable
> you use in the list-of-table declaration quantifies over the entire
> declaration:
>
> tableList = TABLE a => [a]
>
> For a particular instance of tableList you must decide which
> particular table to use. If you would have something like
> "higher-order" typclasses resp. nested constraints:
>
> tableList = [TABLE a => a]
>
> ... then you would have something like dynamic binding. You also have
> a more complicated implementation model (function dictionaries must be
> attached to data), and, I strongly guess, dynamic typing -- that is,
> the possibility that your program crashes with a type error.
You can do precisely this with existential types, where the
existentially quantified type variables are constrained by type
classes. You can thys declare a wrapper type
TableWrapper = TABLE a => TableWrap a
with a single constructor TableWrap. Since the type variable a does
not appear as a parameter to this type, it is taken to be
existentially quantified. Then you can define a heterogeneous (wrt
the table implementations) list as follows:
tl = [TableWrap aHashTable, TableWrap aTreeTable, ...]
Some of this stuff is written up in my thesis, but I also have a
recent draft in
file://ftp.math.luc.edu/pub/laufer/papers/haskell+extypes.ps.gz.
Btw, Haskell B already has this extension built in, and the examples
in my draft run under hbi.
Fernando Mato Mira
> In article <Cr8A2...@dcs.gla.ac.uk>, mof...@dcs.gla.ac.uk (Darren J Moffat) writes:
> > (OOP => Dynamic Binding) == False
> >
> > Why does OOP have to mean dynamic binding?
> >
> > Smalltalk is OOP and has dynamic binding but C++ is OOP and doesn't
> > have dynamic binding. So I don't see why it should mean that Haskell
> > should have dynamic binding (from my understanding it isn't)
a) Incorrect. C++ is not OO
> Incorrect. The following `equation' holds in C++:
>
> (pointer || reference) && virtual function == dynamic (method) binding
b) Meta-incorrect. C++ has no dynamic binding. There's no run-time
type information to support it.
> Dynamic binding is generally considered a necessary condition for
> object orientation [too many references to list].
c) Correct. Implies a) .
--
F.D. "Cyber Kid" Mato Mira
Computer Graphics Lab mato...@epfl.ch
EPFL FAX: +41 (21) 693-5328
Rob Hasker
>b) Meta-incorrect. C++ has no dynamic binding. There's no run-time
> type information to support it.
Why isn't a vtbl (virtual function table) run-time type information?
Rob Hasker
has...@uiuc.edu
Wolfgang Grieskamp
>b) Meta-incorrect. C++ has no dynamic binding. There's no run-time
> type information to support it.
What do you suggest is the kind of those method tables attached to C++
objects of classes with virtual functions -- if not type information?
Darren J Moffat
>> > (OOP => Dynamic Binding) == False
>> >
>> > Why does OOP have to mean dynamic binding?
>> >
>> > Smalltalk is OOP and has dynamic binding but C++ is OOP and doesn't
>> > have dynamic binding. So I don't see why it should mean that Haskell
>> > should have dynamic binding (from my understanding it isn't)
>a) Incorrect. C++ is not OO
It might not be a pure OOPL like Smalltalk80 but it is an OOPL.
>> Incorrect. The following `equation' holds in C++:
>>
>> (pointer || reference) && virtual function == dynamic (method) binding
>b) Meta-incorrect. C++ has no dynamic binding. There's no run-time
> type information to support it.
If you read my original posting I said that C++ is NOT dynamic. If you
had read properly you would see that I was saying that you don't have
to have dynamic binding to be an OOPL.
>> Dynamic binding is generally considered a necessary condition for
>> object orientation [too many references to list].
>c) Correct. Implies a) .
I don't want to start an argument about what makes a language an OOPL
but I would be interested in reading any references you have found
that says that to be an OOPL requires you also to have dynamic
binding.
All this just because someone asked if Haskell was dynamic :-)
(Which I still claim it isn't, type checking is done at compile time)
Paul Krause x7816
> Dynamic binding is generally considered a necessary condition for
> object orientation [too many references to list].
Is it now. I'm quite used to OO programming using only lexical
binding and indefinite extent. What does dynamic binding give me that
these two don't?
--
Paul F. Krause Systems Research and Applications Corporation
(703) 558-7816 Intelligent Information Systems
FAX 558-4723 2000 15th Street North, Arlington, VA 22201
Internet: kra...@sra.com-----Uucp: uunet!uupsi5!sraopus!verdi!krausep
Philip Santas
>>> (pointer || reference) && virtual function == dynamic (method) binding
>
>>b) Meta-incorrect. C++ has no dynamic binding. There's no run-time
>> type information to support it.
>
>If you read my original posting I said that C++ is NOT dynamic.
Are we going to play roulette?
Except for virtual method tables, C++ compilers are about to
support a built-in mechanism for RTTI allowing dynamic castings
and suchlike.
Philip Santas
Todd Plessel
|> I don't want to start an argument about what makes a language an OOPL
|> but I would be interested in reading any references you have found
|> that says that to be an OOPL requires you also to have dynamic
|> binding.
Here's one:
"Understanding Object-Oriented: A Unifying Paradigm"
by Tim Korson and John McGregor
Communications of the ACM
September 1990, Vol. 33, No. 9, pp. 40-60
It proposes these five concepts as 'basic' for OOP:
(1) objects
(2) classes
(3) inheritance
(4) polymorphism
(5) dynamic binding
(with only (3) being a unique contribution from the OO paradigm.)
With regards to C++...
Using these terms, C++ certainly supports OOP:
(1) variables can represent run-time objects (with private state and private and public behavior)
(2) objects are instances of classes
(3) classes can inherit attributes and behavior from other (multiple) classes
(4) templates (and inheritance) support (two kinds of) polymorphism
(5) C++ supports both static binding (via '.') and dynamic binding (via '->' pointers and virtuals).
C++ is not a 'pure' OOPL since it does not _require_ the use of the OO paradigm.
It is a 'multi-paradigm' language. (For example, it supports the procedural paradigm).
However it does _support_ the OO paradigm - including _enforcing_ notions such as
encapsulation (hiding some of an objects features from clients).
Enforcement is a crucial part of 'support'. For example, some propose that C 'supports'
the OO paradigm and point to the fact that C++ implementations often compile to C.
However, since C does not enforce notions such as encapsulation (i.e., nothing prevents
clients from accessing an objects 'private' features), it does not really support the
OO paradigm and is therefore not an OOPL.
(In truth C++, 'inherits' some C 'features' such as casting, which, along with header files,
can be used to violate encapsulation, but let's not go into that...)
Back to OOPLs...
Using the above five critera, Grady Booch presents a long list of OOPLs in his text:
_Object-Oriented Analysis and Design with Applications, 2nd Edition_
Benjamin-Cummings, 1994
Others strengthen or add more concepts to the OOPL definition (e.g. _multiple_ inheritance, assertions, garbage collection). See the text
_Object-Oriented Software Construction_
by Bertrand Meyer,
Prentice-Hall, 1988.
Adding these shrinks the field down even further admitting only Eiffel, Sather, and I'm
not sure what else, as 'real' OOPLs...
Sorry for the lengthly digression. Hopefully these references will be of use to those
interested in OO.
Todd
Thant Tessman
In article <2tn998$1...@trixie.rtpnc.epa.gov>, ple...@oz.rtpnc.epa.gov
writes:
> "Understanding Object-Oriented: A Unifying Paradigm"
> by Tim Korson and John McGregor
> Communications of the ACM
> September 1990, Vol. 33, No. 9, pp. 40-60
>
> It proposes these five concepts as 'basic' for OOP:
>
> (1) objects
> (2) classes
> (3) inheritance
> (4) polymorphism
> (5) dynamic binding
>
> (with only (3) being a unique contribution from the OO paradigm.)
[...]
There is a problem with the "laundry list" approach to categorizing
programming languages. For example, inheritance really plays two
different roles: The first is as a convenience when specifying the
behavior of a class. The second is that it is a common way of
achieving a small subset of one kind of polymorphism. In other words,
the important concept is subtyping, not inheritance.
If a language embodies the concept of subtyping, but doesn't do it via
inheritance, is it not object-oriented? And if it isn't, should
people care?
(I haven't read the book so my criticism might be unfair.)
thant
Darren J Moffat
>It proposes these five concepts as 'basic' for OOP:
^^^^^^^^
>(1) objects
>(2) classes
>(3) inheritance
>(4) polymorphism
>(5) dynamic binding
>(with only (3) being a unique contribution from the OO paradigm.)
>With regards to C++...
>Using these terms, C++ certainly supports OOP:
>(5) C++ supports both static binding (via '.') and dynamic binding (via '->' pointers and virtuals).
I think you are confusing dynamic binding which refers to the time
that type checking mechanism takes place (ie compile time in a static
language and runtime in a dynamic one) and dynamic allocation.
Scott Turner
wrote:
> >If you read my original posting I said that C++ is NOT dynamic.
> Except for virtual method tables, C++ compilers are about to
> support a built-in mechanism for RTTI allowing dynamic castings
> and suchlike.
RTTI provides type information, but it is not related to the "binding"
issue. It does not enhance the meaning of a virtual function call
such as
object->member_func()
David J Hopwood
>In article <CrE42...@dcs.gla.ac.uk>, mof...@dcs.gla.ac.uk (Darren J Moffat) writes:
>|> I don't want to start an argument about what makes a language an OOPL
>|> but I would be interested in reading any references you have found
>|> that says that to be an OOPL requires you also to have dynamic
>|> binding.
>
>Here's one:
>
>"Understanding Object-Oriented: A Unifying Paradigm"
>by Tim Korson and John McGregor
>Communications of the ACM
>September 1990, Vol. 33, No. 9, pp. 40-60
>
>It proposes these five concepts as 'basic' for OOP:
>
>(1) objects
>(2) classes
>(3) inheritance
>(4) polymorphism
>(5) dynamic binding
>
>(with only (3) being a unique contribution from the OO paradigm.)
Sorry to be pedantic, but OO does not require inheritance.
Counterexample: Self, which uses delegation instead, and is quite definately
OO.
In general, any mechanism which allows you to incrementally extend the
implementation of a type to create a new type is acceptable in place of
inheritance.
I agree you also need dynamic binding, etc.
I thought this group was about functional programming, tho? ;-)
David Hopwood
david....@lmh.oxford.ac.uk
Philip Santas
In article <pkt-1606...@138.52.2.129>,
Scott Turner <p...@lpi.liant.com> wrote:
>
>> >If you read my original posting I said that C++ is NOT dynamic.
>
>> Except for virtual method tables, C++ compilers are about to
>> support a built-in mechanism for RTTI allowing dynamic castings
>> and suchlike.
>
>RTTI provides type information, but it is not related to the "binding"
>issue. It does not enhance the meaning of a virtual function call
>such as
> object->member_func()
RTTI gives information and pointer conversion with dynamic cast.
Some claimed C++ cannot be "dynamic" because there is no information
available.
Virtual methods (their tables and the lookup process) do not need RTTI,
but they are related to bindig.
Many of these issues are also implementation dependent and are
confused because of the vocabulary used by different groups.
Food for conferences.
Philip Santas
Konstantin Laufer
> ple...@oz.rtpnc.epa.gov (Todd Plessel) writes:
[...]
> >(5) C++ supports both static binding (via '.') and dynamic binding (via '->' pointers and virtuals).
Precisely.
> I think you are confusing dynamic binding which refers to the time
> that type checking mechanism takes place (ie compile time in a static
> language and runtime in a dynamic one) and dynamic allocation.
I think you are confusing the terminology. Binding refers to the
association between names and values. Dynamic binding means that
names (here, method names) are bound to values (here, method code) at
run-time. What you are talking about is called dynamic *typing*.
Finally, allocation is orthogonal to both binding and typing.
Scott Turner
Laufer) wrote:
> Binding refers to the
> association between names and values. Dynamic binding means that
> names (here, method names) are bound to values (here, method code) at
> run-time.
That definition of "dynamic binding" fairly represents the point of view
which considers C++ to support dynamic binding. Let's try out that
definition in our broader context of comp.lang.functional,
where data and code values are usually on an equal footing.
In C++, a reference to a virtual function looks like
object->member_function
and the value (method code) depends on the particular object as determined
at run-time. One may call that dynamic binding. In C++ or even C,
a reference to a data member looks like
object->data_member
and the value depends on the particular object as determined at run-time.
To be consistent one would call that dynamic binding as well.
That would be absurd.
A meaningful definition of "dynamic binding" must relate to an
inheritance scheme (or as David Hopwood well described it: a
"mechanism which allows you to incrementally extend the
implementation of a type to create a new type").
A virtual function call in C++ does nothing dynamic within the
inheritance hierarchy. It has come to be called "dynamic binding"
only because it can achieve much of the same effect that you get
in Smalltalk, and out of political necessity.
The question "Does Haskell have dynamic binding?" is a problem.
This thread has shown us a little about Haskell, but for the most
part it has attempted to figure out what "dynamic binding" is,
and failed.
Philip Santas writes:
>Food for conferences.
Indeed.
--
Scott Turner
Liant Software Corp., Framingham, Massachusetts, USA
p...@lpi.liant.com
Fergus Henderson
one thread!
There is no common agreement about the precise definition of what is an
Object Oriented Programming Language (OOPL), but C++ *is* an OOPL by any
reasonable definition of the term, and there is widespread agreement
about that. It is not, however, a "pure" OOPL, though the definition
of a pure OOPL is even less well agreed on than the definition of an OOPL -
which languages are pure OOPLs? Smalltalk? Eiffel??
C++ *does* have both static and dynamic binding.
But that issue is seperate to the use of '.' v.s. '->':
in C++, both '.' can be both dynamic and static.
C++ *does* have run-time type information - but only for class types
which include at least one virtual function.
--
Fergus Henderson - f...@munta.cs.mu.oz.au
David J Hopwood
>In article <2tqm4o$3...@apollo.it.luc.edu>, lau...@math.luc.edu (Konstantin
>Laufer) wrote:
>
>> Binding refers to the
>> association between names and values. Dynamic binding means that
>> names (here, method names) are bound to values (here, method code) at
>> run-time.
>
>That definition of "dynamic binding" fairly represents the point of view
>which considers C++ to support dynamic binding. Let's try out that
>definition in our broader context of comp.lang.functional,
>where data and code values are usually on an equal footing.
>In C++, a reference to a virtual function looks like
> object->member_function
>and the value (method code) depends on the particular object as determined
>at run-time. One may call that dynamic binding. In C++ or even C,
>a reference to a data member looks like
> object->data_member
>and the value depends on the particular object as determined at run-time.
>To be consistent one would call that dynamic binding as well.
Not really. There is a big difference between these two cases.
For object->member_function, it isn't just the _value_ which is dependent on
the object; it's the algorithm used to calculate that value. In C, say, there
is no way of using a different algorithm to calculate a data member, depending
on the dynamic type of the object.
>That would be absurd.
>
>A meaningful definition of "dynamic binding" must relate to an
>inheritance scheme (or as David Hopwood well described it: a
>"mechanism which allows you to incrementally extend the
>implementation of a type to create a new type").
Hey, don't twist my words ;-)
Such a mechanism is necessary for _OOP_ (IMO, anyway). However it isn't
necessary for dynamic binding. Smalltalk without inheritance would still be
dynamically bound.
>A virtual function call in C++ does nothing dynamic within the
>inheritance hierarchy. It has come to be called "dynamic binding"
>only because it can achieve much of the same effect that you get
>in Smalltalk, and out of political necessity.
Try telling that to comp.lang.c++ ;-)
To be fair, C++ _can_ do dynamic binding. Perhaps not as well as Smalltalk,
and perhaps only because the definition of dynamic binding has stretched a
little, but it can do it.
>The question "Does Haskell have dynamic binding?" is a problem.
>This thread has shown us a little about Haskell, but for the most
>part it has attempted to figure out what "dynamic binding" is,
>and failed.
Here's how I usually define dynamic binding to myself:
A language is dynamically bound iff it is possible to create objects of
different run-time types, which respond to the same message in different ways.
Thinking about it though, I'm not sure if this is good enough.
For example, what about this:
foo ::= Foo num (num -> num)
bar :: foo -> num
bar (Foo i f) = f i
new_X i = Foo i (*2)
new_Y i = Foo i (+2)
x, y :: foo
x = new_X 1
y = new_Y 2
which gives: bar x = 2
bar y = 4
Isn't it equivalent to:
class Foo
{ int i;
public: virtual void Foo (int a) { i = a; }
virtual int bar () = 0; };
class X: public Foo
{ public: int bar () = i*2; };
class Y: public Foo
{ public: int bar () = i+2; };
Foo x, y;
x = new X (1);
y = new Y (2);
which gives: x.bar = 2
y.bar = 4 ?
(Neither of these have been near a compiler, and what I know of Haskell is
inferred from Orwell).
To call Haskell dynamically bound on the basis of the above example would be
pushing it, but it seems to satisfy my definition.
I guess the difference is that you wouldn't write a Haskell program like that,
whereas in an OOPL it's easy to use dynamic binding all the time.
So, a dynamically bound language is one that explicitly provides support for
allowing objects of different types to respond to the same method (rather than
just one in which it can be done).
>Scott Turner
>p...@lpi.liant.com
David Hopwood
david....@lmh.oxford.ac.uk
Philip Santas
Fergus Henderson <f...@munta.cs.mu.OZ.AU> wrote:
>
>C++ *does* have both static and dynamic binding.
>But that issue is seperate to the use of '.' v.s. '->':
>in C++, both '.' can be both dynamic and static.
Yes. Additionally '->' is an operator which can be redefined, and
as such it can be static (if it is not virtual).
>C++ *does* have run-time type information - but only for class types
>which include at least one virtual function.
Yes. There is no need to keep such information for non polymorphic
types.
Final remark for this thread:
If one knows the constructs of a language and the way its compilers work,
then any fuzziness in terminology can be resolved. If not, then bad luck.
There is no reason to argue on things which exist for more than 20 years
and obviously can be implemented/analyzed in various ways.
Additionally one can simulate OO programs in some functional languages
(for instance, the book of Abelson/Sussman on Scheme describes such
clever techniques --these can be easily scalled-up for typed languages).
The problem is that nobody would write such code in practice, and the run-time
performance of these examples is dissapointing.
Philip Santas
Scott Turner
Henderson) wrote:
> It has been a long time since I've seen so much mis-information in the
> one thread!
>
> There is no common agreement about the precise definition of what is an
> Object Oriented Programming Language (OOPL), but C++ *is* an OOPL by any
> reasonable definition of the term, and there is widespread agreement
> about that. [ ... ]
> C++ *does* have both static and dynamic binding.
Generally speaking, binding is the process which takes a name and
associates a meaning with it.
In Stroustrup's paper "What is Object-Oriented Programming" he doesn't
use the term "dynamic binding" at the critical points of definition.
But he does contrast C++'s virtual function way of achieving O-O
to Smalltalk's method invocations. The latter he describes
First the appropriate table of method names is found by
examining the object pointed to by 'p'. In this table (or
group of tables) the string 'f' is looked up to see if
the object has an f().
Plainly, this process is both dynamic and binding. In contrast,
the C++ virtual function call is dynamic, but it does not bind a name.
The name has already been bound to a virtual function (often
implemented as an offset into an object's table of virtual function
pointers).
This thread has been groping for a clear enough definition of
"dynamic binding" that we can answer the question of whether Haskell
has it. Yes, C++ is an OOP language, but by the best definition
I know, neither C++ nor Haskell has dynamic binding.
I don't mean to get into a low-level dispute over terminology.
The more substantial question is
Do Haskell's OOP features measure up in the area that
C++ supports by "virtual functions", and that is sometimes
called "dynamic binding"?
John Sargeant
|>
|> Generally speaking, binding is the process which takes a name and
|> associates a meaning with it.
In this case, I suggest that the name is the method (function) name and
the meaning is *the actual code which gets executed*.
|>
|> In Stroustrup's paper "What is Object-Oriented Programming" he doesn't
|> use the term "dynamic binding" at the critical points of definition.
|> But he does contrast C++'s virtual function way of achieving O-O
|> to Smalltalk's method invocations. The latter he describes
|>
|> First the appropriate table of method names is found by
|> examining the object pointed to by 'p'. In this table (or
|> group of tables) the string 'f' is looked up to see if
|> the object has an f().
|>
|> Plainly, this process is both dynamic and binding. In contrast,
|> the C++ virtual function call is dynamic, but it does not bind a name.
|> The name has already been bound to a virtual function (often
|> implemented as an offset into an object's table of virtual function
|> pointers).
But it has not been bound to a *real* function. To do that you have to
make the dynamic indirection through the table. I think the real difference
between the mechanisms is just that the C++ one is simpler because the
static type checking restricts the set of bindings allowed (and in
particular guarantees that there will be one - no messageNotUnderstood).
|>
|> This thread has been groping for a clear enough definition of
|> "dynamic binding" that we can answer the question of whether Haskell
|> has it. Yes, C++ is an OOP language, but by the best definition
|> I know, neither C++ nor Haskell has dynamic binding.
By my definition C++ does.
|>
|> I don't mean to get into a low-level dispute over terminology.
|> The more substantial question is
|>
|> Do Haskell's OOP features measure up in the area that
|> C++ supports by "virtual functions", and that is sometimes
|> called "dynamic binding"?
My understanding is that the mapping from type classes to actual types
is (in principle anyway) a static one, and therefore the answer is no.
But I've always been confused by why Haskell implementations need to
pass "dictionaries" around at runtime, which does look like a dynamic
binding mechanism.
|> --
|> Scott Turner
|> Liant Software Corp., Framingham, Massachusetts, USA
|> p...@lpi.liant.com
John
Dr. Kevin Hammond
>But I've always been confused by why Haskell implementations need to
>pass "dictionaries" around at runtime, which does look like a dynamic
>binding mechanism.
They don't *need* to. In the presence of separate compilation it's
just easier to implement type class overloading if you bind
dictionaries dynamically. Linking and compilation are probably
(but not necessarily!) also faster.
So this is an engineering trade-off rather than something fundamental
concerning type classes.
Wolfgang Grieskamp
>A meaningful definition of "dynamic binding" must relate to an
>inheritance scheme (or as David Hopwood well described it: a
>"mechanism which allows you to incrementally extend the
>implementation of a type to create a new type").
>A virtual function call in C++ does nothing dynamic within the
>inheritance hierarchy.
This is wrong. A virtual function call does an implicite type cast
from the superclass down to the subclass which implements the
function.
Jonathan Eifrig
Scott Turner <p...@lpi.liant.com> wrote:
>In Stroustrup's paper "What is Object-Oriented Programming" he doesn't
>use the term "dynamic binding" at the critical points of definition.
>But he does contrast C++'s virtual function way of achieving O-O
>to Smalltalk's method invocations. The latter he describes
>
> First the appropriate table of method names is found by
> examining the object pointed to by 'p'. In this table (or
> group of tables) the string 'f' is looked up to see if
> the object has an f().
>
>Plainly, this process is both dynamic and binding. In contrast,
>the C++ virtual function call is dynamic, but it does not bind a name.
>The name has already been bound to a virtual function (often
>implemented as an offset into an object's table of virtual function
>pointers).
This is a pretty bogus distinction to try to make. First of all,
reasoning about a language's features based on *an* implementation is
rather pointless; after all, why should this "dynamic name look-up"
implementation scheme be the *definition* of what SmallTalk message
passing is?
Secondly, there's really no difference between "looking up the
string 'f' in a method table" and "computing an offset (determined by
the string 'f') into an virtual function table." One could consider
the latter "looking up the string 'f'" as well; it's just a bit smarter,
since it knows where to look. :-)
This is basically because SmallTalk (and C++) don't have first-
class method names. (The C++ "member pointer" abomination doesn't count!)
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Jack Eifrig (eif...@cs.jhu.edu) The Johns Hopkins University, C.S. Dept.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Matthias Blume
Plainly, this process is both dynamic and binding. In contrast,
the C++ virtual function call is dynamic, but it does not bind a name.
The name has already been bound to a virtual function (often
implemented as an offset into an object's table of virtual function
pointers).
Well, if you look at it hard enough you can always dismiss the
``dynamic binding'' part. If you consider the process of finding out
the run-time value (or -- in the case of r-values -- the location)
associated with a name to be the ``meaning'' of that name, then this
meaning is in fact fixed.
So it really depends on what you consider the meaning of a name. In
C++ if you consider the entry address of the actual function to be
called at the call-site of a virtual function invocation to be the
``meaning'' of the p->f construct, then the name p->f is bound
dynamically to that meaning. If you consider the implementation of
the dynamic lookup (something like p->_vtab [index_of_f]) to be the
meaning of p->f, then the binding to that meaning is static.
Using explicit stores, continuations, and so on, one can always give
statically bound meanings (denotations) to all names.
--
-Matthias
Matthias Blume
Well, if you look at it hard enough you can always dismiss the
``dynamic binding'' part. If you consider the process of finding out
the run-time value (or -- in the case of r-values -- the location)
^^^
Whoops, brain-fade: of course, I meant ``l-values'' when I wrote
``r-values''.
associated with a name to be the ``meaning'' of that name, then this
meaning is in fact fixed.
--
-Matthias
Tom Thomson
problem is representing real things with fixed identity and mutable state,
and fp is not very good at that. Lots of complicated tricks (monads,
continuations, streams with non-deterministic merges, switchboards, etc
ad nauseam) have been invented to overcome this problem for fp but if one
believes that the whole point of fp is simplicity of expression arising from
substitutivity (referential transparency) it is absurd to introduce something
inordinately complex in order to express something inherently simple.
We can pick nits ad nauseam about whether Haskell has or has not dynamic
binding and whether C++ has it or not, and recent discussion in this thread
has been doing just that. But why has the argument changed into one about
terminology (most recent posts have disputed the definition of "dynamic
binding") instead of one about how easy it is to express something (ie
to express whatever we mean by dynamic binding)?
We need to understand the distinctions between things which have identity
and maybe mutable state, things which are immutable, things which classify
other things by equivalence of interface syntax (type systems?), things
which classify other things by applicability/suitability for use (we don't
appear to have this concept in computer languages - after advocating for
about a decade I don't think type theorists have noticed that things may
have semantics as well as syntax), and things which classify according
to inheritance relationships (class systems). Getting back to the "Subject"
matter of the thread, I claim that "subtyping" is clearly an instance of the
last named and also an instance of the second - at least any useful form of
subtyping is going to be. A simple example is treating the integers as a
subtype of the reals: if we look at the user integer add, subtract, multiply,
divide, mod, and successor operations these can all be extended in a simple
way to the reals (caveat: the extension of integer division is NOT of course
real division), and the integers have a natural embedding in the reals. There
is no restriction of real division to the integers, on the other hand. Out
there in the "real" world, an integer is a real (identifying the isomorphic
image of the integers in the natural embedding to the reals with the integers
themselves); but the integers can't inherit division from the reals, so in
a strict inheritance world they can't be a subclass - the OO world can't cope
with this. On the other hand, I think it unlikely that exponents of fp would
claim that "real" is a subtype of "integer" despite the extensibility of all
the integer operations in a natural manner (all, not just the ones named above)
so fp isn't going to cope either.
Can we somehow combine fp and OO to cover real-world subtyping properly - or
real-world classification, or whatever we want to call it? Evidently not, if
the above analysis is accurate. What we need in both fp and OO is the addition
of real-world subtyping - neither currently has anything like it. When we've
added that to each we can maybe start to worry about combining fo & OO -
preferably in such a way that we don't discard the clarity of expression that
each provided in it's early manifestations (but not in Haskell and C++). We
will of course get nowhere if semantic issues like subtyping continue to be
confused with syntactic issues like overload; neither will we achieve anything
if we ignore one set of issues in favour of the other.
T.
Jim McDonald
In article <Crt08...@oasis.icl.co.uk>, t...@cs.man.ac.uk (Tom Thomson) writes:
...
|> We need to understand the distinctions between things which have identity
|> and maybe mutable state, things which are immutable, things which classify
|> other things by equivalence of interface syntax (type systems?), things
|> which classify other things by applicability/suitability for use (we don't
|> appear to have this concept in computer languages - after advocating for
|> about a decade I don't think type theorists have noticed that things may
|> have semantics as well as syntax), and things which classify according
One approach to classify things for applicability is to construct
morphisms from a prototypical applicable thing to the particular
thing to be applied. For example, at Kestrel we have an algorithm hierarchy
starting with basic-problem-theory and extending via morphisms to (among
other things) network-flow-theory. A morphism from network-flow-theory
into a specific theory for an oil-flow problem would seem close to what
you are seeking, especially since the construction of that morphism most
naturally proceeds via the stepwise construction of increasingly elaborated
morphisms from basic-problem-theory to oil-flow, constraint-satisfaction-theory
to oil-flow, integer-linear-programming to oil-flow, etc. I.e., proceeding
down the hierarchy amounts to constructing more and more precise
classifications of the problem. (Informally we call it a ladder diagram
because thats what it ends up looking like, with each rung a more elaborate
morphism from a classifying theory on the left side to a newly composed
theory on the right.)
Some uses of category theory, in particular, spec morphisms between
theories, provide a reasonable framework for addressing these problems,
but it requires a paradigm shift from traditional OO programming.
For your example, you could have a functional specification of integers,
a functional specification of reals, and then a spec morphism from integers
into a definitional extension of the reals:
Integer theory Mediating theory Real theory
(def ext of real theory)
sort R' <-- sort R
sort I --> sort IR = R' | zero-fraction?
op R'+ : R', R' -> R' <-- op R+ : R,R -> R
op I+ : I,I -> I --> op IR+ : IR, IR -> IREAL
definition of IR+ using R'+
[A requirement for a spec morphism is that theorems from the domain
theory must translate into theorems in the codomain theory using the
signature (i.e., sort and op) mapping specified by the morphism.]
The mediating theory in the example is a definitional extension of real
theory, so the operations like IR+ don't really increase real theory
except to provide targets for the morphism from integer theory.
Similarly, the sort axioms (e.g. IR = R' | zero-fraction?) can be used
to eliminate references to introduced sorts such as IR. One might view
IR as an abbreviation or as a real sort with an isomorphism between it
and R'|zero-fraction?, depending on the context.
In this paradigm, theories act something like object classes, since
they provide orthogonality and inheritance, etc. but they are different
enough that there are not always simple one-to-one correspondences.
For example, it becomes an interesting question how to clarify the
interaction between the theory of all trees and the theory of a
particular tree, which would correspond to class membership.
Btw, multiple inheritence is handled quite elegantly via colimits in
the category of specs and spec-morphisms.
In short, there is encouraging ongoing work which I think addresses
your concerns, but many details still need to be resolved.
I hope I wasn't too terse, but there were a lot of ideas to pack into
one message (and dinner beckons...).
--
James McDonald
Kestrel Institute mcdo...@kestrel.edu
3260 Hillview Ave. (415) 493-6871 ext. 339
Palo Alto, CA 94304 fax: (415) 424-1807
David J Hopwood
writes:
>|>
>|> Generally speaking, binding is the process which takes a name and
>|> associates a meaning with it.
>
>In this case, I suggest that the name is the method (function) name and
>the meaning is *the actual code which gets executed*.
More generally, you are taking a _selector_, and associating a meaning (ie.
implementation code) to it.
A selector can be a name (eg. in Smalltalk), but it need not be. The only
requirement is that the selector can be determined statically.
>|> In Stroustrup's paper "What is Object-Oriented Programming" he doesn't
>|> use the term "dynamic binding" at the critical points of definition.
>|> But he does contrast C++'s virtual function way of achieving O-O
>|> to Smalltalk's method invocations. The latter he describes
>|>
>|> First the appropriate table of method names is found by
>|> examining the object pointed to by 'p'. In this table (or
>|> group of tables) the string 'f' is looked up to see if
>|> the object has an f().
>|>
>|> Plainly, this process is both dynamic and binding. In contrast,
>|> the C++ virtual function call is dynamic, but it does not bind a name.
>|> The name has already been bound to a virtual function (often
>|> implemented as an offset into an object's table of virtual function
>|> pointers).
>
>But it has not been bound to a *real* function. To do that you have to
>make the dynamic indirection through the table. I think the real difference
>between the mechanisms is just that the C++ one is simpler because the
>static type checking restricts the set of bindings allowed (and in
>particular guarantees that there will be one - no messageNotUnderstood).
I don't think simplicity really comes into it. C++ was designed that way for
run-time efficiency. Avoiding messageNotUnderstood can be achieved through the
typing checking system, while retaining Smalltalk-like binding.
>|> This thread has been groping for a clear enough definition of
>|> "dynamic binding" that we can answer the question of whether Haskell
>|> has it. Yes, C++ is an OOP language, but by the best definition
>|> I know, neither C++ nor Haskell has dynamic binding.
>
>By my definition C++ does.
OK. My definition:
First of all, dynamic binding is not an implementation mechanism; it's a
functionality. (If you don't agree with this, use a word other than dynamic
binding for the implementation).
So for example, if the run-time method lookup implementation can sometimes be
optimized out _without_ affecting functionality (eg. as in Self), you're still
doing dynamic binding to the same extent.
Also, it is not just a matter of whether a language supports dynamic binding,
but _how much_ of dynamic binding it supports.
In order of increasing flexibility, these are the requirements:
1. The code to be executed in response to a message is determined by the
receiver implementation. It is possible for more than one implementation
to be the receiver of a message.
2. An expression may denote an object of more than one possible implementation,
at run-time.
3. Additional object implementations may be created that can receive a
particular message, without changing (or recompiling) the code from which
the message was sent.
4. An object implementation may be created that can receive any set of existing
messages.
Ada-83 supports 1 only. Different implementations may recieve a message, but
these must be bound statically (ie. overloading).
Haskell supports 1 by overloading, and 2 and 3 can be hacked by storing
functions with objects.
C++ supports 1 in all cases, 2 in the case of pointer or reference expressions,
and 3 for virtual functions applied to the results of these expressions.
Eiffel and Sather support 1, 2, and 3 for all features/routines, and all
receiver expressions.
Objective-C supports (I think) 1, 2 and 3 for receivers declared as pointers,
and all 4 for receivers declared as id.
Smalltalk, Self, and Emerald support 1, 2, 3 and 4 for all methods, and all
receivers.
Which languages you consider to be dynamically bound depends on where you put
the cut-off point. Dynamic binding is not (as the term is currently used)
a yes/no question.
David Hopwood
david....@lmh.oxford.ac.uk
John Sargeant
|>
|> First of all, dynamic binding is not an implementation mechanism; it's a
|> functionality. (If you don't agree with this, use a word other than dynamic
|> binding for the implementation).
|>
|> So for example, if the run-time method lookup implementation can sometimes be
|> optimized out _without_ affecting functionality (eg. as in Self), you're still
|> doing dynamic binding to the same extent.
I agree, I didn't mean to imply that DB was merely an implementation mechanism,
I was just pointing out that the Smalltalk and C++ mechanisms are not that
different.
To summarise, most OO languages support 1-3. Some support 4. Looks to me like
1-3 is a reasonable working definition of dynamic binding....
But it doesn't matter too much what we call "it" so long is we're clear
why "it" is useful, and why Haskell doesn't (directly) support "it".
It's obviously much harder to pin down than a nice clean mathematical concept
like referential transparency :-)
|>
|> David Hopwood
|> david....@lmh.oxford.ac.uk
John
John C. Peterson
oriented languages, David Hopwood gives some concrete requirements for
use of the term 'dynamic binding':
In order of increasing flexibility, these are the requirements:
1. The code to be executed in response to a message is determined by the
receiver implementation. It is possible for more than one implementation
to be the receiver of a message.
2. An expression may denote an object of more than one possible implementation,
at run-time.
3. Additional object implementations may be created that can receive a
particular message, without changing (or recompiling) the code from which
the message was sent.
4. An object implementation may be created that can receive any set of existing
messages.
...
Haskell supports 1 by overloading, and 2 and 3 can be hacked by storing
functions with objects.
I won't comment on other languages, but I will point out that Haskell
supports all four of these via the class system without any 'hacks'.
Given a class declaration containing an operator:
class C a where
op :: a -> a
we can trivially assert that all four requirements are satisfied.
Consider the function:
f :: C a => a -> a
f x = op x
This function can be applied to any object which has been admitted to
class C. It requires no further knowledge of the actual type. The
specific instance declaration for a type T in the class C will
determine the meaning of f when applied to a value of type T. So if
we allow that the 'message' is op, then this satisfies 1, 2 since any
value in class C may be passed to f, 3 since new instances of C do
alter f in any way and can be compiled separately, and 4 since any
type may be admitted to C via an instance declaration.
Now this oversimplifies things a bit - for example, the class have
associated superclasses which would constrain requirement 4 a bit -
but I would argue that *according to this definition of dynamic
binding* Haskell should be included. I won't extend this to the
assertion that Haskell is object oriented as this will simply reopen
the debate on the meaning of the term.
One significant difference between Haskell and some of the other
languages using dynamic binding is that the type system carries out
the propagation of the information needed for method dispatch. This
differs from 'value oriented' dispatch mechanisms in that it can work
without having an object of the desired value in hand. For example, in
read :: Text a => String -> a
the read function is passed a string and creates a value determined by
the context in which the read function is called. No value of the
type being read is passed into read. At the implementation level, the
'tag' used to implement dynamic binding (all implementations of
dynamic binding require a tag, for a sufficiently broad definition of
'tag') is decoupled from the data values in Haskell. The association
between objects and their tags (dictionaries) is logical rather
than physical and tags can thus exist as separate entities. This
allows the 'read' function to be passed the tag associated with its
result. On the other hand, this creates the possibility of ambiguity
which is not generally a problem in other languages.
While the class system does give Haskell dynamic binding, this is
restricted by the type system somewhat. While everything works well
for simple operators such as the standard numerics, you need to extend the
type system a bit to generalize operations such as generic
sequence or generic set functions using constructor classes or
parametric type classes. Some (most?) object oriented languages without
polymorphic type systems can overload such operations.
John Peterson
peters...@cs.yale.edu
Yale Haskell Project