login
 How does hash table work when key is a list? 3 points by zhtw 5864 days ago | 8 comments As I understand "is" for lists compares pointers not elements. So:`````` arc> (= a (list 'cons)) (cons) arc> (= b (list 'cons)) (cons) arc> (is a b) nil `````` Implementation of hash doesn't seem to use "is", because it wouldn't be possible to assess the elements at all by list as a key. In fact happens something I don't understand:`````` arc> (= vtable (table)) #hash() arc> (= (vtable (list (type '(1)))) 'a-method) a-method arc> (vtable '(cons)) nil arc> (vtable (list 'cons)) a-method arc> (quote (cons)) (cons) arc> (list 'cons) (cons) `````` Why can't I use '(cons) to access a-method and why is it still possible to access it by (list 'cons)?

 6 points by absz 5864 days ago | link The problem lies in the split between how Arc and mzscheme represent lists. Arc essentially uses iso to compare table keys (iso compares lists by structure, so while (isnt (list 'cons) (list 'cons)), (iso (list 'cons) (list 'cons))). Thus both your examples should work.The problem lies in the definition of lists. (I'm explaining this from the beginning because I don't know what your skill level is; if you know how lists work, then please skip the rest of this paragraph.) Lists are composed of cons cells, each of which is essentially an ordered pair of a car and a cdr. The car holds the value, and in a list, the cdr must be another list. So what do you use to represent the empty list?This is where the problem lies: in mzscheme, () is the empty list, and 'nil is just a symbol. In Arc, nil is a symbol that is also the empty list. Thus, we get`````` arc> vtable #hash(((cons) . a-method)) arc> (= (vtable '(cons)) 'another-method) another-method arc> vtable #hash(((cons) . a-method) ((cons . nil) . another-method)) `````` Note that the two keys are different: the first key is a Scheme list, ending in (), whereas the second is an Arc list, ending in nil. What's happening becomes clearer when we look at the definition of list (Anarki docstring omitted for clarity):`````` (def list args args) `````` So as far as I understand it, when an Arc function with a variadic parameter (like list) is called, the arguments are passed to it as a Scheme list instead of an Arc list. Usually this is transparent, since Arc tries to convert () to nil on the Arc side, and nil to () on the mzscheme side.[1] However, it's not perfect, and here's one of the places where that shows up.I didn't see an easy fix inside ac.scm, and don't have the time to keep looking. However, now I'm worried that that's going to trip me up sometime in the future... The only solution I can think of is to explicitly call ac.scm's ac-nil function, which performs the translation from () to nil, but this is (a) very ugly, and (b) only works on Anarki. For what it's worth, though, here it is (where \$ is Anarki's macro for accessing mzscheme):`````` arc> (= vtable (table)) #hash() arc> (= (vtable (\$.ac-niltree (list (type '(1))))) 'a-method) a-method arc> vtable #hash(((cons . nil) . a-method)) arc> (vtable '(cons)) a-method arc> (vtable (\$.ac-niltree (list 'cons))) a-method arc> (vtable (list 'cons)) nil `````` I hope that helps, but I hope even more that this bug gets fixed. (I, unfortunately, have external obligations and can't continue chasing it down.)[1]: It also tries to convert #f and nil, but that's not relevant for your problem.-----
 2 points by zhtw 5864 days ago | link Thanks for the detailed explanation. I got the idea. Well, in my case this is going to stay deep inside the library. So any workaround would be fine.But I solved this by adding (join ... nil).-----
 2 points by absz 5863 days ago | link That is a much nicer in-Arc solution than mine; good catch. In any case, I'm glad I could be of assistance.-----
 1 point by applepie 5864 days ago | link Because arc is for smart programmers and pg wants to be second-guessed.-----
 5 points by absz 5864 days ago | link Or maybe there's a bug somewhere? The default assumption should not be "pg is an elitist jerk," but "pg is a fallible human being."[1] Whether or not pg is an elitist jerk is irrelevant, as the answer is probably that there's a bug/some unexpected behaviour hiding somewhere in arc.arc or ac.scm. In fact, I think that is the case, and the problem has to do with translating lists between Arc and mzscheme: see http://arclanguage.org/item?id=6993. But it's always best to analyze first, since you get more done that way.[1]: In fact, "so-and-so is a fallible human being" is almost always the best first stop: Hanlon's Razor ("Never attribute to malice that which is adequately explained by stupidity.") and all that.-----
 1 point by sacado 5862 days ago | link There are bugs in the implementation of hash tables, he confirmed this. Don't try them with strings as keys for example (I mean, strings you modify).-----
 2 points by applepie 5862 days ago | link I don't think pg is an elitist at all.-----
 1 point by absz 5862 days ago | link My apologies thenâ€”I misread the sentiment behind your comment. In that case, I direct the sentiment of my previous comment away from you :)-----