Arc Forumnew | comments | leaders | submitlogin
3 points by sacado 4250 days ago | link | parent

I've got a dumb (but obviously working) implementation of hash tables. Actually, it is so dumb that it cannot really be called a hash table, but at least you can use it.

The implementation consists in two arrays : one for the keys, the other one for values. When you look for an object, it goes through the keys array and performs 'is comparison until it finds it. It is as scalable as alists, I know, but I'll work on the actual implementation later...

There are a few other new things. Most notably, the functional notation for accessing parts of lists/strings/hash tables is now implemented : ('(foo bar baz) 2) returns 'baz.

I thought it would bring horrible performance : since something at a functional position can be not only a closure, but also a string, a table or a pair, you have to do multiple dispatch every time you call a closure. Ugh... Well, obviously, gcc (with -O3) is very clever, or I'm missing something, because the actual slowdown isn't really significative.

Will be pushed tonight (Paris time).



3 points by almkglor 4250 days ago | link

Note that a list key is compared using 'iso, not 'is (the quoted list bug notwithstanding)

> There are a few other new things. Most notably, the functional notation for accessing parts of lists/strings/hash tables is now implemented : ('(foo bar baz) 2) returns 'baz.

Cool! How'd you implement it?

I assume it doesn't have support for the 'call* table yet?

-----

3 points by sacado 4249 days ago | link

It looks a little hackish. I implemented it in the END_JUMP macro. If the object in LOCAL(0) (supposed to be a closure) is a string, a table or a cons, perform the adequate lookup operation (taking LOCAL(2) as a parameter). Then perform the actual jump : BEGIN_JUMP, PUSH(LOCAL(1) (which is the continuation)), PUSH(resut of lookup operation), END_JUMP.

call* is not implemented yet.

As for keys in hash tables, I admit I didn't really bother yet. It is quite broken in canonical Arc anyway (and in Anarki too for that matter) : it doesn't work correctly with lists and does not work correctly with strings too (if you update a string key, you're dead). If the hash itself is its own key, it breaks, but I don't know if this is supposed to be feasible or not.

So I'll focus on symbols and numbers as keys, first, as they are the most usual key types anyway, and will gradually introduce other key types.

-----

3 points by almkglor 4249 days ago | link

Just wondering if it's possible to create a bunch of primitives to do the referencing?

  %string-ref
  %list-ref
  %table-ref
Then possibly we could add to lib-ac.scm.arc:

  (= call* (%table)) ;or whatever the table-creating primitive is
  (%sref-table call* 'string
    (fn (s i) (%string-ref s i)))
  (%sref-table call* 'list
    (fn (s i) (%list-ref s i)))
  (%sref-table call* 'table
    (fn (s i) (%table-ref s i)))
  ; for compatibility with existing Anarki
  (set ref
    (fn (c i)
      (if (%is (%type c) 'string)
          (%string-ref c i)
          (if (%is (%type c) 'list)
              (%list-ref c i)
              (if (%is (%type c) 'table)
                  (%table-ref c i)
                  ; dummy stub for error message, when
                  ; errors are implemented
                  ())))))
Then maybe change code-execute* to something like:

  obj fn = SYM2OBJ("fn");
  obj typ;
  goto initjump;
  jump:
  // most common case, so check it first
  if((typ = type(LOCAL(0))) == fn){
    goto realjump;
  } else {
    memmove(&LOCAL(3),&LOCAL(2), (num_args - 2)*sizeof(obj));
    ++num_args;
    LOCAL(2) = LOCAL(0);
    LOCAL(0) = table_lookup(GLOBAL(CALL_TABLE), typ);
    //possibly add a check here to see if it's a function
  }
  realjump:
  pc = LOCAL(0)[0]; //or whichever it should be
  initjump:
  switch(pc){
    ...

-----

1 point by sacado 4249 days ago | link

good idea, I'll implement that soon...

-----

1 point by almkglor 4249 days ago | link

  -#define CAR() { if (TOS() != NILOBJ) {pair * p = (pair *) POP(); PUSH((obj)(p->car)); }}
  -#define CDR() { if (TOS() != NILOBJ) {pair * p = (pair *) POP(); PUSH((obj)(p->cdr)); }}
  +#define CAR() { pair * p = (pair *) POP(); PUSH((obj)(p->car)); }
  +#define CDR() { pair * p = (pair *) POP(); PUSH((obj)(p->cdr)); }
Just wondering: Why was this changed? Shouldn't it be that (car nil) == nil?

-----

1 point by sacado 4249 days ago | link

oh, oh, that's a mistake, sorry. I forgot to merge this with my own code. I'll do it on the next commit, if you don't do it before me...

-----

1 point by almkglor 4249 days ago | link

I'll change it back then ^^

Edit: done

-----

1 point by sacado 4250 days ago | link

pushed

-----