> But if you have such a redundant structure, where the array elements
> point into the list, you have a large overhead to build both the array
> and the list.
I think that building trees take more overhead than executing a
malloc and building a linear list. (And probably more cons cells).
> You can't do any changes (cons, insert, delete, reverse)
> without rebuilding the array. And - as before - you have to keep track
> of your arrays to know when to dispose them.
There's no point in creating array helpers for small lists elements.
These helpers are only useful for large lists.
Most of us always use these big arrays as global, static (in the C
sense), created at the beginning of a program, living during the whole
lifetime of a program, and being disposed of manually at the end of
the program, or automatically by the system at program end. During
their life, these arrays don't grow, the structure remains the same,
because they have the nature of an array.
Of course I could use the allocation and disposing of small arrays at
many points in the source code with this system, as you fear, like C
and C++ programmers do. But that is hell, I would not do that. They
do that because they don't have other means.
So the allocation and disposing using malloc() and free(), are only
made typically for a pair of big arrays at two well known points in
the source code, and that's it.
The following is a typical program showing the use of array helpers:
(setq *Ram (array (readFile 65536 "ram.bin")) # memory array
*PC 0 # Program pointer
*SP 16384 # Stack pointer
*Reg1 0 *Reg2 0 *Reg3 0 # general registers
*Run T )
(setq *P (nth: *Ram *PC)) # random access
(execute *P) )
[... here would be all the main code ...]
(dispose *Ram) # optional
For this kind of program, using trees to emulate raw memory array
functionality seems convoluted, and I guess at least 10 times slower.
Convoluted because of the emulation of a more primitive structure by
means of a more complex one.
The most important data structure in Picolisp, the cons cell, is
nothing more than a array element, addressable by a pointer, that is
just an array index. If I want to use Picolisp to do exploratory
programming of computer interpreters, then having arrays seems
> I'm still not convinced at all that accessing list elements by a numeric
> index is really needed, or at least justifies the effort. The mentioned
> 'hash' mechanism is alread there, in constructs like the built-in
> 'cache' function (see also the answer by Denis Fourt).
If you consider that for building interpreters, emulating raw memory
indexes with trees is appropiate, then I don't think so. I see it
half way as convoluted as clogging the symbol table with symbols like
'M00001, 'M00002 ... for doing that.
Or may be you consider that trees are not appropiate for that kind of
application, as is my opinion, and your solution is to resort to
another computer language, as C, for doing that kind of programming.
In this case I would understand your choice. I would like to be able
to do that kind of low level programming in picolisp.
The implementation effort would be about 20 lines of code.