A dictionary data structure in the Logo language (key/value store)

Question

I'm wondering if there is an implementation of a first class dictionary data structure available for use in the Logo language? I don't see one available in the documentation of UCB Logo or FMS Logo. I see that there are property lists, but those don't appear to be first class, and it looks like they are linear look-up association lists. I'm looking for something based on hashes or trees. It seems like there have been lots of historical Logos out there, and maybe someone has implemented something like this. Also, if anyone knows of a repository of Logo code, I'd appreciate the pointers (i.e. CPAN for Logo).

Answer 1

Here's a real simplistic purely-functional tree implementation based on lists. Keys can be words or numbers. The empty list is the empty dictionary. It isn't self balancing so you'll have to call "rebalance" yourself to after doing inserts with "dict_add". Don't do that a lot since "rebalance" as implemented takes O(n) time. A procedure "testing" exercises things a little bit.

to dict_lookup :dict :key
   if (empty? :dict) [output []]
   localmake "pair first :dict
   if (empty? :pair) [output []]
   localmake "test_k first :pair
   if (equal? :key :test_k) [output last :pair]
   output dict_lookup (ifelse (before? :key :test_k) [left_tree :dict] [right_tree :dict]) :key
end

to left_tree :dict
    output item 2 :dict
end

to right_tree :dict
    output item 3 :dict
end

to dict_add :dict :key :value
    localmake "new_pair (list :key :value)
    if (empty? :dict) [output (list :new_pair [] [])]
    localmake "old_pair first :dict 
    localmake "old_key first :old_pair

    localmake "l_tree left_tree :dict
    localmake "r_tree right_tree :dict

    if (equal? :key :old_key) [output (list :new_pair :l_tree :r_tree)] 
    ifelse (before? :key :old_key) [
        localmake "l_tree dict_add l_tree :key :value] [
        localmake "r_tree dict_add r_tree :key :value]
    output (list :old_pair :l_tree :r_tree)
end

to in_order :dict
    if (empty? :dict) [output []]
    output (sentence (in_order (left_tree :dict)) 
                     (list (first :dict))
                     (in_order (right_tree :dict)))
end

to draw_tree :dict :size
    if (empty? :dict) [label [[]] stop]
    rt 50 fd :size lt 50
        draw_tree (left_tree :dict) :size * 0.7 
    rt 50 bk :size lt 50
    label (first :dict)
    lt 50 fd :size rt 50 
        draw_tree (right_tree :dict) :size * 0.7
    lt 50 bk :size rt 50
end

to list_to_tree :l
    if (empty? :l) [output []]
    localmake "half int (count :l)/2
    localmake "firsts take :half :l
    localmake "rests drop :half :l
    output (list (first :rests) (list_to_tree :firsts) (list_to_tree bf :rests))
end

to take :n :l
    if (or (empty? :l) (:n < 1)) [output []]
    output fput (first :l) take :n-1 bf :l
end

to drop :n :l
    if (:n < 1) [output :l]
    output drop :n-1 bf :l
end

to rebalance :dict
   output list_to_tree in_order :dict
end

to testing
    localmake "test_dict []
    localmake "items [[apple 1] [ball 2] [banana 3] [cat 4] [zebra 5] 
                      [toy 6] [yak 7] [jump 8]]
    foreach :items [make "test_dict (dict_add :test_dict (first ?) (first bf ?))]
    cs pu
    lt 60 fd 500 setheading 180 pd 
        draw_tree :test_dict 200
    pu lt 90 fd 700 setheading 180 pd 
        draw_tree (rebalance :test_dict) 160
end

Answer 2

It is true that in FMSLogo property lists are not first class citizens. However, property list "names" are first class. Also version 6.32.0 of FMSLogo does implement property lists as AVL trees. This is documented here: http://sourceforge.net/p/fmslogo/feature-requests/94/