News for hackers. Stuff that matters.
Re:A brief interview with Awk creator Dr. Brian Kernighan by kragen on Wednesday July 17, 2024 @04:31PM (#40990055)
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)
Re:A brief interview with Awk creator Dr. Brian Kernighan by foobarian on Wednesday July 17, 2024 @05:25PM (#40990506)
I 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...

Re:A brief interview with Awk creator Dr. Brian Kernighan by kazinator on Wednesday July 17, 2024 @11:58PM (#40992375)
The "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.

Re:A brief interview with Awk creator Dr. Brian Kernighan by kragen on Thursday July 18, 2024 @12:15AM (#40992466)
yes! 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/

______

† 'persistent' unfortunately also means 'stored in nonvolatile memory', so i feel the need to disambiguate

Re:A brief interview with Awk creator Dr. Brian Kernighan by chuckadams on Thursday July 18, 2024 @05:00PM (#40999695)
I’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.
Re:A brief interview with Awk creator Dr. Brian Kernighan by kragen on Thursday July 18, 2024 @11:52PM (#41001897)
i 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. but conceptually i feel like they're pretty different ideas