Returning a hash-table iterator from a function?


Is there a way in LispWorks to return an iterator into a hash table
from a function?  I don't think this is possible using standard CL.

For example, I'd like to do something like this:

    (defun hti-closure (ht)
      (with-hash-table-iterator (next ht)
        (lambda () (next))))

    (let ((ii (hti-closure my-hash-table)))
      (multiple-value-bind (found? key value) (funcall ii)
        (when found?
         (format t "First key value is ~a ~a~%", key value))))

This won't work of course, but I was hoping there was a way to do the
equivalent in LispWorks.    

Cheers,
Chris Dean

Re: Returning a hash-table iterator from a function?

On May 13, 2007, at 6:27 PM, Chris Dean wrote:

> Is there a way in LispWorks to return an iterator into a hash table
> from a function?  I don't think this is possible using standard CL.

Not absolutely sure if this is what you meant, but isn't this  
possible in standard Common Lisp?

(defun make-hash-table-iterator (some-hash-table)
   (let ((hash-key-list (loop for key being each hash-key of some- 
hash-table collect key)))
     (lambda () (let ((this-key (pop hash-key-list)))
                  (values this-key (gethash this-key some-hash- 
table))))))

CL-USER 28 > (defvar *my-hash* (make-hash-table))
*MY-HASH*

CL-USER 29 > (setf (gethash 'first-key *my-hash*) 1)
1

CL-USER 30 > (setf (gethash 'second-key *my-hash*) 2)
2

CL-USER 31 > (setf (gethash 'third-key *my-hash*) 3)
3

CL-USER 32 > (defvar *test-hash-iterator* (make-hash-table-iterator  
*my-hash*))
*TEST-HASH-ITERATOR*

CL-USER 33 > (funcall *test-hash-iterator*)
SECOND-KEY
2

CL-USER 34 > (funcall *test-hash-iterator*)
FIRST-KEY
1

CL-USER 35 > (funcall *test-hash-iterator*)
THIRD-KEY
3

CL-USER 36 > (funcall *test-hash-iterator*)
NIL
NIL

CL-USER 37 >

This will even allow you to change the values for existing keys  
between calls to the iterator since the iterator closure only holds a  
list of keys, not their associated values. Of course you can't remove  
or add keys without making a new iterator.

regards,

Ralph

Raffael Cavallaro, Ph.D.
raffaelcavallaro@mac.com

Re: Returning a hash-table iterator from a function?

Raffael Cavallaro <raffaelcavallaro@mac.com> writes:
> Not absolutely sure if this is what you meant, but isn't this
> possible in standard Common Lisp?

This is what I meant, thanks.  But I'd like to avoid the extra consing
if possible.  In this solution, if we're using a large hash table then
we are creating a large list, even if we only end up looking at the
first few elements.

Cheers,
Chris Dean

Re: Returning a hash-table iterator from a function?

Shameless plug.

	http://common-lisp.net/project/cl-enumeration/

Cheers

Marco



On May 14, 2007, at 12:27 AM, Chris Dean wrote:

>
>
> Is there a way in LispWorks to return an iterator into a hash table
> from a function?  I don't think this is possible using standard CL.
>
> For example, I'd like to do something like this:
>
>     (defun hti-closure (ht)
>       (with-hash-table-iterator (next ht)
>         (lambda () (next))))
>
>     (let ((ii (hti-closure my-hash-table)))
>       (multiple-value-bind (found? key value) (funcall ii)
>         (when found?
>          (format t "First key value is ~a ~a~%", key value))))
>
> This won't work of course, but I was hoping there was a way to do the
> equivalent in LispWorks.
>
> Cheers,
> Chris Dean
>

--
Marco Antoniotti, Associate Professor
DISCo, Università Milano Bicocca
Via Bicocca degli Arcimboldi 8, U7, 4 piano
I-20126 Milan (MI) ITALY

Re: Returning a hash-table iterator from a function?

On Mon, 14 May 2007 12:01:23 +0200, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:

> Shameless plug.
>
> 	http://common-lisp.net/project/cl-enumeration/

I looked at the source and it seems it also just conses up lists of
the current keys and values of the hash table.  AFAIU this is not what
Chris wants.  (And I tend to think it's not possible in portable CL.)

Cheers,
Edi.

Re: Returning a hash-table iterator from a function?

Edi Weitz <edi@agharta.de> writes:
> On Mon, 14 May 2007 12:01:23 +0200, Marco Antoniotti <marcoxa@cs.nyu.edu> wrote:
>> 	http://common-lisp.net/project/cl-enumeration/
>
> I looked at the source and it seems it also just conses up lists of
> the current keys and values of the hash table.  AFAIU this is not what
> Chris wants.  (And I tend to think it's not possible in portable CL.)

Right, I'm trying to avoid creating a copy of the hash table keys.  I
also don't think that this is possible in portable Common Lisp.

What I'm looking for is a way to create an iterator into a hash table
that uses minimal consing and has indefinite extent.

Is there a non-portable LispWorks specific way to do this?

On further investigation I see that CLISP has sys::hash-table-iterator
that is used by the series package.  This might be an exampple of what
I want, but of course I can't find any documentation, etc.

Cheers,
Chris Dean

Re: Returning a hash-table iterator from a function?

Wade Humeniuk <whumeniu@telus.net> writes:
> Why not just pass the hash-table around. Why do you need the
> iterator?

Well, I could.  That's what I do now :).  But I'd like to have more of
an abstraction layer between the data types and the operators.  

For example, for some problems I use a disk based btree that has
similar semantics to a hash-table (that is, you can lookup key/value
pairs easily).  Mostly I can just switch to using a hash-table and the
code just works.  But there are some areas where there is a complex
looping construct that I'd like to use my normal Iterate looping macro
and I can't without changing the code from IN-HASHTABLE to IN-BTREE.

Hope that answers your question.

Cheers,
Chris Dean

Re: Returning a hash-table iterator from a function?

On 13 May 2007, at 23:27, Chris Dean wrote:

>
>
> Is there a way in LispWorks to return an iterator into a hash table
> from a function?  I don't think this is possible using standard CL.
>

I once had to do this, and I did something which was a bit horrible  
and somewhat consy but worked. for me.

What you do is to dress your hashtables up a bit so that instead of  
storing the value into the table you store a cons of (value . next).   
The result of that is that the values end up linked together into a  
list (the head of which you keep somewhere so you can iterate and add  
new values) which you can then keep pointers into.

If you modify values then you just change the cons rather than the  
table.

Iteration happens in predictable and non-hash order which may not be  
good.

Deletion is problematic.  What I did was, on deletion, to remove the  
hashtable entry, and to replace the value by a magic broken-heart  
value.  The iteration code then spots these and elides the dead  
cons.  Of course, if you never iterate, you never remove the dead  
conses.

The whole thing has potentially exciting thread-safety issues,  
although things like adding new elements during iteration is OK,  
because they always appear further up the list than you are.

Iterating over the table using this approach doesn't give you the  
keys.  You can fix that at the cost of an extra cons per entry of  
course.

--tim

Re: Returning a hash-table iterator from a function?

"Dmitriy Ivanov" <divanov@aha.ru> writes:
> Though dealing with the universal macro is a nice idea, but why do
> not you move the "point of dispatch" higher? I mean introducing a
> generic function (or functions) with methods specialized on the
> hash-table and btree correspondingly.

It's certainly a matter of taste and I only know what my tastes are.
The short answer is that I've tried both ways and I like one way
better.

For my last gig, I spent several years in a Scheme environment where
we had a large number of high level functions that worked on a variety
of data types.  We used the programming technique that you're
mentioning above.

When I follow the "higher level functions dispatched on type"
technique I often end up following two paths:

-  One implementation of an algorithm that uses functions like map,
   reduce, remove-if, best, etc that conses so much that performance
   if a problem.
-  Two implementations of the same algorithm that are both performant,
   but that are slightly out sync with each other.

Over time as the code stabilizes these problems disappear and we end
up with one performant implementation.  But it's nice during the few
weeks that a task is being developed to be able to change the data
structures easily.

Astute readers might be thinking about functional languages or
languages with iterators that solve this issue by allowing one
implementation to use less memory.  That's right of course!

Cheers,
Chris Dean