Functions and Procedures

[Cervantes]

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:


code:

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


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:


code:

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:


code:

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.


code:

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:


code:

greet ("George")




code:

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:


code:

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?


code:

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. Recall the lesson on expressions from the last tutorial (on if statements). 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:


code:

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:


code:

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:

Output wrote:

Jackie, this is Bruce.
Bruce, meet Jackie.


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


code:

introduce ("Bruce", "Jackie")



Output wrote:

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:


code:

var name1, name2 : string


We can do the same with parameters:


code:

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.


code:

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.



code:

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.


code:

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


Then we could use that elsewhere:


code:

put product (n, 2)   % outputs 9


Or perhaps better yet:


code:

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:


code:

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:


code:

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.


code:

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



Output wrote:

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.

[Cervantes]

Functions vs. Procedures
Fight!

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:


code:

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:


code:

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:


code:

squeeze (Rand.Int (1, 6))




code:

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.


code:

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:


code:

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

Quote:
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:


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:


code:

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


code:

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:

Output of countdown (5) wrote:

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:


code:

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:


code:

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.

When you're ready (I highly suggest you attempt the exercises), move on to learn about loops and for loops. Onwards and upwards!

Solutions

Highlight to see the solution.

Problem One wrote:


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 wrote:


% 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 wrote:


% 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

_________________
mmmgoodness!

[Clayton]

good stuff Cervantes, perhaps you should introduce arrays as arguments and results as well. For example a sorting procedure that takes in an array and sorts it based on ascending or desceding order. Of course this would better suit a function, but you can't return arrays of an unknown size, eg. the following is illegal and will cause an error when run:

code:

fcn foo : array 1 .. * of int     var bar : array 1 .. 2 of int := init (1, 2)     return bar end foo

Instead you have to return an array of a known size, so the following will work:

code:

fcn baz : array 1 .. 2 of int     var qux : array 1 .. 2 of int     return qux end baz

Untested...

[Cervantes]

Freakman wrote:

perhaps you should introduce arrays as arguments and results as well.

That's definitely a topic that should be talked about at some point. However, I don't think this tutorial is the place for it. The reason being that at this point in the Turing Walkthrough, arrays haven't been covered. This tutorial comes just after if statements and just before loops.

[Clayton]

perhaps the arrays tutorial then?

[Cervantes]

Sure. I wouldn't go too far out of your way to explain it though. Work it into an example. Giving an example of sorting is definitely something that should be done. Doing it with a sorting procedure (yeah, it would have to mutate the value you give it--just gotta live with it) is even better.

[stargurl14]

Amazing Job! thankx for all ur help! now i will surely get gud marks in my cs exam

[riveryu]

"To understand recursion, you must first understand recursion."
This quote parallels the philosophy in which i live to. (jk)

Nice tutorial, good structure, very understandable.

However:
-question 3 needs to be more specific i think. When read the question, I thought it meant it was intended for me to only use procedures for the whole thing.. ex. randint instead of Rand.Int which made it seemingly impossible.
- isnt "div 2" the same as floor (n/2)?

[Saad]

Added to Wiki

[Rampragash]

hey, nice lesson!

ummm, i hav a questions though, how would u make procedures within procedures and if that is not possible, what can i do?

[iii]

You use body procedures.

[Mauser]

Thanks for the quick lesson.

[atal]

hi i got a question for this part:

code:

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

how does turing know that george, phil, and antony are names and to substitute them in the name part (were u put put "hello" , name,)? thanks in advance

[Tony]

The string value of "George" from

code:

greet ("George")

gets mapped to the function's signature in

code:

procedure greet (name : string)

and creates a local variable named "name", assigning it the value used in the function call (so "George").

[atal]

Tony @ Tue Jul 19, 2011 12:42 pm wrote:

The string value of "George" from

code:

greet ("George")

gets mapped to the function's signature in

code:

procedure greet (name : string)

and creates a local variable named "name", assigning it the value used in the function call (so "George").

ok... Still kind of sketchy on that one but i'll get it. thanks