# 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.

## Contents

## Using the Sway Interpreter[edit]

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 Variables[edit]

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 functions[edit]

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.

## Recursion[edit]

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 recusive 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 Calculus[edit]

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.

## Questions[edit]

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 .

## Footnotes[edit]

- ↑ 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.