On 15/08/2012, at 3:32 AM, Dobes Vandermeer wrote:
> It's impossible in principle, theory, and practice.
>
> I can easily imagine a list of shapes. There I just did it. The universe
> did not implode.
I can easily imagine my yacht can go 20 knots in a 1 knot breeze and
I have a machine that makes electricity out of air.
> If I have a program that calls for "a list of fruits and vegetables" I might
> construct that using a union type, but the final product is a heterogeneous
> list.
No, it isn't, it's a homogenous list of type EdiblePlant. You have *unified*
the various
types into a single type.
> Not really, you can use the default "_" case to catch everything that isn't
> relevant to the code at hand. The felix compiler does this a lot.
And it''s a huge source of errors. I've been working to eliminate wildcard
matches
for this reason. Writing out all the cases is much better. The compiler then
forces
me to handle the new case everywhere it needs to be handled.
About 50% of the time spent implementing the ** tuple stuff
was going "Oh, I forgot to add a handler for that case in this
function". Seriously!
The problem was the relevant cases, like Unification algorithm,
are considering a *relation*. Its a binary operation. So and exhaustive list
of cases requires N^2 patterns. Easy enough if N=2 or 3. Not so good
when N=15 or something ;(
> However, you DO have to modify the original union to add a new case,
> which makes it hard to extend a library that uses unions.
(1) Unions don't obey the open/closed principle.
(2) if you're using a union because its the right type then
(3) there's no alternative and the resulting invasive behaviour on change
is not only a consequence .. its also desirable
> A library that wants to be extensible has to use functions (perhaps in a
> record or tuple) to operate generically on the objects. Then can a client
> of the library provide their own "type" of objects by providing the required
> operations as closures.
If you mean like Java, then no, that does not even count as a solution.
Only type safe solutions are of any interest.
Functions provide abstraction. There is absolutely nothing
abstract about a list, heterogenous or otherwise.
Casting in OO is nothing directly to do with OO or subtyping.
It is indirectly related in two ways:
(1) OO programmers typically don't have the faintest idea about
how to design programs because they either didn't go to a good
school, or they got stuck with a moronic language that makes
everything OO. They never used a decent language like Ocaml,
which, by the way, has a vastly superior object system. There
are no casts in Ocaml, objects use structural typing.
(2) Casting is required because OO simply does not work.
It is not possible to model most abstractions of interest
with OO, so we need to provide a way to hack it and break
the type system.
OO/subtyping is useful in a well defined context and not otherwise.
If your abstraction can be modelled entirely with properties,
that is, with methods accepting exactly one variant argument,
namely the object, then OO can be used and provides
the advantage of type safe runtime dispatch.
Example: device driver. Perfect for OO. A method
like
object->write(char)
has one variant arguemnt: the object. The second argument
"char" is not variant so it doesn't count. Felix should have
objects with virtual functions because this kind of dispatch
IS useful technology. It just isn't suitable as a *paradigm*.
Any abstraction which requires two variant arguments
cannot be modelled with OO. For example, numbers.
object-> add (object)
Does not work. Cannot work. There is no way this can
ever work. It is easy to prove it cannot work so do not
waste time arguing. The simplest form of the proof is:
Oo provides linear dispatch: N subtypes
are supported by one method.
Binary operations require TWO variant arguments,
that is, quadratic implementations. N^2.
OO cannot model binary operators.
Because N^2 > N.
QED
This means OO cannot be used to model any relations.
Almost all problems in computing are relations (often
with more than two parameters).
Therefore OO is useless as a paradigm. Object *Orientation*
simply does not work. Its a fraud. It advertises the ability
to model abstractions and fails immediately on the most
trivial cases.
This does not mean objects, classes, and vectored dispatch
are useless, it means they're only useful in a limited context.
Again: the context is well defined so you can easily check when
an OO solution to a subproblem in a program can be sustained.
Felix uses OO in the generated C++ to model variables
of function type. It works great! Every function is derived
from an abstraction representing the function type.
The variables are pointers to the abstraction, so they can
accept any function object of the correct type .. and no others.
The function is called by vectored dispatch (virtual function)
to an apply() method.
A complex OO based solution is also used to do asynchronous
OO which works on all platforms, with OO based dispatch
handling the different requests and platforms. This one is
not quite right (because the polling systems don't quite work
in a way that can be suitably unified) but it's reasonable.
> Sure, but actually you have a lot of places where you use the default "_"
> case, so you don't really have to update every place the type is used.
You're missing the point. I do have to!
The problem is that the type system/Compiler is not forcing me to do so
*because* of the wildcards.
I hope you understand. That is the PROBLEM. Its the same
with OO solution where you forget to do a cast in a particular
place for your new "type". The problem is, the method isn't
safe, in OO it is *intrinsically* unsafe and cannot be made safe.
In Ocaml, I have turned on Warning is Fatal Error in the
event i miss a case, but for that to actually force me
to do the right thing, I have to abstain from using wildcards.
Wildcards are there because it is very hard (research problem hard)
to prove a pattern matching set is exhaustive. It can be done in
some cases, but we don't want to know when its exhaustive,
we want to know when it isn't.
Ocaml regularly tells me (when I use matches that
can be proven exhaustive or not) that I have missed
a case and it even tells me which ones! In fact that's
how I add a new case -- I rely on the "IDE" which jumps
me to the place I need to put in the handler for the new
case, I do so, then I recompile.
Sometimes I can't figure out what to put so i do this:
| NewCase -> assert false
and then at run time when I get the assertion i put in
debug prints to see what it is I need to do "by example".
Its a way of cheating the type system with dynamics!
> Nor do you have to do so in Java, you only override the methods that are
> actually different for the new type.
That's a nice example of the extreme stupidity and confusion of Java.
If you have OO a derived class is supposed to be a subtype.
That means it is NOT "a new type".
But actually, you're using downcasts and dynamics to trick
the idiotic type system into implementing unions, because
the language designers were too ignorant to provide them
in the first place.
This is common in most programming languages.
At least C has a union type, even though it is not the required
discriminated union, it at least allows an implementation,
even if you have to hand roll it.
C++98 did not preserve the required property, against my explicit
intentions. Politics. The property was restored in C++11 using
the same rule changes I suggested before C++98 standard.
Original committee -- too ignorant to understand the importance
of unions. New committee -- a bit more knowledgeable both
because of better theoretical knowledge AND bitter experience.
> I don't think this is really the only advantage ... you could probably think
> of some more if you put your mind to it!
>
> For example in dynamic languages you don't have to declare the types of
> things, so you get a lot of "genericity" for free.
In almost every functional language: Ocaml, Haskell, you pretty much don't
have to declare the types of things either. Its called type inference. For
example:
let add x y = x + y
Do you see any types declared?? Nope. The compiler knows x,y
have to be ints.
Felix doesn't do type inference. It does overloading instead.
That's a design choice which is somewhat arbitrary.
> It's much easier to implement generic algorithms without types than with,
> because type systems are often limited in what they allow.
You have hit the core of the issue right there.
There is a name for this. Its called the Expression Problem.
This means: type theorists do not know enough to design a
type system expressive enough to support many correct ideas.
Therefore, if you have static typing you have to work around
the limitation of your type system.
Generally, the first step is to throw out your stupid programming
language and get one with a good type system. That helps
a lot. Haskell or Ocaml for example, or Scala, and maybe Felix.
This doesn't solve the problem, because all those languages have
type systems with limited expressivity, However all those systems
are being *actively* developed to improve the type systems.
If you do this, you still need some dynamics. Typically this is done
with strings or integers or something. The point is to limit it
as much as possible AND to try to see how the type system could
be improved to support what you're doing.
> Consider the difficulty of iterating over a tuple in Python compared to
> Felix as a worst case for statically strictly typed languages. Not that this
> kind of thing MUST be so difficult in Felix, it just takes a lot more work to
> support.
Do you mean "in the language as it is at present"? Then yes, because the support
is being developed as we speak.
You will of course note that it is quite easy to do what Python does in Felix.
Python uses a fixed set of core types plus classes (which are effectively
another fixed type).
So it is easy to do this in Felix with a union. What python does is actually
quite lame
by comparison to the tuple generics I'm implementing in Felix because what
my implementation is doing is supporting ANY types.
Python can't do that, it isn't even close to be genuinely generic.
You get a fixed set of structures and primitives in Python
(you can add more in C extensions but not in Python itself).
> Dynamic languages often use hash tables and dynamically sized arrays for just
> about everything. This makes is easy to "extend" objects - adding a field
> means you simply assign it where you need to assign it, and read it where you
> want to read it: no need to declare it! If the field is only written and
> read once, this is a 30% reduction in code, which is nothing to laugh about.
This is called structural typing. In Felix tuples, records, and pure sums and
variants
provide structural typing.
You can also use nominal typing: structs and unions.
You should note that the Ocaml object system also uses structural
typing. This extremely important. It is VASTLY superior to nominally
typed object system (Java, C++). Roughly, a class B is a subtype of A if its
structure
matches (has all the required methods): you do NOT need to use inheritance. You
add a new
"supertype" of a type AFTER you have the type without breaking anything.
There is a downside: the occasional accidental hijacking which is a feature
of structural typing, and, the performance overhead (dispatch requires
a hashtable -- its quite fast but not as fast a vectored dispatch [indirection])
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
