Week 11 solutions LAB === There aren't really any answers; this is all a try-it-out kind of lab. HOMEWORK ======== 1. Send message to multiple clients. We're supposed to do this all in the client program. Here's the code that sends messages now: (define (im who message) ;;;Send message to who. (if (not (send-msg whoiam who "send-msg" message to-server-write)) (close-connection) #t)) We want to change this so that WHO can be a list instead of just one name. The minimal solution is as follows: (define (im who message) ;;;Send message to who. (IF (LIST? WHO) (FOR-EACH (LAMBDA (USER) (IM USER MESSAGE)) WHO) (if (not (send-msg whoiam who "send-msg" message to-server-write)) (close-connection) #t))) If WHO is a list of names, instead of a single name, just call IM recursively for each name in the list. This isn't perfect, because if something goes wrong, we keep trying to send even after closing the connection. There are many ways to fix that; maybe the easiest is to make sure we have a server before trying to send: (define (im who message) ;;;Send message to who. (if (list? who) (for-each (lambda (user) (IF TO-SERVER (im user message))) who) (if (not (send-msg whoiam who "send-msg" message to-server-write)) (close-connection) #t))) 2. Broadcast to all clients. We're supposed to do the broadcasting in the server, so first we have to be able to send a BROADCAST message from the client to the server: (define (broadcast message) ;; This is in im-client.scm (if (not (send-msg whoiam "server" "broadcast" message to-server-write)) (close-connection) #t)) [Note that there is a procedure named BROADCAST in im-server.scm that has nothing to do with this new feature!] Then we have to modify the message-handling procedure in the server to understand and process the BROADCAST message: (define (handle-client name sock) ;;;Handle messages from the client. ; ;Only handles "send-msg" "BROADCAST" and "logout" messages. *** FIXED COMMENT! ; (let ((read-port (socket-input sock)) (write-port (socket-output sock))) (when-port-readable read-port (lambda () (let ((msg (get-msg read-port))) (if (not msg) (remove-client name) (begin (display (format #f "Received message: ~A~%" msg)) (cond ;Unrecognized commands fall through the (cond). ((string=? "send-msg" (xml-cdata "command" msg)) (send-command (xml-cdata "from" msg) (xml-cdata "to" msg) "receive-msg" (xml-cdata "data" msg)) (if (char-ready? read-port) ((when-port-readable read-port)))) ((STRING=? "BROADCAST" (XML-CDATA "COMMAND" MSG)) (FOR-EACH (LAMBDA (CLIENT) (SEND-COMMAND (XML-CDATA "FROM" MSG) CLIENT "RECEIVE-MSG" (XML-CDATA "DATA" MSG))) (CLIENTS-LIST)) (IF (CHAR-READY? READ-PORT) ((WHEN-PORT-READABLE READ-PORT)))) ((string=? "logout" (xml-cdata "command" msg)) (remove-client (xml-cdata "from" msg))))))))))) I wrote the new part (capital letters) by copying the cond clause for send-msg and modifying it as follows: 1. Change "send-msg" to "broadcast" (the name of the message). 2. Wrap a FOR-EACH around the call to send-command, so that we send a "receive-msg" to every client instead of just one. 3. Change the (xml-cdata "to" msg) to CLIENT (the formal parameter of the lambda expression) because the sender didn't specify a particular recipient. 3. Discuss client-side vs. server-side processing. Either task could be done either way. The main virtue of doing the work in the client (as you can see by comparing the two solutions above) is that it's less work for the programmer, often, because only one program has to be changed. This also makes it less likely that the change will introduce bugs, because you don't have two different programs that have to agree. (This is even more true in the real world, where you're likely to have some people running the new version and other people still running the old version of the client software. If the new client is designed so that no server changes are needed, both new and old clients should still run without problems. When a change is made to the server, you have to take the trouble to ensure that the new server software still supports old versions of the client software.) The main virtue of doing the work in the server is that it reduces the load on the network, at least in these examples. Sending a message to N people entirely through client-side changes means that the client software sends N separate requests to the server, which in turn sends N messages to the other clients. Doing the same thing by teaching the server software a new capability means that only one message goes from the originating client to the server, so the total number of network messages is N+1 instead of 2N. 4. Refusing messages. This will be easier if we do it entirely in the client software, not only for the usual reason of keeping the changes local to one program, but also because each client can maintain its own list of refusees. If we do it in the server, then the server needs a global database of who dislikes whom. (In a real-world IM system, the server already has a database of users, because you have to enroll in order to have a username, so adding another item to the per-user database isn't so bad. But in our version, the server program has no permanent database at all.) What about network efficiency? A refused message takes four network requests: sender to server, server to recipient, recipient sends refusal notification to server, server to sender. If we kept the enemies list in the server software, only two network requests would be needed. But we can hope that refusals aren't that common, so this won't be too much of a burden. But this decision has a bad consequence, noted below! Okay, our first task will be to develop a user interface to allow a user to say whose messages should be refused. I'll invent two new user procedures: (refuse-from "fred") (accept-from "fred") We'll have a global variable ENEMIES that contains a list of usernames: (define enemies '()) (define (refuse-from whom) (if (not (member whom enemies)) (set! enemies (cons whom enemies)))) (define (accept-from whom) (set! enemies (filter (lambda (name) (not (equal? name whom))) enemies))) Now we can modify the handling of an incoming message to see if we want to show it to our user: (define (received-msg from-whom msg) ;;;Handles message received from other clients. ;Change to GUI in future. (IF (MEMBER FROM-WHOM ENEMIES) (IM FROM-WHOM "YOUR MESSAGE WAS REFUSED.") (display (format #f "~%Message from ~A:~% ~A~%~%" from-whom msg)))) That's about it! No other parts of the program have to be changed. But there's one severe bug in the implementation so far: Suppose I'm on your enemies list, and you're on mine. (It's not so unlikely for this symmetry to occur, after all.) If I send you a message, your software will send me back a refusal notice. Since that notice looks like a message from you, I'll refuse it, and so I'll send you a refusal notice. These notices will go back and forth forever! That really bogs down the network for everyone. Here's a case in which using the server software to do some of the work would have helped. We could mark the refusal notice as coming from "server" rather than from the enemy, so the refusal notice wouldn't be refused. Instead, we'll have to put up with not seeing the refusal notification in these situations, but at least we can avoid the infinite message loop: (define (received-msg from-whom msg) ;;;Handles message received from other clients. ;Change to GUI in future. (if (member from-whom enemies) (IF (NOT (EQUAL? MSG "YOUR MESSAGE WAS REFUSED.")) (im from-whom "your message was refused.")) (display (format #f "~%Message from ~A:~% ~A~%~%" from-whom msg)))) [Note: I'm putting the changes in CAPITAL LETTERS to make them easy to find, but in fact two strings aren't equal if one is in capitals and the other in lower case letters. You'd want to be consistent.] Another solution, requiring code in the server as well, would be to invent a new command SEND-REFUSAL that's like SEND-MESSAGE but specially marked so that the target client gets a RECEIVE-REFUSAL command, which it would know not to refuse. 5. Why the 3-way handshake? In other words, why isn't it good enough to send the connection request from client to server, and an acknowledgement from server to client? We want to make sure that we've actually successfully set up a two-way interconnection between the two ends. What if the server can get messages from the client, but the client never sees messages from the server? We want to find out about that, and notify the user that the connection wasn't set up successfully. The network software will "time out" if a reply doesn't come after a certain number of seconds, so both client and server can be confident that each can talk to the other. (Of course it's still possible for a connection to be lost after some of these handshaking messages go by. In really critical situations, hosts will send each other "are-you-alive?" messages every so often, just to be sure that hasn't happened.) This is the sort of thing you don't have to worry about when you're not doing network programming. Failures on a single computer are generally all-or-nothing; if anything works, everything works. 3.38 (a). Peter then Paul then Mary: 100 -> 110 -> 90 -> 45. Peter then Mary then Paul: 100 -> 110 -> 55 -> 35. Paul then Peter then Mary: 100 -> 80 -> 90 -> 45. Paul then Mary then Peter: 100 -> 80 -> 40 -> 50. Mary then Peter then Paul: 100 -> 50 -> 60 -> 40. Mary then Paul then Peter: 100 -> 50 -> 30 -> 40. So the possible final values are 35, 40, 45, and 50. (b). There are lots of extra possibilities. It's especially bad because Mary's command is (set! balance (- balance (/ balance 2))) which examines the value of balance twice, instead of the mathematically equivalent (set! balance (/ balance 2)) which only examines the value once. Here are just a few possibilities: Peter examines balance, then Paul and Mary run in either order, then Peter sets balance. Paul's and Mary's activities become irrelevant; the final balance will be 110. Mary looks at balance, then Paul runs, then Mary looks at balance again to compute (/ balance 2), then Peter runs, then Mary sets the balance. Peter's work is irrelevant, but Paul's isn't; Mary computes (- 100 (/ 80 2)) and the final balance is 60. Paul examines balance, then Peter and Mary run in any order, then Paul sets balance. The result is 80. 3.39 buggy serialization Because multiplying x by itself is serialized, we can eliminate the case in which (* x x) gets two different values of x, which is the one that leads to a final answer of 110. However, because the setting of x in P1 is not serialized along with P1's reading of x, we can still get the incorrect answer 100. And because only the computation part of P1 is serialized, the incorrect answer 11 is also still possible. It can't happen the way it's described in the book: P2 accesses x, then P1 sets x to 100, then P2 sets x but it can happen in this more complicated way: P1 reads x and computes the value 100, then P2 accesses x (still 10), then P1 sets x to 100 (since this part isn't serialized), then P2 sets x to 11. (And of course the correct answers 101 and 121 are still possible.) 3.40 The smallest possible result is the one you get if P1 reads and squares 10, then P2 runs completely, and then P1 sets x to 100. The largest possible result is the correct one, in which the two processes run serially (in either order); the result is 1,000,000. Any power of 10 between these limits is also possible: 1000: P2 cubes 10, then P1 runs completely, then P2 sets x to 1000. 10000: P2 reads x=10 twice, then P1 runs completely, setting x to 100, then P2 reads x=100 for its third factor and sets x to 10*10*100. 100000: P2 reads x=10 once, then P1 runs, then P2 reads x=100 twice. If the processes are serialized, only the correct result 1,000,000 is possible. Either P1 sets x to 100 and then P2 cubes that, or else P2 sets x to 1000 and P1 squares that. 3.41 serialize reading balance? The reason we need serialization in the first place is that if a process makes more than one reference to the same variable, we want to be sure its value is consistent throughout that process. But reading the balance only looks at the balance once; how could another process interrupt that? Actually, this answer is a slight handwave. In order to be confident about it, you must know that a number can be read from the computer's memory in a single, indivisible hardware operation. This is true for every modern computer, provided that the number fits in the usual hardware representation of numbers. However, Scheme supports "bignums", which are unlimited-precision integers. That's why in Scheme you can compute the factorial of 1000 and get a precise answer, even though that answer has 2568 decimal digits. Reading a bignum requires more than one memory reference, and so Ben is right if bignums are allowed. The usual indivisible-lookup kind of integer can support values up to about 2 billion, so this means that the bank that handles Bill Gates' account should take Ben's advice, but the rest of us don't have to worry about it. 3.42 when to serialize procedures Ben is right. The key point to understand is that there are three distinct steps in using a serializer: 1. Create the serializer. 2. Create a serialized procedure. 3. Invoke the serialized procedure. Only step 3 involves concurrency problems. Ben's proposal is to reduce the number of times step 2 is taken, which is fine. 3.44 Transferring money Louis is wrong, as usual. In the case of transferring a fixed (given as argument) amount of money, there really are two entirely separate steps: Withdraw the money from one account, and deposit the money in another. Each step is serialized by the account itself. It doesn't matter if something else happens between the two steps! You might think "another process could change the value of the variable AMOUNT" but that's not so; AMOUNT is a *local* variable within this transfer, not shared with any other process. We only have to worry about synchronization when a state variable is shared among different processes. Also, in the case of TRANSFER, the only constraint on correct answers when several transfers are done in parallel is that the sum of the balances should be the same after the transfers as before. EXCHANGE has a more stringent requirement; after several parallel exchanges, the balances of all accounts should be the same as before, except in a different order. It's not good enough for the sum of the balances to be preserved; the individual balances must be, too. Since the amount to be transferred is a function of the starting balances, we can't let another process intervene between computing that amount and adjusting the balances. 3.46 Why test-and-set! must be atomic Suppose the mutex is initially false. P1 starts doing (if (car cell) ...) and gets the value FALSE, so it thinks the mutex is free. Now P2 runs, before P1 does anything else. It, too, does (if (car cell) ...), reads the value FALSE, and thinks the mutex is free. Then they both set the value to TRUE and claim the mutex. We have to make sure that there is no intervening process between reading (car cell) and (set-car! cell true). 3.48 deadlock The problem we're solving is that P1 and P2 want the same two serializers S1 and S2. Deadlock will happen under the following order of events: 1. P1 gets S1. 2. P2 gets S2. 3. P1 wants S2, can't have it, waits. 4. P2 wants S1, can't have it, waits. Both processes wait forever because they're trying to use a busy serializer. This problem appeared because P1 and P2 asked for the serializers in reverse order from each other. If they both use the same order, the worst sequence of events will be this: 1. P1 gets S1. 2. P2 wants S1, can't have it, waits. 3. P1 gets S2. 4. P1 finishes, releases both serializers. 5. P2 finally gets S1. 6. P2 gets S2. 7. P2 finishes, releases both serializers. Here's the code: (define make-account-and-serializer (LET ((NEXT-ID-NUMBER 1)) (lambda (balance) (define (withdraw amount) ...) (define (deposit amount) ...) (let ((balance-serializer (make-serializer)) (ID-NUMBER NEXT-ID-NUMBER)) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) ((EQ? M 'ID) ID-NUMBER) (else (error ...)))) (SET! NEXT-ID-NUMBER (+ NEXT-ID-NUMBER 1)) dispatch)))) (define (serialized-exchange account1 account2) (IF (> (ACCOUNT1 'ID) (ACCOUNT2 'ID)) (SERIALIZED-EXCHANGE ACCOUNT2 ACCOUNT1) (let ((serializer1 (account1 'serializer)) (serializer2 (account2 'serializer))) ...))) This solution, by the way, assumes that only one account is *created* at a time! If accounts can be created in parallel, then the assigning of account numbers must also be serialized, this way: (define make-account-and-serializer (let ((next-id-number 1) (ID-SERIALIZER (MAKE-SERIALIZER))) (lambda (balance) (define (withdraw amount) ...) (define (deposit amount) ...) ((ID-SERIALIZER (LAMBDA () (let ((balance-serializer (make-serializer)) (id-number next-id-number)) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) ((eq? m 'id) id-number) (else (error ...)))) (set! next-id-number (+ next-id-number 1)) dispatch))))))) There is a separate balance-serializer for each account, but a single id-serializer for the entire account class. In our OOP notation we might say (define-class (account balance) (class-vars (next-id-number 1) (id-serializer (make-serializer))) (instance-vars (balance-serializer (make-serializer)) (id-number #f)) (initialize ((id-serializer (lambda () (set! id-number next-id-number) (set! next-id-number (+ next-id-number 1)))))) (method (withdraw amount) ...) (method (deposit amount) ...)) EXTRA FOR EXPERTS ----------------- Mail program: Umm, I haven't actually written this, but it's straightforward. You just have to put a database in the server. When a message is sent, instead of the server passing it on to the recipient's client right away, the server just adds it to the database. When a client connects, it can ask to retrieve all its messages. One detail that's intellectually trivial but will take some effort is that a message has to be able to be more than one line of text. 3.33 averager We want to implement c=(a+b)/2, but we don't have a division constraint; these are unnecessary since we can run the multiplication ones backwards. So we implement a+b = c*2: (define (averager a b c) (let ((x (make-connector)) (y (make-connector))) (adder a b x) (multiplier c y x) (constant 2 y) 'ok)) 3.34 Louis's squarer It would be nice if Louis's idea worked, and if the multiplier constraint were smart enough, maybe it could. We could add a clause to the COND in the multiplier's process-new-value procedure: ((and (has-value? product) (eq? m1 m2)) (set-value! m1 (sqrt (get-value product)) me)) Note that the EQ? test is *not* a test of numeric equality! On the contrary, in this situation we are assuming that m1 (and m2, since they're the same connector) has no numeric value. The EQ? test is asking if they're the same connector, not two connectors with the same value. But our multiplier doesn't have this feature, so Louis's program won't work. More precisely, it'll work fine in the forward direction; if we give connector A a value, then Louis's program will give connector B the square of that value, because the multiplier will carry out the COND clause ((and (has-value? m1) (has-value? m2)) (set-value! product (* (get-value m1) (get-value m2)) me)) since m1 and m2 are both attached to connector A. But we want our constraints to work backward, too; if we give B a value, the squarer should assign its square root to A. And that won't happen because (except in the special case of a multiplicand of zero) the multiplier constraint requires two known values in order to compute the third value. 3.35 Ben's squarer (define (squarer a b) (define (process-new-value) (if (has-value? b) (if (< (get-value b) 0) (error "square less than 0 -- SQUARER" (get-value b)) (SET-VALUE! A (SQRT (GET-VALUE B)) ME)) (SET-VALUE! B (* (GET-VALUE A) (GET-VALUE A)) ME))) (define (process-forget-value) (FORGET-VALUE! A ME) (FORGET-VALUE! B ME)) (define (me request) (COND ((EQ? REQUEST 'I-HAVE-A-VALUE) (PROCESS-NEW-VALUE)) ((EQ? REQUEST 'I-LOST-MY-VALUE) (PROCESS-FORGET-VALUE)) (ELSE (ERROR "UNKNOWN REQUEST -- SQUARER" REQUEST)))) (CONNECT A ME) (CONNECT B ME) me) 3.36 environments The constraint system is an OOP system, in which the classes are "connector" and the various constraint types ("adder" etc.). So we should expect to see four levels of environment: global, class, instance, and method. But this particular program is simpler, in that there are no class variables or class methods. If, for example, the connector class had a class variable FOO, the code would be (define make-connector (let ((foo 87)) (lambda () ...))) Instead we have the straightforward (define (make-connector) ...) which doesn't generate a class frame. Make-connector and set-value! are procedures whose right bubble points to the global environment. The first call to make-connector established a new frame: E1: ; points to global environment The LET inside make-connector creates a procedure: P1: params: value, informant, constraints; body (define...)...; points to E1. and another frame: E2: value = #F, informant = #F, constraints = (); points to E1. The four definitions in the LET body generate P2: params: newval, setter; body (cond...); points to E2. P3: params: retractor; body (if...); points to E2. P4: params: ; body (if...)...; points to E2. P5: params: request; body (cond...); points to E2. and also add four new bindings to E2: E2: value = #F, informant = #F, constraints = (), set-my-value = P2, forget-my-value = P3, connect = P4, me = P5; points to E1. Make-connector returns the binding for ME, namely P5, so the (define a ...) adds the binding A = P5 to the global environment. Similarly, the (define b (make-connector)) gives another five new procedures and two new frames, which I'm going to ignore because they don't do anything interesting in the SET-VALUE! call. But we'll name them P6-P10 and E3-E4. Now we call set-value!, which is defined in the global environment, and whose right bubble points to the global environment. So this creates E5: connector = P5, new-value = 10, informant = user; points to global env. The body of set-value! first calls (connector 'set-value!), i.e., it calls P5. This creates another frame: E6: request = set-value!; points to E2. This call returns the value of set-my-value in E2, namely P2. We then do the outer invocation in set-value!'s body, which is in effect (P2 10 'user), so this creates E7: newval = 10, setter = user; points to E2. In this environment we evaluate the body of set-my-value, which is a COND expression. We start by calling has-value?, which is a global procedure, so this makes the frame E8: connector = P5; points to global env. This calls P5: E9: request = has-value?, points to E2. P5 (i.e., ME) checks the value of INFORMANT, which it finds in E2. It's false, so P5 returns #F. This is used as the argument to the primitive procedure NOT, which doesn't affect the environment, but returns #T. Therefore we carry out the rest of the first COND clause. * Change the binding of VALUE in E2 to 10. * Change the binding of INFORMANT in E2 to USER. And finally we can call for-each-except, so we're finished doing what the question asked. The actual argument values to for-each-except are USER, the inform-about-value procedure (which is defined globally), and the empty list. 3.37 expression-oriented constraint language This is pretty straightforward, as long as you remember that C- has to use an adder constraint, not a (nonexistent) subtracter constrant, etc. (define (c- x y) (let ((z (make-connector))) (adder y z x) ;; note the order! z)) (define (c* x y) (let ((z (make-connector))) (multiplier x y z) z)) (define (c/ x y) (let ((z (make-connector))) (multiplier y z x) z)) (define (cv num) (let ((z (make-connector))) (constant num z) z))