Lambda the Ultimate

... might be the reason why...

It seems unfair to lay the blame for that bizarre experience on a throwaway comment. The failings in the way I was originally taught programming have a lot to do with the computing facilities available at the time, but mostly to do the interests and skills of the lecturers.

I remember struggling in a first job, trying to figure out why programs were failing - was it an error in the compiler, the system libraries, my program. Luckily I got hold of a pre-release Modula-2 compiler and unlike the C compiler that came with the machine it provided accurate specific error messages, which allowed me to report bugs in the system libraries (and fix my own code).

I also remember bursting out laughing when the Modula-2 compiler warned correctly that I had written an infinite loop! Ooops.

...the fact that the industry went chasing off on on the C/C++ trail vs. the Pascal/Modula/Modula-2/Oberon trail. Things would be so, so different if it hadn't, IMHO.

I disagree. I don’t think that things would be any different. Except for superficial syntax similarities, Java as actually a descendent of Pascal rather than of C. The lineage of Java is:

Pascal -> Mesa -> Cedar -> Oak/Java
             \-->Modula2

You can even see the lineage in Java’s original name: “Oak”, which pays homage to “Cedar”. The purpose of the Oak project was to take Cedar and give it a more “C”-ish syntax so that it would acceptable to the masses (of C programmers). (Modula2 was also inspired by Mesa so I guess that would make it Java’s Uncle.)

C# is also derived from Pascal:

Pascal -> Mesa -> Cedar -> Oak/Java -> C#
Pascal -> TurboPascal -> Delphi -------/

Despite whatever Microsoft may say about C#’s origins, it has nothing to do with C++. C# is clearly just a Java clone with some added ideas from Delphi (which is Pascal).

Today, most programmers are programming in languages which are semantically descendent from Pascal and merely syntactically descendent from C. (Better this than the other way around ;-) ).

C, on the other hand, has become an evolutionary dead-end (which is not to say that it’s dead, just that it isn’t spawning any new descendents).

very true. C syntax hiding a mix of algol and smalltalk semantics underneath... :)

In fact they are so similar, that one can consider them as different skins for the same language.

...if you mean Pascal extended with the various direct-memory-access features of Turbo Pascal or Mac Pascal. As a matter of historical fact, by the time I joined Apple, MPW Pascal and MPW C shared a common intermediate representation and code generator—only the lexing and parsing was different. This did nothing whatsoever to mitigate the endless flamewars as to which compiler produced [faster|smaller|your definition of "better" here] code.

Yes, they are very similar, owing to their common Algol heritage, but where they differ: bounds checking, strength of typing, use of pointers, etc., modern languages like Java and C# follow the Pascal rather than the C tradition. It is only because they are so similar that the majority of developers never noticed the switch.

I read that anecdote somewhat differently. I thought that they wrote a compiler for a subset of pascal in fortran (which was successful), and intended to translate the pascal compiler in fortran into a pascal compiler in pascal. He then comments that the style of the compiler was so tied to fortran that translating it was impossible.

However, Wirth then goes on to say that they wrote a pascal compiler in pascal from scratch, without the benefit of being able to test it by testing via compilation. Apparently, they then translated the pascal compiler in pascal to assembly to bootstrap the compiler. I'm confused by this, because of the prior claims that they had a working pascal compiler in fortran for a substantial subset of pascal. Does anyone understand this?

Butler Lampson's list is of honestly good ideas. Some of them might fall into Wirth's list now, but most of them are timeless IMO.

...is the one in which an object maintains some state that's shared by the methods that it implements. In such a context, a method isn't a mathematical function, since its return value can be affected by calling other methods between calls to it.

but I do hope that your understanding of OOP is not based entirely on C++ and Java. :)

It got me wondering if c++ programmers still use structs since a struct is basically a class without any methods and all of its instance variables are public.

The only difference between a class and a struct is the default visibility. Classes start out private, structs start out public. Either may have methods (including constructors and destructors, virtual methods), either may have private members, participate in inheritance, etc. Using dot and -> for both is like using + for both positive and negative integers.

Personally, I use "class" for opaque objects and "struct" for simple tuples. It's more documentation than anything else.

In C++, a class may be laid out in memory as the compiler wishes, but a struct must follow the same order (and alignment issues, etc.) as declared. This is part of the valid C == valid C++ issue. Also one of those cases where no-one knows an actual instance of this every being implemented in a C++ compiler.

My personal preference wrt to classes and struct is that I use a class for things that have non-trivial invariants (thus also necessitating get/set methods, copy constructions, etc.) and a simple struct when I would use a tuple in languages that support them natively. Unfortunately, boost::tuple sometimes takes too great a compile hit to use ubiqutiously.

Wirth was talking about records as in: simple data structure to hold together several kinds of information in one package. You're talking about a particular implementation which can have methods. This is not really an equivalent to a simple record.

And i agree with Wirth: a class is a record with some pointers to functions as record members and which receive the record instance itself as an implicit argument. Of course, compiler help to get that implicit argument passed on is needed.

And i agree with Wirth: a class is a record with some pointers to functions as record members and which receive the record instance itself as an implicit argument. Of course, compiler help to get that implicit argument passed on is needed.

You don't need to supply the extra argument. Just use a record of closures. The "objects are records of closures" motto actually is folklore, particularly in the functional world.

As for the rest of Wirth's paper, it is hard to resist ranting, because some of it I really found shockingly naive or out of touch with today's reality. And it seems to me that Wirth does not value abstraction. Nested procedures are not worthwhile? Please, everybody seems to be finally going higher-order these days, as it is the prerequisite for powerful abstraction. Linear lists for storing environments? Every compiler writer should know the mantra about the possibility of generated code, and using scalable algorithms. It's just too trivial to do right to ever bother doing it wrong, at least in a language that enables abstraction. And what were these bits about memory protection?

And what were these bits about memory protection?

I didn't understand his objection to this (in addition to other stuff). He seemed to say we didn't need page mapping because we have huge memories nowadays. After that I was lost. Even single address space systems relu on memory protection to prevent programs interfering with each other. A bit OT for LtU though.

He was making the (correct) argument that if you work in a safe language you don't need hardware memory protection. This is because no program can corrupt another program's memory, because there program can corrupt memory, period.

However, it seems to me that you'd want virtual memory even with safe programs, because it lets you abstract away from the amount of physical RAM. And memory protection falls out as a very cheap extra once you have the machinery to do paging. Can any systems hackers tell me if I am wrong about this?

His argument is only correct on two conditions. 1) Everyone is using a safe language. 2) The compiler is provably correct. With memory protection a compiler bug might make your program crash, as opposed to all your programs. If you're really unlucky programs that have had their memory overwritten might not crash....

The compiler need not be provably correct.

The way a system like this would work is: the operating system refuses to run anything but safe code. All safe code must contain a machine-verifiable proof of its safety.

If the compiler has a bug, it spits out bad code, or a buggy proof, and the operating system then refuses to run the code. Not catastrophic.

The Java VM's bytecode verifier serves an analogous purpose. (Here "proof" maps to "type information", which is embedded in class files.)

(Perhaps this is a too-generous interpretation of Wirth.)

This was essentially how JavaOS worked, IIRC. It actually got pretty good performance numbers, both because it didn't require any memory protection, and because I/O didn't require copying data between user space and kernel space. It could do that because it only ran programs written as JVM bytecodes, with the accompanying memory-safety proofs. The only thing that had to be trusted was the JVM.

Perhaps this thread will be of interest.

Jorend said "The compiler need not be provably correct."

It seems to me like you are just altering the definition of correct so that the compiler must "merely" be provably correct in never attaching a 'good' proof to buggy code. The cost of this is that the OS must provably never run code with a buggy proof and the verifier that verifies the proof must also be provably correct and never accept a 'bad' proof. I note that few of these could be relaxed if others were made more strict, but this is just more shuffling the "must be provably correct" code around, (or so it seems to me).

This doesn't seem to me substantially different from "the compiler must be provably correct."

The verifier is likely a smaller program than the compiler. The OS has to never run code with a buggy proof regardless of everything else, as the bugs may be due to intentional malice rather than compiler error.

First, "good" proofs can't be attached to buggy code, as validating the proof of course includes checking that the proof corresponds to the code. You don't need to prove that the compiler does this correctly. You just need to know that if doesn't do it correctly, your program will fail to load.

Second, commercial compilers tend to be large and complex beasts, far too large to formally verified with current tools. Proof verifiers can be much smaller. There have been JVM bytecode verifiers written for smart cards with sizes as small as 11kb. These validate proof-carrying-bytecode for not just memory safety but also bytecode well-formedness, control-path safety (every jump is to a valid executable position), and some aspects of type-safety (references can't be used as ints, etc.). I don't know if any of these have been formally validated, but the level of security scrutiny for verifiers has been much higher than anything possible for compilers.

Note also that the verifier isn't just preventing code created by a buggy compiler, it's also preventing malicious code, even if hand-crafted as assembly.

Also note that some of the "proofs" are actually very simple statements. In the simplest version of JVM bytecode verification, the attached memory safety "proof" is nothing more than an annotation on each method detailing the maximum size of it's local computation stack. This is specified as just two 8-bit integers (one for local variables, one for parameters). The verifier both checks that that size is never exceeded, and uses that maximum size to figure out everything else it needs for the proof. There are more complex validations that require more intermediate values to be provided (thus trading program size for load time), in general the compiler's job can be best seen as "calculating correct values" rather than "generating proofs".

See this and related papers here.

Update: There's much more information at the Verificard site.

The VerifiCard project finished some time ago, but there's more recent stuff from the Everest group at Inria about Program verification and Proof Carrying Code.

He was making the (correct) argument that if you work in a safe language you don't need hardware memory protection. This is because no program can corrupt another program's memory, because there program can corrupt memory, period.

I thought that what he was getting at but it only works if all languages are safe. If someone creates an unsafe language (which is possible due to the generality of the instruction sets we use today), all bets are off when you've doing away with hardware protection.

If we only allow safe languages on your system wouldn't that require hardware protection of some sort, implicit in the design? Possibly more sophisticated than those Wirth objected with more complex hardware? Something along the lines of a Java, MSIL, Parrot chip?

What I mean is, to be sure programmes could not interfere with one another and be safe in the environment Wirth proposes, you'd need the hardware to more closely follow the semantics of safe languages. That wouldn't be a bad thing, but it would be a rather big shift for hardware folk (software folk less so due to the use of things like Java, etc).

[edit: removed superfolous 'and']

If we only allow safe languages on your system wouldn't that require hardware protection of some sort, implicit in the design?

No. It can be done in software. The operating system would have to verify that code is safe before allowing it to run.

Remember the Lilith project? (Here is the abstract from the still-secret 1981 ACM paper about it.) I'm guessing that's one of the systems that Wirth had in mind.

The personal work station offers significant advantages over the large-scale, central computing facility accessed via a terminal. Among them are availability, reliability, simplicity of operation, and a high bandwidth to the user. Modern technology allows to build systems for high-level language programming with significant computing power for a reasonable price. At the Institut fur Informatik of ETH we have designed and built such a personal computer tailored to the language Modula-2. This paper is a report on this project which encompasses language design, development of a compiler and a single-user operating system, design of an architecture suitable for compiling and yielding a high density of code, and the development and construction of the hardware. 20 Lilith computers are now in use at ETH. A principal theme is that the requirements of software engineering influence the design of the language, and that its facilities are reflected by the architecture of the computer and the structure of the hardware. The module structure is used to exemplify this theme. That the hardware should be designed according to the programming language, instead of vice-versa, is particularly relevant in view of the trend towards VLSI technology.

I think that one of his points was that one could make reasonably capable systems that are vastly simpler than most of those in use today, by changing a few basic assumptions (e.g., one safe language for all apps).

MS Research Singularity project has some ideas of Wirth implemented. ( http://research.microsoft.com/os/singularity/)

From the page: "We recently released two Technical Reports. MSR-TR-2006-43 shows that hardware protection is not "free" and can have significant performance costs. We advocate the use of software isolated processes (SIPs) to replace hardware isolated processes. MSR-TR-2006-51 defines a new sealed process architecture to replace the open process architecture developed by Multics and used in almost all modern operating systems. We advocate the use of sealed processes to improve the security and dependability of software systems."

Heiko

For the record, Singularity was discussed on LtU.

They even go into hybrid systems, so people who don't trust their compiler could run in a "classic" mode, or something.

Yet, if someone doesn't trust their compiler, then why should they even trust the code to do proper things? Memory protection protects very little in computer systems that is of importance. There's all the user's files, which under most systems, any program the user runs could trash them.

Also, the idea of safe languages and their memory protection makes the micro-kernel vs monolithic kernel debate silly. The monolithic people are right that the performance impact from runtime protection barriers are too great, the micro-kernel people are right that component isolation is necessary even in kernel design.

Safe languages offer protection barriers that don't require runtime enforcement. That popular kernels are not using safe languages will make me never trust them even how much data about their stability is collected.

Well I think that his point that now that we have enough memory, do we still need virtual memory?

There are quite a few person which disable the swap because they're fed up with the poor interactivity of the computer..

Uses of virtual memory go well beyond simply "having enough memory". They include file mapping (including demand-paged executables), copy-on-write sharing, memory defragmentation, and sparse addressing of data structures. Not to mention single-level storage systems, where there is a unified very big address space used for everything.

There are quite a few person which disable the swap because they're fed up with the poor interactivity of the computer..

Yorick did a fine reply on why we still need virtual memory. Disabling the swap is a hack to avoid some problem they have noticed, rather than a statement that nobody needs swap.

A closure is just a struct with a function pointer as one member, which function receives a pointer to the struct instance itself as an implicit argument. Of course, compiler help to get that implicit argument passed in is needed.

Time to invoke Anton's old gem:

The venerable master Qc Na was walking with his student, Anton. Hoping to
prompt the master into a discussion, Anton said "Master, I have heard that
objects are a very good thing - is this true?" Qc Na looked pityingly at
his student and replied, "Foolish pupil - objects are merely a poor man's
closures."

Chastised, Anton took his leave from his master and returned to his cell,
intent on studying closures. He carefully read the entire "Lambda: The
Ultimate..." series of papers and its cousins, and implemented a small
Scheme interpreter with a closure-based object system. He learned much, and
looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by
saying "Master, I have diligently studied the matter, and now understand
that objects are truly a poor man's closures." Qc Na responded by hitting
Anton with his stick, saying "When will you learn? Closures are a poor man's
object." At that moment, Anton became enlightened.

The truth of this, unfortunately, might be largely lost upon those who have never encountered Oaklisp, which is a somewhat rare system because objects are taken as primitive, and lambdas are a special case of objects. :-) For perfectly good hysterical raisins, most implementations treat lambda as primitive, building objects (if they have them at all) therefrom.

Yeah, "automatically declared variables" is a better pointer to what I'm describing. It would certainly be conceptually possible to declare a variable without declaring its type, which would address the problem of accidentally creating a variable but still allow implicit typing.

I suppose I would mostly agree with that rule of thumb, aside from the fact that in 3 I'd prefer to have the default be off rather than on. Forgetting to turn it off leads to weird obscure bugs; forgetting to turn it on leads to immediate and obvious bugs.

The mention of Perl, though, brings up another point -- automatic declarations probably are safer in interpreted languages, which have the luxury of only allowing variable-creation on the lhs of expressions. (Though, even there, procedure calls could be tricky, unless one allows something equivalent to passing undeclared variables that may or may not get automatically declared in the procedure. Maybe strict tracking of undefined variables would deal with that, but it still seems likely to lead to much more obscure bugs.)

It would certainly be conceptually possible to declare a variable without declaring its type, which would address the problem of accidentally creating a variable but still allow implicit typing.

This is what let...in is for, to give an example. Or if you want mutability, the various ML-style new reference operations.

I don't see the problem you point out in 4.3, about the 'case' statement. 'case' is terminated by 'end', and the individual branches are separated by '|'. That seems pretty unambiguous because terminators are presented where necessary.

I was pointing at the bunch of if..then..else after "Now the apparently simple statement goto S[i] is equivalent to [...]". He reuses, because it is practical, a syntax that he severely criticized one page before.

(Note that this precise example does not admit the "dangling else" ambiguity, as only the last "if" branch has its "else" branch missing. But stil...)