Lambda the Ultimate

I don't really buy this. Although all the major language features (tuples/records, choices/variants and functions) are instances of second-class things promoted to first class, sometimes the value of such promotions is questionable, or even makes the language worse.

For an example of the former consider continuations. Making continuations first class is useful but it also forces a language to adopt call-by-value or call-by-name semantics, so it's not a 100% win, and it's not a conservative extension. Linear (one-shot) continuations may be a different matter; I don't know enough about them.

For an example of the latter consider first-class types (meta-classes) as in Java. Part of the point of these is that they support introspection, which is ostensibly useful. But they also break all the encapsulation guarantees which the rest of the language purports to provide.

I think one mark of clean language design is an elegant (usually this means nicely factored/orthogonal) and strong meta-theory, that is, simple and powerful reasoning principles for programs. Sometimes making things first class can improve the meta-theory, but sometimes it can make it weaker and more complicated.

(I haven't read the article yet, so I'm only taking exception to that one sentence.)

Some thoughts as I shoot from the hip (as usual)...

• Encapsulation is not all it's cracked up to be.
• Java's Class objects are hardly "first class" (even in the loose definition of that term).

one mark of clean language design is an elegant (usually this means nicely factored/orthogonal) and strong meta-theory, that is, simple and powerful reasoning principles for programs.

I have nothing against strong theory, I am all for it. However, theory typically follows practice, whether it is continuations, "objects" (note the quotes), reflection, or generally "side effects".

Specifically Smalltalk and CLOS have demostrated a successful practice of "first class" (again, note the quotes) messages. Maybe a theory should or could put this into a clean, elegant context as existing theories have been doing for other effects listed above. Meanwhile, the practice is still useful, perhaps "elegant", if ad hoc.

I'm not going to say therefore that "first class" anything implies a "clean" design. Yet a combination of simple ingredients, one of them being "first classness" for most things, appears to have led to *utility* in several similar ad hoc languages, e.g. Smalltalk, Lisp, Python, Ruby.

This is not necessarily true. Java introspection does not allow you to access or invoke non-public members.

It is also very clear when code is using instrospection since it involves calls to methods of classes in the java.lang.reflect package. It doesn't change the semantics of the language "syntax" level (iykwim).

On the other hand, the Class-loader capabilities, coupled with a bytecode manipulation library, lets you subvert the semantics at the lowest level...

import java.lang.reflect.Field;
public class Foo {
    private String bar;
    public Foo(String bar) {
        this.bar = bar;
    }
    public String toString() {
        return this.bar;
    }
    public static void main(String[] args) throws Exception {
        Foo foo = new Foo("Hello World!");
        System.out.println(foo);
        Field barField = foo.getClass().getDeclaredField("bar");
        barField.setAccessible(true);
        barField.set(foo, "Goodbye World!");
        System.out.println(foo);
    }
}

Even supposing it is, it would be nuts to ignore the nifty things you can do with encapsulation-breaking introspection features.

An obvious example is writing a debugger. A common "encapsulation respecting" way is to write it as hairy under-the-hood runtime system extension. A more fun way is to expose some encapsulation-breaking primitives for inspecting the stack and pulling apart objects, then just writing the debugger as a regular program. Profilers are another example.

Lisp hackers write some really nice development tools using tricks like inspecting the stack, iterating through the whole heap, dismantling arbitrary objects, temporarily replacing function definitions, and so on. To ignore all of this on software-engineering principle would be to miss the party!

Also what is Second Class? supported only through libraries?

Luke: Even supposing it is, it would be nuts to ignore the nifty things you can do with encapsulation-breaking introspection features.

I've written lots of Python code that loads functions dynamically and stuffs them into objects as singleton methods, or builds classes at runtime or walks the stack looking for interesting information, and it's true that I do miss that flexibility when I'm working in statically typed languages. Some folks say the answer is an optional type system, where you can supply types and have the compiler check them, or omit them and then the runtime system will have to do the checking. But I don't like this idea much. As LTU readers probably know, I like static type checking a lot, and I'm not convinced making it optional helps anybody.

However, I sometimes feel that systems that emphasize static typing are more static than they need to be. Basically, I'd like to keep the safety of static typing, but without giving up dynamic program behavior. I'd like to be able to load plugins, say, or update running code, in my Haskell program. I don't need ultimate dynamicity in every aspect of my program, but I would like to be able to make graceful transitions from one known (statically checked) program state to another.

So for example, I run the compiler and it checks my types, generates an executable. I start the program, it runs for a while, and at some point it dynamically loads or reloads some code. The type checker automatically runs again. If it doesn't like the new code, it rolls the program back to its old state. If the new code is acceptable, then the modified program continues on its merry way, and I get to know that the modified program has every bit as much type safety as the original. Then I could have my eval, and eat it too.

I suppose someone will tell me that there's a version of the Haskell web server that supports plugins, or that the Ocaml or SML toplevel does things like this, but I don't think they make all the safety guarantees I'd like when loading new code, and it doesn't seem like it's going "with the grain" of the language to use these things for production systems anyway. Maybe I'm wrong.

Maybe something like MetaOcaml could help with this problem someday... Or there may already be a solution somewhere I'm just not aware of. Anyone?

That's because you're running under a SecurityManager that allows you that access. If you run that same program under a tighter SecurityManager (say the one installed by your Applet class loader), you'll get an exception.

This means that, yes, you can break encapsulation, but only when it's safe - i.e. explicltly allowed.

For reference, from a previous LtU post on Sina:

The behaviour of an object [in Sina] can be modified and enhanced through the manipulation of incoming and outgoing of messages.

Bryn: Or there may already be a solution somewhere I'm just not aware of. Anyone?

You'll find what you need in Alice ML with its limited dynamic typing extensions to ML.

Toby: This means that, yes, you can break encapsulation, but only when it's safe - i.e. explicltly allowed.

My definition of `encapsulation' is more rigorous, and no system of introspection types can respect it. (Actually, instanceof doesn't respect it either, but the problem is not as severe.)

Here is the problem. Suppose I have types A and B, with B <: A. In Java they would be interfaces. The meaning of subtyping is merely that the language permits a B anywhere an A is required, but the way subtyping is used in practice requires roughly that B behaves like A (the LSP, Liskov Subsititution Principle) in such a way that we can regard B as an implementation of A. The point of this, of course, is that I can switch out different implementations of A by supplying different objects which belong to a subtype of it; that is, the point of this is encapsulation.

In order for this to work, it has to be the case that an A-context (any code which uses an A) cannot depend on the particular subtype of A which is supplied it, because then if I replaced the implementation with another, it would break. (Well, not quite.) But this is precisely what introspection allows. Notice (nickmain) that even being able to determine the existence even of a public method is problematic.

(instanceof is not as bad because you can only really use it when you can enumerate the subtypes of a type, that is, when there is a closed-world assumption in effect. In this case, you can write code that handles all the cases. But, as everyone knows, instaceof sucks and should be avoided regardless.)

Now here is, I think, the real reason that first-class types are dangerous: the `best' notion of equivalence for values is (beta-eta-)equality (in contrast to syntactic equality), while the `bestt' notion of equivalence for types is one step weaker, namely isomorphism. The reason is that any type B isomorphic to a type A can serve just as well in any A-context, provided you insert a coercion (which in OO languages is effectively determined dynamically by dispatch), and vice versa. This is analagous to the fact, at the value level, it does not affect the behavior of a program whether I write 2+2 or 4, since they are equal. (Note, BTW, that LISP-style macros can distinguish these two, which is one reason I object to them. :)

Well, maybe it's confusing for you to hear about `equality' and `isomorphy' if you are not used to equational languages. The asymmetric analogues to this in non-equational languges (such as all OO ones I know of) are `convertibility' (the reduction relation) and `behavioral subtyping'. For values, `x' behaves like `y' if `x' converts (reduces) to `y'. Similarly, a type B behaves like A if B is a behavioral subtype of A, which I'll write B << A.

So, suppose now that I have an operator type, which, given a type A, produces a value type(A) that represents the type A as a value. In order to respect encapsulation in the presence of first-class, then, one needs to ensure at least that, for all A, B:

B << A     implies     type(B) => type(A)    (*)

where << means `is a behavioral subtype of' and => means `reduces to'.

Of course, Java doesn't respect this; indeed, it can't respect this since it doesn't even respect the LSP, since it can't decide the behavioral subtyping property! And if Java did implement this rule then Luke's example of a (conventional) debugger would not be implementable using introspection, since you wouldn't be able to access the methods or fields which are hidden by upcasting, that is, the ones which are only accessible if you know the `dynamic' type of an object, that is, the ones belonging to the implementation..

Now, you might argue, `well, if we use subtyping as a weak replacement for behavioral subtyping, putting the burden on the users to respect the LSP, we might as well add the above as a reduction rule to Java.' But in my opinion this is a bridge too far. It would be OK if people actually wrote programs in such a way that they didn't depend on subtyping modeling behavioral subtyping, but they don't, and I'm sure OO people would find that unacceptable.

You might also argue, `well, if we use subtyping as a weak replacement for behavioral subtyping, putting the burden on the users to respect the LSP, we might as well put the burden on the users to respect (*) as well.' But writing programs which respect the LSP without the compiler double-checking it for you is hard enough; writing introspective programs which respect the LSP and (*) is even harder...

Incidentally, a calculus I'm developing does enforce/respect behavioral subtyping, for, admittedly, a very weak notion of `behavior'; furthermore, it does not identify inheritance with subtyping, or force types to have a single supertype. Adding first-class types there might be interesting, and I spent this morning thinking about how to do it, and what uses there might be for it; mainly I'm thinking of extensional polymorphism like in G'Caml, lightweight generics and dependent sums (dynamics). I can imagine a natural categorical semantics for it... so perhaps first-class types are interesting after all.

If you have to throw out such a basic and uncontroversial principle as encapsulation to advocate such an experimental feature as first-class types, I would say your argument is very suspect.

I also wonder if you realize what a double-edged blade it is. Anyone who is willing to promote introspection because they feel encapsulation is not-so-important must also be prepared to accept criticism of nearly every other language feature, such as higher-order functions and, perhaps most notably in your case, OOP, since the worth of these things is largely that they support encapsulation.

In brief, I think you're throwing the baby out with the bathwater.

Java's Class objects are hardly "first class" (even in the loose definition of that term).

My definition of `first-class' (which I assumed was shared by everyone here) is `can be passed to and/or returned from a procedure'. Surely that admits Class objects.

theory typically follows practice

More like `theory that follows practice typically follows practice'. There is a huge world of theory out there which, I suspect, you are unaware of.

Specifically Smalltalk and CLOS have demostrated a successful practice of "first class" (again, note the quotes) messages. Maybe a theory should or could put this into a clean, elegant context as existing theories have been doing for other effects listed above.

Bit of a tangent...

I can identify two schools of theoretical PLT, which I'll call the `archeological' and `engineering' schools.

The archeologists are interested in picking through existing and older languages, and finding nice ways to organize and explain what is found there. This type of research typically involves finding a semantics for a language, or figuring out if a type system is sound. Occasionally this produces immediately useful results (like fixing the bugs in Java's class-loading system, or the problems with variance in Eiffel's type system), but in my view the main worth of language archeology is that it identifies problems and issues that can only be adequately addressed in future, yet-to-be-designed languages.

The `engineering' school comprises people who try to use theory (which may have originated from archeologists) to design new features and languages. This is the crowd that invented things like algebraic datatypes, type classes, implicit parameters, monad syntax and so on.

I am in the subset of this crowd who believes good languages don't arise by accident, but rather are designed to be that way. This is an idea which maybe goes back to Dijkstra and the structured programming school. Dijkstra believed that good programs are structured, and that it's impracticable to try to extract latent structure, that, instead, it ought to be explicit. Thus they introduced structured programming constructs like while to replace goto's, making the structure explicit rather than implicit. (To my mind, static typing is just an extension of this idea, c.f., `latent' typing. This is also why I'm not very interested in using external theorem provers to improve program reliability.)

In a way, I have to admit I think of archeology as pessimistic and engineering as optimistic, because one rarely gets an archeological result like, "hey, you know what, this feature was actually really great!' :) An exception might be Algol 60, which people like Reynolds (in `The Essence of Algol') and Hoare laud for its elegance. Hoare said, Algol 60 is

a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors.

By which he means, I think, most notably Algol 68 and the C family.

Yet a combination of simple ingredients, one of them being "first classness" for most things, appears to have led to *utility* in several similar ad hoc languages, e.g. Smalltalk, Lisp, Python, Ruby.

I would think you would know me better by now than to try to convince me of the worth of feature by pointing to this family of languages. :)

Of course it is very easy in untyped programming languages to make everything in sight first-class, because untypedness (= single-typedness) smooshes everything together into one big ball of mud, which the poor programmer is left to pick apart at run-time. The problem is, what is the best way to pick it apart?

And that is where untyped languages always punt. They might get the introduction rules right, but never the elimination rules. Let me suggest that that's why so many arguably useful ideas and constructs like referential transparency, pattern-matching, folds, monads, even OOP originate in typed languages.

It reminds me of the XML community. They think that by tagging everything in sight now, they are `adding value' that sometime in the future they'll be able to exploit. But that is always infinitely postponed; the only tags that actually get exploited are the ones that are actually assigned an unambiguous semantics now, that is, the ones that have elimination rules.

I think the untyped community is caught in a cycle of infinite regress. Your remark on encapsulation exemplifies this. `Encapsulation: we want it, we don't want it, we want it, we don't want it, ...'

nickmain: This is not necessarily true. Java introspection does not allow you to access or invoke non-public members.

This is irrelevant. See my post above.

Luke: Even supposing it [encapsulation is all it's cracked up to be], it would be nuts to ignore the nifty things you can do with encapsulation-breaking introspection features.

An obvious example is writing a debugger... Profilers are another example.

It is telling that you use these two particular examples, because they are prototypical examples of metaprograms, and have a very narrow domain of application. The vast majority of applications benefit from encapsulation and, in your words, it would be nuts to ignore the nifty things you can do with it! (Even a debugger and profiler only break encapsulation in a few select places.)

But, you're right that there is a time and a place for breaking encapsulations and, indeed, every method of encapsulation needs such a time and place, because for every interface/type/module/whatever you need to supply an implementation somehow.

What I object to, rather, is that the language provides no method of enforcing encapsulation when you want it, that is, Java introspection is half-baked. It is possible, I think, to support both up-to-equality and up-to-iso/coercion typing. The first would allow Java-like introspection and break encapsulation; the second would use the law I suggested above and respect encapsulation.

(What I object to even more strenuously is that language designers who adopt features like introspection do not make clear that those features break encapsulation. And what is the upshot? Things like Joel Spolsky's leaky abstractions article!)

BTW, I made an error in my first post, when I said that introspection breaks `all the encapsulation guarantees which the rest of the language purports to provide.' Here I fell into the trap of thinking that Java subtyping is actually behavioral, so that Java does actually manage to provide encapsulation via subtyping. But this is false, so actually introspection can't break what isn't there in the first place. Consequently, it's not the case that supporting introspection in Java breaks any guarantees that people who don't use it might otherwise have.

There seems to be an important distinction between "supporting" and "enforcing" encapsulation. I'm sure I've seen this discussed before, but I don't recall where. Like most people in this enlightened age I use a lot of encapsulation. However, I don't feel threatened by the possibility of myself and the friends I program with being able to deliberately break through this encapsulation if we want to.

Personally I think that encapsulation and abstraction are great things. I want my programming language to make them easy to respect, but why is it important to make it difficult or impossible to bypass deliberately?

No doubt.

It is telling that you use these two particular examples [debuggers and profilers], because they are prototypical examples of metaprograms, and have a very narrow domain of application.

Each one of these examples may be considered a narrow domain of application. But you add them up and result is fairly broad, well beyond the typical development tools domain.

The `engineering' school comprises people who try to use theory (which may have originated from archeologists) to design new features and languages. This is the crowd that invented things like algebraic datatypes, type classes, implicit parameters, monad syntax and so on.

I am glad this school of thought exists. I believe this approach is being motivated by the desire to ground practices from more ad hoc systems in more formal notations, without losing the expressiveness of the ad hoc notations. That is noble, and when I find the results as satisfying as, say, Smalltalk, I intend to use them, because then they will certainly be better.

For reasons I'm sure you well know: an encapsulated/abstract data structure has a different semantics from a plain one. If T implements S, then by definition T may satisfy properties in addition to the ones S satisfies. A client of T is allowed to depend on those additional properties, but a client of S is not. So roughly the set of clients of S is a subset of the clients of T.

Let me anticipate your arguments. This is not a question of flexibility, because `you can write more programs using T than S'. And it's not a question of trying to force people using your code to program defensively or reliably or whatever. And it's not a question of imposing your own opinions or values on your user community.

It's just a question of semantics. When, in your documentation or interface, say, you write `S' instead of `T' you are exactly saying to all the people who are going to use your code that `you can rely on this certain set of properties, but no more; if you rely on more, your program may not function the way you expect.' Indeed, T may not even `exist' at that point, or if it does perhaps you are planning to change its behavior in the future, or you may not have made a decision yet as to how to implement S.

Suppose you tell your friend "Hey, I'll see you next week," and then next Tuesday you meet him and he comes up to you and says, "Hey man, you promised to see me on Monday!" Of course you would reply, "No, I didn't; I said I'd see you this week, and I have. Are you deaf or just stupid?" And if he then says, "I know you said `next week' but when you say `next week' you always mean `Monday'," naturally you would say, "Motherfucker, if I had meant Monday I would have said `Monday', not `next week'." And if he said, "Well, why didn't you say Tuesday?", you would say, "Why the hell do I have to explain myself to you? Maybe I hadn't decided yet, or I thought I might have other commitments on Tuesday but ended up being free, or I like to lead a happy-go-lucky existence and see you at my whim whenever the hell I goddamn please (within this week, at least)."

and

Patrick: Each one of these examples may be considered a narrow domain of application. But you add them up and result is fairly broad, well beyond the typical development tools domain.

I'm sure you can give other examples, and I suspect that they all or most are metaprograms of some sort. Let me explain by analogy why I don't consider them so important.

I'm sure you have used the C preprocessor and other preprocessing programs, and macro systems. And I'm sure you're aware of the problems with them, for example, the difficulty of tracing errors back to their source, even when you have things like #line to help, or the difficulty that occurs when you try to use multiple preprocessors (or macros), which don't know about each other, together.

One role for which the C preprocessor was indispensible was for duplicating function and class definitions when they differed only in the types involved. In C++, the template mechanism helps to obviate that use. In ML, polymorphism plays a similar role. Besides being neat-o keen, these features improve on the preprocessor in that the compiler can produce good error messages. (Well, at least an ML compiler can. :)

The reason this is possible when they are language features, but not via a preprocessor, is that really preprocessed programs form a language of their own, and that a preprocessor needs to be a compiler in itself. That is, it needs to know more than simply the lexical syntax of C, it needs to know about the C grammar, and even the C semantics, to do it's job in a transparent fashion. In other words, it's kind of a hack. LISP macros are better because they know not only about LISP lexical syntax, but also its grammar; but they don't know about LISP semantics, so they are still troublesome. Scheme hygienic macros are even better because they know the lexical syntax, the grammar and some of the semantics, namely variable binding. But still they can be troublesome.

To solve all the problems, you really need to modify the compiler itself, and not just preprocess the input. Obviously, that's a lot of work. You can, of course, ignore the problems; but then the user has to know about how the preprocessor works in order to make sense of the problems he encounters. The whole point of a preprocessor is to hide the intermediate stage, but that is what the user has to look at to understand any problems.

The crucial thing about ML-style polymorphism, though, is not that the compiler knows about it. The crucial thing is that it can be specified in a way that does not depend on lexical syntax or grammar, so the compiler doesn't need to expose any of its internals; it can translate any errors it encounters back into a language understandable by the user. Also, you can understand that style of polymorphism in any language, even though it may have a completely different syntax from ML (like, say, Haskell). So ML-style polymorphism solves one of the same problems as the C preprocessor, but does it in a syntax-independent fashion. (Of course, it has to have some syntax for the user to be able to use it, but the point is that the particular syntax doesn't matter.)

Now replace `syntax' with `implementation' and `semantics' with `specification' (or `interface' or`contract').

What I want to suggest is that, just as a language feature like polymorphism can subsume at least one role played by a preprocessor, so also can the roles of metaprograms like debuggers and profilers be played in some respects by programs (not metaprograms) or modules or whatever in a sufficiently expressive language. Now, of course, without introspection there would be no way to get at the name, say, of a method or variable or whatever. But the purpose of a debugger, ultimately, is not to print out the names of variables in the source; it's to help debug the source, right? Printing names is only a means to an end.

Well, I cannot say what such a program would look like (though, look at Hood), except that it would be a sort of abstract debugger. And I'm not saying that every useful metaprogram can be completely subsumed by a program. But I am saying that, just as ML polymorphism is more useful than doing the same thing with a preprocessor, it is usually better to write programs than metaprograms, when possible, and that the better and more powerful a language is, the less the need for metaprogramming.

Smalltalk "messages" are first class objects, however, like stack frames, it's more efficient to not have most messages as objects as this slows down the virtual machine's message processing performance dramatically. To compensate for this vm implmentation choice Smalltalk enables you to access messages as first class objects when needed. You can also create messages as first class objects just like you would create any other object.

In Smalltalk you'll find messages as objects if you halt a process and debug it. This is how the debugger works with messages. In addition it's easy to create message object instances and then send them.

Most of the Meta data in Smalltalk are first class objects: classes, block contexts (closures), methods, messages, etc... All of the meta data that are first class objects are used and accessed via the same message sending syntax that you access any objects with. This important aspect of the "elegant design" impact of "first class objects" enables "meta data" manipulation just the same as any other object in the system. This is one of the goals in Smalltalk, using the simple message sending syntax for all meta data. In this way all meta data in Smalltalk is expressed in same syntax as regular non-meta data.

Now that processors have billions of cycles available it might be wise to revisit this vm design choice to find if there are other capabilities that would be more valuable than simple raw performance of message sends. As we are learning execution time isn't the only performance measure that matters. Human effort, comprehension and development time and costs are becoming the most relevant performance measures that developers face in the real world.

What is lacking in the current elegant Smalltalk syntax is a concise manner to express on the fly "Message Meta Data" in message expressions themselves rather than having to step out of "context" and use the combersome and verbose approach of constructing messages from objects. In addition it's advantagous to have the ability to do this while retaining the use of Smalltalk message sending syntax for this "message meta data".

I've achieved this "inline message meta enhancement" in defining Zoku, a variant of the Smalltalk language that also owes much to LISP, Self, and a host of other languages. As work progresses more details will be released.

The key point is that access to the underlying message sending system and to any message object in the system can be achieved using either existing Smalltalk syntax or the simple Zoku extensions. This creates a complete language that enables both objects and messages to be expressed fully on a first class and equal basis (inline in the grammar) while using and keeping the beauty and elegance of the original Smalltalk grammar.

We feel that this is a step into the future even though we've not yet fully explored all of the implications that this new "meta message" syntax makes possible. A door to new possibilites is opened. The key now is unlocking and realizing the potential.

Please see upcoming articles on dev.Smalltalk.org for more information on "Message, Object and Meta Oriented Programming and Zoku".

I am not sure where the line is with Smalltalk. What is programming vs. metaprogramming in Smalltalk? I don't know. It's Smalltalk all the way down for Smalltalk-80 based systems, until you get to a fairly thin layer of magic that varies by implementation.

Regardless, I think the quote above illustrates my point that the useful theory work I see today in PL design seems to be significantly motivated by the more ad hoc practices of so called dynamic languages. Modern functional languages are becoming more expressive, approaching the better less formal languages, yet they are bringing the formality with them, which is a good thing. But as stated above, they're not all the way there yet.

Kind of like Objective-C wraps C into a Smalltalk message framework, I'd like to be able to wrap ML typed functions into objects. (O'Caml probably does this already).

If you are used to special and distinct "meta" grammar and syntax in the languages you are using I can see why you'd be confused where the line is. The line is very clear in Smalltalk.

I address Patrick's question in depth here.

As Patrick mentions, that's only necessarily true for Smalltalk-80 derivations, and not for other languages (like #Smalltalk) that follow the ANSI Smalltalk standard but have very different implementations. But to me, Smalltalk-80 is the point; the language as a specification is wholly uninteresting.

i've been wondering exactly what Meta Programming means recently - there seem to be two different approaches (at least).

one is typically macro based - you process source "before compilation". the other is typically connected with late binding in bootstrapped languages - you rebind the functions associated with evaluation and so modify the "run-time" behaviour.

in some sense they're equivalent - it's just a case of where you do the indirection (isn't it always? ;o) - but the implementation is quite different.

does that make sense? am i stating the obvious? :o)

(i'm working on a tiny language that has almost nothing except the ability to rewrite lists. but since it can be bootstrapped and names rebound it's surprisingly flexible. i can add crude support for time-slice multithreading in 60 lines of code!)

[edit - russell's paradox was a bad choice because it's going to send people off on set theory, which is a bit of a red herring. "this sentence is false" is a better example.]

What a double standard!

As I've shown before, and have repeatedly pointed out, by defining a universal type, you can do anything in a statically typed language that you can do in an untyped language, including run-time reflection, dynamic loading, introspection, OO-style objects and dispatch, etc.

What you cannot do, except in certain experimental languages like Meta(ML/Ocaml), is get the same static guarantees for those features that you get for the remainder of the language. But this is no worse than in an untyped language, since there one gets no static guarantees at all!

When we say, for example, that "Haskell does not support eval but Scheme does," we are comparing apples and oranges. What we're really saying is, "Both Haskell and Scheme support untyped eval but neither support typed eval." Clearly, when you look at it this way, Haskell is much closer to supporting typed eval than Scheme, since at least it supports static typing for the part of the language which does not involve eval, whereas Scheme does not. (And languages like LISP only support monomorphic type annotations at best.)

Now, of course, mixing typed and untyped code in Haskell is not as easy as we would like it to be. But it is possible (as I also showed). But mixing typed and untyped code in Scheme is impossible, since Scheme has no notion of static typing in the first place!

People talk about delaying things until run-time as if it were an advantage. But it is clearly always easier to do things at run-time than to do the same things statically. It actually lowers the bar. And anything done dynamically in an untyped functional language can be done dynamically in a typed functional language, because of Turing-completeness.

So statically typed functional languages long ago transcended their untyped functional counterparts. It is untyped languages that are playing the game of catchup!

What a punt!

8^)

In your example you defined the universal type like type t = String of string | Int of int | Bool of bool. Is there a way to get rid of the tags, so that one could write just "foo" and not String "foo"?

Probably you would want to quote them somehow to reuse the syntax for typed literals, so, '"foo" means String "foo" and '3 means Int 3. If you are willing to write univ rather than ', you could define a type class:

class Universal t where univ :: t -> Univ
instance Universal String where univ = String
instance Universal Int where univ = Int
instance Universal (Univ -> Univ) where univ = Fun
instance Universal Univ where univ = Quote

If you could please exand on your definition of the line and why you don't think it's clear?

While it seems clear that we see Smalltalk differently, I'm not quite sure what you mean when you say that. So, how do you see Smalltalk?

Yes an implementation of Smalltalk could model all aspects of the virtual machine in the language itself and enable you access to all of the internal components: compilation, method tables, stack frames, garbage collection, object headers, method dispatch, primitives and any other parts of interest.

I would agree that Meta Programming in Smalltalk is just like regular programming. That is a direct result of the meta data being represented as first class objects that can be manipulated like any other objects. Yes, not all the meta data from the virtual machine is accessible.

Slate Smalltalk is making an attempt to eliminate the "virtual machine" altogether. If successful will this mean the elimination of the "hard barrier" that you speak of? Not likely as ALL software that uses current microprocessors has the problem that you speak of relating to "the metalevel for machine language": the metadata of the machine is ultimately inaccessible. Even if you are using a Field Gate Array Programable chip that you can reprogram at will there will always be some "meta level" that you can't access as a result of the processor hardware exising in reality to get the work done.

In addition, in a vm-less system there will be parts that are very sensitive to change, such as the message dispatch code, and any changes could instantly break the system. Well, this is also true of Smalltalk and some other truely dynamic systems like LISP and Forth. The point is that even with access to all parts of a system you realistically may not be able to really change it that much or at all without seriously affecting the system's function or performance. But I suppose at least you'd have a chance. So it's a balancing act to determine how far down this road to travel.

The "meta level" for assembly language "bottoms out" with the machine as you say. An important aspect of meta programming in Assembly language should allow for dynamic (and easy) access to writing and manipulating assembly language programs from within assembly language. Most assembly language systems are not designed this way, yet you could do so if you wished.

The question I have is of what relevance is this bottoming out in your view? Obvously things bottom out and there will be a "layer of magic" to make things work. If a system like Slate Smaltlalk succeeds and brings all of this "magic layer" into the language itself or it's object library have we really gained anything? I think so.

Why is "the language as a specification wholly uninteresting" to you? Where is your interest?

I consider the "syntax" of Smalltalk as a limiting factor that shapes, to a high degree, what is possible to express in the system and certainly how it's expressed. Many different "less limited" implementations of virtual machines (or virtual machineless) systems could be built that implement Smalltalk-80 or the ANSI Smalltalk standard.

I've found the language specification of Smalltalk-80 of interest because with some minor adjustments to the grammar the expressiveness of a Smalltalk like language can be increased significantly. In addition a refactoring of the object library can see substantial improvements as well, including in access to the majority of the meta data in the virtual machine.

The Smalltalk syntax is of great interest since it pushes much of the "magic layer" from the language compiler, where it most certainly is hidden in the vast majority of langauges, to the run time environment and library of objects that are accessible to the running programs themselves. Too few languages do this.

One of my interests are programs that write programs. This is an area that needs major improvements, and not just in Smalltalk, but in any language system that writes programs.

I'm not just for First Class Messages, access to the Message Sending System (message dispatcher), but I'm also for Fully First Class Methods and Blocks at the expression level. I'm for Meta Programming. I'm for better implmentations, vm or vm-less, of the language and it's variants. I'm for many versions of Smalltalk from many vendors and open source projects to support a growing eco-system for more powerful and literate systems.

People talk about delaying things until run-time as if it were an advantage. But it is clearly always easier to do things at run-time than to do the same things statically. It actually lowers the bar.

It's an advantage for all the capabilites that are gained that can't be decided statically. It's not always easier to do things at run-time. Self goes to great lengths to figure out the types of parameters at run-time and generate optimized methods based on that potentially changing information. Since there are many things that can be done at run-time that can't be done statically the bar is raised in dynamic systems that do their work at run-time. In addition since performance is usually a concern at run-time dynamic languages have a high standard to reach and thus a higher bar to cross.

anything done dynamically in an untyped functional language can be done dynamically in a typed functional language, because of Turing-completeness.

I suppose, but Turing-completeness isn't all it's cracked up to be. Just look at the twists and turns involved in translating applications from one language to the next. More often than not the result is, well, cryptic ick.

It is untyped languages that are playing the game of catchup!

You are asserting that "typed" languages are superior to "untyped" langauges. Could it be that there is simply no valid need for "typed variables" in a language? Could it be that languages like LISP, Smalltalk, Self, Forth, Postscript, and others get along fine without "types"? Yes types give you some benefits but they also cost a tremendous amount in terms of extra development time and increased and bulkier code sizes. Essentially the gains from types just don't provide any worthwhile all compelling advantages. In fact they often seriously hinder development.

Typed code tends to be less generic, thus less reusable and as a result more code is required to express the same ideas. As we all know, more code more bug potential. A primary argument for types is that they help stop bugs. Ironically it seems that it's quite possible that "typed" code begets more code which "requires" types to keep it safe which begets more code... an icky upward and self reinforcing spiral that eventually contrains the programs and programmers expresiveness to the breaking point. The end result of typed programs tend to be highly brittle systems.

It's not that programming typeless systems are perfect, anyone can make a mess anywhere, but if you can get the results without using types why use them at all? For the occasion that you need to check a type you can do so at run-time and gain the same "type safety". More often than not static type safety doesn't provide you anything other than an unnecessary and expensive illusion.

[ducks behind wall]

Typed code is more specific, especially when using large object libraries that use "non-universal" types. Since typed code is more specific you need to write more of it to cover all the possible types, thus the program bloats unnecessarily. It's unnecessary since an equilivant dynamically typed program would be smaller. Not illusion, fact.

Let's see why with a brief case study that supports my assertion that "typed" languages require more code to be written.

For many years I programmed in Objective-C on the NeXT OpenStep systems (now MacOSX). Objective-C is a typed language that also borrows a subset of Smalltalk style message passing. Naturally as someone with lot's of Smalltalk experience and a preference for dynamic typing I would use the universal type "id" (Object) in all of my code. Even though I did this I was still forced to use C types for all of the non-objects. So in this mixed language I have some choice about types but also some requirements that I must follow. Ok, no sweat I can survive.

The commercial programs that I wrote tended to be larger in Objective-C than in Smalltalk. This was a result of always having to "type more" (no pun intended) characters to define the types of all the variables in all the methods and function prototypes. In addition the methods tended to be upwards of twice as long as equilivant Smalltalk methods would have been with a Smalltalk version of the (otherwise) excellent OpenStep Application and Foundation Kits. This is a result of the way that Objective-C handles types and this impacts the design of software.

I spent a lot of my debugging time chasing down silly typo's that prevented the program from compiling or running. About half of these were simple errors related to "variable types" of one sort or the other. If I'd been using Smalltalk I would have saved much of that time and likely delivered the system faster. That would have given me a larger profit on a number of the jobs and cost the client less on some of them as well.

There are real practical financial consequences to using a typed language. I'll take the untyped language that gives me the financial and competitive edge.

Seriously...

I have a question for those of you who like types, when you have classes why do you need types?

Anyway the point of this thead is having messages be first class objects by way of having rich meta data for messages. I support these kinds of improvements in all languages that can make it happen.

[on edit: in 1 types where a typo, corrected to classes]

I am presuming good will though.

I have a question for those of you who like types, when you have classes why do you need types?

When you have apples why do you need oranges?

As Daniel already mentioned, classes are a bundled offer. Being of mostly Java background, I usually do not consider data layout seriously, so my definition of (badly overloaded) classes is: unit of code reuse, classification, and instantiation (meaning identity is coupled to instances of classes). I think these roles should be played by mixins, interfaces, and classes correspondingly (if one does not want to change language more drastically, at least). In other languages mixins may be called modules or components, interfaces may be called types or specifications, and classes, well, there may be no classes :-)

In fact, it is possible to find languages located at any point of the space with these three dimensions. By bundling all the three aspects together one kills a lot of diversity and freedom in the design of a PL.

But obviously if what you are asking is why classes shouldn't be used to imitate types, the reason is static type safey. If you don't want that, this reason won't satisfy you I guess...

When you have objects (or entities or whatever you want to call them) that carry "type information" via their "prototype" or "classification" along with them why do you need "typing information" to constrain "variables" in object instances, method parameters and method variables?

Why is it so important to "type" variables? Why is it so important to constrain a variable to be an "integer" or an "array" when the object contained in that variable knows it's own "type" or "class"?

What code properties are made explicit with types? How can "types" be "the best way" to make code properties explicit? How are types "semantically" simpler?

If you don't use "objects" that carry their own type information then how do you do "object oriented programming"?

There seem to be two sides of the coin when it comes to variables. Having the variables carry the "type" information and having the thing that the variables point to carry the "type/class/prototype" information. Both kinds of systems exists including systems that do both. Many successful applications and systems are in major operation that use these various approaches. There are differences between these approaches that affect not only the source code that is written but also the thinking styles of the people involved. Or perhaps it's the thinking styles of people that lead them to choose the particular language format. In any case there are major camps and much has been written slinging which is better back and forth. The point is it comes down to some basic choices and human values about what is important. It is a worthwhile subject to pursue and learn since it dramatically affects the design of not only computer languages but also operating systems, applications, software quality, development time and costs, the scope of applications, and ultimately the economics of the majority of those involved.

The "typed" or "untyped" variable discussion is relevant to the "case for first class messages" since they are both questions about "meta data" and how it's handled in the language and library of objects that come with the system.

The arguments for "typed variables".

1) Types allow "static" compile time "code" performance optimizations.

2) Types allow "static" compile time "code quality" by ensuring that "operations" only are done to "variables" of the "correct type".

3) Types are "semantically simpler" because they work with only one concept.

The arguments for "untyped variables".

1) Since objects carry their own "class" or "prototype" information with them it's "redundant" and "unnecessary" to "type variables".

2) When variables are "typed" the flexibility of methods is reduced and constrained. This is the purpose of typed variables. As a result methods become "more specific" by limiting the "types" of objects that can be "put into" a variable (instance variable, method parameter variable or temporary method variable). By becoming more specific with respect to what can be put into variables the methods can't be used in as many "contexts" with as many kinds of "objects". (If you are only using one "universal type" through out an entire then you are in part not really using typed variables but you might not have the "dynamic binding" capabilities depending on the language).

If a variable is typed it can only take objects of that kind. For example if we type a counter variable as an integer as follows we can only store integers in it.
aCounter Integer;
Now this method can only have integers in this variable. What if a case comes up that needs to use more generic "numbers" such as floats or fractions (which are supported in Smalltalk). The method is limited to "integers" and won't work thus another method would need to be created thus increasing (doubling) the code size. Yes, you could type the variable as a "Number" and not have to "duplicate" it, but now you have a variable that can't handle other types of "Magnitudes" (or other types of ordered sequences).

When variables are typed in a large group of classes the method parameters (function prototypes) are limited and often there are multiple function prototypes created to allow for more each type. Thus you end up with more methods.

3) It's faster to write code that is "typeless". It leads to, in many if not the majority of cases, to methods that are shorter and more generic.

It's possible to write Smalltalk methods that are overly specific. It's a bit of an art to write methods that are generic. Often the first few iterations of the methods of an object are too specific. Overtime as an object is recognized to be useful in more "contexts" it's code can be evolved into a "more generic" style. Sometimes methods themselves are split off of an object to become an object of it's own. (A verb (method) becomes a noun). More generic methods tend to be smaller and are often fragmented into multiple methods enabling even more code reuse thus reducing overall code size even further. Typical method sizes in Smalltalk itself are on the order of under nine lines. This was actually a unofficial guideline of the original Smalltalk team in how to recognize opportunities to gain from fragmentation code reuse. When small methods are "typed" they limit their "reusability" since they have use only with certain types that are passed into them. By having generic types methods become usable in more contexts thus increasing code reuse. Of course this depends upon the purpose of the objects in question.

Types are often stated as a way to limit the use of objects to those intended by the original designers. In some languages "static classes" are declared locking down the functionality of these classes in the name of "safety". This is at the expense of reuse. If a "static class" is too limited then uses will have to "reinvent" the majority of the code by writing a new class that is a variant to get the job done. If the class wasn't declared static it is often possible to "expand, evolve or iterate" it's design to include the new context into new areas that were not though of before by the original designers. Obviously this is more difficult with more complex objects that have complex algorithms but in many cases it enables a class to take on a few more capabilities thus reducing the overall number of classes thus reducing code size and increasing the reliability of the system by having less code to debug and maintain. Untyped code tends to be less cryptic and easier to read.

--

Limiting what ends up in a variable can easily be handled at run time with dynamic tests of the "class" or "prototype" information that objects carry themselves. This is most often done for object data validation especially in places where information is coming from "input" sources. For example, in a Graphical User Interface window it's often important to check and filter the kinds of data that are input into certain fields.

There really are very different styles of programming when it comes to typed and untyped lanugos. These styles are dramatically different although they might seem similar.

The meta data carried by objects themselves provide a rich source of information that can be accessed to provide "type protection" for type sensitive sections of code.

What is certain is that successful systems can be built in both typed and untyped languages. The author asserts, from over twenty fives of programming experience, that untyped languages offer a more productive environment to build programs in. This is a point of view shared by many in the industry. It's also clear that many people are fervent about this issue. Many in the industry take the point of view that typed languages are superior and build successful systems with them. The proponents of untyped languages believe that their successes and productivity gains speak for themselves. Ultra large systems like JPMorgan's Das Kapital speak for itself. In systems like Das Kapital where you have tens of thousands of classes it's usually important to be able to comprehend as many of them as you can so you can maximize your use of the system. It's also important to keep the numbers of classes (or prototypes) as small as possible so that people have a chance of comprehending as much as they possibly can. As we've seen code size, number of methods, and numbers of classes/prototypes all can be reduced using generalized "untyped variable" writing style.

1) Since objects carry their own "class" or "prototype" information with them it's "redundant" and "unnecessary" to "type variables".

The assumption that values know their types at runtime is pretty strong. I am not against run-time type info in general, but in many cases it can be proved by compiler that it is redundant and unnecessary to check for a type of the value at runtime.

2) When variables are "typed" the flexibility of methods is reduced and constrained.

But not necessarily more than it's needed to carry out their responsibilities. If your typing is structural (as opposed to nominal), or your PL has implicit parameters, or type inference, the difference between the set of values that could meaningfully be bound, and the set allowed by typing is very small.

3) It's faster to write code that is "typeless". It leads to, in many if not the majority of cases, to methods that are shorter and more generic.

Did you hear about type inference?

In systems like Das Kapital where you have tens of thousands of classes... It's also important to keep the numbers of classes (or prototypes) as small as possible...

I don't consider tens of thousands of classes to be speaking for your cause. Do you imply that if written using a PL with static type checking there would be more conceptual entities?

More Peter Wiliam Lount philosophy (no value judgment implied by my post):

What is the simplest syntatic [sic] language needed to provide a full featured computer language that crosses the Wolfram Computational Equilivance Threshold where simple systems become capable of generating systems as complex as any more complicated language?

Do you imply that if written using a PL with static type checking there would be more conceptual entities?
Yes that's what I'm saying. There is a significant tendency of languages using statically typed variables to have more conceptural entities. This is caused by the tendency towards more and larger methods which leads to more complex classes. More complex classes are more difficult to add to since they contain more code. In addition in languages with "static classes" developers are often forced to duplicate functionality since they can't access the internals of the locked down "static classes". So they add a new class instead of enhancing an existing one.

where simple systems become capable of generating systems

Meaning that human factor is obsolete? Just run the simplest language that could possible work overnight, and you have the code (source or binary?).

Just run the simplest language that could possible work overnight, and you have the code (source or binary?).
No, I was not talking about autonomous "AI" program generators. That wasn't a meaning I was intending for people to get. It seems that you took the quote out of it's context and it's meaning changed.

The point is that "typed variables" are not necessary in a computer language. Untyped languages demonstrate that.

Typed variables, in my view, increase the complexity of a language beyond what is necessary. I've not heard any complelling reasons for typed variables. Untyped languages are less complex yet can be used to implement complex systems. Turing and Wolfram support this. I was referring to Wolfram's discovery to support this view. Wolfram demonstrates that "less complex" systems can generate complex results that are on par with complex systems. I was attempting to point out that this applies to computer languages as well.

In addition I'm wondering if the syntax of Smalltalk can be similified even further yet maintain it's capabiliites. It's seems that there might be some wiggle room to simlify it a little. At least with some minor adjustments the Smalltalk syntax can be improved while keeping it simple.

Along these lines, I've been able to take the Smalltalk syntax and run with it to create a new language known as Zoku that integrates many new capabilies into the language and system. I'm currently developing the Zoku compiler (using Squeak as a development platform).

The article is still being edited and is a rough draft. That particluar paragraph needs to be rewritten for clarity. Thanks for pointing it out. I can see that the article needs more work.

It amazed me that the author assigns so much value to syntactic simplicity of transformation rules, while ignoring complexity of rules interpreter.

Even if you express your program exclusively in the form of S and K combinators (and even one combinator is enough), you still are using the full power of logic theory, which is anything but simple.

I will not repeat my arguments why I think statically typed code need not be bigger or more clumsy than dynamically typed one. I can offer a narrower setting, though: why not discuss which approach is superior, passing arguments as a dictionary or as a statically typed record?

really?

anyway, sounds like he would be interested in chaitin's work.

All other things being equal, for software development, absolutely, yes.

Peter, I started replying to your arguments, but the truth is (and this is why everyone is groaning) that:

• I have covered this ground here and elsewhere, many times before,
• after looking through your posts, it is clear to me you are ill-informed about typed programming languages, and
• you are not accustomed to supporting your claims in an unambiguous manner.

Given these facts, in order for me to reply to your arguments in a way you would understand, I would have to write quite a lot and I'm not willing to do that just now.

So, I took what I wrote and started writing a (hopefully) short paper called `How to argue about types', which I'll make public when I'm satisfied with it.

For now, let me just say:

Peter: Wolfram has discovered that there is a threshold that when crossed enables very simple systems to generate complexity as complex as any complex system can generate.

It has not been demonstrated that they can generate any complex system, only certain ones of limited complexity.

Typed variables, in my view, increase the complexity of a language beyond what is necessary. I've not heard any complelling reasons for typed variables.

It's clear you haven't looked very hard. Are you even familiar with typed languages like Standard ML, Objective Caml, Haskell, Nice or Scala? Hindley-Milner type inference? Parametric polymorphism? Polymorphic lambda-calculus? Dependent types?

I'm sure you are a fine and accomplished programmer, but that alone does not equip you with the tools one needs to reason unequivocally about programming languages.

BTW, from your article:

The more complex grammar and syntax of C, C++, Perl, and Java does not give them any more computational sophistication than Smalltalk. In terms of fully featured programming lanugages, Smalltalk provides a bare minimum of capabilities needed to cross the "Wolfram Computational Equilivance threshold" or as I'll call it the "less is more threshold". This principle gives Smalltalk a tremendous expressive advantage over more complex language grammars.

I am itching to criticize this in a large number of ways, but will just remark:

This is an extraordinary claim. Can you prove it? You can elide the anecdotal evidence and dogma; I'm impervious to it. :)

Typed code tends to be less generic, thus less reusable and as a result more code is required to express the same ideas.

1. Less generic/reusable than what?

2. Given your answer to the above, are you sure they are `the same ideas'?

3. There is a sense in which the integers are more generic/reusable than the real numbers. Real numbers are more complex and difficult to understand than integers, and it would be easier simply to replace each real n by its floor (or ceiling, or truncation, or whatever), and to modify arithmetic operations like division so that the quotient of two integers always produces the closest (or whatever) integer. Do you believe this is a tidier approach to mathematics and, based on this, would you recommend we abandon the reals and work exclusively with the integers?

I await your reply.

(incidentally, ehud, i've given up on further alternative site stuff. you're acct is still the only one i send email to that bounces, which makes it a lot of fuss...)

Very strange. I'll send you an alternate address. I hope the reason for giving up isn't my email account. It would be quite a lame reason, if this is the only problem...

The operative phrase being "need not". The best "statically typed" languages (e.g. I would say Haskell, Clean, O'Caml in my experience) are very expressive. I simply do not know enough about them to say what it would take for me to be as productive with them as I am with the best "dynamically typed" languages (e.g. I would say Lisp, Smalltalk, Python in my experience).

So to put it another way, I don't know where the edges are in these languages vs. where the learning curve is for me personally. I've only done small samples in them. I see more stuff coming from these languages, but I've yet to be convinced a decent programmer will be X percent more productive, where X is an interesting number, say, X >= 2. For X < 2 the developer familiar with the older languages are better off staying where they are as the newer languages are improved.

I can offer a narrower setting, though: why not discuss which approach is superior, passing arguments as a dictionary or as a statically typed record?

All things being equal I would choose the statically typed record. But what I have found in practice is that all things are not equal. In any case, this isolated example is too narrowly contrived for a useful discussion. Obviously in Smalltalk, Lisp, etc. we do not pass dictionaries around as the single argument to all functions.

tmp = 1
a = tmp + 1
tmp = "hello"
b = tmp ++ " world"

In other words, if you have static type inferencing, should it be smart enough that the tmp variable contains values of different types at different times?

test = fromJust $ do
                     let tmp = 1
                     let a = tmp + 1
                     let tmp = "hello"
                     let b = tmp ++ " world"
                     return (a,b)