Amazing Job! thankx for all ur help! now i will surely get gud marks in my cs exam
Computer Science Canada Functions and Procedures |
| Author: | Cervantes [ Sun Dec 31, 2006 1:33 am ] | ||||||||||||||||||||||||||||||||||||||||||||
| Post subject: | 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:
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:
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:
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:
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.
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:
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:
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?
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:
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:
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:
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:
We can do the same with parameters:
Now, I'll give another trivial example. This one will involve writing a procedure that takes two numbers and outputs their product.
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.
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.
Then we could use that elsewhere:
Or perhaps better yet:
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:
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:
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.
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. |
|||||||||||||||||||||||||||||||||||||||||||||
| Author: | Cervantes [ Sun Dec 31, 2006 1:35 am ] | ||||||||||||||||||||||
| Post subject: | |||||||||||||||||||||||
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:
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:
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:
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.
So my_randint isn't really random, but it might fool you. Take a look at some sample data:
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:
I will give a condensed trace of the factorial function:
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!!"
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:
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:
Hint: You should use the binary definition of a natural number. That is, a natural number is one of 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! |
|||||||||||||||||||||||
| Author: | Clayton [ Mon Jan 01, 2007 2:56 pm ] | ||||
| Post subject: | |||||
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:
Instead you have to return an array of a known size, so the following will work:
Untested... |
|||||
| Author: | Cervantes [ Mon Jan 01, 2007 3:43 pm ] |
| Post subject: | |
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. |
|
| Author: | Clayton [ Mon Jan 01, 2007 5:01 pm ] |
| Post subject: | |
perhaps the arrays tutorial then? |
|
| Author: | Cervantes [ Mon Jan 01, 2007 5:20 pm ] |
| Post subject: | |
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. |
|
| Author: | stargurl14 [ Fri Jan 26, 2007 11:55 am ] |
| Post subject: | RE:Functions and Procedures |
Amazing Job! thankx for all ur help! now i will surely get gud marks in my cs exam |
|
| Author: | riveryu [ Mon Feb 11, 2008 10:15 pm ] |
| Post subject: | RE:Functions and Procedures |
"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)? |
|
| Author: | Saad [ Sun Oct 12, 2008 2:32 pm ] |
| Post subject: | RE:Functions and Procedures |
Added to Wiki |
|
| Author: | Rampragash [ Sat Jan 16, 2010 9:48 am ] |
| Post subject: | RE:Functions and Procedures |
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? |
|
| Author: | iii [ Sun Jan 17, 2010 12:26 am ] |
| Post subject: | RE:Functions and Procedures |
You use body procedures. |
|
| Author: | Mauser [ Tue Mar 09, 2010 10:42 pm ] |
| Post subject: | RE:Functions and Procedures |
Thanks for the quick lesson. |
|
| Author: | atal [ Tue Jul 19, 2011 12:30 pm ] | ||
| Post subject: | Re: Functions and Procedures | ||
hi i got a question for this part:
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 |
|||
| Author: | Tony [ Tue Jul 19, 2011 12:42 pm ] | ||||
| Post subject: | RE:Functions and Procedures | ||||
The string value of "George" from
gets mapped to the function's signature in
and creates a local variable named "name", assigning it the value used in the function call (so "George"). |
|||||
| Author: | atal [ Wed Jul 20, 2011 1:10 pm ] | ||||
| Post subject: | Re: RE:Functions and Procedures | ||||
Tony @ Tue Jul 19, 2011 12:42 pm wrote: The string value of "George" from
gets mapped to the function's signature in
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 |
|||||
| Author: | 2goto1 [ Wed Jul 20, 2011 3:40 pm ] |
| Post subject: | RE:Functions and Procedures |
name : string is a variable. It's akin to a virtual wallet. If you greet("George"), you're filling your name wallet with the value "George". So when you put "Hello", name, Turing opens the name wallet and voila, the name George is inside. |
|
| Author: | IamPillzbury [ Mon Apr 20, 2015 10:26 am ] |
| Post subject: | RE:Functions and Procedures |
Is there a certain command to exit the procedure? I have a procedure that prints out some text and I want it to exit the procedure when a certain button is pressed |
|
| Author: | Insectoid [ Mon Apr 20, 2015 11:25 am ] |
| Post subject: | RE:Functions and Procedures |
A procedure is just like your main program (sort of). How do you make a program end? You just run out of code to run. When there's no more code, the program ends. Same deal with procedures. When there's no more code to run in it, it ends. Remember that when inside a procedure, no code outside the procedure will run. This means your button code has to be inside the procedure as well as the text. |
|