Re: the forward method [dynamic vs. static typing]

[address@hidden]

Ken Shan writes:
> On 2003-12-11T03:26:54-0500, FranklinChen@cmu.edu wrote:
> > That printing code is not faithful to your intention, which was
> >         data SuperList a = SuperList a (SuperList [a])
> > The code you wrote reflects the intention
> >         data SuperList a = SuperList a (Maybe (SuperList [a]))
> > which is quite different.
> 
> If the printing code I gave is not faithful to my intention, then
> neither is the data structure definition that you gave, even though
> you explicitly asked me whether the definition you gave is faithful to
> my intention.  A C++ pointer can be either null or non-null; non-null
> pointers can be expressed in C++ as references.

True, my compile-time implementation was not faithful to the Haskell,
because I was changing the task and illustrating a tangent point.
 
> > C++'s NULL is a value, not a type, so it is impossible, as you correct
> > indicate, to write a function template using an encoding of Maybe in
> > which NULL is a Nothing and a pointer is a Maybe.
> 
> Are you drawing a distinction between C++ and Haskell here, in that
> C++'s null is a value where as Haskell's Nothing is a type?  But in
> fact, Nothing in Haskell is a value, not a type.

No, I was not drawing such a distinction, since it would be of course
false.  I was speaking loosely with regard to the key point that NULL
in C++ has no type, while Nothing does have a type.  This is actually
a genuine problem that who knows if the C++ committee will eventually
resolve.

Also, given that NULL is not an object, one cannot override methods on
it, to fully simulate sum types in C++.  This is why, in order to
simulate Maybe in C++, you need to define a Nothing class.

Therefore, C++ NULL is pretty evil.

> In any case, I would be happy to switch as you did to the Haskell data
> type definition
> 
>     data SuperList a = SuperList a (Maybe (SuperList [a]))
> 
> However, the two approaches to coding in C++ you presented are not as
> expressive as Haskell type classes.  To be more concrete, let me provide
> not just the above data type definition but also some Haskell code
> manipulating that data type in a way that I (still) don't know how to
> achieve with C++ (templates).

I never claimed C++ was as expressive as Haskell.  We all know it
isn't.

The only reason I brought anything up at all was to address a very
specific point, i.e., the claim that printing could not be made
generic.  I disproved it in two different ways (one of which I
posted), though both could be considered "cheating".

> Here is a complete Haskell program incorporating the data type
> definition above:
> 
> >   module Main where
> 
> >   data SuperList a = SuperList a (Maybe (SuperList [a])) deriving Show
> 
> >   make :: a -> Int -> SuperList a
> >   make a 0 = SuperList a Nothing
> >   make a n = SuperList a (Just (make [a,a] (n - 1)))
> 
> >   main :: IO ()
> >   main = getLine >>= print . make True . read
> 
> The crucial point here is that the "make" function takes an arbitrary
> integer and returns a SuperList of that depth.  The main program ("main"
> above) simply reads an integer (say "n") from standard input and returns
> a SuperList of that depth (namely "make True n").

It would be possible to encode part of the "make" functionality (using
either the static or dynamic method) by using a Factory pattern, but
I'm not going to try, because it would be messy and we already know
that it's not going to be really faithful to the Haskell anyway.

> It does not suffice in C++ to simply define a Show class with a virtual
> member function for printing to an ostream, because that solution does
> not extend to
> 
>   - comparing two SuperLists of possibly different depth for
>     equality (say by overloading operator==);
> 
>   - storing multiple SuperLists of possibly different depth in a single
>     container, say vector.
> 
> Two SuperLists should be compatible for equality comparisons or storage
> in a homogeneous array iff their root type ("a" above) is the same, even
> if they may be of different depth.  Indeed, different branches of the
> same SuperList may be of different depth, so a C++ solution that encodes
> the depth or shape of a SuperList in its type is overly specific.  On
> the other hand, two SuperLists whose root types are different should not
> be eligible for equality comparisons, even if they are both printable to
> ostreams.

The code I posted doesn't do this stuff, of course.  It's the code I
didn't post, but compiles and runs fine, which does the following:
- SuperList<T> for all SuperLists of different depths (and therefore
  storable in a homogeneous container)
- ostream output
- equality comparison

It may be cheating, but the way to do it was to make printing and
equality comparison virtual, and override them appropriately.  It's a
simple-minded encoding of sum types and functions over them by means
of classes with overriding.

A small sample of it:

/*
t = SuperList (1, Just (SuperList ([3, 1, 4, 1, 5, 9], Just (SuperList
([[3, 1, 4, 1, 5, 9], [2, 7, 1, 8, 2, 8]], Nothing)))))
t1 = SuperList (2, Just (SuperList ([3, 1, 4, 1, 5, 9], Just
(SuperList ([[3, 1, 4, 1, 5, 9], [2, 7, 1, 8, 2, 8]], Nothing)))))
u = SuperList (2, Just (SuperList ([3, 1, 4, 1, 5, 9], Nothing)))
(t == t1) = 0
(t == u) = 0
(t1 == u) = 0
(u == u) = 1
*/
  SuperList<int> &t = 
    makeList(one, 
             makeJustList(v, 
                          makeJustLast(lv))); 
 
  SuperList<int> &t1 = 
    makeList(two, 
             makeJustList(v, 
                          makeJustLast(lv))); 
 
  SuperList<int> &u = 
    makeList(two, 
             makeJustLast(v)); 
 
  cout << "t = " << t << endl; 
  cout << "t1 = " << t1 << endl; 
  cout << "u = " << u << endl; 
 
  cout << "(t == t1) = " << (t == t1) << endl; 
  cout << "(t == u) = " << (t == u) << endl; 
  cout << "(t1 == u) = " << (t1 == u) << endl; 
  cout << "(u == u) = " << (u == u) << endl; 

-- 
Franklin