Solutions to the fourth homework assignment

Exercise 3.6.1 An implementation of an abstract data type for finite functions, using the "ribcage" representation described in section 3.6.3.

(define create-empty-ff
  (lambda ()
    (list 'empty-ff '())))

(define extended-ff*
  (lambda (sym-list val-vector old-ff)
    (list
      'extended-ff
      (list (list sym-list val-vector) old-ff))))

(define apply-ff
  (lambda (ff symbol)
    (form-case ff
      (empty-ff (ff) (error
		       'apply-ff
		       "No association for ~a" symbol))
      (extended-ff (ff)
	(let ((assoc-list (car ff)))
	  (let ((sym-list (car assoc-list)))
	    (let ((val-vector (cadr assoc-list)))
	      (let ((val (ribassoc symbol sym-list val-vector
			   '*fail*)))
		(if (eq? val '*fail*)
		  (apply-ff (cadr ff) symbol)
		  val))))))
      (else  (error 'apply-ff "Invalid finite function")))))

(define ribassoc
  (lambda (s los v fail-value)
    (letrec ((helper (lambda (los index)
                       (cond ((null? los) fail-value)
                             ((eq? s (car los)) (vector-ref v index))
                             (else (helper (cdr los) (+ index 1)))))))
      (helper los 0))))

Exerise 4.6.1

(define make-stack
  (lambda (n)
    (let ((stk (make-vector n))
	  (index -1))
      (lambda (message)
	(case message
	  ((empty?) (lambda () (= index -1)))
	  ((push!) (lambda (x)
		     (set! index (add1 index))
		     (if (> index n)
		       (error 'push! "Stack size exceeded!")
                       (vector-set! stk index x))))
	  ((pop!) (lambda () (if (= index -1)
			       (error 'pop! "Stack empty!")
			       (let ((val (vector-ref stk index)))
				 (set! index (sub1 index))
				 val))))
	  ((top) (lambda () (if (= index -1)
			      (error 'top! "Stack empty!")
			      (vector-ref stk index))))
	  (else (error
		  'make-stack
		  "Unknown message to stack ADT encountered!")))))))

Exercise 4-6-2 The finite function data representation is a list of pairs. To extact the value, we use assoc. The extend operation takes one symbol and one asociated value, and extends the finite function.

(define make-ff
  (lambda ()
    (let ((ff '()))
      (lambda (message)
	(case message
	  ((empty?) (lambda ()
		      (null? ff)))
	  ((extend) (lambda (sym val)
		      (set! ff (cons (list sym val) ff))
		      "Finite function extended!")) ;hides representation
	  ((apply) (lambda (sym)
		     (let ((val (assoc sym ff)))
		       (if val
			 (cadr val)
			 (error 'apply "No association for ~a"
			   sym)))))
	  (else (error 'make-ff "Unknown message encountered!")))))))

Vikram Subramaniam, 1995