% Document Type: LaTeX % Master File: ps7.tex \input ../6001mac \def\fbox#1{% \vtop{\vbox{\hrule% \hbox{\vrule\kern3pt% \vtop{\vbox{\kern3pt#1}\kern3pt}% \kern3pt\vrule}}% \hrule}} \begin{document} \psetheader{Sample Problem Set}{Simulation and Concurrency} \medskip The programming assignment for this week explores two ideas: the simulation of a world in which objects are characterized by collections of state variables and the characteristics of systems involving concurrency. These ideas are presented in the context of a market game. In order not to waste too much of your own time, it is important to study the system and plan your work before coming to the lab. This problem set begins by describing the overall structure of the simulation. The exercises will help you to master the ideas involved. \begin{center} {\bf How England lost her Barings } \\ or \\ an abject Leeson for the banking community \end{center} Earlier this year the English banking community was stunned by the failure of the 233-year-old Baring Brothers investment banking company. A 28-year-old trader in Singapore, Nick Leeson, lost over \$1G in a rather short time. Mr. Leeson, who was originally involved in arbitrage trading on the differences between the prices of the Nikkei-225 average in the Osaka and Singapore stock exchanges incurred massive losses from an extremely leveraged position in the Nikkei average. \section{Markets} In our simplification, we model a market, such as the Osaka market in Nikkei-225 derivatives or the Singapore market in Nikkei-225 derivatives, as a message acceptor with internal state variables, {\tt price} and {\tt pending-orders}. The message acceptor can handle requests to get the current price, to update the price, to accept an order, and to process pending orders. We make these markets with a market-constructor procedure as follows: \beginlisp ;;; The initial price (define nikkei-fundamental 16680.0) \null (define Osaka (make-market "Osaka:Nikkei-225" nikkei-fundamental)) \null (define singapore (make-market "Singapore:Nikkei-225" nikkei-fundamental)) \endlisp There are several messages accepted by a market. For example, one may obtain the current price on the Singapore market as follows: \beginlisp (singapore 'get-price) ;;; Value: 16673.23 \endlisp Traders interact with markets. A trader is modeled by an object that holds two kinds of assets: a monetary balance and a number of contracts. In this simulation there is only one kind of contract: A Nikkei-225 derivative contract (whatever that is! However, we may watch Mr. Leeson lose money with or without knowing what these contracts are about.) The message {\tt get-price} will be used by traders to obtain quotes of the current market price of a contract. The trader bases his decisions on this price. Every so often, a trader may place a new order by sending a {\tt new-order!} message to a market. An order is a procedure (of no arguments) supplied by the trader to be executed by the market in the near future. An order may modify the assets of the trader. Our simulation system for the interaction of traders and markets sends certain system messages to the objects to model the flow of time. Thus, every so often a market receives, from the system, a message to change the price or to process orders. The markets are implemented as follows: \beginlisp (define (make-market name initial-price) (let ((price initial-price) (price-serializer (make-serializer)) (pending-orders '()) (orders-serializer (make-serializer))) (define (the-market m) (cond ((eq? m 'new-price!) (price-serializer (lambda (update) (set! price (update price))))) ((eq? m 'get-price) price) ((eq? m 'new-order!) (orders-serializer (lambda (new-order) (set! pending-orders (append pending-orders (list new-order)))))) ((eq? m 'execute-an-order) (((orders-serializer (lambda () (if (not (null? pending-orders)) (let ((outstanding-order (car pending-orders))) (set! pending-orders (cdr pending-orders)) outstanding-order) (lambda () 'nothing-to-do))))))) ((eq? m 'get-name) name) (else (error "Wrong message" m)))) the-market)) \endlisp We can instantiate the general market to make a particular market, say the Osaka market in Nikkei-225 derivatives: \beginlisp (define nikkei-fundamental 16680.0) \null (define Osaka (make-market "Osaka:Nikkei-225" nikkei-fundamental)) \endlisp Notice that in {\tt make-market} the {\tt price-serializer} is applied to a procedure that takes a procedure {\tt update} and uses it to compute the new price from the old one. The {\em critical region} guarded by the serializer contains both the assignment to the protected variable and a read access of that variable. The acceptance of a new order is similarly serialized. Execution of an order is also serialized with the {\tt orders-serializer}, but this is a much more complicated situation. \paragraph{Exercise 1:} Why do we need two different serializers to implement a market? What bad result could we expect if we made only one serializer and used it to serialize all three of the guarded regions? Why must the {\tt orders-serializer} be used for guarding two regions? The message {\tt new-price!} will be issued to each market every so often by a process that models random market forces. There are many factors that influence the price of a market commodity, and we cannot begin to model those factors. However, we can imagine that the commodity price will take a random walk starting with its fundamental value, and drifting. The procedure {\tt nikkei-update} implements just such a strategy, whose details are probably not important, except in the way that it updates the prices when called (see the listing). The {\tt execute-an-order} message is used by the system to cause the market to execute one of the pending orders. If there are orders pending then the first is selected and executed, and removed from the list of orders. \paragraph{Exercise 2:} The code for handling an {\tt execute-an-order} message is quite complicated. Louis Reasoner suggests that it could be simplified as follows: \beginlisp ((eq? m 'execute-an-order) ((orders-serializer (lambda () (if (not (null? pending-orders)) (begin ((car pending-orders)) (set! pending-orders (cdr pending-orders)))))))) \endlisp Unfortunately, Mr. Reasoner's suggestion is (as usual) not completely correct; it will work in the simple cases we have included in the problem set, but not in general. A slightly better idea, which is still not quite correct is: \beginlisp ((eq? m 'execute-an-order) (let ((current-order (lambda () 'nothing-to-do))) (if (not (null? pending-orders)) ((orders-serializer (lambda () (begin (set! current-order (car pending-orders)) (set! pending-orders (cdr pending-orders))))))) (current-order))) \endlisp Explain in no more than three short, clear sentences each, what is wrong with Louis's idea, and why the second try is better but still not quite right. Watch out -- this question is subtle -- the answer is not obvious. Try to draw timing diagrams showing how these methods may fail. \bigskip The code supplied defines a particular kind of trader, an arbitrager, Nick Leeson, who tries to make money on the difference of the value of a commodity on different exchanges. He buys on the low exchange and sells on the high one, pocketing the difference. The idea works, if the orders can be processed faster than the exchange moves. The arbitrager is implemented as follows: \beginlisp (define (make-arbitrager name balance contracts authorization) (let ((trader-serializer (make-serializer))) (define (change-assets delta-money delta-contracts) ((trader-serializer (lambda () (set! balance (+ balance delta-money)) (set! contracts (+ contracts delta-contracts)))))) (define (a (- high-price low-price) transaction-cost) (let ((amount-to-gamble (min authorization balance))) (let ((ncontracts (round (/ amount-to-gamble (- high-price low-price))))) (buy ncontracts low-place change-assets) (sell ncontracts high-place change-assets))))) (define (consider-a-trade) (let ((nikkei-225-Osaka (Osaka 'get-price)) (nikkei-225-singapore (singapore 'get-price))) (if (< nikkei-225-Osaka nikkei-225-singapore) (a