Turing Functions and Procedures

From Compsci.ca Wiki

Revision as of 19:35, 12 October 2008 (view source) Saad (Talk | contribs) ← Older edit		Latest revision as of 20:25, 12 October 2008 (view source) Saad (Talk | contribs) (→Functions and Procedures)
(3 intermediate revisions not shown)
Line 1:		Line 1:
-	==Functions and Procedures==	+
	==Introduction==		==Introduction==
Line 462:		Line 462:
	==Credits==		==Credits==
	Authour: [[Cervantes]]		Authour: [[Cervantes]]
		+
	Added by: [[Saad]]		Added by: [[Saad]]

---

Latest revision as of 20:25, 12 October 2008

Contents 1 Introduction 2 Introducing the Procedure 3 Procedures with Parameters 4 Procedures with Multiple Parameters 5 Introducing Functions 6 A Closer Look at 'result' 7 Variable Parameters 8 Functions vs. Procedures 9 Recursion 10 Conclusion 11 Solutions 11.1 Problem One 11.2 Problem Two 11.3 Problem Three 12 Credits

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:

% Define the greet procedure
procedure greet
    put "Hello world!"
end greet

% Call the greet procedure
greet

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:

% Define the greet procedure
procedure greet
    put "Hello world!"
end greet

% Call the greet procedure
put "Hello world!"

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:

procedure greet
    put "Hello George!"
end greet

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:

var name : string
procedure greet
    put "Hello ", name, "!"
end greet

name := "George"
greet

name := "Phil"
greet

name := "Anthony"
greet

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.

procedure greet (name : string)
    put "Hello ", name, "!"
end greet

greet ("George")
greet ("Phil")
greet ("Anthony")

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:

greet ("George")

put "Hello ", "George", "!"

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:

procedure greet (name : string)
    put "Hello ", name, "!"
    name := "Freddy"
    put "And hello to ", name, " as well!"
end greet

greet ("George")

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?

procedure greet (name : string)
    put "Hello ", name, "!"
    name := "Freddy"
    put "And hello to ", name, " as well!"
end greet

var person : string := "George"
greet (person)

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:

procedure greet (name : string)
    put "Hello ", name, "!"
end greet

greet ("George")
put name

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:

procedure introduce (person1 : string, person2 : string)
    put person1, ", this is ", person2, "."
    put person2, ", meet ", person1, "."
end introduce

% Call the procedure
introduce ("Jackie", "Bruce")

The output of this program will be:

Jackie, this is Bruce.
Bruce, meet Jackie.

However, reversing the order of the names results in a different output:

introduce ("Bruce", "Jackie")

Bruce, this is Jackie.
Jackie, meet Bruce.

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:

var name1, name2 : string

We can do the same with parameters:

procedure introduce (person1, person2 : string)
    %...
end introduce

Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.

procedure put_product (num1, num2 : real)
    put num1 * num2
end put_product

put_product (4, 6)  % Outputs 24

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.

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

put product (4, 6)  % outputs 24

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.

var n : real := product (1.5, 3)   % n := 4.5

Then we could use that elsewhere:

put product (n, 2)   % outputs 9

Or perhaps better yet:

put product (product 1.5, 3) 2)   % outputs 9

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:

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)

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:

procedure greet (name : string)
    put "Hello ", name, "!"
end greet

greet ("George")

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.

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

Hello George!
And hello to Freddy as well!
After calling greet, the value of person is now Freddy

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:

var n : int
n := Rand.Int (4, 11)

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:

var n : int
randint (n, 4, 11)

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:

squeeze (Rand.Int (1, 6))

var n : int
randint (n, 1, 6)
squeeze (n)

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.

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

So my_randint isn't really random, but it might fool you. Take a look at some sample data:

% 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

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:

To understand recursion, you must first understand recursion.

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:

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

I will give a condensed trace of the factorial function:

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

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!!"

procedure countdown (high : int)
    if high = 0 then
        put "Blast off!!"
    else
        put high, "..."
        countdown (high - 1)
    end if
end countdown

Calling countdown (5) produces:

5...
4...
3...
2...
1...
Blast off!!

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:

function add1 (n : int) : int
    result n + 1
end add1
function sub1 (n : int) : int
    result n - 1
end sub1

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:

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

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

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

Problem Two

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

Problem Three

% 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

Credits

Authour: Cervantes

Added by: Saad