Assignment 2 - Common Lisp (due Sun 9 Dec 2012)

1. Design an abstract data type for dictionaries, i.e., key-value stores. An ordered tree should be used for representation You should have at least the following operations (all purely functional)

• create-dictionary &key compare - create a new empty dictionary with compare being the comparison function to be used for keys. The comparison function should take two keys and return one of the atoms LT, EQ, GT to express the relationship between the keys. If compare is not given, assume that the keys are strings (string= and string< can be used for comparison).
• lookup key dict &key default - find value for key, return default if it does not exist. Return nil if no default value is given.
• update key value dict - return a new dictionary where key now maps to value, regardless of if it was present before.
• fold fun dict initial - fold the key-value pairs of the dictionary using the function fun. fun should take three arguments: key, value and sofar (in this order) which is the accumulated value so far. initial is the initial value for sofar. Please note that order of application is (or at least should be) not relevant.
• rebalance dict - return a new dictionary that is more balanced (if needed). This could be run when needed as part of update as well.
• keys dict - return the keys of the dictionary in a list. The order of the keys is not relevant.
• Write a function samekeys dict1 dict2 that determines if dict1 and dict2 contain the same set of keys. Take care to make it efficient, i.e., do not construct unnecessary large intermediate data structures. samekeys should use the compare function, which should be the same for the two dictionaries and can be assumed to behave 'in the right way' for its two arguments (i.e. EQ return value implies that the arguments can be swapped and the result is still EQ, GT implies that if the arguments are swapped the return value will be LT and vice-versa).

Task 1

Write a macro with-keys (key value dict) body, which evaluates body once for each key-value pair in the dictionary from the previous exercise. key and value should be bound to each key-value pair.

Example:

* (defun my_comp (a b) (cond ((< a b) 'LT) ((= a b) 'EQ) (t 'GT)))
MY_COMP

* (let ((d (update 2 4 (update 1 2 (create-dictionary :compare #'my_comp))))) (with-keys (k v d) (format t "~D~%" (+ k v))))
6
3
NIL

The last line could be different, depending on what you return after you have done 'folding' over the dictionary. Also the order of the two results could be different.

Task 2

Write a macro match-pattern expr (pattern_1 body_1) (pattern_2 body_2) .. (pattern_n body_n) that evaluates expr and then tries to match the result against pattern_i. If it succeeds body_i is evaluated with the free variables in pattern_i bound during the evaluation. A pattern is a general S-expression, where a symbol is a variable and can match anything. A quoted structure must match exactly (and thus contains no variables). Note that a variable can occur several times in a pattern and must then have the same value. Since 'sexpr expands to (quote sexpr), the symbol quote can not be used as a variable. This is ok, as is disallowing t and nil as variables. Note that expr should only be evaluated once.

Example:

* (match-pattern '((foo bar) foo baz)
                 ((car . car) `(:cons ,car ,car))
                 ((one two three) `(:three ,one ,two ,three)))

(:THREE (FOO BAR) FOO BAZ)