MIT Scheme Message Passing Abstraction

问题:

In a Computer Science course I am taking, for homework, we were tasked with several different questions all pertaining to message passing. I have been able to solve all but one, which asks for the following:

Write a mailman object factory (make-mailman) that takes in no parameters and returns a message-passing object that responds to the following messages:

• 'add-to-route: return a procedure that takes in an arbitrary number of mailbox objects and adds them to the mailman object's “route”
• 'collect-letters: return a procedure that takes in an arbitrary number of letter objects and collects them for future distribution
• 'distribute: add each of the collected letters to the mailbox on the mailman's route whose address matches the letter's destination and return a list of any letters whose destinations did not match any mailboxes on the route (Note: After each passing of 'distribute the mailman object should have no collected letters.)

Some remarks that are given to make the code easier include:

• If multiple letters are distributed to the same mailbox in one distribution round, any one of them may be the “latest” letter whose message is returned by passing 'get-latest-message to the mailbox.

• No two mailboxes will have the same address.

• No mailbox or letter will be passed to the mailman more than once.

• The bad letters returned by distribute do not need to be in a specific order.

• Use the . args syntax for accepting arbitrary amount of arguments.

This is what I have been able to figure out for myself:

(define (make-mailman)
  (let ((T '()))
    (define (route-adder . mobjects)
      (assoc mobjects T))
    (define (letter-collecter . lobjects)
      (assoc lobjects T))
    (define (add-to-route mobjects)
      (begin (set! T (cons (route-adder . mobjects) T)) 'done))
    (define (collect-letters lobjects)
      (begin (set! T (cons (sort-strings (letter-collecter . lobjects)) T)) 'done))
    (define (dispatch z)
      (cond ((eq? z 'add-to-route) add-to-route)
        ((eq? z 'collect-letters) collect-letters)
        ((eq? z 'distribute) "unsure of what to do here")
        (else "Invalid option")))
    dispatch))

Any help that can be given to me here will be appreciated, as I have tried looking at this problem for a while, and cannot figure out what to do from here.

回答1:

Your code has all kinds of mix-ups. :) Let's proceed step by step.

The dispatch bit is almost OK:

(define (make-mailman)
 (let ...
  ...
  (define (dispatch msg)                ;; use short but suggestive var names
   (cond 
    ((eq? msg 'add-to-route)    add-to-route)
    ((eq? msg 'collect-letters) collect-letters)
    ((eq? msg 'distribute) 
       ;; "unsure of what to do here" <<-- Distribute the letters, what else?
                                distribute-the-letters)
    (else "Invalid option")))
  dispatch))

With such objects, a sample call will be (define ob (make-mailman)) and then ((ob 'add-to-route) box1 box2 ... boxn) etc. So add-to-route procedure must be defined this way:

(define (make-mailman)
 (let ((self (list '(ROUTE)           ; each mailman has a route, and a mailbag
                   '(MAILBAG))))      ; use suggestive name here (T, what T?)
  ...
  (define (add-to-route . mailboxes)
    (let ((route (assoc 'ROUTE self))) 
      (set-cdr! route
          (append mailboxes           ; there will be no duplicates
            (cdr route)))
      'DONE))

Right? Same with the letters:

  (define (collect-letters . letters)
    (let ((mailbag (assoc 'MAILBAG self)))
      .....
      'DONE))

Now we can deal with the missing part, distribute-the-letters:

  (define (distribute-the-letters)
    ;; for each letter in my mailbag
    (let* ((mailbag (assoc 'MAILBAG self))
           (mailboxes (cdr (assoc 'ROUTE self)))
           (letters (cdr mailbag)))
      (if (null? letters) ()
        (let loop ((letter  (car letters))
                   (letters (cdr letters))
                   (not-delivered ()))
    ;;   access its address, 
          (let* ((address (letter 'get-address))
            ;; (we assume it supports this interface, 
            ;;   or maybe that's part of a previous assignment)
    ;;     and find a mailbox on my route such that
                 (mbx (find-mailbox address mailboxes)))
    ;;     its address matches the letter's
    ;;     and if so,
             (if .....
    ;;        put that letter into this mailbox: 
               ((mbx 'put-letter) letter)
    ;;            (we assume it supports this interface, 
    ;;             or maybe that's part of a previous assignment)
    ;;     but if not, add letter to the "not-delivered" list
               ..... )
            (if (null? letters)
    ;; having emptied the mailbag, return the "not-delivered" list
              (begin (set-cdr! mailbag nil) not-delivered)
              (loop (car letters) (cdr letters) not-delivered)))))))

We assume that both letter and mailbox objects support the message type 'get-address to which they both return the same comparable address type of object, and that mailbox objects support 'put-letter message.

回答2:

Other than the specifics of the message functionality, it looks like you've nailed it. There are however some errors:

This (route-adder . mobjects) should be (router-adder objects) and similarly for (letter-collector . lobjects).

The use of begin is unneeded. The body of a (define (func . args) <body> ...) is implicitly enclosed in a begin.

Idiomatically your code could be written as:

(define (make-mailman)
  (let ((T '()))
    ;; ...
    (lambda (z)
      (case z
        ((add-to-route)    add-to-route)
        ((collect-letters) collect-letters)
        ((distribute)      distribute)
        (else (error "Invalid option"))))))

[but you may not know about case nor lambda yet...]

As for solving the actual messaging functionality. You are going to need to maintain a set of mailboxes where each mailbox is going to hold a set of letters. A letter will presumably consist of an address and some content (extra credit for a return-address). The distribute behavior will check the address on each letter and deposit it in its mailbox. The mailman will need to hold letters (while on his route collecting-letters) until instructed to distribute.

For this you might start by building up the lower-levels of the functionality and then using the lower-levels to build up the actual message passing functionality. Starting like, for example:

(define (make-letter addr content)
  `(LETTER ,addr ,content))
(define letter-addr cadr)
;; ...

(define (make-mailbox addr)
  '(MBOX ,addr))
(define mailbox-letters cddr)
(define (mailbox-letters-add mailbox letter)
  (set-cdr! (cdr mailbox) (cons letter (mailbox-letters mailbox))))

;;...