Compsci.ca Wiki - User contributions [en]

Turing Joysticks

2008-10-12T21:56:33Z

Saad:

Hello and welcome to the tutorial on using joysticks/joypads. I personally have a joypad with 2 analog sticks, 12 buttons, and a D-PAD/POV which has been tested. This tutorial will require two things:
*You have at least one joystick/joypad
*Secondly, you need the revised module at the bottom as the Turing default will not work

==FAQ==
*So what do you plan to accomplish in this tutorial?
**I'm planning to tackle the four main parts of the joystick module, breaking it down into parts, and ultimatly sharing this method of input with the world!

*So what's so great about joysticks/joypads?
**Well the mouse has upto 3 buttons and a cursor, a keyboard has keys, however a joypad (depending on the model) will have upto 32 buttons, upto 3 analog sticks, and a D-PAD/POV! that equals a ton more input and functionallity

*What if I don't have a joypad/joystick?
**Not to worry just follow along

Well now to get started!

==Setup==
First things first, since the module is not pervasive it needs to be imported, also make sure the module is in the same folder as the program using it.

<pre>
import joystick
</pre>

Now that that is done varibles need to be initalized just as though mouse input or keyboard input were being used.
<pre>type joypad : % create a joypad type
record
button : array 1 .. 32 of boolean %create 32 instances of buttons
pos : joystick.PosRecord /*used to find all joypad intake with
the exception of buttons*/
caps : joystick.CapsRecord %used to find the max on joypad analog
end record

var joy : array 1 .. 2 of joypad %create an array of joypad</pre>

What just happened? Well now to break that down.

First an instance of the joypad type containing a set of varibles was created. The first varible is an array of 32 boolean the number can be any number 1<n<32, basically it's all the buttons being used (32buttons were used to show the maximum potential). The next varible is actually taking the type of another record.
The record can be found in the joystick module it is basically bringing all input except the button states. Next is another type found in the joystick module this time bringing back the maximum potential of the joystick/joypad. Then a joy varible to use the varibles was created an array can be used for multiple joysticks/joypads.

Well now that is done time to move on. Default values need to be assigned as a failsafe for any joysticks not detected.

<pre>/*set default joypad varibles*/
for i : 1 .. upper (joy)
for ii : 1 .. upper (joy (i).button)
joy (i).button (ii) := false
end for
joy (i).pos.POV := 66535
joystick.Capabilities (i - 1, joy (i).caps)
end for</pre>

What just happened is rather simple. First a for loop was created to to cover all elements of joy, then another for loop for all 32 buttons to set the array to false false. Then the D-PAD/POV' was set to the default value of 66535. Lastly the joystick capibilities was called to find maximum capiblities of the joystick/joypad. Next joystick needs to be galled upon each loop run in the main program to gather information to what buttons are being pressed, etc... just as if it were a mouse or keyboard.

<pre>joystick.GetInfo (joystick[1/2], joy ([1/2]).button)
joystick.Read (joystick[1/2], joy ([1/2]).pos)</pre>

The GetInfo procedure will return upto 32 button values. The Read procedure will return with Analog and D-PAD/POV information.

==Using Buttons==
This part of the tutorial is similar to a keyboard. A keyboard has an array of keys that return true if the key is pressed (info found with Input.KeyDown). A joystick/joypad has an array of buttons that return true if the button is pressed (info found with joystick.GetInfo). Therefore:

<pre>if joy.button(4) then
put "Button 4 is being pressed"
end if</pre>

Hopefully that is understandable. And that is all for buttons.

==Using Analog Sticks==

This part is not to hard however the analog does not return an X/Y pixel value, so a conversion is needed. First to get the current analog position.

<pre>put "analog 1 - x - ", joy (1).pos.xpos
put "analog 1 - y - ", joy (1).pos.ypos</pre>

Well these values need to be converted like so.

<pre>put "analog 1 - x - ", round (joy (joystickNO + 1).pos.xpos / joy (joystickNO + 1).caps.maxX * maxx)
put "analog 1 - y - ", round (joy (joystickNO + 1).pos.ypos / joy (joystickNO + 1).caps.maxY * maxy)</pre>

This must be done everytime but it shouldn't be to hard to create a function to do this.

The axis use a name for each x and y direction: analog 1 x - xpos, analog 1 y - ypos, analog 2 x - zpos, analog 2 y - rpos, analog 3 x - upos, analog 3 y - vpos.

==Using D-PAD/POV==
First off, reading D-PAD/POV data.

<pre>put joy ([1/2]).pos.POV</pre>

This to needs to be converted into usable code.

<pre> put "D-PAD (AKA POV) - " ..
if joy ( [ 1 / 2]).pos.POV = 0 then
put "up"
elsif joy ( [ 1 / 2]).pos.POV = 4500 then
put "up right"
elsif joy ( [ 1 / 2 ]).pos.POV = 9000 then
put "right"
elsif joy ( [ 1 / 2 ]).pos.POV = 13500 then
put "down right"
elsif joy ( [ 1 / 2 ]).pos.POV = 18000 then
put "down"
elsif joy ( [ 1 / 2 ]).pos.POV = 22500 then
put "down left"
elsif joy ( [ 1 / 2 ]).pos.POV = 27000 then
put "left"
elsif joy ( [ 1 / 2 ]).pos.POV = 31500 then
put "up left"
else
put "none"
end if</pre>

==Conclusion==
Well that is all there is to it.

==Challenges==
Here are some challenges to try out.

# Make a circle that moves with the analog stick
# Move a sprite around the screen with the D-PAD/POV
# Make a simple Simon game with the buttons
# Try to make a basic game where you talk to people, walking around with D-PAD/POV talking to the character with the buttons

==Refrences==
*Joystick info http://compsci.ca/v3/viewtopic.php?t=6373
*Joystick info http://compsci.ca/v3/viewtopic.php?t=169

==Downloads==
[http://compsci.ca/v3/download.php?id=5324>Joystick Module]

[http://compsci.ca/v3/download.php?id=5325>Demonstration]

Turing Functions and Procedures

2008-10-12T20:25:36Z

Saad: /* Functions and Procedures */

==Introduction==

Thus far, we've learned enough of the Turing language to be able to write some decently large programs. We've learned some fundamentals of Turing -- variables, basic input/output, and if statements. Indeed, these concepts translate relatively smoothly to most any other programming language you might learn. So, having mastered these basics, what's next? Well, having a way to organize our code would be good. Right now, whatever code you write runs linearly, from top to bottom. If you want to run a section of code twice, you have to type it out twice. Wouldn't it be great if we could factor out the commonalities in our code, so we can write less? In truth, we haven't learned very much, so it might be difficult to see the advantage of this. Just bear with me.

==Introducing the Procedure==

At its simplest, a procedure is just some lines of Turing code. We wrap some special syntax around our lines of Turing code and think up a name for them. After we have defined our procedure, we can ''call'' the procedure by saying its name. When we do this, we run those lines of Turing code that are wrapped inside the procedure definition. This is easiest to see with an example:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
greet
</pre>
So now the single line of code, ''put "Hello world!"'', can be executed any time we call the ''greet'' procedure. The above code is identical to the following code:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
put "Hello world!"
</pre>
All I've done is substituted the code inside the ''greet'' procedure for the call to ''greet'' in the last line of the original program.

So, why is this useful? It's useful because now whenever we want to output "Hello world!", we don't have to type, ''put "Hello world!"'', but only ''greet''. Okay, so we saved on typing fourteen charactes. Not a big deal, right? But what if we wrote a program that said "Hello world!" a lot. Our program said hello to the world ten times during the course of its execution. Now, we're looking back at our program and thinking, "You know, 'Hello world!' isn't really what we want to say. We really are only talking to one person--George. We should instead say 'Hello George!'." So, now we've got to go into our code and change it. If we used a ''greet'' procedure, this change involves changing the definition of the procedure so that it becomes the following:
<pre>
procedure greet
put "Hello George!"
end greet
</pre>
If we hadn't used this procedure, we would have to go through our code, searching for any time we said "Hello world!" and change it to be "Hello George!". That's a lot of unnecessary work, relative to how effective our ''greet'' solution is.

But now, what if we aren't always talking to George?

==Procedures with Parameters==

Instead of writing a procedure to greet to George and another procedure to greet to Phil and another to greet to Anthony, we should try to write a procedure that can greet to anyone. Here's one possibility:
<pre>
var name : string
procedure greet
put "Hello ", name, "!"
end greet

name := "George"
greet

name := "Phil"
greet

name := "Anthony"
greet
</pre>
This works, but it's clunky. We've got that variable up there, ''name''. It's what we call a '''global variable'''. It's called that because it is global to the whole program. No matter where we are in our code, we can always see the ''name'' variable. Really, we don't need to keep track of ''name''. We only need it ''inside the greet procedure''. Here's where '''parameters''' are used.
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
greet ("Phil")
greet ("Anthony")
</pre>
In the definition of our greet procedure, I added that extra bit at the end--the stuff in parentheses. That says that when we call the greet procedure, we must give it one '''argument''', and that argument must be a string. It also says that for all code inside the procedure, there exists a '''constant''' called "name" that has the value we give it when we call the procedure. So, when we call ''greet ("George")'', we are setting ''name'' to be "George", and we execute the code inside the procedure. The following two pieces of code are identical:
<pre>
greet ("George")
</pre>
<pre>
put "Hello ", "George", "!"
</pre>
I mentioned earlier that inside the ''greet'' procedure there exists this constant called name. There are two things we need to understand about it. First, it is constant. We can't change the value of name. Let's get some example code and figure out why:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

greet ("George")
</pre>
This code fails because, inside ''greet'', ''name'' is really just a ''reference to "George"''. When we try to redefine name, we're really trying to redefine the string literal "George". Of course, that's impossible. What if we did this, though?
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
</pre>
Now you might think that, inside ''greet'', ''name'' is a reference to ''person'', which is a variable, so attempting to redefine ''name'' is really redefining ''person'', and that's okay. However, it's not quite that simple. See, ''greet'' expects a string as its argument, not a variable. In ''greet (person)'', ''person'' is an expression. It gets evaluated down to a string value; it gets evaluated to "George". Now, once again, we're passing the string literal "George" into ''greet'', and we're back at our first situation.

The second thing we need to understand about ''name'' is that it's '''local'''. It exists only within the procedure. The following code fails:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
put name
</pre>
''name'' doesn't exist outside of the ''greet'' procedure. It's '''local'''. It's '''scope''' is the ''greet'' procedure. You should also note that each time we call ''greet'' we are creating a new ''name'' constant.

What if we wanted to write a procedure that introduces two people to each other? We need a procedure that can two arguments, not one.

==Procedures with Multiple Parameters==

I will now define a procedure, called ''introduce'', that introduces two people to each other:
<pre>
procedure introduce (person1 : string, person2 : string)
put person1, ", this is ", person2, "."
put person2, ", meet ", person1, "."
end introduce

% Call the procedure
introduce ("Jackie", "Bruce")
</pre>
The output of this program will be:
<pre>
Jackie, this is Bruce.
Bruce, meet Jackie.
</pre>
However, reversing the order of the names results in a different output:
<pre>
introduce ("Bruce", "Jackie")
</pre>
<pre>
Bruce, this is Jackie.
Jackie, meet Bruce.
</pre>
You should be able to see how this works. When I call ''introduce'', person1 references the first name I give, and person2 references the second name I give. It's based on the ''order'' of the parameters/arguments. (Note some terminology here: person1 and person2 are the parameters; "Bruce" and "Jackie" are the arguments.)

Here's a little, unimportant shortcut. We can declare more than one variable on the same line, provided they are of the same type:
<pre>var name1, name2 : string</pre>
We can do the same with parameters:
<pre>
procedure introduce (person1, person2 : string)
%...
end introduce
</pre>

Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.
<pre>
procedure put_product (num1, num2 : real)
put num1 * num2
end put_product

put_product (4, 6) % Outputs 24
</pre>
However, what we're doing is rather silly, isn't it? I mean, aside from the fact that we're defining a procedure to do multiplication, which we can do very quickly anyways. What's silly about this is that we've cornered ourselves. This procedure forces us to send the product to the standard output. What if we wanted to store it in a variable, or draw it in a pretty font, or pass it to some other procedure? Take a minute and think about how we might solve this problem. We want to be able to generalize, here. We want to write something that can multiply two numbers we give it, but still give us the flexibility to do what we want with the answer.

If you're thinking about passing in another parameter that says what we are to do with the prodcut we calculate, then you're thinking way ahead of the game. It's possible, but not easy. There's an easier way.

==Introducing Functions==

Instead of writing a procedure that outputs the product of two numbers, we'll write a function that computes the prodcut of two numbers and ''returns that value''. Then we can decide what to do with that number. That's what a function is: it's the same as a procedure, except it returns a value.

<pre>
function product (num1, num2 : real) : real
result num1 * num2
end product

put product (4, 6) % outputs 24
</pre>
There's some new syntax there. First, we're using the keyword, "function", instead of "procedure". Next, there's a ": real" after our parameter list. That signifies what type of value our function will return. Also, we've used the '''result''' keyword. Earlier I said that functions return a value. The value returned is given by what is immediately after the '''result''' keyword.

Using a function gives us more flexibility. We don't have to send our answer to the standard output. We could store it in a variable, for instance.
<pre>
var n : real := product (1.5, 3) % n := 4.5
</pre>
Then we could use that elsewhere:
<pre>put product (n, 2) % outputs 9</pre>
Or perhaps better yet:
<pre>put product (product 1.5, 3) 2) % outputs 9</pre>

Let's now look a little closer at '''result'''. It has an interesting behaviour that we have yet to examine.

==A Closer Look at 'result'==

A function's sole purpose is to compute and return a value. With that in mind, let's write a ficticious function:
<pre>
function ficticious (number : int) : int
result number + 1
put "Yarr, it be a cold day."
end ficticious

% Call our function and store its answer in a variable
var n : int := ficticious (4)
</pre>
What has happened here? Surely, ''ficticious (4)'' returns the value 5. So ''n'' should be 5. What about that crazy pirate message? Well, as soon as the function computed its value, it returned that value and completed execution. The "Yarr..." message was never output; that line of code was never reached.

This behaviour is a bit irratic. It can make it difficult to understand how a function is working. At the same time, it can be quite useful in shortening code. You've got a find a balance between short code and understandable code.

Soon we will compare and contrast procedures and functions. Before we can do that, however, we need to re-examine what I said earlier about our parameter being constant.

==Variable Parameters==

Let's go back to our first example with parameters:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
</pre>
I had argued that ''name'' is constant. We cannot change its value. Indeed, we cannot. However, we can change this code so that ''name'' is in fact variable. All we have to do is specify that the ''name'' parameter is not simply a string, but is a variable that is a string. We do this by using the '''var''' keyword.
<pre>
procedure greet (var name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
put "After calling greet, the value of person is now ", person
</pre>
<pre>
Hello George!
And hello to Freddy as well!
After calling greet, the value of person is now Freddy
</pre>
The difference here is that ''greet'' is expecting to take a string variable, instead of just a string. So when we pass ''person'' to it, ''name'' actually becomes a reference to the variable ''person''. Then, changing the value of ''name'' changes the value of ''person''.

Now, we're familiar with procedures and functions. We now know enough to start thinking about when we should use a procedure and when we should use a function.

==Functions vs. Procedures==

Both functions and procedures are what some call "''subroutines''"--they are something we can use to store code and call at a later point. A function computes and returns a value, whereas a procedure just runs some code. We need to get an understanding of when to use a function and when to use a procedure. Let's look at a pretty famous case study.

In Turing, there are two ways of generating a random integer. The first way is to use the built-in function, ''Rand.Int''. (This is a function just like what we've been writing so far. Don't let the fact that it has a period in it's name fool you.) ''Rand.Int'' takes two numbers, a low and a high; it produces a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
n := Rand.Int (4, 11)
</pre>
Now n is a random integer between 4 and 11.

The second way to produce random integers is to use the procedure, ''randint''. This procedure first takes a variable (like our ''greet'' procedure did in the last section) and also takes two numbers, a low and a high. ''randint'' takes the variable you give it and sets it to a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
randint (n, 4, 11)
</pre>

Now, which is better: ''Rand.Int'' or ''randint''? The correct answer is ''Rand.Int''. Here's why:

First, ''Rand.Int'' is more flexible. Say you wrote a function called "squeeze" that took in an integer. You want to give it a random integer between 1 and 6. Let's look at the two options:
<pre>squeeze (Rand.Int (1, 6))</pre>
<pre>
var n : int
randint (n, 1, 6)
squeeze (n)
</pre>
Clearly the ''Rand.Int'' version is cleaner. There's no polluting the global namespace with useless variables like "''n''".

The second reason is a bit more theoretical, but is of equal importance. ''randint'' takes in a variable and does something to it. We don't really know what. We have trust the documentation. Now, we've also got to trust the documentation of ''Rand.Int''. However, there's an important difference. With ''Rand.Int'', we assign to our variable the value returned by the function. With ''randint'', we have given our precious variable to the procedure, along with all the permissions necessary for the procedure to slaughter our poor variable. It has complete control. It can write whatever it wants in there. We've suddenly given away control of the ''state'' of our program. (State is a term that collectively means the values of all our variables and also our current location in the execution of the code.) The fewer people we give this control to, the better.

If you're not yet convinced, take a look at this. I'll code a version of ''randint'' for you.
<pre>
procedure my_randint (var num : int, low, high : int)
if num mod 2 = 0
num := low + (num * 2) mod (high - low + 1)
else
num := low + (num + 2) mod (high - low + 1)
end if
end my_randint
</pre>
So ''my_randint'' isn't really random, but it might fool you. Take a look at some sample data:
<pre>
% I've taken a shortcut here. When I say
% my_randint (0, 5, 10)
% I really mean
% var n : int := 0
% my_randint (n, 5, 10)

my_randint (0, 5, 10) %-> 5
my_randint (1, 5, 10) %-> 8
my_randint (2, 5, 10) %-> 9
my_randint (3, 5, 10) %-> 10
my_randint (4, 5, 10) %-> 7
my_randint (5, 5, 10) %-> 6
my_randint (6, 5, 10) %-> 5
my_randint (7, 5, 10) %-> 8
my_randint (8, 5, 10) %-> 9
my_randint (9, 5, 10) %-> 10
my_randint (10, 5, 10) %-> 7
</pre>

I could not have done a similar thing if I were using a function, because I was never given a value for ''num''. (I know what some of you are thinking: "What if I give an uninitialized variable to my_randint? It'll crash." It's possible that I could hack something together that could take care of this, but that's not the point.) The point of this is to show you that by giving the procedure control of your variable, it can use it that variable for evil purposes, as I have done with this ''my_randint'' procedure.

I sincerely hope this has convinced you that functions are superior to procedures. I'm not saying that functions should be used exclusively. There are times when procedures are needed. Rather, I'm just saying that when you have a choice of using a function or using a procedure, choose the function. Nice functions are ones that compute a value based soley on the parameters they take. They don't rely on any global variables. These are functions that are easily documented. At the other extreme are procedures that use global variables inside their definition and also take in variables and modify them. These procedures are ''dangerous!'' and very hard to document.

There is one last thing for us to discuss. It's a very powerful concept known as "recursion".

==Recursion==

I'd like to start this section off with a quotation:
<pre>To understand recursion, you must first understand recursion.</pre>
A recursive subroutine is a subroutine that calls itself. One of the most famous and basic examples is the factorial function. The factorial function takes in a number and returns the product of that number and the factorial of the number minus one. Also, the factorial of one is defined to be one. This is the recursive definition of the function. It translates very easily into code:
<pre>
function factorial (n : int) : int
if n = 1 then
result 1
else
result n * factorial (n - 1)
end if
end factorial

put factorial (3) % Outputs "6". Note 6 = 3*2*1
put factorial (5) % Outputs "120". Note 120 = 5*4*3*2*1
</pre>
I will give a condensed trace of the factorial function:
<pre>
factorial (5)
(5 * factorial (4))
(5 * (4 * factorial (3)))
(5 * (4 * (3 * factorial (2))))
(5 * (4 * (3 * (2 * factorial (1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6))
(5 * 24)
120
</pre>
I've given the recursive definition of the factorial function. A non-recursive definition is to say that factorial (n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1. if you know about loops, you can code this definition of the factorial function. You can then compare and contrast the two definitions and see which you prefer. I hope you'll prefer this version, but that's for time to decide.

As a segue into the next tutorial (which will be a tutorial on looping constructs), I will now present a recursive procedure that counts down to 1, and then displays, "Blast off!!"
<pre>
procedure countdown (high : int)
if high = 0 then
put "Blast off!!"
else
put high, "..."
countdown (high - 1)
end if
end countdown
</pre>
Calling ''countdown (5)'' produces:
<pre>
5...
4...
3...
2...
1...
Blast off!!
</pre>

'''Question One!''' Create a guessing game. Your program will have a global variable that represents the number the user is trying to guess. Use recursion to write a procedure called ''guess''. When run, ''guess'' prompts the user to input a number. If the guessed number is equal to ''the'' number, a winning message is displayed. Otherwise, the user is told whether his/her guess was too high or too low, and is prompted to guess another number.
A solution to this problem can be found at the end of the tutorial.

'''Question Two!''' Define a function called ''add'' that takes two natural numbers and returns their sum. There's a catch, though. You're not allowed to use the + operator. However, you are allowed to use these two functions that I supply you with:
<pre>
function add1 (n : int) : int
result n + 1
end add1
function sub1 (n : int) : int
result n - 1
end sub1
</pre>
A solution to this problem can be found at the end of the tutorial.

'''Question Three''' Define a function called ''multiply'' that takes two natural numbers and returns their product. Once again, there's a catch. You're not allowed to use the built in * operator. (You are allowed to use the + operator though.) You can, however, use the following two functions that I provide you with:
<pre>
function double (n : int) : int
result n + n
end double

% The halve function performs integer division by 2.
% Examples: halve (8) -> 4
% halve (17) -> 8
function halve (n : int) : int
result floor (n / 2)
end halve
</pre>
Hint: You should use the binary definition of a natural number. That is, a natural number is one of

*1
*2*k where k is a natural number
*2*k + 1 where k is a natural number

That is why I gave you the double and halve functions. It's possible to write a solution using the unary definition of a natural number (sort of like in the solution to problem two), but it will be much slower than the solution using the binary definition.
A solution to this problem can be found at the end of the tutorial.

==Conclusion==

I hope you find these exercises in recursion interesting. At this point, we've learned a small amount of the Turing language, but you see we can do some pretty powerful things using this concept of recursion.

Even if we don't take advantage of recursion, however, the topics covered in this tutorial still give us considerable power. They allow us to organize our code. We can save ourselves from repeating ourselves. We can generalize by using parameters. Indeed, the rather simple idea of factoring out common code has led to powerful advances.

==Solutions==

===Problem One===
<pre>
var the_num := Rand.Int (1, 100)

proc guess
put "Please input a guess: " ..
var g : int
get g
if g = the_num then
put "You've got it!"
elsif g < the_num then
put "You've guessed too low. Try again."
guess
else
put "You've guessed too high. Try again."
guess
end if
end guess

guess
</pre>

===Problem Two===
<pre>
% This function works by increasing n2 by one as we
% decrease n1 by one. If n2 = 0, then we just return n1.
% Essentially, it works on the following identity:
% n1 + n2 = (n1 + 1) + (n2 - 1)
function add (n1, n2 : nat) : nat
if n2 = 0 then
result n1
else
result add (add1 (n1), sub1 (n2))
end if
end add

% Note that this function could be made more efficient if, instead
% of blindly choosing to decrease n2 and increase n1, we chose to
% decrease the smaller of n1 and n2 and increase the larger of n1 and n2.
% Try writing another function that calls this add function in that way.
</pre>

===Problem Three===
<pre>
% This function works by decreasing n2 and increasing n1.
% It works on the following identity:
% If n2 is even: n1 * n2 = double (n1) * halve (n2)
% If n2 is odd: n1 * n2 = n1 + double (n1) * halve (n2)
function multiply (n1, n2 : nat) : nat
if n2 = 1 then
result n1
elsif n2 mod 2 = 0 then % n2 is even
result multiply (double (n1), halve (n2))
else % n2 is odd
result n1 + multiply (double (n1), halve (n2))
end if
end multiply
</pre>

==Credits==
Authour: [[Cervantes]]

Added by: [[Saad]]

Turing Joysticks

2008-10-12T20:24:21Z

Saad: /* Body */

Hello welcome to my tutorial on using joysticks/joypads. I personally have a joypad with 2 analog sticks, 12 buttons, and a D-PAD/POV which has been tested. This tutorial will require two things: Firstly, you have atleast one joystick/joypad. Secondly, you grab my revised module at the bottom as the Turing default will not work. Now for some Q and A.

==FAQS==

q)So what do you plan to accomplish in this tutorial?

a)Well I'm planning to tackle the four main parts of the joystick module, breaking it down into parts, and ultimatly sharing this method of input with the world!

q)So what's so great about joysticks/joypads?

a)Well the mouse has upto 3 buttons and a cursor, a keyboard has keys, however a joypad (depending on the model) will have upto 32 buttons, upto 3 analog sticks, and a D-PAD/POV! that equals a ton more input and functionallity.

q)What if I don't have a joypad/joystick?

a)Not to worry just follow along and post/PM me with the questions (I'm sometimes busy so results not will be immediate).

Well now to get started!

==Setup==

First things first, since the module is not pervasive it needs to be imported, also make sure the module is in the same folder as the program using it.

Code:
import joystick

Now that that is done varibles need to be initalized just as though mouse input or keyboard input were being used.
Code:
<pre>type joypad : % create a joypad type
record
button : array 1 .. 32 of boolean %create 32 instances of buttons
pos : joystick.PosRecord /*used to find all joypad intake with
the exception of buttons*/
caps : joystick.CapsRecord %used to find the max on joypad analog
end record

var joy : array 1 .. 2 of joypad %create an array of joypad</pre>

What just happened? Well now to break that down.

First an instance of the joypad type containing a set of varibles was created. The first varible is an array of 32 boolean the number can be any number 1<n<32, basically it's all the buttons being used (32buttons were used to show the maximum potential). The next varible is actually taking the type of another record.
The record can be found in the joystick module it is basically bringing all input except the button states. Next is another type found in the joystick module this time bringing back the maximum potential of the joystick/joypad. Then a joy varible to use the varibles was created an array can be used for multiple joysticks/joypads.

Well now that is done time to move on. Default values need to be assigned as a failsafe for any joysticks not detected.

Code:
<pre>/*set default joypad varibles*/
for i : 1 .. upper (joy)
for ii : 1 .. upper (joy (i).button)
joy (i).button (ii) := false
end for
joy (i).pos.POV := 66535
joystick.Capabilities (i - 1, joy (i).caps)
end for</pre>

What just happened is rather simple. First a for loop was created to to cover all elements of joy, then another for loop for all 32 buttons to set the array to false false. Then the D-PAD/POV' was set to the default value of 66535. Lastly the joystick capibilities was called to find maximum capiblities of the joystick/joypad. Next joystick needs to be galled upon each loop run in the main program to gather information to what buttons are being pressed, etc... just as if it were a mouse or keyboard.

Code:
<pre>joystick.GetInfo (joystick[1/2], joy ([1/2]).button)
joystick.Read (joystick[1/2], joy ([1/2]).pos)</pre>

The GetInfo procedure will return upto 32 button values. The Read procedure will return with Analog and D-PAD/POV information.

==Using Buttons==

This part of the tutorial is similar to a keyboard. A keyboard has an array of keys that return true if the key is pressed (info found with Input.KeyDown). A joystick/joypad has an array of buttons that return true if the button is pressed (info found with joystick.GetInfo). Therefore:

Code:
<pre>if joy.button(4) then
put "Button 4 is being pressed"
end if</pre>

Hopefully that is understandable. And that is all for buttons.

==Using Analog Sticks==

This part is not to hard however the analog does not return an X/Y pixel value, so a conversion is needed. First to get the current analog position.

Code:
<pre>put "analog 1 - x - ", joy (1).pos.xpos
put "analog 1 - y - ", joy (1).pos.ypos</pre>

Well these values need to be converted like so.

Code:

<pre>put "analog 1 - x - ", round (joy (joystickNO + 1).pos.xpos / joy (joystickNO + 1).caps.maxX * maxx)
put "analog 1 - y - ", round (joy (joystickNO + 1).pos.ypos / joy (joystickNO + 1).caps.maxY * maxy)</pre>

This must be done everytime but it shouldn't be to hard to create a function to do this.

The axis use a name for each x and y direction: analog 1 x - xpos, analog 1 y - ypos, analog 2 x - zpos, analog 2 y - rpos, analog 3 x - upos, analog 3 y - vpos.

==Using D-PAD/POV==

First off, reading D-PAD/POV data.

Code:
<pre>put joy ([1/2]).pos.POV</pre>

This to needs to be converted into usable code.

Code:
<pre> put "D-PAD (AKA POV) - " ..
if joy ( [ 1 / 2]).pos.POV = 0 then
put "up"
elsif joy ( [ 1 / 2]).pos.POV = 4500 then
put "up right"
elsif joy ( [ 1 / 2 ]).pos.POV = 9000 then
put "right"
elsif joy ( [ 1 / 2 ]).pos.POV = 13500 then
put "down right"
elsif joy ( [ 1 / 2 ]).pos.POV = 18000 then
put "down"
elsif joy ( [ 1 / 2 ]).pos.POV = 22500 then
put "down left"
elsif joy ( [ 1 / 2 ]).pos.POV = 27000 then
put "left"
elsif joy ( [ 1 / 2 ]).pos.POV = 31500 then
put "up left"
else
put "none"
end if</pre>

==Conclusion==

Well that is all there is to it.

==Challenges==

Here are some challenges to try out.

1)make a circle that moves with the analog stick

2)move a sprite around the screen with the D-PAD/POV

3)make a simple Simon game with the buttons

4)try to make a basic game where you talk to people, walking around with D-PAD/POV talking to the character with the buttons

==Refrences==

1) joystick info http://compsci.ca/v3/viewtopic.php?t=6373

2) joystick info http://compsci.ca/v3/viewtopic.php?t=169

And I am terribly sorry but there was one another post that really helped me understand joysticks myself but I forget who posted it and I can no longer find the post.

==Downloads==

[http://compsci.ca/v3/download.php?id=5324>Joystick Module]

[http://compsci.ca/v3/download.php?id=5325>Demonstration]

Turing Functions and Procedures

2008-10-12T19:39:31Z

Saad: /* Functions and Procedures */

==Functions and Procedures==

==Introduction==

Thus far, we've learned enough of the Turing language to be able to write some decently large programs. We've learned some fundamentals of Turing -- variables, basic input/output, and if statements. Indeed, these concepts translate relatively smoothly to most any other programming language you might learn. So, having mastered these basics, what's next? Well, having a way to organize our code would be good. Right now, whatever code you write runs linearly, from top to bottom. If you want to run a section of code twice, you have to type it out twice. Wouldn't it be great if we could factor out the commonalities in our code, so we can write less? In truth, we haven't learned very much, so it might be difficult to see the advantage of this. Just bear with me.

==Introducing the Procedure==

At its simplest, a procedure is just some lines of Turing code. We wrap some special syntax around our lines of Turing code and think up a name for them. After we have defined our procedure, we can ''call'' the procedure by saying its name. When we do this, we run those lines of Turing code that are wrapped inside the procedure definition. This is easiest to see with an example:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
greet
</pre>
So now the single line of code, ''put "Hello world!"'', can be executed any time we call the ''greet'' procedure. The above code is identical to the following code:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
put "Hello world!"
</pre>
All I've done is substituted the code inside the ''greet'' procedure for the call to ''greet'' in the last line of the original program.

So, why is this useful? It's useful because now whenever we want to output "Hello world!", we don't have to type, ''put "Hello world!"'', but only ''greet''. Okay, so we saved on typing fourteen charactes. Not a big deal, right? But what if we wrote a program that said "Hello world!" a lot. Our program said hello to the world ten times during the course of its execution. Now, we're looking back at our program and thinking, "You know, 'Hello world!' isn't really what we want to say. We really are only talking to one person--George. We should instead say 'Hello George!'." So, now we've got to go into our code and change it. If we used a ''greet'' procedure, this change involves changing the definition of the procedure so that it becomes the following:
<pre>
procedure greet
put "Hello George!"
end greet
</pre>
If we hadn't used this procedure, we would have to go through our code, searching for any time we said "Hello world!" and change it to be "Hello George!". That's a lot of unnecessary work, relative to how effective our ''greet'' solution is.

But now, what if we aren't always talking to George?

==Procedures with Parameters==

Instead of writing a procedure to greet to George and another procedure to greet to Phil and another to greet to Anthony, we should try to write a procedure that can greet to anyone. Here's one possibility:
<pre>
var name : string
procedure greet
put "Hello ", name, "!"
end greet

name := "George"
greet

name := "Phil"
greet

name := "Anthony"
greet
</pre>
This works, but it's clunky. We've got that variable up there, ''name''. It's what we call a '''global variable'''. It's called that because it is global to the whole program. No matter where we are in our code, we can always see the ''name'' variable. Really, we don't need to keep track of ''name''. We only need it ''inside the greet procedure''. Here's where '''parameters''' are used.
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
greet ("Phil")
greet ("Anthony")
</pre>
In the definition of our greet procedure, I added that extra bit at the end--the stuff in parentheses. That says that when we call the greet procedure, we must give it one '''argument''', and that argument must be a string. It also says that for all code inside the procedure, there exists a '''constant''' called "name" that has the value we give it when we call the procedure. So, when we call ''greet ("George")'', we are setting ''name'' to be "George", and we execute the code inside the procedure. The following two pieces of code are identical:
<pre>
greet ("George")
</pre>
<pre>
put "Hello ", "George", "!"
</pre>
I mentioned earlier that inside the ''greet'' procedure there exists this constant called name. There are two things we need to understand about it. First, it is constant. We can't change the value of name. Let's get some example code and figure out why:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

greet ("George")
</pre>
This code fails because, inside ''greet'', ''name'' is really just a ''reference to "George"''. When we try to redefine name, we're really trying to redefine the string literal "George". Of course, that's impossible. What if we did this, though?
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
</pre>
Now you might think that, inside ''greet'', ''name'' is a reference to ''person'', which is a variable, so attempting to redefine ''name'' is really redefining ''person'', and that's okay. However, it's not quite that simple. See, ''greet'' expects a string as its argument, not a variable. In ''greet (person)'', ''person'' is an expression. It gets evaluated down to a string value; it gets evaluated to "George". Now, once again, we're passing the string literal "George" into ''greet'', and we're back at our first situation.

The second thing we need to understand about ''name'' is that it's '''local'''. It exists only within the procedure. The following code fails:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
put name
</pre>
''name'' doesn't exist outside of the ''greet'' procedure. It's '''local'''. It's '''scope''' is the ''greet'' procedure. You should also note that each time we call ''greet'' we are creating a new ''name'' constant.

What if we wanted to write a procedure that introduces two people to each other? We need a procedure that can two arguments, not one.

==Procedures with Multiple Parameters==

I will now define a procedure, called ''introduce'', that introduces two people to each other:
<pre>
procedure introduce (person1 : string, person2 : string)
put person1, ", this is ", person2, "."
put person2, ", meet ", person1, "."
end introduce

% Call the procedure
introduce ("Jackie", "Bruce")
</pre>
The output of this program will be:
<pre>
Jackie, this is Bruce.
Bruce, meet Jackie.
</pre>
However, reversing the order of the names results in a different output:
<pre>
introduce ("Bruce", "Jackie")
</pre>
<pre>
Bruce, this is Jackie.
Jackie, meet Bruce.
</pre>
You should be able to see how this works. When I call ''introduce'', person1 references the first name I give, and person2 references the second name I give. It's based on the ''order'' of the parameters/arguments. (Note some terminology here: person1 and person2 are the parameters; "Bruce" and "Jackie" are the arguments.)

Here's a little, unimportant shortcut. We can declare more than one variable on the same line, provided they are of the same type:
<pre>var name1, name2 : string</pre>
We can do the same with parameters:
<pre>
procedure introduce (person1, person2 : string)
%...
end introduce
</pre>

Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.
<pre>
procedure put_product (num1, num2 : real)
put num1 * num2
end put_product

put_product (4, 6) % Outputs 24
</pre>
However, what we're doing is rather silly, isn't it? I mean, aside from the fact that we're defining a procedure to do multiplication, which we can do very quickly anyways. What's silly about this is that we've cornered ourselves. This procedure forces us to send the product to the standard output. What if we wanted to store it in a variable, or draw it in a pretty font, or pass it to some other procedure? Take a minute and think about how we might solve this problem. We want to be able to generalize, here. We want to write something that can multiply two numbers we give it, but still give us the flexibility to do what we want with the answer.

If you're thinking about passing in another parameter that says what we are to do with the prodcut we calculate, then you're thinking way ahead of the game. It's possible, but not easy. There's an easier way.

==Introducing Functions==

Instead of writing a procedure that outputs the product of two numbers, we'll write a function that computes the prodcut of two numbers and ''returns that value''. Then we can decide what to do with that number. That's what a function is: it's the same as a procedure, except it returns a value.

<pre>
function product (num1, num2 : real) : real
result num1 * num2
end product

put product (4, 6) % outputs 24
</pre>
There's some new syntax there. First, we're using the keyword, "function", instead of "procedure". Next, there's a ": real" after our parameter list. That signifies what type of value our function will return. Also, we've used the '''result''' keyword. Earlier I said that functions return a value. The value returned is given by what is immediately after the '''result''' keyword.

Using a function gives us more flexibility. We don't have to send our answer to the standard output. We could store it in a variable, for instance.
<pre>
var n : real := product (1.5, 3) % n := 4.5
</pre>
Then we could use that elsewhere:
<pre>put product (n, 2) % outputs 9</pre>
Or perhaps better yet:
<pre>put product (product 1.5, 3) 2) % outputs 9</pre>

Let's now look a little closer at '''result'''. It has an interesting behaviour that we have yet to examine.

==A Closer Look at 'result'==

A function's sole purpose is to compute and return a value. With that in mind, let's write a ficticious function:
<pre>
function ficticious (number : int) : int
result number + 1
put "Yarr, it be a cold day."
end ficticious

% Call our function and store its answer in a variable
var n : int := ficticious (4)
</pre>
What has happened here? Surely, ''ficticious (4)'' returns the value 5. So ''n'' should be 5. What about that crazy pirate message? Well, as soon as the function computed its value, it returned that value and completed execution. The "Yarr..." message was never output; that line of code was never reached.

This behaviour is a bit irratic. It can make it difficult to understand how a function is working. At the same time, it can be quite useful in shortening code. You've got a find a balance between short code and understandable code.

Soon we will compare and contrast procedures and functions. Before we can do that, however, we need to re-examine what I said earlier about our parameter being constant.

==Variable Parameters==

Let's go back to our first example with parameters:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
</pre>
I had argued that ''name'' is constant. We cannot change its value. Indeed, we cannot. However, we can change this code so that ''name'' is in fact variable. All we have to do is specify that the ''name'' parameter is not simply a string, but is a variable that is a string. We do this by using the '''var''' keyword.
<pre>
procedure greet (var name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
put "After calling greet, the value of person is now ", person
</pre>
<pre>
Hello George!
And hello to Freddy as well!
After calling greet, the value of person is now Freddy
</pre>
The difference here is that ''greet'' is expecting to take a string variable, instead of just a string. So when we pass ''person'' to it, ''name'' actually becomes a reference to the variable ''person''. Then, changing the value of ''name'' changes the value of ''person''.

Now, we're familiar with procedures and functions. We now know enough to start thinking about when we should use a procedure and when we should use a function.

==Functions vs. Procedures==

Both functions and procedures are what some call "''subroutines''"--they are something we can use to store code and call at a later point. A function computes and returns a value, whereas a procedure just runs some code. We need to get an understanding of when to use a function and when to use a procedure. Let's look at a pretty famous case study.

In Turing, there are two ways of generating a random integer. The first way is to use the built-in function, ''Rand.Int''. (This is a function just like what we've been writing so far. Don't let the fact that it has a period in it's name fool you.) ''Rand.Int'' takes two numbers, a low and a high; it produces a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
n := Rand.Int (4, 11)
</pre>
Now n is a random integer between 4 and 11.

The second way to produce random integers is to use the procedure, ''randint''. This procedure first takes a variable (like our ''greet'' procedure did in the last section) and also takes two numbers, a low and a high. ''randint'' takes the variable you give it and sets it to a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
randint (n, 4, 11)
</pre>

Now, which is better: ''Rand.Int'' or ''randint''? The correct answer is ''Rand.Int''. Here's why:

First, ''Rand.Int'' is more flexible. Say you wrote a function called "squeeze" that took in an integer. You want to give it a random integer between 1 and 6. Let's look at the two options:
<pre>squeeze (Rand.Int (1, 6))</pre>
<pre>
var n : int
randint (n, 1, 6)
squeeze (n)
</pre>
Clearly the ''Rand.Int'' version is cleaner. There's no polluting the global namespace with useless variables like "''n''".

The second reason is a bit more theoretical, but is of equal importance. ''randint'' takes in a variable and does something to it. We don't really know what. We have trust the documentation. Now, we've also got to trust the documentation of ''Rand.Int''. However, there's an important difference. With ''Rand.Int'', we assign to our variable the value returned by the function. With ''randint'', we have given our precious variable to the procedure, along with all the permissions necessary for the procedure to slaughter our poor variable. It has complete control. It can write whatever it wants in there. We've suddenly given away control of the ''state'' of our program. (State is a term that collectively means the values of all our variables and also our current location in the execution of the code.) The fewer people we give this control to, the better.

If you're not yet convinced, take a look at this. I'll code a version of ''randint'' for you.
<pre>
procedure my_randint (var num : int, low, high : int)
if num mod 2 = 0
num := low + (num * 2) mod (high - low + 1)
else
num := low + (num + 2) mod (high - low + 1)
end if
end my_randint
</pre>
So ''my_randint'' isn't really random, but it might fool you. Take a look at some sample data:
<pre>
% I've taken a shortcut here. When I say
% my_randint (0, 5, 10)
% I really mean
% var n : int := 0
% my_randint (n, 5, 10)

my_randint (0, 5, 10) %-> 5
my_randint (1, 5, 10) %-> 8
my_randint (2, 5, 10) %-> 9
my_randint (3, 5, 10) %-> 10
my_randint (4, 5, 10) %-> 7
my_randint (5, 5, 10) %-> 6
my_randint (6, 5, 10) %-> 5
my_randint (7, 5, 10) %-> 8
my_randint (8, 5, 10) %-> 9
my_randint (9, 5, 10) %-> 10
my_randint (10, 5, 10) %-> 7
</pre>

I could not have done a similar thing if I were using a function, because I was never given a value for ''num''. (I know what some of you are thinking: "What if I give an uninitialized variable to my_randint? It'll crash." It's possible that I could hack something together that could take care of this, but that's not the point.) The point of this is to show you that by giving the procedure control of your variable, it can use it that variable for evil purposes, as I have done with this ''my_randint'' procedure.

I sincerely hope this has convinced you that functions are superior to procedures. I'm not saying that functions should be used exclusively. There are times when procedures are needed. Rather, I'm just saying that when you have a choice of using a function or using a procedure, choose the function. Nice functions are ones that compute a value based soley on the parameters they take. They don't rely on any global variables. These are functions that are easily documented. At the other extreme are procedures that use global variables inside their definition and also take in variables and modify them. These procedures are ''dangerous!'' and very hard to document.

There is one last thing for us to discuss. It's a very powerful concept known as "recursion".

==Recursion==

I'd like to start this section off with a quotation:
<pre>To understand recursion, you must first understand recursion.</pre>
A recursive subroutine is a subroutine that calls itself. One of the most famous and basic examples is the factorial function. The factorial function takes in a number and returns the product of that number and the factorial of the number minus one. Also, the factorial of one is defined to be one. This is the recursive definition of the function. It translates very easily into code:
<pre>
function factorial (n : int) : int
if n = 1 then
result 1
else
result n * factorial (n - 1)
end if
end factorial

put factorial (3) % Outputs "6". Note 6 = 3*2*1
put factorial (5) % Outputs "120". Note 120 = 5*4*3*2*1
</pre>
I will give a condensed trace of the factorial function:
<pre>
factorial (5)
(5 * factorial (4))
(5 * (4 * factorial (3)))
(5 * (4 * (3 * factorial (2))))
(5 * (4 * (3 * (2 * factorial (1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6))
(5 * 24)
120
</pre>
I've given the recursive definition of the factorial function. A non-recursive definition is to say that factorial (n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1. if you know about loops, you can code this definition of the factorial function. You can then compare and contrast the two definitions and see which you prefer. I hope you'll prefer this version, but that's for time to decide.

As a segue into the next tutorial (which will be a tutorial on looping constructs), I will now present a recursive procedure that counts down to 1, and then displays, "Blast off!!"
<pre>
procedure countdown (high : int)
if high = 0 then
put "Blast off!!"
else
put high, "..."
countdown (high - 1)
end if
end countdown
</pre>
Calling ''countdown (5)'' produces:
<pre>
5...
4...
3...
2...
1...
Blast off!!
</pre>

'''Question One!''' Create a guessing game. Your program will have a global variable that represents the number the user is trying to guess. Use recursion to write a procedure called ''guess''. When run, ''guess'' prompts the user to input a number. If the guessed number is equal to ''the'' number, a winning message is displayed. Otherwise, the user is told whether his/her guess was too high or too low, and is prompted to guess another number.
A solution to this problem can be found at the end of the tutorial.

'''Question Two!''' Define a function called ''add'' that takes two natural numbers and returns their sum. There's a catch, though. You're not allowed to use the + operator. However, you are allowed to use these two functions that I supply you with:
<pre>
function add1 (n : int) : int
result n + 1
end add1
function sub1 (n : int) : int
result n - 1
end sub1
</pre>
A solution to this problem can be found at the end of the tutorial.

'''Question Three''' Define a function called ''multiply'' that takes two natural numbers and returns their product. Once again, there's a catch. You're not allowed to use the built in * operator. (You are allowed to use the + operator though.) You can, however, use the following two functions that I provide you with:
<pre>
function double (n : int) : int
result n + n
end double

% The halve function performs integer division by 2.
% Examples: halve (8) -> 4
% halve (17) -> 8
function halve (n : int) : int
result floor (n / 2)
end halve
</pre>
Hint: You should use the binary definition of a natural number. That is, a natural number is one of

*1
*2*k where k is a natural number
*2*k + 1 where k is a natural number

That is why I gave you the double and halve functions. It's possible to write a solution using the unary definition of a natural number (sort of like in the solution to problem two), but it will be much slower than the solution using the binary definition.
A solution to this problem can be found at the end of the tutorial.

==Conclusion==

I hope you find these exercises in recursion interesting. At this point, we've learned a small amount of the Turing language, but you see we can do some pretty powerful things using this concept of recursion.

Even if we don't take advantage of recursion, however, the topics covered in this tutorial still give us considerable power. They allow us to organize our code. We can save ourselves from repeating ourselves. We can generalize by using parameters. Indeed, the rather simple idea of factoring out common code has led to powerful advances.

==Solutions==

===Problem One===
<pre>
var the_num := Rand.Int (1, 100)

proc guess
put "Please input a guess: " ..
var g : int
get g
if g = the_num then
put "You've got it!"
elsif g < the_num then
put "You've guessed too low. Try again."
guess
else
put "You've guessed too high. Try again."
guess
end if
end guess

guess
</pre>

===Problem Two===
<pre>
% This function works by increasing n2 by one as we
% decrease n1 by one. If n2 = 0, then we just return n1.
% Essentially, it works on the following identity:
% n1 + n2 = (n1 + 1) + (n2 - 1)
function add (n1, n2 : nat) : nat
if n2 = 0 then
result n1
else
result add (add1 (n1), sub1 (n2))
end if
end add

% Note that this function could be made more efficient if, instead
% of blindly choosing to decrease n2 and increase n1, we chose to
% decrease the smaller of n1 and n2 and increase the larger of n1 and n2.
% Try writing another function that calls this add function in that way.
</pre>

===Problem Three===
<pre>
% This function works by decreasing n2 and increasing n1.
% It works on the following identity:
% If n2 is even: n1 * n2 = double (n1) * halve (n2)
% If n2 is odd: n1 * n2 = n1 + double (n1) * halve (n2)
function multiply (n1, n2 : nat) : nat
if n2 = 1 then
result n1
elsif n2 mod 2 = 0 then % n2 is even
result multiply (double (n1), halve (n2))
else % n2 is odd
result n1 + multiply (double (n1), halve (n2))
end if
end multiply
</pre>

==Credits==
Authour: [[Cervantes]]

Added by: [[Saad]]

Turing Functions and Procedures

2008-10-12T19:39:09Z

Saad: /* Functions and Procedures */

=Functions and Procedures=

==Introduction==

Thus far, we've learned enough of the Turing language to be able to write some decently large programs. We've learned some fundamentals of Turing -- variables, basic input/output, and if statements. Indeed, these concepts translate relatively smoothly to most any other programming language you might learn. So, having mastered these basics, what's next? Well, having a way to organize our code would be good. Right now, whatever code you write runs linearly, from top to bottom. If you want to run a section of code twice, you have to type it out twice. Wouldn't it be great if we could factor out the commonalities in our code, so we can write less? In truth, we haven't learned very much, so it might be difficult to see the advantage of this. Just bear with me.

==Introducing the Procedure==

At its simplest, a procedure is just some lines of Turing code. We wrap some special syntax around our lines of Turing code and think up a name for them. After we have defined our procedure, we can ''call'' the procedure by saying its name. When we do this, we run those lines of Turing code that are wrapped inside the procedure definition. This is easiest to see with an example:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
greet
</pre>
So now the single line of code, ''put "Hello world!"'', can be executed any time we call the ''greet'' procedure. The above code is identical to the following code:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
put "Hello world!"
</pre>
All I've done is substituted the code inside the ''greet'' procedure for the call to ''greet'' in the last line of the original program.

So, why is this useful? It's useful because now whenever we want to output "Hello world!", we don't have to type, ''put "Hello world!"'', but only ''greet''. Okay, so we saved on typing fourteen charactes. Not a big deal, right? But what if we wrote a program that said "Hello world!" a lot. Our program said hello to the world ten times during the course of its execution. Now, we're looking back at our program and thinking, "You know, 'Hello world!' isn't really what we want to say. We really are only talking to one person--George. We should instead say 'Hello George!'." So, now we've got to go into our code and change it. If we used a ''greet'' procedure, this change involves changing the definition of the procedure so that it becomes the following:
<pre>
procedure greet
put "Hello George!"
end greet
</pre>
If we hadn't used this procedure, we would have to go through our code, searching for any time we said "Hello world!" and change it to be "Hello George!". That's a lot of unnecessary work, relative to how effective our ''greet'' solution is.

But now, what if we aren't always talking to George?

==Procedures with Parameters==

Instead of writing a procedure to greet to George and another procedure to greet to Phil and another to greet to Anthony, we should try to write a procedure that can greet to anyone. Here's one possibility:
<pre>
var name : string
procedure greet
put "Hello ", name, "!"
end greet

name := "George"
greet

name := "Phil"
greet

name := "Anthony"
greet
</pre>
This works, but it's clunky. We've got that variable up there, ''name''. It's what we call a '''global variable'''. It's called that because it is global to the whole program. No matter where we are in our code, we can always see the ''name'' variable. Really, we don't need to keep track of ''name''. We only need it ''inside the greet procedure''. Here's where '''parameters''' are used.
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
greet ("Phil")
greet ("Anthony")
</pre>
In the definition of our greet procedure, I added that extra bit at the end--the stuff in parentheses. That says that when we call the greet procedure, we must give it one '''argument''', and that argument must be a string. It also says that for all code inside the procedure, there exists a '''constant''' called "name" that has the value we give it when we call the procedure. So, when we call ''greet ("George")'', we are setting ''name'' to be "George", and we execute the code inside the procedure. The following two pieces of code are identical:
<pre>
greet ("George")
</pre>
<pre>
put "Hello ", "George", "!"
</pre>
I mentioned earlier that inside the ''greet'' procedure there exists this constant called name. There are two things we need to understand about it. First, it is constant. We can't change the value of name. Let's get some example code and figure out why:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

greet ("George")
</pre>
This code fails because, inside ''greet'', ''name'' is really just a ''reference to "George"''. When we try to redefine name, we're really trying to redefine the string literal "George". Of course, that's impossible. What if we did this, though?
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
</pre>
Now you might think that, inside ''greet'', ''name'' is a reference to ''person'', which is a variable, so attempting to redefine ''name'' is really redefining ''person'', and that's okay. However, it's not quite that simple. See, ''greet'' expects a string as its argument, not a variable. In ''greet (person)'', ''person'' is an expression. It gets evaluated down to a string value; it gets evaluated to "George". Now, once again, we're passing the string literal "George" into ''greet'', and we're back at our first situation.

The second thing we need to understand about ''name'' is that it's '''local'''. It exists only within the procedure. The following code fails:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
put name
</pre>
''name'' doesn't exist outside of the ''greet'' procedure. It's '''local'''. It's '''scope''' is the ''greet'' procedure. You should also note that each time we call ''greet'' we are creating a new ''name'' constant.

What if we wanted to write a procedure that introduces two people to each other? We need a procedure that can two arguments, not one.

==Procedures with Multiple Parameters==

I will now define a procedure, called ''introduce'', that introduces two people to each other:
<pre>
procedure introduce (person1 : string, person2 : string)
put person1, ", this is ", person2, "."
put person2, ", meet ", person1, "."
end introduce

% Call the procedure
introduce ("Jackie", "Bruce")
</pre>
The output of this program will be:
<pre>
Jackie, this is Bruce.
Bruce, meet Jackie.
</pre>
However, reversing the order of the names results in a different output:
<pre>
introduce ("Bruce", "Jackie")
</pre>
<pre>
Bruce, this is Jackie.
Jackie, meet Bruce.
</pre>
You should be able to see how this works. When I call ''introduce'', person1 references the first name I give, and person2 references the second name I give. It's based on the ''order'' of the parameters/arguments. (Note some terminology here: person1 and person2 are the parameters; "Bruce" and "Jackie" are the arguments.)

Here's a little, unimportant shortcut. We can declare more than one variable on the same line, provided they are of the same type:
<pre>var name1, name2 : string</pre>
We can do the same with parameters:
<pre>
procedure introduce (person1, person2 : string)
%...
end introduce
</pre>

Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.
<pre>
procedure put_product (num1, num2 : real)
put num1 * num2
end put_product

put_product (4, 6) % Outputs 24
</pre>
However, what we're doing is rather silly, isn't it? I mean, aside from the fact that we're defining a procedure to do multiplication, which we can do very quickly anyways. What's silly about this is that we've cornered ourselves. This procedure forces us to send the product to the standard output. What if we wanted to store it in a variable, or draw it in a pretty font, or pass it to some other procedure? Take a minute and think about how we might solve this problem. We want to be able to generalize, here. We want to write something that can multiply two numbers we give it, but still give us the flexibility to do what we want with the answer.

If you're thinking about passing in another parameter that says what we are to do with the prodcut we calculate, then you're thinking way ahead of the game. It's possible, but not easy. There's an easier way.

==Introducing Functions==

Instead of writing a procedure that outputs the product of two numbers, we'll write a function that computes the prodcut of two numbers and ''returns that value''. Then we can decide what to do with that number. That's what a function is: it's the same as a procedure, except it returns a value.

<pre>
function product (num1, num2 : real) : real
result num1 * num2
end product

put product (4, 6) % outputs 24
</pre>
There's some new syntax there. First, we're using the keyword, "function", instead of "procedure". Next, there's a ": real" after our parameter list. That signifies what type of value our function will return. Also, we've used the '''result''' keyword. Earlier I said that functions return a value. The value returned is given by what is immediately after the '''result''' keyword.

Using a function gives us more flexibility. We don't have to send our answer to the standard output. We could store it in a variable, for instance.
<pre>
var n : real := product (1.5, 3) % n := 4.5
</pre>
Then we could use that elsewhere:
<pre>put product (n, 2) % outputs 9</pre>
Or perhaps better yet:
<pre>put product (product 1.5, 3) 2) % outputs 9</pre>

Let's now look a little closer at '''result'''. It has an interesting behaviour that we have yet to examine.

==A Closer Look at 'result'==

A function's sole purpose is to compute and return a value. With that in mind, let's write a ficticious function:
<pre>
function ficticious (number : int) : int
result number + 1
put "Yarr, it be a cold day."
end ficticious

% Call our function and store its answer in a variable
var n : int := ficticious (4)
</pre>
What has happened here? Surely, ''ficticious (4)'' returns the value 5. So ''n'' should be 5. What about that crazy pirate message? Well, as soon as the function computed its value, it returned that value and completed execution. The "Yarr..." message was never output; that line of code was never reached.

This behaviour is a bit irratic. It can make it difficult to understand how a function is working. At the same time, it can be quite useful in shortening code. You've got a find a balance between short code and understandable code.

Soon we will compare and contrast procedures and functions. Before we can do that, however, we need to re-examine what I said earlier about our parameter being constant.

==Variable Parameters==

Let's go back to our first example with parameters:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
</pre>
I had argued that ''name'' is constant. We cannot change its value. Indeed, we cannot. However, we can change this code so that ''name'' is in fact variable. All we have to do is specify that the ''name'' parameter is not simply a string, but is a variable that is a string. We do this by using the '''var''' keyword.
<pre>
procedure greet (var name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
put "After calling greet, the value of person is now ", person
</pre>
<pre>
Hello George!
And hello to Freddy as well!
After calling greet, the value of person is now Freddy
</pre>
The difference here is that ''greet'' is expecting to take a string variable, instead of just a string. So when we pass ''person'' to it, ''name'' actually becomes a reference to the variable ''person''. Then, changing the value of ''name'' changes the value of ''person''.

Now, we're familiar with procedures and functions. We now know enough to start thinking about when we should use a procedure and when we should use a function.

==Functions vs. Procedures==

Both functions and procedures are what some call "''subroutines''"--they are something we can use to store code and call at a later point. A function computes and returns a value, whereas a procedure just runs some code. We need to get an understanding of when to use a function and when to use a procedure. Let's look at a pretty famous case study.

In Turing, there are two ways of generating a random integer. The first way is to use the built-in function, ''Rand.Int''. (This is a function just like what we've been writing so far. Don't let the fact that it has a period in it's name fool you.) ''Rand.Int'' takes two numbers, a low and a high; it produces a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
n := Rand.Int (4, 11)
</pre>
Now n is a random integer between 4 and 11.

The second way to produce random integers is to use the procedure, ''randint''. This procedure first takes a variable (like our ''greet'' procedure did in the last section) and also takes two numbers, a low and a high. ''randint'' takes the variable you give it and sets it to a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
randint (n, 4, 11)
</pre>

Now, which is better: ''Rand.Int'' or ''randint''? The correct answer is ''Rand.Int''. Here's why:

First, ''Rand.Int'' is more flexible. Say you wrote a function called "squeeze" that took in an integer. You want to give it a random integer between 1 and 6. Let's look at the two options:
<pre>squeeze (Rand.Int (1, 6))</pre>
<pre>
var n : int
randint (n, 1, 6)
squeeze (n)
</pre>
Clearly the ''Rand.Int'' version is cleaner. There's no polluting the global namespace with useless variables like "''n''".

The second reason is a bit more theoretical, but is of equal importance. ''randint'' takes in a variable and does something to it. We don't really know what. We have trust the documentation. Now, we've also got to trust the documentation of ''Rand.Int''. However, there's an important difference. With ''Rand.Int'', we assign to our variable the value returned by the function. With ''randint'', we have given our precious variable to the procedure, along with all the permissions necessary for the procedure to slaughter our poor variable. It has complete control. It can write whatever it wants in there. We've suddenly given away control of the ''state'' of our program. (State is a term that collectively means the values of all our variables and also our current location in the execution of the code.) The fewer people we give this control to, the better.

If you're not yet convinced, take a look at this. I'll code a version of ''randint'' for you.
<pre>
procedure my_randint (var num : int, low, high : int)
if num mod 2 = 0
num := low + (num * 2) mod (high - low + 1)
else
num := low + (num + 2) mod (high - low + 1)
end if
end my_randint
</pre>
So ''my_randint'' isn't really random, but it might fool you. Take a look at some sample data:
<pre>
% I've taken a shortcut here. When I say
% my_randint (0, 5, 10)
% I really mean
% var n : int := 0
% my_randint (n, 5, 10)

my_randint (0, 5, 10) %-> 5
my_randint (1, 5, 10) %-> 8
my_randint (2, 5, 10) %-> 9
my_randint (3, 5, 10) %-> 10
my_randint (4, 5, 10) %-> 7
my_randint (5, 5, 10) %-> 6
my_randint (6, 5, 10) %-> 5
my_randint (7, 5, 10) %-> 8
my_randint (8, 5, 10) %-> 9
my_randint (9, 5, 10) %-> 10
my_randint (10, 5, 10) %-> 7
</pre>

I could not have done a similar thing if I were using a function, because I was never given a value for ''num''. (I know what some of you are thinking: "What if I give an uninitialized variable to my_randint? It'll crash." It's possible that I could hack something together that could take care of this, but that's not the point.) The point of this is to show you that by giving the procedure control of your variable, it can use it that variable for evil purposes, as I have done with this ''my_randint'' procedure.

I sincerely hope this has convinced you that functions are superior to procedures. I'm not saying that functions should be used exclusively. There are times when procedures are needed. Rather, I'm just saying that when you have a choice of using a function or using a procedure, choose the function. Nice functions are ones that compute a value based soley on the parameters they take. They don't rely on any global variables. These are functions that are easily documented. At the other extreme are procedures that use global variables inside their definition and also take in variables and modify them. These procedures are ''dangerous!'' and very hard to document.

There is one last thing for us to discuss. It's a very powerful concept known as "recursion".

==Recursion==

I'd like to start this section off with a quotation:
<pre>To understand recursion, you must first understand recursion.</pre>
A recursive subroutine is a subroutine that calls itself. One of the most famous and basic examples is the factorial function. The factorial function takes in a number and returns the product of that number and the factorial of the number minus one. Also, the factorial of one is defined to be one. This is the recursive definition of the function. It translates very easily into code:
<pre>
function factorial (n : int) : int
if n = 1 then
result 1
else
result n * factorial (n - 1)
end if
end factorial

put factorial (3) % Outputs "6". Note 6 = 3*2*1
put factorial (5) % Outputs "120". Note 120 = 5*4*3*2*1
</pre>
I will give a condensed trace of the factorial function:
<pre>
factorial (5)
(5 * factorial (4))
(5 * (4 * factorial (3)))
(5 * (4 * (3 * factorial (2))))
(5 * (4 * (3 * (2 * factorial (1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6))
(5 * 24)
120
</pre>
I've given the recursive definition of the factorial function. A non-recursive definition is to say that factorial (n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1. if you know about loops, you can code this definition of the factorial function. You can then compare and contrast the two definitions and see which you prefer. I hope you'll prefer this version, but that's for time to decide.

As a segue into the next tutorial (which will be a tutorial on looping constructs), I will now present a recursive procedure that counts down to 1, and then displays, "Blast off!!"
<pre>
procedure countdown (high : int)
if high = 0 then
put "Blast off!!"
else
put high, "..."
countdown (high - 1)
end if
end countdown
</pre>
Calling ''countdown (5)'' produces:
<pre>
5...
4...
3...
2...
1...
Blast off!!
</pre>

'''Question One!''' Create a guessing game. Your program will have a global variable that represents the number the user is trying to guess. Use recursion to write a procedure called ''guess''. When run, ''guess'' prompts the user to input a number. If the guessed number is equal to ''the'' number, a winning message is displayed. Otherwise, the user is told whether his/her guess was too high or too low, and is prompted to guess another number.
A solution to this problem can be found at the end of the tutorial.

'''Question Two!''' Define a function called ''add'' that takes two natural numbers and returns their sum. There's a catch, though. You're not allowed to use the + operator. However, you are allowed to use these two functions that I supply you with:
<pre>
function add1 (n : int) : int
result n + 1
end add1
function sub1 (n : int) : int
result n - 1
end sub1
</pre>
A solution to this problem can be found at the end of the tutorial.

'''Question Three''' Define a function called ''multiply'' that takes two natural numbers and returns their product. Once again, there's a catch. You're not allowed to use the built in * operator. (You are allowed to use the + operator though.) You can, however, use the following two functions that I provide you with:
<pre>
function double (n : int) : int
result n + n
end double

% The halve function performs integer division by 2.
% Examples: halve (8) -> 4
% halve (17) -> 8
function halve (n : int) : int
result floor (n / 2)
end halve
</pre>
Hint: You should use the binary definition of a natural number. That is, a natural number is one of

*1
*2*k where k is a natural number
*2*k + 1 where k is a natural number

That is why I gave you the double and halve functions. It's possible to write a solution using the unary definition of a natural number (sort of like in the solution to problem two), but it will be much slower than the solution using the binary definition.
A solution to this problem can be found at the end of the tutorial.

==Conclusion==

I hope you find these exercises in recursion interesting. At this point, we've learned a small amount of the Turing language, but you see we can do some pretty powerful things using this concept of recursion.

Even if we don't take advantage of recursion, however, the topics covered in this tutorial still give us considerable power. They allow us to organize our code. We can save ourselves from repeating ourselves. We can generalize by using parameters. Indeed, the rather simple idea of factoring out common code has led to powerful advances.

==Solutions==

===Problem One===
<pre>
var the_num := Rand.Int (1, 100)

proc guess
put "Please input a guess: " ..
var g : int
get g
if g = the_num then
put "You've got it!"
elsif g < the_num then
put "You've guessed too low. Try again."
guess
else
put "You've guessed too high. Try again."
guess
end if
end guess

guess
</pre>

===Problem Two===
<pre>
% This function works by increasing n2 by one as we
% decrease n1 by one. If n2 = 0, then we just return n1.
% Essentially, it works on the following identity:
% n1 + n2 = (n1 + 1) + (n2 - 1)
function add (n1, n2 : nat) : nat
if n2 = 0 then
result n1
else
result add (add1 (n1), sub1 (n2))
end if
end add

% Note that this function could be made more efficient if, instead
% of blindly choosing to decrease n2 and increase n1, we chose to
% decrease the smaller of n1 and n2 and increase the larger of n1 and n2.
% Try writing another function that calls this add function in that way.
</pre>

===Problem Three===
<pre>
% This function works by decreasing n2 and increasing n1.
% It works on the following identity:
% If n2 is even: n1 * n2 = double (n1) * halve (n2)
% If n2 is odd: n1 * n2 = n1 + double (n1) * halve (n2)
function multiply (n1, n2 : nat) : nat
if n2 = 1 then
result n1
elsif n2 mod 2 = 0 then % n2 is even
result multiply (double (n1), halve (n2))
else % n2 is odd
result n1 + multiply (double (n1), halve (n2))
end if
end multiply
</pre>

==Credits==
Authour: [[Cervantes]]

Added by: [[Saad]]

Turing Functions and Procedures

2008-10-12T19:36:39Z

Saad: /* Credits */

Turing String Manipulation

2008-10-12T19:36:18Z

Saad: /* Credits */

==String Manipulation In Turing==

Hello thrill-seekers! So you've decided delve into the terrible and mystifying world of string manipulation, aye? For the next half-hour, you will be my slave. Do what I tell you, and you will learn well. Do otherwise, and you shall... not learn well!
Alright, enough of that. Let's start.
===What is String Manipulation and why do we care?===
String manipulation means, quite simply, manipulating strings. For example, if we take a string that the user inputs (such as Paul Simon, as their user name) we might want to greet the user by saying "Hello ", usersFirstName (in this case, Paul). Or what if we want to prevent the program from crashing when the user does something stupid like enter "qr7" when we want them to input an integer?

==Search for a space==
Strings allow us to do stuff with a specific character from them. For example,
<pre>
put "Paul Simon" (1 .. 4)
</pre>
would output Paul. Or I could do stuff like
<pre>
if myString (5) = " " then
put "I found a space!"
end if
</pre>
But how do we know that the 5th character of myString is a space? We don't. If we want to find one, we can run through a for loop:
<pre>
for i : 1 .. length (myString)
if myString (i) = " " then
put "Space found at position ", i
end if
end for
</pre>
Notice the use of the length function. Length returns the length of the string, quite simply. In other words, it returns the number of characters in the string. So length ("a") would be 1, and length ("12345") would be 5.

===Find the user's first name===
Excellent. So now let's say hello to Mr. Simon, only a little less formally:
<pre>
var name := "Paul Simon"
var firstName : string
for i : 1 .. length (name)
if name (i) = " " then
firstName := name (1 .. i - 1)
end if
end for
put "Hello ", firstName, "!"
</pre>
We go through the whole string searching for a space. As soon as we find one, we set firstName to be everything before that space, then exit the for loop.
But what if the user enters his/her full name, ie. Paul Frederic Simon. The program will output "Hello Paul Frederic!" That's not what we want. This is easily fixed, though. We'll just add an exit after we've decided where the first space is.
What if the user enters only his first name (ie. "Paul")? The program will crash, because firstName was never assigned anything. We can fix this problem by setting firstName to equal name at the beginning of the program. So, if name contains any spaces, it will chomp them off, otherwise it will just (effectively) use name as the output.
Final code looks like this:
<pre>
var name := "Paul Simon"
var firstName := name
for i : 1 .. length (name)
if name (i) = " " then
firstName := name (1 .. i - 1)
exit
end if
end for
put "Hello ", firstName, "!"
</pre>

===Find the users last name===
This is easy enough: it's just a small modification on the last code.
<pre>
var name := "Paul Simon"
var lastName := name
for i : 1 .. length (name)
if name (i) = " " then
lastName := name (i + 1 .. *)
end if
end for
put "Hello Mr. ", lastName, "!"
</pre>
Note the user of the asterisk (*). The asterisk represents the last character of the string.
<pre>
var name := "Paul Simon"
put name (*)
put name (length(name))
</pre>
Both of these methods output the same thing. The * is just shorter. Smile
Also, note that I removed the exit. This way, if the user's name is set to "Paul Frederic Simon", it will output "Simon" not "Frederic Simon".

===Finding the middle name===
This one's a little bit trickier.
<pre>
var name := "Paul Frederic Simon"
var middleName := name
var firstSpace := 0
for i : 1 .. length (name)
if name (i) = " " and firstSpace ~= 0 then
middleName := name (firstSpace + 1 .. i - 1)
end if
if name (i) = " " then
firstSpace := i
end if
end for
put "Hello Mr. ", middleName, "!"
</pre>
In this one, I've used a variable to store the positin of the first space. Then, we continue on looking for the next space. When we find it, we make everything after the first space but before the current space equal to middleName. Also, note the positions of the if statements. Were they to be in reverse order, as soon as a space is found, firstSpace would be given a new value and then the next if statement would be true because firstSpace is no longer 0. So we would end up with an error.

Note that all these things could also be done using the index function.

==Converting variable types==
This next part is really useful for error-traping. But it's also useful for other things, such as drawing text on the screen using Font.Draw (where you must use a string)
The Functions
<pre>
strint (s : string [base : int]) : int
intstr (i : int [, width : int [, base : int]]) : string
strreal (s : string) : real
realstr (r : real, width : int) : string
</pre>
A couple things you need to know. First, these are functions. They return a value. That's what the last : typeSpec means: it tells us what kind of value the function will return. Thus, the strint function returns an integer, whereas the intstr function returns a string. Next, anything inside brackets ( () ) are your parameters. These are the things that you pass into the function. In the strreal function, s : string means that I must pass a string into the function. Anything inside square brackets ( [] ) is optional.

===Error Proofing===
We'll error proof our integer input. The first and basic way to do integer input is like so:
<pre>
var num : int
get num
</pre>
But that crashes if the user enters "y". So let's fix it.
<pre>
var input : string
var num : int
get input
num := strint (input)
put num
</pre>
Whoo-whee! It runs! Sure, but we've still got the same problem. The program will still crash if the user enters "y". Why? Basically, strint cannot turn a "y" into a number. strint must return an integer (we know this because of the last : int). If it can't, it halts the program.
So, how do we fix this? Well, here's some more nice functions!
<pre>
strintok (s : string [, base : int]) : boolean
strrealok (s : string) : boolean
</pre>
These functions return boolean values: true or false. They return true if the string can be successfully changed into an integer (or real, in the case of the second function) and false if they cannot. No halting. So let's use them.
<pre>
var input : string
var num : int
get input
if strintok (input) then
num := strint (input)
put num
end if
</pre>
And there we have it. It's error proofed. (Well, close enough. The user can still crash the program by inputting lots and lots (255, is it?) of characters.)
The next thing to do would be to force the user to input an integer. We can use a loop and an exit statement for this:
<pre>
var input : string
var num : int
loop
cls
locate (1, 1)
put "Enter an integer: " ..
get input
if strintok (input) then
num := strint (input)
put num
exit
else
put "That's not a number, silly!"
delay (1000)
end if
end loop
</pre>
We only want to exit when the user enters a integer, like they were told.

===Font.Drawing an integer===
After error-proofing, this should be really easy.
If we want to use Font.Draw to put a number on the screen, we have to first convert it to a string. Why? Because Font.Draw expects it's first parameter to be a string. We know this because:
<pre>
Font.Draw (textStr : string, x, y, fontID, Colour : int)
</pre>
Alright, so say we want to draw a number on the screen.
<pre>
var font := Font.New ("Garamond:26:bold")
var num : int
get num %error proof this!
Font.Draw (intstr (num), 100, 100, font, black)
</pre>
Easy enough. We could also have simply done
<pre>
Font.Draw (intstr (10), 100, 100, font, black)
</pre>
But the first way gets you to error proof it for me. Mwahaha!

==ord and chr==
Next up, we learn about two new functions.
<pre>
ord (ch : char) : int
chr (i : int) : char
</pre>
ord takes a single character and returns an integer (that is specific to that character).
chr takes an integer and returns a single character (that is specific to that integer).
To use these, we need to haul out our ASCII chart. So, open Turing, open the Turing Help Manual (that's code for "press F10"), expand Turing Language, select Keystroke Codes.
Find the letter "A". It's ordinal value is 65. So
<pre>
put ord ("A")
</pre>
would output 65. Similarly,
<pre>
put chr (65)
</pre>
would output the letter "A" (without the quotes).
<pre>
var s : char := "A"
put chr (ord (s))

var i : int := 65
put ord (chr (i))
</pre>
For any character, s, chr (ord(s)) = s. Also, for any integer, i, ord (chr (i)) = i.
These functions are useful for a variety of things. For example, say you want to loop until the user presses Ctrl + Backspace:
<pre>
var input : string (1)
loop
getch (input)
exit when ord (input) = 127 %crtl + backspace
end loop
</pre>
Or, say you want to output the alphabet to the screen, in lower case letters:
<pre>
for i : 97 .. 122
put chr (i), " " ..
end for
</pre>
How about converting a string from upper case to lower case?
<pre>
var upperCaseString := "ROOOOAAAR"
var lowerCaseString := ""
for i : 1 .. length (upperCaseString)
lowerCaseString += chr (ord (upperCaseString (i)) + 32)
end for
put lowerCaseString
</pre>
If you don't already know what += means, it simply incriments the variable by whatever is after it.
<pre>
num += 1
</pre>
is the same as
<pre>
num := num + 1
</pre>
When using strings, it just adds the string (or character) to the end of my string.
Note that the ordinal value of any lower case letter is equal to the ordinal value of any upper case letter + 32.
Note that this doesn't quite work if your string contains things other than numbers. To fix this:
Turing:
<pre>
var upperCaseString := "RAWR!! HERE ME ROAR!!"
var lowerCaseString := ""
for i : 1 .. length (upperCaseString)
if ord (upperCaseString (i)) >= 65 and ord (upperCaseString (i)) <= 90 then %if it is a capital letter
lowerCaseString += chr (ord (upperCaseString (i)) + 32)
else
lowerCaseString += upperCaseString (i)
end if
end for
put lowerCaseString
</pre>
Yay! Next up, let's try outputting "Aa Bb Cc ... Yy Zz"
<pre>
for i : 65 .. 90
put chr (i), chr (i + 32), " " ..
end for
</pre>

==Conclusion==
So there you have it, string manipulation in a really big nutshell that took a long time to write. Aah, let's let Asian sum things up for me, my fingers are tired:
AsianSensation wrote:

Know this though, string manipulation comes with practice, and problem solving is a big part of this. So don't assume knowing all about index will make sure you will be able to solve a question. Index is merely a tool, not the solution.

Replace the word "index" with the words "the stuff covered in this tutorial, whatever that may be" and heed his advice (or wisdom).

Happy string manipulating

==Credits==
Authour: [[Cervantes]]

Added by: [[Saad]]

Turing String Manipulation

2008-10-12T19:35:42Z

Saad:

Turing Functions and Procedures

2008-10-12T19:35:20Z

Saad:

Turing Functions and Procedures

2008-10-12T19:33:59Z

Saad: /* Recursion */

Turing Walkthrough

2008-10-12T19:31:54Z

Saad: /* Essentials */

== Essentials ==

* '''[[The Start: Introduction, Comments, Output, Variables, Input (Turing)|The Basics]]''' - Introduction to programming, commenting, basic output, variables, and basic input ''by Cervantes''
* '''If structures''' - Write code that can make decisions ''by Cervantes''
* '''[[Turing_Functions_and_Procedures|Functions and Procedures]]''' - Organize your code into sections and call them at will; introduction to recursion ''by Cervantes''
* '''Loops and For loops''' - To repeat sections of code over and over ''by Cervantes''
* '''[[Turing_String_Manipulation|String Manipulation]]''' ''by Cervantes''
* '''Index''' - searching through a string ''by AsianSensation''
* '''Records and Types''' - Create new, compound data types ''by AsianSensation''
* '''Arrays''' - Mass variables ''by Clayton and Cervantes''
* '''Enumerated Types''' - Create an indexing system that is readable and understandable ''by Clayton''
* '''[[Turing_File_IO|File Input/Output]]''' - Reading and writing data from/to text files ''by Clayton''
* '''Bitwise Operators''' - Experiment with binary, getting closer to lowlevel programming ''by Zylum''
* '''Recursion''' - Subroutines that call themselves can achieve amazing results ''by Zylum''
* '''Modules''' - Collections of procedures and functions ''by Delos''
* '''Pointers''' - Referencing memory and creating linked lists ''by lyam_kaskade''.
* '''Classes Part I''' - Make your own objects ''by Cervantes''
* '''Classes Part II''' - Create objects that interact with each other ''by Cervantes''
* '''Classes Part III''' - Inheritance and Polymorphism to create a network of objects ''by Cervantes''
* '''Functional Programming (in Turing!)''' - Passing and returning anonymous functions ''by Cervantes''

== Extras ==

=== Graphics ===

* '''Basic Graphics''' - Make your program look nice ''by Asok''
* '''Fonts and locating put''' - Make your text look nice ''by basketball4ever''
* '''[[Turing_Eliminate_Flickering|View.Set and View.Update]]''' - Configuring the run window and eliminating animation flickering ''by Clayton''
* '''Windows''' - Managing the window(s) your program run(s) in ''by Delos''
* '''Pictures''' - Import your own .bmp's and .jpg's ''by Hacker Dan''
* '''RGB''' - Create your own colours as you need them ''by TheZsterBunny''
* '''Intro to 3D''' - Project a 3D world onto the 2D computer screen ''by Windsurfer''
* '''GUI (Graphical User Interface)''' - Make clickable buttons ''by Recneps''

=== Advanced Input ===

* '''More advanced input''' - getch, Input.KeyDown, Mouse.Where ''by DanShadow''
* '''Input.KeyDown''' - in more detail ''by Tony''
* '''Mouse.Where''' - some more detail ''by Hacker Dan''

=== Other Stuff ===

* '''The Dir Module''' - Traverse and manipulate directories ''by jamonathin''
* '''The Net Module''' - Use Turing and the internet together by ''DanShadow''
* '''Collision Detection''' - Determine when two objects collide--a necessity for games ''by richcash''
* '''Whatdotcolour''' - Another approach to collision detection and other useful things

== Credits ==

Original walkthrough by [[Cervantes]].

Turing Functions and Procedures

2008-10-12T19:31:00Z

Saad:

==Functions and Procedures==

==Introduction==

Thus far, we've learned enough of the Turing language to be able to write some decently large programs. We've learned some fundamentals of Turing -- variables, basic input/output, and if statements. Indeed, these concepts translate relatively smoothly to most any other programming language you might learn. So, having mastered these basics, what's next? Well, having a way to organize our code would be good. Right now, whatever code you write runs linearly, from top to bottom. If you want to run a section of code twice, you have to type it out twice. Wouldn't it be great if we could factor out the commonalities in our code, so we can write less? In truth, we haven't learned very much, so it might be difficult to see the advantage of this. Just bear with me.

==Introducing the Procedure==

At its simplest, a procedure is just some lines of Turing code. We wrap some special syntax around our lines of Turing code and think up a name for them. After we have defined our procedure, we can ''call'' the procedure by saying its name. When we do this, we run those lines of Turing code that are wrapped inside the procedure definition. This is easiest to see with an example:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
greet
</pre>
So now the single line of code, ''put "Hello world!"'', can be executed any time we call the ''greet'' procedure. The above code is identical to the following code:
<pre>
% Define the greet procedure
procedure greet
put "Hello world!"
end greet

% Call the greet procedure
put "Hello world!"
</pre>
All I've done is substituted the code inside the ''greet'' procedure for the call to ''greet'' in the last line of the original program.

So, why is this useful? It's useful because now whenever we want to output "Hello world!", we don't have to type, ''put "Hello world!"'', but only ''greet''. Okay, so we saved on typing fourteen charactes. Not a big deal, right? But what if we wrote a program that said "Hello world!" a lot. Our program said hello to the world ten times during the course of its execution. Now, we're looking back at our program and thinking, "You know, 'Hello world!' isn't really what we want to say. We really are only talking to one person--George. We should instead say 'Hello George!'." So, now we've got to go into our code and change it. If we used a ''greet'' procedure, this change involves changing the definition of the procedure so that it becomes the following:
<pre>
procedure greet
put "Hello George!"
end greet
</pre>
If we hadn't used this procedure, we would have to go through our code, searching for any time we said "Hello world!" and change it to be "Hello George!". That's a lot of unnecessary work, relative to how effective our ''greet'' solution is.

But now, what if we aren't always talking to George?

==Procedures with Parameters==

Instead of writing a procedure to greet to George and another procedure to greet to Phil and another to greet to Anthony, we should try to write a procedure that can greet to anyone. Here's one possibility:
<pre>
var name : string
procedure greet
put "Hello ", name, "!"
end greet

name := "George"
greet

name := "Phil"
greet

name := "Anthony"
greet
</pre>
This works, but it's clunky. We've got that variable up there, ''name''. It's what we call a '''global variable'''. It's called that because it is global to the whole program. No matter where we are in our code, we can always see the ''name'' variable. Really, we don't need to keep track of ''name''. We only need it ''inside the greet procedure''. Here's where '''parameters''' are used.
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
greet ("Phil")
greet ("Anthony")
</pre>
In the definition of our greet procedure, I added that extra bit at the end--the stuff in parentheses. That says that when we call the greet procedure, we must give it one '''argument''', and that argument must be a string. It also says that for all code inside the procedure, there exists a '''constant''' called "name" that has the value we give it when we call the procedure. So, when we call ''greet ("George")'', we are setting ''name'' to be "George", and we execute the code inside the procedure. The following two pieces of code are identical:
<pre>
greet ("George")
</pre>
<pre>
put "Hello ", "George", "!"
</pre>
I mentioned earlier that inside the ''greet'' procedure there exists this constant called name. There are two things we need to understand about it. First, it is constant. We can't change the value of name. Let's get some example code and figure out why:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

greet ("George")
</pre>
This code fails because, inside ''greet'', ''name'' is really just a ''reference to "George"''. When we try to redefine name, we're really trying to redefine the string literal "George". Of course, that's impossible. What if we did this, though?
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
</pre>
Now you might think that, inside ''greet'', ''name'' is a reference to ''person'', which is a variable, so attempting to redefine ''name'' is really redefining ''person'', and that's okay. However, it's not quite that simple. See, ''greet'' expects a string as its argument, not a variable. In ''greet (person)'', ''person'' is an expression. It gets evaluated down to a string value; it gets evaluated to "George". Now, once again, we're passing the string literal "George" into ''greet'', and we're back at our first situation.

The second thing we need to understand about ''name'' is that it's '''local'''. It exists only within the procedure. The following code fails:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
put name
</pre>
''name'' doesn't exist outside of the ''greet'' procedure. It's '''local'''. It's '''scope''' is the ''greet'' procedure. You should also note that each time we call ''greet'' we are creating a new ''name'' constant.

What if we wanted to write a procedure that introduces two people to each other? We need a procedure that can two arguments, not one.

==Procedures with Multiple Parameters==

I will now define a procedure, called ''introduce'', that introduces two people to each other:
<pre>
procedure introduce (person1 : string, person2 : string)
put person1, ", this is ", person2, "."
put person2, ", meet ", person1, "."
end introduce

% Call the procedure
introduce ("Jackie", "Bruce")
</pre>
The output of this program will be:
<pre>
Jackie, this is Bruce.
Bruce, meet Jackie.
</pre>
However, reversing the order of the names results in a different output:
<pre>
introduce ("Bruce", "Jackie")
</pre>
<pre>
Bruce, this is Jackie.
Jackie, meet Bruce.
</pre>
You should be able to see how this works. When I call ''introduce'', person1 references the first name I give, and person2 references the second name I give. It's based on the ''order'' of the parameters/arguments. (Note some terminology here: person1 and person2 are the parameters; "Bruce" and "Jackie" are the arguments.)

Here's a little, unimportant shortcut. We can declare more than one variable on the same line, provided they are of the same type:
<pre>var name1, name2 : string</pre>
We can do the same with parameters:
<pre>
procedure introduce (person1, person2 : string)
%...
end introduce
</pre>

Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.
<pre>
procedure put_product (num1, num2 : real)
put num1 * num2
end put_product

put_product (4, 6) % Outputs 24
</pre>
However, what we're doing is rather silly, isn't it? I mean, aside from the fact that we're defining a procedure to do multiplication, which we can do very quickly anyways. What's silly about this is that we've cornered ourselves. This procedure forces us to send the product to the standard output. What if we wanted to store it in a variable, or draw it in a pretty font, or pass it to some other procedure? Take a minute and think about how we might solve this problem. We want to be able to generalize, here. We want to write something that can multiply two numbers we give it, but still give us the flexibility to do what we want with the answer.

If you're thinking about passing in another parameter that says what we are to do with the prodcut we calculate, then you're thinking way ahead of the game. It's possible, but not easy. There's an easier way.

==Introducing Functions==

Instead of writing a procedure that outputs the product of two numbers, we'll write a function that computes the prodcut of two numbers and ''returns that value''. Then we can decide what to do with that number. That's what a function is: it's the same as a procedure, except it returns a value.

<pre>
function product (num1, num2 : real) : real
result num1 * num2
end product

put product (4, 6) % outputs 24
</pre>
There's some new syntax there. First, we're using the keyword, "function", instead of "procedure". Next, there's a ": real" after our parameter list. That signifies what type of value our function will return. Also, we've used the '''result''' keyword. Earlier I said that functions return a value. The value returned is given by what is immediately after the '''result''' keyword.

Using a function gives us more flexibility. We don't have to send our answer to the standard output. We could store it in a variable, for instance.
<pre>
var n : real := product (1.5, 3) % n := 4.5
</pre>
Then we could use that elsewhere:
<pre>put product (n, 2) % outputs 9</pre>
Or perhaps better yet:
<pre>put product (product 1.5, 3) 2) % outputs 9</pre>

Let's now look a little closer at '''result'''. It has an interesting behaviour that we have yet to examine.

==A Closer Look at 'result'==

A function's sole purpose is to compute and return a value. With that in mind, let's write a ficticious function:
<pre>
function ficticious (number : int) : int
result number + 1
put "Yarr, it be a cold day."
end ficticious

% Call our function and store its answer in a variable
var n : int := ficticious (4)
</pre>
What has happened here? Surely, ''ficticious (4)'' returns the value 5. So ''n'' should be 5. What about that crazy pirate message? Well, as soon as the function computed its value, it returned that value and completed execution. The "Yarr..." message was never output; that line of code was never reached.

This behaviour is a bit irratic. It can make it difficult to understand how a function is working. At the same time, it can be quite useful in shortening code. You've got a find a balance between short code and understandable code.

Soon we will compare and contrast procedures and functions. Before we can do that, however, we need to re-examine what I said earlier about our parameter being constant.

==Variable Parameters==

Let's go back to our first example with parameters:
<pre>
procedure greet (name : string)
put "Hello ", name, "!"
end greet

greet ("George")
</pre>
I had argued that ''name'' is constant. We cannot change its value. Indeed, we cannot. However, we can change this code so that ''name'' is in fact variable. All we have to do is specify that the ''name'' parameter is not simply a string, but is a variable that is a string. We do this by using the '''var''' keyword.
<pre>
procedure greet (var name : string)
put "Hello ", name, "!"
name := "Freddy"
put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)
put "After calling greet, the value of person is now ", person
</pre>
<pre>
Hello George!
And hello to Freddy as well!
After calling greet, the value of person is now Freddy
</pre>
The difference here is that ''greet'' is expecting to take a string variable, instead of just a string. So when we pass ''person'' to it, ''name'' actually becomes a reference to the variable ''person''. Then, changing the value of ''name'' changes the value of ''person''.

Now, we're familiar with procedures and functions. We now know enough to start thinking about when we should use a procedure and when we should use a function.

==Functions vs. Procedures==

Both functions and procedures are what some call "''subroutines''"--they are something we can use to store code and call at a later point. A function computes and returns a value, whereas a procedure just runs some code. We need to get an understanding of when to use a function and when to use a procedure. Let's look at a pretty famous case study.

In Turing, there are two ways of generating a random integer. The first way is to use the built-in function, ''Rand.Int''. (This is a function just like what we've been writing so far. Don't let the fact that it has a period in it's name fool you.) ''Rand.Int'' takes two numbers, a low and a high; it produces a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
n := Rand.Int (4, 11)
</pre>
Now n is a random integer between 4 and 11.

The second way to produce random integers is to use the procedure, ''randint''. This procedure first takes a variable (like our ''greet'' procedure did in the last section) and also takes two numbers, a low and a high. ''randint'' takes the variable you give it and sets it to a random integer between the low and the high. Here's an example of it in use:
<pre>
var n : int
randint (n, 4, 11)
</pre>

Now, which is better: ''Rand.Int'' or ''randint''? The correct answer is ''Rand.Int''. Here's why:

First, ''Rand.Int'' is more flexible. Say you wrote a function called "squeeze" that took in an integer. You want to give it a random integer between 1 and 6. Let's look at the two options:
<pre>squeeze (Rand.Int (1, 6))</pre>
<pre>
var n : int
randint (n, 1, 6)
squeeze (n)
</pre>
Clearly the ''Rand.Int'' version is cleaner. There's no polluting the global namespace with useless variables like "''n''".

The second reason is a bit more theoretical, but is of equal importance. ''randint'' takes in a variable and does something to it. We don't really know what. We have trust the documentation. Now, we've also got to trust the documentation of ''Rand.Int''. However, there's an important difference. With ''Rand.Int'', we assign to our variable the value returned by the function. With ''randint'', we have given our precious variable to the procedure, along with all the permissions necessary for the procedure to slaughter our poor variable. It has complete control. It can write whatever it wants in there. We've suddenly given away control of the ''state'' of our program. (State is a term that collectively means the values of all our variables and also our current location in the execution of the code.) The fewer people we give this control to, the better.

If you're not yet convinced, take a look at this. I'll code a version of ''randint'' for you.
<pre>
procedure my_randint (var num : int, low, high : int)
if num mod 2 = 0
num := low + (num * 2) mod (high - low + 1)
else
num := low + (num + 2) mod (high - low + 1)
end if
end my_randint
</pre>
So ''my_randint'' isn't really random, but it might fool you. Take a look at some sample data:
<pre>
% I've taken a shortcut here. When I say
% my_randint (0, 5, 10)
% I really mean
% var n : int := 0
% my_randint (n, 5, 10)

my_randint (0, 5, 10) %-> 5
my_randint (1, 5, 10) %-> 8
my_randint (2, 5, 10) %-> 9
my_randint (3, 5, 10) %-> 10
my_randint (4, 5, 10) %-> 7
my_randint (5, 5, 10) %-> 6
my_randint (6, 5, 10) %-> 5
my_randint (7, 5, 10) %-> 8
my_randint (8, 5, 10) %-> 9
my_randint (9, 5, 10) %-> 10
my_randint (10, 5, 10) %-> 7
</pre>

I could not have done a similar thing if I were using a function, because I was never given a value for ''num''. (I know what some of you are thinking: "What if I give an uninitialized variable to my_randint? It'll crash." It's possible that I could hack something together that could take care of this, but that's not the point.) The point of this is to show you that by giving the procedure control of your variable, it can use it that variable for evil purposes, as I have done with this ''my_randint'' procedure.

I sincerely hope this has convinced you that functions are superior to procedures. I'm not saying that functions should be used exclusively. There are times when procedures are needed. Rather, I'm just saying that when you have a choice of using a function or using a procedure, choose the function. Nice functions are ones that compute a value based soley on the parameters they take. They don't rely on any global variables. These are functions that are easily documented. At the other extreme are procedures that use global variables inside their definition and also take in variables and modify them. These procedures are ''dangerous!'' and very hard to document.

There is one last thing for us to discuss. It's a very powerful concept known as "recursion".

==Recursion==

I'd like to start this section off with a quotation:
<pre>To understand recursion, you must first understand recursion.</pre>
A recursive subroutine is a subroutine that calls itself. One of the most famous and basic examples is the factorial function. The factorial function takes in a number and returns the product of that number and the factorial of the number minus one. Also, the factorial of one is defined to be one. This is the recursive definition of the function. It translates very easily into code:
<pre>
function factorial (n : int) : int
if n = 1 then
result 1
else
result n * factorial (n - 1)
end if
end factorial

put factorial (3) % Outputs "6". Note 6 = 3*2*1
put factorial (5) % Outputs "120". Note 120 = 5*4*3*2*1
</pre>
I will give a condensed trace of the factorial function:
<pre>
factorial (5)
(5 * factorial (4))
(5 * (4 * factorial (3)))
(5 * (4 * (3 * factorial (2))))
(5 * (4 * (3 * (2 * factorial (1)))))
(5 * (4 * (3 * (2 * 1))))
(5 * (4 * (3 * 2)))
(5 * (4 * 6))
(5 * 24)
120
</pre>
I've given the recursive definition of the factorial function. A non-recursive definition is to say that factorial (n) = n * (n-1) * (n-2) * ... * 3 * 2 * 1. Once you've learned about '''loops[''', you can code this definition of the factorial function. You can then compare and contrast the two definitions and see which you prefer. I hope you'll prefer this version, but that's for time to decide.

As a segue into the next tutorial (which will be a tutorial on looping constructs), I will now present a recursive procedure that counts down to 1, and then displays, "Blast off!!"
<pre>
procedure countdown (high : int)
if high = 0 then
put "Blast off!!"
else
put high, "..."
countdown (high - 1)
end if
end countdown
</pre>
Calling ''countdown (5)'' produces:
<pre>
5...
4...
3...
2...
1...
Blast off!!
</pre>

'''Question One!''' Create a guessing game. Your program will have a global variable that represents the number the user is trying to guess. Use recursion to write a procedure called ''guess''. When run, ''guess'' prompts the user to input a number. If the guessed number is equal to ''the'' number, a winning message is displayed. Otherwise, the user is told whether his/her guess was too high or too low, and is prompted to guess another number.
A solution to this problem can be found at the end of the tutorial.

'''Question Two!''' Define a function called ''add'' that takes two natural numbers and returns their sum. There's a catch, though. You're not allowed to use the + operator. However, you are allowed to use these two functions that I supply you with:
<pre>
function add1 (n : int) : int
result n + 1
end add1
function sub1 (n : int) : int
result n - 1
end sub1
</pre>
A solution to this problem can be found at the end of the tutorial.

'''Question Three''' Define a function called ''multiply'' that takes two natural numbers and returns their product. Once again, there's a catch. You're not allowed to use the built in * operator. (You are allowed to use the + operator though.) You can, however, use the following two functions that I provide you with:
<pre>
function double (n : int) : int
result n + n
end double

% The halve function performs integer division by 2.
% Examples: halve (8) -> 4
% halve (17) -> 8
function halve (n : int) : int
result floor (n / 2)
end halve
</pre>
Hint: You should use the binary definition of a natural number. That is, a natural number is one of

*1
*2*k where k is a natural number
*2*k + 1 where k is a natural number

That is why I gave you the double and halve functions. It's possible to write a solution using the unary definition of a natural number (sort of like in the solution to problem two), but it will be much slower than the solution using the binary definition.
[size=10]A solution to this problem can be found at the end of the tutorial.[/size]

==Conclusion==

I hope you find these exercises in recursion interesting. At this point, we've learned a small amount of the Turing language, but you see we can do some pretty powerful things using this concept of recursion.

Even if we don't take advantage of recursion, however, the topics covered in this tutorial still give us considerable power. They allow us to organize our code. We can save ourselves from repeating ourselves. We can generalize by using parameters. Indeed, the rather simple idea of factoring out common code has led to powerful advances.

==Solutions==

===Problem One===
<pre>
var the_num := Rand.Int (1, 100)

proc guess
put "Please input a guess: " ..
var g : int
get g
if g = the_num then
put "You've got it!"
elsif g < the_num then
put "You've guessed too low. Try again."
guess
else
put "You've guessed too high. Try again."
guess
end if
end guess

guess
</pre>

===Problem Two===
<pre>
% This function works by increasing n2 by one as we
% decrease n1 by one. If n2 = 0, then we just return n1.
% Essentially, it works on the following identity:
% n1 + n2 = (n1 + 1) + (n2 - 1)
function add (n1, n2 : nat) : nat
if n2 = 0 then
result n1
else
result add (add1 (n1), sub1 (n2))
end if
end add

% Note that this function could be made more efficient if, instead
% of blindly choosing to decrease n2 and increase n1, we chose to
% decrease the smaller of n1 and n2 and increase the larger of n1 and n2.
% Try writing another function that calls this add function in that way.
</pre>

===Problem Three===
<pre>
% This function works by decreasing n2 and increasing n1.
% It works on the following identity:
% If n2 is even: n1 * n2 = double (n1) * halve (n2)
% If n2 is odd: n1 * n2 = n1 + double (n1) * halve (n2)
function multiply (n1, n2 : nat) : nat
if n2 = 1 then
result n1
elsif n2 mod 2 = 0 then % n2 is even
result multiply (double (n1), halve (n2))
else % n2 is odd
result n1 + multiply (double (n1), halve (n2))
end if
end multiply
</pre>

==Credits==
Authour: [[Cervantes]]

Turing Walkthrough

2008-10-12T14:24:23Z

Saad: /* Essentials */

== Essentials ==

* '''The Basics''' - Introduction to programming, commenting, basic output, variables, and basic input ''by Cervantes''
* '''If structures''' - Write code that can make decisions ''by Cervantes''
* '''Functions and Procedures''' - Organize your code into sections and call them at will; introduction to recursion ''by Cervantes''
* '''Loops and For loops''' - To repeat sections of code over and over ''by Cervantes''
* '''[[Turing_String_Manipulation|String Manipulation]]''' ''by Cervantes''
* '''Index''' - searching through a string ''by AsianSensation''
* '''Records and Types''' - Create new, compound data types ''by AsianSensation''
* '''Arrays''' - Mass variables ''by Freakman and Cervantes''
* '''Enumerated Types''' - Create an indexing system that is readable and understandable ''by Freakman''
* '''[[Turing_File_IO|File Input/Output]]''' - Reading and writing data from/to text files ''by Freakman''
* '''Bitwise Operators''' - Experiment with binary, getting closer to lowlevel programming ''by Zylum''
* '''Recursion''' - Subroutines that call themselves can achieve amazing results ''by Zylum''
* '''Modules''' - Collections of procedures and functions ''by Delos''
* '''Pointers''' - Referencing memory and creating linked lists ''by lyam_kaskade''.
* '''Classes Part I''' - Make your own objects ''by Cervantes''
* '''Classes Part II''' - Create objects that interact with each other ''by Cervantes''
* '''Classes Part III''' - Inheritance and Polymorphism to create a network of objects ''by Cervantes''
* '''Functional Programming (in Turing!)''' - Passing and returning anonymous functions ''by Cervantes''

== Extras ==

=== Graphics ===

* '''Basic Graphics''' - Make your program look nice ''by Asok''
* '''Fonts and locating put''' - Make your text look nice ''by basketball4ever''
* '''View.Set and View.Update''' - Configuring the run window and eliminating animation flickering ''by Freakman''
* '''Windows''' - Managing the window(s) your program run(s) in ''by Delos''
* '''Pictures''' - Import your own .bmp's and .jpg's ''by Hacker Dan''
* '''RGB''' - Create your own colours as you need them ''by TheZsterBunny''
* '''Intro to 3D''' - Project a 3D world onto the 2D computer screen ''by Windsurfer''
* '''GUI (Graphical User Interface)''' - Make clickable buttons ''by Recneps''

=== Advanced Input ===

* '''More advanced input''' - getch, Input.KeyDown, Mouse.Where ''by DanShadow''
* '''Input.KeyDown''' - in more detail ''by Tony''
* '''Mouse.Where''' - some more detail ''by Hacker Dan''

=== Other Stuff ===

* '''The Dir Module''' - Traverse and manipulate directories ''by jamonathin''
* '''The Net Module''' - Use Turing and the internet together by ''DanShadow''
* '''Collision Detection''' - Determine when two objects collide--a necessity for games ''by richcash''
* '''Whatdotcolour''' - Another approach to collision detection and other useful things

== Credits ==

Original walkthrough by [[Cervantes]].

Turing String Manipulation

2008-10-12T14:22:46Z

Saad:

IRC channel

2008-08-24T21:18:57Z

Saad: /* IRC Names to CompSci.ca User Names */

[[The]] #compsci.ca channel on IRC is where all the cool members are hanging out. Chances are, if you're not there, you're missing something exciting and important.

To join the CompSci.ca IRC community, you need an [[IRC Client]]. We recommend [[X-Chat]]. Join any of the servers and channels described below.

==Networks==

===CompSci.ca community on AfterNET===

'''Server:''' irc.afternet.org or irc.compsci.ca

'''Main Channel:''' #compsci.ca

'''Self-taught Programming Channel:''' #exile-cafe

==History==
===Of The Main Channel===

Much of #compsci.ca's early history is shrouded in mystery. Nobody is quite sure the exact time when it was created, but rumour has it that [[Coutsos]] was its founder, although he did not begin to regularly attend it until quite some time later. Its first regular inhabitants were [[wtd]] and a mysterious lurker named [[Ultrahex]], who though a member of compsci does not seem to ever post on the forums. Things took off sometime in early 2005, when a wave of members, including [[Hikaru79]], [[Coutsos]], [[Cervantes]], and [[Gandalf]] started regularly attending the channel. At present, #compsci.ca has a regular population of about ten, give or take, although it is subject to occasional flurries of activity, often when the moon is full.

As of April 15th, 2006, #compsci.ca is for [[CompSci.ca]] and programming related discussion. Excessive off topic discussion is to be held elsewhere.

''Please note: The above rule of 'off topic discussion' rarely holds, and don't think you've gotta be a stickler. That doesn't mean you can be a jackass, though. And there often is a lot of programming talk, or otherwise geeky conversations, usually [[wtd]] dispensing out some parcel of [[wtd's infinite wisdom]].

===Of The Self-taught Programming Channel===
This channel was thought of on the [http://www.compsci.ca/v2/viewtopic.php?t=10613 forums] by [[wtd]] on December 14, 2005. The main interest of this new channel is [[Ruby]] and [[O'Caml]]. This channel is not for the people who are taught programming in high school but for the people who self-teach it. When [[wtd]] announced it, there was a great cheer for [[wtd]] since he created the channel for the rest of the users to use and ask questions about. Now that the #cs-self-taught channel has been merged into the #exile-cafe channel, all relevant discussion may proceed there.

===Of The Compsci.ca Chat Channel===
Founded in April 15th, 2006 during the [[Great IRC Crackdown]] of 2006, it was designed to reduce much of the spam going on in the #compsci.ca main room.

This new channel is a place for more relaxed chat, the old is for more [[CompSci.ca]] related discussion and computer science in general. Programming, operating systems, etc., it's all welcome in #compsci.ca. If you are going to spam, please join #compsci.ca-chat. If you spam too much, you will be devoiced and/or kicked.

As of July 2006 this channel's existance has dwindled, and it is no longer used. General discussion may take place in #compsci.ca in a moderated fashion. Spamming and the like are still not tolerated on the main channel.

==Daily Life==

Much of #compsci.ca's time is spent in utter silence (while its members spend time in deep personal reflection and thought), broken periodically by outbursts of conversation, instruction, and weirdness. Hilarity often ensues. Confusion can become rampant when [[the]] mature members take to stealing each other's nicknames (see [[Coutsos Identity Crisis]]). On a good day, [[wtd]] can be observed teaching some interesting, mind-blowing new programming concept.

Ocasionally if you are really lucky you'll witness something as bizzare as [http://www.compsci.ca/wiki/index.php?title=IRC_2006_01_17 this wonderful event], or the short but horrifing [[vibrator incident]].

== IRC Names to CompSci.ca User Names ==
*'''[[wtd]]''' - wtd, Lotho ([http://www.afternet.org/afternet_status/?account=wtd&small=1 Status])
*'''[[Cornflake]]''' - God, md, minor_deity, cornflake, or Thinkpod ([http://www.afternet.org/afternet_status/?account=minor_deity&small=1 Status])
*'''[[Mazer]]''' - [niko|Stukkm] ([http://www.afternet.org/afternet_status/?account=ncout1&small=1 Status])
*'''[[Cervantes]]''' - Cervantes, [[Minsc]], and 100's of other variations that come up ([http://www.afternet.org/afternet_status/?account=cervantes&small=1 Status])*
*'''[[Gandalf]]''' - Gandalf, [Gandalf] ([http://www.afternet.org/afternet_status/?account=gandalf11111&small=1 Status])
*'''[[Hikaru79]]''' - Hikaru79 ([http://www.afternet.org/afternet_status/?account=hikaru79&small=1 Status])*
*'''[[Hacker Dan]]''' - Hacker_Dan, Dan ([http://www.afternet.org/afternet_status/?account=hacker_dan&small=1 Status])*
*'''[[timmytheturtle]]''' - timmy, timmytheturtle, timmythetortoise ([http://www.afternet.org/afternet_status/?account=timmytheturtle&small=1 Status])
*'''[[Amailer]]''' - Amailer ([http://www.afternet.org/afternet_status/?account=amailer&small=1 Status])*
*'''[[TheFerret]]''' - TheFerret, Furo ([http://www.afternet.org/afternet_status/?account=TheFerret&small=1 Status])
*'''[[Martin]]''' - mdkess ([http://www.afternet.org/afternet_status/?account=mdkess&small=1 Status])*
*'''[[rdrake]]''' - rdrake ([http://www.afternet.org/afternet_status/?account=rdrake&small=1 Status])
*'''[[rizzix]]''' - rizzix ([http://www.afternet.org/afternet_status/?account=rizzix&small=1 Status])*
*'''[[apomb]]''' - '''[[Apomb]]''' ([http://www.afternet.org/afternet_status/?account=compwiz333&small=1 Status])*
*'''[[Bored]]''' - Bored, Confused ([http://www.afternet.org/afternet_status/?account=bored&small=1 Status])*
*'''[[Aziz]]''' - Aziz ([http://www.afternet.org/afternet_status/?account=Aziz&small=1 Status])*
*'''[[ZeroPaladn]]''' - ZeroPaladn, ZeroWeapon
*'''[[StealthArcher]]''' - StealthArcher
*'''[[Mackie]]''' - [[Mackie]]
*'''[[Saad]]''' - Saad ([http://www.afternet.org/afternet_status/?account=Saad&small=1 Status])*

*Please update your account= with the proper account name if necessary.

===Statistics===
Statistics based on a combination of logs from many different users is available at [http://theferret.ath.cx/Logs/compsci.ca.html http://theferret.ath.cx/Logs/compsci.ca.html] They are updated daily.

==The Future==

The future for #compsci.ca is looking bright, as it receives more and more attention in the compsci.ca community, particularly through the siggies and evangelism of [[Cervantes]], [[Coutsos]], and [[Hikaru79]]. With any luck, it will soon be as integral a part of the compsci.ca experience as the forum has come to be.

[[Hacker Dan]] has integrated a Java-based IRC client that will send users to the channel directly from the forums. The feature is currently included in the alpha version of [[V3]].

IRC channel

2008-08-24T21:17:48Z

Saad: /* Statistics */

[[The]] #compsci.ca channel on IRC is where all the cool members are hanging out. Chances are, if you're not there, you're missing something exciting and important.

To join the CompSci.ca IRC community, you need an [[IRC Client]]. We recommend [[X-Chat]]. Join any of the servers and channels described below.

==Networks==

===CompSci.ca community on AfterNET===

'''Server:''' irc.afternet.org or irc.compsci.ca

'''Main Channel:''' #compsci.ca

'''Self-taught Programming Channel:''' #exile-cafe

==History==
===Of The Main Channel===

Much of #compsci.ca's early history is shrouded in mystery. Nobody is quite sure the exact time when it was created, but rumour has it that [[Coutsos]] was its founder, although he did not begin to regularly attend it until quite some time later. Its first regular inhabitants were [[wtd]] and a mysterious lurker named [[Ultrahex]], who though a member of compsci does not seem to ever post on the forums. Things took off sometime in early 2005, when a wave of members, including [[Hikaru79]], [[Coutsos]], [[Cervantes]], and [[Gandalf]] started regularly attending the channel. At present, #compsci.ca has a regular population of about ten, give or take, although it is subject to occasional flurries of activity, often when the moon is full.

As of April 15th, 2006, #compsci.ca is for [[CompSci.ca]] and programming related discussion. Excessive off topic discussion is to be held elsewhere.

''Please note: The above rule of 'off topic discussion' rarely holds, and don't think you've gotta be a stickler. That doesn't mean you can be a jackass, though. And there often is a lot of programming talk, or otherwise geeky conversations, usually [[wtd]] dispensing out some parcel of [[wtd's infinite wisdom]].

===Of The Self-taught Programming Channel===
This channel was thought of on the [http://www.compsci.ca/v2/viewtopic.php?t=10613 forums] by [[wtd]] on December 14, 2005. The main interest of this new channel is [[Ruby]] and [[O'Caml]]. This channel is not for the people who are taught programming in high school but for the people who self-teach it. When [[wtd]] announced it, there was a great cheer for [[wtd]] since he created the channel for the rest of the users to use and ask questions about. Now that the #cs-self-taught channel has been merged into the #exile-cafe channel, all relevant discussion may proceed there.

===Of The Compsci.ca Chat Channel===
Founded in April 15th, 2006 during the [[Great IRC Crackdown]] of 2006, it was designed to reduce much of the spam going on in the #compsci.ca main room.

This new channel is a place for more relaxed chat, the old is for more [[CompSci.ca]] related discussion and computer science in general. Programming, operating systems, etc., it's all welcome in #compsci.ca. If you are going to spam, please join #compsci.ca-chat. If you spam too much, you will be devoiced and/or kicked.

As of July 2006 this channel's existance has dwindled, and it is no longer used. General discussion may take place in #compsci.ca in a moderated fashion. Spamming and the like are still not tolerated on the main channel.

==Daily Life==

Much of #compsci.ca's time is spent in utter silence (while its members spend time in deep personal reflection and thought), broken periodically by outbursts of conversation, instruction, and weirdness. Hilarity often ensues. Confusion can become rampant when [[the]] mature members take to stealing each other's nicknames (see [[Coutsos Identity Crisis]]). On a good day, [[wtd]] can be observed teaching some interesting, mind-blowing new programming concept.

Ocasionally if you are really lucky you'll witness something as bizzare as [http://www.compsci.ca/wiki/index.php?title=IRC_2006_01_17 this wonderful event], or the short but horrifing [[vibrator incident]].

== IRC Names to CompSci.ca User Names ==
*'''[[wtd]]''' - wtd, Lotho ([http://www.afternet.org/afternet_status/?account=wtd&small=1 Status])
*'''[[Cornflake]]''' - God, md, minor_deity, cornflake, or Thinkpod ([http://www.afternet.org/afternet_status/?account=minor_deity&small=1 Status])
*'''[[Mazer]]''' - [niko|Stukkm] ([http://www.afternet.org/afternet_status/?account=ncout1&small=1 Status])
*'''[[Cervantes]]''' - Cervantes, [[Minsc]], and 100's of other variations that come up ([http://www.afternet.org/afternet_status/?account=cervantes&small=1 Status])*
*'''[[Gandalf]]''' - Gandalf, [Gandalf] ([http://www.afternet.org/afternet_status/?account=gandalf11111&small=1 Status])
*'''[[Hikaru79]]''' - Hikaru79 ([http://www.afternet.org/afternet_status/?account=hikaru79&small=1 Status])*
*'''[[Hacker Dan]]''' - Hacker_Dan, Dan ([http://www.afternet.org/afternet_status/?account=hacker_dan&small=1 Status])*
*'''[[timmytheturtle]]''' - timmy, timmytheturtle, timmythetortoise ([http://www.afternet.org/afternet_status/?account=timmytheturtle&small=1 Status])
*'''[[Amailer]]''' - Amailer ([http://www.afternet.org/afternet_status/?account=amailer&small=1 Status])*
*'''[[TheFerret]]''' - TheFerret, Furo ([http://www.afternet.org/afternet_status/?account=TheFerret&small=1 Status])
*'''[[Martin]]''' - mdkess ([http://www.afternet.org/afternet_status/?account=mdkess&small=1 Status])*
*'''[[rdrake]]''' - rdrake ([http://www.afternet.org/afternet_status/?account=rdrake&small=1 Status])
*'''[[rizzix]]''' - rizzix ([http://www.afternet.org/afternet_status/?account=rizzix&small=1 Status])*
*'''[[apomb]]''' - '''[[Apomb]]''' ([http://www.afternet.org/afternet_status/?account=compwiz333&small=1 Status])*
*'''[[Bored]]''' - Bored, Confused ([http://www.afternet.org/afternet_status/?account=bored&small=1 Status])*
*'''[[Aziz]]''' - Aziz ([http://www.afternet.org/afternet_status/?account=Aziz&small=1 Status])*
*'''[[ZeroPaladn]]''' - ZeroPaladn, ZeroWeapon
*'''[[StealthArcher]]''' - StealthArcher
*'''[[Mackie]]''' - [[Mackie]]

*Please update your account= with the proper account name if necessary.

===Statistics===
Statistics based on a combination of logs from many different users is available at [http://theferret.ath.cx/Logs/compsci.ca.html http://theferret.ath.cx/Logs/compsci.ca.html] They are updated daily.

==The Future==

The future for #compsci.ca is looking bright, as it receives more and more attention in the compsci.ca community, particularly through the siggies and evangelism of [[Cervantes]], [[Coutsos]], and [[Hikaru79]]. With any luck, it will soon be as integral a part of the compsci.ca experience as the forum has come to be.

[[Hacker Dan]] has integrated a Java-based IRC client that will send users to the channel directly from the forums. The feature is currently included in the alpha version of [[V3]].