An Overview of the Dylan Type System

http://dylanfoundry.org/2014/08/28/type-system-overview/

by BruceM • 12 years ago

71 8 12 years ago

tel• 12 years ago

Convenient singleton types are quite interesting—what limitations do they have? Clearly this can become a massive thorny issue quickly if you try to achieve singletons in a general fashion.

BruceM4• 12 years ago

The main issue with them is that they require that the object be ==, not just =. But given that almost every use that I know of for them in the core libraries is for integers or symbols, this isn't a big issue at all.

Other than that, they seem to work out fine.

ekidd• 12 years ago

I've previous written about techniques for implementing fast multiple dispatch using Dylan's type system: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-404/

In my personal experience as a Dylan programmer and amateur compiler maintainer, here's what I liked and disliked about Dylan's types:

- Multiple inheritance and multiple dispatch have surprisingly clean semantics in Dylan, except for limited types. Yes, you really can have complicated multiple inheritance and runtime multiple dispatch in one language. It's not even that hard to implement, if you know the right tricks.

- Limited integer types were a mess, particularly when it came to multiple dispatch. You don't want two overrides of a function, one which applies to values from -1 to 7, and another which applies to values from 6 to 11. Similarly, limited collection types were supposedly used to implement typed collections, but it always felt like it was bolted on.

- Singletons had clean semantics but they made dispatch more expensive.

- Both type unions and subclass types worked quite well in practice.

- Dylan's design suffered from "sufficiently smart compiler syndrome" in several areas. This manifested as language features which were painfully slow in the general case, but which could run quite fast in a few special cases. This made it hard for users to build a good mental model of Dylan performance. It also meant that Dylan compilers needed to provide multiple implementations of certain features and choose between them at compile time.

Dylan was an exceptionally good language for its time, and I had a ton of fun using it. I keep meaning to try out Julia, which apparently inherits quite a few cool features from Dylan.

yarrel• 12 years ago

The Fun-O Dylan compiler highlighted text for performance didn't it?

BruceM4• 12 years ago

Yes. The compiler kept track of which source locations were impacted by which types of "method upgrades". Was something inlined? Dead code eliminated? Converted to a direct call to an internal entry point (avoiding dispatch)? Converted to a direct slot accessor? All of those could be colored differently.

I'm thinking of writing a blog post along the lines of "So, you thought that was a function call, eh?" as Dylan treats everything as a function call at the syntax level, but can go and optimize it into something better. That'll be a pretty complicated post though with a lot of Dylan + generated code examples and I know that I lost some people today by showing C in the type system overview post.

BruceM4• 12 years ago

Hey Eric!

I've previous written about techniques for implementing fast multiple dispatch using Dylan's type system: http://www.cs.dartmouth.edu/reports/abstracts/TR2001-404/

We may be coming back to you about this. The dispatch mechanism implemented in Open Dylan is great for 1990s hardware, but less so on today's architectures.

Limited integer types were ....

One of my next posts (already a good deal written, but a lot to go) is about the "limits of limited types" and looks at how they might be generalized into some more interesting and broadly useful types, namely parametric polymorphism and refinement types. There's some interesting research required to pull that off though.

- Both type unions and subclass types worked quite well in practice.

Funny ... I forgot to mention subclass types (since they're technically an extension to the language and not part of the core specification).

Dylan was an exceptionally good language for its time, and I had a ton of fun using it.

I hope that you're on the hackers mailing list still, then. We're going to start some discussions this coming week about the future of Dylan and making some fairly drastic changes to things.

One thing is that we'd like to make it much easier to hack on. The compiler is, as you indicate, fairly complex and it would be great to reduce the build time, add more tests, and in general, make it simpler.

Another is that some parts of Dylan could use an update in keeping with modern research and theory. The type system is an interesting example of this, and that's why I wrote an overview of what we have now. We'd like to increase the knowledge available to the compiler and increase the amount of static checking that can be done. I've already written about adding function types, we want to add parametric polymorphism in a general sense, and there are other things that can still be improved.

There are also just some missing features in the language & implementation like vector math, a solid Unicode definition and implementation. It would be interesting to revisit mutability of some things.

We'll see!

joesb• 12 years ago

I like Dylan for its generic function and restart system is probably what should have been in Common Lisp. Generic function is the same in Common Lisp, but Dylan actually utilizes it in the standard library.

BruceM4• 12 years ago

This does make the compiler work much harder though! Having to optimize dispatch everywhere makes it quite a different thing from how a good optimizing Scheme or CL compiler works.

An Overview of the Dylan Type System

Related Stories