[Tutorial] Introduction -> Pointers -> Part 1

[Jerrik]

Pointers Part 1 - In Turing

Welcome to my tutorial on Pointers, Part 1 (of a possible 4). If you see any errors, whether its typo's, syntax, or an incorrect way of doing something please check the replies of the thread before submitting it. There is a chance that someone has already...*ahem*...pointed it out. Submit corrections as a reply not as a PM (that way I don't get a dozen corrections for the same mistake). This is my first tutorial, and I will go through it a half dozen times after I submit it (not right away, I'll give it a day or so before I do) to read it over and make sure it makes sense. If you don't understand something, please post on what it was and I will either adjust the tutorial accordingly, or simply clarify it for you. For a lot of people its hard to get their mind around pointers; just take it slow and mess around with the code until you get it.

To continue any further, I suggest you are well versed in the following topics; (Click to be taken to tutorials on the subjects)
Records [1]

Purpose: This guide is meant to teach anyone who is unfamiliar with Turing pointers, or pointers in general, how they work, as well as some useful features of pointers (which will be explained in detail in part 2). It will contain a lot more on theory then actual coding, as the code I find is simple after you get passed the beggining.

I have only been using Pointers for a few days as of me writing this tutorial, so everything is based on what I have learned through trial and error. Not everything will be 100% accurate, but it should be close to whats actually happening. Mostly speculation and extrapolation...Well the key is that you will know pointers if you read this either way; even if the knowledge is warped over how or why something works.

What are pointers and why are they useful?
Pointers are things that metaphorically point to different things. They don't literally hold out a finger and say "The values are over there!", but they do reference where values are. If you have ever done sorting algorithms where you swapped values you will find that sorting with pointers to be faster (in most cases). Especially if you are sorting records. If you sort pointers that reference records your are swapping one value in the memory, not a whole bunch of values.

I'll clarify.

When you have two pointers, a and b, and you swap them the values that a and b are pointing to do not change. The only thing that changes is the references, a and b. If you have this record;

Turing:

type personData :     record         name : string         age : int         phoneNumber : string         houseNumber : int         streetNames : array 1 .. 2 of string         nofChildren : int         ChildrenNames : array 1 .. 30 of             record                 age : int                 name : string             end record     end record var a, b : personData

a and b are variables in this instance, not records. If you were to swap a and b;

code:

var a, b, c : personData c := a a := b b := c

You would be replacing all the values in those three variable records (a, b, and c) of personData. In other words, you are swapping each value of name, age, phoneNumber, etc...If it were to be done with pointers (don't worry about the code, I will explain it later) you would only be swapping the references;

Turing:

var personData : collection of     record         name : string         age : int         phoneNumber : string         houseNumber : int         streetNames : array 1 .. 2 of string         nofChildren : int         ChildrenNames : array 1 .. 30 of             record                 age : int                 name : string             end record     end record var a, b, c : pointer to personData new a new b c := a a := b b := c

In the case of pointers you do not change name or age or the rest of the variables. The only thing that changes is the references to them.

Lets say you line up three of your friends. They each have a name, a height, a weight, etc...Now give them each a number from 1 to 3. If you call out 1, person 1 would read out his/her information on the card; name, and age, etc.. We will call your three friends Fred, George, and Lizwappet (1, 2, and 3). So you say "one", and Fred steps forward and gives you the information on his card. If you said three, miss Lizwappet would step forward, and give her information like Fred did. Now lets say you want to swap Lizwappet's and George's cards (3 and 2). With variables George would have to write down all of Lizwappet's information, and Lizwappet would have to write all of Georges information.

With pointers, instead of holding their own cards, the cards are on a wall. Fred, George, and Lizwappet only have to remember the card number. So if you called George, he would goto card 2 and read off the information. If you swapped Fred and George, when you called George he would read card 1 (Freds old number) and Fred would read card 2 (Georges old number).

Instead of rewriting the information, they learn where the information is. If you want to change the information on any of the cards, you simply have to know where the card is, and change the information. "George, change the name on your card!", and he will change it to whatever you want it to be.

So pointers are typically faster to deal with. Lets take apart some of the code though;

code:

var personData : collection of

You are making a variable of a record. This variable doesn't technically exist until you make it later on (using new, as I will explain later). You are simply saying "This is a variable template of variables". In that sense it is very similar to typed-records. However, unlike typed-records, you cannot make an instance of this in a variable. It is itself a variable. With TR's (typed-record). In other words you cannot have;

Turing:

var personData : collection of     record         ...variables..     end record     var a : personData

So if you cannot make a variable that is a personData type, whats the use? How can we harness the awesome power? I will explain.

You will notice in the first example the following code (modified);

code:

var a : pointer to personData new a

On the first line we create a variable 'a', which is a pointer. It points to personData. That mean it can point to any variable we create of personData. In that sense, the pointer a is not pointing to personData, but an instance of personData.
The second line creates an instance of personData and stores the location in 'a', the pointer. "new a" is the short version of "new personData, a". In Turing we are allowed to shorten it. The variable 'a' can only point to personData, so its redundent to say "create a new instance of personData, and store it in 'a' ". We can just say "Create a new instance of what a points to, and store it in 'a' ".

You can't just create a new instance of personData. If you did, you'd never be able to access it, since you have no idea 'where' it is. Thats why a new one has to be created with something that will point to it. If you had;

code:

new a new a

You would have created two instances of personData, but you would lose the first reference. Both still exist, but you only have the reference of the one. Just something to keep in mind.

Alright, so we have created a collection of information, and we have created a pointer, and then we created an instance of our collection, and we stored it in our pointer variable. What now? How do you declare information? How do we use this?

Turing:

var personData : collection of     record         name : string         age : int         phoneNumber : string         houseNumber : int         streetNames : array 1 .. 2 of string         nofChildren : int         ChildrenNames : array 1 .. 30 of             record                 age : int                 name : string             end record     end record var a : pointer to personData new a % ***END OLD INFO** % a -> name := "Fred" put a -> name personData (a).name := "Geogre" put personData (a).name

What you see is the same thing in two different ways. First of all;

code:

personData (a).name := "Geogre" put personData (a).name

To declare and call the name as Fred in personData, in the location of 'a' we have this code.

If you think of personData as an unbounded array (ie, without the "1..10" part) then 'a' is first location (if we called new again, it would be the next location). So we call that location by having the code: personData (a). What we do with that is just like a regular record stored in a variable (similar in syntax anyways). As you can see in the example, its pretty straight forward.

CollectionName (pointerVariable).variableInCollection

We also have a second way of doing the exact same thing as seen above;

code:

a -> name := "Geogre" put a -> name

We are saying "Look wherever 'a' is pointing, put "George" in the name variable". 'a' is a pointer to personData, so again its redundant to clarify that. This makes it a LOT simpilar, especially when you get into multidimensional linked lists (Linked lists are pointers that reference themselves. So inside person data you would have a variable that that is variableName : pointer to personData).

I would also like to note at this point, that you don't have to say "pointer to" every single time you create a pointer. You can just use the "^" symbol called the Karot. For instance;

code:

var a : pointer to personData

becomes

code:

var a : ^personData

Its the exact same thing, just different syntax.

That is pointers. You can now call and use pointers, you must be excited. There is however, a lot more to learn. There is so much you can do with them. You can have arrayed pointers. You can have pointers that point to objects and class's.

This is part 1. As of now it has several hours of work put into it, but I have NOT gone through it to look for spelling errors, typos, syntax errors, etc...I will, but not now.

Part 2 will have the following code explored and explained in detail. For now, you just get to look at it and figure it out for yourself;

Code:1

Turing:

var tree : collection of     record         n : int         link : ^tree     end record var root : ^tree new root var tRoot : ^tree := root root -> n := 1 for i : 1 .. 100     new tRoot -> link     tRoot := tRoot -> link     tRoot -> n := i end for tRoot -> link := root loop     put tRoot -> n     tRoot := tRoot -> link     if hasch then         delay (100)         Input.Flush         Input.Pause     end if end loop

Code:2

Turing:

type personData :     record         name : string         age : int         nofChildren : int     end record var tree : collection of     record         Person : personData         Children : array 1 .. 10 of ^tree         Parent : ^tree     end record var root : ^tree new root root -> Person.name := "Fred" root -> Person.age := 95 root -> Parent := root procedure newChildren (var tRoot : ^tree, peeps : array 1 .. * of personData)     tRoot -> Person.nofChildren := upper (peeps)     for i : 1 .. min (tRoot -> Person.nofChildren, 10)         new tRoot -> Children (i)         tRoot -> Children (i) -> Person := peeps (i)         tRoot -> Children (i) -> Person.nofChildren := 0         tRoot -> Children (i) -> Parent := tRoot     end for end newChildren procedure displayFamily (Root : ^tree, n : int)     color (black)     put repeat (" ", n * 4), "-", Root -> Person.name, "(", Root -> Person.age, ") " ..     if Root -> Parent -> Person.name ~= Root -> Person.name then         color (brightred)         put "Parent[", Root -> Parent -> Person.name, "]"     else         put ""     end if     for i : 1 .. Root -> Person.nofChildren         displayFamily (Root -> Children (i), n + 1)     end for end displayFamily var names1 : array 1 .. 3 of personData names1 (1).name := "Josheph" names1 (1).age := 64 names1 (2).name := "Sarah" names1 (2).age := 62 names1 (3).name := "Samantha" names1 (3).age := 67 var names2 : array 1 .. 2 of personData names2 (1).name := "Jarid" names2 (1).age := 34 names2 (2).name := "Billy" names2 (2).age := 36 % names2 (3).name := "Booolna" % names2 (3).age := 38 newChildren (root, names1) newChildren (root -> Children (2), names2) displayFamily (root, 0)

[Jerrik]

*Placeholder for links to other pages*

Does anyone know why the text gets smaller at a certain point? I couldn't find code in the post that was responsible (size=#), but it appears to start right after the second syntax=turing. I thought it might have had something to do with how syntax formats, but it didn't do that after the first one.

I am at a loss, if anyone knows I would really appreciate that knowledge.

[Cervantes]

Don't worry about the font size. It's a bug that will get fixed at some point. You're right: it does have to do with the syntax tagging.

Thanks for taking the time to write a tutorial on this topic! We don't really have a good tutorial on pointers. We've got one that jumps pretty quickly into Linked Lists, but that's about it. That said, there is a lot of work that could be done here, but it's still pretty good. And you say that you're going to go over it again. I hope that when you've gone over it for the last time and are content with it, you will remove the comments about going over it and such. Also, I would have liked to see a more technical description of what pointers do: basically, they are integers that are interpreted as representing a certain address in memory (RAM). They also contain information to tell us what kind of data is stored in memory at their address. With this information one can go and look at that address in memory and extract the value, and interpret the data there as data of the type determined by the pointer.

[Jerrik]

Cervantes @ Sun Jun 10, 2007 7:04 am wrote:

Don't worry about the font size. It's a bug that will get fixed at some point. You're right: it does have to do with the syntax tagging.

Thanks for taking the time to write a tutorial on this topic! We don't really have a good tutorial on pointers. We've got one that jumps pretty quickly into Linked Lists, but that's about it. That said, there is a lot of work that could be done here, but it's still pretty good. And you say that you're going to go over it again. I hope that when you've gone over it for the last time and are content with it, you will remove the comments about going over it and such. Also, I would have liked to see a more technical description of what pointers do: basically, they are integers that are interpreted as representing a certain address in memory (RAM). They also contain information to tell us what kind of data is stored in memory at their address. With this information one can go and look at that address in memory and extract the value, and interpret the data there as data of the type determined by the pointer.

Excellent, thank you very much (for the nice comments, and suggestions). I will be going over this thoroughly after exams next week, and I'll make sure to add in the technical information as well as I go through.

A quick question for the technical end though, pointers are 8-byte integers rather then 4-byte (largest available) integers right?

[CodeMonkey2000]

Finally, a good tutorial on pointers. I already taught my self about pointers in pascal a while ago and got confused with linked lists, but this really clarifies it for me, thanks

+karma

[Dan]

This is a great intro to pointers in truing. The documentation for pointers in truing is lacking and i have seen very few uses of them. It is an very useful topic to Computer Science that is under looked in most high schools.

+150 bits and +karma

[Clayton]

I'm going to throw in a few more bits because I myself have not looked into pointers for a long time in Turing, and this was a nice refresher for me. Well done!

bits++ !