# deconstruction of subtyping

16 replies
extempore
Joined: 2008-12-17,

One more bucket of grist for your mills:

I find this angle on subtyping resolves some of the anxiety I always
feel that things don't quite fit together correctly. I am reminded of
PartialFunction and Function. People are usually surprised to find out
that PF inherits from F1 and not the other way around, but if we view an
F/PF as possessing constraints characterizing the values at which it is
defined:

F1 has all the constraints of PF, plus more
PF has all the functionality of F1, plus more

(This phrasing adopted from someone's similar expression regarding a
circle and an ellipse.) In that light neither of them should always be a
subtype of the other. But inheritance admits no subtlety: either they
have no inheritance relationship or one is the parent, now and forever.
I suppose the ability to reorder stackable traits means that's not
completely ordained, but practically speaking it's close enough.

James Iry
Joined: 2008-08-19,
Re: deconstruction of subtyping
What constraints does F1 have over and above PF?

On Wed, Jun 30, 2010 at 7:10 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:
One more bucket of grist for your mills:

http://alistair.cockburn.us/Constructive+deconstruction+of+subtyping

I find this angle on subtyping resolves some of the anxiety I always
feel that things don't quite fit together correctly.  I am reminded of
PartialFunction and Function.  People are usually surprised to find out
that PF inherits from F1 and not the other way around, but if we view an
F/PF as possessing constraints characterizing the values at which it is
defined:

F1 has all the constraints of PF, plus more
PF has all the functionality of F1, plus more

(This phrasing adopted from someone's similar expression regarding a
circle and an ellipse.) In that light neither of them should always be a
subtype of the other.  But inheritance admits no subtlety: either they
have no inheritance relationship or one is the parent, now and forever.
I suppose the ability to reorder stackable traits means that's not
completely ordained, but practically speaking it's close enough.

--
Paul Phillips      | One way is to make it so simple that there are
Analgesic          | obviously no deficiencies. And the other way is to make
Empiricist         | it so complicated that there are no obvious deficiencies.
all hip pupils!    |     -- Hoare

extempore
Joined: 2008-12-17,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 08:01:01AM -0700, James Iry wrote:
> What constraints does F1 have over and above PF?

If we name a function domain containing { A, B, C } and range R, then we
can imagine an interface:

trait Total {
def f(x: A): R
def f(x: B): R
def f(x: C): R
}

A partial function can implement any or none of those methods and be
fully implemented. A total function must implement them all. So the
total function has constraints the partial function doesn't.

Maybe you meant the question more concretely, like in scala today as it
stands. Given the fact that one can implement the total function to
throw exceptions and pretend it's a partial function, it's hard to say
there are meaningful additional constraints. I'm probably missing the
real point of the question, so feel free to re-pose it so I can't.

James Iry
Joined: 2008-08-19,
Re: deconstruction of subtyping
Yeah that was my question: given that "Function1" does not mean "TotalFunction", what constraints are on Function1 that aren't on PF?
F1 has all the constraints of PF, plus more
PF has all the functionality of F1, plus more
It seems like PF says "I have additional functionality that may or may not tell you where I am undefined" but there aren't really any differences in constraint.
On Wed, Jun 30, 2010 at 8:21 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:

Maybe you meant the question more concretely, like in scala today as it
stands.  Given the fact that one can implement the total function to
throw exceptions and pretend it's a partial function, it's hard to say
there are meaningful additional constraints.  I'm probably missing the
real point of the question, so feel free to re-pose it so I can't.

extempore
Joined: 2008-12-17,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 09:04:01AM -0700, James Iry wrote:
> It seems like PF says "I have additional functionality that may or may
> not tell you where I am undefined" but there aren't really any
> differences in constraint.

functionality: it's just that as an optimization, we removed Function1's
isDefinedAt method, since it's always def isDefinedAt(x: A) = true.

One can easily get caught up in the miscelleny. My point was that that
for inheritance in general and these two concepts in particular, there
is no One Right Way to model an inheritance relationship: and that this
indicates to me that a more granular abstraction may be a boon.

Johannes Rudolph 2
Joined: 2010-02-12,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 6:04 PM, James Iry wrote:
> It seems like PF says "I have additional functionality that may or may not
> tell you where I am undefined" but there aren't really any differences in
> constraint.

A F1 has to return a result on any element of the domain, while a PF
may not. This would be an additional constraint.

extempore
Joined: 2008-12-17,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 07:49:14PM +0200, Johannes Rudolph wrote:
> A F1 has to return a result on any element of the domain, while a PF
> may not. This would be an additional constraint.

He's saying that in practice this isn't true: F1 can throw an exception
on any element, and PF can be called with any element, whereupon it will
throw an exception. When Nothing is consistent with any return type,
then it's all lies and everyone is naked under their clothes.

James Iry
Joined: 2008-08-19,
Re: deconstruction of subtyping
An F1 may get stuck or throw an exception or shut down the JVM.  It need not be total
scala> val f : Int => Int = {x => error("HAHA!")}f: (Int) => Int = <function1>

On Wed, Jun 30, 2010 at 10:49 AM, Johannes Rudolph <johannes [dot] rudolph [at] googlemail [dot] com> wrote:
On Wed, Jun 30, 2010 at 6:04 PM, James Iry <jamesiry [at] gmail [dot] com> wrote:
> It seems like PF says "I have additional functionality that may or may not
> tell you where I am undefined" but there aren't really any differences in
> constraint.

A F1 has to return a result on any element of the domain, while a PF
may not. This would be an additional constraint.

--
Johannes

-----------------------------------------------
Johannes Rudolph
http://virtual-void.net

Johannes Rudolph 2
Joined: 2010-02-12,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 8:00 PM, Paul Phillips wrote:
> On Wed, Jun 30, 2010 at 07:49:14PM +0200, Johannes Rudolph wrote:
>> A F1 has to return a result on any element of the domain, while a PF
>> may not. This would be an additional constraint.
>
> He's saying that in practice this isn't true: F1 can throw an exception
> on any element, and PF can be called with any element, whereupon it will
> throw an exception.  When Nothing is consistent with any return type,
> then it's all lies and everyone is naked under their clothes.

Ok, point accepted. However, I'm not sure, if you really should take
every unchecked exception into account here. I mean, I'm pretty sure,
that if you do that, there are many theories which are not sound any
more.

extempore
Joined: 2008-12-17,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 08:35:02PM +0200, Johannes Rudolph wrote:
> Ok, point accepted. However, I'm not sure, if you really should take
> every unchecked exception into account here. I mean, I'm pretty sure,
> that if you do that, there are many theories which are not sound any
> more.

Oh yes, that is what I mean by "it's all lies." But you can't have it
both ways: in practice the only thing which distinguishes
PartialFunction's apply from Function's apply is that we expect the
former to be somewhat more likely to throw an exception. If we aren't
going to take exceptions into account when considering them then they
become indistinguishable.

You can't even say that calling isDefinedAt tells you anything
interesting, because even when true the apply can throw any exception.

If by some dependent type magic we could statically restrict
partialfunctions to being called with arguments for which they are
defined (which I realize is impossible in isolation) then we would have
some meaningful difference upon which to base an inheritance
relationship. As it is, what we have is "an inconvenient fiction".

odersky
Joined: 2008-07-29,
Re: deconstruction of subtyping

On Wed, Jun 30, 2010 at 6:27 PM, Paul Phillips wrote:
> On Wed, Jun 30, 2010 at 09:04:01AM -0700, James Iry wrote:
>> It seems like PF says "I have additional functionality that may or may
>> not tell you where I am undefined" but there aren't really any
>> differences in constraint.
>
> functionality: it's just that as an optimization, we removed Function1's
> isDefinedAt method, since it's always def isDefinedAt(x: A) = true.
>
No, that;s not true. In fact that would violate the Liskov Subtitution
Principle: if F1's isDefinedAt is always true, PF's
isDefinedAt could be no different. The right interpretation is that an
F1 will not tell you whether it's defined for its argument or not, but
a PF will.

Cheers

extempore
Joined: 2008-12-17,
Re: deconstruction of subtyping

On Thu, Jul 01, 2010 at 12:36:56AM +0200, martin odersky wrote:
> No, that;s not true. In fact that would violate the Liskov Subtitution
> Principle: if F1's isDefinedAt is always true, PF's isDefinedAt could
> be no different. The right interpretation is that an F1 will not tell
> you whether it's defined for its argument or not, but a PF will.

Ah. So we declare isDefinedAt to be a question which can only be asked
of PF, and limit the inheritance relationship to the apply. The second
method is the key to a grimy warehouse where PF hangs out with other PFs
and they all talk smack about Function1s like they're better than them.
Like we don't all know who their parents are. From that standpoint it
seems reasonably natural for PF to be the subtype: they are both
functions, but one can be quizzed.

Still, it's my impression that if you ask most people (math person,
computer science person, or otherwise person) which of those two ought
to be the subtype, they'll say F is a subtype of PF. I could be wrong
in that assessment, and even if it's true that doesn't make them right:
but if it is true, we should try to write something convincing about
this. I find people will use any "obviously wrong" thing to drop-kick a
programming language, even if it's right. And I hate losing people
before the starter gun has fired.

Martin Odersky
Joined: 2009-10-07,
Re: deconstruction of subtyping

Maybe the name partialfunction is the misleading thing here , it could

Esser 2
Joined: 2010-03-23,
Re: deconstruction of subtyping

IMHO:

The Liskov Subtitution Principle has nothing to do with the mathematical
notion of subtypes.
It just postulates, that any method of a supertype must be accepted by all
its subtypes.

If we define a class Real, all operations of Real may be accepted by a
(sub-)class Complex.

qed

friedrich

Johannes Rudolph 2
Joined: 2010-02-12,
Re: deconstruction of subtyping

Still, I don't understand why - for practical reasons - the current
inheritance scheme (PF <: F1) is seen as the best of the
possibilities. There are at least those possibilities:

1. PF <: F1 (current)
2. PF and F1 not related
3. F1 <: PF
4. PF <: AF and
F1 <: AF

where AF is

class AbstractFunction1[-T] { def isDefinedAt(t: T): Boolean }

1.
+ Convenience: A PF can be used everywhere a F1 is expected.
+ F1 doesn't have to implement isDefinedAt
- No type-safety: Even if you know that a PF will fail for some
values you can use it as if it didn't.
- => There's no user-definable way to enable this type-checking.
- F1 can't be used at places where PF is expected. (solution:
implicit conversion)

2.
+ Controllable type-safety: Can't pass PF as F1 generally. Enable by
explicit conversion or explicit importing an implicit conversion into
scope
+ F1 doesn't have to implement isDefinedAt
- Needs implicit conversion to pass F1 as PF

+ F1 can be used where PF is expected without conversion
- F1 has to implement isDefinedAt = true

4. as 2 but
+ A library can declare its expectations (PF = may fail, F1 = may not
fail, AF = don't care)
- F1 has to implement isDefinedAt

For me it looks like, the current solution is actually the worst one,
because you cannot possibly declare with types that you want a F1
which is defined for the complete domain and not a PF. (You actually
can by creating an implicit ambiguity but that seems a bit awkward.)

I think I would prefer 2. because you could probably preserve
compability with implicits and still could remove the implicit PF <:
F1 if you don't like it.

Johannes

On Thu, Jul 1, 2010 at 10:30 AM, Martin Odersky wrote:
> Maybe the name partialfunction is the misleading thing here , it could be
>

Esser 2
Joined: 2010-03-23,
Re: deconstruction of subtyping

Sorry, one more thing (as exception were mentioned!):

null and exception have both in common that they are "billion dollar
mistakes"
(the way they are!).

exception:
they are (mis)used for different meanings (look at java: RTE vs. Checked
Exception vs. Errors). As they are used as signals/messages (thread death,
interrupted exception), recoverable, unrecoverable errors.
Error is used, just because it cannot be catched as Exception.

There are 1000+ different types of exceptions, and hopefully as many
catch's(???). The poor programmer ignores exceptions most of the time,
because even if one can solve they problem, one will not come back to the
point where they are thrown to resume.

null:
null as a keyword in Java was a problem. Null is now a "real" type in Scala
with one instance null. Everything is better now as Null is a subtype of Any
and one may use the Liskov Subtitution Principle

scala> println(null)
null

scala> println(null.toString)
java.lang.NullPointerException

Here it is: the world of subtypes

friedrich

Joshua.Suereth
Joined: 2008-09-02,
Re: deconstruction of subtyping
I prefer quizzical functions to quizzable functions.

In any case, to answer Johannes,  I think in actuality a PartialFunction is defined for its entire domain.   It's just defined to throw exceptions for a portion of its domain.   As Paul stated, you could have a regular function that has the same behavior.   I believe this is why Martin called them "quizable" because Partial functions give you a chance to see what types of input won't immediately throw an exception.   Kind of like Phillip's "translucent" function that lets you see what class-types are not immediately rejected by a pattern match in the function.   You can think of these as refinements of behavior from a raw function.

Theoretically though, you are right.  A Partial function is only available for some portion of the domain.   In that theoretical ideal world, you'd also want the compile to catch when you use the partial function on a portion of the domain where it is not defined.   Scala opted for runtime checking of the domain, so the only "enforcing" it could do is make sure you called "isDefinedAt" and that is less than useful.
So... given the runtime check of input values, I think the current hierarchy actually makes the most sense.   PartialFunction is a refinement for a specialized type of function that gives you partial access into knowing what arguments it doesn't immediately reject with exceptions.   All functions can still throw exceptions, even when isDefinedAt returns true.
- Josh

On Thu, Jul 1, 2010 at 4:30 AM, Martin Odersky <odersky [at] gmail [dot] com> wrote:
Maybe the name partialfunction is the misleading thing here , it could be called quizzablefunction instead.