Karel the Robot

The purpose of the Karel language and runtime environment was educational. Like Logo (Turtle Graphics) the program was developed to give people unfamiliar with computer programming a starting environment with a gentle learning curve.

Richard Pattis at Stanford developed the language and used it as a first step in teaching an introductory programming course in the Pascal language. Much of the original rules and syntax mimic Pascal. This was intentional. Students got used to being careful with syntax, finding bugs and developing small programs in a simpler environment before diving into the complexities of Pascal itself.

Karel is known as much for the language features it lacks as for those it has. There are no data structures, no variables, no values or assignment of values, no numbers or strings. What it does have are very simple commands to move Karel around his environment. This environment consists of pathways and wall sections with Karel somewhere on a pathway. Karel can't see but can feel his way around. He can tell if there is a wall section in front of him, to his left or to his right. He also has a compass and can tell if he is facing North, East, South or West. Initially, until you, the programmer, have taught him more, he can do only a very few commands such as move a step forward, turnleft, and turnoff.

There are also "Beepers" in the environment and Karel has a bag to store any number of them. If the bag is not empty Karel can leave a beeper at his current location or put a beeper into his bag if there are any at his location. He can tell if his bag is empty or not and also whether there are any beepers at his current location. We'll see how in a moment. But he can't know how many because, of course, he has no concept of numbers.

So two more primitive instructions, pickbeeper (from location to bag) and putbeeper are available.

As we'll see later, these simple instructions are augmented with just a few control instructions such as IF/ELSE and WHILE as well as a means to create subprograms.

This implementation just uses the terminal window in Linux. With each change in the environment the screen is cleared and redrawn. This is done with a system call that runs the program clear. For windows find the os.system call and change the program name to cls. For windows you will also need to be able to run Python from the Command window.

Let's look at an example environment as defined here

# Find your way out of the box

|-----------------------|
| .........1........... |
| ....xxxxx.xxxxxxx.... |
| ....x...........x.... |
| ....x...........x.... |
| ....x......^....x.... |
| ....x...........x.... |
| ....xxxxxxxxxxxxx.... |
| ..................... |
|-----------------------|

It's just a simple text file. Karel is the "^" roughly in the center. Periods are locations that Karel can move to. A number (like the "1") is a hidden period that Karel can visit and indeed detect that 1 beeper is there for the picking. Everything else is "wall material" that Karel can feel but must not try to move into.

The example is a box with an opening on the North (top) side. Karel will exit the box by first finding the West wall, follow it north to the north wall, follow that until he senses the opening and finally exit. Here is an animation, without the beeper 1.

The following Karel program accomplishes this in a very basic manner. It will be explained, modified and improved in a later section.

# Find your way out of the box. Door on north side
#
BEGIN
  WHILE not-facing-west DO turnleft

  WHILE front-is-clear DO move
  turnleft turnleft turnleft

  WHILE front-is-clear DO move
  turnleft turnleft turnleft

  WHILE left-is-blocked DO move

  turnleft move move
  turnoff
END

Karel's Environment

The world of Karel consists mostly of what we have seen above. It is contained in an instance of the class Env. The following is code from runtime.py

05 class Environment :
06     def __init__(self, text, fatal, interval=.3) :
07         self.board = text.rstrip().split("\n")
08         self.board = filter(lambda x: len(x)>0, self.board)
09         self.karelPos = self.karelDir = None
10         self.karelBeepers = 0           # beepers in Karel's bag
11         self.beepers = {}               # squares with beepers
12         self.fatal   = fatal            # the exit function
13         self.interval   = interval      # the time between moves
14         self.nrows = len(self.board)    # rows on the board
15         self.ncols = len(self.board[0]) # row 0 must be longest
16         self.incr  = ((-1,0),(0,1),(1,0),(0,-1)) # for each dirc
17         self.conditions = conditions    # boolean tests
18         for row in range(self.nrows) :
19             self.board[row] = list(self.board[row]) # nested lists
20             for col in range(self.ncols) :
21                 pos = (row,col)
22                 c = self.board[row][col]
23                 kdir = "^>v<".find(c)    # set Karel's direction by symbol
24                 if kdir >= 0 :
25                     self.karelPos = (row,col)
26                     self.karelDir = kdir
27                 elif " 123456789".find(c) > 0 :
28                     self.beepers[pos] = int(c) # set # of beepers for pos
29

The initial board is set (line 9). Some attributes are set (10-18) and then board is split into a 2 dimensional list of of single characters. Karel is found (24) and his direction set by the symbol used. His direction is 0-3 for North, East, South and West. North points up like a map. As Karel turns the direction is adjusted with modulo addition, keeping it in the same 0-3 range. Symbols 1-9 are also used to set the number of beepers for each square that contains any.

Methods for inspecting and manipulating the environment follow

31     def getSquare(self, dirc) : # dirc relative to kdir
32         incr  = ((-1,0),(0,1),(1,0),(0,-1)) # for each dirc
33         kpos  = self.karelPos
34         kdir  = self.karelDir
35         ndir  = (kdir+dirc)%4
36         return self.addPos(kpos,self.incr[ndir])
37
38     def isBlocked(self,sqr) :
39         occu = self.boardGet(sqr)
40         return not (occu == '.' or self.beepers.get(sqr))
41
42     def nbrBlocked(self, dirc) :
43         sqr = self.getSquare(dirc)
44         return self.isBlocked(sqr)
45

Determining if neighboring squares to Karel are blocked or not (38-40) uses the method getSquare. This is passed a direction for ahead, right or left. Karel can't look backwards. Positions such as kpos are tuples with (row,column) and the method addpos adds positions. Notice the modular addition in line 35 and the relative position of the neighboring squares in line 31.

The ability to move Karel is actually the most detailed item.

46     def move(self) :
47         kdir = self.karelDir
48         kpos = self.karelPos
49         dest = self.getSquare(0)  # one square ahead
50         beeps= self.beepers.get(kpos)
51         sym  = self.boardGet(kpos)
52         if not self.isBlocked(dest) :
53             self.boardPut(dest,sym)         # Place Karel here
54             self.karelPos = dest
55             if beeps : old = str(beeps)[0]  # just room for 1 digit
56             else     : old = "."
57             self.boardPut(kpos,old)         # replace prev content
58         else : self.fatal("move is blocked")
59         self.printBoard()
60

Karel needs to move one square ahead (line 48=9). The square must be unblocked (52). We put Karel's symbol at the new square (53) and restore the square we just left. If there were beepers there we put the appropriate digit back (55), otherwise just the empty symbol "." and finally, print the board (59).

Handling beepers is pretty straight-forward.

61     def pickbeeper(self) :
62         kpos = self.karelPos
63         if not self.beepers.get(kpos) : self.fatal("No beeper to pick up")
64         else :
65             self.beepers[kpos] -= 1
66             self.karelBeepers  += 1
67         self.printBoard()
68
69     def putbeeper(self) :
70         kpos = self.karelPos
71         if not self.karelBeepers : self.fatal("No beeper to put down")
72         else :
73             self.beepers[kpos] = self.beepers.get(kpos,0) + 1
74             self.karelBeepers  -= 1
75         self.printBoard()
76

The dictionary beepers contains the number of beepers for each square having some. We just transfer a beeper from square to Karel's beeper bag (65-66) or the other way around (73-74).

Finally, the primitive instruction turnleft is fairly simple.

77     def turnleft(self) :
78         self.karelDir = (self.karelDir-1) % 4  # 0-3 to the left
79         row,col = self.karelPos
80         self.board[row][col] = "^>v<"[self.karelDir]
81         self.printBoard()
82

Our modulo addition (counter clockwise) sets the new direction and updates Karel's symbol on the board (80).

Printing the board is done at spaced amount of time after each change. First the terminal windows is erased with the system call clear (or in Windows CLS), the rows of the board reconstituted from lists into strings and printed.

 95     def printBoard(self) :
 96         if not testing :
 97             time.sleep(self.interval)
 98             os.system('clear')   # in windows change 'clear' to 'cls'
 99         for row in range(self.nrows) :
100             print("".join(self.board[row]))  # make a string from list
101

Finally, there are conditions that we will need to check. The names of the conditions are keys in a dictionary conditions and each key points to a function (lambda expression) that returns True or False.

102 conditions = {
103   "facing-north"     : lambda env: env.karelDir == 0,
104   "not-facing-north" : lambda env: env.karelDir != 0,
105   "facing-east"      : lambda env: env.karelDir == 1,
106   "not-facing-east"  : lambda env: env.karelDir != 1,
107   "facing-south"     : lambda env: env.karelDir == 2,
108   "not-facing-south" : lambda env: env.karelDir != 2,
109   "facing-west"      : lambda env: env.karelDir == 3,
110   "not-facing-west"  : lambda env: env.karelDir != 3,
111   "front-is-clear"   : lambda env: not env.nbrBlocked(0),
112   "front-is-blocked" : lambda env:     env.nbrBlocked(0),
113   "right-is-clear"   : lambda env: not env.nbrBlocked(1),
114   "right-is-blocked" : lambda env:     env.nbrBlocked(1),
115   "left-is-clear"    : lambda env: not env.nbrBlocked(3),
116   "left-is-blocked"  : lambda env:     env.nbrBlocked(3),
117   "next-to-a-beeper"     : lambda env: env.beepers.get(env.karelPos,0) > 0,
118   "not-next-to-a-beeper" : lambda env: env.beepers.get(env.karelPos,0) < 1,
119   "any-beepers-in-beeper-bag": lambda env: env.karelBeepers > 0,
120   "no-beepers-in-beeper-bag" : lambda env: env.karelBeepers < 1,
121 }
122

Karel's Language

We saw an example of a Karel program above finding its way out of a box and picking up the beeper at the extrance. It consists of basic instructions plus the WHILE instruction. The control instructions are WHILE, IF/ELSE, ITERATE, DEFINE-INSTRUCTION/AS, BEGIN/END and enable us to create more interesting programs. These instructions are in upper-case.

This dialect of the Karel language has taken a few liberties from the original in 1978. There, program sections delimitated the main logic from subprograms and also instructions seperated with a strict use of semicolons. This mirrored rules in the Pascal language which the students would later be learning. I've taken a more Pythonic approach. The semicolons are optional and Python style comments are also allowed.

This is the complete set of control instructions

BEGIN <inst> <inst> ... END. gathers instructions to be executed sequentially into a single instruction

DEFINE-NEW-INSTRUCTION <name> AS <inst> lets you create subprograms. The name becomes an alias for the <inst> which is generally a BEGIN/END construct

WHILE <condition> DO <inst> we've seen already

ITERATE <number> TIMES <inst> works much like a for i in range(xx)

IF <condition> THEN <inst1> [ELSE <inst2>] works as you expect. The square brackets indicate that the ELSE part is optional

The compilation of a Karel program results in a very simple data structure.

A simple instruction is a string with the name. "turnleft"

A BEGIN/END multiple instruction is a list of instructions

An ITERATE is a list like ["ITERATE", <number>, "TIMES", <inst> ]

A WHILE is a list like ["WHILE", <condition>, <inst>]

An IF is like ["IF", <condition>, <inst1>, <inst2>]. If there is no ELSE then <inst2> is the value None.

The module lang.py contains the class for compiling and interpreting programs in the Karel language:

01 # lang.py
02
03 class Lang :
04     def __init__(self, env, source) :
05         self.env   = env
06         self.conditions = env.conditions
07         self.words = source.split()     # Make prog a list of words
08         self.lookup= {}                 # for defined words

On initialization an environment is passed from the caller. The conditions table with each condition referencing a function is kept locally. The source code for the program already has had its comments and semicolons stripped and is simply split into a list of words. The lookup table for words that will be defined is created.

09
10     def consume(self, what) :
11         word = self.getword()
12         if word == what : return True
13         else : self.exit ("Expecting %s" % what)
14
15     def exit(self, mesg) :
16         import sys
17         trace = "<%s>" % " ".join(self.ahead)
18         if mesg : print("Fatal error: %s %s" % (mesg,trace))
19         sys.exit()

The function consume tracks "empty" words such as "TIMES", "AS" making sure they appear when expected. Method exit is used for compilation errors to show where in the source the error occured.

20
21     def execInstruction(self, inst) :
22         if not inst : return
23         if   inst == "move"       : self.env.move()
24         elif inst == "turnleft"   : self.env.turnleft()
25         elif inst == "pickbeeper" : self.env.pickbeeper()
26         elif inst == "putbeeper"  : self.env.putbeeper()
27         elif inst == "turnoff"    : self.exit(None)
28         elif inst == ""           : pass

Method execInstruction is passed a compiled instruction, either a word or a list. If it is a simple instruction the the environment is requested to carry it out.

29
30         elif inst[0] == "IF" :          # IF cond THEN ... [ELSE ...]
31             if self.conditions[inst[1]](self.env) :
32                 self.execInstruction(inst[2])
33             elif inst[3] :
34                 self.execInstruction(inst[3])  # optional ELSE

An IF tests the condition in the environment. If it returns True the instruction after the IF is executed, otherwise if there is an ELSE clause then that is executed.

35
36         elif inst[0] == "ITERATE" :     # ITERATE times ...
37             for i in range(inst[1]) :
38                 self.execInstruction(inst[2])
39
40         elif inst[0] == "WHILE" :       # WHILE cond DO ...
41             while self.conditions[inst[1]](self.env) :
42                 self.execInstruction(inst[2])
43
44         elif type(inst) == type([]) :   # BEGIN ... END
45             for subInst in inst : self.execInstruction(subInst)
46
47         else : self.exit("Illegal instruction: %s" % inst)

With the above in mind, lines 35-47 should be easy to grasp. Note that an illegal instruction (line 47) will use the local exit method.

Next is the compilation phase.

49     def getword(self) :
50         if not self.words : return "EOF"
51         self.ahead = self.words[:6]     # for error messages
52         word = self.words.pop(0)
53         return word

Method getword accesses the next word in the program. It also sets ahead in case there is an error to let the programmer know where in the program the error occurred.

55     def getInstruction(self) :
56         word = self.getword()
57         if word == "EOF"   : return "EOF"
58         if word == "BEGIN" :
59             insts = []
60             while self.nextword() != "END" :
61                 inst = self.getInstruction()
62                 if inst : insts.append(inst)
63             self.consume("END")
64             return insts

Method getInstruction compiles an instruction into a list or simple string. At line 58 the BEGIN/END instruction is handled. Notice the recursive call at line 61 to handle nested structures. Method nextword allows one word lookahead in the source.

65
66         elif word == "DEFINE-NEW-INSTRUCTION" :
67             name = self.getword()
68             self.consume("AS")
69             inst = self.getInstruction()
70             self.lookup[name] = inst
71             return None

DEFINE-NEW-INSTRUCTION creates subprograms, attaching an instruction to a name in the lookup table (line 70).

72
73         elif word == "ITERATE" :
74             times = int(self.getword())
75             self.consume("TIMES")
76             inst = self.getInstruction()
77             return ["ITERATE",times,inst]
78
79         elif word == "WHILE" :
80             cond  = self.getword()
81             self.consume("DO")
82             inst = self.getInstruction()
83             return ["WHILE",cond,inst]
84
85         elif word == "IF" :
86             cond  = self.getword()
87             self.consume("THEN")
88             inst1 = self.getInstruction()
89             if self.nextword() != 'ELSE' :
90                 return ["IF", cond, inst1, None]
91             self.consume("ELSE")
92             inst2 = self.getInstruction()
93             return ["IF", cond, inst1, inst2]
94         else :
95             return self.lookup.get(word,word)  # change if it was redefined

The last 4 clauses above should at this point be self-explanatory.

97     def nextword(self) :
98         if self.words : return self.words[0]
99         else          : return None

The last method nextword lets us peek at the word coming up without consuming it.

In the Drivers Seat

The main program karel.py is quite straight-forward.

3 #  karel.py
 4 #
 5 from   runtime  import Environment
 6 from   lang     import Lang
 7
 8 def readProgram(karelProgram) :
 9     import re
10     prog = open(karelProgram).read()
11     prog = re.sub("#.*"," ",prog)      # strip comments
12     return re.sub(";"," ",prog)        # semicolons are optional
13

The Karel program resides in the file passed. It is opened and read as a single string. Comments starting with *#* continuing to *\\n* become just whitespace (line 11) and those pesky semicolons are also just changed to whitespace.

14 def readBoard(game) :
15     # make into a square box
16     board = open(game).readlines() # initial board
17     board = [x.strip() for x in board]
18     board = list(filter(lambda x: len(x)>0, board))
19     width = max([len(x) for x in board])
20     board = list([x.ljust(width) for x in board])
21     return  list(board)
22

Reading the initial board setup is more complex. The board is a list of lines all padded to the maximum width for easy navigation. Empty lines are discarded (16) and the board is returned as a 2 dimensional array. Notice the necessity of applying the list function in lines 18 and 20. This is necessary for Python 3 which returns iterators for many functions like filter .

23 def main() :
24     import sys
25     game = sys.argv[1]
26     startBoard = readBoard(game)
27     program = readProgram(sys.argv[2])
28
29     env = Environment(startBoard,exit)
30     env.printBoard()
31     prog = Lang(env, program)
32     while True :
33         inst = prog.getInstruction()
34         if inst == "EOF" : break
35         if not inst : continue
36         prog.execInstruction(inst)
37
38 if __name__ == "__main__" : main()
39

The entry point takes 2 arguments. A game board and a program in Karel. The initial environment is created (line 29). The program is compiled as a Lang instance (line 31) and then the instruction are executed one by one.

A simple example follows.

 1 # Find your way out of the box. Door on north side
 2 #
 3 BEGIN
 4   WHILE not-facing-west DO turnleft
 5
 6   WHILE front-is-clear DO move
 7   turnleft turnleft turnleft
 8
 9   WHILE front-is-clear DO move
10   turnleft turnleft turnleft
11
12   WHILE left-is-blocked DO move
13
14   turnleft move move
15   WHILE not-next-to-a-beeper DO move
16   pickbeeper turnleft move move
17   putbeeper move
18   turnoff
19 END
20

The program is invoked as follows.

$ python karel.py box.brd box1.krl

The program box2.krl makes better use of subprograms.

 1 # Find your way out of the box. Door on north side
 2 #
 3 BEGIN
 4   WHILE not-facing-west DO turnleft
 5
 6   WHILE front-is-clear DO move
 7   turnleft turnleft turnleft
 8
 9   WHILE front-is-clear DO move
10   turnleft turnleft turnleft
11
12   WHILE left-is-blocked DO move
13
14   turnleft move move
15   WHILE not-next-to-a-beeper DO move
16   pickbeeper turnleft move move
17   putbeeper move
18   turnoff
19 END
20

Odds and Ends

You can download the zip file for Karel here. It includes 2 more programs climb and stack each with a .krl and .py file. They also use the IF/THEN and ITERATE instructions. They are run with:

$ python karel.py climb climb.krl   # python3 also ok
$ python karel.py stack stack.krl

If you have comments or suggestions You can email me at mail me

* * *