clarkd99

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.

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

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.

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.

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

My current project is over 90,000 lines of C and I have programmed in C since the 1970's (as well as many other languages). I have never used a ternary operator and I think it reads quite poorly. I just use a few lines of easily read code instead. I also never use a do/while construction with the condition at the bottom of the loop. When I need such a construct I just put in an "if" and "break" where ever needed instead. I don't think C should be dissed because of a few unneeded and probably unused features. In C, you can put more than 1 statement on a line if they are separated by a ';' but I have never done that in hundred's of thousands of lines of C code.

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.

A circular buffer can contain a number of nodes and get bigger when it runs out of space by making a larger buffer and copying the old data or clustering as I described above. It doesn't have a "fixed capacity".

My circular queue works without moving any elements on insertion (with cluster method) or just moving the nodes each time the buffer size is exceeded. It seems this "double ended queue" isn't as useful because it has to copy nodes, find a middle etc.

Even in the "cluster" version of my circular queue, you can quickly calculate the actual location of any node directly using it's "virtual" index number, even though the head and tail can "float" anywhere along each cluster array of structs.

I have made a circular queue where data can be pushed or popped on either end of a vector of structs.

Adding an entry can be done on the end or the head without moving any other nodes. All that is required is to have an index for the head and one for the tail. Used as a queue, you would push nodes on the tail and pop nodes off the head. You could just as easily add nodes to the head and pop them off the tail or any combination that you like. You could iterate over the list by starting at the tail and moving backward toward the head. You could also start at the head and move forward toward the tail. If you try to move below the first element then set the index to the last entry. If you try to move above the last entry then continue on the front of the vector.

If the head and tail have the same number then no entries are in the vector.

If the buffer size (which determines how many entries you can have) is about to be exceeded then create a bigger buffer and copy the old entries to the new buffer.

Instead of creating a bigger buffer and copying all the entries, you could make a new "cluster" of the same size as the current buffer and then you could use an integer division and modulo to determine in which cluster and what offset any node might be at.

Using the cluster method, the whole struct could grow as needed, and never move any existing data entries while pushing/popping data at either the head or tail of the list of array nodes. The struct could be just a single number or any other sized structure. Memory allocations would be minimized by allocing a buffer of "n" times the size of each node.