Now, most strongly-typed languages do give you some way to explicitly
circumvent type-checking (the "dynamic" type in Cecil, a downcast in Java).
These constructs can cause run-time errors if used carelessly -- but the
programmer has to make an explicit choice to use them.  Any code that avoids
these constructs will never cause a run-time type error.  It seems to me
that Dylan is much less explicit about identifying code that could cause
run-time type errors.

Of course, many people are perfectly happy with a dynamically-typed language
such as Smalltalk, and if Dylan sees itself as another language in that
category, I have no objection.  But Dylan programmers do seem to identify it
as a strongly-typed language -- or rather, as an optionally strongly-typed
language, in which you can prevent run-time type errors by following a
certain coding discipline.  I'm not convinced that is the case.

Here's a sample of some code that causes the kind of problem I'm talking
about:

  define abstract class <bird> (<object>) end;
  define class <sparrow> (<bird>) end;
  define class <penguin> (<bird>) end;

  define generic fly (b :: <bird>) => ();

  define method fly (s :: <sparrow>) => ()
    format-out("Sparrow flying!");
  end method fly;

  // don't define fly (p :: <penguin>) -- penguins can't fly!

  define method get-bird() => (bird :: <bird>)
    make(<penguin>);
  end method get-bird;

  define function do-it()
    let bird = get-bird();  // compiler doesn't know it's a penguin
    fly(bird);              // causes run-time dispatch failure
  end function do-it;

When I compile this sample with HD, in "production" mode, I don't get any
warnings.  But it causes a run-time dispatch failure.  Basically, the
<penguin> class fails to live up to its contract.  The failure should be
obvious to the compiler (or linker) in this case.  In other cases, it might
be harder to tell -- with multiple dispatch, the question of contractual
responsibility becomes much thornier.  But it seems that the HD compiler
doesn't make any attempt to catch this kind of error, and as far as I can
tell, the language definition doesn't require it to do so.

The Cecil language addresses these issues by defining a sophisticated type
system on top of the normal OO class system.  The purpose of Cecil's types
is precisely to define these sorts of contracts and let the compiler ensure
that they are fulfilled properly.  Dylan's types seem superficially similar
to Cecil's, but based on my experience I'd have to say that they don't
provide the same kind of safety that Cecil's do.

Another way to describe the problem is that Dylan's types define
implementations but not interfaces.  In Cecil, classes (actually objects)
define implementations, and types define interfaces.  In more traditional OO
languages like Eiffel (ignoring all the CAT problems for the sake of this
discussion), classes define interfaces and may define implementations as
well.  Real type-safety comes from having clearly-defined interfaces, which
Dylan doesn't support.

Can somebody prove me wrong, or shed more light on this issue?

Dylan is dynamically typed.  With the specializers on variables,
though, the programmer may give more type information to the compiler.
What the compiler chooses to do with that information is somewhat
open-ended.  To simplify a little, suppose there is some code such as

  ...
  let a :: <foo> = b;
  ...

A simple, purely dynamic, implementation would look up the value for
the variable b, check that instance?(b, <foo>), and, if so, assign
that value to a.  All type errors would be detected at run time.

A more sophisticated approach would be to analyze the code to try to
figure out the types of all values that flow into b.  Possibly (and
especially if the programmer makes good use of type annotation) the
compiler may figure out that all possible values of b will be of type
<foo>.  For example, maybe the preceding line is

   define method m (b :: <foo>)

In this case, the compiler may omit the type check before the
assignment.   Alternatively, the compiler may deduce that all possible
values of b will _not_ be an instance of <foo>;  in which case a
compile time error would be signalled.  Finally of course, the
compiler may not be able to tell, and some sort of dynamic type check
will be necessary.

One more thing that the compiler could do with the results of its
analysis is to tell the programmer what it deduced.  If the compiler
indicates all points where either a type check or a possibly-failing
dynamic dispatch occur, then code which has none of these points could
legitimately be called "statically type correct".

Harlequin Dylan has a similar feature -- code coloring (see View/Color
Dispatch Optimizations) in the HD Editor.  This technically colors
code according to optimizations applied to call sites.  Since code
cannot be directly called or inlined if there is a possibility of
dispatch failure, an "optimized" call site can be viewed as type
correct.

 Harry> A discussion has come up in some other newsgroups (comp.lang.object a few
 Harry> weeks ago, comp.lang.eiffel yesterday) about whether Dylan has strong static
 Harry> type-checking.  My impression, as a relative newbie, is that it doesn't:
 Harry> even if you scrupulously declare the types of all your variables and
 Harry> methods, you can easily write code that causes run-time type errors with no
 Harry> warning from the compiler, and with no indication in the code that you're
 Harry> doing anything dangerous.

--

Sullivan  http://www.ai.mit.edu/~gregs/

Does "open-ended" mean "not specified in the language definition"?  I.e.,
one valid compiler might accept a piece of code while another (smarter)
compiler might reject the same code as being non-type-safe?

Also, in cases where there's an error, this technique would localize it
incorrectly.  In my bird/penguin/flying example, it's not wrong to call
fly(bird) when bird is of type <penguin> -- after all, bird is of type
<bird> and there's a fly generic function on <bird>.  What's really wrong is
to declare the type <penguin> but fail to define a fly method for it.
Traditional OO languages would catch this error easily and identify it as a
problem with the <penguin> class.  But it seems that Dylan doesn't really
consider this an error, and if you coax the compiler into calling it an
error, it will say that the error is in the call to fly(bird) (which may be
in an entirely different module, written by a different programmer, who now
must dig into the definitions of <bird> and <penguin> and the fly generic
function to figure out what went wrong).

Again, I don't mean to be harshly critical of Dylan here, any more than I
would criticize Smalltalk for the same kinds of problems.  I'm simply
arguing that what Dylan provides isn't static type-safety as it's normally
understood.  Or as Lyn A Headley put it in comp.lang.eiffel yesterday,
"Maybe you guys have a different definition of static typing... I think
Dylan has a distinctly dynamically-typed feel to it."

That said, the culture of the Dylan is evolving in the direction of
the providing more and more compile time analysis and feedback.
People recognize its value.

...

Let's take a very simple example:

  define method add-two-integers (x :: <integer>, y :: <integer>)
    x + y;
  end method add-two-integers;

  define method attempt-the-impossible (z :: <list>)
    add-two-integers (z, z);
  end method attempt the impossible;

Two points about this example:

  The compiler can analyze add-two-integers, deduce the exact concrete
type of x and y, understand the set of available methods in the '+'
generic function, and inline the call to '+'.  This is possible because
the <integer> class is sealed, and so it cannot be given additional
subclasses, and because the '+' generic function is sealed over a
domain that includes <integer>.  In point of fact, Harlequin Dylan
makes this operation, and so integer arithmetic is often as efficient
as it is in C or Pascal or Assembly language.  This is true in spite
of the fact that <integer> is a full-fledged class and integers are
objects.  We don't take the Java shortcut, choosing instead to maintain
the consistency of our object model.

  Second point:  if this is your entire program, the compiler can deduce
that attempt-the-impossible will generate a type error.  It can understand
the type of z, it can understand that <list> and <integer> are disjoint,
and it can understand that there is only one method in the add-two-integers
generic function.  Harlequin Dylan will not refuse to compile the program
given above, but it will generate a serious warning when you compile it.
(Note: you'll still be able to run the program.  It may be that there are
other parts of the program that work fine, and that a type error in this
section shouldn't prevent you from testing the rest.)

  This type analysis is not rocket science.  Implementing it can be
more or less difficult, depending on how far you want to push things,
and what range of the language semantics you want to statically analyze.
But fundamentally, it is seems patently obvious that you can write
statically typed programs in Dylan.  If you disagree, we must have
different definitions of static typing, and perhaps you could let me
know what yours is.

  On the other hand, if you agree, perhaps you could forward this message
to those other news groups where people apparently don't understand
how Dylan works!

  -Andrew

p.s. give my regards to Thads if you talk to him.

--

                                            http://www.folly.org/~alms
This is our garden, although we have no grass.
-Bahrije Baftiu, Kosavar refugee in Macedonia

--

                                            http://www.folly.org/~alms
This is our garden, although we have no grass.
-Bahrije Baftiu, Kosavar refugee in Macedonia

Which we probably don't yet have :-)

I think it's interesting that what you get in Gwydion is:

Expected an instance of {the class <sparrow>}, but got {an instance of
<penguin>}
Aborted (core dumped)

This is interesting because it shows that the compiler knew quite a bit
about the situation.  In fact, here is the C code generated for do-it():

/* do-it{} */
descriptor_t * birdsZbirdsZdo_it_METH(descriptor_t *orig_sp)
{
    heapptr_t L_bird; /* bird */
    descriptor_t L_temp;

    /* #line {Class <unknown-source-location>} */

    #line 23 "./birds.dylan"
    /* get-bird{} */
    L_bird = birdsZbirdsZget_bird_METH(orig_sp);

    #line 365 "./condition.dylan"
    if ((birdsZbirdsZCLS_sparrow.heapptr == SLOT(L_bird, heapptr_t, 0))) {

        #line 24 "./birds.dylan"
        /* fly{<sparrow>} */
        birdsZbirdsZfly_METH(orig_sp, L_bird);
        return orig_sp + 0;
    }
    else {
        /* #line {Class <unknown-source-location>} */

        #line 368 "./condition.dylan"
        L_temp.heapptr = L_bird;
        L_temp.dataword.l = 0;
        /* type-error{<object>, <type>} */
        dylanZdylan_visceraZtype_error_METH(orig_sp, L_temp,
birdsZbirdsZCLS_sparrow.heapptr);
        not_reached();
    }

It would also be quite possible for d2c to issue an error or a warning
when it analyses the generic function for fly() and finds that there is no
applicable method for <penguin>.

d2c does neither of these things at the moment, but if it was desired it's
just a SMOP.

   define generic fly (b :: <bird>) => ();

... doesn't appear according to anything I can find in the DRM to be a
contract that all subclasses of <bird> will be able to respond to fly().
I agree that it would be very desirable to have this property, but:

a) Had fly() been an open generic (generics are sealed by default) it
would be impossible to ensure this at compile time because other libraries
could add fly(<penguin>).  It would also be impossible to ensure this at
link time, because methods could be added or removed from the generic
function at runtime.  However, given that the generic function is sealed,
the compiler could certainly check this, if it was part of the language.

b) a program that doesn't define fly(<penguin>) may be correct if it
happens to never call fly() on a <penguin>.  This is, of course,
impossible to prove at compile time.

c) a program that doesn't define fly(<penguin>) may still be correct even
if it calls fly() on a <penguin> because the program might trap and deal
with the "no applicable method" exception.

d) there would be an inconsistency in that a generic function that is not
declared explicity is implicitly the same as if it had been declared
taking parameters of type <object>.  It would be unreasonable to require
that every subclass of <object> should be able to respond to a call of
such a generic function.  We thus would need to make <object> an
exception.  Which seems sucky.

I'd sure like to see Dylan have (optionally) the sort of type-safety that
you want.

What I think I could support either:

1) a compiler switch that optionally causes the compiler to check that any
generic function for which at least one required parameter is declared to
be of a class other than <object> must have an applicable method for every
subclass of that class.  Where possible (sealed class and either sealed
generic or sealed domain) this is checked at compile time, otherwise it is
checked immediately at program startup, before main() is run.

Actually, due to add-method() and remove-method() this may not be possible
at program startup, but it could be redone at the first execution of the
generic method after add-method() or remove-method() are used.  Or, we
could just not do it at all for open generics.

I'm not sure whether this counts as a change to the language defnition or
not :-) but I think I'll put in on my wish-list for d2c.

OR

2) a new pair of keywords in the declaration of a generic method.  Perhaps
"covering" could be one of them, but I'm not sure what the opposite should
be.

Clearly this *is* a language change, and would need veeeery careful
consideration.

What Dylan doesn't do is guarantee that all aspects of the interface are
implemented.

Objective-C's "protocol"s and Java's "interface"s are better in that regard.

Since Dylan already has full multiple inheritence (unlike Obj-C and Java),
we have no use for a separate "protocol" concept, but it might be useful
to be able to specify the "covering" attribute for every method on a
particular (abstract?) class.  Hmmm ... maybe "protocol" and "adhoc" could
be the opposites, and could apply to either a class or to a generic
function?

Experts?

-- Bruce

In a program not intended to be fully type-safe, it's OK just hwo it is
:-)  It would be nice if we could support both styles.

-- Bruce

A true static type system must be flexible enough to allow the programmer to
express his/her intentions clearly, so that the compiler can verify that
those intentions are fulfilled.  Dylan's type system allows programmers to
express _some_ intentions, and compilers may point out _some_ violations of
those intentions at compile time.  The language extensions you proposed
(such as a "covering" keyword) would improve the expressiveness somewhat.
They might improve it enough for me to consider Dylan a true
statically-typed language.

For a language like Dylan, I would consider the following set of
capabilities as an ultimate goal:

1) You can write code with few (or no) type annotations, and the code will
be type-checked at runtime.

2) You can add type annotations in various ways to express your intentions
(or "contracts") more fully.  If you do so, the runtime system will issue an
error when you when you violate your stated intentions.  The compiler will
warn you of some violations but perhaps not all.

3) You can instruct the compiler to warn you more aggressively about
potential violations.  In this mode, any program that gets past the compiler
without warnings is guaranteed to run without runtime type errors.

4) Since the above mode is awfully restrictive, there should be some
language constructs you can use to circumvent it in specific places.  These
would be the equivalent of casts in Java: constructs that are known to be
dangerous and are used when you specifically need dynamic type-checking
instead of static type-checking.  The compiler wouldn't warn about these
constructs.  The constructs must be identifiable locally, without doing
whole-program analysis -- that is, it should be simple to write a tool that
would point out all the locations of these constructs in your code.

5) If a program runs correctly using dynamic type-checking, it should be
possible to rewrite it to use static type-checking without too much trouble,
perhaps using the known dangerous constructs in a few places.  The basic
paradigms of Dylan programming should be expressible within the static type
system.  When a program moves outside of those paradigms for some reason, it
can use the dangerous constructs as needed.

I would say that today's Dylan satisfies 1 and 2 but not 3 and 4.  5 is
clearly more subjective than the others, but I think it should be used as a
goal when designing the language features needed by 3 and 4.  For example, I
would say that Java (without generics) fails to satisfy 5, because you need
to use casts to implement common paradigms like collection classes.  Today's
Dylan _could_ be made to satisfy 3 by simply changing the compiler
implementations, but you'd be throwing out the baby with the bathwater:
you'd make it impossible to write complex programs.  In other words, if you
tried to satisfy 3 by changing the compiler only, you'd be violating 5.  The
only way to satisfy 3 and 5 together is to change the language definition.

I'm curious to see whether the Dylan language will evolve in this direction
over the next few years.  I'm also curious about how much work it would take
to accomplish this.  I believe that Cecil's type system satisfies all 5 of
the goals, but it's designed from the ground up specifically for that
purpose, and it also relies on whole-program analysis which may not be
feasible in a dynamic language like Dylan.  It would be great if Dylan's
type system can be upgraded smoothly to meet the goals.  (Even if it can't,
I'd still of course recommend Dylan to anybody interested in a
high-performance dynamically-typed language!)

- an explicitly declared sealed generic function, with
- specialisers that are sealed classes

... to be a contract to supply implementations of that generic function
for all subclasses.  The same would apply to an open generic function that
has been declared to have a "sealed domain" on specialisers that are
sealed classes.

What either of these situations means is that:
- no new subclasses can be defined in this branch of the class tree,
either at runtime or in another library
- no methods that would affect the dispatch of this generic function on
this branch of the class tree can be defined, either at runtime or in
another library.

In these cases the compiler *can* statically check that there are no
potential runtime errors -- in fact d2c already does, in order to figure
out whether or not to generate a conditional call to no-applicable-method
in the generated C code -- and can issue at least a warning if not an
outright error.

I'll see if I can figure out how to add this warning to d2c. (I'm just
starting to poke around in the guts if it, so it may take a while -- I've
been confining myself to the runtime system so far).

-- Bruce

Please read the Dylan article in Develop, available at
http://www.mactech.com/articles/develop/issue_21/21strassman.html
It shows a project starting with typeless slots moving to stronger
type-checking, and use of classes to enforce contracts.

One of the things that attracted me to Dylan was the ability to work type-safe
or dynamic in the same language. In the same function, even. Dylan is as
type-safe as you make it, and has a far stronger and more dynamic ( the two are
not opposing ) grasp of type than many langauges.

Updating Patrick Beard's Mac Toolbox code, I am finding practical examples of a
powerfully flexible type system of a level undreamt of in C++ or Java.

- Rob.

At the very least, some changes in the intuitive semantics of the language
will be required.  For instance, according to Bruce, declaring a generic
function with a <bird> argument does not amount to a contract that all
concrete subclasses of <bird> must provide an implementing method.  At
least, that's not how generic function declarations have been seen
historically.  Maybe we could change our view of the meaning of a g.f.d.,
and say that it does express such a contract in some cases.  That's not a
change to the language definition, but it's a change in point of view that
might take some existing Dylan programmers by surprise.  It would be nice if
this kind of change (plus changes to the compiler implementations) is all
that's required to make Dylan statically type-safe.

Executive summary as I understand it:

1) a Dylan compiler may strenuously warn the programmer about possible
runtime errors

2) a Dylan compiler may have an option (could even be the default?) to
refuse to link & run the program if there are serious warnings

3) if the user wants to run it anyway, then they should be able to.

I think there's room to keep everyone happy here, *without* changing the
language definition.

-- Bruce

Hi guys,

IMO, one of the best intentions of Dylan is that it is a statically
compiled language except when the programmer explicitly requests for
some aspects of it to be dynamic. This means that by default Dylan
programs should be efficient with accurate compile-time warnings, and
the cost of dynamic programming can be carefully introduced as
necessary. I think there are a few areas in the current design that
fall short of this lofty goal.

Here's an example that has been discussed a lot at Harlequin, I'd like
to hear some more opinions. The Dylan language specification states
that a generic function can list a set of keywords, but that any
method is allowed to add new keywords. This has the unfortunate side
effect that the compiler can never determine the valid set of keywords
for an open generic, unless the particular domain in question is
sealed.

So, with the following code:

  define abstract class <foo> (<object>)
  end class <foo>;

  define open generic foo
      (foo :: <foo>, #key x :: <integer>, y :: <integer>) => ();

  define function bar
      (f :: <foo>) => ()
    foo(f, z: 20)
  end function bar;

the compiler cannot issue any warnings about the keyword z: because
there is no way to know if that keyword is actually accepted by the
applicable method.

If you consider how many important generic functions are declared
open, a large percentage of Dylan code passes through Harlequin Dylan
without any warnings for incorrect keyword arguments. This means that
bugs in obscure parts of the code are not found at compile-time, and
so only get found by very thorough QA, or worse still are first
discovered by customers.

IMO there needs to be a language change to allow a generic to declare
exactly the set of allowable keywords, that way the compiler can issue
warnings. IMO this should be the default, based on the 'static by
default' principle, so creating a generic that allows methods to
handle extra keywords would need to take an extra argument. Something
like:

  define open generic make
      (class :: <class>, #key, #other-keys)
   => (object :: <object>)

The distinction between #other-keys and #all-keys would be that it is
an error to pass unacceptable keywords to a function that takes
#other-keys, but it isn't for one that takes #all-keys (the extra
keywords are just ignored).

My contention would be that #other-keys really isn't needed very
often, almost every generic function that I can think of takes a rigid
set of keywords. It is unfortunate that making this rare situation the
default disallows the compiler from enforcing the validity of keyword
arguments at compile-time.

Well, that was pretty long, it's just one example of several places in
Dylan that don't properly scale to a static programming style. I
believe with some careful thought we could redesign the langauge to
fix these issues, and that this would make an already great language
even better.

Cheers,

Andy

P.S. I would like to make clear that I'm not attacking dynamic
programming, in fact I love it. I also would like to strongly endorse
Andrew Shalit's point that a program with potential runtime errors
should be allowed to be built and run, at the very least this feature
is of great benefit when writing test suites:

  check-condition("Verify integer overflow",
                  <integer-overflow>,
                  $maximum-integer + 1);

----------

Harlequin Inc.

On the other hand, I do think it would be possible to write a Dylan
program from scratch which had no warnings of type 1, 2, or 3.  This
would require that you write in a subset of Dylan, but it would still
be a very powerful subset.  By supporting this kind of warning mechanism,
we would also gain insights in how the language would need to be changed
to extend this type safe subset.

  -Andrew

p.s. to Harry: if you've only made it half way through the DRM, skip
ahead and read the chapter on sealing.  That should make a lot of
this clearer.  That's where you lock things down, and really support
static compilation.

--

                                            http://www.folly.org/~alms
This is our garden, although we have no grass.
-Bahrije Baftiu, Kosavar refugee in Macedonia

Should have written "of any substantial size" (i.e. large).

--

                                            http://www.folly.org/~alms
This is our garden, although we have no grass.
-Bahrije Baftiu, Kosavar refugee in Macedonia