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

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

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.