# The Science of Programming/How Low Can You Go?

Recall from the last chapter that the symbol *d*
with respect to Calculus means
'to take tiny pieces of'. Let's
practice taking small pieces of
a number and, at the same time,
learn some programming.
And, because you must, as future
Computer Scientists, you *must* learn to let go and be wild,
we will take a small piece of a small piece,
and a small piece of *that* very small piece, and so on and so on,
*ad infinitum*.

At this point, you should install Sway on your system.

## Using the Sway InterpreterEdit

We begin by starting the Sway interpreter, Sway being
the *Programming Language* you will learn. Once started,
the interpreter rewards you with a *prompt*:

sway>

This prompt signals to you to enter some code. When you
do so, the interpreter will tell you the result of
running (or *evaluating* or *executing*) that code.

sway> 3; INTEGER: 3

To exit the interpreter, type <Ctrl-d> or a <Ctrl-c>.
These key strokes are generated by holding the Control
key down while at the same type tapping the 'd' or 'c'
key at the same time.^{[1]}
Here, we have entered a 3 followed by a semicolon (the semicolon
tells the interpreter that we are done entering code).
Sway (actually the Sway interpreter)
responds by saying 3 is an integer with a value
of 3. Of course, we already knew all that, so the interpreter
doesn't seem to be all that useful. But did you know that
43 times 112 is 4816?

sway> 43 * 112; INTEGER: 4816

Sway does! Let's use the fact that the interpreter
is pretty good at math to figure out what a small part of a
big number is. Let's assume that a small part is
of the whole.^{[2]}
First, let's figure out what
is as a decimal number, or *real* number,
since that will be easier to type in:

sway> 1/16; SOURCE CODE ERROR file stdin,line 1 an expression was expected, found token of type BAD_NUMBER error occurred prior to: 16;[END OF LINE]

Uh oh. Sway did not like the '1' followed so closely by the '/'. In fact, Sway requires spaces around things like division signs in most instances. Let's try again:

sway> 1 / 16; INTEGER: 0

Better, at least we got an answer instead of an error. However, it doesn't seem that the interpreter is that good at math after all. If we put on our Sherlock Holmes cap and ponder, we see that the interpreter said the result of dividing 1 by 16 is an integer, but we know it should be a real number. It turns out that the Sway language, like most programming languages, uses a rule that combining two things of the same type yields a result of the same type. In this case, zero happens to be the largest integer that is less than the desired result. In other words, the interpreter truncated the fractional part of the real number and gave us the integer that was left. Let's experiment and see if this is so:

sway> 7 / 2; INTEGER: 3

Seems to be. So getting back to our original problem, how do we find out what is 1 divided by 16 as a real number? Let's enter the numbers as real numbers instead of integers:

sway> 1.0 / 16.0; REAL_NUMBER: 0.0625000000

That's much better!

Now let's figure out what a small part of a million is (using our assumption of what is small):

sway> 1000000 * 0.0625; REAL_NUMBER: 62500.0000000000

Sixty-two and a half thousand. Still big in an absolute sense, but much smaller that a million. Being wild and crazy, let's take a small part of a small part:

sway> 1000000 * .0625 * .0625; REAL_NUMBER: 3906.2500000000

About 4000. Much smaller.

You should familiarize yourself with Sway primitives and combinations, including Sway's precedence and associativity rules, at this point.

## Using VariablesEdit

Shall we continue taking ever smaller parts?

Before we do, I must admit that I am, at heart, a lazy person,
as are most Computer Scientists.^{[3]}
Typing in all those numbers is just too much work! I am
going to use two short symbols to represent both the million and the
fraction:

sway> var x = 1000000; INTEGER: 1000000 sway> var f = .0625; REAL_NUMBER: 0.0625000000

What I've done is created a *variable* to stand in for
the million and a variable to stand in for the fraction,
*x* and *f* respectively.^{[4]}
Now I can use those variables
instead of the numbers. Let's check to see if I did things
right:

sway> x * f * f; REAL_NUMBER: 3906.2500000000

Looks like I did. Let's go a step further:

sway> x * f * f * f; REAL_NUMBER: 244.1406250000

It seems variables are a nice way to reduce the amount of
typing needed. The only drawback is remembering what a
variable stands for. This is why it is so important
to name your variables in such a way as to make it
easy for you to recall their meanings. Generally,
single letter variable names are '*not* a good idea
(although there are exceptions to this rule).

To learn more, see Sway variables.

## Using functionsEdit

We could go further with this, but you have yet to understand the
depths of my laziness. Even typing in `* f` repeatedly
is too much for my sensibilities. I am going to define (or write) a
function to do the work for me (you can cut and paste this
function into the interpreter if you are lazy like me and
don't want to type it in yourself):

function smaller(amount,fraction) { inspect(amount * fraction); }

Whether you paste it in or type it in, you should get the following response from the interpreter:

sway> function smaller(amount,fraction) more> { more> inspect(amount * fraction); more> } FUNCTION: <function smaller(amount,fraction)>

The `more>` prompt indicates that the Sway interpreter
is expecting some more code.

There are two things you must do when dealing with functions,
(1) *define* them and (2) *call* them. Here, we have just defined a
function; now we need to call it. We will call it by typing
the name of the function followed by a parenthesized list
of *arguments*.
Sometimes we say this is "passing the
arguments to the function".

When calling the function *smaller*^{[5]},
the values of the arguments will be
*bound* to the variables *amount* and *fraction*, which are
found after the function name in its definition. These variables
are known as the *formal parameters* of the function.
This passing
and binding, in essence,
defines those variables for us.
Note that the arguments and formal parameters do need to
be separated by whitespace; the comma serves as a separator.

After these implicit variable definitions,
the code between the curly braces {} will be evaluated
as if you had typed them in directly to the interpreter. This
is why I said in the previous chapter that a function does
the work for you. If we look at the code (or body) of the
function we just defined, we see that a function named
*inspect* is being called. Since we haven't defined
*inspect*, we can assume that this function already
exists within the interpreter. By its name, we can guess
that it will tell us something about what happens when we
multiply *amount* by *fraction*:

sway> smaller(x,f); amount * fraction is 62500.000000 REAL_NUMBER: 62500.000000

There is a whole lot going on here that needs explanation. The
first is that the value of *x* (1000000) was bound to the
formal parameter *amount* of the function *smaller*.
Likewise, the value of *f* (0.0625) was bound to the formal
parameter *fraction*. Then the body of the function *smaller*
was evaluated, triggering a call to the *inspect* function.
What *inspect* does is print out its literal argument, followed
by the string " is ", followed by the value of its argument.
Since the call to inspect is that last thing *smaller* does,
whatever *inspect* returns is returned by *smaller*. This
return value appears to be the evaluated argument.

Note that interpreter reported two things. The first is
the string produced by *inspect*. The second is the
report of the return value as we have seen before.
We call an action that has an effect outside the called function
(in this case, the printing by *inspect*) a *side effect*.

To learn more, see Sway Functions.

## RecursionEdit

Now, at this point, you are probably thinking that, not only
am I lazy, I must be a rather dim bulb as well, because I spent
a lot more effort writing the *smaller* function and calling
it than I would have simply typing:

sway> x * f; REAL_NUMBER: 62500.000000

If that was all I was going to do, you would be quite right
in your assessment. But I am not finished yet. Now I am
going to make *smaller* much, much more powerful:

function smaller(amount,fraction) { inspect(amount * fraction); smaller(amount * fraction,fraction); }

Notice that I have added a call to the *smaller* function after
the call to the *inspect* function.
When a function calls itself, it is said to be a *recursive*
function, that it exhibits the property of *recursion* and
that at the point of the *recursive* call,
the function *recurs*.^{[6]}
Notice further that the first argument to *smaller* in that
internal call will send a (hopefully) smaller number to the
*smaller* function. In *that* call, *smaller* will be
called again with yet an even smaller number, and so on.
Let's try it:

sway> smaller(1000000,.0625); amount * fraction is 62500.0000000000 amount * fraction is 3906.2500000000 amount * fraction is 244.1406250000 amount * fraction is 15.2587890625 amount * fraction is 0.9536743164 amount * fraction is 0.0596046448 amount * fraction is 0.0037252903 amount * fraction is 0.0002328306 amount * fraction is 1.4551915228e-05 amount * fraction is 9.0949470177e-07 ... amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 amount * fraction is 0.0000000000e+00 encountered a fatal error... stack overflow.

Wow! Unless you have very quick eyes, all you
saw is the bottom part of this output.
What happened?
What we did was to define a function that fell into
an *infinite loop* when we called it. An infinite loop
occurs because we never told our function when to stop
calling itself. Thus, it tried to call itself *ad infinitum*.
Of course, a computer has a limited amount of memory, so
in this particular case, the calls could not go on
forever.^{[7]}
Let's redefine our function so that it pauses after every
inspection so we can slow down the output:

function smaller(amount,fraction) { inspect(amount * fraction); pause(); smaller(amount * fraction,fraction); }

You can start up the Sway interpreter again and paste in our revised function definition.

Now when we call our function we see this output (assuming you repeatedly hit the enter key on your keyboard):

sway> smaller(1000000,.0625); amount * fraction is 62500.0000000000 amount * fraction is 3906.2500000000 amount * fraction is 244.1406250000 amount * fraction is 15.2587890625 amount * fraction is 0.9536743164 amount * fraction is 0.0596046448 amount * fraction is 0.0037252903 amount * fraction is 0.0002328306

You can stop the interpreter by typing in a <Ctrl>-c which is entered from your keyboard by holding the Control key down while tapping the 'c' once.

We can see that `amount * fraction` gets very small very quickly.
If you start
again and keep going, you will see that `amount * fraction`
eventually reaches zero.
Theoretically, it doesn't, but at some point
the quantity gets smaller that can be represented by Sway,
so Sway reports zero.

You should read more about
recursion and
learn about *if* expressions before continuing.

Let's try a new version of the function, this one calls itself a given number of times before stopping:

function smaller(x,f,n) { if (n == 0) { :done; } else { inspect(x); smaller(x * f,f,n - 1); } }

This time, we have a new formal parameter *n*, which represents
the number of times to the function recursively calls
itself again. We've also changed the call to *inspect*
to print out the value of *x*.
Note that the recursive call not only makes *x* smaller, it
makes *n* smaller as well.
When *n* gets small enough, the function returns the symbol
*done*.

We must remember to add an extra argument to the call. Let's send in 8 as the number of times to recursively call:

sway> smaller(1000000,.0625,8); x is 1000000 x is 62500.000000 x is 3906.2500000 x is 244.14062500 x is 15.258789062 x is 0.9536743164 x is 0.0596046448 x is 0.0037252903 SYMBOL: :done

Yay! Our program stopped recuring infinitely. Formally, the *if*
inside the function has two cases: the *base* case, which does not
contain a recursive call and a *recursive* case, which does.
Infinite recursive loops occur when the base case is never reached,
usually due to some misstatement of the base case condition or
a misunderstanding of the range of values taken on by the formal
parameter being tested in the base case condition.

## Back to CalculusEdit

What did this exercise with finding ever smaller numbers have to
do with calculus? Well, the symbol means 'take
a tiny piece of'. How tiny? Infinitesimally small, or in other
words, the value computed by an infinite number of recursive calls
to *smaller*. Of course, this is smaller than we can fathom,
but that is not a big deal. We can't fathom how our brains work,
but we get along OK, or at least most of us do.

## QuestionsEdit

All formulas are written using Grammar School Precedence.

**1**.
What happens when you combine an integer and a real number?

**2**.
This question and subsequent questions refer to the last version of smaller.
Why did the call to *smaller* return a real number?

**3**.
Redefine *smaller* so that it prints out nine inspections rather than eight,
for the same initial value of 8.

**4**.
What happens when zero is passed as the count to *smaller*?

**5**.
What happens when -1 is passed as the count to *smaller*? Why?

**6**.
What happens if the recursive call in *smaller* is replaced by `smaller(x *f,f,n)`? Why?

**7**.
Write a Sway function to represent , and evaluate it for , and
.

**8**.
Using the Sway function for in the previous problem, write a new Sway function ,
and evaluate as before.

**9**.
A series is a sequence of terms that are added together. If as more
and more terms are added together, the sum of the terms get closer
and closer to a number *k*, then, *k* is said to be the limit of
that series. The book explains this with Zeno's paradox. Let's say you
start a distance 1 away from a wall and with each step, you travel half
the remaining distance to the wall (why is this a paradox?).
Using recursion and Sway, define a
function *zeno*(*n*) that demonstrates this process. The argument
to zeno is the number of steps taken and the return value should be the
total distance travelled. What is the limit of the *zeno* series?

**10**.
Let
and
.
Calculate
,
,
, and
.
Express
in terms of
.
Draw a graph of *h* in the range .

**11**.
The formula for the chance of an *NPC* (Non-Player Character)
landing a crushing blow in the World of Warcraft (a popular Massively
Multiplayer Online Role-Playing Game or *MMORPG*),
is
.
For a level 70 NPC, express this as a function of
and give the value of defense that makes the chance 0.

**12**.
The amount of experience to level a character is
where *x* is the character level and where is the basic amount of experience
earned for dispatching a mob of level equal to the character.
Calculate , , , and
.
Express in terms of *x*.
Plot a graph of *h* for .

## FootnotesEdit

- ↑ If you restart the Sway interpreter, you can recover your previous commands by using the up arrow on your keyboard. If you go too far up, you can use the down arrow to move through the list of previous commands in the opposite direction. You can edit the previous commands as well.
- ↑ Computer Scientists love numbers that are a power of 2, as in 1, 2, 4, 8, 16, 32, and so on. The inverses of those numbers are much loved, as well.
- ↑ Lazy, as in I abhor doing work that could (and should) be automated.
- ↑
A variable can be thought of as a name for something else. However,
it is
*not*the something else, just as your name is not you, but a handy way for people to refer to you. - ↑
the variable
*smaller*is not really a function, but a handy name for the function we defined. But rather than say 'the function named by the variable*smaller'*, we often say 'the function*smaller*. Technically, that is incorrect, but is simpler to say. - ↑
Some poor souls will use the verb 'recurse' instead of
the proper 'recur'. Recur means to call oneself, recurse
means to swear again. Do
*not*make this mistake, otherwise people will deem you ignorant. - ↑ There are clever languages in which some infinite recursive loops do not use up computer memory. Someday, Sway will be that clever and this section will need to be rewritten.