| Author |
Message |
< Erlang ~ Modeling a heap |
| chmaruni |
 Posted: Wed Oct 07, 2009 9:31 am |
 |
|
|
Joined: 07 Oct 2009
Posts: 4
|
Hi there,
I have an imperative language "L" with mutable data structures (let's call them "objects") and I am trying to write an interpreter for that language in erlang. The reasons why I do that are not important:)
May problem is, how I can model the heap of L without losing the erlang garbage collection? (Maybe that's just not possible?)
More precisely: Let's assume three objects A, B, C with one field each that reference each other in a circle. Obviously, one cannot represent those objects directly as erlang tuples, because they are a recursive data structure.
That leaves something like modeling a heap. For example, storing the objects in a dictionary where the key is their "address" such as an increasing integer. References are then represented as the integer address of the object that it references. The problem here is, that the erlang garbage collector cannot help with cleaning this heap dictionary and I would have to implement either reference counting or my own GC.
Translating an "L" object into an erlang process doesn't help, either, because process handles are not garbage collected, as I understand. So when an object becomes unreachable, the process ID is "lost" and the object stays alive forever.
This is different when implementing something like this in Java, for example, where every "L" object is represented by some Java object (that contains a hashmap for the fields, for example) and every "L" reference is a normal Java reference. Then, the Java garbage collector automatically also cleans up those "L" objects.
Are there any erlang tricks I missed? Or libraries? Or some other ideas that help with such cases?
Thanks a lot in advance!
Christoph |
|
|
| Back to top |
 
|
| uwiger |
| Posted: Wed Oct 07, 2009 1:01 pm |
|
|
|
User
Joined: 03 Jul 2006
Posts: 604
Location: Sweden
|
chmaruni wrote: Hi there,
I have an imperative language "L" with mutable data structures (let's call them "objects") and I am trying to write an interpreter for that language in erlang. The reasons why I do that are not important:)
May problem is, how I can model the heap of L without losing the erlang garbage collection? (Maybe that's just not possible?)
If it's an interpreter you want, you might want to look at erl_eval. It interprets symbolic erlang expressions using the function
Code: erl_eval(Exprs, Bindings) -> {value, Result, NewBindings}
This is used by the Erlang shell, which supports is own form of variable mutation (you can 'forget' a variable binding and re-bind it). Basically, you control what variables should be bound when entering the list of expressions, and you can, if you want to, rewrite the variable binding expressions ({match,Line,Var,Expr}) so that you can first evaluate Expr, then replace the Var entry in the list of bindings with the value returned from the evaluation.
What remains to figure out is when variables should be removed from the list of bindings. Not knowing the language 'L', I can't give you much help there. But if translating 'L' expressions to corresponding erlang forms feels like an acceptable way forward, you might be able to produce an interpreter fairly quickly. |
|
|
| Back to top |
|
| chmaruni |
| Posted: Wed Oct 07, 2009 5:25 pm |
|
|
|
Joined: 07 Oct 2009
Posts: 4
|
(You can think of "L" as a simple object-oriented language with objects that reference each other, i.e., they form an object graph.)
Thanks for the tips, erl_eval might help me indeed!
However, the "what remains to figure out is when variables should be removed from the list of bindings" is exactly the garbage collection problem I was talking about.
Anyhow, I guess I just go with "objects as processes" plus reference counting for now, even though reference counting cannot deal with cycles.
If somebody knows of a library that implements "garbage collected cyclic data structures" then I would still be interested, though:) |
|
|
| Back to top |
|
| Allan |
| Posted: Wed Oct 07, 2009 8:22 pm |
|
|
|
User
Joined: 29 Jun 2009
Posts: 30
|
chmaruni wrote: May problem is, how I can model the heap of L without losing the erlang garbage collection? (Maybe that's just not possible?)
As there is no Erlang structure, that can contain itself (directly or indirectly), this is indeed not possible.
But maybe, using ETS as object storage is a better aproach than using one process for each object.
A worker process may scan the table regularly for unused objects. You just have to ensure, that objects get not "temporarily" unlinked - that would confuse the asynchronous garbage collector process...
chmaruni wrote: More precisely: Let's assume three objects A, B, C with one field each that reference each other in a circle. Obviously, one cannot represent those objects directly as erlang tuples, because they are a recursive data structure.
You will use "references" of some sort - as other OOP languages are modelled the same way.
You will have to implement a garbage collector of one sort or the other - or just do not care about memory and free it all up when the "L" application completes ;) |
|
|
| Back to top |
 
|
| jmontelius |
| Posted: Fri Oct 09, 2009 9:58 pm |
|
|
|
User
Joined: 07 Mar 2009
Posts: 29
|
chmaruni wrote: If somebody knows of a library that implements "garbage collected cyclic data structures" then I would still be interested, though:)
Don't know about library but here is something that will get you started. I've left some things out so that you have something left to do in your homework 
Code:
-module(gc).
-export([copy/2, test/0]).
test() ->
copy([1,2,3], [{1, [2]}, {4, [1,3]}, {3, [1]}, {2, [3]}]).
copy(Regs, Heap) ->
copy(Regs, Heap, []).
copy([], _, Copy) ->
????;
copy([Ref|Rest], Heap, Copy) ->
case lists:keymember(???, 1, ???) of
true ->
copy(???, ???, ???);
false ->
{value, Obj} = lists:keysearch(Ref, 1, Heap),
Refs = refs(???),
copy(Refs ++ ???, Heap, [Obj|???])
end.
refs({_, Refs}) ->
Refs.
|
|
|
| Back to top |
|
| chmaruni |
| Posted: Fri Oct 09, 2009 10:13 pm |
|
|
|
Joined: 07 Oct 2009
Posts: 4
|
I guess I passed the times of homework and assignments, but thanks anyhow.
so I figured that I cannot "piggyback" on the erlang GC and have to implement my own. Not too surprising I guess.
Anyhow, thanks to the fruitful suggestions and if anybody has more ideas I'd be happy if you'd post them here... |
|
|
| Back to top |
|
| wuji |
| Posted: Tue Aug 21, 2012 7:52 am |
|
|
|
User
Joined: 10 Aug 2012
Posts: 654
|
untagged herself in photos she didn't like. But none of of cheap polo shirts of it was enough."Here is a weak-chin photo that I
untag myself in ... because I was working out really really cheap Christian Louboutin really hard that summer, and I am pleased with everything
in the photo," Lavey said. "But it's my darn chin chin [h4]designer replica *beep*[/h4] chin that bugs the living daylights out of me in
photo. ... You keep looking and looking, and now it's it's cheap replica *beep* it's the first thing I look for in a photo.
all started with Facebook."Surgery was the only way to fix fix replica designer *beep* fix it. Simply cutting down her social media use wasn't
option."That can't happen. ... Where my career is headed and and [h1]cheap polo shirts[/h1] and the industry is headed, I have to be on
media," Lavey said. Lavey is not alone. According to to cheap replica *beep* to the American Society of Plastic Surgeons, chin augmentations have
71 percent in the last year. Doctors confirm that more more discount designer *beep* more and more patients are asking for the Facebook facelift |
|
|
| Back to top |
|
| dongdongwu |
| Posted: Thu Sep 20, 2012 2:17 am |
|
|
|
User
Joined: 19 Sep 2012
Posts: 236
|
His good friend Diane said: "Christian Louboutin Men Shoes was a magician, he make shoes is immediately put his female people with legs and advantage. He understands women wanted to do and can make them into beautiful Cinderella." Madonna often in its concert wearing Christian louboutin high heels , and some famous superstar like Angelina jolie, mariah Carey, beyonce Knowles, the famous Japanese singer YaYouMei Hamasaki helps Christian Louboutin Men Shoes set up its powerful position. The youngest customers will count Tom cruise's daughter sully cruz. Louboutin made for only a pair of handmade Christian Louboutin high heel Shoes! Want to be more fashion? Put on Christian Louboutin Outlet !
Candy colors of the chalaza high-heeled shoes with lolita type allure, set full finely gem blue "neon shoes" is to need to use "sexy" to describe. Each pair are worth careful appreciation of lithe and graceful fairy ludaoli, what kind of most let you move?Christian Louboutin Men Shoes that one brush red is always cannot resist the temptation, Christian Louboutin men outlet continue to use the days of high 8cm above slender heel proclaim the sexy and luxuriant. The bowknot on black pointed high-heeled shoes with sharp rivet concomitant, wild python met enchanting color printing grain, It is that pairs of high-heeled shoes lets Carrie more feminine flavour. Like Christian Louboutin for men her word. |
|
|
| Back to top |
|
|
|
All times are GMT
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
|
|
|
Digg It
Del.icio.us
Reddit
Facebook
Stumble Upon
Technorati
