Re: Pointers in Haskell??
Hello, > "Bryan" == Bryan Hayes <(Hayes Technologies)" ><[EMAIL PROTECTED]>> writes: Bryan> My question is: Bryan> Does Haskell principally not need pointers (i.e. in case of 2 Bryan> data structures needing to reference an other very large data Bryan> structure) or is this a design flaw or have a overlooked Bryan> something? if you hold two variables to a data structure, the structure is represented only once. This is established by a graph structure of data, instead of just a tree structure. If you modify one copy, only the reachable parts between the handle (variable) and the position where the change has been made, are copied. All common substructures that are not affected by the change remain shared. Memory is allocated and released automatically. However, if you prefer a more state-based way of programming, you can deal with pointers in a so-called "monad", but if you need pointers for no other reason than efficiency, you should first try to use efficient programming techniques and data structures in Haskell. Programming in Haskell is completely different from imperative programming but it'll be worth it from the perspective of programming productivity. Just finding a way to fit imperative style in the syntax of Haskell will not give you the benefit you may expect from Haskell. Have a look at the book by Simon Thompson: "Haskell: The Craft of Functional Programming". It explains the methodology of programming in Haskell very well. Cheers -- Christoph Herrmann ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
At 9:30 AM -0600 12/7/01, Bryan Hayes (Hayes Technologies) wrote: > I am totally new to Haskell, so maybe this is a stupid question. > Various languages have pointers (or references), for good reason. > Haskell can at least partly do without them (they are only existing > internally somehow). > My question is: Does Haskell principally not need pointers (i.e. in case > of 2 data structures needing to reference an other very > large data structure) or is this a design flaw or have a overlooked >something? In Haskell, you can arrange for a large data structure to be shared by giving it a name, and then using the name wherever you'd use a pointer in some other language. For example, in > t = [0..] -- could be quite large > b = 3 : t > c = 5 : t the lists b and c share list t. Of course, these lists' implementations are full of pointers, but there's never a need for them to appear explicitly in Haskell programs. -- Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138Austin, Texas 78712-1188 [EMAIL PROTECTED][EMAIL PROTECTED] -- ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
The answers are making this question seem trickier than I'd thought it was, because so far they (both) make it sound like structure-sharing is tied very closely to names / variables. For instance: > In Haskell, you can arrange for a large data structure to be shared by > giving it a name, and then using the name wherever you'd use a pointer in > some other language. The idea here seems to be that you have a name that refers specifically to the struccture you wish to share (as opposed to needing only an expression whose value is that structure), and then there are two possible interpretations: One possible interpretation is: this is *a* way to get sharing, to show that it's possible to have shared structures. The other possible interpretation is: this is *the* (only) way to do it. What I'd expected was that it would suffice to have an expression (and indeed that implementationally it would be much like Lisp or Java so that values were always (except in exceptional cases) secretly "pointers to".) -- Jeff ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
"Bryan Hayes (Hayes Technologies)" wrote: > > I am totally new to Haskell, so maybe this is a stupid question. > Various languages have pointers (or references), for good reason. > Haskell can at least partly do without them (they are only existing internally >somehow). > My question is: Does Haskell principally not need pointers (i.e. in case of 2 data >structures needing to reference an other very > large data structure) or is this a design flaw or have a overlooked something? All Haskell compilers use pointers internally. The idea is that because Haskell is referentially transparent and side effect free, you can overwrite a function application with its result. For example, let x = [1..1000] in foo (A x) (B x) Will internally have "x" pointing to the function application [1..1000], when this function application is evaluated it will overwrite the memory cell "x" points to with the result. So eventually it will look like this: +---+---+ +---+---+ | A | x | | B | x | +---+---+ +---+---+ | | +---+---+ | V +---+---+--+ | : | 1 | tail |---> The list 2..1000 +---+---+--+ Where each block is a memory cell and each arrow is a pointer. A book that describes this a lot better is: Simon Peyton-Jones. The implementation of functional programming languages. Prentice-Hall, 1987 Jan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
Jan Kort <[EMAIL PROTECTED]> writes: > > Simon Peyton-Jones. The implementation of functional > programming languages. Prentice-Hall, 1987 is this book could be made available online ? cos on amazon it seems out of print. > > Jan > > ___ > Haskell-Cafe mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. ** Get Free. Be Smart. Simply use Linux and Free Software. ** ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
> All Haskell compilers use pointers internally. The
> idea is that because Haskell is referentially
> transparent and side effect free, you can overwrite
> a function application with its result. For example,
>
> let
> x = [1..1000]
> in
> foo (A x) (B x)
>
> Will internally have "x" pointing to the function
> application [1..1000], when this function application
> is evaluated it will overwrite the memory cell "x"
> points to with the result. So eventually it will
> look like this:
>
> +---+---+ +---+---+
> | A | x | | B | x |
> +---+---+ +---+---+
>| |
>+---+---+
>|
>V
>+---+---+--+
>| : | 1 | tail |---> The list 2..1000
>+---+---+--+
>
> Where each block is a memory cell and each arrow is a
> pointer.
What does it mean to have a letter ("A", "x", or a number or "tail",
etc) inside a box?
> A book that describes this a lot better is:
>
> Simon Peyton-Jones. The implementation of functional
> programming languages. Prentice-Hall, 1987
Are they always implemented that way these days?
-- J
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
In my previous example, > t = [0..] > b = 3 : t > c = 5 : t lists b and c share t, but in > x = 3 : [0..] > y = 5 : [0..] lists x and y share nothing. Extensionally, they have the same values as b and c, but each has its own copy of [0..]. Unless, that is, the compiler is clever enough to recognize the subexpression [0..] which x and y have in common. I don't know whether any Haskell compilers look for common subexpressions, but it's certainly an option. So the question of whether names are "*the* (only) way" to obtain sharing isn't really a language question-- it's more of a compiler question. Thanks to Haskell's referential transparency, whether or not structures --or the expressions that define them-- are shared doesn't affect Haskell programs' semantics; it affects only their efficiency. That "only" is not intended to depreciate the significance of efficiency. It's just that one of the benefits of referential transparency is that it allows an unusually clean separation of concerns between efficiency and correctness. The absence of any update operation means that it's impossible to write a program that can detect whether a structure is being shared, so sharing is extremely common. And indeed, in the typical implementation values are nearly always implemented by pointers. In a function call, for instance, all occurrences of a parameter in the function's definition point to the same argument, thereby sharing it (another example in which sharing involves names). If the argument is an expression not in normal form, it's never evaluated more than once: On the first evaluation, the value replaces the argument, and all occurrences of the parameter share that value. --Ham At 11:07 AM -0600 12/7/01, Jeff Dalton wrote: >The answers are making this question seem trickier than I'd thought it >was, because so far they (both) make it sound like structure-sharing >is tied very closely to names / variables. For instance: > >> In Haskell, you can arrange for a large data structure to be shared by >> giving it a name, and then using the name wherever you'd use a pointer in >> some other language. > >The idea here seems to be that you have a name that refers >specifically to the struccture you wish to share (as opposed >to needing only an expression whose value is that structure), >and then there are two possible interpretations: > >One possible interpretation is: this is *a* way to get sharing, >to show that it's possible to have shared structures. > >The other possible interpretation is: this is *the* (only) way >to do it. > >What I'd expected was that it would suffice to have an expression >(and indeed that implementationally it would be much like Lisp or >Java so that values were always (except in exceptional cases) >secretly "pointers to".) > >-- Jeff -- Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138Austin, Texas 78712-1188 [EMAIL PROTECTED][EMAIL PROTECTED] -- ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
In-Reply-To: Hamilton Richards's message of Fri, 7 Dec 2001 12:11:23 -0600 > In my previous example, > > > t = [0..] > > b = 3 : t > > c = 5 : t > > lists b and c share t, but in > > > x = 3 : [0..] > > y = 5 : [0..] > > lists x and y share nothing. Extensionally, they have the same values as b > and c, but each has its own copy of [0..]. That's because you're interpreting "same value" extensionally. The same sort of issue comes up in Lisp or Java. But suppose in Java I have Object x = new Whatever(); and that new object has some large substructures. I can get one of those substructures to be shared, rather than copied, without having a variable whose value is that substructure. For instance, the substructure might be shared in Object[] anArray = new Object[](x.getSubstructure(), x.getSubstructure()); provided that x.getSubstructure() returns the very same substructure (not a copy) each time. >Unless, that is, the compiler is clever enough to recognize the > subexpression [0..] which x and y have in common. I don't know whether any > Haskell compilers look for common subexpressions, but it's certainly an > option. >So the question of whether names are "*the* (only) way" to obtain > sharing isn't really a language question-- it's more of a compiler question. Are they the only way that's guaranteed to result in sharing, or is even that not the case? Cheers, Jeff ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
This book is already on-line at http://research.microsoft.com/Users/simonpj/Papers/student.ps.gz (It was noted on the "Books and Tutorials" link from haskell.org, which is usually the best place to start looking for something Haskell.) Best Wishes, Greg On Fri, 2001-12-07 at 12:57, Yoann Padioleau wrote: > Jan Kort <[EMAIL PROTECTED]> writes: > > > > > Simon Peyton-Jones. The implementation of functional > > programming languages. Prentice-Hall, 1987 > > is this book could be made available online ? cos on amazon it seems > out of print. > > > > > > Jan > > > > ___ > > Haskell-Cafe mailing list > > [EMAIL PROTECTED] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > -- > Yoann Padioleau, INSA de Rennes, France, > Opinions expressed here are only mine. Je n'écris qu'à titre personnel. > ** Get Free. Be Smart. Simply use Linux and Free Software. ** > > ___ > Haskell-Cafe mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Gregory Wright Chief Technical Officer PacketStorm Communications, Inc. 20 Meridian Road Eatontown, New Jersey 07724 1 732 544-2434 ext. 206 1 732 544-2437 [fax] [EMAIL PROTECTED] ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Pointers in Haskell??
I would also recommend the following book, which, in Chapter 3, discusses graph reduction, closures, and pointers: Fethi Rabhi, and Guy Lapalme. Algorithms: a functional programming approach; Second Edition. Addison-Wesley, 1999. Another useful book, but probably not for the beginner, is Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998, 1999. Best Regards, Richard E. Adams Softmatrix, Inc. Roseville, CA Email: [EMAIL PROTECTED] -Original Message- From: Bryan Hayes (Hayes Technologies) [mailto:[EMAIL PROTECTED]] Sent: Friday, December 07, 2001 7:30 AM To: [EMAIL PROTECTED] Subject: Pointers in Haskell?? I am totally new to Haskell, so maybe this is a stupid question. Various languages have pointers (or references), for good reason. Haskell can at least partly do without them (they are only existing internally somehow). My question is: Does Haskell principally not need pointers (i.e. in case of 2 data structures needing to reference an other very large data structure) or is this a design flaw or have a overlooked something? -- HAYES TECHNOLOGIES Software Speed Optimization Bryan Hayes Managing Director Mannheimer Str. 8 D-67098 Bad Dürkheim Deutschland / Germany Tel. +49 / (0)6322 / 94 950 - 68 Fax +49 / (0)6322 / 94 950 - 69 Mobile Tel. +49 / (0)163 / 6111867 E-Mail: mailto:[EMAIL PROTECTED] Web-Site: http://www.hayestechnologies.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
At 12:29 PM -0600 12/7/01, Jeff Dalton wrote: >In-Reply-To: Hamilton Richards's message of Fri, 7 Dec 2001 12:11:23 -0600 > > ... But suppose in Java I have > > Object x = new Whatever(); > >and that new object has some large substructures. I can get >one of those substructures to be shared, rather than copied, >without having a variable whose value is that substructure. >For instance, the substructure might be shared in > > Object[] anArray > = new Object[](x.getSubstructure(), > x.getSubstructure()); > >provided that x.getSubstructure() returns the very same substructure >(not a copy) each time. As far as the semantics of Haskell programs is concerned, there's no distinction between *same* and *equivalent*. An efficient implementation will exploit this by using identity to implement equivalence. For example, in x = ["zero","one","two","three"] y = [x!!2, x!!2] -- (!!) is list indexing the components of y would most likely be implemented by pointers to the same string "two" in memory, but it would also be correct (although less efficient) for y's two components to be separate copies of "two". >> ... So the question of whether names are "*the* (only) way" to obtain >> sharing isn't really a language question-- it's more of a compiler question. > >Are they the only way that's guaranteed to result in sharing, or is >even that not the case? Depends on what you mean by "guaranteed". Since in Haskell sharing vs. not sharing is not a semantic issue, you can't very well say that if sharing doesn't occur under such-and-such circumstances, the language specification is violated. This is very different from languages like Java, where Object[] x = new Object[](...) Object[] y = x; means that x and y refer to the same array (not merely equivalent arrays), and if they don't, it's not Java. And what's crucial is that you can write a Java program that detects whether x and y refer to the same array, by updating the array via x and observing the effect via y. In Haskell, no such program can be written, because there's no update operation. Hence an implementation is free to share or not, and neither choice violates the language definition. To determine under what circumstances a given Haskell implementation exploits sharing, you really have to look at the implementation's source code. Or you can make some time and space measurements of Haskell programs, and derive educated guesses. Cheers, --Ham -- Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138Austin, Texas 78712-1188 [EMAIL PROTECTED][EMAIL PROTECTED] -- ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Pointers in Haskell??
| > > Simon Peyton-Jones. The implementation of functional | > > programming languages. Prentice-Hall, 1987 | > | > is this book could be made available online ? cos on amazon it seems | > out of print. | | This book is already on-line at | | http://research.microsoft.com/Users/simonpj/Papers/student.ps.gz | | (It was noted on the "Books and Tutorials" link from haskell.org, which | is usually the best place to start looking for something Haskell.) That's a useful resource too, but it's not the book that the first poster mentioned. The earlier book was more advanced, more research-oriented, and (in most respects) covered more material than the later one (which was intended as an executable tutorial). Personally, I honestly don't think I would have been able to put Gofer together without many hours poring over Simon's 1987 book. (Noting that I'm getting quite old (:-), perhaps I should explain that Gofer was the predecessor of Hugs ...) I'll have to take extra special care of my well-worn copy now that the book is out of print! All the best, Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
> >> ... So the question of whether names are "*the* (only) way" to obtain > >> sharing isn't really a language question-- it's more of a > >> compiler question. > > > >Are they the only way that's guaranteed to result in sharing, or is > >even that not the case? > > Depends on what you mean by "guaranteed". Since in Haskell sharing vs. not > sharing is not a semantic issue, you can't very well say that if sharing > doesn't occur under such-and-such circumstances, the language specification > is violated. But the answers to the original question seemed to be saying you would get sharing if you wrote code of a certain sort. I take it that the language semantics doesn't strictly require sharing, but it sounded like it was something programmers could assume would happen in practice. If not, then shouldn't the answers to the original question have been different? What I was wondering was why the answers to the original question about pointers involved giving a name to the thing you wanted shared. Is there something less direct that would also work? For instance, could I instead name something that contained the structure I wanted shared and then use an appropriate expression to refer to the part I wanted shared - or do I have to give a name directly to that part. The main point of my Java example was to give an example where I didn't give a name to the very thing I wanted shared, but instead gave a name to something that contained it. > This is very different from languages like Java, where > >Object[] x = new Object[](...) >Object[] y = x; > > means that x and y refer to the same array (not merely equivalent arrays), > and if they don't, it's not Java. And what's crucial is that you can write > a Java program that detects whether x and y refer to the same array, by > updating the array via x and observing the effect via y. You can just use ==. Also, I'm not sure the Java language semantics really does require that x and y in your example above refer to the same locations in memory. The update test doesn't necessarily show that either. It just shows that if you change one, the "other" changes too. Of course, programmers assume that assignment to array elements is done in a fairly direct and simple way; but the language semantics might nonetheless allow something more expensive and complex. -- Jeff ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Pointers in Haskell??
| > Simon Peyton-Jones. The implementation of functional | > programming languages. Prentice-Hall, 1987 | | is this book could be made available online ? cos on amazon | it seems out of print. I'm planning to scan it in and make the copy available online. In the next month or two. Simon ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
On Mon, Dec 10, 2001 at 12:58:33AM -0800, Simon Peyton-Jones wrote: > | > Simon Peyton-Jones. The implementation of functional > | > programming languages. Prentice-Hall, 1987 > | > | is this book could be made available online ? cos on amazon > | it seems out of print. > > I'm planning to scan it in and make the copy available online. > In the next month or two. At long last! Thank you so very much! Thanks, Bill ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
Hamilton Richards writes: | In my previous example, | | > t = [0..] | > b = 3 : t | > c = 5 : t | | lists b and c share t, but in | | > x = 3 : [0..] | > y = 5 : [0..] | | lists x and y share nothing. Extensionally, they have the same | values as b and c, but each has its own copy of [0..]. |Unless, that is, the compiler is clever enough to recognize the | subexpression [0..] which x and y have in common. I don't know | whether any Haskell compilers look for common subexpressions, but | it's certainly an option. |So the question of whether names are "*the* (only) way" to | obtain sharing isn't really a language question-- it's more of a | compiler question. Hi. It's a difficult question for a compiler, especially as sharing isn't always a good thing. let t = [0..] b = 3 : t c = 5 : t in b !! (c !! 100)-- likely to have a space leak let x = 3 : [0..] y = 5 : [0..] in x !! (y !! 100)-- compact, unless transformed to gain sharing (The space leak arises because a million cells of t are allocated, but the garbage collector can't free them because they're still reachable via b.) Because of examples like that, I prefer to stick with a simple name-based sharing scheme. Regards, Tom ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
