Hacker News Reader

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.

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.

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.

Big time array fan here. I'd love to check out your language when you publish it. Sooner the better.. we need new ideas! Email in profile if you'd like to chat about it.

>"every LISP garbage collector writer, knows about CDR-coding."

I thought CDR needed hardware support as opposed it being a general programming technique, is that not correct?

I've only ever read about it on FAQs like in the following:

http://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/fa...

> 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).

> 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.

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.

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).

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.

(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.

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.

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.

David Clark is like John Smith and no, I am not any famous person but I have been around the micro computer world for a very long time (1975).

My website is www.rccconsulting.com where you will find an essay on the data structure I mentioned here called SLIST and some documentation and high level design for the system/language I am currently developing called MAX.

Users do care more about response times (as you say) and instantaneous and 1/2 instantaneous are considered equal by end users. Most user developed code doesn't need optimization but the data structures that under pin that user code should be as performant as possible, just in case.

Designing a language like Lisp or a special purpose language/system like I am creating have design criteria that is much different from the application programmer that is just trying to make stuff work. I have completed at least 1,000 projects big and small as an application programmer, as well as all the system programming I have done so I think I have a good incite into both points of view.

>> use of lists; most applications don't use them

You may be correct but most programs manipulate variable length character strings whether that is formatting, creating HTML documents, creating JSON data etc. Most currently used programming languages don't do variable length strings either well or efficiently. I also don't like the fact that almost all useful data must be manipulated and stored in database systems that reside somewhere other than my computer. My new system was designed to help solve that problem and more.

There's already a language called Max: https://cycling74.com/products/max/#.WFRNp-wWVpg

Your SLIST sounds similar to data structures which go by various names in different languages, e.g. list in Python or ArrayList in Java. Common Lisp vectors support that functionality too.

Your VCHAR presumably works in a similar way? I agree ASCIZ is a very inefficient way of representing strings, unless they're guaranteed to be very short.

Max is the internal name I use for my system. The actual name will be decided when I publish the program.

At the top of my description of SLIST, I acknowledge that I may not be the first to define a simple structure like that but I can say that I never got the idea from somewhere else. These lists can be used as an autobalanced binary tree for small lookups? Are these other structures pointer free with next to no overhead even on a 64 bit compiler? If they can do all that my humble SLIST can do then I will have invented a very good data structure and there isn't anyone using linked lists with pointers, right?

Most languages have made strings read only so they aren't very useful for manipulating large and small amounts of variable text. Actually, my VCHAR struct just uses my buffers which are used whenever memory is needed. My language is object oriented but even more it is collection oriented so most objects don't allocate space just for themselves. When using my buffer routines, no buffer can ever use data that doesn't belong to it or overflow it's allocated space.

I have many local and global memory managers and my buffer structure keeps track of use, size and origin. Memory that is alloced globally is always on cache line boundaries and so I don't put headers on allocated data. All chunks of memory are tracked and can't get lost so I count on less memory allocations than most other languages (collections remember)

Compared to any alternative I have found (unicode etc), ascii is quite efficient. When I get around to adding any unicode support, it will be UTF8 so none of the current code needs replaced or will run slower than now.

ASCIZ = https://en.wikipedia.org/wiki/Null-terminated_string

This web page doesn't fit into the L1 cache, and your browser uses some horrible data structure for it, the individual pieces of which do not cache well. Why are you here at all?

I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of an insufficiently powerful and generic type system.

Say you have (pseudocode)

  Array(4 16 5 20)

What's its type?

  Array
  Array<Int>
  Array<4>
  Array<Int 4>
  Array(Int Int Int Int)

None of these lend themselves easily to paradigms other than imperative, true. But this is because they unnecessarily discard known information. The type of an array ought to be itself:

  assert Array(4 16 5 20) hasType Array(4 16 5 20)
    => Ok
  
  assert Array(4 16 5 20) hasType Array<Int>
    => Error("Expected Array<Int> but got Array(4 16 5 20). Hint: Typeclass Array<Int> cannot be directly instantiated")
  
  assert Array(4 16 5 20) hasTypeclass Array<Int>
    => Ok

Fully functional and referentially transparent.

And if you want a new array whose first element is increased by one, you either have to allocate space for the entire array, modify the array, or use a different data structure.

No you don't, you merely need each index into an array to be a monad over all possible values it can contain. An array is itself and modifications are (take as arguments and return) its indices.

And how is that implemented under the hood?

Same as in a higher-level statically typed imperative language: mutable arrays contained within larger dynamic buffers for amoritized constant-time append and prepend.

So it isn't really functional at all. It just hides the side effects behind a lot of complexity.

This is precisely what functional programming does. Purely functional abstractions are just that, abstractions.

> you merely need each index into an array to be a monad over all possible values it can contain

Now keep a straight face and say "L1 cache" once again.

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.

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?

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.

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).

Haskell and Elm use whitespace as well, but I don't recall if they enforce the indentation.

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.

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.

I get an error when trying to redefine 'if' in SBCL, though you could probably do it through the abuse of packages. The C preprocessor does allow 'if' to be redefined, though. No one does that sort of thing outside of obfuscated C competitions, though, so it isn't really a problem in either language.

What you find easy to read depends on what you're used to reading.

> After I wrote that statement I started thinking

You will have a better time on HN if you swap these two more often than not.

Fortran (at least the last version I used, which was F77) requires specific indenting.