5 ms·

This great idea of Lisp (the simple syntax of function calls in round brackets) isn't much different than a good macro assembler even back in the 1960's. The on

This great idea of Lisp (the simple syntax of function calls in round brackets) isn't much different than a good macro assembler even back in the 1960's. The only major difference was that more than 1 function could be defined in 1 source code line. (I think that machine code is nothing but a sequence of function calls where the function is the logic encoded in the CPU itself for each opcode.) Is it fair to compare the complexity of expression evaluation etc (Fortran) with a macro assembler? Obviously any program can be coded in a macro assembler and therefore that would also be true from a syntax like Lisp. When I was in my 20's, I programmed at least 100,000 lines of Z80 assembler for the first micro computers. One project was at least 40,000 lines and so I know how difficult it is to program larger assembler programs. The biggest problem is that it is hard to see the structure of the loops and conditionals that we normally indent in higher level languages. (You can indent a Lisp program in any way but the language doesn't require any at all.) It is also difficult to recognize expressions. Both of these problems are also there in Lisp (unlike most other high level languages). One last point about the linked list structure at the heart of Lisp. Linked lists are poorly executed in modern computers that rely heavily on locality of data, to optimize the L1 cache. Lisp was very easy on the compiler/interpreter writer but wasn't very good at optimizing the readability of the code for the programmer. (I don't want a religious war but I will point out that most programmers have never programmed in Lisp even though it was one of the first computer languages created.) Before I get a lot of dissing comments, I think with practice, some programmers developed an eye for the lack of structural clues and made some reasonable size code. You could say the same about some programmers making quite good large scale programs in assembler but that doesn't mean that writing in assembler or Lisp should be encouraged.

deleted 10y ago
[deleted]
smitherfield 10y ago
Agreed about linked lists; that virtually all functional languages make them the default/literal data structure is IMO a poor practical design choice (no matter how theoretically elegant) and is the primary culprit for their reputation for slowness. And the tendency for functional compile-to-JS langs to emulate linked lists in Javascript and keep them the default data structure is downright laughable.
- DonaldFisk 10y ago
  (Singly linked) lists are a functional data structure. You can manipulate them efficiently without modifying the lists you started with. You can't do that easily with arrays. So if you base your language around arrays, you're better off making it imperative. Lisp predated level 1 caches. I think it's better to design hardware around the software that runs on it (the Burroughs mainframe/Lisp machine approach), than design programming languages around the machines which run them (the C approach). In this case, it means finding a way to make non-local data references more efficient. Lisp's original reputation for slowness predated the use of Level 1 caches, and was because many early implementations ran on interpreters.
  - clarkd99 10y ago
    I can 'efficiently modify the lists you started with' with a dynamic multi-type array and I have cache locality and random access. I have a single data structure with an 8 byte overhead, 2 byte overhead per node that can be used as a tuple array with direct lookup, a single linked list, double linked list, a queue, a stack, and a balanced binary search tree. This whole structure is allocated in a single contiguous memory chunk and is cache friendly. It can be serialized and un-serialized without any processing which would be required by a Lisp style linked list even if the list was just moved in memory, saved/restored to/from disk or transmitted to another computer. Lisp DOES predate level 1 cache but we DO have level 1 cache now and it dwarfs all other optimizations on modern computers. Wouldn't it be nice if the hardware was designed to optimize our languages instead of the other way around but I live in this universe rather than an alternate one. What matters is now, not decades ago.
    - DonaldFisk 10y ago
      I'd be interested to learn more about your language. Is there a web page about it, or a paper? Are you the D Clark who's at UCL? The way things are now can be changed. For most applications users care more about response times than CPU clock rates. Hardware has speeded up by several powers of ten (Moore's law) but software has at the same time slowed down (Wirth's law), resulting in little if any net gain, and that has nothing to do with the use of lists: most applications don't use them.
hindenburg 10y ago
You make some specific claims here that sound a little odd to this LISP and assembly language hacker. Assembly language doesn't provide any datatypes. LISP does. Assembly language doesn't provide any type checking. LISP does. Assembly language doesn't provide automatic storage reclamation. LISP does. Assembly language doesn't provide naming. LISP does. You also make a claim about L1 caches and locality of reference. Every LISP compiler writer, and every LISP garbage collector writer, knows about CDR-coding. We also know about how Cheney copying garbage collectors and their descendants like the Baker incremental collector compact data, precisely for locality of reference. The compiler writer of course is thinking about cache performance and how lines are mapped in particular target architectures. You should probably educate yourself a little more about LISP if you are so interested in it as to make statements in a public forum.
- smitherfield 10y ago
  He was talking about macro assemblers, which often do provide naming and some level of type checking (and pure assembly is arguably at a lower level of abstraction than type systems, with separate instructions and registers for integers, pointers, floating-point etc). I agree it's a somewhat odd comparison. There are of course plenty of obvious and non-obvious ways to optimize linked lists, but even still they have poor performance characteristics, space efficiency and cache locality compared to alternative structures like arrays and even immutable arrays. There's a reason Java, C#, Python etc store strings as immutable arrays; not only do they start from a generally better performance baseline than lists, but they too have well-understood optimization characteristics.
- clarkd99 10y ago
  I was only talking about the 'list of function calls' aspect of assembler and Lisp, not the type system. I agree that Lisp has a type system and assembler doesn't. Forth is another language that also has very simple syntax that approximates the 'list of function calls' style that I would say isn't unlike a macro assembler either. I am writing a new language with built-in garbage collection that I think is quite superior to other languages. I have created a full standard library with almost 1,000 built-in functions and none of my data structures (lists, maps, trees, stacks, indexes, tables etc) contain pointers or linked lists (that use pointers). I sold over 30,000 copies of a language/database system in 1987 so I think your last comment is quite inappropriate. I have know about Lisp since I started CS in University in 1975. Linked lists are horrible data structures when being used as well as when being freed (your garbage collection comment). I use simple dynamic multi-typed arrays instead of linked lists (pointers) and they can be freed in 1 chunk or a bigger version can be freed with a few memory de-allocations. I get full cache locality and improved speed of allocation and de-allocation. I would love to see an incremental GC that can copy all linked lists nodes into contiguous memory automatically. Nice trick if you can do it but that doesn't help you if your linked list doesn't cause a GC.
DonaldFisk 10y ago
Code readability depends mostly on giving variables and functions meaningful names, and function size/number of variables. That applies to all languages. Code layout/indentation is also an issue, but there's a single standard for Lisp, which Emacs is aware of.
- goatlover 10y ago
  It's an issue for all languages which don't force layout/indentation. Why does Lisp gets criticized for parens when the C family has curly braces all over the place?
  - kazinator 10y ago
    Moreover, people write Makefiles for C, containing notation like: $(patsubst %.foo,%.bar,$(foreach blah,$(VAR),\ whatever $(blah))) People who can say with a straight face they find Lisp parentheses confusing have GNU Makefiles full of this crap, well debugged and all.
sbov 10y ago
There's a lot here, but this one jumped out at me: > You can indent a Lisp program in any way but the language doesn't require any at all. Off the top of my head, isn't this true of basically all languages? Except one, and it got a lot of criticism for it (Python).
- goatlover 10y ago
  Haskell and Elm use whitespace as well, but I don't recall if they enforce the indentation.
- clarkd99 10y ago
  After I wrote that statement I started thinking that C programs can be formatted so that they don't read very well also. In C, an 'if' is always an 'if' (unless you use the pre-processor to screw it up) but in Lisp an 'if' could be anything. I do like the idea of Lisp macros where you can run a Lisp program at compile time to generate the code that is then compiled inline. What I should have said was that Lisp has no commands or structure that can't be changed. Some might argue that this is it's strength but I have seen hundreds of samples of Lisp and it looks very confusing. I don't normally program in C# or Java or many other languages but I can normally understand their code. (Lisp and functional languages are the most opaque to me) My language uses a byte code interpreter and that byte code is in polish prefix notation just like Lisp. I wouldn't want to code in my byte code either (even if the byte codes were replaced with keywords instead of the binary code). Polish prefix notation is great for the compiler but not very good for people.
  - sbov 10y ago
    I haven't worked on a program that hijacked the core language functions in the Lisp I use (Clojure). So your concern seems odd to me, especially since you admit you can do the same thing in C. That said, I only use it in my spare time and not for work, so my exposure is limited. Beyond that, your objections seem to be based upon familiarity. I had similar ones before I started using Clojure more often. I think the notation is just fine - it's not much different from imperative languages except they place the parenthesis in a different spot - I think it's more the nesting than the notation, which isn't a common tactic in imperative languages. I still use imperative languages during my day job so I can decipher imperative code easier, but I am much better at deciphering functional code than I used to be.
pg314 10y ago
> One last point about the linked list structure at the heart of Lisp. Linked lists are poorly executed in modern computers that rely heavily on locality of data, to optimize the L1 cache. You could maybe say that linked lists are at the heart of the platonic ideal of Lisp. Naive interpreters might use linked lists in their internal representation. But real implementations of e.g. Common Lisp or Scheme provide a wide array of data structures (multi-dimensional arrays, hash tables, linked lists).
greggman 10y ago
As someone that's also written hundreds of thousands of lines of assembly with macros I don't really see the comparison. Lisp macros are written in lisp itself. You can create complicated data structures, interate over loops, do file io, query databaes, access the network, whatever you want at compile time in lisp where as assembly language macros were never much more complicated than then the C preprocessor. I certaibly did tons of creative things with assembly language macros but they aren't remotely similar to lisp macros. As for perf, 7 very popular and performant games were written in Lisp. Crash Bandicoot 1, 2, 3 as well as Jak and Daxter 1, 2, 3 and Racing.
- clarkd99 10y ago
  I never said that Lisp macros were anything like assembly macros. I was referring to a macro assembly language as a list of opcodes (function calls) and macros. I am quite a fan of Lisp macros which are much more flexible as you can create code at compile time from a Lisp program. I also know that Lisp or assembler can do anything/everything. I don't like polish notation or the lack of structure in Lisp programs. Everything is a function (with only a couple of exceptions).
lispm 10y ago
> This great idea of Lisp (the simple syntax of function calls in round brackets) isn't much different than a good macro assembler even back in the 1960's. Far from it. Recursive functions and symbolic expressions were nothing like assembler back then. > You can indent a Lisp program in any way but the language doesn't require any at all. One can indent it in any way, but practically people use common indentation styles. Lisp also provides formatting&indentation via the pretty printer. CL-USER 48 > '(DEFUN COLLAPSE (L) (COND ((ATOM L) (CONS L NIL)) ((NULL (CDR L)) (COND ((ATOM (CAR L)) L) (T (COLLAPSE (CAR L))))) (T (APPEND (COLLAPSE (CAR L)) (COLLAPSE (CDR L)))))) (DEFUN COLLAPSE (L) (COND ((ATOM L) (CONS L NIL)) ((NULL (CDR L)) (COND ((ATOM (CAR L)) L) (T (COLLAPSE (CAR L))))) (T (APPEND (COLLAPSE (CAR L)) (COLLAPSE (CDR L)))))) > I think with practice, some programmers developed an eye for the lack of structural clues Lisp has a lot of syntax and structural clues, but you just don't know them. You have to learn them, since much of, say, C syntax knowledge does not carry over to Lisp. >and made some reasonable size code. Like the 1 million lines of Lisp code of the Lisp Machine OS? Or the several hundred thousand lines of an editor largely written in Lisp (GNU Emacs)? > Linked lists are poorly executed in modern computers that rely heavily on locality of data Lisp nowadays usually does not execute linked lists, but runs compiled Lisp. Some data is in linked lists, but there are many other data structures not made of linked lists. Still the language runtime is often pointer heavy.

deleted 10y ago

[deleted]

smitherfield 10y ago

Agreed about linked lists; that virtually all functional languages make them the default/literal data structure is IMO a poor practical design choice (no matter how theoretically elegant) and is the primary culprit for their reputation for slowness. And the tendency for functional compile-to-JS langs to emulate linked lists in Javascript and keep them the default data structure is downright laughable.

DonaldFisk 10y ago
(Singly linked) lists are a functional data structure. You can manipulate them efficiently without modifying the lists you started with. You can't do that easily with arrays. So if you base your language around arrays, you're better off making it imperative. Lisp predated level 1 caches. I think it's better to design hardware around the software that runs on it (the Burroughs mainframe/Lisp machine approach), than design programming languages around the machines which run them (the C approach). In this case, it means finding a way to make non-local data references more efficient. Lisp's original reputation for slowness predated the use of Level 1 caches, and was because many early implementations ran on interpreters.
- clarkd99 10y ago
  I can 'efficiently modify the lists you started with' with a dynamic multi-type array and I have cache locality and random access. I have a single data structure with an 8 byte overhead, 2 byte overhead per node that can be used as a tuple array with direct lookup, a single linked list, double linked list, a queue, a stack, and a balanced binary search tree. This whole structure is allocated in a single contiguous memory chunk and is cache friendly. It can be serialized and un-serialized without any processing which would be required by a Lisp style linked list even if the list was just moved in memory, saved/restored to/from disk or transmitted to another computer. Lisp DOES predate level 1 cache but we DO have level 1 cache now and it dwarfs all other optimizations on modern computers. Wouldn't it be nice if the hardware was designed to optimize our languages instead of the other way around but I live in this universe rather than an alternate one. What matters is now, not decades ago.
  - DonaldFisk 10y ago
    I'd be interested to learn more about your language. Is there a web page about it, or a paper? Are you the D Clark who's at UCL? The way things are now can be changed. For most applications users care more about response times than CPU clock rates. Hardware has speeded up by several powers of ten (Moore's law) but software has at the same time slowed down (Wirth's law), resulting in little if any net gain, and that has nothing to do with the use of lists: most applications don't use them.

hindenburg 10y ago

You make some specific claims here that sound a little odd to this LISP and assembly language hacker. Assembly language doesn't provide any datatypes. LISP does. Assembly language doesn't provide any type checking. LISP does. Assembly language doesn't provide automatic storage reclamation. LISP does. Assembly language doesn't provide naming. LISP does. You also make a claim about L1 caches and locality of reference. Every LISP compiler writer, and every LISP garbage collector writer, knows about CDR-coding. We also know about how Cheney copying garbage collectors and their descendants like the Baker incremental collector compact data, precisely for locality of reference. The compiler writer of course is thinking about cache performance and how lines are mapped in particular target architectures. You should probably educate yourself a little more about LISP if you are so interested in it as to make statements in a public forum.

smitherfield 10y ago
He was talking about macro assemblers, which often do provide naming and some level of type checking (and pure assembly is arguably at a lower level of abstraction than type systems, with separate instructions and registers for integers, pointers, floating-point etc). I agree it's a somewhat odd comparison. There are of course plenty of obvious and non-obvious ways to optimize linked lists, but even still they have poor performance characteristics, space efficiency and cache locality compared to alternative structures like arrays and even immutable arrays. There's a reason Java, C#, Python etc store strings as immutable arrays; not only do they start from a generally better performance baseline than lists, but they too have well-understood optimization characteristics.
clarkd99 10y ago
I was only talking about the 'list of function calls' aspect of assembler and Lisp, not the type system. I agree that Lisp has a type system and assembler doesn't. Forth is another language that also has very simple syntax that approximates the 'list of function calls' style that I would say isn't unlike a macro assembler either. I am writing a new language with built-in garbage collection that I think is quite superior to other languages. I have created a full standard library with almost 1,000 built-in functions and none of my data structures (lists, maps, trees, stacks, indexes, tables etc) contain pointers or linked lists (that use pointers). I sold over 30,000 copies of a language/database system in 1987 so I think your last comment is quite inappropriate. I have know about Lisp since I started CS in University in 1975. Linked lists are horrible data structures when being used as well as when being freed (your garbage collection comment). I use simple dynamic multi-typed arrays instead of linked lists (pointers) and they can be freed in 1 chunk or a bigger version can be freed with a few memory de-allocations. I get full cache locality and improved speed of allocation and de-allocation. I would love to see an incremental GC that can copy all linked lists nodes into contiguous memory automatically. Nice trick if you can do it but that doesn't help you if your linked list doesn't cause a GC.

DonaldFisk 10y ago

Code readability depends mostly on giving variables and functions meaningful names, and function size/number of variables. That applies to all languages. Code layout/indentation is also an issue, but there's a single standard for Lisp, which Emacs is aware of.

goatlover 10y ago
It's an issue for all languages which don't force layout/indentation. Why does Lisp gets criticized for parens when the C family has curly braces all over the place?
- kazinator 10y ago
  Moreover, people write Makefiles for C, containing notation like: $(patsubst %.foo,%.bar,$(foreach blah,$(VAR),\ whatever $(blah))) People who can say with a straight face they find Lisp parentheses confusing have GNU Makefiles full of this crap, well debugged and all.

sbov 10y ago

There's a lot here, but this one jumped out at me: > You can indent a Lisp program in any way but the language doesn't require any at all. Off the top of my head, isn't this true of basically all languages? Except one, and it got a lot of criticism for it (Python).

goatlover 10y ago
Haskell and Elm use whitespace as well, but I don't recall if they enforce the indentation.
clarkd99 10y ago
After I wrote that statement I started thinking that C programs can be formatted so that they don't read very well also. In C, an 'if' is always an 'if' (unless you use the pre-processor to screw it up) but in Lisp an 'if' could be anything. I do like the idea of Lisp macros where you can run a Lisp program at compile time to generate the code that is then compiled inline. What I should have said was that Lisp has no commands or structure that can't be changed. Some might argue that this is it's strength but I have seen hundreds of samples of Lisp and it looks very confusing. I don't normally program in C# or Java or many other languages but I can normally understand their code. (Lisp and functional languages are the most opaque to me) My language uses a byte code interpreter and that byte code is in polish prefix notation just like Lisp. I wouldn't want to code in my byte code either (even if the byte codes were replaced with keywords instead of the binary code). Polish prefix notation is great for the compiler but not very good for people.
- sbov 10y ago
  I haven't worked on a program that hijacked the core language functions in the Lisp I use (Clojure). So your concern seems odd to me, especially since you admit you can do the same thing in C. That said, I only use it in my spare time and not for work, so my exposure is limited. Beyond that, your objections seem to be based upon familiarity. I had similar ones before I started using Clojure more often. I think the notation is just fine - it's not much different from imperative languages except they place the parenthesis in a different spot - I think it's more the nesting than the notation, which isn't a common tactic in imperative languages. I still use imperative languages during my day job so I can decipher imperative code easier, but I am much better at deciphering functional code than I used to be.

pg314 10y ago

> One last point about the linked list structure at the heart of Lisp. Linked lists are poorly executed in modern computers that rely heavily on locality of data, to optimize the L1 cache. You could maybe say that linked lists are at the heart of the platonic ideal of Lisp. Naive interpreters might use linked lists in their internal representation. But real implementations of e.g. Common Lisp or Scheme provide a wide array of data structures (multi-dimensional arrays, hash tables, linked lists).

greggman 10y ago

As someone that's also written hundreds of thousands of lines of assembly with macros I don't really see the comparison. Lisp macros are written in lisp itself. You can create complicated data structures, interate over loops, do file io, query databaes, access the network, whatever you want at compile time in lisp where as assembly language macros were never much more complicated than then the C preprocessor. I certaibly did tons of creative things with assembly language macros but they aren't remotely similar to lisp macros. As for perf, 7 very popular and performant games were written in Lisp. Crash Bandicoot 1, 2, 3 as well as Jak and Daxter 1, 2, 3 and Racing.

clarkd99 10y ago
I never said that Lisp macros were anything like assembly macros. I was referring to a macro assembly language as a list of opcodes (function calls) and macros. I am quite a fan of Lisp macros which are much more flexible as you can create code at compile time from a Lisp program. I also know that Lisp or assembler can do anything/everything. I don't like polish notation or the lack of structure in Lisp programs. Everything is a function (with only a couple of exceptions).

lispm 10y ago

> This great idea of Lisp (the simple syntax of function calls in round brackets) isn't much different than a good macro assembler even back in the 1960's. Far from it. Recursive functions and symbolic expressions were nothing like assembler back then. > You can indent a Lisp program in any way but the language doesn't require any at all. One can indent it in any way, but practically people use common indentation styles. Lisp also provides formatting&indentation via the pretty printer. CL-USER 48 > '(DEFUN COLLAPSE (L) (COND ((ATOM L) (CONS L NIL)) ((NULL (CDR L)) (COND ((ATOM (CAR L)) L) (T (COLLAPSE (CAR L))))) (T (APPEND (COLLAPSE (CAR L)) (COLLAPSE (CDR L)))))) (DEFUN COLLAPSE (L) (COND ((ATOM L) (CONS L NIL)) ((NULL (CDR L)) (COND ((ATOM (CAR L)) L) (T (COLLAPSE (CAR L))))) (T (APPEND (COLLAPSE (CAR L)) (COLLAPSE (CDR L)))))) > I think with practice, some programmers developed an eye for the lack of structural clues Lisp has a lot of syntax and structural clues, but you just don't know them. You have to learn them, since much of, say, C syntax knowledge does not carry over to Lisp. >and made some reasonable size code. Like the 1 million lines of Lisp code of the Lisp Machine OS? Or the several hundred thousand lines of an editor largely written in Lisp (GNU Emacs)? > Linked lists are poorly executed in modern computers that rely heavily on locality of data Lisp nowadays usually does not execute linked lists, but runs compiled Lisp. Some data is in linked lists, but there are many other data structures not made of linked lists. Still the language runtime is often pointer heavy.