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 Interpreter

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. 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 ${\frac {1}{16}}$ of the whole. First, let's figure out what ${\frac {1}{16}}$ 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

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

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, 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

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

What did this exercise with finding ever smaller numbers have to do with calculus? Well, the $d$ 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

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 $y=2x^{a}$, and evaluate it for $x=1,2,3$, and $a=2,4,6$.

8. Using the Sway function for $y$ in the previous problem, write a new Sway function $z=ay$, 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 $g(x)=x^{2}$ and $h(x)=(g(1+x)-g(1-x))/(3x)$. Calculate $h(1)$, $h(2)$, $h(3)$, and $h(0.5)$. Express $h(x)$ in terms of $x$. Draw a graph of h in the range $-2\leq x\leq 2$.

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 $({\mathit {NPCLevel}}*5-{\mathit {PlayerDefense}})*2\%-15\%$. For a level 70 NPC, express this as a function of $PlayerDefense(x)$ and give the value of defense that makes the chance 0.

12. The amount of experience to level a character is $h(x)=g(x)*(1344-((69-x)*((69-x)*4+3)))+155$ where x is the character level and where $g(x)=5x+45$ is the basic amount of experience earned for dispatching a mob of level equal to the character. Calculate $h(61)$, $h(69)$, $h(0.5)$, and $h(1)$. Express $h(x)$ in terms of x. Plot a graph of h for $61\leq x\leq 69$.