Arc Forum | How does hash table work when key is a list?

Arc Forum

How does hash table work when key is a list?

3 points by zhtw 5997 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 5997 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 5997 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 5997 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 5997 days ago | link

Because arc is for smart programmers and pg wants to be second-guessed.

-----

5 points by absz 5997 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 5996 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 5996 days ago | link

I don't think pg is an elitist at all.

-----

1 point by absz 5995 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 :)

-----