I admit that I don't completely understand Lisp's claim to fame. Yes, programs in the language are represented by a built-in data type, and you can write a self-interpreter quite easily. But the same is true for a simple assembly language, if you know the instruction encoding! You can represent a program as a code pointer, and it's easy to write an analog of "eval" by hand, using just a handful of arithmetic instructions and conditional jumps. What's more, such an "eval" won't even depend on a garbage collector or other niceties that Lisp self-interpreters take for granted.
The "claim to fame" has more to do with homoiconicity, ie. that the language is its own syntax tree. This allows you to extend the language in arbitrarily complex ways in the language itself - a consequence of this is the simplicity of writing a self-interpreter.
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.).
Where this argument loses me is that I have yet to see a single Lisp person going around extolling the virtues of Prolog, a language that is also homoiconic and has macros.
(If Lisp people want to start doing that though, I'd be happy. Prolog is great.)
A lot of Lispers are interested in logic programming, if not Prolog. It's in SICP, it's the topic of The Reasoned Schemer (www.amazon.com/Reasoned-Schemer-Daniel-P-Friedman/dp/0262562146/), Shen includes a Prolog and you can use its syntax: http://www.shenlanguage.org/learn-shen/prolog.html
So you'll have to modify your statement at minimum to "a single person other than Mark Tarver" ^_^.
Well I would, I often mention logic programming in the same list as functional. However, lisp is simply awesome/powerful/etc. while logic and more formal-abstract kinds of programming (from Prolog to Haskell) are "difficultly" awesome.
Lisp gets a great deal of undue credit as being some kind of timeless enlightened wisdom, which I see as ignorant of the history of the language's development.
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.
Exactly the same is true of Maxwell's equations. The four we use today are different than the 20 he originally came up with; most of that reduction comes from vectorizing them, and they gain a lot of clarity by using vector-calculus operations such as gradient and curl.
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".
No language that is developed is perfect on release. The timeless wisdom of Lisp, as you call it, rest largely on macros and lambdas. Those ideas are powerful in their ability to allow you to build abstractions and customize the language to your needs. Basically, Lisp allowed for DSLs before the concept of a DSL was even recognized.
Pythagoras did not discover the theorem, it's just named after him. He may have been the first to record a proof of it. It's conceivable that the very first peoples to become seriously interested in geometrical calculation would have discovered it as a matter of course. It does meet the definition of timelessness whereas Lisp does not.
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."
... which is irrelevant. The point posed was that the ephemeral form heralds the so-called 'revolutionary' concepts, and stating that a prolonged delivery of the concepts invalidates their usefulness is the result of an overly literal interpretation of a common phrase.
I'm not sure what you're talking about here. The latest language in Lisp family is Clojure and it came out in 2007. The syntax that it uses is quite a bit different from Lisps from 30 years go.
I wouldn't call it quite a bit different. Really just seems to have a few small changes where they prefer [] over (). Otherwise just a different set of standard macros.
Clojure is not that different, but besides that, parent implied changes from Lisp circa '60s that were already in CommonLisp and Scheme 30 years ago...
Not redesign, but recycle old ideas. It might change in details, but as far as I've thus far observed, IT operates in cycles. The terminal + mainframe -> the personal computer -> the cloud (personal mainframe) -> ?
Some of the "old Lisp things" are becoming new again.
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...
It's the opposite side of the computing spectrum. Many languages aimed at using machines, Lisp was an ideal to express computability. As other said, yeah the eval definition hides away GC, IO and the read function, which fits my interpretation (sic) of lisp as an abstraction abstraction. They weren't interested much in the machine details, this itself is already a fun fact.
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.
There's a spectrum of near vs. far from the machine, but there's no spectrum of computability, all Turing complete languages are equally Turing complete. There's no difference between Lisp and assembly in this regard. In fact if you take into account the big-O time complexity, then assembly is better than the version of Lisp described in the OP, because the latter suffers a logarithmic penalty due to immutability.
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!
It's true that Turing complete languages are (almost by definition) equivalent for writing programs of type "Nat -> Nat". However, things are not so simple at other types and it turns out there is actually something of a spectrum of computability. Andrej Bauer has a nice post on such things here: http://math.andrej.com/2011/07/27/definability-and-extension...
Please correct me if I'm wrong, since this is very much not my field, but as I understand it, there are at least 4-5 mathematically equivalent fundamental models of computation, and in practice the Turning machine and the lambda calculus (developed by Turing's thesis adviser ... I gather that was a small world back then) are useful.
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).
Yeah, you understand correctly. The thing is, I don't know any mathematical insight that singles out lambda calculus as a basis for computation among other possible bases, or any mathematical insight that singles out Lisp as an approach to writing self-interpreters. In other words, there's no theorem saying Lisp lies at the extreme end of any spectrum.
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.
I saw that bit about McCarthy too. I wonder if his point was that while you can do functional programming in lisp, you can do a lot of other non-functional-programming stuff too, and so in that sense he didn't see Lisp as an implementation of lambda calculus.
According to D. Gabriel, the imperative forms were added later to seduce scientists used to FORTRAN algorithms. But Steele's interview of McCarthy makes it clear that Lisp is more a natural accident turning into compressed carbon than the implementation of an apriori concept.
That seems like a huge disadvantage to me. The bottle neck in any software project (> 1 person) 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.
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™.
> That seems like a huge disadvantage to me. The bottle neck in any software project (> 1 person)
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.
The thing is when you know lisp (or scheme) you understand programming languages much more fundamentally than you would otherwise and so jumping from one programming language to another becomes much easier. (BTW, I hated Scheme in school, but I have since seen the light thanks to SICP.) Overall, I agree with the theme of this sub-thread that non-idiomatic code in any language is a real pain in the ass. I see this everyday when I look at code written by scientists who are smart, driven, motivated people and therein lies the problem.
>With that in mind, I would not want to learn a new language for every project I was a part of
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?"
It depends on the complexity of the new language, doesn't it? If these new languages are highly domain-specific DSL's for complex domains, then the entire software package might be more understandable overall.
It's not so much a huge disadvantage as a huge trade-off.
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.
I think there are multiple factors to Lisp's claim to fame, and other have covered a few of them. But one thing to also keep in mind is the historical context. Lisp had features like garbage collection and much more of a "batteries included" standard library. It was a much higher level language, and more safe to use (memory safe, fewer incidence of off-by-one errors, etc.) compared to most other contemporary languages in the 70s and 80s (C for instance). You might still see a lot of Lisp advocacy aimed at wooing you away from those languages by touting the virtues of bignums/rationals, garbage collection, anonymous functions/closures, etc.. By the time the late 90s and 2000s rolled around pretty much of all of the popular languages had incorporated high-level features pioneered by lisp, and so now-a-days lisp doesn't probably seem quite as attractive to python or ruby or javascript or C# or Haskell users. Also, I think there may just be some personal preferences involved in different language choices. If you like C, and think it is a great language, then I'd say there is a lower probability that you'd like lisp, because they have a different philosophy about how programs could be built.
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.
ADDED: the author of the deleted post I'm responding to thought that he remembered that the Scheme 79 chip failed to actually run Lisp (Scheme). I replied:
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.
Lisp's eval/apply is so short and dense that it can fit on a chalkboard. Its also easy experiment with language design by making slight changes to the intrepeter.
This is very close to the idea explored by Forth. It has just a simple engine that compiles pieces of code on the fly. No need for garbage collection or any complicated macros.
Perhaps, but when you add alternates like Algol and PL/1 (1964) that case becomes a lot weaker. (Although I don't really know Algol and only know PL/1 as of IBM's late '70s version.) The weaknesses of COBOL were widely realized (and in it's niches it's not hardly so bad, or so I say from one week of using it).
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.
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.
I understand why Alan Kay said what he did, but a closer analogy would be to Euclid's Elements. If one follow's Lisps axioms, one ends up with Lispian Computation, elegant, clean, tail-call optimized.
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 rather partial to the differential form version. Something about the neat almost symmetry (in the layman's sense) of the two equations. And how deceptively innocent looking they are.
I just noticed this was authored by Michael Nielsen... co-author of the text on quantum computation, and now a huge open-academia advocate. And he's open-sourced the micro-lisp he wrote in this article: https://github.com/mnielsen
There is at least one current project - Mezzano -that boots a Common Lisp and some apps on bare metal.
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.
One of the biggest issues is that a FPGA design running at 50-100 MHz (compare to the contemporaneous Cray-1 80MHz), with little memory that can be used as cache, gets blown out of the water by a +3GHz CPU with megabytes of on die cache. In terms of just being a "Lisp Machine", it only makes sense as retro-computing. Even a CADR, 3600 etc. simulator running on a fast x86-64 CPU would be (a lot) faster.
Aren't we loosing the focus by looking at the Lisp Machines only from "HW" point of view? They were "ported" on Alpha, and I can run them today on a x86-64 VM.
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?
Well, we do have a rather early fully legal 1981 copy of the system, and one or more illicit but no one seems to care copies of much later Symbolics systems (don't know if those included source, though). So that in part an issue of software archaeology, when we can also ask most if not all of the people involved about details.
And I fully agree the focus should be on the software, as I hope I made clear in other comments in this topic.
What do they cost in single unit quantities, or rather, what does a development board that I can stick GiBs of hopefully ECC DRAM cost? And the development tools?
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 wayway 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?
I'm not saying it is economically competitive. (It is possible pay over $25k for a really high end FPGA) And if you are just synthesizing a general purpose synchronous CPU you definitely not going to get a lot of bang-for-the-buck, because you are going against the grain of what an FPGA can provide. In that instance you're just vetting your design until you convert it over to a mask-programmable "equivalent", or do a full-custom design. The interesting things about an FPGA would be to use its inherent parallelism, fine grain programmability, and the reprogramability to run circles around something constrained by a von Neumann bottleneck in the cache hierarchy.
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."
...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.
I've been thinking hard about this lately, and the first question for me is "What would a 21st Century Lisp Machine mean?"
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.
Well, there's the first Connection Machine architecture, very roughly contemporaneous with Lisp Machines (I had to regretfully tell my friend Danny Hillis that LMI wouldn't be able to provide Lisp Machines for Thinking Machines Corporation in time (which had to be formed because the project needed 1-2 analog engineers, which MIT was structurally unable to pay, no one gets paid more than a professor). He was really, legitimately pissed off by what Symbolics did with Macsyma, a sleazy licensing deal to keep it out of everyone else's hands (and they tried to get everyone in the world who'd gotten a copy of it to relinquish it). Later neglected, even when it became the Symbolics cash cow.)
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.
I've been wondering about it since like every other programmer I hit that time when I'm really looking at programming languages and VMs (in the "what would I design" sense). Looking to Lisp Machines to see what they were about leads me to the question: would concentrating on hardware memory management / garbage collection be a starting point to answer your question?
One indication is that Azul, after 3 generations of ccNUMA systems with zillions of custom chips and a memory infrastructure that gives each one "mediocre" access speed to all the system's memory for running Java with gonzo GC ("generic" 64 bit RISC chips with things like a custom read barrier instruction), has given up and is doing their thing on x86-64 systems with their Zing product, albeit at least initially with tricks like kernel extensions to do bulk MMU operations before a single TLB invalidation. Look up their papers on the Pauseless and C4 GCs. The former was done in time to make it into the 2nd edition of sorts of the book on GC: http://www.amazon.com/Garbage-Collection-Handbook-Management...
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.
There's nothing inherently unnatural about taking a bottom up approach to solving problems. Sometimes, knowing you're going to need a particular tool and doing that first makes sense. I think of it like the cooking technique Mise en place [1], where you lay out all the ingredients before you start cooking. Neither bottom up, nor top down, is always the most natural way to attack a problem. Sometimes you can attack a problem from both sides at once.
What does Lisp provide on top of e.g. the lambda calculus? I'd expect the latter to be even more fundamental. But I suppose one could reasonably argue that that wasn't 'Software', just Math.
I think you've missed the point of OPs question - he's not trying to argue that lisp isn't useful over Lambda Calculus from a practical perspective, but asking how both relate to the "fundamentals of computing" perspective.
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.
> So to answer your question, nothing (in this context), because the Turing machine is a more useful model for thinking about computation itself.
This 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 agree completely, and didn't mean to compare the Turing machine to Lambda calculus, only to the C language (it made more sense before the context above was deleted).
surely this is actually that a short lisp compiler or interpreter is the maxwell's equations. the analogy is way off the mark for software as a discipline in total. you can know nothing about lisp and understand pretty much everything... thats not true of classical electromagnetism and maxwell's equations
for what it is worth, here is a version of a lisp interpreter I wrote in python:
https://github.com/keithgabryelski/plisp
I used _Interpreting_LISP_ by Gary D. Knott as a guide.
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.
An extended abstract is basically just a short paper, and not usually the abstract to anything [1]. So that might be everything the authors wrote on the topic. It's reasonable to assume that any full paper by P.T. Withington would be posted on his personal site[2] alongside the abstract.
Interesting. Thanks for pointing out that the abstract mentions "the full paper." It is possible though that the paper was never completed / published: note that though this abstract was "Submitted to PLDI '94," it doesn't appear in the proceedings for that event [1]. If the abstract was rejected the authors may have never finished the paper.
The car/cdr list is the only data structure described in cute metacircular interpreters, and even then only when supported by a substantial amount of implied runtime code.
> LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies.
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...
And in practice, compromise is possible. E.g. Clojure's vectors which are unashamedly LISP-like to work with, but still avoid much of the pointer-chasing of a linked list.
Yes, there are various implementations of persistent vector-like lists, Clojure's being one of them. They are extremely useful, however, they are far more complex than a cons cell. Most of the time, I want simple cons cells.
Persistence has some good properties, particularly if you are writing compilers.
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.
Although the funny thing is, as the 2nd oldest surviving computer language after FORTRAN, and at least back then used for very difficult problems, to be competitive let alone justifiable on extremely scarce and expensive hardware, "Lisp" has always been "obsessed" with performance. ADDED along with a bit before: It first ran on the IBM 704, a vacuum tube computer. It was derived from the IBM 701, which initially used Williams tubes for memory (https://en.wikipedia.org/wiki/Williams_tube).
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.
Yes, but there are many ways to be obsessed with performance while keeping correctness.
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.
To indicate how far we've come from that, my biggest concern with the lowRISC project I mention elsewhere is that it's a RISC-V project, and in a very New Jersey way, that CPU has no provision for integer math errors other than divide by zero. Also makes the large integer cryptographic crowd rather upset.
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.)
> Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput.
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.
Retrocomputing (such as the Cult of Knuth) seeds programmers with obsolete knowledge which displaces useful 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.
I hate that. The half page of code is not Lisp. Not even close, and I'm not talking about a standard library. There is no parser in there. Eval is operating on Lisp data, not lisp source code. There is no support for efficient math, or strings, or anything really.
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.
