Lisp as the Maxwell Equations of Software (2012)
michaelnielsen.org
michaelnielsen.org
Languages involve a lot of apparent mystification, in part because the syntax tree and the semantics of the syntax tree are not the program you are writing. Who knows what "class X {}" actually does to the (virtual) machine?
By essentially providing a 1:1 correspondence between the "real" semantics and the "apparent" semantics, programming this way can seem magical compared to other languages.
With assembly you arent taking objects of the language and making them objects of a metalanguage, ie. you arent preserving semantics when you abstract. All you're doing is creating hacks on top of the basic semantics, so in effect, introducing a new language (of specialized jumps, etc.).
(If Lisp people want to start doing that though, I'd be happy. Prolog is great.)
So you'll have to modify your statement at minimum to "a single person other than Mark Tarver" ^_^.
I'll give Prolog a shot!
It took years to develop approaches to garbage collection (the earliest prototypes used bump allocators and crashed when they exhausted a heap), years to finalize the syntax of the language (you'll notice that the "maxwell's equations" are written using M-Expressions, a syntax for the language which was discarded for ease of implementation and later rationalized because homoiconicity can be handy), decades to realize how important lexical scope (versus dynamic) is to maintaining encapsulation. Modern Lisps are substantially different in syntax and semantics from these earliest ideas; we're just still calling them Lisp.
It's very easy to make Lisp look elegant when you brush all the implementation details under the rug.
Together these changes brush the computational complexities under the rug, and leave only the descriptive power of the laws:
* "the gradient of the electric field is proportional to the amount of electric charge"
* "the curl of an electric field is always zero"
* "the gradient of a magnetic field is always zero"
* "the curl of a magnetic field is proportional to the size of the electric current plus the amount of change in the electric field with respect to time".
As Wikipedia notes: "Mesopotamian, Indian and Chinese mathematicians are all known to have discovered the theorem independently and, in some cases, provide proofs for special cases."
An interesting take on "modern", meaning "the last 3 decades or so", which is like millenia in the IT industry...
Or are you referring to some other difference?
Work clothes, suits and hazmat wear also don't change their design every three months.
Like cycles in economics, climate, fashion, etc.
For example, John Shutt has developed a non-trivial theory of F-Expressions (vau-calculus)[1] and a language named Kernel that employs them[2]. Neither has received wide attention yet, but the Lisp renaissance of the past few years is still young...
[1] https://www.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...
[2] ftp://ftp.cs.wpi.edu/pub/techreports/pdf/05-07.pdf
So it started an ideal until a student was foolish enough to actually program it. Yet this vaporous ideal was enough to write a symbolic differentiator. You don't have bytes nor integers but you can express non trivial mathematical concepts.
You had almost nothing yet you could do a lot, another fun fact. To me Lisp is like a linguistic library, on top of which you'll add primitive types as needed. The expressiveness is given by scope, lambdas, logic and recursion, the rest is secondary. Maybe my lambda calculus classes are making me biased though. McCarthy said he wasn't too inspired by LC even though I've read he was a student of A. Church.
ps: about scoping, I've read emails from Lisp users circa 59 who were discussing the addition of lexical scope, that was before Algol was publicly released.
More to the point, Lisp is nice because it's in a sweet spot of language complexity vs self-interpreter complexity, and lambda calculus is nice because it's a simple basis of computation. But there are many languages that make self-interpreters simple (assembly, Forth...) and many simple bases of computation (SKI calculus, rule 110...)
To call something the "Maxwell equations of software", IMO you need something more substantial. For example, Haskell folks can claim that lazy evaluation is provably superior (in termination and time complexity) to any other evaluation strategy. The dependent typing folks can claim that all valid programs correspond to valid proofs and vice versa, and that strict and lazy evaluation are equivalent w.r.t. termination. The guy behind Kernel can claim that the one true Lisp should allow you to mapcar a macro. There are many kinds of wonderful math that give you insight into computation!
E.g. does the additional math you're talking about stand on top of either of those? I don't know (By nature and calling I'm a scientist of the continuous world, not discrete, damnit! :-).
Of course, I'm moving the goalposts by using "Lisp" as a stand in for the lambda calculus (and I remember someone, maybe McCarthy, saying Lisp is what you get after you've read and only understand the first chapter of a book on it :-), which I don't even know at the poets level (but am maybe starting to correct that; don't know if the payoff is worth it to me at this point in my life).
To many people, Lisp is simply the most advanced language they know, so they view other languages as "Lisp plus some features that you could implement with macros". They might as well view other languages as "assembly plus some features that you could implement with assembly". It's just the blub paradox all over again.
To add insult to injury, many of today's advanced languages aren't even built on Lisp. They throw away the key idea of Lisp (easy equivalence between code and data) in order to achieve other things which are not achievable in Lisp (provability of certain classes of statements about all valid programs). To put it in an exaggerated but not entirely untrue way, these days Lisp seems like a dead end in terms of research. Most of the interesting stuff is coming from ML-like languages instead.
With that in mind, I would not want to learn a new language for every project I was a part of. I'd even go so far as to say: The majority of programmers cannot design a good language, and if Lisp gives them the opportunity to try then that's a BadThing™.
[1]http://blogs.msdn.com/b/peterhal/archive/2006/01/04/509302.a...
Even single-author projects have the person who wrote the code months ago and the person reading it today. :)
> is usually the time it takes to read and understand source code. Some estimates[1] claim that up to 78% of development time is spent just reading code.
Sure. This is a big deal.
I'm not sure the software-conservative approach of locking down the syntax and flexibility of expression is deeply helpful, though. My experience is that comprehending syntax (while it can be a barrier) isn't the biggest portion of that 78% you're talking about -- maybe 15%. Wrapping your head around the semantics of what a piece of code does is a much bigger portion.
The semantics of what the software does are the true language of the program you're writing, so in a sense the choice isn't whether or not you're going to have a DSL or not, it's just how concisely the syntax of the language will support the expression of it. And I've found that the less flexibility you have in syntax, the more likely it is over time that you'll have to type/read over larger amounts of code in order to capture the expression of a given semantic goal.
Well, you have to. Every new project comes with its own vocabulary and semantics. You have to learn those whether they're expressed in terms of data/function abstractions or syntactic abstractions. Sometimes—perhaps less often than many Lisp programmers appreciate, but sometimes nonetheless—those new concepts are simply easier to understand when expressed syntactically.
>The majority of programmers cannot design a good language, and if Lisp gives them the opportunity to try then that's a BadThing™
There are many programmers (I say "many" because I haven't actually met most programmers, but "most" might be true, too) who cannot design good data abstractions. Would you consider that [your favorite "OO" language here] allows one to form data abstractions to be a "bad thing?"
The risk is that Lisp is used to create a lousy language ill-suited for the task at hand. The benefits come when it is used to capture the ubiquitous language of a domain and used at the appropriate level of abstraction.
If it makes the code harder to reason about, then it's not the right level of abstraction. But poor code can be written in any language.
This takes Lisp as the machine language of a high-level machine (with READ as the assembler). You could do the same with C, but without a compiler stage it'd be absurd.
Deleted comment
Not that I know of, but only because of microcode errors. I was told "Sussman wasn't quite as smart as he thought he was" to tape it out without making really sure the microcode was correct.
In all fairness, at the time they had little in the way of available computer resources to e.g. simulate it, and it was all part of a very exciting time when MIT started doing Mead and Conway style VLSI, see https://en.wikipedia.org/wiki/Mead_%26_Conway_revolution and note the latter gave a famous course on it at MIT in 1978.
I stumble upon that article from my bookmarks while pouring my latest side project (http://www.learn-computing-directory.org/languages-and-progr...) and thought about submitting it to HN. By the way, feel free to give me feedbacks about the directory! (in still in very alpha state but already online). I only fill for the moment the "Algorithms and Data Structures", "Compilers" and "Theory of computation" topics.
Two great articles that complements perfectly the one submitted are LISP interpreters in Python from Norvig: http://norvig.com/lispy.html and http://norvig.com/lispy2.html Also, the book "Understanding Computation" (http://computationbook.com/) can be a great companion as there is a section about Lambda Calculus.
Jérémie.
Usable and efficient Common Lisp implementation can be build from just ~25 primitives (more than core LISP but still very elegant). Elegant derivation of Lisp world does not matter when the atoms and the molecules can't be distinguished. Is the object system and meta-object protocol implemented as primitives by people who designed the Lisp implementation, or is it external library? Who cares. Only performance and correct function matter.
Other axioms of computing lead the user in different directions, notably Hindley-Milner. Lisp carves territory in mathematical state space, not physical reality.
I'm curious how people might carry that through the analogy.
http://www.meetup.com/Boston-Clojure-Group/events/218650142/
But the Lisp Machines were more than Lisp on hw. They were about the software, the shell, the IDE. Some work was started more than 15 years ago to revive the CLIM API that made this possible and the original authors still work on it now. I'm really glad about this:
Developing your own special-purpose hardware is easier than ever these days. There are numerous open-source off-the-shelf FGPAs that are mature and fast.
See more in my longer comment in this subthread.
I think we're overwhelmed by nostalgia and this stops us from looking at what's important: software. We are missing the software pieces that made the Lisp Machines. We don't have those and this is more important than not having a CL CPU.
I would hate to have a Lisp Machine made with today's custom hardware and all the C/C++/Java/Python guys come and ask: what was the fuss was all about? Where's that IDE from 25 years ago you so proudly preached?
And I fully agree the focus should be on the software, as I hope I made clear in other comments in this topic.
http://www.xilinx.com/products/silicon-devices/fpga/virtex-u...
http://www.altera.com/devices/fpga/stratix-fpgas/stratix-v/o...
I know I can do this with small scale ones, including some of the tools, on sub-$100/$200 boards with not a lot of memory (the research lowRISC has prompted me to do has been fascinating). If the answer to the above is 6 figures, the intersection of those who can afford it and those who are inclined to do it would be small.
Maybe not 0, then again, at what speed could you get a synchronous microcoded CPU working? Aren't we still talking way way below +3GHz, like the 50-100MHz I just cited? Is 200MHz possible?
I've read of one that uses magic (and no doubt $$$ in tools) to translate your sync design into an faster async one in the middle of their magic FPGAs, but even then I don't recall the potential speed breaking past a GHz if that. Although that was a while ago, 1-2 Moore's Law doublings ^_^.
Flip side, are the FPGA companies going to open up their kimonos to allow a lot more people to design in their increasingly inexpensive (Moore's Law) parts?
As to clock speeds, here's part of the abstract to a white paper that might interest you:
"A clock rate higher than 500 MHz can be supported on a mid-speed grade 7 series device with almost 100% of the logic slices, more than 90% of the DSP48 slices, and 70% of the block RAMs utilized. This requires the designer to follow some rather simple design rules that cover both algorithmic and implementation aspects. These rules are reviewed in the paper."
http://www.xilinx.com/support/documentation/white_papers/wp4...
...but clock speed isn't necessarily a super interesting factor if your data bus is 2048 bits wide, with a pipline 100 stages deep, comparing to say 64 bits wide and 10 stages deep on a CPU. Again, this is not to say that anyone should try implementing a Lisp machine on an FPGA to try to take market share away from Intel.
Lisp Machines were created in part due to the desire to get the most performance possible back in the days when CPUs were made out of discrete low and medium scale integration TTL (there were also ECL hot-rods, but their much greater costs across the board starting with design limited them to proven concepts, like mainframes of proven value, supercomputers, and the Xerox Dorado, after the Alto etc. had proven the worth of the concept).
Everyone was limited: maximum logic speeds were pretty low, you could try to avoid using microcoded synchronous designs, but e.g. Honeywell proved that to be a terrible idea, as noted elsewhere memory was very dear. E.g. the Lisp Machine was conceived not long after Intel shipped the first generally available DRAM chip, a whopping 1,024 bits (which was used along with the first model of the PDP-11 to provide graphics terminals to the MIT-AI PDP-10), etc. etc.
So there was a lot to be said for making a custom TTL CPU optimized for Lisp. And only that, initially: to provide some perspective, the three major improvements of LMI's LAMBDA CPU over the CADR were using Fairchild's FAST family of high speed TTL, stealing one bit from the 8 bits dedicated to tags to double the address space (no doubt a hack enabled by it having a 2 space copying GC), and adding a neat TRW 16 bit integer multiply chip.
The game radically changed when you could fit all of a CPU on a single silicon die. And for a whole bunch of well discussed reasons, to which I would add Symbolics being very badly managed, and LMI killed off by dirty Canadian politics, there was no RISC based Lisp processor, Lisp Machines didn't make the transition to that era. And now CPUs are so fast, so wide, have so much cache ... e.g. more L3 cache than a Lisp Machine of old was likely to have in DRAM, the hardware case isn't compelling. Although I'm following the lowRISC project because they propose to add 2 tag bits to the RISC-V architecture.
So, we're really talking about software, and what was the Lisp Machine in that respect. Well, us partisans of it thought it was the highest leveraged software development platform in existence, akin to supercomputers for leveraging scientists (another field that's changed radically, in part due to technology, in part due to geopolitics changing for the better).
For now, I'll finish this overly long comment by asking if a modern, productive programmer could be so without using a web browser along with the stuff we think of as software development tools. I.e., what would/should the scope of a 21st Century Lisp Machine be?
My limited & roseate view of a 21st century Lisp machine is based on an old theme - a massively parallel computing system using bespoke silicon logic blocks.
As you have noted below, not only are the cache sizes in a modern CPU monstrous, there's also the compilers optimized for these caches, instructions, branch prediction units, etc. No point in ending up with a chip that is much slower than an equivalent one running on a specially-designed virtual machine, which is itself much slower than MPI.
Dreaming on, such a Lisp machine would need a vast collaborative academic effort with substantially new IP design, in say the 32nm silicon process node. That's the most advanced node where lithography is still (somewhat) manageable for custom IP design.
Anyway, if you're not talking ccNUMA, the limitations of which has got me looking hard at Barrelfish (http://www.barrelfish.org/), e.g. if you're talking stuff in the land of MPI, again it's going to be very hard to beat commodity CPUs.
Although in that dreaming, look at lowRISC: http://www.lowrisc.org/ looking at things now, they propose taping out production silicon as soon as 2016, and say 48 and 28nm processes look good. From the site:
What level of performance will it have?
To run Linux "well". The clock rate achieved will depend on the technology node and particular process selected. As a rough guide we would expect ~500-1GHz at 40nm and ~1.0-1.5GHz at 28nm.
Is volume fabrication feasible?
Yes. There are a number of routes open to us. Early production runs are likely to be done in batches of ~25 wafers. This would yield around 100-200K good chips per batch. We expect to produce packaged chips for less than $10 each.
And with a little quality time with Google, the numbers look good. Ignoring the minor detail of NRE like making masks, a single and very big wafer really doesn't cost all that much, like quite a bit less than $10K.
And we now have tools to organize these sorts of efforts, e.g. crowdsourcing. But it's not trivial, e.g. one of the things that makes this messy is modern chips have DRAM controllers, and that gets you heavily into analog land. But it's now conceivable, which hasn't been true for a very long time, say starting somewhere in the range between when the 68000 and 386 shipped in the '80s.
Or to put it another way, without exhausting my bank account I could build from parts I can purchase today on Newegg a many CPUs 3/4ths TiB DRAM Supermicro system. Supermicro has standard boards with more memory, and has a monster you can only buy complete that'll hold 4 CPU chips and up to 6 TiB DRAM on daughter boards; I think based on some Googling that has a starting price of less than $35K.
Moore's Law is our friend. But its economics is not the friend of custom CPUs in competition with commodity ones.
Deleted comment
So to answer your question, nothing (in this context), because the Turing machine is a more useful model for thinking about computation itself.
Perhaps the same might apply to lisp / lambda calculus, although I suspect the answer here is that it's just a lot harder to right a self-interpreter in lambda calc.
Here's one for the http://en.wikipedia.org/wiki/Binary_lambda_calculus, all of 29 bytes long, including parsing:
0101000110100000000101011000000000011110000101111110011110
0001011100111100000011110000101101101110011111000011111000
0101111010011101001011001110000110110000101111100001111100
0011100110111101111100111101110110000110010001101000011010This isn't obvious to me. It seems to me that a TM is more useful for thinking about computation from an operational perspective. But this isn't the only, or arguably even the most effective, way to think about computation. The lambda calculus is much more useful for thinking about computation from a denotational perspective.
I do not see any low-level I/O routines, or a reader to scan expressions and convert them into objects.
I don't see the actual function call mechanism: where the subroutine linkage is set up and torn down, and what goes into what register.
I don't see a garbage collector.
A whole bunch of hand-written assembly language made the code on that page work.
LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies.
The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS.
Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense.
Lisp implementations that run well on, and take advantage of, architectures with caches, branch prediction and complex memory hierarchies are well-known, and have been well-known for, literally, decades. http://pt.withy.org/publications/VLM.html is an example from 1994. More importantly though, even the earlier Lisp machines (at least since 1983!) implemented a form of instruction caching, and had hardware-aided garbage collection.
> The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS. Conceptually it is really clean, but about the only application it makes sense for is first order theorem proving, or in languages that support pattern matching. If you actually want to use lists as lists something like the Java ArrayList makes more sense.
The car/cdr list is not the only data structure in Common Lisp.
[1] http://academia.stackexchange.com/a/1352 [2] http://pt.withy.org/
[1] The extended abstract itself mentioned " The full paper also discusses other aspects...".
(Yes, it's not the world's fastest.)
It might perform like a dog, but that is another matter.
You mean like in the 80s with very little RAM, larger virtual memory to very slow disks, paging files of networks, booted images from network servers over 10Mbit links, ...
A time when commercial Lisp did a lot to be memory efficient (like cdr coding of Lisps, compacting GCs, incremental GCs, ephemeral GCs, generational GCs, ...).
> The car/cdr list is just about the worst way to represent lists in terms of performance on modern CPUS.
Actually modern CPUs are really fast with these list operations. For a lot of operations linked lists are fully sufficient.
You might also want to note that Lisp has data structures like vectors, multi-dimensional arrays, records, instances of Classes, hash tables and all kinds of fancy stuff, including access to 'foreign' memory which is accessible with pointers and manual memory management.
Currently optimized Lisp code is as fast as F#, OCaml, Java, Haskell or similar...
Yeah, let's just forget about decades of Lisp development since.
>something like the Java ArrayList makes more sense.
Except you lose the most important detail of Lisp pairs: persistence.
Just about every language that promises an advance in parallelism (other than solidly "worse is better" approaches such as Hadoop and Pig) is selling some kind of snake oil, and immutability is one of the worst of them.
Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. With modern memory hierarchies a lot revolves around never letting two threads touch the same cache line and this happens at all you lose at least an order of magnitude in performance. Garbage collection involves global properties of the system, so there will always be some "stop the world" element of GC, so GC itself becomes a scaling bottleneck when you allocate lots of memory and throw it all behind your rear.
I'll take correctness over raw performance any day.
http://web.nvd.nist.gov/view/vuln/search-results?query=&sear...
Scare quotes because "anyone" can program up a Lisp "in a week". High performance LISPs not surprisingly require very roughly the same amount of effort as any other high performance language implementation. Lisp got its first compiler in 1962, 4 years after its launch (and it was the first self-hosting compiler, i.e. written in itself). As the inventor of garbage collection, it's long been a major driver of innovations in GC (although of course much less so now that Java etc. gave GCed languages mainstream cred).
But by and large, except for strictness of dynamic type checking (often a tunable variable), sacrificing correctness for speed has never been part of Lisp's DNA.
As you might imagine by my post history I had a specific language in mind.
Funny that you mention FORTRAN, as it reminds me of a systems programming language used for writing several OS, about the same age as FORTRAN and Lisp, namely Algol and its variants.
When they questioned their customers if Algol compilers should support disabling bounds checking, they said no responsible engineer would ever need it. As described by Hoare on his Turing award.
While this is ... tolerable, I seriously wonder what other corners are being cut, e.g. in the unreleased privileged ISA.
(A bit more background: RISC-V is intended to be a open core for everything, so making the base processor simple for education is good, but promoting it as a CPU for industry is in the direction of bad, IMHO.)
Wrong. Immutability can (and often does) increase scalability. It does that mainly by making this situation harmless:
> With modern memory hierarchies a lot revolves around never letting two threads touch the same cache line and this happens at all you lose at least an order of magnitude in performance.
https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#...
Don't blame the language for lack of programmer knowledge.
If you learn anything about binary search you should learn to avoid it. Even computer science books have a wrong implementation of it more than 50% of the time and, that, together with all the algorithms based on total ordering, tends to blind people to the fascinating world of algorithms that are based on partial orderings. 99% of the time you are better off using the hashtables that come with your language than you are to look into a "data structures and algorithms" book we're you'll probably pick something that performs worse and you'll screw up the implementation of.
(I recently wasted a few days coding up something that was "kinda like" binary search, but the analogy with binary search led me to think about it the wrong way.)
Today people still read the stuff on Random Number generators from Knuth, which was obsolete by 1985. It's very likely that the rand() function in your language comes out of Knuth, even though his stuff was completely superceded but what was in Numerical Recipes (Knuth never did scientiic computing) and the stuff in NR was obsolete by 1990.
They're removing rand() from the C++ standard library because they can't burn all the copies of Knuth fast enough to stop standard library implementers from reimplementing all the bad algorithms.
is date of post also considered?
If that is lisp, then a byte code interpreter loop is every interpreted language: read_opcode, inc_pc, call a function indexed from a list indexed by opcode. It can be written in one line of C. This BTW translates to hardware a lot easier than the half page of Lisp. That one line of code by itself is also just as useless as the half page of Lisp.
It's still interesting, but people need to stop claiming it's Lisp defined in this tiny little block of code.