Vectors

Vectors a new data type, that are currently a variation on cons lists. However, in the Arrays branch they are implemented with Bash arrays. This is a brief description of that code.

Internal Functions

The implementation uses native bash indexed arrays. Every time new_array is called, it does a gensym for the array name, and uses declare -a to establish it as an array. A bit of eval magic then allows the array to be read/updated.

The array functions are:

• new_array
• vset (changed to match vget)
• vget (was aget but this name is already in use)
• count_array
• append
• append_all
• prepend
• dup (duplicate to a new array)
• concat (calls dup/append_all)

All of these functions do in-place updates to the array, with the exceptions of dup and concat.

Example use of these functions is:

new_array
a=$r
append $a quick
append $a brown
append $a fox
new_array
b=$r
append $b jumped
append $b over
concat $a $b
c=$r
prepend The $c
append $c "the lazy dog"
vset $c 4 jumps

This creates 3 arrays:

• $a contains ([0]=quick [1]=brown [2]=fox)
• $b contains ([0]=jumped [1]=over)
• $c contains ([0]=The [1]=quick [2]=brown [3]=fox [4]=jumps [5]=over [6]="the lazy dog")

Format

Each of the array vars are actually strings of the form ${tag_marker}003arrNNN, where the "NNN" is an incrementing number. Accessing an array means stripping off the tag and type info, resulting in values such as "arr8". The variable "arr8" is initialized as an indexed array, and an operation like (nth ... 2) could be done with ${arr8[2]}. However, since the value "arr8" never appears anywhere in code, it requires eval operations for access.

Dispatch

Right now there are "if" statements differentiating between cons and vector in several places. The code is similar, but not enough to avoid duplication. We see paired code like this in:

• read_list/read_vector (called from lisp_read)
• str_arr/str_list (called from str)
• if cons/vector in eval_args ('vector' calls this from lisp_eval)
• if cons/vector in apply_user for (fn [x] ...) vs. (fn (x) ...)
• if cons/vector in apply_primitive, case $APPLY (apply + [1 2]) vs. (apply + '(1 2))
• if cons/vector in add_bindings (let [bindings] ...) vs. (let (bindings) ...)
• listify_args/vectify_args (called via a new case in lisp_eval)

One hassle is how to deal with operations like nth. Lists do this in a function based on car/cdr/reduce, so need to go through the apply_user dispatch. However, arrays can do this as a O(1) operation that needs to be apply_primitive. This would need a choice of dispatch based on the data type. This should be done in an extensible way, rather than special-casing the use of a vector in these contexts. Similarly, concat can be performed efficiently with arrays and would need to dispatch via apply_primitive to get through to the bash "concat" function.

Protocols will provide some of this answer, but that would mean protocols need to be dispatched in apply, before getting to the apply_user vs. apply_primitive test.