University of Cincinnati Logo
 

CS-4003 - Organization of Programming Languages
Electrical Engineering and Computer Science

Lab Hints
   Interfaces
Subclass the Salesperson and define a ManagerInterface interface requiring a double managerComputepay() method. Implement this interface in class SalesManager and define
   double computePay() {
      return super.computePay() + managerComputePay();
   }
in class SalesManager. Note: this may require declaring monthlysalary in this class as separate from the monthlysalary in the Manager class.
   Deadlock with threads
Add a third synchronized method to the Monitor class called release. This method can be used by one thread to release another. Change ping to cause an entering thread to release the other thread, then wait then, after being awakened (via the other thread's release method), confirm the other thread and release it a second time.

Still mystified? Try this hint.

   CollectorStream
Extend the Stream class. The constructor gets a Notifier object as argument. Maintain a collection of producers using a Vector or Hashtable or some other container and write a method that adds producers to this collection. In the run method visit all producers for their next output. When completed, the Notifier object should record the sum in a local variable and the CollectorStream object should put the Notifier object into its output stream. Since the Notifier object extends Stream, it can be carried anywhere and divulge its stored value on request.
   Reflection
See the bottom of the assignment for all the hints that you will need.
   Sieve for Prime Numbers
The sieve begins with the list of all numbers up to N. That is:
  2,3,4,5,6,7,...,N
So create a procedure called int-builder to do this:
  (define int-builder
    (lambda (n)
      (if (= n 1)
          '()
          (append ...))))
You will need a procedure to filter numbers from your current sieve list. For example, if the current list is
  2,3,4,5,6,7,8,9, ..., N
you will want to remove all multiples of 2 from the list to get
  3,5,7,9, ..., N
then filter 3 from what's left and so on. So create
  (define filter-out-mults
    (lambda (num lst)
      (if (null? lst)
          '()
          (if (= (modulo (car lst) num) 0)
              ...
              (cons (car lst) (filter-out-mults num (cdr lst)))))))
and test it like this:
  (filter-out-mults 2 (int-builder 20))
  ;Value: (3 5 7 9 11 13 15 17 19)
  (filter-out-mults 3 '(3 5 7 9 11 13 15 17 19))
  ;Value: (5 7 11 13 17 19)
  (filter-out-mults 5 '(5 7 11 13 17 19))
  ;Value: (7 11 13 17 19)
  (filter-out-mults 7 '(7 11 13 17 19))
  ;Value: (11 13 17 19)
and so on. Next you will want to perform this repeated task AND save all the numbers you filter because they are the prime numbers (the numbers to filter are always at the head of the current sieve). Create:
  (define sieve
    (lambda (lst)
      (if (null? lst)
          '()
          (cons (car lst) (sieve (filter-out-mults ...))))))
To generate primes up to the number N do this:
  (define primes (lambda (n) (sieve (int-builder n))))
Finally,
  (define stol
    (lambda (m)
      (let ((lst (primes (* m 20))))
         (take m lst))))
where
  (define take 
    (lambda (m lst)
      (if (= m 0)
	'()
	(cons (car lst) (take (- m 1) (cdr lst))))))
takes the first m numbers from list lst. Test it like this:
  (stol 100)
  ;Value: (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
  79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167
  173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263
  269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367
  373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
  467 479 487 491 499 503 509 521 523 541)
The next lab removes the awkward dependence of stol on knowing (a bound on) the minimum size of N that is needed to get the first M primes.
   Sieve for Prime Numbers with Streams
Create a stream counterpart to int-builder and call it int-builder$. This procedure will not have an if expression because an infinite list will be created. It will have a single argument that is the first number in the list.

Create a stream counter part to take and call it take$ like this:

  (define take$
    (lambda (m s)
      (if (or (= m 0) (null? s))
          '()
          (cons (car s) (take$ (- m 1) ((cdr s)))))))
and try it out like this:
  (take$ 10 (int-builder$ 2))
  ;Value: (2 3 4 5 6 7 8 9 10 11)
Create a stream counterpart to filter-out-mults and call it filter-out-mults$. Test it like this:
  (take$ 10 (filter-out-mults$ 2 (int-builder$ 2)))
  ;Value: (3 5 7 9 11 13 15 17 19 21)
  (take$ 10 (filter-out-mults$ 3 (filter-out-mults$ 2 (int-builder$ 2))))
  ;Value: (5 7 11 13 17 19 23 25 29 31)
and so on. Create a stream counterpart to sieve and call it sieve$. Test it like this:
  (take$ 10 (sieve$ (int-builder$ 2)))
  ;Value: (2 3 5 7 11 13 17 19 23 29)
Finally, create:
  (define stol$
    (lambda (n) 
      (take$ n (sieve$ (int-builder$ 2)))))
and try it out:
  (stol$ 100)
  ;Value: (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73
  79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167
  173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263
  269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367
  373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
  467 479 487 491 499 503 509 521 523 541)
   Multiply (escape) and Round Robin
  1. multiply: Use
      (let ((result (call/cc (lambda (k) (set! halt k) '())))) <body-of-let>)
    
    inside a procedure, say called tester. Define multiply recursively in the 'fail' expression of an if which is in the body of the let. Invoke (halt 0) to escape from multiply. Doing so sets a value of 0 for result causing termination if the test of if returns when result is not a procedure or is 0.

  2. round robin: The modified procedure might look like this:
    (define pl
      (lambda (l)
        (if (null? l)
            (remove-from-round-robin)
            (begin (step-and-swap (car l)) (pl (cdr l))))))
    
    and may be used like this:
    (define main
      (lambda lst
        (map (lambda (x) (create pl x)) lst)
        (demand-tokens)))
    
    where the purpose of create is to record a continuation of each invocation of pl (in the assignment example there are three calls to pl). Define a global variable produce that holds a list of these continuations. Create just adds each continuation to the list. The procedure demand-tokens might look like this:
    (define demand-tokens
      (lambda ()
        (let ((temp (demand)))
             (if (null? temp) '() (cons temp (demand-tokens))))))
    
    where the purpose of demand is to invoke the continuation at the head of produce (that is, ((car produce) ...)). To facilitate a return to demand define another global variable consume that holds demand's continuation. When the continuation (car produce) is invoked only one token of the input list of the associated call to pl is to be output, (car produce) must be moved to the end of the produce list and the continuation (car produce) must be called to continue the round-robin cycle. The procedure step-and-swap does this.

    Summary of procedures that may be defined:

    • create: inputs a function func and an argument arg that func is to be applied to. Grabs a continuation and saves it to consume. Calls add-to-round-robin to add a continuation to the produce list that will return control to the add-to-round-robin expression and then invoke func on args.
    • add-to-round-robin: grabs and adds to produce the continuation mentioned in create above, then invokes the continuation in consume which has the effect of immediately returning from create (that is, (func args) is not invoked).
    • demand: grabs a continuation and saves it to consume, then it invokes the continuation (car produce).
    • step-and-swap: takes as input a value, grabs a continuation k, removes (car produce), appends (list k) to produce, invokes the consumer continuation on value. Hence (step-and-swap (car l)) in pl will simply create a new continuation that, when invoked, will be followed by an immediate return from step-and-swap and then invocation of (pl (cdr l)).
    • remove-from-round-robin: removes (car produce) from produce and invokes a consumer continuation if there is one.
   Magic Square
Define variables s11, s12, s13, s14 to hold values given to row 1, columns 1-4, variables s21, s22, s23, s24 to hold values given to row 2, columns 1-4, s31, s32, s33, s34 same for row 3, and s41, s42, s43, s44 same for row 4. Limit the use of amb to no more than seven expressions. One way to do this is to use amb for values given to s11, s13, s14 then use
  (let* ((s12 (- 34 (+ s14 s13 s11))) ;; row 1
         ...)
     ...)
to assign a value to s12 to fill the 1st row. Next use amb to assign values to s23, s32 and force s41, s44 to have values like this:
  (let* (...
         (s41 (- 34 (+ s14 s23 s32))) ;; diagonal
         (s44 (- 34 (+ s11 s14 s41))) ;; outer box
         ...)
     ...)
Next use amb to assign a value to s22 which forces s33, s42, s43 like this:
  (let* (...
         (s33 (- 34 (+ s32 s22 s23))) ;; inner box
         (s42 (- 34 (+ s32 s22 s12))) ;; column 2
         (s43 (- 34 (+ s13 s23 s33))) ;; column 3
         ...)
     ...)
Finally, use amb to set a value for s34 which forces values for s24, s31, s21 like this:
  (let* (...
         (s24 (- 34 (+ s14 s34 s44))) ;; column 4
         (s31 (- 34 (+ s32 s33 s34))) ;; row 3
         (s21 (- 34 (+ s22 s23 s24))) ;; row 2
         ...)
     ...)

Parts of the code:

  • There should be a distinct? procedure that checks whether an element of one given list is a member of any of the other given lists, and calls to distinct? should be asserted, for example like this:
      (assert (distinct? s14 (list s13 s12 s11)))
    
  • The variables that are forced should be asserted to be between 1 and 16 like this:
      (assert (and (<= s24 16) (<= 1 s24)))
    
  • After all the assert expressions you can do this:
      (list (list s11 s12 s13 s14)
            (list s21 s22 s23 s24)
            (list s31 s32 s33 s34)
            (list s41 s42 s43 s44))
    
   Knapsack
Inputs and output will be lists of tuples of type inp :: [([Char], Double, Double)]. For example:
 inp = [("A",4,12),("B",2,1),("C",2,2),("D",1,1),("E",10,4)]::[([Char],Double,Double)]
A new list of objects of the same type can be constructed, one for each input tuple, where the middle element is the ratio of the last two elements of the input tuple. This can be done with a list comprehension that looks like this:
 manip lst = [ (name, v/w, w) | (name, v, w) <- lst ]
The result of manip inp needs to be sorted in decreasing order of the second element of the tuples. Recall the mergesort code which is here. That code is written for inputs of the following type:
 srt::(Num a, Ord a) => [a] -> [a]
It should be rewritten for the following types:
 srt :: Ord a => [(t, a, t1)] -> [(t, a, t1)]
and changed to sort downward instead of upward. Since the sort is on the second element of the tuple access to that element is needed. A function for this is the following:
 sec (_, x, _) = x
Then, in srt, instead of if (a < b) use if ((sec a) > (sec b). Finally, write
 knapsack :: (Fractional t, Ord t) => [([Char], t, t)] -> t -> [([Char], t, t)]
 knapsack lst w = drop 1 ans 
   where 
     ans = ("Start",w,0):[ (name, v-u, if (u < v-u) then u; else v)
                         | (name, r, u) <- sorted_list
                         | (crss, v, p) <- ans]
and sorted_list uses manip, the modified srt on u and v. An example use:
 *Main> knapsack inp 15
 [("E",11.0,4.0),("B",10.0,1.0),("C",8.0,2.0),("D",7.0,1.0),("A",-5.0,7.0)]
Note: the third element of the output tuples indicates how much weight each object will contribute to the total in the knapsack. The middle element of the output tuples is the remaining weight allowed for the knapsack. The -5.0 indicates completion of the run. The above knapsack code needs to be modified to prevent tuples with a negative second element, after the first one, from being in the output. This can be done several ways. The easiest way is to create a separate function to do it. The knapsack code must also be modified to express the weights of each object in the knapsack (only the last tuple will have a weight and value that is different).

Note: The above hint relies on a parallel list comprehension. To be able to use this feature start the interpreter like this:

  linux-prompt> ghci -XParallelListComp
I add the following line to my .bashrc file:
  alias ghci='ghci -XParallelListComp -XTypeSynonymInstances'
ERC
MainStreet
Paul Erdos
NIT
Ladies on Campus
Oscar Robinson