SEQUENTIAL AND FUNCTIONAL PROGRAMMING IN SCHEME
SIMULATING STATE CHANGES

Scheme is, as you know, a functional language, which technically means
that there is no such thing as 'state' in Scheme. In practice, there are
several extremely useful things that computers do which require - or, at
least, benefit greatly from - the use of non-functional programming. These
include input-output and random numbers.

As a compromise, then, Scheme allows changes in state, simply for convenience.
Obviously, we've already seen one feature of Scheme which allows changes in
state - namely, define

  STk> foo ;;At this point, foo is unbound
  *** Error:
      unbound variable: foo
  STk> (define foo 5) ;;Here we define foo
  foo
  STk> foo ;;And now it is defined
  5

Define, therefore, changed the state of Scheme so that a previously
undefined variable was now defined. You may not have seen it before, but
there is a function which modifies the value of an already extant variable.
This function is set!, where the ! at the end indicates that it effects
a change in state.

  STk> (define bar 8)
  bar
  STk> bar
  8
  STk> (set! bar 3)
  okay
  STk> bar
  3

Critically, set! will only work if the variable has already been defined,
and define is only supposed to be used when something has not yet been
defined. (In practice, it will redefine the value of a variable - but
when you're trying to redefine the value of something that's not a function,
you should use set! instead of define.)

  STk> (set! baz 'something)
  *** Error:
      set!: variable not defined: baz


FACTORIAL - SEQUENTIAL AND FUNCTIONAL

In a lot of programming languages, factorial looks a lot different from
Scheme's recursive factorial. That's because a lot of programming language
have something called 'loops' which take advantage of sequential programming
to do a given thing again and again until the state of the program changes
in a way that it finds appropriate. Here's what that might look like in a
(fictional) programming language.

In this language, the symbol := works like set!, assigning the value on
the right to the variable on the left.

x := 0;
while (x < 10) {
  print(x);
  x := x + 1;
}

This will print every number starting at 0 and ending with 9. Think about
how we might do this in Scheme, without state. We'd probably use recursion.

(define (count-to-nine x)
  (if (< x 10)
      (begin (print x) (count-to-nine (+ x 1)))))

(count-to-nine 0)

Well, unbeknownst to you, Scheme can also use a while contruction! We never
introduced it because it requires changes in state, but here's the same
thing using Scheme's while:

(define (count-to-nine)
  (let ((x 0))
   (while (x < 10)
     (print x)
     (set! x (+ x 1)))))

Looks a little bit different, eh? Let's try a harder problem with this - the
traditional factorial. Using sequential programming, it might look more
like this:

define factorial(x) {
  result := 1
  while (x > 0){
    result := result * x;
    x := x - 1;
  }
  return result;
}

This will loop until x is 0 and change result each time, multiplying it by
every number from x through 1, and then finally return that value. Now, in
sequential Scheme:

(define (factorial x)
  (let ((result 1))
   (while (> x 0)
     (set! result (* result x))
     (set! x (- x 1)))
   result
))

...pretty gross, huh? Compare it to the old, familiar

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

and you'll see that it looks a lot hairier and weird. Here's an example where
doing state changes just ends up complicating things, and doesn't really give
us any benefit as a programmer. Here's a good example of the drawbacks of
sequential programming - in Scheme, it's not very natural to program this
way, and most problems are more easily and efficiently solved using idiomatic
Scheme constructs like recursion or higher-order functions. Here's an
even worse example:

(define (mystery x)
  (let ((foo '()))
   (while (not (null? x))
     (set! foo (cons (square (car x)) foo))
     (set! x (cdr x)))
   (reverse x)))

...figured it out? This, in functional Scheme, could more easily be written as

(define (mystery x)
  (map square x))

With a massive boost in clarity and simplicity!

Now, there are situations where we think that changing state might be an
excellent idea. Let's say we've got a video game where the player moves
all over a board and can spend money or something else. You might expect
to see a lot of 

(set! player-location new-location)

and 

(set! player-money (- player-money 5))

However! Just because we can do this, it doesn't necessarily mean we should.
Sometimes, you may be tempted to use changes in state to manage large
amounts of information, but that doesn't mean that's the best way. Let's take
a look at how we'd do a simple interactive game without using state change.


TREASURE HUNTER CASE STUDY

First, let's imagine that we want to make a treasure-hunting game for
our final project. In this game, you have a 20x20 grid, so coordinates go
from 0 to 19 on each axis, for 400 possible locations. As a player, you can
move north, south, east and west, and you have two other actions available
to you - 'sense' and 'dig.'

The goal of this game is that you want to dig up a piece of treasure that
you know is somewhere on this game board, but the trick is this - digging
costs money, and you want to end up with as much money as possible. So, you
use a metal detector which tells you if you're near the treasure, which costs
far less to use. Let's look at how we want a game of this to look:

  Welcome to Treasure Hunter!
  You begin at (10, 10) with $50.
  > north
  You are at (10, 11)
  > north
  You are at (10, 12)
  > sense	 
  ...nothing. You must not be very close. Money is at $49
  > east
  You are at (11, 12)
  > east
  You are at (12, 12)
  > east
  You are at (13, 12)
  > sense
  beep... beep... beep... You're getting closer. Money is at $48
      [ ... excised for reasons of monotony ... ]
  > north
  You are at (18, 18)
  > sense
  beepbeepbeep! You're close! Money is at $42
  > dig
  It's not here. Money is at $30
  > north
  You are at (18, 19)
  > dig
  You've found the treasure! It's a box of gold.
  Congratulations! You found the treasure with $28 to spare!


Let's think about what a game like this would need. First, it needs some way
to keep track of where the player is standing and where the treasure is
hidden. You also need some way to allow the player to move from place to place,
and some way to figure out how far away the treasure is.

For simplicity's sake, let's assume we already have the following definitions:

  (display-sensor-message player-location treasure-location)

  ;;Takes, as arguments, two two-argument lists representing the player's
  ;;and treasure's locations, respectively. So
  ;; (display-sensor-message '(0 0) '(20 20)) ;;prints something like
  ;;   ...nothing. You're nowhere near the treasure.
  ;; (display-sensor-message '(10 10) '(10 10)) ;;prints something like
  ;;   beepbeepbeep! You're right on top of it!
  ;; And other values would print appropriate messages.

  (display-player-location player-location)

  ;;Takes, as argument, the player's location as a two-element list
  ;;and prints it in a pretty way for the player.
  ;; (display-player-location '(5 15)) ;;prints something like
  ;;   You are at (5, 15)

  (display-amount money)

  ;;Takes, as argument, an integer represent an amount of money
  ;;and prints it in a pretty way for the player.
  ;; (display-amount 22) ;;prints something like
  ;;   Money is at $22

  (display-winning-message money)

  ;;Takes the player's money as argument and prints a winning message.
  ;;For example:
  ;; (display-winning-message 40)
  ;;   You've found the treasure! It's a priceless heirloom.
  ;;   Congratulations! You had $40 to spare.

  (is-valid-command? cmd)

  ;;Takes a word as argument and determines whether it's a valid
  ;;command for our game.
  ;; (is-valid-command? 'north) returns #t
  ;; (is-valid-command? 'beowulf) returns #f
  
  (get-next-location player-location direction)
  ;;Takes the player's location as a two-element list and a word
  ;;that is one of the four cardinal directions, and returns
  ;;the coordinate to that direction.
  ;; (get-next-location '(10 10) 'north) returns '(10 11)
  ;; (get-next-location '(2 5) 'east) returns '(3 5)

Now, let's get to it, shall we?

We want the game to keep looping until the player wins. That really means
we want a recursive function; in this case, we'll use a helper function, so
we can call the game by simply typing (play-game). We'll write this last,
so we can write the helper first.

The helper function is going to need to keep track of the state. There are
really three parts to the state of the game - the player's location, the
player's money, and the treasure's location. Our helper function is going
to look a bit like this:

(define (game-loop player treasure money)
  ...)

Now, what do we need to do each time? Well, it can be broken down into
a few steps:

1. Get the input from the player.
2. Make sure it's proper input - in our case, one of the words
     north, south, east, west, sense, or dig. We can also accept the letters
     n, s, e, and w as shorthand, if we'd like, to make it easier on
     the player.
3. Tell the player what has changed as a result of their command.
4. Recurse, taking into account the changes in the world.


Rather than walk step-by-step through the writing of this, I'll
write the entire thing and then explain how each section contributes to this.


(define (game-loop player treasure money)
  (display "> "
  (let ((new-command (read)))

    (cond ((not (is-valid-command? new-command))
	   (display "Invalid command!\n"))

	  ((member new-command '(north south east west n s e w))
	   (let ((new-location (get-next-location player new-command)))
	     (display-player new-location)
	     (game-loop new-location treasure money)))

	  ((equal? new-command 'sense)
	   (let ((new-money (- money 1)))
	     (display-sensor-message player treasure)
	     (display-amount new-money)
	     (game-loop player treasure new-money)))

	  ((equal? new-command 'dig)
	   (let ((new-money (- money 12)))
	     (if (equal? player treasure)
		 (display-winning-message new-money)
		 (begin
		   (display "It's not here. ")
		   (display-amount new-money)
		   (game-loop player treasure new-money))))))))


Whew! It looks a bit daunting, but let's take a look at what it's doing
step by step.

The first thing we see is a let which creates a new variable, called
new-command, and sets it to a word which is being read from the keyboard.
There is also a display call so we get the pretty > prompt before the user
input, but that's a purely aesthetic concern.

It's VERY IMPORTANT that we use a let statement like this for the user input.
If we use read more than once in a single call to game-loop, then we'll find
that it tries to read a new token for each call - which is not what we want
at all! Using a let like this allows us to read only one value and continue
using that same value multiple times.

The next step is to figure out how to change the world as a result of that
command. Here, we use a cond to look at every possible case. The first case
is that it's not a valid command at all! Our function is-valid-command? will
determine whether the user has typed something which doesn't make sense, and
deal with it accordingly.

The next condition handles all motion - that is, all compass directions. If
new-command is any direction, then we figure out which new grid square the
player is trying to go to, inform the player of the change, and then begin
the next step with the updated information. Notice that the recusrive call
to game-loop uses almost all the same arguments it was first called with,
as only the player's location has changed - it costs no money to move, and
the treasure never moves at all, so both the money and treasure-location
variables do not change. (This let, unlike the previous one, is purely
for simplicity's sake; it could be removed, sacrificing some readability.)

The next condition is the sense condition. Our display-sensor-message function
takes care of the hard parts - figuring out how far the treasure is and
printing the appropriate message - so all we need to do is subtract a dollar
for sensing and recurse. The player has not moved, and neither has the
treasure, so when we recurse, we keep those the same and use the new
dollar value.

Finally, the digging. If we dig, we subtract twelve dollars and then check
to see if we dug in the right place. If the player's right on top of the
treasure, then we display the winning message and be done with it. However,
if the player is elsewhere, we print an appropriate message and inform the
player of their new amount of money, and finally recurse with the money
changed.


There! Not so bad, eh?

(As a side note, there are a few problems with the game; fixing them will be
left as an optional exercise. First and foremost is that it's impossible to
lose - we have a money amount, but if it goes negative, nothing happens! How
would we change the game to end if the player goes under? Also, the player
can wander forever, even off the map. How would you display a message if
the player tries to move elsewhere?)

Now, to call the helper and start the game.

(define (play-game)
  (game-loop '(10 10)
             (list (random 20) (random 20))
             50))

We always start the player out at (10, 10) and always give him $50 to start.
We want the treasure to go to a different place each time, so we create a
random location using random, and go! It's as simple as that.


THE SEQUENTIAL ALTERNATIVE

...is really too hairy for me to want to write out, but it shouldn't be too
hard to imagine. Instead of writing

  (game-loop new-location treasure-location new-money)

we'll be writing something like

  (set! player-location new-location)
  (set! money new-money)
  (game-loop)

...which, really, accomplishes the same thing, when you think about it.


B-B-B-BUT...

Okay, that's an easy example, because the 'state' was simple: in that example,
our state consisted of five numbers - two coordinate pairs and the money.
All possible states of the game can be represented by those five numbers.
But what about a more complicated game, like chess, where we have many
pieces in many places?

(WARNING: Attempting to write chess in Scheme is not advised. Caution is
recommended.)

Well, let's do the same thing that we did with Treasure Hunter.

;; white-king, white-queen, ... are two-element lists that represent
;; the locations of each piece
(define (chess-loop white-king white-queen white-bishop1 ...)
  ...)

Okay, that would get extremely complicated very fast. Let's make that simpler.

(define (chess-loop board)
  ...)

Okay, that's a bit better! Now we've got only one variable, board, which can
contain a list of lists of pieces. So, when we start playing chess, it'll
look like this:

(chess-loop '((WR WK WB WQ WK WB WK WR)
              (WP WP WP WP WP WP WP WP)
              (__ __ __ __ __ __ __ __)
              (__ __ __ __ __ __ __ __)
              (__ __ __ __ __ __ __ __)
              (__ __ __ __ __ __ __ __)
	      (BP BP BP BP BP BP BP BP)
	      (BR BK BB BQ BK BB BK BR)))

...where the first letter of each piece stands for the color (W for white or
B for black) and the second stands for the type of piece (K for king, R for
rook, and so forth.) This is a perfectly serviceable way to write such a
program, if you come up with a set of helper functions to aid in its
creation.

...but it still is a bit complicated. Maybe it might be better to represent
each piece's location in a list without listing every board location
explicitly? The number of __ pieces (that is, not-pieces) in the previous
system could easily get out of hand.

(chess-loop '((wr (0 0)) (wk (1 0)) (wb (2 0)) ...
	      (bk (6 7)) (br (7 7))))

Now, we only need to specify the locations of pieces and not of non-pieces,
and we can use helper functions to search through the list to find the
location of a given piece or whether anything exists in a given square.

Or perhaps we can split them into two lists - one for the white pieces,
and one for the black pieces?

(chess-loop '((rook (0 0)) (knight (1 0)) (bishop (2 0)) ..)
	    '((rook (0 7)) ...))

Same basic principle; we'd just have to modify our code slightly. If we wanted
to program Go or Othello or checkers, or any game which has only one type
of piece, then you could use a list of locations without quantifiers for
all of a player's pieces, e.g. '((0 0) (1 0) (2 0) (4 4)). For a more
complicated game - say, a generic fantasy text adventure in which the player
fights generic fantasy monsters - you might need more complicated data to
represent enemies:

(game-loop '((orc (17 4) (hp 15) (weapon club 4) (armor none 0))
	     (goblin (15 3) (hp 12) (weapon dagger 7) (armor leather 2))
	     ...))

(WARNING: This game is almost certainly more complicated to program in Scheme
than chess. Attempt at your own risk!)

In short, 'changes in state' can be simulated (and often simplified) by
representing them explicitly as arguments to recursive functions. While state-
changing functions such as set! can be (and are) very useful in certain
circumstances, always consider that there are ways of programming the same
program without them!


G.D. Ritter, 2009