Lab 7: Accelchain

Partners

For this lab, please do work with your homework partner. If your partner is not present, please inform a TA.

Immutable Hash Tables (20min)

We discussed association lists and binary search trees in the previous lab. An immutable hash table is is a map from keys to values, just like association lists and BSTs. However, under the hood, Racket does work to make lookups and inserts significantly faster. The hashtable-extras library defines the following functions. Download and use the library.

;; A [Hash-Table-of X Y] is a (make-hash (list (list X Y) ...))
;; where X is the key and Y is the value that the key maps to

;; make-hash : [List-of [List-of-Two X Y]] -> [Hash-table-of X Y]
;; Creates a hash table from a list of pairs.

;; hash-has-key? : [Hash-table-of X Y] X -> Boolean
;; Checks if a hash table has a key. Returns #true if it does, #false otherwise.

;; hash-ref : [Hash-table-of X Y] X -> Y
;; Returns the value associated with the key in the hash table.

;; hash-set : [Hash-table-of X Y] X Y -> [Hash-table-of X Y]
;; Returns a new hash table with the key mapped to the value.

;; hash-remove : [Hash-table-of X Y] X -> [Hash-table-of X Y]
;; Returns a new hash table with the key removed

;; hash-keys : [Hash-table-of X Y] -> [List-of X]
;; Returns a list of all the keys in the hash table

;; hash-values : [Hash-table-of X Y] -> [List-of Y]
;; Returns a list of all the values in the hash table

TA Demo. Design a function hash-update : [Hash-table-of X Y] X (Y -> Y) Y that updates the entry using the function if present and sets it to the default value otherwise.

;; hash-update : [Hash-table-of X Y] X (Y -> Y) Y
;; updates entry using function if present, else default

(check-expect (hash-update (make-hash (list)) "foo" add1 0)
              (make-hash (list (list "foo" 0))))
(check-expect (hash-update (make-hash (list (list "foo" 0) (list "bar" 0)))
                           "foo" add1 0)
              (make-hash (list (list "foo" 1) (list "bar" 0))))

(define (hash-update h k upd def)
  (hash-set h k (if (hash-has-key? h k) (upd (hash-ref h k)) def)))

1. In the previous homework, you wrote a function word-freq that counts how often a word appears in a list.¹ Rewrite this function to output a hash table instead.

   ;; word-freq : [List-of String] -> [Hash-table-of String Number]
   ;; computes frequency of all words in list
   (check-expect (word-freq empty) (make-hash empty))
   (check-expect (word-freq (list "foo" "bar" "foo" "baz" "bar"))
                            (make-hash (list (list "foo" 2)
                                             (list "bar" 2)
                                             (list "baz" 1))))
   

2. Use the following functions to test your implementation.

   ;; nat->alpha : Natural -> String
   ;; converts natural number to corresponding capital letter in alphabet
   ;; (check-expect (nat->alpha 0) "A")
   (check-expect (nat->alpha 0) "A")
   (check-expect (nat->alpha 26) "A")
   (check-expect (nat->alpha 25) "Z")
      
   (define (nat->alpha n)
     (string (integer->char (+ 65 (modulo n 26)))))
      
   ;; build-word-list : Number -> [List-of String]
   ;; computes a word list of the given size n, where
   ;; each character in the alphabet appears (n % 26) times
   (define ALPHABET (build-list 26 nat->alpha))
   (check-expect (build-word-list 0) (list))
   (check-expect (build-word-list 3) (list "A" "B" "C"))
   (check-expect (build-word-list 52) (append ALPHABET ALPHABET))
   (check-expect (build-word-list 27) (append ALPHABET (list "A")))
      
   (define (build-word-list n)
     (build-list n nat->alpha))
   

3. Use the time function to see how your implementation performs on large inputs. Start with small inputs and gradually build up to larger ones. See if you can characterize how the run time is changing.

TA Demo. It turns out that the natural implementation is rather slow for large inputs. There is no real reason to wait to update the frequency table until the recursive call returns. Instead, we can maintain the table so far as an accumulator argument and update it before the recursive call.

;; word-freq/fast : [List-of String] -> [Hash-table-of String Number]
;; computes frequency of all words in list, but faster

(define (word-freq/fast alos)
  (local ((define (word-freq/acc alos freq)
            (cond
              [(empty? alos) freq]
              [else (word-freq/acc (rest alos) (hash-update freq (first alos) add1 1))])))
    (word-freq/acc alos (make-hash empty))))

Notice that the else branch of word-freq/acc is just a recursive call to word-freq/acc. In particular, we never examine the results of the recursive call. This is called a tail call, which can often lead to a faster implementation.

Activity. Use time to compare the performance of this implementation to that of the previous one.

Balance Validation (70min)

For the remainder of the lab, we will be working on the helper functions outlined in Part 1.5 of of Accelchain. These helper functions will be useful for writing account-balances-ok?, which checks whether every transaction sends at least 1 accelcoin and every sender always has enough accelcoin to send.

;; A Ledger is a [Hash-Table-of PublicKey Nat]
;; A ledger maps wallet IDs (public keys) to the number of accelcoins they have.

;; reward : PublicKey Ledger -> Ledger
;; Grants the miner the reward for mining a block.

;; update-ledger/transaction: Transaction Ledger -> [Optional Ledger]
;; Updates the ledger with a single transaction. Produces #false if
;; the sender does not have enough accelcoin to send.

;; update-ledger/block : Block Ledger -> [Optional Ledger]
;; Updates the ledger with the transactions in a block, and rewards the miner.

;; update-ledger/blockchain : Blockchain Ledger -> [Optional Ledger]
;; Produces the ledger for a blockchain, or #false if any of the transactions in
;; the blockchain are invalid (i.e., the sender doesn't have enough accelcoin).