Fog Creek Software
Discussion Board




Purpose of a pointer?

Am I correct in saying that the purpose of a pointer is to prevent the duplication of data in memory?

Dave B.
Monday, July 28, 2003

A pointer simply holds the address of a memory location.  What you do with it is your business ;-) 


Monday, July 28, 2003

Basicly, yes.

Pointers also let you re-define what the data means and how you can access it if you cast it to a different data type.  A simple example is to take a pointer to a 32-bit word and cast it as a pointer to an array of 4 bytes. This allows you to change a byte in that value without multiple bit shifts, bit-wise AND/OR/XOR, and assignment operations.

JbR
Monday, July 28, 2003

Never heard that one before.

Purpose of a pointer is to be able to access (and possibly create/modify) data through a memory address.

Another purpose would be when you want to modify a big structure and you pass an pointer to it so that the called function can change it (pass by reference)

Yet another purpose would be to pass it to a function when passing the whole structure would be expensive in terms of time and space required for copying it

Finally I guess the purpose is for the C/C++ programmers who understand pointers to be able to be paid more than VB programmers :-)

Non-Microsoft Bob
Monday, July 28, 2003

No, not even close.

A pointer is the address of a location in memory.

You use a literal address when you need direct access to the underlying hardware.

You use a memory address as a "pointer" to make logical conections between structures or objects. For example to create a linked list or a tree.

You pass a "pointer" to a subroutine when you want that routine to modify the original value instead of a temporary copy of that value. That is to perform a "call by reference" rather than a "call by value".

Anonymous Coward
Monday, July 28, 2003

There is one thing that wouldn't be possible without pointers/references of some sort: circular data structures.  Whether you have a circular list, or simple two structures that refer to each other, it wouldn't work if you couldn't refer to another structure in some way.

On a side note, you have to be careful using that array of bytes trick to make sure you access the appropriate entry according to the endianness of your system.

Mike McNertney
Monday, July 28, 2003

Anonymous Coward,

Though "preventing duplication of data" is not what you would think of as a pointer's main purpose, it is not a stretch to see why someone would think this, if you really understand pointers.

If you have a bunch of structs or objects, you can relate them by containment, either by value or by reference.  Doing it by value can lead to duplicated data.

Example: You have a list of people and their addresses.  It's not uncommon that the "person" struct would just contain an address string by value.  However, if you're storing a list of people in the entire state, it would make more sense to store them by reference, since many people live at a single address.  No need to repeat that single address for all 5 people that live there.  You would save a lot of space this way.

Andy
Monday, July 28, 2003

A better, more general purpose is indirection. Understand and recognize that concept, both inside and outside programming, and you'll be much better off.

Steven E. Harris
Monday, July 28, 2003

Agreed about indirection.  It might help to realize that when you use pointers you are creating a graph of objects in memory.  Although you might not know what a graph is if you don't know pointers.

Andy
Monday, July 28, 2003

What does a "graph of objects" mean? "Graph", much like "refactor" or "pattern", is a word that I've noticed has suddenly become extremely popular, and I think I missed that edition of "Hip Lingo Monthly". I am honestly curious what the meaning is in this context.

I always thought a graph was a visual representation of points.

Dennis Forbes
Monday, July 28, 2003

Graph has two meanings here, one business, one mathematical. The former is, as you suggest, a visualization of certain data. The latter is essentially a network; a collection of nodes (vertices) and the edges which connect them.

Devil's Advocate
Monday, July 28, 2003

> I always thought a graph was a
> visual representation of points.

It is, and a tree is just some branching plant that grows out of the ground. But then there are data structures. A graph is an abstraction or data structure consisting of vertices and connecting edges. Trees are a limited subset of graphs.

To learn more, see, for example, the Boost Graph Library's "Review of Elementary Graph Theory":

http://www.boost.org/libs/graph/doc/graph_theory_review.html

Steven E. Harris
Monday, July 28, 2003

"What does a "graph of objects" mean? "Graph", much like "refactor" or "pattern", is a word that I've noticed has suddenly become extremely popular, and I think I missed that edition of "Hip Lingo Monthly". I am honestly curious what the meaning is in this context."

Actually Graph is a very popular word in CS form a few dozen years =)

The poster above already said what it is, I add that many problems in CS are solved by considering the data as a graph (nodes connected with vertices). For instance, knowing the smallest route to take between two cities is modeled as the smallest distance between two nodes in a graph.

whatever
Monday, July 28, 2003

"Actually Graph is a very popular word in CS *for* a few dozen years =)"

Note to self: remember to re-read before posting... =)

whatever
Monday, July 28, 2003

Philo's "Teach pointers in five minutes":

Imagine you had ten bookcases full of books. Each book has an index number - know the number, you can walk right to the book.

But what if you want to find a specific title, or author? What if your friend down the street asks what books you have, or wants a list of every book starting with "A"?

Instead of taking the books off the shelves and shuffling them around to sort them, leave them there. Instead create a card catalog - each card refers to a book - it has author, title, and index number. You can sort the *cards* by author or title, or pull the ones that start with "A" and send them to your friend. When he finds the book he wants, he calls you and asks for book number 'x'.

The cards are pointers. The books are data. The index numbers are memory addresses.

Philo

Philo
Monday, July 28, 2003

What are cards again? <g>

...
Monday, July 28, 2003

So, to conclude, the word "graph" has absolutely no practical value whatsoever when referring to data structures. Basically it means nothing. I am not arguing about the etymology of the word, or whether it exists in a textbook somewhere to vaguely wax poetic when one really isn't sure what they're describing, however words like "linked-list", "b-tree", "adjacency-list", "pointer array" are practical, concrete ideas. Graph means "something to do with things that relate in some undefined way".

Did I get that correctly? Cue up the pedantry.

Dennis Forbes
Monday, July 28, 2003

> Did I get that correctly?

No, not even close.

> Cue up the pedantry.

You're trolling when you should be studying.

Steven E. Harris
Monday, July 28, 2003

Well, I am a kindly hearted man so I will answer your post in the spirit it isn't a plain troll.

Since you don't fell like searching the net, lets explain quickly: '(1) what is a graph? and (2) why do I bother?'

(1) Is not that hard: graphs are nodes connected by vertices. But I guess you didn't get it: a linked-list *IS* a graph. A binary-tree *IS* a graph. So if you build an useful algorithm that work on a graph, it will work on those data structures too. Other example: suppose you have cities. Those cities are linked by highways. The cities are the nodes, and the highways are the vertices, so analyzing this data is actually operating on a graph. The interesting thing (you will have to google now) is that a lot of problems/data structures can be modeled as graphs, so discovering a new algorithm to operate on graphs has a huge impact on CS in general.

(2) Depends what you do for a living and if you want to be good at it. If you work with programming, then graphs are important. Knowing at least some basic stuff about then is useful because this will let you understand better how: databases work, memory managers, operating systems, web servers, language parsers, multi-threaded algorithms, etc etc etc...

Well... even if you indeed was trolling, I hope this post is interesting to someone else...

whatever
Monday, July 28, 2003

I concede that indeed I did partake of a bit of trolling. Every now and then I come across a board or thread inhabited by either a) students, or b) struggling software developers who were recently students, or c) developers who are informally-trained-but- feel -a-great-lack-of-confidence -so-they-grasp-onto- whatever-smells - like-academia, and the terminology oft used is straight out of "impractically vague terminology that convey nothing but imply great wisdom". I'd love to see a practical shop where someone other than a Junior Programmer proclaims that they're going to implement "graphs".

Dennis Forbes
Monday, July 28, 2003

"So, to conclude, the word "graph" has absolutely no practical value whatsoever when referring to data structures. Basically it means nothing. "

Nope, it means everything. They are everywhere. To conclude, every sructure with entities like nodes and links IS A damn GRAPH.

Then, there is a special kind of graph we call TREE. There is a special kind of graph we call LINKED LIST. There is a special kind of graph we call CIRCULAR LIST. There is a special kind of graph we call TABLE. There is a special context when graphs are called NETWORKS. ETC.

We say graph when it is not a list, a tree, etc. If every node can be linked to every other node, then the only word that fits is graph. Anyway, I guess there are other graph categories (Math stuff here).

"Graph" does not belong exclusively to Maths, nor to CS data structures: graph it's that thing we build when we want to express things and their relations (typichally now it's when everyone draws some weird lines and points in a piece of paper).

PS. Of course, anyone talking about a graph *the first* thing he/she has to do for his/her audience, is to define what is a node, a which relations are valid (mono-direction, bi-direcion, weight on links, weight on nodes,  maximum links per node, etc).

Ross
Monday, July 28, 2003

I apologize if I came off a bit harsh whatever, as you seem like a good guy just discussing things (as opposed to, say, Pillsbury L. Doughboy who comes across more as an arrogant, pedantic dick). However the reason why certain vocabulary is jettisoned by some in the profession is because it is so rudimentary, and so fundamentally useless, that it serves no practical purpose. If you think I'm grasping for understanding pointers and linked lists (or btrees, or hierarchies, or network nodes, or how highways link cities), then I think you're a bit confused about the relevence of a shared vocabulary when it comes to vague terms. I was humored in my original message because I'd swear that after going years seeing the vague term "graphs" applied to computer science perhaps once a month (though perhaps it's because I don't hang with the grand pooh-bahs), at most, over the past decade, suddenly I've seen it, quite literally, applied liberally in various discussion boards several dozen times in the past couple of weeks. I'm not quite sure what makes a term become so likeable all of a sudden. Maybe it's some sort of terminology pattern.

Dennis Forbes
Monday, July 28, 2003

(ignoring all the argument about trolling)

Dennis, for a very concrete example of why graphs are a useful idea, try reading about how garbage collection (e.g. in Java) works.  One way is to just "follow all the links" and see what is unreachable.  This is very simple to express when you think of your program's data as a graph: the objects are "nodes" and the pointers are "edges" (look "graph" up in google images and that will beceome apparent).  Then the idea is that your program's data must form a "connected" graph.  The components of the graph that are not connected to the main component are deleted.  That's it, very simple when you use this abstraction.

Another example of a graph is a computer network, e.g. the internet.  The nodes are computers and the edges are wires.  Another example is the the WWW.  The "nodes" are the pages and the "edges" are the hyperlinks.  Note that the internet graph is different than the WWW graph, though they are related.  A web spider (like google uses) is an program that uses graph algorithms to traverse the WWW graph.

Inheritance can be represented like a graph -- so can #include structures in C++, function calls, data dependencies.  Yes, basically everything important in programmming.  : )

Andy
Monday, July 28, 2003

Just think of them as a Windows shortcut -- it points to an .exe file somewhere. You can delete the exe, but the shortcut remains; likewise, you can delete the shortcut but the exe remains. Also, you can change the location(pointer TO) of the shortcut, but the shortcut itself won't "move" away from, say, the desktop.
Pardon my (half-assed?) attempt at explaining it.

Mickey Petersen
Monday, July 28, 2003

Pointers have no motive, they are pointless in themselves.

Occasionally programmers that make use of pointers have a point of their own.

Sometimes it coincides with the fact of what the pointer points at.

Pointers don't always point at the same thing all the time.

Pointers may point at themselves, or nothing at all.

Simon Lucy
Monday, July 28, 2003

Oh, btw a pointer may or may not be part of a graph, the one may presuppose the other but is not contingent on the existence of same.

Simon Lucy
Monday, July 28, 2003

I hope those last two posts were a joke : )

Andy
Monday, July 28, 2003

Dennis:

I think I now get what you're really discussing here, but I agree with you that your choice of words created some unecessary flaming =)

Anyway, I can't say for the other ppl in this forum, but I have had lots of interaction with graphs after graduating. But then, I recently started a master's degree in CS and before that one of my latest jobs was designing an application to handle "consumer-relation" workflow...

Perhaps this is your answer, I noticed that lots of ppl are talking now about "product/consumer workflow management" and "datawarehousing", mainly in CRM and other buzzword-ladden areas, and since all this is directly related with graphs it is not surprising it get to be a must-know word for some ppl.

Well... at least it does have a real background behind it... And knowing at least the basics about operation on graphs can be really useful, trust me!

whatever
Monday, July 28, 2003

Of course they were a joke, in what way weren't they also true?

Simon Lucy
Monday, July 28, 2003

The purpose of a pointer was originally to provide a cheap way for functions to access large amounts of data. Instead of passing the data, you pass the address of that data in memory.

Programmers also learnt that pointers provided a way for functions to return the results of operations to the caller.

.
Monday, July 28, 2003

Pointers are used for making applications crash in new and exciting ways.

Oh, and while I'm here, can I just advocate for the quick demise of pointer analogies?  I think the reason why no one groks pointers any more is because they can't use them without invoking the mental image of a street of houses, each mailbox being a memory location referenced by street location and the pointer is like a cute little puppy pissing on the mailbox post of interest, and all the street addresses that end in ODD numbers are bad because they cause misaligned data interrupts or cache misses, sorta like a mailman that has to lean the OTHER way to put the letter in the box -- and then they got to translate that back into boring computer terms, boring things like integers and arrays and objects, and is the distance to the next post box equal to sizeof(HOUSE), and what exactly does the mailman represent in this whole analogy?

Let's just keep it simple.  A pointer's just a 32-bit number that represents the beginning of your data structure in memory.  That's all that needs to be said about that.

Alyosha`
Monday, July 28, 2003

The original purpose of a pointer was to pass the address of some memory location that might be used (for almost any purpose later). It has it roots in assembly. If you describe it as originating in high level languages, you have it backwards, I think.

BTW the same applies to IMHO to the comments about data-type casting using pointers.

>A better, more general purpose is indirection

Agreed

A quick parse didn't see any mention of pointers to objects or functions.  When you consider these cases with regards to pointers to data/variables, then I think most would probably agree indirection is the best general description that covers all the cases.

S. Tanna
Monday, July 28, 2003

Why?  Objects and functions have addresses just like integers and other variables.  And you can cast pointers to objects and functions to pointers to integers/characters if you want to say dump memory.

Nothing about having pointers to objects and functions is different than pointers to other variables.  They are all addresses of the same form, and they all provide a method for indirection.

Andy
Monday, July 28, 2003

Pointers are definite offshoots from the memory address manipulation of assembly language.  You do a mathematical computation in assembly, then you put the result directly into a specified memory location. You don't have variables as such (although the assembler will let you declare memory locations symbolically with variable names).

My first programming language wasn't assembly, it was BASIC on the Commodore 64 when I was a teen. But the memory manipulation that could be done with PEEK and POKE in BASIC made it a small jump to grasping pointers in C and Pascal.

T. Norman
Monday, July 28, 2003

Right, at the lowest level are registers.  There are no pointer registers or integer registers, it's how the instructions interpret them.  You just have instructions that say "interpret the bits of this register as an integer and use it for an operand of an add operation" or "interpret the bits in this register as a memory address and load the memory into another register".

Andy
Monday, July 28, 2003

Hey, the 68k has pointer registers and data registers.

mb
Monday, July 28, 2003

Don't forget function pointers.  They're not really useful in C++, but they're invaluable in C.

Jason
Monday, July 28, 2003

True about the 68k, but it's not true in general, and it doesn't contradict my point, which may not have been clearly stated.

The point was basically what T. Norman says, that pointers come from CPU instructions.  Addresses are essential to the operation of the CPU and memory (How could they not be?  How else would the CPU load bytes from memory?).  Pointers are programming language abstractions on top of addresses, but just barely.  Most people, at least C programmers, just think of them as addresses.  C++ references are just pointers with some special features.  They are implemented in exactly the same way at runtime (with addresses), but undergo different checking at compile time.  I think C is one of the only languages that lets you do pointer arithmetic, which pretty much exposes the fact that a pointer is just an address, so you might as well think of it as an address, or an integer.  Programming languages introduce the idea that a pointer type is different than an integer type, but it's all the same bits.  Just like a character is an integer; it's just how you interpret it.

But really there is no difference between a pointer and an array index.  A pointer is just an index into the array that is ALL OF YOUR MEMORY.  That's all.  An old near pointer is just an index into an array that is 64k long.  Everybody knows arrays; they're the first thing you learn.  But for some reason pointers are harder, and I think it is more for the reason of the programming language abstraction than the actual concept of addresses.  I remember first learning C and how the * and & operators confused the shit out of me.  When I first _really_ got pointers is when I took an architecture class.  After architecture, learning * and & are trivial.

I think for some reason people have trouble with unary operators that are not obvious (like "not").  (a + b) / ( c - d ) is trivial -- we all took arithmetic in elementary school.  But (++(*p))++) and *(&p+1) are harder for some reason.

As a side note, about the 68k thing, I think I read that it has 8 address registers and 8 data registers, but some of them are the same?  I may be wrong.  i.e. you can have 16 logical registers and only 12 physical registers (with 4 of them being both data and address).  Some of them you can use as data operands, some of them as address operands, and some of them for both.  If that's true then it kind of enforces my points.

Andy
Tuesday, July 29, 2003

No, Andy, the 68000 has 8 honest-to-gosh data registers and 8 honest-to-gosh address registers.

However, A7 is the 68000's stack pointer, and when the 68000's in supervisor mode, it uses a different A7 than when in user mode.

More likely you're thinking of the 8086, which has four 16-bit registers (AX, BX, CX, and DX) that can be broken up into eight 8-bit registers (AH and AL, BH and BL, etc).  And then when the 386 came along, AX was really just the lower 16 bits of EAX.

I know no one really cares.  I'm just trying to impress the ladies lurking on this board.

Alyosha`
Tuesday, July 29, 2003

The more I learn, the more I think that indirection is *the* fundamental idea in computing.

BTW, a great book to read to learn about how computers really work is "Code" by Petzold.

John Topley (www.johntopley.com)
Tuesday, July 29, 2003

*  Recent Topics

*  Fog Creek Home