The LISP עץ החיים

Plain awesome!

(cached copy in case the original site goes down)

Proglangs are machines, not media

I've blogged about this before, but I think it's worth stressing again:

Programming languages should not be viewed as media, but as machines.

I first had this intuition when learning Common Lisp: CL is like a big program (i.e. an object, a machine), that's configured and used through Lisp code.

This has the nice side-effect of vindicating Lisp's built-in uglyness: who cares what a machine looks like, as long as it's the best for the job?

(Thanks to Harrison Ainsworth for the initial inspiration.)

[Edit: Ah well, I guess I pushed the publish button too quick. Of course, PLs are media. But that's obvious. I think it's important to also look at their object, machine aspects.]

Maniacal, religious dedication to code beauty

It's hard to keep source code "beautiful".

I think the only way it can work is to be dedicated like Zen monks cleaning their monastery - even one speck of dreck is too much.

The best example I know is Jonathan Bachrach's GOO (which also has a lot of other qualities). The code in there is phenomenally clean and consistent, and looks funny and artful to boot.

The dark, dark, dark art of unwinding the stack

Ian Lance Taylor, the author of the gold linker and the GCC version of the Go language, has written a nice mini-series on how to unwind the stack:

• .eh_frame
• .eh_frame_hdr
• .gcc_except_table

This is wizard-level material, and it probably helps to have the ELF and DWARF specs handy.

A Lisp slogan

Lisp is the worst programming language, except all the others that have been tried.

Curing PL Anxiety

Some years ago I was in a state that I now discover in many other people on the web, and which I term "PL anxiety". It is characterized by a constant insecurity about which PL is the best, which one to learn, how "fast" each one is, whether PG is really right, etc etc.

In retrospective, my way out of this was a four-pronged approach:

(1) The Breadwinner PL

You should know one language that's reasonably popular where you live, and which will always land you a job. In the past that meant C++, C, Java, C#, and maybe Perl and PHP, but these days you can probably also get away with Python, Ruby, JavaScript, or Scala.

What's important about the breadwinner PL is that you know its semantics and its standard library by heart.

(2) The C PL

Infinitely many good things come to you by learning C, because your OS is written in it. Studying C, you'll learn awesome stuff, like how to handle SIGSEGV, exploit your branch predictor, write a language runtime, and what a linker is, for example.

The more you learn about C, the more you'll learn about a wide array of services that are already provided to you by your OS and compiler. And C is fun and simple to boot, and will give you the warm fuzzy feeling that comes from building things (almost) from the ground up.

(3) The Romantic PLs

These are languages that you really like and if you're really lucky, might one day get paid for using. You don't have to make a choice - learn them all. They all have their pros and cons, and in the end you'll have to roll your own, anyhow.

(4) The Other Interesting PLs Out There

Also keep an eye on olden golden PLs and newcomers to the scene, even if you're never going to use them: they may blow your mind, and that's what you really should be looking for. Ωmega is a good example.

The Real World

I've come to start new non-hobby projects in my breadwinner language, because it's the most convenient, I know it by heart, all my problems have already been encountered and hopefully solved by somebody else, there are tons of libraries, and PLs seem to matter very little for many projects (and if they matter, you can always Greenspun it).

Motivation

The thing that keeps me motivated learning more about PLs are PLs themselves. I learned C writing Lisp->C compilers, for example. I'm learning about dependent types because I'd like to implement a PL that has them. It's weird, but works for me.

HTH.

On Python and Ruby

I often like to make snide remarks at Python and Ruby, because ... well, because they're not Lisp.

To offset this a bit I'd like to say what I find good and impressive about them:

Python seems to be a great language for describing algorithms. For example, Kragen's hacks abound with samples of Python code that is simply wonderful to read, and seems like exactly the way to go.

Ruby is to be congratulated for demonstrating once and for all that dynamically-typed, semi-functional, object-oriented programming is a fun and useful paradigm for systems scripting.

Why Lisp is a Big Hack (And Haskell is Doomed to Succeed)

2013 Update: I was young and stupid when I wrote this.

---

I fear that Haskell is doomed to succeed. — Tony Hoare

I ♥ Lisp. I think it's the best tool we have, at the moment, for many applications.

I don't really love Haskell that much, but I track its progress with awe. (When I say Haskell, I'm not only speaking about Haskell per se, but also about all the FP languages in its halo, like Ωmega, Agda, Epigram, ...)

And when I look at Haskell, it seems obvious to me that it's out to eat Lisp's lunch. In fact, eat all other languages' lunches.

The gist of this post is: In the not-so-far future, Haskell will be able to do everything Lisp can do now (and more), but in an adjustably-safe, statically-verified manner.

What do I mean by that?

Adjustably-safe: In this mythical, not yet-existing, but clearly on-the-horizon "Haskell", you'll be able to choose how much safety you want. You'll have "knobs" for increasing or decreasing compile-time checks for any property and invariant you desire. Or don't desire. You'll be able to switch between Lisp-style dynamic typing, Haskell-style static typing, and probably even C-style weak/no-typing. In the same program.

Statically-verified: Haskell is clearly moving towards dependent typing, which in theory, allows the expression of arbitrary invariants that are maintained statically, without having to run the program. Dependent typing is the weirdest and most awesome thing to expect of programming, this side of quantum computers.

Lisp, as it stands, can't do any of that, and won't be able to do any of that. That's simply a fact. Why? Because it's coming at the problem from the wrong direction. Trying to graft an interesting type system or verification onto Lisp is simply too heroic and ill-specified a task. Lisp starts with ultimate freedom/unsafety, and you can't constrain it. Haskell starts with ultimate bondage/safety, and then, piece by piece, adds that freedom back. On a theoretically well-founded basis.

Right now, Lisp has certain advantages. As a command or scripting language where ultimate dynamism is desired (Emacs), it's still clearly superior. But Haskell is encroaching on its habitat from all sides, just like it's encroaching on the habitats of all other languages. Right now it may appear pointy-headed and harmless. But I think it's unstoppable, and doomed to succeed.

How does that make Lisp a big hack? If my theory is right, then once Haskell will be able to do everything Lisp can do now (and more), all the while maintaining adjustable safety and static verification, I think it will be justified to call Lisp a big hack - because it lacks the possibility of this safety and verification, in principle. (Of course you have to subscribe to the idea that this safety and verification is something that's good and superior. I do.)

(HN, Reddit)

random notes

• Great discussion over on LtU: The AST Typing Problem:
  

  So to summarize, my basic argument is that the separation into distinct IRs may not necessarily reduce the overall complexity of your compiler, but it will certainly modularize it and make it easier to evolve.

  As for the compilation speed target, coupled with a desire to use the static type system of the implementation language to enforce a higher dimension of correctness than seems to be borne out in existing compilers, and your overall goal of creating a new language, be careful not to ask for too many miracles :-) -- Ben L. Titzer
  

• Emacs 24 finally gets the much-needed create-animated-image functionality.
• Good example of collaborative software design on LKML: [concept & "good taste" review] persistent store.
  

More fully-featured, modern Lisps, pulleezz

``Horsey Horseless''

While I don't like the tone of my earlier post, No more "minimal early Lisps", pulleezz, I stand by its core message: implementing a "minimal early Lisp" may actually be bad for you.

Why? An analogy: if you want to learn how to build a car, learning to build a horse carriage doesn't seem right. And the difference between "LISP" and modern Lisps is similar to that between horse carriages and cars.

IMO, modern "mainstream" Lisp (Common Lisp, Scheme, Dylan, Goo, EuLisp, ISLISP) is the king of dynamic languages. All the others (PHP, Lua, Python, Ruby, ...) are merely variations on the theme.

Compared to Haskell, Lisp is a big hack. But it has its uses. And over the course of decades, Lispers have accumulated a wealth of tricks to cope with the hackish character inherent in Lisp.

So if you reimplement an early Lisp, you're missing out on a lot of stuff, just like Lisp's "successors" in the dynamic language area do. It's a shame, really. IMO, if you care about Lisp, you owe it to yourself to not only learn about "LISP", but also what happened in the 5 decades since.

And I also think you owe it to others. The world is already plagued enough by bad programming languages. If you want to put out a new one, even if it's meant just as a toy, by all means do us all a favor and study history first.

Here's a list of some of the stuff that I think every Lisp (re-)implementer should care about:

Bindings

Understand the difference between SETQ and DEFPARAMETER for global variables.

Understand PROGV and BOUNDP. Ponder their absence in Scheme.

Understand Scheme's LET, LET*, LETREC, and LETREC*. (Yeah, Schemers are funny people. But sometimes they do have a point.)

Understand the difference between Common Lisp's dynamic variables and Scheme's parameter objects (SRFI 39). Compare to EuLisp's DYNAMIC-LET.

Understand why Clozure CL offers DEFSTATIC.

Macros

Understand EVAL-WHEN. Understand the need for something like EVAL-WHEN.

Understand Scheme's expansion process.

Understand hygienic macros, preferably SRFI 72.

Understand why some Schemes use full phase separation, while others like to collapse meta-levels (also).

Understand negative meta-levels. (Once you do, please tell me how they work.)

Control Flow

Understand CATCH/THROW, TAGBODY/GO, and BLOCK/RETURN-FROM, and how they can be implemented in terms of each other.

Understand UNWIND-PROTECT vs DYNAMIC-WIND.

Understand the condition firewall.

Contrast Dylan's, Goo's, and CL's condition systems.

Conclusion

These are just some of the ingredients shared by "mainstream" modern Lisps. They have been developed and refined over the course of 5 decades by some of our best minds. You cannot understand modern Lisp, its history, or contribute to its glorious future without knowing about them.

If you want to learn how to build horse carriages, implement a "LISP". If you want to learn how to build cars, study the items in this list.

</soapbox>

(Update: See the HN discussion for some clarifications.)

Nice quotations

Although I'm not sure I get most of them - Tim Chevalier's Quotations File:

[Satanism and Wicca] are to world religions what JavaScript is to programming languages. -- Juli Mallett

...Debugging-by-printf is a universal theme that transcends cultures and concrete syntaxes. This shit is Joseph Campbell, yo. -- Jason Reed

...real programmers often wear climbing boots to work in case a mountain should suddenly spring up in the middle of the machine room. -- anonymous

Happy new year!

PL Predictions for 2011

• JSON will be the default format for new internet APIs.
• As more people use JSON, we'll see a XML renaissance, as we - for the first time - discover that XML actually gets some things right. No really.
• GHC will get typed type-level programming and end this highly embarrassing state of untypedness. ;)
• We'll have a verified compiler-and-OS toolchain for compiling and running some kinds of apps. It won't be x86-based.
• All kinds of stuff targetting JavaScript.
• Split stacks and maybe some scheduler improvements will be shown competitive with green threads in the millions-of-threads!!1! (anti-)scenario.

I'd really like to predict some insanely great new PL for 2011...

Quick, what does this machine do?

From Dieter Rams, ten principles for good design.

HXA just published A comment adding to Dijkstra on natural language programming:

Software must always be an ‘un-natural language’ because its (ultimate, essential) purpose is different (and particular): it is not communication, it is design. ...

When you look at software, what you see is not a language, it is a machine.

I'll have to come back to this topic at another time, for now take it as a fine weekend inspiration.

[Update: Of course, Lev Manovich comes to mind immediately. From his Info-aesthetics:

Never before a single machine was an engine of economy -- AND the main tool for representation.

[Further riffing off on this idea reveals that our major platform for delivering software is called a (markup) language.]]

On Git

Giles Thomas commenting on A Guide to GIT using spatial analogies:

A much simpler view IMO is to consider the Git repositories as narratives, or meta-narratives, each committer being seen as an author of one or more. This is made particularly clear in the git man pages, where a predominant concept is the distinction between closing and opening — in a sense, it promotes the use of structural deappropriation to challenge the linear view of “revisions”. As Torvalds says, “[l]inearity is fundamentally impossible”, so the repository — or at least, a branch — is interpolated into a realism that includes the “current” revision (tip or head, as you prefer) as a reality. To put it in political terms, Mercurial deconstructs Marxist socialism, while Git analyses capitalist construction.

HTTP request visualization

You can clearly see the handshake, slow-start ramp-up and full bandwidth phases.

Packet Flight: HTTP request @ 40X from Carlos Bueno on Vimeo. (via Russ Cox)

objectophilia alert!

Here is our latest minicluster design. (Ron Minnich on 9fans (hat tip to Chris))



Plan 9 is in the works. This is a nice test and development platform
for software. We're going to make the design available in a way that
people can easily build their own.

User space? Almost certainly not.

> Should this kind of thing be done in user space?

Almost certainly not.

First off, user-space is a fragmented mess. Just from a "let's get it
done" angle, it just doesn't work. There are lots of different thing
that create new tty's, and you can't have them all fixed. Plus it
would be _way_ more code in user space than it is in kernel space.

Secondly, user-space daemons are a total mess. We've tried it many
many times, and every time the _intention_ is to make things simpler
to debug and deploy. And it almost never is. The interfaces end up
being too painful, and the "part of the code is in kernel space, part
of it is in user space" means that things just break all the time.

Finally, the whole "user space is more flexible" is just a lie. It
simply doesn't end up being true. It will be _harder_ to configure
some user-space daemon than it is to just set a flag in /sys or
whatever. The "flexibility" tends to be more a flexibility to get
things wrong than any actual advantage.

Just look at the patch in question. It's simple, it's clean, and it
"just works". Doing the same thing in user space? It would be a total
nightmare, and exactly _because_ it would be a total nightmare, the
code would never be that simple or clean.

                    Linus

(from LWN)

Ghosts of Unix Past

One of the most awesome collection of articles on software design is Neil Brown's

• Ghosts of Unix Past: a historical search for design patterns
• Ghosts of Unix past, part 2: Conflated designs
• Ghosts of Unix past, part 3: Unfixable designs
• Ghosts of Unix past, part 4: High-maintenance designs
  

Nulla Salus Extra Ecclesiam

There is always a well-known solution to every human problem - neat, plausible, and wrong. — H. L. Mencken

In software design, there often appears to be a situation where you either get a concept exactly right, or it will just be plain wrong and mess up your entire downstream development. (Maybe sometimes there are multiple good ways to solve a problem, instead of just one, but the wrong ones will always outnumber them.)

I think a good example is the difference in lexical scoping in Scheme vs Python. For my tastes, Scheme gets it exactly right, and harvests a lot of benefits from its clean design, whereas Python is just plain wrong, and harvests a lot of pain, everywhere. [In my limited experience.]

How can we avoid making systemic design errors? One way is to stick to what works. If you're designing a new PL, and your lexical scoping is different from Scheme or Haskell, I think you have a lot of explaining to do.

To know what actually works, you need taste. To create new designs without systemic error, you need a lot of midnight oil.

Which brings us back to:

Why do you glorify doing something new and stupid, when doing good things well is what people really should be admiring. — Linus Torvalds

Wow

A Turing Machine in the classic style:



Here's the awesome video:



(via LtU)

Systems programmers relax, most advice isn't for you

I'm an incredibly slow programmer (in the hobby projects I do for the love of it, that is). My ratio of thinking to typing must be around 10,000 : 1. Just to give you an indication of how slow I am: there's this one nagging project on which I've been working more or less continuously since... 2001.

Thus, programming advice of the DTSTTCPW variety (i.e. 99% of programming advice) always makes me a bit uneasy. Instead of thinking - shouldn't I just be crankin' out code, putting it online, and blogging about it on LJ?

But a couple of days ago I made an observation: almost all programming advice applies to applications, but what I'm mostly working on are systems. Since then, I'm sleeping better.

As Dr. Theodor Holm Nelson says, you can't get to the moon by piling up chairs. You may be able to learn something about an application by cranking out a quick and dirty prototype. But for systems, prototyping seems futile. Either your ideas work, or they don't, and a quick gedankenexperiment will usually be enough to find out.

Of course, I don't want to denounce experimentation as worthless. You have to know whether your ideas will be useful and work on really existing computers. But if your system is so removed from reality or complex that you're unsure about that, you're probably doing it wrong.

Take Unix pipes. There's an early memo about the need for pipes from 1964. And in 1972, pipes appeared in Unix. Do you think they spent 8 years DTSTTCPWing? I don't think so. I think that in these 8 years they spent a lot of quality time thinking about the issue, and when they had the right idea, they just knew it was right, and went ahead and implemented it.

So, to all systems programmers out there: most programming advice isn't for you. Relax, and take the time to find the right ideas.

That looks like one fine book

(via proggit)

Numbers Everybody Should Know

Julian Hyde graciously transcribed the following table from Jeff Dean's Stanford talk:

L1 cache reference	0.5 ns
Branch mispredict	5 ns
L2 cache reference	7 ns
Mutex lock/unlock	25 ns
Main memory reference	100 ns
Compress 1K bytes w/ cheap algorithm	3,000 ns
Send 2K bytes over 1 Gbps network	20,000 ns
Read 1 MB sequentially from memory	250,000 ns
Round trip within same datacenter	500,000 ns
Disk seek	10,000,000 ns
Read 1 MB sequentially from disk	20,000,000 ns
Send packet CA->Netherlands->CA	150,000,000 ns

For more details: Agner's Software optimization resources.