11 ms·

Lisp as the Maxwell Equations of Software (2012)

196 points by jgrodziski 12y ago

charlieflowers 12y ago
Shouldn't [2012] be appended to the title? I've seen the article discussed on HN before. [1] [1] https://news.ycombinator.com/item?id=3830867 https://news.ycombinator.com/item?id=3830867
- falcolas 12y ago
  Meta: does the date really matter, when we're discussing concepts and theory which change infrequently, if at all?
  - PaulHoule 12y ago
    Things change. 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.
    - davexunit 12y ago
      >LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. 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.
      - dasmoth 12y ago
        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.
        davexunit 12y ago
        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.
        gsg 12y ago
        There are schemes to "unroll" conses, too. CDR-coding, Appel's paper (although IIRC that requires immutable conses), etc.
      - PaulHoule 12y ago
        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.
        davexunit 12y ago
        >Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. I'll take correctness over raw performance any day.
        pjmlp 12y ago
        I am with you, specially since we all know where languages obsessed with performance over correctness lead to. http://web.nvd.nist.gov/view/vuln/search-results?query=&search_type=all&cves=on http://web.nvd.nist.gov/view/vuln/search-results?query=&sear...
        hga 12y ago
        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 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.
    - lispm 12y ago
      > 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...
    - weland 12y ago
      That's... basically not even wrong. 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 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.
      - RodgerTheGreat 12y ago
        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.
        pjmlp 12y ago
        This doesn't look like a substantial runtime code. http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
        RodgerTheGreat 12y ago
        That doesn't look like sufficient runtime code. That paper quite explicitly avoids implementing a garbage collector, among other things.
        pjmlp 12y ago
        A simple reference counted implementation with cycle collector is not a big deal to implement, nor a substantial effort. It might perform like a dog, but that is another matter.
    - pjmlp 12y ago
      Although it is called List Processing, it does support other types of data structures, including arrays. https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#SECTION002110000000000000000 https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#... Don't blame the language for lack of programmer knowledge.
      - PaulHoule 12y ago
        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.
- _lce0 12y ago
  I thought HN wont allow to re-post the exact same url, so to bypass people add noise to the url. is date of post also considered?
  - phowat 12y ago
    Yes, after some time has passed, HN will allow the same link to be resubmitted.
  - andyjohnson0 12y ago
    As far as I know, re-posts are allowed after some period of time has elapsed. I don't think this is documented anywhere though.
    - samatman 12y ago
      I've always figured the URLS just fall off a queue, so there's no absolute period of time involved. No actual knowledge, just a guess.
      - _lce0 12y ago
        sweet, so we could attempt to find out the queue size!!
cousin_it 12y ago
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.
- RodgerTheGreat 12y ago
  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.
  - coldtea 12y ago
    >Modern Lisps are substantially different in syntax and semantics from these earliest ideas; we're just still calling them Lisp. An interesting take on "modern", meaning "the last 3 decades or so", which is like millenia in the IT industry...
    - TeMPOraL 12y ago
      I understand that by "IT industry" you mean the Web, which is the industry's equivalent of a fashion show. Work clothes, suits and hazmat wear also don't change their design every three months.
quarterwave 12y ago
Any chance of a resurgence in Lisp machines? Especially in view of the changes in CPU architecture due to semiconductor scaling challenges.
- copsarebastards 12y ago
  What's stopping you from making it happen? 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.
  - hga 12y ago
    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. See more in my longer comment in this subthread.
    - GregBuchholz 12y ago
      Modern high-end FPGAs can have upwards of 5-10 megabytes of on die memory: http://www.xilinx.com/products/silicon-devices/fpga/virtex-ultrascale.html http://www.xilinx.com/products/silicon-devices/fpga/virtex-u... http://www.altera.com/devices/fpga/stratix-fpgas/stratix-v/overview/stxv-overview.html http://www.altera.com/devices/fpga/stratix-fpgas/stratix-v/o...
      - hga 12y ago
        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 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?
jgrodziski 12y ago
Hi, Submitter here, I stumble upon that article from my bookmarks while pouring my latest side project (http://www.learn-computing-directory.org/languages-and-programming/compilers-fundamentals.html 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 http://norvig.com/lispy.html and http://norvig.com/lispy2.html http://norvig.com/lispy2.html Also, the book "Understanding Computation" (http://computationbook.com/ http://computationbook.com/) can be a great companion as there is a section about Lambda Calculus. Jérémie.
nabla9 12y ago
While this is nice academic view. As a Lisp programmer, the Power of Lisp comes from being big ball of mud, see: https://en.wikipedia.org/wiki/Big_ball_of_mud#In_programming_languages https://en.wikipedia.org/wiki/Big_ball_of_mud#In_programming.... 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.
GFK_of_xmaspast 12y ago
Disagree with premise, Maxwell's equations are useful in practice.
samatman 12y ago
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.
- abecedarius 12y ago
  Maxwell's equations in the usual Heaviside form aren't even the most elegant way to write them: http://www.av8n.com/physics/maxwell-ga.htm http://www.av8n.com/physics/maxwell-ga.htm I'm curious how people might carry that through the analogy.
  - jheriko 12y ago
    Einstein tensor notation is amazing. :)
  - MeadowTheory 12y ago
    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.
phkahler 12y ago
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.
- deleted 12y ago
  [deleted]
unoti 12y ago
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. http://en.m.wikipedia.org/wiki/Mise_en_place http://en.m.wikipedia.org/wiki/Mise_en_place
gobengo 12y ago
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.
- deleted 12y ago
  [deleted]
  - one-more-minute 12y ago
    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.
    - acomar 12y ago
      > 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.
      - one-more-minute 12y ago
        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).
    - tromp 12y ago
      > 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 http://en.wikipedia.org/wiki/Binary_lambda_calculus, all of 29 bytes long, including parsing: 0101000110100000000101011000000000011110000101111110011110 0001011100111100000011110000101101101110011111000011111000 0101111010011101001011001110000110110000101111100001111100 0011100110111101111100111101110110000110010001101000011010
adamgravitis 12y ago
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 https://github.com/mnielsen
keithgabryelski 12y ago
for what it is worth, here is a version of a lisp interpreter I wrote in python: https://github.com/keithgabryelski/plisp https://github.com/keithgabryelski/plisp I used _Interpreting_LISP_ by Gary D. Knott as a guide.
- lisper 12y ago
  Lisp in Python in 137 LOC: http://www.flownet.com/ron/l.py http://www.flownet.com/ron/l.py
  - keithgabryelski 12y ago
    not really, but it is interesting.
keithgabryelski 12y ago
for what it is worth, here is a version of a lisp interpreter I wrote in python: https://github.com/keithgabryelski/plisp https://github.com/keithgabryelski/plisp I used _Interpreting_LISP_ by Gary D. Knott as a guide.
jheriko 12y ago
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
- one-more-minute 12y ago
  Not necessarily. You learn a ton about electromagnetism before you ever get to Maxwell's equations.
  - MeadowTheory 12y ago
    Faraday sure did.
  - MeadowTheory 12y ago
    Faraday sure did.
mvc 12y ago
If you're near Boston/Cambridge, the Clojure Meetup Group is showing a live video of William Byrd talking about this tonight. http://www.meetup.com/Boston-Clojure-Group/events/218650142/ http://www.meetup.com/Boston-Clojure-Group/events/218650142/
kazinator 12y ago
That half a page of code isn't "Lisp in itself". 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.

196 points by jgrodziski 12y ago

Shouldn't [2012] be appended to the title? I've seen the article discussed on HN before. [1] [1] https://news.ycombinator.com/item?id=3830867 https://news.ycombinator.com/item?id=3830867

falcolas 12y ago
Meta: does the date really matter, when we're discussing concepts and theory which change infrequently, if at all?
- PaulHoule 12y ago
  Things change. 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.
  - davexunit 12y ago
    >LISP was popular in the 1980s before caches, branch prediction, and complex memory hierarchies. 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.
    - dasmoth 12y ago
      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.
      - davexunit 12y ago
        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.
        gsg 12y ago
        There are schemes to "unroll" conses, too. CDR-coding, Appel's paper (although IIRC that requires immutable conses), etc.
    - PaulHoule 12y ago
      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.
      - davexunit 12y ago
        >Immutability has benefits in terms of correctness, but not in terms of scalability to more processors or total throughput. I'll take correctness over raw performance any day.
        pjmlp 12y ago
        I am with you, specially since we all know where languages obsessed with performance over correctness lead to. http://web.nvd.nist.gov/view/vuln/search-results?query=&search_type=all&cves=on http://web.nvd.nist.gov/view/vuln/search-results?query=&sear...
        hga 12y ago
        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 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.
  - lispm 12y ago
    > 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...
  - weland 12y ago
    That's... basically not even wrong. 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 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.
    - RodgerTheGreat 12y ago
      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.
      - pjmlp 12y ago
        This doesn't look like a substantial runtime code. http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
        RodgerTheGreat 12y ago
        That doesn't look like sufficient runtime code. That paper quite explicitly avoids implementing a garbage collector, among other things.
        pjmlp 12y ago
        A simple reference counted implementation with cycle collector is not a big deal to implement, nor a substantial effort. It might perform like a dog, but that is another matter.
  - pjmlp 12y ago
    Although it is called List Processing, it does support other types of data structures, including arrays. https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#SECTION002110000000000000000 https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node158.html#... Don't blame the language for lack of programmer knowledge.
    - PaulHoule 12y ago
      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.
_lce0 12y ago
I thought HN wont allow to re-post the exact same url, so to bypass people add noise to the url. is date of post also considered?
- phowat 12y ago
  Yes, after some time has passed, HN will allow the same link to be resubmitted.
- andyjohnson0 12y ago
  As far as I know, re-posts are allowed after some period of time has elapsed. I don't think this is documented anywhere though.
  - samatman 12y ago
    I've always figured the URLS just fall off a queue, so there's no absolute period of time involved. No actual knowledge, just a guess.
    - _lce0 12y ago
      sweet, so we could attempt to find out the queue size!!

cousin_it 12y ago

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.

RodgerTheGreat 12y ago
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.
- coldtea 12y ago
  >Modern Lisps are substantially different in syntax and semantics from these earliest ideas; we're just still calling them Lisp. An interesting take on "modern", meaning "the last 3 decades or so", which is like millenia in the IT industry...
  - TeMPOraL 12y ago
    I understand that by "IT industry" you mean the Web, which is the industry's equivalent of a fashion show. Work clothes, suits and hazmat wear also don't change their design every three months.

quarterwave 12y ago

Any chance of a resurgence in Lisp machines? Especially in view of the changes in CPU architecture due to semiconductor scaling challenges.

copsarebastards 12y ago
What's stopping you from making it happen? 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.
- hga 12y ago
  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. See more in my longer comment in this subthread.
  - GregBuchholz 12y ago
    Modern high-end FPGAs can have upwards of 5-10 megabytes of on die memory: http://www.xilinx.com/products/silicon-devices/fpga/virtex-ultrascale.html http://www.xilinx.com/products/silicon-devices/fpga/virtex-u... http://www.altera.com/devices/fpga/stratix-fpgas/stratix-v/overview/stxv-overview.html http://www.altera.com/devices/fpga/stratix-fpgas/stratix-v/o...
    - hga 12y ago
      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 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?

jgrodziski 12y ago

Hi, Submitter here, I stumble upon that article from my bookmarks while pouring my latest side project (http://www.learn-computing-directory.org/languages-and-programming/compilers-fundamentals.html 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 http://norvig.com/lispy.html and http://norvig.com/lispy2.html http://norvig.com/lispy2.html Also, the book "Understanding Computation" (http://computationbook.com/ http://computationbook.com/) can be a great companion as there is a section about Lambda Calculus. Jérémie.

nabla9 12y ago

While this is nice academic view. As a Lisp programmer, the Power of Lisp comes from being big ball of mud, see: https://en.wikipedia.org/wiki/Big_ball_of_mud#In_programming_languages https://en.wikipedia.org/wiki/Big_ball_of_mud#In_programming.... 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.

GFK_of_xmaspast 12y ago

Disagree with premise, Maxwell's equations are useful in practice.

samatman 12y ago

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.

abecedarius 12y ago
Maxwell's equations in the usual Heaviside form aren't even the most elegant way to write them: http://www.av8n.com/physics/maxwell-ga.htm http://www.av8n.com/physics/maxwell-ga.htm I'm curious how people might carry that through the analogy.
- jheriko 12y ago
  Einstein tensor notation is amazing. :)
- MeadowTheory 12y ago
  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.

phkahler 12y ago

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.

deleted 12y ago
[deleted]

unoti 12y ago

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. http://en.m.wikipedia.org/wiki/Mise_en_place http://en.m.wikipedia.org/wiki/Mise_en_place

gobengo 12y ago

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.

deleted 12y ago
[deleted]
- one-more-minute 12y ago
  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.
  - acomar 12y ago
    > 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.
    - one-more-minute 12y ago
      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).
  - tromp 12y ago
    > 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 http://en.wikipedia.org/wiki/Binary_lambda_calculus, all of 29 bytes long, including parsing: 0101000110100000000101011000000000011110000101111110011110 0001011100111100000011110000101101101110011111000011111000 0101111010011101001011001110000110110000101111100001111100 0011100110111101111100111101110110000110010001101000011010

adamgravitis 12y ago

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 https://github.com/mnielsen

keithgabryelski 12y ago

for what it is worth, here is a version of a lisp interpreter I wrote in python: https://github.com/keithgabryelski/plisp https://github.com/keithgabryelski/plisp I used _Interpreting_LISP_ by Gary D. Knott as a guide.

lisper 12y ago
Lisp in Python in 137 LOC: http://www.flownet.com/ron/l.py http://www.flownet.com/ron/l.py
- keithgabryelski 12y ago
  not really, but it is interesting.

keithgabryelski 12y ago

jheriko 12y ago

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

one-more-minute 12y ago
Not necessarily. You learn a ton about electromagnetism before you ever get to Maxwell's equations.
- MeadowTheory 12y ago
  Faraday sure did.
- MeadowTheory 12y ago
  Faraday sure did.

mvc 12y ago

If you're near Boston/Cambridge, the Clojure Meetup Group is showing a live video of William Byrd talking about this tonight. http://www.meetup.com/Boston-Clojure-Group/events/218650142/ http://www.meetup.com/Boston-Clojure-Group/events/218650142/

kazinator 12y ago

That half a page of code isn't "Lisp in itself". 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.