General computer philosophy.. shouldn't the structures that work well with CPU's be present in the language, and used by the language, but not neccesarily accessible by humans, and the structures that work well with humans be the ones that are accessible to humans.
So while anarki might need to support arrays internally for efficiency, they need not neccesarily be part of the language as far as the users can tell.
If the above is true, then right now the implementation of things that are efficient for the language when it wants to communicate with the cpu are of a lower priority than the things that are efficient for the communication between the user and the language.
I think we can have the best of both worlds. I would love Arc to have an intelligent compiler that figures out the best representation for your data, but I would also like access to the low-level data types.
Why? Because Lisp is supposed to be a reprogrammable programming language, where the user can do anything the compiler can do. If the user has access to the underlying bits and bytes, then they can implement new representations of high-level structures, rather than relying on the compiler writer. In fact, I would argue that Arc should only provide low-level structures in the axioms, and then high-level ones can be implemented on top.
If I wanted to represent a matrix of objects.... say a world populated by virtual creatures... I might prefer to predefine the size of the world and identify creature locations using numeric coordinates. I might then want to use an array of arrays to represent the world ^^. I might even abstract away the position of an object using a "location" type composed of a pair of numeric coordinates and a reference to the world, then have "north" and "east" etc. functions to get locations in those directions. Then I might get the reference or set the reference of a location object and thus query and/or change the state of the creatures in that world.... ^^
In Arc-F for example I might use:
(using <vector>v2) ; vector and vector-of
(def make-world (xwidth yheight)
(apply vector
(w/collect:for i 0 (- xwidth)
(collect:vector-of yheight nil))))
; create a location type
(def location (world x y)
(annotate 'location
(list world x y)))
(defcall location (r)
(let (world x y) r
(world.x y)))
(defm sref ((t loc location) val)
(let (world x y) (rep loc)
(sref world.x val y)))
; 0---> INF
; |
; |
; v
; INF
(def south (loc (o step 1))
(err "'north and 'south expect a location"))
(defm south ((t loc location) (o step 1))
(let (world x y) (rep loc)
(location world x (+ y step))))
(def north (loc (o step 1))
(south loc (- step)))
(def east (loc (o step 1))
(err "'east and 'west expect a location"))
(defm east ((t loc location) (o step 1))
(let (world x y) (rep loc)
(location world (+ x step) y)))
(def west (loc (o step 1))
(east loc (- step)))
I should put some more work into it. The good news is that I just found a nice and simple editor that plays well with arc-f on windows (LispIDE - http://www.daansystems.com/lispide/)
btw. arc-f arc.bat doesn't play nice yet with "Program Files" type of directories. Works fine in C:\arc-f.
Got this error:
> default-load-handler: cannot open input file: "C:\Program" (The system cannot find the file specified.; errno=2)
We could give only lists to the user, and implement them internally as arrays when they are frequently used with indexed access and with lists when they are mainly used with car/cdr. Not an easy thing to implement, though.
I made a suggested implementation of lists as unrolled lists which preserves the use of 'scdr on the Arc Forum a long time ago. http://arclanguage.com/item?id=4146 . Basically it would be effectively arrays.
The problem with the proposed implementation however is that the "cons pointer" is a data structure of at least two cells (a pointer to the root of the underlying array, which includes a pointer to the cdr-table somewhere, and a pointer to the actual entry within the array).
However recently I thought of a method by which all that is necessary would be a (probably tagged) pointer to the actual entry within the array. This would require tagged pointers (i.e. no Boehm-Weiser!).
Basically we would define a tagged pointer type which, when found in a list-as-array, would not be a valid 'car of that entry, but rather would be a pointer to an object containing the real 'car and 'cdr for that object. It might be possible to also use a tagged pointer (potentially the same tag, but say with a null pointer) to denote the end of a list.
Let's call this invalid tag a "NON_CAR_TAG", and let's call the tag for a pointer to an array-as-list-cons-cell a "CONS_ARRAY"
Basically a (list 1 2 3 4) would be represented with the array:
[0] INTEGER(1) // tagged with an INTEGER
[1] INTEGER(2)
[2] INTEGER(3)
[3] INTEGER(4)
[4] NON_CAR_TAG( NULL ) // null pointer
A 'cons object would either be a (potentially nontagged) pointer to a real cons cell, or a CONS_ARRAY() tagged pointer to an entry in an array such as the above.
Now suppose we have the operation (= foo (list 1 2 3 4)). 'foo would then contain a CONS_ARRAY() tagged pointer to the above. Suppose the pointer to the above array is 0xDEADBEE0. 'foo would then be CONS_ARRAY(0xDEADBEE0).
Now suppose that a cell is exactly 16 bytes (just an example for easier reasoning). So (cdr foo) would be CONS_ARRAY(0xDEADBEF0), (cdr:cdr foo) would be CONS_ARRAY(0xDEADBF00), etc. Basically, 'cdr would first check if the input is a CONS_ARRAY() tagged pointer, and just add 0x10 (or the cell size). If the resulting address points to an entry that happens to be NON_CAR_TAG(NULL), it should return a NILOBJ, otherwise it returns the result of the addition.
Now, suppose we then do (scdr (cdr foo) 42). 'scdr should first detect if the the pointer it is given is a CONS_ARRAY() tagged pointer. If so, it determines if the value being pointed to is a NON_CAR_TAG() or not. If it's a NON_CAR_TAG(), it gets the underlying cons cell pointed to by the NON_CAR_TAG and modifies that. Otherwise, it allocates a new cons cell, populates it with the existing 'car and the new 'cdr, tags the cons cell pointer with NON_CAR_TAG(), and replaces the entry:
+---------> CONS: A INTEGER(2)
[0] INTEGER(1) | D INTEGER(42)
[1] NON_CAR_TAG( * )
[2] INTEGER(3)
[3] INTEGER(4)
[4] NON_CAR_TAG(NULL)
Note however that it has a drawback that l.index is still O(N) T.T
