3 ms·
in a sense lisp alists are 'associative arrays', sure. but, although they were used in the metacircular interpreter that bootstrapped lisp and still inspires u
by kragen 2y ago
in a sense lisp alists are 'associative arrays', sure. but, although they were used in the metacircular interpreter that bootstrapped lisp and still inspires us today, they aren't a language feature, and the lisp ones aren't efficient enough for the things you use them for in awk
you can of course build an associative array in any language, especially if you're satisfied with the linear search used by lisp alists. you can hack one together in a few minutes almost without thinking:
.intel_syntax noprefix
lookup: push rbx
push rbp
mov rbx, rdi # pointer to alist node pointer
mov rbp, rsi # key
2: mov rdi, [rbx] # load pointer to alist node
test rdi, rdi # is it null?
jnz 3f # if not null, skip not-found case
mov rax, rbx # pointer to null pointer is return value
xor rdx, rdx # but associated value is null (sets zero flag)
jmp 4f # jump to shared epilogue
3: mov rdi, [rdi] # load pointer from key field of alist node
mov rsi, rbp # reload key from callee-saved register
call comkey # sets zero flag if rsi and rdi are equal keys
jne 1f # skip following return-value case code if !=
mov rax, rbx # pointer to node pointer is return value
mov rdx, [rbx] # also let’s follow that pointer to the node
mov rdx, [rdx + 16] # and return its value field too in rdx
test rax, rax # clear zero flag (valid pointer is not null)
4: pop rbp
pop rbx
ret
1: mov rbx, [rbx] # load pointer to alist node again
add rbx, 8 # load pointer to next-node pointer field
jmp 2b
(untested, let me know if you find bugs)
but that's very different from having them built in as a language feature, like snobol4, mumps, awk, perl, python, tcl, lua, and js do. the built-in language feature lisp had for structuring data 20 years earlier was cons, car, and cdr, which is not at all the same thing
other programs on unix that contained associative arrays prior to awk included the linker (for symbols), the c compiler, the assembler, the kernel (in the form of directories in the filesystem), and the shell, for shell variables. none of these had associative arrays as a programming language feature, though. the bourne shell came closest in that you could concatenate variable names and say things like
eval myarray_$key=$val
here's the implementation of binary tree traversal for setting shell variables in the v7 bourne shell from 01979
NAMPTR lookup(nam)
REG STRING nam;
{
REG NAMPTR nscan=namep;
REG NAMPTR *prev;
INT LR;
IF !chkid(nam)
THEN failed(nam,notid);
FI
WHILE nscan
DO IF (LR=cf(nam,nscan->namid))==0
THEN return(nscan);
ELIF LR<0
THEN prev = &(nscan->namlft);
ELSE prev = &(nscan->namrgt);
FI
nscan = *prev;
OD
/* add name node */
nscan=alloc(sizeof *nscan);
nscan->namlft=nscan->namrgt=NIL;
nscan->namid=make(nam);
nscan->namval=0; nscan->namflg=N_DEFAULT; nscan->namenv=0;
return(*prev = nscan);
}
if you're not sure, that's c (now you know where the ioccc came from)
- foobarian 2y agoI love that Bourne abused C macros to make sh source look like Algol. Lots of references to this elsewhere but this is my favorite: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh/mac.h https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/sh...
- kazinator 2y agoThe "killer feature" of alists is that they are persistent data structures; when we extend a shorter alist to make a longer one, the shorter one is unaffected. Moreover, if the program has only a reference to the tail portion of a longer alist, the head portion can be garbage-collected. With this, we can correctly implement lexical closures: we simply take the current environment (head of the alist) ssociate it with the lambda body and arguments, and we are done.
- kragen 2y agoyes! also when you only have two or three things in them, they are faster than hashing, especially on machines without a data cache. clojure uses hamts for this, thus getting this fp-persistence† as well as efficient lookup in large dictionaries, and chris wellons posted a concise, fast c hamt implementation last year at https://nullprogram.com/blog/2023/09/30/ https://nullprogram.com/blog/2023/09/30/ ______ † 'persistent' unfortunately also means 'stored in nonvolatile memory', so i feel the need to disambiguate
- chuckadams 2y agoI’d say plists have a stronger claim on being “real” associative arrays. Lisp never made much distinction between “built in” and “library” to begin with, you're using the same syntax to use the feature either way.
- kragen 2y agoi think it's true that, much of the time that you'd use a dict in python, you'd use a property in 01960s lisp, because it let you take advantage of the read-time implicit hashing of symbols; you probably only had one or two properties on most of your symbols, so getting from the interned symbol to the property was a matter of a handful of instructions---probably faster than a hash function. but conceptually i feel like they're pretty different ideas