Lambda the Ultimate

Once a language gets clean enough that most of the complexity of a given implementation is irreducible instead of accidental, the next step is to have the language support explication of design intent and analysis of design and implementation quality.

Actually, there is now a reasonable argument to be made that both Smalltalk and Java have reached the level of analyzability you described. Commercial refactoring IDEs, interactive static analyzers and code rewrite systems are available for both of them. Those languages seem trickier than the various Lisps due to the base complexity of the syntax, but are actually easier in that their syntax is not extensible. Preprocessors, code generators, dynamic scoping and macro systems may make code easier to write and more terse, but complicate the work of code analyzers immensely. I get the feeling that time will eventually show them to be a bad path.

macro systems may make code easier to write and more terse, but complicate the work of code analyzers immensely

Are there major wins that could be gained in this area from a Lisp without macros? If everything was a primitive or a function, what interesting thing would be possible immediately? (I'm not familiar with what Java and Smalltalk analyzers do, so a point or two from their book might be the major win that applied?)

randallsquared: Are there major wins that could be gained in this area from a Lisp without macros? If everything was a primitive or a function, what interesting thing would be possible immediately? (I'm not familiar with what Java and Smalltalk analyzers do, so a point or two from their book might be the major win that applied?)

Absolutely. If you want to see a real horror story, find a copy of the Xerox Portable CommonLoops source code and find their codewalker, which is 90% hair around portability issues in macroexpansion. Take away macros, take away macroexpansion, take away 90% of PCL's codewalker, which then reduces to just... knowing what the standard Common Lisp special forms are, and using normal evaluation rules for the rest. Simple.

It's much worse in languages where "macros" are done with a preprocessor, especially if it's just plain ol' textual substitution. Parsing standard C isn't hard at all. Parsing C as it's found in the wild, including preprocessor use, is nearly impossible, and in fact a good many C analysis tools require that you run any "real-world code" through the preprocessor before running it through the analyzer in question.

Paul Snively: It's much worse in languages where "macros" are done with a preprocessor[...]

Funny, I was just about to say, "Wouldn't it solve this to use a preprocessor?" If you had macros that weren't really part of the language, but were expanded by a preprocessor that used the language, then you could have tools that did analysis do said analysis on the expanded functions-and-primitives-only code. Further, if the external macro system expanded macros in such a way as to leave a signature, you could have editors and other tools for human viewing of source to code recompact the macros into their written forms, so it seems like you could get all the benefits of macros to people, and not have them in the language itself, so that codewalkers and other tools wouldn't have to have any handling for them.

Maybe there's some reason you can't do this?

One problem is that the whole point of analyzable languages is to present results back to the developer, in a way that they can understand them. The system you describe can do analyses, but the analyses can't report back the actual locations of any of the issues found. That information was destroyed within the preprocessor and recompact phases. Even if you can get back location information, the resulting analyses will be more difficult to interpret, as they will require implicit knowlege of any macros used. "The analyzer says I've got a possible memory leak here, but it's buried somewhere in this 500 line macro which is expanded by this 200 line macro." As analysis interpretation gets more difficult, it is is less likely that analyses will actually be used.

None of this is technically impossible, but from a practical point of view it's extremely challenging to do so well enough that busy programmers will actually use your code-walkers.

I see. I'd imagined that the point of analysis (as in the PCL example) was to do some sort of transformation on the code.

is to show me what I've written, or what my coworkers have written, and how it is flawed or can be improved. Show me how it's mis-structured. Show me how it's abstractions leak. Show me how I'm misusing my dependency APIs. Show me the deadlocks, races, and stale data issues. Show me the invariants. Show me the parts of my code that aren't being tested, even if they are being executed by the tests, and show me what tests I should write. Show me what needs to be documented, and why. Show me the requirements I've missed, and the requirements I've hit. Ideally, I should be shown all of this as early as possible, and in as insightful and compelling a way as possible, so that I can claim to actually understand the engineering tradeoffs I'm paid to make.

Market my code to me, in the best possible sense of the term.

Preprocessors and pluggable compilation paths are ten-a-penny, and execution is just about the least interesting story you can tell about code. "Analyzable" means much more than that.

A truly macroless Lisp isn't a posibility because Lisp uses eager evaluation. This is why "if" has to be a macro; if it were a function, "(if (x = y) (do-this) (do-that)) would evaluate the condition and then both consequences before it passed the results of all of these to "if".

Smalltalk avoids the problem with lazy evaluation. When you say "(x = y) ifTrue: [ self.doThis ] ifFalse: [ self.doThat ] you are passing two as-yet-unevaluated blocks of code to the boolean object resulting from (x = y), and that boolean knows whether it's true or false, and thus knows which block to execute. (I find this amazingly elegant, by the way.)

The beauty of Lisp, well, moreso Scheme, is that it's a very simple language (so you don't get caught up in trying to find the odd way to do this or that, a la Ruby) and you can essentially write new languages in it.

Oh, and the last bit I left off of the previous post:

The beauty of Lisp being that you can use the macros essentially to write new languages, well, it's a good thing in many ways, all of us agree. But I've met Smalltalkers who claim to be able to do pretty much the same thing in Smalltalk without macros, so perhaps macros aren't really necessary, but are more a crutch to get around the eager evaluation issue.

You can do a similar thing to Smalltalk from Tcl too: if you use [] brackets then the argument is evaluated eagerly, but if you use {} then it is passed in as-is (as a string). For instance, just yesterday I wrote this little DSL for computer game AI on the comp.lang.tcl newsgroup:

plan Attack {
    when {$health < 40} do { goal Retreat }
    when {$nearest < $range} do { fire_at $target }
    otherwise { move_to $target }
}
plan Retreat {
    when {$health > 60} do { goal Attack }
    when {![at $base]} do { move_to $base }
    otherwise { repair }
}
goal Attack 

The action parts of rules are only evaluated when their conditions are met (and when no previous rule in the plan has fired — a form of teleoreactive program). The actual code for the DSL is quite tiny:

proc goal {name} {
    global GOAL
    set GOAL $name
}
proc plan {goal body} {
    global GOAL ACTIONS ELSE
    set GOAL $goal
    set ACTIONS($GOAL) [list]
    set ELSE($GOAL) ""
    uplevel #0 $body
}
proc when {cond _do_ action} {
    global ACTIONS GOAL
    lappend ACTIONS($GOAL) $cond $action
}
proc otherwise {action} {
    global ELSE GOAL
    set ELSE($GOAL) $action
}
# Typically, "run" would be incorporated into your game main-loop
proc run {} {
    global ACTIONS GOAL ELSE
    while 1 {
        set fired 0
        foreach {cond action} $ACTIONS($GOAL) {
            if {[uplevel #0 [list expr $cond]]} {
                 uplevel #0 $action
                 set fired 1
                 break; # Only first matching action fires
            }
        }
        if {!$fired} {
            uplevel #0 $ELSE($GOAL)
        }
    }
} 

Hope you'll excuse the use of global vars: it was just a quick demo. I wonder what a Lisp macro version would look like?

Actually, "if" is a special operator in Common Lisp (and in pretty much every other language), exactly because it is non-strict in its second and third argument. But that does not automatically make a language not "truly macroless", of course.

(p.s.: I don't like no double negations. :))

Seems like this is just the same short circuit evaluation we see in C, Pascal... maybe I'm just used to seeing lazy evaluation mean delayed evaluation.

the only difference is that smalltalk has a lightweight notation for thunks.

(if (= x y) (lambda () (do-this)) (lambda () (do-that)))

is equivalent to what you wrote (assuming full eager evaluation). I believe goo & arc have a more lightweight notation.

those blocks that smalltalk uses for control flow are simply thunks (lambdas). So your contention regarding smalltalk is incorrect.

It's worthwhile to distinguish between unnecessary and inherent complexity. Programming languages can help reduce the former and help manage the latter.

Even in the world of the perfect language, there will still be a very large measure of inherent complexity.

More than we can really cope with.

The Dilbert Principle says it well. "People Are Stupid." You, me, the author of Dilbert, Einstein, we are all too plain way too stupid to really understand the enormous programs the software industry is creating.

This is where we need a _lot_ of help.

Obviously. I never implied otherwise.

• Joel Spolsky's Law of Leaky Abstractions
• Abstractions = page faults

For example, the Java hype (purposely) confused the advantages of garbage collection and virtual machines. J2ME is the worst example. If you have a mobile phone with a slow processor, why do you want to write software for a JVM bytecode interpretor? Write native code, please. And whether garbage collection is a good or bad idea for mobile phone software is a separate question. :)

...we need languages with better modules, type systems...

What might be more useful is developing a better understanding of how to work with the module facilities and type systems we already have: What constitutes a "good module"? Or a "good type scheme"? What metrics can we use to help compare two different module or type schemes, and pick the best one for the problem at hand? How can we determine how well a particular set of module definitions, or a given type scheme, fits a problem domain?

IMHO part of the problem with modern "software engineering" is that there's no way to judge a good design. As far as I am aware, we have no way of judging which of two (or more) possible abstractions is the "better" one. In a lot of cases we don't even know what criteria we should use to judge "better" (aside from vague concepts like "coupling" and "cohesion"). Since the job of software engineers is essentially to design "good" abstractions, the lack of tools with which to judge "good" seems like a particularly serious problem to me.

Of course, these problems are only made worse by the fact that the customer often is not able to fully communicate the key features of the problem domain. How can you design an "appropriate" (let alone "good") abstraction if you don't have a clear understanding of what it is you're trying to abstract? The result is that developers demand tools that allow them to rapidly reconfigure their abstractions as they gain a better understanding of the problem domain (that's possibly one of the reasons that "dynamic" languages are so popular - and why "refactoring" IDEs are in such demand). So perhaps it would be a good idea to develop better techniques for understanding problem domains as well.

I agree. But I triedto debate another argument as well. According to this argument, the problem isn't the the generated code is unreadable (they'll grant that that this isn't really an important concern), butthat code generation makes the software architecture more complex. There are cases where this is true, but the generalized assertion isn't.

...a sign that the programming language isn't expressive enough to capture the abstraction pattern in question. Instead of kludging together a code generator in the mismatched PL, sometimes it would just make more sense to move the problem to a more capable language where the pattern can be expressed sans code generation.

In many languages you can simply embed a DSL in the same language; Scheme and Lisp are the obvious ones, with the macros. Haskellers often make combinator libraries, which are nothing more than a DSL. Even C++ can be used to embed many things, for example Boost.Spirit, which is an LL1 parser that allows BNF to be written (bastardized) in native C++. There are even people trying to create DSLs in Java (there was an earlier thread on that). Do these count as "generating" code? I've personally used C++ templates to create optimized sparse vector libraries, which have their multiplication routines generated from a multiplication table.

Semantically, if done well code generation doesn't have to be a problem. The specification language can have sound semantics, the code generator verfied, and the resulting code can be analyzed as well. It would be great to have traceability of semantic information between all levels. This would mean better tools/multi-stage languages.