5 ms·

It's interesting to me that he refers to association arrays as "newish", when they showed up in Lisp nearly 20 years earlier.

chasil 2y ago
This is from the first edition free PDF online of The AWK Programming Language: "Associative arrays were inspired by SNOBOL4 tables, although they are not as general. Awk was born on a slow machine with a small memory, and the properties of arrays were a result of that environment. Restricting subscripts to be strings is one manifestation, as is the restriction to a single dimension (even with syntactic sugar). A more general implementation would allow multi-dimensional arrays, or at least allow arrays to be array elements." Stable release - SNOBOL4 / 1967 https://en.wikipedia.org/wiki/SNOBOL https://en.wikipedia.org/wiki/SNOBOL
jerf 2y ago
Two things to keep in mind: Pre-internet, it was quite easy to be skilled and knowledgeable and yet never have been exposed to something another community somewhere would consider basic, or for it to take many many years to percolate across. I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. Second, while the programming world fancies itself a very fast mover, it really isn't, and it especially wasn't back then. 20 years isn't necessarily as long as you would think in 2024. We're still trying to convince people in 2024 that you really don't need a language that will happily index outside of arrays, and how long has that been a staple in existing languages? (You may think that's silly, but we've had that fight on HN, yes, yea verily, this very year. Granted, this is winding down, but it's still a live argument.) There's a lot of things that showed up in some language in the 1960s or 1970s and wasn't widely adopted for another few decades. (Though I suspect one problem with Lisp is that back in the day, its performance was pretty awful relative to the other things of the day. It was not always the best advertisement for its features. A bit too ahead of its time sometimes.)
- Zambyte 2y ago
  I totally get the first point, but this comment from Brian was made when the internet had been available for many, many years. It seems more like it felt newish at the time, and that is how he has seen it since then. I guess that's more why I find it to be an interesting comment. Regarding the second point, when I hear the term "associative arrays" or "associative lists" I think of them in a pretty high level of abstraction. Like really: a C struct is an association abstraction. A simple array of structs is not often considered an "associative array", but it can easily be used for the same things. Maybe it would be more accurate to say that the way they were using associative arrays way newish, rather than the construct itself.
- vram22 2y ago
  >I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. That's a little surprising, considering that the classic first book about C, K&R was first published in 1978 and again in 1988, the first and second edition, respectively. One of the editions, maybe the first, had a simple hash table implementation, that just summed up the ASCII values of the characters in the given string, modulo some value, and used that as the key for the string being hashed. . https://en.m.wikipedia.org/wiki/The_C_Programming_Language https://en.m.wikipedia.org/wiki/The_C_Programming_Language
- xarope 2y ago
  I remember being taught about associative caches in CPU architecture, and later on programming the same in C. So I'm not sure about the 90's and hash tables being "exotic". My first real use of hashes was in perl4; with perl5 released in 1996 (https://dev.perl.org/perl5/news/ https://dev.perl.org/perl5/news/), surely it meant people were also well aware of the usefulness of hash arrays even back then.
  - cancerhacker 2y ago
    It was a common practical interview question in 1996 to ask a candidate to implement a hash table in C.
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)
shawn_w 2y ago
Common Lisp, of course, has built in hash tables. MacLisp doesn't seem to - I didn't see anything about them in the Pitmanual. ZetaLisp/LML and InterLisp have them. So it seems like built in lisp associative arrays (I'm not counting alists, or property lists, though the latter goes back to the early days and maybe should be) are roughly contemporary to the birth of awk. Maybe a bit newer.

chasil 2y ago

This is from the first edition free PDF online of The AWK Programming Language: "Associative arrays were inspired by SNOBOL4 tables, although they are not as general. Awk was born on a slow machine with a small memory, and the properties of arrays were a result of that environment. Restricting subscripts to be strings is one manifestation, as is the restriction to a single dimension (even with syntactic sugar). A more general implementation would allow multi-dimensional arrays, or at least allow arrays to be array elements." Stable release - SNOBOL4 / 1967 https://en.wikipedia.org/wiki/SNOBOL https://en.wikipedia.org/wiki/SNOBOL

jerf 2y ago

Two things to keep in mind: Pre-internet, it was quite easy to be skilled and knowledgeable and yet never have been exposed to something another community somewhere would consider basic, or for it to take many many years to percolate across. I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. Second, while the programming world fancies itself a very fast mover, it really isn't, and it especially wasn't back then. 20 years isn't necessarily as long as you would think in 2024. We're still trying to convince people in 2024 that you really don't need a language that will happily index outside of arrays, and how long has that been a staple in existing languages? (You may think that's silly, but we've had that fight on HN, yes, yea verily, this very year. Granted, this is winding down, but it's still a live argument.) There's a lot of things that showed up in some language in the 1960s or 1970s and wasn't widely adopted for another few decades. (Though I suspect one problem with Lisp is that back in the day, its performance was pretty awful relative to the other things of the day. It was not always the best advertisement for its features. A bit too ahead of its time sometimes.)

Zambyte 2y ago
I totally get the first point, but this comment from Brian was made when the internet had been available for many, many years. It seems more like it felt newish at the time, and that is how he has seen it since then. I guess that's more why I find it to be an interesting comment. Regarding the second point, when I hear the term "associative arrays" or "associative lists" I think of them in a pretty high level of abstraction. Like really: a C struct is an association abstraction. A simple array of structs is not often considered an "associative array", but it can easily be used for the same things. Maybe it would be more accurate to say that the way they were using associative arrays way newish, rather than the construct itself.
vram22 2y ago
>I remember getting into programming even in the 1990s and I can tell you a lot of the C world would still consider associative data structures like a hash table something to be a bit exotic and only to be pulled out if you had no other choice. It was very easy to not be very up to date on these things. That's a little surprising, considering that the classic first book about C, K&R was first published in 1978 and again in 1988, the first and second edition, respectively. One of the editions, maybe the first, had a simple hash table implementation, that just summed up the ASCII values of the characters in the given string, modulo some value, and used that as the key for the string being hashed. . https://en.m.wikipedia.org/wiki/The_C_Programming_Language https://en.m.wikipedia.org/wiki/The_C_Programming_Language
xarope 2y ago
I remember being taught about associative caches in CPU architecture, and later on programming the same in C. So I'm not sure about the 90's and hash tables being "exotic". My first real use of hashes was in perl4; with perl5 released in 1996 (https://dev.perl.org/perl5/news/ https://dev.perl.org/perl5/news/), surely it meant people were also well aware of the usefulness of hash arrays even back then.
- cancerhacker 2y ago
  It was a common practical interview question in 1996 to ask a candidate to implement a hash table in C.

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)

shawn_w 2y ago

Common Lisp, of course, has built in hash tables. MacLisp doesn't seem to - I didn't see anything about them in the Pitmanual. ZetaLisp/LML and InterLisp have them. So it seems like built in lisp associative arrays (I'm not counting alists, or property lists, though the latter goes back to the early days and maybe should be) are roughly contemporary to the birth of awk. Maybe a bit newer.