Basic question on emulating pointers for sharing memory

[Ed W]

Hi, new to functional programming question:

I'm building a structure to store a "graph", lets pretend the algorithm
is say GADDAG (http://en.wikipedia.org/wiki/GADDAG)

Now one of the space saving techniques in such a structure is where
several sub graphs are identical, to replace them with pointers to each
other. I'm unsure how to achieve this in Erlang/Elixir.

Phrased another way

a = [1,2,3,4]
t1 = {:something, a}
t2 = {:something2, a}

Is the storage for "a" allocated more than once (or twice)?

If the answer is it stores it once, then will this also work via matching?


a = [1,2,3,4]
t1 = {:something, a}
{_, b} = t1
t2 = {:something2, b}

Again in this instance is my list stored just the once?

I'm hoping that the VM is smart enough to combine these and store the
data just once. My proposed solution then to reducing allocation side in
my GODDAG is presumably then to find sub graphs which are "identical" in
turns of node contents and then "copy" one sub graph to the other (I'm
not sure what the correct word would be in a functional sense for
"copy", but hopefully the above illustrates the action)

Thanks for advice

Ed W

[Onorio Catenacci]

This strikes me as _possibly_ being premature optimization.  I'd think the better question is how to measure how much space is being used by the structures. Once you're sure that space is an issue then worry about what you might do to get it to share space.  Just my humble suggestion.

--

Onorio

 

[José Valim]

Phrased another way

    a = [1,2,3,4]
    t1 = {:something, a}
    t2 = {:something2, a}

Is the storage for "a" allocated more than once (or twice)?

No. Both tuples would reference the list contained by a. 

 

If the answer is it stores it once, then will this also work via matching?

    a = [1,2,3,4]
    t1 = {:something, a}
    {_, b} = t1
    t2 = {:something2, b}

Yes, it also works with matching. Remember though they are immutable, if you change in one tuple, the other tuple will not be affected (which is likely what you want here)!

Notice those properties even work when cons'ing into a list:

a = [1, 2, 3, 4]

b = [0|a]

In this case, b is only a cons cell with 0 that points to 0 (there is sharing).

However, if you append to the end of a list, a copy is done:

a = [1, 2, 3, 4]

b = a + [5]

There is no sharing above. That's one of the reasons we typically avoid such operations.

[Ed W]

Thanks Jose, that's really helpful.  I wonder if a variation of this is sensible for an FAQ point?

If you google around functional programming then there are a lot of naive glib answers highlighting that "pointers" aren't possible.. But knowing how the language deals with copying (immutable) structures allows us to effectively still build datastructures which one would require using "pointers" in an imperative language.

So I think we can summarise and say: As long as you avoid append (+), then you can essentially view constructing lists and tuples as being the equivalent of pointer assignments in an imperative language.  This is of course an expected optimisation for a language with immutable data structures.

I see now how I can use this to build various efficient tree structures (which should also have efficient update operations)

Thanks

Ed W

[José Valim]

I see now how I can use this to build various efficient tree structures (which should also have efficient update operations)

Exactly! Here are some interesting talks on the matter:

http://www.infoq.com/presentations/julia-vectors-maps-sets

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

[Ed W]

On 12/06/2014 17:19, José Valim wrote:

I see now how I can use this to build various efficient tree structures (which should also have efficient update operations)

Exactly! Here are some interesting talks on the matter:

http://www.infoq.com/presentations/julia-vectors-maps-sets

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Cool - thanks

How do you want to approach new datastructures in Elixer? Are you interested in seeing anything in core in the future? What is a sensible path for ideas to "breed", do you want to see code in github, protocols on the mailing list?

Specifically I'm playing with generating prime numbers this week, hence I wanted a high performance "Priority Queue" implementation.  I'm currently twiddling with a Pairing Heap (and Skewed Binomial Heap), which is basically straight out of Okasaki (with an eye also on Wikipedia - slightly easier to read...).  However, Priority Heap and Queue don't map well to Dict, which is the closest structure we have in Elixir...

How to proceed (in general)?  Throw up a request for comments on the mailing list? Bang it into the Dict structure (it does kind of fit if you squint a bit)? Something else? Basically, how interesting do new data structures need to be before you are interested in seeing them become somewhat "core"?

Thanks

Ed W

[José Valim]

Data structures would follow the same process of all improvements to the language. First it needs to be developed separately and if it is useful enough for multiple people, we should definitely consider its inclusion in the language.

Once you create something, you can put it in a package and publish to hex.pm for example. You can also send announcements to this mailing list. And there is no need to map it to a dict!

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dave Martin]

On Thursday, June 12, 2014 10:16:10 AM UTC-6, Ed Wildgoose wrote:

If you google around functional programming then there are a lot of naive glib answers highlighting that "pointers" aren't possible..

To speak to this from a C/C++ perspective for a moment... There is a concept of a pointer, and the concept of a reference.  Lots of languages have references, but only a few have pointers, and sometimes when people say pointer they mean reference. And when someone says a language doesn't have pointers, they usually mean specifically C/C++ style pointers, and not references.

So, the difference is, a reference can only refer to existing data (or absence of data, like Nil, or Null), and the only thing you can do with a reference is change it to a reference to something else, or go through it to get at the object its referencing.

A pointer on the other hand, can be directly manipulated, and in ways that may not be safe. In C (or C++) I can mathematically manipulate pointers and the pointer may now be pointing at the middle of some object, or it might be pointing to allocated or invalid memory. I can also do things like claim a pointer points to a foo structure, and then actually make it point at a fum structure, and then proceed to manipulate the foo structure as if it were a fum structure and potentially corrupt things.

This is from a C perspective, its possible other languages might be using the terminology differently. Pascal has pointers, but they are really what a C++ person would think of as a reference. So its important to make sure the definitions are clear in any particular does/doesn't or can/can't discussions.

[Onorio Catenacci]

I know you didn't ask and this is dramatically more primitive than what you're discussing but for whatever it's worth:

http://codereview.stackexchange.com/questions/51541/how-could-this-be-written-using-continuation-passing-style

--

Onorio