EECS 321 Programming Languages: Homework Ω

Part 1 – Threads

Add spawn, deliver and receive forms to RFAE.

   <TRFAE> = <number>
           | {+ <RFAE> <RFAE>}
           | {- <RFAE> <RFAE>}
           | {fun {<id>} <RFAE>}
           | {<RFAE> <RFAE>}             ;; function application
           | <id>
           | {with {<id> <RFAE>} <RFAE>} ;; shorthand for fun & app
           | {struct {<id> <RFAE>} ...}  ;; all fields must be distinct
           | {get <RFAE> <id>}
           | {set <RFAE> <id> <RFAE>}
           | {spawn <RFAE>}
           | {deliver <RFAE> <RFAE>}
           | {receive}
           | {seqn <RFAE> <RFAE>}

All of the rules of homework 6 apply here.

A spawn form creates a new thread. A deliver expression sends the value of its second expression to the thread given in its first expression. This expression does not wait for the delivery to complete. A receive operation waits for a delivery and then returns it.

Also extend parse to support the new operations.

Define the usual interp-expr, which takes an expression and interprets it with an empty initial deferred substitution and empty initial store. Instead of returning a value, it returns a list of values, one for each thread that was created. The list may be in any order but it must have an element for each thread that was created during the evaluation of the program.

If any of the threads raise an error, the entire call to interp-expr must raise an error; the results of other threads are ignored. If a thread evaluates {receive} and no other thread ever delivers to it, interp-expr must return a list containing 'blocked. If a threads result is itself a thread, the result list must contain 'thd.

Your implementation must not use threads or mutation at the PLAI level. It may not have the letters thread appearing together in that order in the source.

Deliveries must be made in order. The first value delivered to a thread must be the first value received by that thread.

deliver's result is the value that was delivered to the other thread.

spawn runs in the same scope as its enclosing expression

Some examples (these are just a few to think about; this does not constitute anything near a comprehensive test suite):

    (define (same-elements? l1 l2)
      (define (sub-mutiset? l1 l2)
        (cond
          [(null? l1) #t]
          [else (and (member (car l1) l2)
                     (subset? (cdr l1) (remove (car l1) l2)))]))
      (and (sub-mutiset? l1 l2) (sub-mutiset? l2 l1)))

    (test (same-elements?
           (interp-expr (parse `{seqn {spawn 1} 2}))
           (list 1 2))
          #t)

    ;; spawn's argument is in the same scope as the spawn expression
    (test (same-elements?
           (interp-expr (parse `{with {x 1} {seqn {spawn x} 2}}))
           (list 1 2))
          #t)

    ;; deliveries must be made in order
    (test (same-elements?
           (interp-expr
            (parse `{with {t1 {spawn {seqn {receive} {receive}}}}
                          {seqn {deliver t1 1}
                                {seqn {deliver t1 2}
                                      3}}}))
           (list 2 3))
          #t)


    ;; if the result of evaluation of a thread is a thread,
    ;; the interpreter returns 'thd
    (test (same-elements? (interp-expr (parse '(spawn 1)))
                          (list 'thd 1))
          #t)          

    ;; exceptions raised in a thread kill the entire program
    (test/exn (interp-expr (parse '{spawn {0 0}}))
              "application expected procedure")

    ;; these two tests make sure that your implementation
    ;; doesn't commit to a particular thread forever
    (test/exn (interp-expr
               (parse '{seqn {spawn {{fun {x} {x x}} {fun {x} {x x}}}}
                             {0 0}}))
              "application expected procedure")

    (test/exn (interp-expr
               (parse '{seqn {spawn {0 0}}
                             {{fun {x} {x x}} {fun {x} {x x}}}}))
              "application expected procedure"))

Part 2 – Errors

There is one new kind of error introduced over the ones in homework 6, when deliver's first argument is not a thread. In that case, the interpreter must raise an error that has this string:

deliver expected thd

Your parser will be supplied only well-formed TRFAE programs, according to the grammar above.

Part 3 – Advice

There are many different ways to structure your interpreter to solve this homework. Nevertheless, I recommend you start with these definitions:

(define-type RCFAE-Value
  [numV (n number?)]
  [closureV ...]
  [recV ...] ;; records

  ;; thd values hold the location in the
  ;; store where undelivered values wait
  ;; to be delivered
  [thdV (address number?)])

(define-type Store 
  [mtSto]
  [aSto (address integer?)
        (value (or/c RCFAE-Value?

                     ;; lists mean that this
                     ;; location in the store
                     ;; belongs to a thd
                     (listof RCFAE-Value?)))
        (rest Store?)])

(define-type Thds*Store
  [thds*store (thds (listof Thd?)) (store Store?)])

;; the tid's are the store locations for those thds
(define-type Thd
  [active (tid integer?) (go (-> Store? Thds*Store?))]
  [blocked (tid integer?) (continue (-> RCFAE-Value? Store? Thds*Store?))]
  [done (v RCFAE-Value?)])

Also, try using this contract for the helper interpreter function (the one that does the actual work of interpreting expressions).

  (-> RCFAE? DefrdSub? integer? Store?
      (-> RCFAE-Value? Store? Thds*Store?)
      Thds*Store?)

The integer? argument is the location in the store where the current thread is allocated.

Part N – Handin instructions

Provide a definition of interp-expr : RFAE -> number or 'procedure or 'struct, as above.

Provide a definition of parse : sexpression -> RFAE, as usual (no extra n-ary functions this time, but do include with as a parser transformation)

Do not include any useless code in your handed in assignment. That is, if you start with you previous assignment's code, remove code that implemented features from previous assignments that are not present in this one.

There is no second try for this assignment.


Last update: Wednesday, March 8th, 2017
stamourv@eecs.northwestern.edu