Generalized Algebraic Data Types and Object-Oriented Programming

Generalized Algebraic Data Types and Object-Oriented Programming. Andrew Kennedy and Claudio Russo. OOPSLA, October 2005, San Diego, California.

Generalized algebraic data types (GADTs) have received much attention recently in the functional programming community. They generalize the type-parameterized datatypes of ML and Haskell by permitting constructors to produce different type-instantiations of the same datatype. GADTs have a number of applications, including strongly-typed evaluators, generic pretty-printing, generic traversals and queries, and typed LR parsing. We show that existing object-oriented programming languages such as Java and C# can express GADT definitions, and a large class of GADT-manipulating programs, through the use of generics, subclassing, and virtual dispatch. However, some programs can be written only through the use of redundant run-time casts. We propose a generalization of the type constraint mechanisms of C# and Java to avoid the need for such casts, present a Visitor pattern for GADTs, and describe a switch construct as an alternative to virtual dispatch on datatypes. We formalize both extensions and prove a type soundness result.

I've been waiting for awhile for this paper to be available online.

This paper is, of course, related to the other items posted here about GADTs. The examples in the introduction might be somewhat relevant to the recent discussion about the static versus dynamic features of Java, and its type system.

Software Factories at OOPSLA 2005

See here for some examples/demos from Microsoft.

The papers presented at the International Workshop on Software Factories (held at OOPSLA 2005) are avialable online as well.

OOPSLA 2005: Io, a small programming language

(via Keith)

Io is small, pure object oriented, prototype-based programming language. The ideas in Io are mostly inspired by Smalltalk (all values are objects), Self, NewtonScript and Act1 (prototype-based differential inheritance, actors and futures for concurrency), LISP (code is a runtime inspectable/modifiable tree) and Lua (small, embeddable).

The paper and slides are available here.

Smalltalk case-statement

When the tutor said that Smalltalk has no case-statement, he meant it has no case-statement in the base class library.

Wiki page that shows you how to write a case construct with Smalltalk's surprisingly versatile syntax. Here's what it looks like:

aValue switch
   case: [matchCode1] then: [actionCode1];
   case: [matchCode2] then: [actionCode2];
   default: [otherCode].


ContextL is a CLOS extension for Context-oriented Programming. Currently, there is no documentation available, but you can find a small test case in the distribution and an introduction to ContextL's features in a first overview paper.

The paper says:

We present ContextL,a language extension for the Common Lisp Object System that allows for Context-oriented Programming. It provides means to associate partial class and method definitions with layers and to activate such layers in the control flow of a running program. When a layer is activated, the partial definitions become part of the program until this layer is deactivated. This has the effect that the behavior of a program can be modified according to the context of its use without the need to mention such context dependencies in the affected base program. We illustrate these ideas by describing a way to a)provide different UI views on the same object while b)keeping the conceptual simplicity of OOP that objects know themselves how to behave, in this case how to display themselves. These seemingly contradictory goals can be achieved by separating out class definitions into separate layers instead of separating out the display code into different classes.

Sounds kinda like AOP to me. It intriguings, anyway.

Tim Bray on Ruby

How I got here was, two recent pieces of writing that made me think heavily were Ruby-centric: Mikael Brockman’s Continuations on the Web and Sam Ruby’s Rails Confidence Builder... So I went and bought Programming Ruby ('Pickaxe' in the same sense that Programming Perl is the 'Camel book')

The conclusion of this piece is that Ruby looks like more than a fad, so LtU readers who still haven't checked it out might want to do so...

Where are the other editors, I wonder?

A Typed Intermediate Language for Compiling Multiple Inheritance

Juan Chen. A Typed Intermediate Language for Compiling Multiple Inheritance.
This paper presents a typed intermediate language EMI that supports multiple and virtual inheritance of classes in C++-like languages. EMI faithfully represents standard implementation strategies of object layout, "this" pointer adjustment, and dynamic dispatch. The type system is sound. Type checking is decidable. The translation from a source language to EMI preserves types. We believe that EMI is the first typed intermediate language that is expressive enough for describing implementation details of multiple and virtual inheritance of classes.

If you really must have mutiple inheritance...

A Theory of Distributed Objects

A Theory of Distributed Objects - Asynchrony - Mobility - Groups -Components. Denis Caromel and Ludovic Henrio.

Distributed and communicating objects are becoming ubiquitous. In Grid and Peer-to-Peer environments, extensive use is made of objects. This book provides a general theory for distributed objects interacting asynchronously, for the sake of efficiency and scalability. Further, it copes with advanced issues such as mobility, groups, and components.

Pi-Calculus, Join-Calculus and more...

Check out the sample chapter to get a feeling of the writing style.

Squeak tutorial

A nice Squeak tutorial.

it has been awhile since we mentioned Squeak, but there were days when it was mentioned quite regularly...

Generics are a mistake?

Generics Considered Harmful

Ken Arnold, "programmer and author who helped create Jini, JavaSpaces, Curses, and Rogue", writes that the usefulness of generics is outweighed by their complexity. Ken is talking about Java 5, but such critiques are well-known for C++, and C# is not immune either. Ken describes the Java case as follows:

So, I don't know how to ease into this gently. So I'll just spit it out.

Generics are a mistake.

This is not a problem based on technical disagreements. It's a fundamental language design problem.

Any feature added to any system has to pass a basic test: If it adds complexity, is the benefit worth the cost? The more obscure or minor the benefit, the less complexity its worth. Sometimes this is referred to with the name "complexity budget". A design should have a complexity budget to keep its overall complexity under control.


Which brings up the problem that I always cite for C++: I call it the "Nth order exception to the exception rule." It sounds like this: "You can do x, except in case y, unless y does z, in which case you can if ..."

Humans can't track this stuff. They are always losing which exception to what other exception applies (or doesn't) in any given case.


Without [an explicit complexity] budget, it feels like the JSR process ran far ahead, without a step back to ask “Is this feature really necessary”. It seemed to just be understood that it was necessary.

It was understood wrong.

The article contains a few simple supporting examples, including the interesting definition of Java 5's Enum type as:

Enum<T extends Enum<T>>

...which "we're assured by the type theorists ... we should simply not think about too much, for which we are grateful."

If we accept the article's premise, here's a question with an LtU spin: do the more elegant, tractable polymorphic inferencing type systems, as found in functional languages, improve on this situation enough to be a viable alternative that could address these complexity problems? In other words, are these problems a selling point for better type systems, or another barrier to adoption?

[Thanks to Perry Metzger for the pointer.]

XML feed