John Fremlin's blog

After more than fifty years, and fifteen years of being an ANSI standard, Lisp still has a feature advantage over platforms like .NET and Java. It's sad. Behind me at work sits a Smalltalker and the pain is shared.

As SGML was in some ways superior to XML and DSSSL was massively more capable than CSS, there's no natural force compelling progress to be in the direction of technical advancement.

The strange difficulty faced by the .NET platform in programmatically generating a class without resorting to manual IL generation and the assembly builder is symptomatic of the unnecessary balkanisation between compile and run time. F# includes a compiler that can be called programmatically, but bizarrely mishmashes two type systems together (the ML type-system which finds order of definition significant and the .NET type system which works class at a time and supports overloading) without any serious attempt to reconcile them.

On the JVM which is the intellectual heir to much of the Lisp legacy, you have the ASM bytecode framework. What about real macros?

With real macros, you can leverage the program you've already written and build on it. Emitting bytecode requires a conceptual shift, new debugging tools, and so on. It demands a (presumably slightly differently featured) parallel implementation of numerous aspects of the domain already done in the more expressive overlying language; and unnecessarily burdensome, as the C# to IL compiler is hardly a vast technological feat that needs to be guarded for its competitive advantage. Shouldn't it be available at all stages of the programming process?

The entropy and complexity of the computing universe increases naturally; things don't necessarily improve — hard and thankless work is needed.

The Scala programming language has all the features of Java, and supports all sorts of fun things like closures, higher-kinded types and inline XML. If you're starting a new project for the JVM, shouldn't you just use Scala?

The Scala environment is very interesting and in 2.8 has the ability to pass around unboxed primitive types through to functions that are specified over multiple types — so that generic functions no longer have a massive performance penalty.

Scala has operator overloading, and even the ability to give the appearance of adding new methods to existing types via the implicit mechanism.

These things make the task of writing code much more convenient. There's less need to explicitly distinguish between arrays and other sequences and unboxed doubles and other numeric types. Papering over the division between arrays, primitive types and reference types in the JVM actually reduces to some extent the conceptual complexity of using it.

But these ideas are fundamentally opposed to the reason Java came into being. Scala positions itself as multi-paradigm programming language designed to express common programming patterns in a concise, elegant way. Java is culturally opposed to these ideas: it is deliberately simple. The Java design team examined many aspects of the "modern" C and C++ languages to determine features that could be eliminated in the context of modern object-oriented programming while still retaining some similarity to C++ syntax.

In particular, a founding principle was that everything should be very explicit: A major problem with C and C++ is the amount of context you need to understand another programmer's code: you have to read all related header files, all related #defines, and all related typedefs before you can even begin to analyze a program. In essence, programming with #defines and typedefs results in every programmer inventing a new programming language that's incomprehensible to anybody other than its creator, thus defeating the goals of good programming practices.

This definition of a good programming practice is one that Scala vehemently opposes. The ability to write domain specific languages that integrate with the core is promoted as a positive.

In my opinion, the definition of a good programming practice should include whether or not it gets results. After the HotJava experiment failed perhaps it's time to admit that all three major webbrowsers (Mozilla Gecko, Webkit, and Internet Explorer) are all written in C++ for real reasons and not just force of habit.

Java was supposed to start small and grow as a reaction against the perceived causes for which languages like Lisp and Smalltalk were rejected. Scala is proud of the power of its higher-kinded types: Java is proud of removing multiple inheritance. They're not really competitors: the cultural gulf is huge.

Perhaps Scala will be able to drag the JVM into competition with numerous other platforms. It has a good set of web companies (for example, Foursquare) using it as a replacement for programmer-orientated scripting languages, and that's where Scala has a natural fit, albeit with strong-typing.

Java is deliberately not programmer-orientated. That's the point of using it — it was designed to restrict the kind of trouble programmers can get themselves into. If you're stuck with the JVM, I guess the question is: how much rope do you want to give your programmers? Scala is essentially the opposite answer to Java.

Lisp's (and especially Scheme's) greatness is its coherence — instead of expressions, statements, sequence points and so on, it just has expressions. In implementations, instead of separate tools for compiler, debugger, profiler, you generally have one tool and, if you have the source, can in a unified way examine and fluidly adapt any part. This is never going to fly in the Balkanized world of other languages, where the compiler is generally not implemented in the language itself.

Mainstream languages like JavaScript, Python, C#, C++ and Java have steadily adopted some of Lisp's ideas (e.g. garbage collection (1959)), but some, sadly, remain overlooked. Having moved back to programming in C++ and doing some C#, I'm constantly amazed that some really fundamental things from Lisp remain shrouded in mysterious brackets.

1. In my opinion, most basic and most overlooked are the benefits of usable global variables. In Lisp you don't have to keep passing extra parameters to functions because a function they call needs them. Each special variable has its own stack (per-thread in most implementations, leading to performance compromises). So you can use global variables without worrying about affecting other contexts.

Historically, lexical scoping is relatively new to Lisp (last thirty years?), and as it is much cleaner as a default, old Lisp's dynamic or special scoping received a bad name. But in the right places it makes the difference between having to add a parameter to a chain of function calls or adding an unnecessary field to a class, and simply implementing the needed functionality.

2. The condition system by Kent Pitman is utterly fantastic. C++'s STL is vastly better thought out than Common Lisp's sequences; but the conditions system in Common Lisp is a leap ahead of C++'s exceptions. Instead of an exception automatically unwinding the stack, callers can choose to catch a specific exception (called a condition) and perform some action — like, say, popping up a dialog box asking the user to free up disk space and retry — all without affecting the control flow. You're free to unwind the stack if you like of course. In implementation, this is normally pretty much a library on top of the language using special variables and closures. . .

3. Which brings me on to powerful closures. C++ is getting lambda functions, but they're not as powerful as Common Lisp's. Python resists allowing you to modify variables in the enclosing scope. In a Common Lisp lambda, you can not only modify variables in your enclosing lexical scope, but also return-from the enclosing scope (provided of course that it's still on the stack). This can be implemented by an exception with a tag unique to the enclosing function in C++ and other languages. But it is immensely useful, and much more convenient to have the compiler insert the boilerplate for you, as it allows all sorts of things.

It would be great if some these ideas would be massaged into other languages.

Played in the codejam then got an FBML Facebook app working — a small scale recreation of a program by my father, that asks progressively harder arithmetic problems. You score is saved between rounds and I guess I should start adding social friends links and things.

The source is here. It's rather hacky and needs an up-to-the-minute tpd2. Try it out!

I've never found a VM that handled running out of memory properly. Maybe Lispworks? I know that Allegro and SBCL can just crash horribly when you try to allocate too much. And Java tends to bring down my machine. I was a .NET evangelist to the all the Scala people I ran into, but now having used it, I have to eat my words.

Take a look at this C# (pseudo-code as I haven't .NET at home).

var sb = new StringBuilder();
while(true){
    try {
        sb.EnsureCapacity(1000000);
        break;
    }catch(OutOfMemoryException){
        GC.Collect();
    }
}

Even when there is plenty of memory free (2GB available on the machine and only 300MB in the program), if you rapidly repeatedly allocate this 20MB, sometimes it will throw an OutOfMemoryException. This would normally crash your program but you can just call GC.Collect() to get the GC to agree to allocate more heap for the program. It is insane that it throws OutOfMemoryException when there is so, so much space free to allocate! The fragmentation argument does not wash, as the program could freely allocate more memory. And simply, why doesn't the allocator call GC.Collect instead of throwing this exception? Having managed code in a VM means that you can de-fragment your memory when you feel like it . . .

PS. And while ThreadPool.QueueUserWorkItem is pretty great, parallel for, isn't.

Blogs normally show the last few posts on the front page. This is great if you are frequent visitor. However, if you are just stumbling onto the site for the first time, you will have to dig to find the best content — which is unlikely to be always the most recent.

Consequently, I've changed the blog frontpage to display the hottest articles in larger text sizes. The old chronological order is still available and the Atom feed is unchanged.

Any ideas for how to make the front page prettier much appreciated! As always the source is on github.

Russ Cox wrote a series of articles on regexps and then released RE2. The idea is to make a general regexp engine with a time and space complexity that does not grow horribly when confronted with a pathological string/regexp combination.

This interested me as when I made cl-irregsexp I found that the performance of competing regexp engines varied wildly. The best was generally the Perl engine which has some very good special case paths.

Years ago, when I released cl-irregsexp I wanted a good headline. I looked a small example that would keep in the fast case for cl-irregsexp, but which would trip up other implementations. I ended up with searching for either indecipherable or undecipherable &mdash indecipherable|undecipherable. Funnily, in many implementations this is slower than searching for one string then the other.

If the freshly released RE2 lives up to its interesting and useful claim that complex regexps combined with large strings cannot cause it to blow up, then it should easily handle this straightforward case.

And it does, and handles it well, coming second after cl-irregsexp — taking only 60% more time than cl-irregsexp with SBCL 1.0.36.13 and actually significantly faster than cl-irregsexp on ClozureCL 1.4. This is the one thing that cl-irregsexp specialises in (it doesn't do anything else very well) and it's nice to see a decent competitor emerge.

Combining the silly implementation tricks in cl-irregsexp with Russ Cox's general idea for dealing with regexps as DFA and then compiling them to native code via SBCL (if only computed gotos were added) could make something better than either without being massively complex. The avoidance of exponential blow-up would be nice too. But generally for most practical use, the Perl engine's tuned but unnecessarily self-limiting toolchest will be hard to beat.

I was trying to update the benchmarks for cl-irregsexp and to my surprise I found that as my laptop heated up it was getting slower. The observation was that the more times I repeated a benchmark, the slower it became.

I'd set the cpu_scaling_governors to performance, and made sure that the max scaling frequency was okay. But the CPUs were entering throttling states, as shown by acpitool.

One of the thermal zones was right on the throttle temperature when I looked at it

  Thermal zone 2 : ok, 85 C
  Trip points : 
  ------------- 
  critical (S5):           130 C
  passive:                 85 C: tc1=0 tc2=3 tsp=10 devices=CPU0 CPU1 

The room I am in is unusually hot. I guess this may invalidate some of my benchmark results. Fortunately, people have repeated most of the HTTP ones to get similar numbers, but I shall have to run them again. With the heating off.

Does anybody know a way of checking whether throttling ever kicks in? I guess I shall poll the temperature every few seconds.

PS 20100318. Worked round it for long running benchmarks by forcing the CPU to be in the lowest possible speed, and moving to a colder room.

Every two minutes, some ignorant fanboy for a particularly opinionated programming language will claim that it can be fast as C or even faster. Sadly, Common Lispers are not immune to this idiocy. And idiocy it is. Languages inherently don't have speeds.

Firstly, when comparing two languages with the same program, the results depend on how you structure the program and the compilers or language environments you choose. You have to compare best possible programs in each language to start with, which simply invalidates most of these arguments as the C program is usually very badly written.

Secondly, performance in real programs is more about communication than computations. The claim that a language can be fast as C because it can do floating point operations on data in registers (the typical argument), misses completely that modern performance is dominated by data-locality considerations (caches, talking to other cores, etc.).

Thirdly, C compilers are generally much better at optimizing than compilers for novelty languages. Making a compiler that can produce code as good as modern GCC is pretty tricky. Many novelty languages solve this by compiling down to C code. If I remember correctly, there was a point when BitC had better scores than C on the ever changing programming language benchmark game — despite compiling down to C. Again, this does not make logical sense.

The essential reason why these arguments are ridiculous is that computers have speeds, not languages. If you have a problem and you know that it requires reading through 100TB of data, then you know that you can't do it faster than the time you need to read through 100TB. All your program can do is slow that down. Unfortunately, it is true that many programming environments do slow you down, or make it very difficult to avoid being slowed down.

Once you have decided on an algorithm, then your computer determines how fast it can possibly be, and your programming environment may restrict that more. For example, in many cases the most efficient data-structure for a problem is a bit-array. A common operation needed is to find the first set bit. X86 computers include the bsf/bsr instructions to quickly find that bit. How much trouble is it to use that instruction in your novelty programming language? In GCC, there is a semi-standard asm construct; that makes it a cinch to use an instruction like this. Under Common Lisp in SBCL, for example, you would have to mess about with the compiler and defknown.

Simply being unable to utilise the dedicated hardware (even very important things like vector instructions) is a common problem for less mainstream programming environments. But this is a distraction from the main point. Poor data layout in memory and unnecessary inter-core communication are the typical causes for inefficiency.

How much trouble is it to control how structures are laid out in memory in your chosen programming environment? The language specification probably doesn't say much about it and is therefore irrelevant. It's about the compiler/environment implementation, not the language.

Talking about the inefficiencies introduced into programs by a compiler implementation is much more interesting than talking about the (very few) cases where it does well, because that further constrains how you can structure your program. Finding the best algorithm is fantastic fun, but it's diminished by people trying to whitewash the inefficiencies introduced by their chosen programming environment.

Languages don't have speeds, computers do.

I was looking at a disassembly. It contained this

nopl   0x0(%rax)

What is the point of passing an operand to NOP? NOP is the instruction that does nothing. Yet not quite true: Intel's US Patent 5,701,442 Method of modifying an instruction set architecture of a computer processor to maintain backward compatibility suggests that they could opt to use more complex NOP instructions to provide hints like memory prefetch requests. On processors without the prefetch logic the operations would do nothing, but processors with prefetch would initiate memory requests to bring the data into cache. The extended NOPs taking operands that lie in the amd64 and x86 instruction sets are called hinting nops for this reason, but as far as I know they don't yet hint anything (see the PREFETCH instructions near the same opcode code points).

It turns out that these interesting nopls, nopw, etc. are generated by GAS (that is, when using GCC). As the instruction set is encoded in quite a uniform way to simplify the decode stage, there are many instructions that achieve nothing: for example, xchg %ax,%ax (the standard two-byte nop) or leal 0(%esi),%esi, a three-byte nop. Dedicating opcodes for longer NOPs is a sensible way to simplify the CPU's own optimizations.

Aligning jump targets in code to a 16-byte boundary to make sure that the target can be fetched in a single cacheline request is important. However the padding used to flow through to this aligned boundary should be as efficiently encoded as possible, and using only a single instruction to take up eight bytes — nopw 0L(%[re]ax,%[re]ax,1), is more efficient than repeatedly exercising the decode logic on eight one-byte nops. The code to do this is in binutils/gas/config/tc-i386.c:i386_align_code.

Goes to show how mature the AMD64 instruction set has become — and how far from the days of the Binary Coded Decimal nonsense.