Lambda the Ultimate

inactiveTopic Reversible Garbage Collection (and more)
started 9/11/2003; 1:00:59 AM - last post 10/30/2003; 1:07:51 AM
David B. Wildgoose - Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 1:00:59 AM (reads: 482, responses: 12)
The Thermodynamics of Garbage Collection

A fascinating and readable account of some of the implications of Reversible Computation, including references to Psi-Lisp, a Reversible Linear Lisp.

Example snippet: The ability to summarize the information within a fixed number of "state variables" is the reversible computer's analogue to the "tail recursion optimization".

Patrick Logan - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 5:40:17 AM (reads: 472, responses: 0)
Oh, we could spend a good bit of time and space on Henry Baker's papers.

It's been a long time since I read any of those. What a collection.

David B. Wildgoose - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 6:57:43 AM (reads: 466, responses: 0)
Your comment has a sarcastic tone.

Care to enlighten us?

Patrick Logan - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 1:30:38 PM (reads: 428, responses: 1)
Your comment has a sarcastic tone.

Completely unintended. I meant to say Henry Baker's papers are broad and deep, and I am in awe of his command of the problems he thinks about.

I didn't have anything to say about this specific paper since it's been so long since I've read anything of Baker's. But I'd highly recommend people spend a great deal of time with his entire repertoire.

Ehud Lamm - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 1:51:00 PM (reads: 433, responses: 0)
I agree. It's an interesting paper (I read it a long time ago, so I don't remember the specifics). Baker's papers are well worth reading (he even wrote about Ada ).

I was sure Patrick wasn't being sarcastic, and I am glad to see I was right.

Bryn Keller - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 4:51:23 PM (reads: 414, responses: 0)
Are there any existing, implemented, reversible languages available for experimentation?

David B. Wildgoose - Re: Reversible Garbage Collection (and more)  blueArrow
9/11/2003; 11:22:07 PM (reads: 407, responses: 0)
Sorry for misreading the "tone" of your comment Patrick. I had also posted a link on another list only to have a response that the paper was "bull" based on a reading of just the first few paragraphs. I wouldn't have minded so much if this "Slashdot" approach to commenting without first reading hadn't come from someone whose opinions I usually respect.

I have now heard of 3 reversible languages, Psi-Lisp, Janus (nice name that one) and "R", but I don't know any more details.

Michael Vanier - Re: Reversible Garbage Collection (and more)  blueArrow
9/12/2003; 12:53:30 AM (reads: 394, responses: 0)
I was struck by the property of Psi-Lisp that procedures consume their arguments. I immediately thought of Forth, where this is the normal convention. Perhaps Forth could be used to make an accessible reversible language? You'd have to get rid of DUP and DROP.

Patrick Logan - Re: Reversible Garbage Collection (and more)  blueArrow
9/12/2003; 5:50:31 AM (reads: 384, responses: 0)
I was struck by the property of Psi-Lisp that procedures consume their arguments. I immediately thought of Forth

In fact Baker (not sure about this paper, but others) uses Forth as a means of illustrating linear objects.

Michael Vanier - Re: Reversible Garbage Collection (and more)  blueArrow
9/12/2003; 7:25:43 PM (reads: 364, responses: 0)
Patrick, do you offhand remember which papers discuss Forth? I can search for it, but I'm lazy ;-)

Michael Vanier - Re: Reversible Garbage Collection (and more)  blueArrow
9/13/2003; 1:17:25 AM (reads: 351, responses: 0)
Never mind, here it is:

http://www.pipeline.com/~hbaker1/ForthStack.html

It's worth reading. It deals with using a Forth-like (or PostScript-like) stack machine to implement a linear dialect of lisp. Linearity is an easier concept to grok than reversibility, although they're related. As I understand it, a linear language is one in which copying and duplication of objects have to be done explicitly. A reversible language is one in which copying and duplication simply aren't done. It's really fascinating stuff.

Shin-Cheng Mu - Re: Reversible Garbage Collection (and more)  blueArrow
10/30/2003; 1:07:51 AM (reads: 238, responses: 0)
I have now heard of 3 reversible languages, Psi-Lisp, Janus (nice name that one) and "R", but I don't know any more details.

I happen to know of another one. Paolo Zuliani described in his DPhil thesis a language based on Dijkstra's guarded command lanugage. The relevant chaper was published as a separate paper. It's more a language for specification than for implementation, however.

I am curious to know other related work.

(Sorry about the preivous message. I registered with a wrong email address..)