Lambda the Ultimate

I knew enough to write that bit of code because I had read the source code for Dennis Ritchie's PDP-11 C Compiler, specifically the version shipped with Fifth Edition UNIX. It's a remarkable program -- it compiles a fairly sophisticated language, producing decent code, all in a 64K byte footprint.

Most of the syntax analysis is done by recursive descent, except for expressions, which are parsed by using precedence tables with what we called the Railway Siding algorithm when I was in school. Code generation is done by a table-driven tree-pattern matcher.

The whole compiler runs in two passes (uhh, actually seven if you count one for the preprocessor, one for the optional freestanding peep-hole optimizer and three for the assembler), but the organization is essentially single pass -- it was split in two for space reasons. The first pass does syntax analysis & typechecking and generates code for everything but expressions. (And maybe switch statements? It's been 30 years since I read the code.) Its output is an assembly-language code/data stream with embedded expression trees to be processed in the second pass.

If the machine it compiled for were still of contemporary interest, I'd recommend it to anyone looking for a good introduction to the practicalities of software design and implementation.

Presumably to keep the compiler's size managable, case labels are treated syntactically as ordinary goto labels with a number attached. There was a stack of switch statements, and whenever a case was encountered, a label went in the output and was recorded in the stack (with an error if the stack was empty, i.e. if no switch was active.) Since case labels weren't syntactically bound to switch statements, they could occur anywhere in the switch's body, including, for example, in the middle of a nested do-while statement.

Is this available online somewhere?

At the bottom of this page there is source for a 1972 version.

www.cs.bell-labs.com/who/dmr/primevalC.html

Oh mama...

Sorry - I forgot the warning.

It's great stuff. I love code like that. I really do.

It's great stuff. I love code like that. I really do.

Yeah, I spent last evening reading through all the code and it was a lot of fun. It really is portable (or maybe not-so-portable) assembly code. You gotta love this gem:

block(n, op, t, d, p1,p2,p3)
int p1[],p2[],p3[]; {
	extern space[], error, exit, ossiz, ospace[];
	auto p[], ap[];

	p = space;
	ap = &op;
	n =+ 3;
	if(space+n >= ospace+ossiz) {
		error("Expression overflow");
		exit(1);
	}
	while(n--)
		*space++ = *ap++;
	return(p);
}

That's just plain evil (in a good way). I did a double-take, followed by an "aha" after I'd asked myself, "Why the hell isn't he referencing any of the parameters aside from n and op?" :)

That's just plain evil (in a good way). I did a double-take, followed by an "aha" after I'd asked myself, "Why the hell isn't he referencing any of the parameters aside from n and op?" :)

If I'm reading this correctly, it won't work if parameters are passed in registers, right?

Remember that when this was written, there was exactly one C compiler on Earth, so depending on details of its behavior was a venial, rather than a mortal, sin. More to the point, <stdarg.h> hadn't been invented yet -- it was developed in response to ad hoc ways (like this) of dealing with variable argument lists.

The version of the compiler that I remember was on the Fifth Edition UNIX tape, which I believe is archived as a tar file here.

The compiler is in the directory ./usr/c

There is a set of browsable archives of ancient Unix source code, including something that looks like the V5 C compiler.

The point here is to do some code *in between* iterations (i.e., interleave). This is a simple case which is just printing a delimiter between entries in a list:

void print_joined (const char *first, const char *delim,
                   const char *last, const char *def,
                   char **list) {
  switch (*list == NULL) {
    for (; *list; ++list) {
      printf("%s", delim);
      if (0) {
  case 0:
        printf("%s", first);
      }
      printf("%s", *list);
    }
    printf("%s", last);
    break;
  default:
    printf("%s", def);
    break;
  }
}

And here's the macro version, inspired by protothreads:

#define FOREACH(test, inc) \
  switch (!(test)) { \
    for (; test; inc)

#define BETWEEN 
#define FIRST if (0) { case 0:
#define EACH }
#define LAST }
#define OR_ELSE break; default:
#define DONE }

      
void print_joined (const char *first, const char *delim,
                   const char *last, const char *def,
                   char **list) {

  FOREACH(*list, ++list) {
    BETWEEN {
        printf("%s", delim);
    }
    FIRST {
        printf("%s", first);
    }
    EACH {
        printf("%s", *list);
    }
    LAST {
        printf("%s", last);
    }
    OR_ELSE {
        printf("%s", def);
    }
    DONE
}

That kind of thing still works. case labels still seem to be equivalent to goto labels. You can usefully nest ifs inside switches, for example, along the lines of:

switch(mode) {
case M_1:
  if(whatever) {
    //
  } else {
case M_2:
    //
  }
  break;
}

I don't remember exactly why I had to do this (I vaguely recall the if being a late insertion into a very large switch due to some messy logic) but the correct code was produced.

"Protothreads are extremely lightweight stackless threads designed for severely memory constrained systems, such as small embedded systems or wireless sensor network nodes."

It is curious that Duff's device doesn't work in any safe language I can think of. I don't care about the device per se, but given modern optimizers can equivalently compact code be generated in safe languages today?

The Original 'Lambda Papers' by Guy Steele and Gerald Sussman

Not this time. Sorry...

No matter, Ehud. Rules are necessary.

After the "original papers" where already cited, I'm not ashamed to reference another evergreen, which might be a source of joy for some and annoyance for others: the quine page.

One might dispute whether the befunge quines are beautiful or not. The Java quines obviously aren't very amazing.

Kay

I suppose that there could be really great business code out there,however given that business data is often extremely dirty the code itself, while perhaps heroic in coping with the data will not be likely to be 'beautiful'.

Code in real programs looks like that (we are in the fun department, aren't we?).

Is it impossible to write beautiful code in Java or is just real hard? ;-)

Java and C# are just very, very low-density programming languages. It's like a Roy Lichtenstein painting — if you stand too close, all you see are the dots. To see any beauty other than the beauty of the dots themselves, you have to stand further back and look at it from a distance. Further... further... just a bit more... are you seeing it yet? Try squinting...

But, really, what we need are more examples.

I think we need to call in Darius and Luke...

I can't think of any Java code I'd like to read in bed, either.

My favorite example for this topic is Paradigms of AI Programming, a big fat book packed with superbly crafted code and enlightening text, including (obLtU) both DSLs and some bigger language implementations. A great work of 20th century literature. :-)

I almost didn't buy it, as it looked to be by and large about things I already knew; but what's inspiring is the sustained clarity in code as communication, that's at the same time production-quality code for execution. It doesn't jump out at you with fancy tricks; it's more like reading an unobtrusively excellent prose stylist. Luke used to joke that no matter how proud you were of your code, I would send it back much better. In this case, I'd often have an idea, then after some working-out I'd invariably see that the author knew just what he was doing. Multiply by 900+ pages on a wide variety of interesting topics, and you start to see why this is my paradigm of literate code. (I did find one new bug. Norvig said it had been over a year since the last bug report and he'd started to hope there weren't any more.)

At the other end of the length scale, I've been enjoying Kragen Sitaker's hacks lately, e.g. this object calculus evaluator and this bit of text processing. Well above the usual standard for hacks -- nicely factored, organized, and documented, teaching about both their subjects and intelligent use of Python.

So you need a tool like this to find the beauty in those programs?

If you move to far away the picture itself becomes pixel. Is there anything you can still see about your code from a far distance? Design pattern, class diagrams, component diagrams... ? I've once recreated an UML diagram from a C++ program and hang it up as a wallpaper in the office. Some colleagues mentioned it to be beautiful. But I'm not really sure about deceptive trapping? Is UML the right technique to detect code smells visually?

Kay

Damn, Anton. You nearly had me laughing out of my chair here.

Java: All the beauty of C++, and none of the flexibility.

What's funny is that Anton's link above, which presumably once showed a painting, now displays an error with the following stack trace:

java.sql.SQLException: [Macromedia][SQLServer JDBC Driver][SQLServer]Invalid object name 'ArtistWorks'.
at macromedia.jdbc.base.BaseExceptions.createException(Unknown Source)
at macromedia.jdbc.base.BaseExceptions.getException(Unknown Source)
at macromedia.jdbc.sqlserver.tds.TDSRequest.processErrorToken(Unknown Source)
at macromedia.jdbc.sqlserver.tds.TDSRequest.processReplyToken(Unknown Source)
at macromedia.jdbc.sqlserver.tds.TDSRPCRequest.processReplyToken(Unknown Source)
at macromedia.jdbc.sqlserver.tds.TDSRequest.processReply(Unknown Source)
at macromedia.jdbc.sqlserver.SQLServerImplStatement.getNextResultType(Unknown Source)
at macromedia.jdbc.base.BaseStatement.commonTransitionToState(Unknown Source)
at macromedia.jdbc.base.BaseStatement.postImplExecute(Unknown Source)
at macromedia.jdbc.base.BasePreparedStatement.postImplExecute(Unknown Source)
at macromedia.jdbc.base.BaseStatement.commonExecute(Unknown Source)
at macromedia.jdbc.base.BaseStatement.executeInternal(Unknown Source)
at macromedia.jdbc.base.BasePreparedStatement.execute(Unknown Source)
at macromedia.jdbc.base.BasePreparedStatementPoolable.execute(Unknown Source)
at coldfusion.sql.Executive.executeQuery(Executive.java:1202)
at coldfusion.sql.Executive.executeQuery(Executive.java:1008)
at coldfusion.sql.Executive.executeQuery(Executive.java:939)
at coldfusion.sql.SqlImpl.execute(SqlImpl.java:325)
at coldfusion.tagext.sql.QueryTag.executeQuery(QueryTag.java:831)
at coldfusion.tagext.sql.QueryTag.doEndTag(QueryTag.java:521)
at cfQRY2d22ecfm556017016.runPage(D:\inetpub\NGA\InternationalPrints\Application\Includes\QRY-2.cfm:27)
at coldfusion.runtime.CfJspPage.invoke(CfJspPage.java:192)
at coldfusion.tagext.lang.IncludeTag.doStartTag(IncludeTag.java:366)
at coldfusion.runtime.CfJspPage._emptyTag(CfJspPage.java:2644)
at cfDetail2ecfm51378331.runPage(D:\inetpub\NGA\InternationalPrints\Tyler\Detail.cfm:3)
at coldfusion.runtime.CfJspPage.invoke(CfJspPage.java:192)
at coldfusion.tagext.lang.IncludeTag.doStartTag(IncludeTag.java:366)
at coldfusion.filter.CfincludeFilter.invoke(CfincludeFilter.java:65)
at coldfusion.filter.ApplicationFilter.invoke(ApplicationFilter.java:279)
at coldfusion.filter.RequestMonitorFilter.invoke(RequestMonitorFilter.java:48)
at coldfusion.filter.MonitoringFilter.invoke(MonitoringFilter.java:40)
at coldfusion.filter.PathFilter.invoke(PathFilter.java:86)
at coldfusion.filter.ExceptionFilter.invoke(ExceptionFilter.java:70)
at coldfusion.filter.ClientScopePersistenceFilter.invoke(ClientScopePersistenceFilter.java:28)
at coldfusion.filter.BrowserFilter.invoke(BrowserFilter.java:38)
at coldfusion.filter.NoCacheFilter.invoke(NoCacheFilter.java:46)
at coldfusion.filter.GlobalsFilter.invoke(GlobalsFilter.java:38)
at coldfusion.filter.DatasourceFilter.invoke(DatasourceFilter.java:22)
at coldfusion.CfmServlet.service(CfmServlet.java:175)
at coldfusion.bootstrap.BootstrapServlet.service(BootstrapServlet.java:89)
at jrun.servlet.FilterChain.doFilter(FilterChain.java:86)
at coldfusion.monitor.event.MonitoringServletFilter.doFilter(MonitoringServletFilter.java:42)
at coldfusion.bootstrap.BootstrapFilter.doFilter(BootstrapFilter.java:46)
at jrun.servlet.FilterChain.doFilter(FilterChain.java:94)
at jrun.servlet.FilterChain.service(FilterChain.java:101)
at jrun.servlet.ServletInvoker.invoke(ServletInvoker.java:106)
at jrun.servlet.JRunInvokerChain.invokeNext(JRunInvokerChain.java:42)
at jrun.servlet.JRunRequestDispatcher.invoke(JRunRequestDispatcher.java:284)
at jrun.servlet.ServletEngineService.dispatch(ServletEngineService.java:543)
at jrun.servlet.jrpp.JRunProxyService.invokeRunnable(JRunProxyService.java:203)
at jrunx.scheduler.ThreadPool$ThreadThrottle.invokeRunnable(ThreadPool.java:428)
at jrunx.scheduler.WorkerThread.run(WorkerThread.java:66)

...Java doesn't have TCO, so at least the stack trace is easy to read.

[sarcasm is a much easier device than is irony].

I had to look it up in wikipedia. Apparently the technical term is Benday Dots.

LtU - serving PLT and culture since 2000

Significant whitespace is one of the trademarks of beautiful code for me. Curly braces bother me (too much vertical garbage). I'm sure some people find "some" Java code beautiful.

I guess I could go on a rant about the psychology of computer programming, and how it's very under-appreciated, but I'll leave that for another thread.

Knowing how to format code is another untaught art that separates the master from the apprentice...

I really wish the psychology of computer programming was more part of PLT. Yes type/category theory is important. But it is curious that many scientists(Physicists, Chemists, etc..) really like Python.

Why? It's Pseudocode.

We need to balance density with readibility, and we need studies on this.

I also stress the notion of code reading tools and discuss several of the things you mention (e.g., regular expressions).

But do you feel that there is a concept of beauty in programming that these fulfill, or do you study them for other qualities aside from the concept of beauty?

Of course!

But I don't think I can make it explicit. I can give examples, which reflect my taste. Seeing them you will come to grasp what I mean by beutiful programming, a qaulity that like other kinds of beauty cannot be explained in words.

Well I am somewhat leery of the whole concept that there is not a possibility of ever defining an aesthetic concept apart from the level of individual tastes but anyway I think that if you give some examples of what you find beautiful you would be likely to be aware of a reason that you find them beautiful, and that such reasoning when applied across a number of examples comprises an unofficial aesthetic theory as formulated by Ehud. Have you noticed such a theory in formulation.

And if we go with it far enough will there be seen to be a general consensus Lambda theory of what is beautiful code and what is the most beautiful language (I'm expecting some Lisp variant here)

The definition of beauty can be (and has been) debated endlessly, but definitions are, in my opinion, good only insofar as they are useful towards some end.

In that light, I like this definition: a system is beautiful when nothing can be either added or taken away without changing some essential part of the system's nature. That is, everything you need is there, and nothing is there that you don't need.

Of course, "need" changes wildy with the author, audience, and users, so a piece of code that may be beautiful in one context might be completely inadequate--or completely overengineered--in another. Thus, measuring the beauty of a piece of code, even if it's just the "measurement" of one's aesthetic reaction, means understanding what a piece of code is meant to be. In the curious case of the IOCCC, being beautiful also means being extremely ugly: a horribly fascinating state of affairs.

I like to imagine beautiful (or elegant) systems as those that occupy points of local maxima on some ability/cost ("bang-for-buck") curve. Moving around on this curve involves tradeoffs between what you want and how much you're paying for it, but the most impressively beautiful systems are those that give you a lot for very little, like LISP's eval, or Hoare's in-place quicksort (as opposed to "Hello World", for example, which occupies a local maximum but does very little).

Of course, all of this is from someone who's never crafted a really beautiful piece of code, so take it as you will :)

piet hello world is now my msn messenger display picture

Where are the results of the Erlang obfuscated programming competition?

Regards,
Marc

TeX: The Program looks pretty opaque if you haven't studied TeX already. I imagine Metafont poses a similar hurdle, and tAoCP asks for dedication in another way, by being in archaic assembly language. (I coded up the MIX machine before finding I lacked the energy to actually use it.) So it's not the Pascal -- if you know C, Pascal's not a problem.

The first half of CWEB is well-written in a close-to-the-machine kind of way, but not especially interesting, and I never got around to the rest. (Where he made up a kind of DSL for syntax-directed translation and then converted the code by hand into Pascal/C.)

Literate Programming has some admirable and clever shorter examples, like the hash-trie one. Excellent book.

A problem with some of this discussion is that it emphasises the notion that 'beautiful' code consists of well defined and self-contained algorithms.

I agree. In kernel codes, beauty consists in part of identifying the right smallish constraint set for maintaining the integrity of the kernel. The implementation of these as code is generally not localized, but rather consists of the right calls made from many locations throughout the system. There are other kinds of constraint-based programs for which this is true, but in my experience it is most commonly true in critical control systems (a class of which, I would argue, well-engineered kernels are members).

So for kernels, there is a level of beauty (sometimes) in the code qua code, but there is another level of beauty in discovering constraints that are not only minimal, but are chosen in such a way that there placement in the code is suitably obvious. In a well-written kernel, ugly code is almost invariably dictated by hardware constraints or hardware bugs. Or BIOS legacy (boot sectors, anyone?), which is merely a pass-through hardware constraint.

Once you become accustomed to the style and rhythm of these things, one finds in reading the UNIX v7 code (or, I am told, the EROS code, though I'm blind to it myself -- too close) is that a missing or misplaced check screams out to the reader that something is wrong.