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
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:
(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
here's the implementation of binary tree traversal for setting shell variables in the v7 bourne shell from 01979 if you're not sure, that's c (now you know where the ioccc came from)