Cadence.com will be under maintenance from Friday, Oct. 3rd at 6pm (PST) thru Sunday, Oct 5th at 11pm (PST).
Cadence.com login, registration, community posting and commenting functionalities will be disabled.
Home > Community > Blogs > Custom IC Design > skill for the skilled how to copy a hash table
 
Login with a Cadence account.
Not a member yet?
Create a permanent login account to make interactions with Cadence more convenient.

Register | Membership benefits
Get email delivery of the Custom IC Design blog (individual posts).
 

Email

* Required Fields

Recipients email * (separate multiple addresses with commas)

Your name *

Your email *

Message *

Contact Us

* Required Fields
First Name *

Last Name *

Email *

Company / Institution *

Comments: *

SKILL for the Skilled: How to Copy a Hash Table

Comments(6)Filed under: SKILL, Team SKILL, programming, LISP, SKILL++, IC615, Jim Newton, SKILL for the Skilled, hash tableIn this posting I want to look at ways to copy a hash table in SKILL. There are several ways you might naively try to do this, but some of these naive approaches have gotchas which you should be aware of.

In the following paragraphs several inferior functions will be presented: portable_1, copyTable_2, copyTable_3, copyTable_4, and copyTable_5. Finally three useful robust functions will be presented (copyTable, getHashDefault, and getHashPrintName)which you, the reader, can copy (attach a customer specific prefix to) and use in your own programs.

Copy by iteration

The first way you might try to implement the function copyTable is as follows.
(defun copyTable_1 (hash)
  (let ((new (makeTable 'copy)))
    (foreach key hash
      new[key] = hash[key])
    new))

The function copyTable_1 works perfectly for most applications for which you might want to use it. This approach, unfortunately, has several limiting corner cases which might be important.

Troublesome hash keys

In some sense this example reminds me of little Bobby Tables from xkcd.


The problem is that if you are not in control of the data, then you don't know what might be in there.

If the function copyTable_1 is defined as shown above, it will fail if either of the following keys are found in the hash table: ?, ??, or unbound. While it is indeed unlikely that most people would ever encounter this case, it is nevertheless something to consider if you want your implementation of copyTable which is robust and general purpose.

Try the following test case and see what happens.

(let ((table (makeTable 'x)))
  table[?] = 1
  table[??] = 2
  table['unbound] = 3 
  (copyTable_1 table))

*Error* eval: unbound variable - key
<<< Stack Trace >>>
(new[key] = hash[key])
foreach(key hash (new[key] = hash[key]))
let(((new makeTable(&))) foreach(key hash (new[key] = hash[key])) new)
copyTable_1(table)
let(((table makeTable(&))) (table[?] = 1) (table[??] = 2) (table['unbound] = 
3) copyTable_1(table))

Using the unbound is easier in SKILL++

The resulting stack-trace is admittedly confusing.

The error is triggered because foreach encounters the symbol unbound in the hash table. On doing so, it effectively sets the variable key to unbound, as if by (key = 'unbound). Thereafter new[key] contains a reference to an unbound variable. In SKILL, an error is triggered if an attempt is made to evaluate a variable whose value is the symbol: unbound.

To demonstrate this to yourself, try the following in SKILL.

(inSkill
  (let ((key 'unbound))
    (printf "the value is [%L]\n" key)))


*Error* eval: unbound variable - key
<<< Stack Trace >>>
printf("the value is <%L>\n" key)
let(((key 'unbound)) printf("the value is [%L]\n" key))
inSkill(let(((key &)) printf("the value is [%L]\n" key)))

This problem is easily avoided by using SKILL++. In SKILL++ the unbound symbol is not special: it is a supported feature to set a variable to the symbol unbound, and to evaluate the variable thereafter. Try the same example as above, but using in inScheme rather than inSkill.

(inScheme
  (let ((key 'unbound))
    (printf "the value is [%L]\n" key)))


the value is [unbound]

Redefine the function in SKILL++

We can fix the problem associated with the unbound symbol simply by defining the function either in a .ils file or by surrounding the definition with (inScheme ...).
(inScheme
  (defun copyTable_2 (hash)
    (let ((new (makeTable 'copy)))
      (foreach key hash
        new[key] = hash[key])
      new)))
Now if we run the same test again we see a different result.
(let ((table (makeTable 'x)))
  table[?] = 1
  table[??] = 2
  table['unbound] = 3 
  (copyTable_2 table))

table:copy

More troublesome hash keys: ? or ??

If we test a bit further we find that it has failed for another subtle reason. We can use the tableToList function to examine all the key/value pairs in a hash table. Notice that the content of the original list and the content of the copy are not the same.
(let ((table (makeTable 'x)))
  table[?] = 1
  table[??] = 2
  table['unbound] = 3

  (printf "contents of original:\n--> %L\n"
          (tableToList table))
  (printf "contents of copy:\n--> %L\n"
          (tableToList (copyTable_2 table))))


contents of original:
--> ((unbound 3) (? 1) (?? 2))
contents of copy:
--> ((unbound 3) (? (unbound ? ??)) (?? (unbound 3 ? 1 ?? 2)))

This is not something you normally need to worry about, because if you created the hash table in your SKILL application, then you probably know that neither ? nor ?? is a hash key in your table. However, if the goal is to write a general purpose function for copying any given hash table, then this is an exotic case you must consider.

Why the crazy behavior?

It is not so difficult to understand this crazy behavior. It is because ? and ?? have special meanings to the functions arrayref, get, getq and a few more functions. The following expressions do not retrieve the value of the hash key ?. Rather they all return the list of hash keys.
hash->?
hash[?]
(arrayref hash ?)
(get hash ?)
(getq hash ?)
Similarly hash->?? does not retrieve the value associated with the key ??, it instead returns a special list which embeds they hash keys and values.

This means the line new[key] = hash[key] within the previous versions of copyTable does something special with the value of the variable key is ? (or ??). It does the following: new[?] = hash[?], which assigns the ? key of the new hash table to the list of keys in the old hash table.

Use append with hash tables

To fix this problem, take advantage of the feature of the append SKILL function. It can append two hash tables.
(defun copyTable_3 (hash)
  (let ((new (makeTable 'copy)))
    (append new hash)
    new))
But since, append returns its first argument if the first argument is a hash table, copyTable_3 can be made much simpler.
(defun copyTable_4 (hash)
  (append (makeTable 'copy) 
          hash))
The append function does not have a problem when it encounters the symbols ?, ??, or unbound. Take a look at the same example using copyTable_4.
(let ((table (makeTable 'x)))
  table[?] = 1
  table[??] = 2
  table['unbound] = 3

  (printf "contents of original:\n-->%L\n"
          (tableToList table))
  (printf "contents of copy:\n-->%L\n"
          (tableToList (copyTable_4 table))))


contents of original:
-->((unbound 3) (? 1) (?? 2))
contents of copy:
-->((unbound 3) (? 1) (?? 2))

Even if you are not worried about the special, extremely unlikely hash keys discussed above, using append to copy hash tables makes for smaller and faster code.

Preserving the table name

Depending on how good a copy you need, you might also want the new table to print the same as the original table. Look at this example. One prints as table:data and the other as table:copy.
(let ((table (makeTable 'data)))
  (printf "original: %L\n" table)
  (printf "copy:     %L\n" (copyTable_4 table)))


original: table:data
copy:     table:copy

To fix this problem we need to pass the correct value to makeTable within the copyTable function as follows.

(defun copyTable_5 (hash)
  (append (makeTable (getHashPrintName hash))
          hash))
Here is an implementation of the function getHashPrintName which returns the print name of the given hash table. If the table prints as table:myname, getHashPrintName returns the string "myname".
(defun getHashPrintName (hash)
  (substring (sprintf nil "%L" hash)
             7))
If we test copyTable_5 we see that the two tables do print the same way.
(let ((table (makeTable 'data)))
  (printf "original: %L\n" table)
  (printf "copy:     %L\n" (copyTable_5 table)))


original: table:data
copy:     table:data

Preserving the default value

There is one more important difference between the two hash tables (the one given to copyTable_5 and the one it returns). The difference is how the hash tables behave when accessing a missing key. Take a look at this example.
(letseq ((table (makeTable 'data 0))
         (copy (copyTable_5 table)))
  (printf "default from original: %L\n" table[42])
  (printf "default from copy:     %L\n" copy[42]))


default from original: 0
default from copy:     unbound
You see that if the original hash table was created with a second argument to makeTable, then the copy is liable to return a wrong default value. To fix this problem is a bit challenging but interesting.

We need to pass a second argument to the call to makeTable within copyTable. Moreover, we need to pass the correct value for this second argument, based on the given table. Unfortunately, there is no built-in function in SKILL which will access the default value of a hash table.

Calculating the default value of a hash table

The following function returns the default value of the hash table. It is pretty efficient, and works on the following algorithm.
  • Choose a token key; we use the symbol t in this case, but any key would work.
  • Save away the length of the hash table, by calling (length hash).
  • Save away the value of hash[t].
  • Call (remove hash t) to delete the t key from the table if it is there. If t is not a hash key, no harm done.
  • Evaluate hash[t] once t has been removed. That access will return the default value which we want getHashDefault to return.
  • Determine whether t was in the table at the start by comparing the hash table size before and after deleting the t key.
  • Before getHashDefault returns the default value, restore t to the hash table if and only if it was there originally.

To return a particular value from a SKILL function but first do some cleanup, use prog1.

To do the restoration we save the old value of hash[t] before calling remove, then check the length of the hash before and after calling remove. If the length of the hash changed, then t was a key originally, so restore the value to the saved value. Otherwise, there is no need to restore anything.

(defun getHashDefault (hash)
  (let ((old_size (length hash))
        (old_value hash[t]))
    (remove t hash)
    (prog1 hash[t]
      (unless ((length hash) == old_size)
        hash[t] = old_value))))

A working version of copyTable

All that remains to have a working version is to update copyTable to make use of getHashDefault.
(defun copyTable (hash)
  (append (makeTable (getHashPrintName hash)
                     (getHashDefault hash))
          hash))
We can test it to make sure it works.
(letseq ((table (makeTable 'data 0))
         (copy (copyTable table)))
  (printf "default from original: %L\n" table[42])
  (printf "default from copy:     %L\n" copy[42]))


default from original: 0
default from copy:     0

Summary

In this blog post we saw several things when trying to implement a robust version of copyTable.
  • How to find the default value of a hash table
  • How to find the print name of a hash table
  • How the symbol unbound behaves differently in SKILL vs SKILL++
  • How the symbols ? and ?? behave as hash keys.
  • Some details of the SKILL function makeTable, in particular the first and second arguments.
  • How append and remove work with hash tables.
  • How to use the function tableToList to serialize the contents of a hash table.

Jim Newton

Comments(6)

By Andrew Beckett on August 29, 2013
I started reading this, thinking "why doesn't he just use append?" - so good to see that this is where you were heading...

At one point, this capability of append wasn't documented, but that seems to have been corrected now.

I like the way of finding the default value of a hash!

Andrew.


By Team SKILL on August 30, 2013
Hi Andrew, I really have to give some credit to Hank Jones.  I was in a discussion with him where we together came up with this way of getting the hash default value.  The way I originally suggested such much more compute intensive.
Jim

By Julien Faucher on October 10, 2013
Any way the append approach could be made to work recursively. I happen to have a table with some tables down the hierarchy...


By Team SKILL on October 11, 2013
Hi Julien, thanks for the question.  Copying recursive usually needs to be done according to the semantics of your application.  I.e., how deep do you want to copy, what types of objects do you want to descend into, how to detect circularity, what to do with duplicate elements, etc.  If you can give me more details of your particular application, I'll be happy to make some suggestions.

Jim


By Julien Faucher on October 11, 2013
Hi Jim,

First, thank you for your answer. Ideally, I'd want the copyTable function to be generic so assume it might have to go down many levels. This is why I thought about using recursion. The object I want to descend into at each level is just another table. Circularity might be a problem with recursion, but without going into the specifics of my data structure, let's assume there won't be any. The examples below illustrate the problem I have:

First, let me define the functions I will be using. The first three functions are from above in this thread. The last one is copyTable_1 modified to support recursion.

(defun getHashPrintName (hash)

 (substring (sprintf nil "%L" hash)

            7))

(defun getHashDefault (hash)

 (let ((old_size (length hash))

       (old_value hash[t]))

   (remove t hash)

   (prog1 hash[t]

     (unless ((length hash) == old_size)

       hash[t] = old_value))))

(defun copyTable (hash)

 (append (makeTable (getHashPrintName hash)

                    (getHashDefault hash))

         hash))

procedure(jfCopyTable(hash)

 let( (newT)

   newT = makeTable(getHashPrintName(hash) getHashDefault(hash))

   foreach(key hash

     if(tablep(hash[key]) then

       newT[key] = jfCopyTable(hash[key])

     else

       newT[key] = hash[key]

     )

   )

   newT

 )

)

Now here are the examples to illustrate what I want to do. Example 2b, with jfCopyTable, is the behavior I would ideally want from copyTable():

Example 1a:

x = makeTable(`foo nil)

x->a = "a"

x->b = "b"

y = x

y->a = "a_overwrite"

x->??

 (a "a_overwrite" b "b")

Example 1b:

x = makeTable(`foo nil)

x->a = "a"

x->b = "b"

y = jfCopyTable(x)

y->a = "a_overwrite"

x->??

 (a "a" b "b")

Example 2a:

x = makeTable(`foo nil)

x->a = "a"

x->b = "b"

y->a = "a"

y->b = "b"

y->x = x

y->x->a = "a_overwrite"

x->??

 (a "a_overwrite" b "b")

Example 2b:

x = makeTable(`foo nil)

x->a = "a"

x->b = "b"

y = makeTable(`foo nil)

y->a = "a"

y->b = "b"

y->x = x

z = jfCopyTable(y)

z->a = "c"

y->??

 (a "a" b "b")

z->x->a = "a_overwrite"

; x is not impacted because z was copied recursively in jfCopyTable()

x->??

 (a "a" b "b")

I am happy with jfCopyTable() in my current application, but for the function to be as generic as possible, I would like to use the append approach to support the ? and ?? cases in case it happens down the road.

Thanks,

Julien


By Team SKILL on October 14, 2013
Hi Julien, You might consider using the tableToList function to first

serialize the hash table.  You can actually pass this serialization

back to append later to populate the new hash table, but in the mean

time you can examine it, finding embedded tables and copy them

recursively.  Here is an example of how you might do that.

(defun copyObjRec (obj)

 (cond

   ((tablep obj)

    (append (makeTable (getHashPrintName obj)

                       (getHashDefault obj))

            (foreach mapcar pair (tableToList obj)

              (list (car pair)

                    (copyObjRec (cadr pair))))))

   (t

    obj)))

This approach has some limitations.  1) If the default value is

another hash table, that table needs to be copied. 2) You might want

other types of data structures also coped.  E.g., if a value in the

table is a list, that list may need to be copied (depending on the

requirements of your application.  In particular that list might

contain yet another hash table. 3) There may be hash keys which also

need to be copied.  It is impossible to have a hash table as a key to

a hash table, but certainly lists are valid hash keys.

These three issues are addressed in the version of copyObjRec below.

In addition, you can extend the (cond ...) to also include other types

of data which you want to copy such as defstructs, standard objects,

pcre compiled regular expression objects, etc.

(defun copyObjRec (obj)

 (cond

   ((tablep obj)

    (append (makeTable (getHashPrintName obj)

                       (copyObjRec (getHashDefault obj)))

            (foreach mapcar pair (tableToList obj)

              (mapcar copyObjRec pair))))

   ((listp obj)

    (mapcar copyObjRec obj))

   ;; extend this cond as necessary

   ;; ...

   (t

    obj)))
 
Kind Regards
Jim


Leave a Comment


Name
E-mail (will not be published)
Comment
 I have read and agree to the Terms of use and Community Guidelines.
Community Guidelines
The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.