Sample question (on the hard side)

You are to write an interpreter for a small robot control language. The robot starts at position (0,0) of an infinite grid. The basic commands of the robot control language are simple moves which intruct the robot to move

North, East,
South

or West. This is represent in Ocaml as:

type move = N | E | S | W

If a robot is at position (x,y) then a command N moves it to position (x+1,y), a command E moves it to position (x,y+1), and so on.

Write a function interp of type move -> (int,int) -> (int,int). The function should take a move, the current position of the robot, and return the new position. For example,
```
interp N (4,2)
```
should return (5,2).
The command language of our robot is extremely poor. We would like to tell our robot to perform a certain sequence of commands. We extend our language as follows:
```
type move = N | E | S | W 
          | Sequence of move list 
```
Extend the function interp to implement this new case. For example,
- interp (Sequence [N; N; N; N]) (5,2) returns (9,2)
- interp (Sequence [N; N; Sequence [E; E; E]; N; N]) (5,2) returns (9,5)
- interp (Sequence [N; Sequence [E; E; E]; N; Sequence [E; E; E]; N; Sequence [E; E; E]; N]) (5,2) returns (9,11).
To make the command more convenient we would like to bind certain sequences to names and then invoke them later. For example, the last example above would be convenient to write as:
```
interp (Define("3E", Sequence [E;E;E], 
              Sequence [N; Invoke "3E"; N; Invoke "3E"; N; Invoke "3E"; N]))
       (5,2)
```
In other words the command language is now:
```
type move = N | E | S | W 
          | Sequence of move list 
          | Define of string * move * move 
          | Invoke of string
```
Modify and extend the function interp appropriately.

Sample question (on the hard side)

Final solution