CS173 - Scripting

Scripting and Domain-specific Languages

In this assignment, you will use Scheme macros to implement a domain-specific programming language for controlling robots. You will write scripts that read from the robot's sensors (such as a camera and touch-sensitive bumpers) and send commands to the motors. This is the brain of the robot, and so we call the language "Brainscript".

Perhaps infamously, robots never die. Thus, the basic building block in Brainscript is the infinite loop, and Brainscript has special operators for combining infinite loops into larger loops.

Note: For this assignment, you have to use the language PLAI - Pretty Big, otherwise SYNTAX-RULES and SYNTAX-CASE are not defined. You will work in your third team for this.

The support code is in three files: robot.ss, robot-sim.ss, and default-robot.ss.

The Brainscript Language

What does Brainscript look like? The following script plays a little game of soccer. It runs on a robot that can move around, detect the ball and kick the ball (if it is close enough).

(brain
 (ball-distance ball-direction)
 (go-forward go-left go-right kick)
 (do 
     (while (> (ball-distance) 10)
	    (cond-flip [(eq? (ball-direction) 'forward) (go-forward)] 
		       [(eq? (ball-direction) 'left) (go-left)]  
		       [else (go-right)]))
     (timed 1 (kick)))

Brainscript programs begin with a call to the macro brain, followed by two lists of identifiers, followed by one or more body expressions. Each name in the first list is bound to a sensor predicate of type void -> any. In this case, ball-distance returns an integer representing the distance between the robot and the ball (in centimeters), and ball-direction returns one of 'left, 'forward or 'right, depending on the position of the ball relative to the robot.

In the call to brain, each identifier in the second list is bound to an action loop. Actions loops are procedures of no arguments that, when called, take control of the robot's motors. Action loops are infinite loops: first they refresh the sensor sensor cache by using the robot's low-level API, second they set the robot's motors positions, then they repeat -- ad infinitum.

The sensor cache make sure that during a particular iteration of the brain all sensor readings are consistent with one another. Without the sensor cache, the robot would read its sensors at slightly different times and could end up with a self-contradicting view of its environment.

Action loops are useful in robots that require complex and careful motions. For example, in a walking robots, the go-forward action loop maintains the balance of the robot by updating the force of the motors every milliseconds.

However, infinite loops are not as much fun when you get stuck in one. For this, Brainscript has a number of control operator that break out of nested action loops. The body of the soccer-player script uses four of the five control operators that you will implement: do, while, cond-flip and timed (the fifth one is flip). The do statement creates an infinite loop: it execute each statement of its body in order, until the last, then restarts with the first one. In contrast, the four other operators have a guard condition that breaks out of infinite loops. At first, while, flip, cond-flip and timed act just like do: they execute each statement of their body in order, repeating when necessary. However, if their guard expression ever becomes false, they will break the current action loop, no matter how deeply nested, and escape out.

Let's see how this works with an example statement. The statement

(timed 1 (go-forward))

runs the go-forward action loop for one second then escapes out of timed expression. To do this, the Brainscript support code keeps a single global stack of active guard thunks, each with a corresponding escape thunk. (A thunk is a function of no arguments.) The guard of this timed expression returns true at first, but if it is called after one second has passed since execution entered the timed statement, it returns false. The corresponding escape thunk simply exits the timed statement.

When the execution enters the timed statement, your Brainscript implementation will push this guard-thunk/escape-thunk pair onto the stack, execute its body, and, when execution exits the body (that is, when the escape continuation is invoked), pop the pair from the stack. The action loops are responsible for calling the guard functions and invoking the escape thunks. That is, the go-forward action loop (and all other action loops for the matter) execute three steps, in cycle:

Update sensors.
Check each guard on the stack, from oldest to newest, and invoke the continuation of first guard that returns false.
If all the guards return true, adjust the motors to move the robot forward, then jump to step 1.

The other action loops work similarly.

The right way to implement escape thunks is with continuations. Since Brainscript statements do not have return values, the escape functions are thunks. Your escape thunks can simply invoke continuations with (void) as the argument to signify no useful return value. Remember that you can capture the current continuation with Scheme's let/cc statement. Look in the lecture notes on continuations for more details.

Formal definition

Formally, the Brainscript language has the following grammar:

<brain> ::= (brain (<id> ...) (<id> ...) <brainscript> ...)  

<brainscript> ::= (do <brainscript> ...)
                | (while <scheme> <brainscript> ...)
                | (flip <scheme> <brainscript> <brainscript>)
                | (cond-flip [<scheme> <brainscript>] ...)    
                | (timed <scheme> <brainscript> ...)  
                | <scheme>

The grammar forbids the usage of the brain macro from within a brain. Also, only standard Scheme expressions are legal in the guard position of a Brainscript statement -- Brainscript statements are not allowed as guards. This will simplify your implementation somewhat, since it guarantees that there is only one brain active at any given time. As usual, your implementation does not have to do error detection. All the programs we will test with will respect the Brainscript grammar.

You have to implement the following six macros. It will pay off greatly if you think ahead and write some macros in terms of others. For example, you only need to write infinite-loop code once if your other macros expand to code that contains a do block. Only implementing what you need to is part of this assignment. Don't copy your code!

```
(brain (<sensor> ...) (<action> ...) <body> ...)
```
The brain macro creates and binds a sensor procedure to each name of the first list, and it creates and binds an action procedure to each name of the second list.

The sensor procedures should look up the appropriate piece of robot state in the sensor cache using the support-code function read-sensor-cache. read-sensor-cache takes one argument, namely, the name of the sensor to read from, as a symbol, and returns the most recent value from that sensor. So, if the robot has a sensor called ball-distance, adding the identifer ball-distance to the list of sensors in a brain statement would bind ball-distance to a Scheme thunk that returns value of (read-sensor-cache 'ball-distance). This binding is only available from within the <body> expression. (This means that expanding into a series of nested let expressions is not correct.)

As for actions, the support code provide you with the low-level robot function do-action-loop. For each name <action>, your brain macro should generate a function that calls do-action-loop with the symbol <action> as an argument, then it should bind that function to the name <action>. do-action-loop performs the three steps discussed above: (1) obtain a fresh sensor cache (2) check all the guards on the stack; (3) send a command to the robot; then it repeats.

Once all the names are bound, brain executes each <body> statements in order, then returns.
```
(do <body> ...)
```
The do macro executes each <body> statement in order, then repeats.
```
(while <guard> <body> ...)
```
First, the while macro evaluates its guard once. If this returns false, the while returns right away. Otherwise while pushes its guard and its continuation onto the stack. Then, like the do macro, while executes each <body> statement in order, then repeats with the first <body> statement. During the execution of the bodies, action loops will traverse the stack and evaluate the guards. If the guard of this while returns false, the action loops will invoke the escape thunk and thus escape out of the while statement. Make sure that you clear the stack of every guard-thunk/escape-thunk pairs you are escaping from, for all the nested Brainscript constructs. There can be more than one!
```
(flip <guard> <true-branch> <false-branch>)
```
flip acts as an if statement that repeatedly re-evaluates it condition. If the condition differs from its previous value, flip escapes and executes the other branch. You may implement flip in terms of while, but you will get a few points more if you implement it without. This is because the while version evaluates its guard more often than necessary. It is, however, very succinct.
```
  (cond-flip [<guard> <body>] ...) 
| (cond-flip [<guard> <body>] ... [else <body>]) 
```
cond-flip is another conditional statement which repeatedly re-evaluates its conditions.cond-flip can have a catch-all else clause, and if it does, it must be the last clause. else clause are specified by using the keyword else in place of a guard. (Remember that you need to specify keywords in the syntax-case statement.) If a cond-flip does not have an else clause, and all the guards evaluates to false, cond-flip should signal an error.
```
(timed <num-expr> <body> ...) 
```
First, the timed macro evaluates the <num-expr> expression. If this returns a number smaller or equal to zero, timed returns right away. Otherwise, timed pushes a new guard and its continuation on the stack and executes each <body> in order (again, with repetitions). Each time the guard is invoked, it will invoke the <num-expr> and obtain an integer. If more than that many seconds have elapsed since the beginning of the execution of this timed expression, the new guard returns false, otherwise it returns true. Use the Scheme function current-seconds to obtain the current time.

The Low-level Robot API and Support Code

The support code we give you implements the global stack required for Brainscript evaluation model. To load the support code, write the following line at the top of your code:

(require "robot.ss")

This will define the following data-type and procedures:

 (define-type StackFrame 
   [stack-frame (guard thunk?) (escape thunk?)])

thunk? -- returns true if the argument is a procedure of no arguments.
brain-push! : StackFrame -> void -- pushes the given stak frame onto the global Brainscript stack.
brain-pop! : void -> void -- pop the top stack frame from the global Brainscript stack.
get-brain-stack : void -> (listof StackFrame) -- returns the current Brainscript stack.
set-brain-stack! : (listof StackFrame) -> void -- sets the Brainscript stack to the given stack. get- and set-brain-stack! are useful to safeguard the state of the stack and restore it at a later time.
read-sensor-cache : symbol -> any -- Consumes a symbol, and looks in the sensor cache for the last values read from the sensor, and returns that value. Different robots have different sensors. If the current robot does not have the sensor specified by the given symbol, an error is signaled.
do-action-loop : symbol -> void -- Consumes a symbol, and executes the action loop for that symbol, as mentioned earlier: (1) obtain a fresh sensor cache (2) check all the guards on the stack (3) send the command to the motor, according to the given symbol (then repeat). Different robots have different motors and different motor loops. If the current robot does not have the motor loop specified by the given symbol, an error is signaled.
set-current-robot! : Robot -> void -- Installs a robot
make-default-robot : void -> Robot -- We will provide you with a small collection of interesting simulated robots to play with. When you first load the support code, it installs one instance of the default robot. To reset the current robot back to a fresh instance of the default robot, evaluate: (set-current-robot! (make-default-robot)). This is useful to do between tests, to reset the robot back to its original configuration.

Debugging macros is notoriously difficult, since you usually do not see the result of the expansion. The support code give you two procedures that expose the result of the macro expansion. They will help find bugs in your macro expanders.

view-macro-result : sexp -> sexp -- consumes a sexp and produces a sexp with all the macros invocations completely expanded. Note that many Scheme primitives are themselves macros. For example, and, or, and cond are macros which expand into instances ofif and let (as we have seen in class.) The return value of view-macro-result will reflect this, and you will find the expanded form of and, or, and cond in the result of view-macro-result.
watch-macro-expansion : sexp -> (listof sexp) -- consumes a sexp and produces a list containing each intermediate result of the macro expension.

The Robots

We provide you with two different robot to test your brain macros againts. The first one does not do anything interesting beside exercising your brain macros. The second one is a physical simulation of a 2d robot that play with a bouncing ball.

The default robot

The default robot has two sensors (ball-distance and ball-direction) and four actions (go-forward, go-left, go-right and kick). The default robot responds to commands according to simple deterministic rules.

If the distance between the robot and the ball ends in 1 or ends in 6, declare that the ball is on the right.
If the distance between the robot and the ball ends in 4 or ends in 9, declare that the ball is on the left.
For other distances, declare that the ball is in front.
If the ball is smaller than 10, and the action is 'kick, add 100 to the distance.
If the ball is in front, and the action is 'forward, substract one from the distance.

The details the rules are not important, what matters is that they are simple and deterministic. It will make your first round of debugging easier. You should test the soccer player script sample (at the top of this page), with your Brainscript macros, against the default robot. When the sample script runs against the default robot, it produces the following output:

      ((ball-distance 30) (ball-direction forward)) : sending go-forward
      ((ball-distance 29) (ball-direction forward)) : sending go-forward
      ((ball-distance 28) (ball-direction left)) : sending go-left
      ((ball-distance 28) (ball-direction forward)) : sending go-forward
      ((ball-distance 27) (ball-direction forward)) : sending go-forward
      ((ball-distance 26) (ball-direction forward)) : sending go-forward
      ((ball-distance 25) (ball-direction right)) : sending go-right
      ((ball-distance 25) (ball-direction forward)) : sending go-forward
      ((ball-distance 24) (ball-direction forward)) : sending go-forward
      ((ball-distance 23) (ball-direction left)) : sending go-left
      ((ball-distance 23) (ball-direction forward)) : sending go-forward
      ((ball-distance 22) (ball-direction forward)) : sending go-forward
      ((ball-distance 21) (ball-direction forward)) : sending go-forward
      ((ball-distance 20) (ball-direction right)) : sending go-right
      ((ball-distance 20) (ball-direction forward)) : sending go-forward
      ((ball-distance 19) (ball-direction forward)) : sending go-forward
      ((ball-distance 18) (ball-direction left)) : sending go-left
      ((ball-distance 18) (ball-direction forward)) : sending go-forward
      ((ball-distance 17) (ball-direction forward)) : sending go-forward
      ((ball-distance 16) (ball-direction forward)) : sending go-forward
      ((ball-distance 15) (ball-direction right)) : sending go-right
      ((ball-distance 15) (ball-direction forward)) : sending go-forward
      ((ball-distance 14) (ball-direction forward)) : sending go-forward
      ((ball-distance 13) (ball-direction left)) : sending go-left
      ((ball-distance 13) (ball-direction forward)) : sending go-forward
      ((ball-distance 12) (ball-direction forward)) : sending go-forward
      ((ball-distance 11) (ball-direction forward)) : sending go-forward
      ((ball-distance 10) (ball-direction right)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending kick
      ((ball-distance 110) (ball-direction forward)) : sending go-forward
      ((ball-distance 109) (ball-direction forward)) : sending go-forward

And so on.

You can install the default robot by evaluating the expression:

(set-current-robot! (make-default-robot))

The simulated soccer robot

The simulated robot has three sensors: ball-in-sight, ball-distance and ball-direction; and five actions: go-forward, go-backward, go-left, go-right and kick.

You can install a simulated robot by evaluating the expressions:

       (require "robot-sim.ss")
       (set-current-robot! (make-frtime-robot))

When you install the simulated robot, a window will open with a display of the simulated robot.

You can control this robot both via the keyboard and via your Brainscript implementation. On the keyboard, the arrow keys make the robot move, the shift key stops it, and the control key activates the kicking device. The goal of the game is to kick the ball with the kicker many times.

Of course, it is more fun if the robot kicks the ball autonomously, via Brainscript. In Brainscript, (do-action-loop 'go-forward) makes the robot go forward (similarly for 'go-backward, 'go-left and 'go-right). (do-action-loop 'kick) runs the kicker device. With the simulated robot, (read-sensor-cache 'ball-in-sight) will return either true if the ball is within the range of vision of the robot, otherwise it will return false. When the ball is not in sight, (read-sensor-cache 'ball-direction) returns 'out-of-sight. In that respect, the game is harder from Brainscript's perceptive, since you do not always know where the ball is.

FAQ

If an infinite loop does not contain a robot action, Brainscript never breaks out of the loop. This is because, if there are no robot actions, nothing checks if the guards have become false. That's ok. This is how Brainscript is supposed to work.
cond-flip breaks out if any one of the guards before the current branch switches from false to true. The invariant is that we execute the branch of the first guard that returned true during the latest stack check.

Changes

Sat Dec 4 2004 :

Added else to the grammar specification of cond-flip

Wed Dec 1 2004 :

Described the available robots.
timed was missing its ellipsis in the grammar definition.
Documented watch-macro-expansion.
Added two FAQ items.

CS 173

“Assignments in Programming Languages!”