Home‎ > ‎CIS 98‎ > ‎

The Art of Programming

  1. PowerPoint Slides
  2. Programming in Middle Earth
    1. Frodo's World
      • 2 dimensional flat plane (potentially infinite size)
      • Bounded to the west and south by a vertical wall
      • Plane is diced by vertical and horizontal paths, or streets
      • The distance between two streets is a block
      • The origin refers to the intersection of streets 0 and 0
      • Middle Earth is inhabited by Frodo, (a Hobbit Robot), vertical wall sections and rings of power
    2. Frodo's Capabilities
      • Frodo can move forward 1 block at a time     move
      • He can turn to the right 90 degrees     turnright
      • He can pick up rings if they are in the same intersection as he is standing     pickring
      • He can deposit rings that he may be carrying in his ring-bearing bag     putring
      • He can turn himself off.     stop
    3. Tasks and Situations
      Something we want Frodo to do as specified by a program, or list of instructions
      An exact description of what Frodo's world looks like, e.g.
      • Frodo's position and direction he is facing
      • Location and size of each wall section
      • Location of each ring in the world, including the number of rings in Frodo's bag.
  3. Primitive Instructions
    • move When Frodo executes a move instruction, he moves forward one block; he continues to face the same direction. Frodo will not move beyond the existing boundaries of Middle Earth; an attempt to move beyond the grid will fail, and Frodo will remain in the position he was before the instruction was executed. To avoid damaging himself, Frodo will not move into a wall section. If he sees a wall section between himself and the corner he would otherwise occupy, he executes the stop instruction. This action is called an error shutoff, and it terminates the execution of the program.
    • turnright Frodo executes a turnright instruction by pivoting 90 degrees to the right; thus, Frodo remains on the same street corner while executing a turnright instruction. The turnright instruction cannot result in an error shutoff. Why?
    • pickring When Frodo executes a pickring instruction, he picks up a ring from the corner on which he is standing, and then deposits it in his ring-bearing bag. If he executes a prickring instruction on a ringless corner, Frodo performs an error shutoff. On a corner with more than one ring, Frodo picks up one and only one of the rings and then places it in the ring bag.
    • putring Frodo executes a putring instruction by extracting a ring from his ring-bag and placing it on his current street corner. If Frodo tries to execute a putring instruction with an empty ring bag, he performs an error shutoff.
    • is_clear Frodo uses his forward camera to tell if the path is clear or blocked. The instruction returns "true" or "success" if the way is clear, and "false" if the way is blocked. 
      This instruction takes an argument of RIGHT or LEFT to determine if the path is clear to his immediate right or left respectively.
    • next_to_ring Frodo uses a metal detecting sensor to tell if there are any rings located on the block where he is standing. The instruction returns "true" or "success" if there is at least 1 ring for him to pick up, and returns "false" if there are no rings within his reach.
    • any_rings Frodo uses a sensor to tell if there are any rings located in his ring-bearing bag. The instruction returns "true" or "success" if there is at least 1 ring in his bag, and returns "false" if there are no rings in his bag.
    • at_origin Returns success (true) if Frodo is at the origin, Square (0,0); otherwise, failure.
    • facing NORTH | EAST | SOUTH | WEST Returns success (true) if Frodo is facing in the direction that is specified with the command. e.g. '>' implies facing EAST is true.
    • stop This instruction is our way of telling Frodo that hi is finished with his task. When he executes a stop instruction, he turns himself off and is incapable of executing any more instructions until he is restarted on another task. The last instruction in every Middle Earth program must be a stop instruction.
    • start The start instruction is executed automatically when you invoke the Frodo interpreter.

  4. The Form of a Program
    1. HEADER - Comment fields describing the purpose of the program
    2. BODY - a sequence of instructions; one instruction per line
    3. END - the stop instruction
  5. Program Errors
    1. syntactic (grammar) e.g. two instructions on one line
    2. semantic (logic) e.g. a turnright instruction when you meant to turn left
  6. Functions - a mechanism for defining new instructions
    Functions have two parts:
    1. A Name: function-name()
      A Function name must be comprised of letters, numbers, dashes (-) and underscores (_) and must always end with a pair of parentheses.
    2. A Body: A set of instructions beginning and ending with curly brackets, { } 
      Once Defined, a function can be executed by invoking just the name of the function as if it were a primitive instruction. Note: the parenthesis are not included with the name when invoking a function.

Exercise 1

Using map1 as your guide, create a file called myprogram that contains the instructions to make Frodo snatch the ring in the lower cave and place it in the upper house in the same square as the other ring. Notice that Frodo's starting location is on the corner of 2nd and 9th street. Your last command should be a stop command; this will terminate the program.

Exercise 2

Write a program called lap that makes Frodo traverse the perimeter of Middle Earth starting and ending at the origin.

Exercise 3

Rewrite the lap program using a turnleft function and a dash function. The dash function should simply move Frodo 10 blocks in the direction he is pointing.
Notice how the body of the program becomes more readable when new instructions are defined.