Homework 3

home work!

Programming Language BSL

Due Date: Thursday January 30 at 9pm

Purpose: To design World programs; to practice designing and using structured data


Failure to comply with these expectations will result in deductions and possibly a 0 score.

Exercise 1 A bank has a wicked type of interest-bearing account that works as follows. The customer opens the account with an initial deposit of some non-zero dollar amount (a natural number). The bank then recalculates the balance every day, according to these rules:

  • if the dollar amount is odd, then the bank (i) adds 1 dollar, then (ii) divides the resulting amount by 2, and finally (iii) subtracts one dollar.

  • if the dollar amount is even, then the bank (i) adds 1 dollar, and then (ii) multiplies the resulting amount by 3.

The first customer reads only the "multiply by 3" part and is very excited. Someone else has thought about this form of interest accrual, however, and warns the customer, suspecting that no matter what the initial deposit, the money will always be gone after some number of days, i.e. the balance will be zero. The small-print in the contract says that, if that happens, the account will be closed, and the money is lost.

Help the customer investigate this, by designing the function monitor-account that takes the initial deposit–a positive natural number–as input and starts a World program. Upon each clock tick, which we assume to represent one day, visualize the current account balance using a solid rectangle of width 10 times the balance, a fixed height of 20, and color gold. Place this "gold bar" into a scene of size 1000x100 pixels. "What if the customer is so rich that the rectangle extends beyond the scene boundary?" Ignore that.

If and when the account is depleted (0), print the message, "You are broke!" (rather than showing a zero-width gold bar), and end the simulation. Make your clock tick every 1 second.

Should the customer be concerned? What happens for an initial balance of the form 2n-1, for example $127 (=27-1) or $63 or $31? Also try an initial balance of $49. State your findings (in English) in comments in your file.

Exercise 2 (Credit goes to Kenyon Allan, a student in Section 1, whose question inspired this homework.)

Revisit the Traffic Light example from Lecture 6 (01/16; remember that you can find all code used in the lectures on Piazza). Using the [on-tick next-tl 1] clause, this continuously displays the traffic lights RED -> GREEN -> YELLOW, with lights switching every second. The goal of this exercise is a more realistic traffic light simulator that displays RED for 3 seconds, GREEN for 2, YELLOW for 1. One cycle of the traffic light displaying RED, GREEN, YELLOW therefore takes 3+2+1=6 clock ticks.

We can accomplish this as follows. Let us first assume we have access to a "cyclic wall clock", in the form of a natural number that is initialized to 0 and advances in increments of 1 until it reaches 5, whereupon it cycles around and repeats: 0,1,2,3,4,5,0,1,2,3,... In each cycle beginning with 0, the first three ticks are RED, the next two GREEN, the final one yellow.

But where do we get a cyclic wall clock from? The solution is to keep track of our own cyclic time, by creating a cyclic counter inside the World State that starts with 0 and is incremented by 1 each second using on-tick, modulo 6. Follow these steps:

  • Copy the TrafficLight data design from Lecture 6 into your solution.

  • Design data to hold a ClockedLight, which consists of a TrafficLight and a natural number in [0,6). Do not use a posn for these two values, but instead define-struct a new 2-field structure, so you can name the fields suitably, according to what they represent: a traffic light and a cyclic time. Follow the complete data design recipe for ClockedLight.

  • Define a function loop-light that takes a ClockedLight cl as input and calls big-bang, initializing the World State to cl. Your big-bang needs a clause to draw the World State, and an event handler for clock ticks.

    Remember that the function design recipe applies to loop-light, except for check-expects, which are not required.

  • Design the function to draw the traffic light. Do not display the clock value, only the light. You can do this in a similar way as we did it in class, but of course the World State is now of a different data type.

  • Design an event handler that responds to ticks of BSL’s internal clock. This handler needs to accomplish two things: (i) set the appropriate traffic light. This depends on the current value of the cyclic World State clock and follows the rules sketched above; and (ii) increment the value of the World State clock modulo 6, since this clock needs to be in sync with BSL’s time, modulo 6.

  • Show a call of your loop-light function that starts the traffic light simulation with a RED light and a clock value of 0.

    Suppose you start the simulation with a RED light but a clock value of 4: this seems to contradict the traffic light timing rules. What happens? does the traffic light get confused? Briefly explain the behavior of the program on that input.

Exercise 3 Your task is to build a calendar app that helps the assistant of a manager keep track of the manager’s events of a particular day.

  • Design data to hold an event. An event has a title, a daytime when it starts, a daytime when it ends, a location, a field that tells whether the event is public (i.e., whether the event details are revealed in the web view of the calendar), and the name or job title of the event creator. Represent a daytime as a possibly fractional number, where 6.0 represents 6am, 8.5 represents 8:30am, and 13.75 represents 1:45pm. We assume that no event lasts past midnight.

    First define-struct a suitable structure, and then follow the four steps of the data design recipe.

  • List ALL functions that BSL automatically defines over this new structure, along with their signatures. Make the signatures as precise as possible, i.e. include everything we know about the types of input and output data of these functions in the signatures.

  • Design a function duration that, given an event, returns its length in minutes. If the start time is after the end time, your function should signal an error:

    "event ’TITLE’: incorrect time specification: start > end"

    where TITLE is replaced by the actual event’s title.

  • Design a function reschedule that, given an event and a daytime, reschedules the event to begin at the given daytime such that the duration remains the same. If the rescheduled event lasts until midnight or later, your function should signal an error:

    "event ’TITLE’: rescheduling extends event to midnight"

    where TITLE is replaced by the actual event’s title.

  • Design a function overlap? that, given two events, returns #t if they overlap (so that the manager cannot participate in both of them, at least not fully).

    For this function, create at least one check-expect that takes two non-overlapping events e1 and e2 and calls overlap? on e1 and the result of rescheduling e2 such that it starts while e1 is ongoing.