A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips. A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech. The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before. A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.) Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism. To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes. Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted. Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand. The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine.
I look forward to the day when the OS will notice that a binary was compiled from haskell, and therefore is provably not buggy due to haskells strong type system. So it happily turns off all memory protection and lets it run on the bare hardware at full speed. :) This is not entirely unreasonable, operating systems with trusted compilers and typed assembly languages are active areas of research. I was thinking that if I were to try to implement a G-machine, I'd start with an FPGA and start hacking one of the open MIPS cores out there, but I think I like your soupcan solution better. :) John -- John Meacham - ⑆repetae.net⑆john⑈
On Wed, May 16, 2007 at 03:41:30PM -0700, John Meacham wrote:
I look forward to the day when the OS will notice that a binary was compiled from haskell, and therefore is provably not buggy due to haskells strong type system. So it happily turns off all memory protection and lets it run on the bare hardware at full speed. :)
This is not entirely unreasonable, operating systems with trusted compilers and typed assembly languages are active areas of research.
But then GHC would be faster then JHC! (Nobody cares about jhc, certainly not enough to implement a recognizer for it...) Stefan
On Wed, May 16, 2007 at 03:47:07PM -0700, Stefan O'Rear wrote:
On Wed, May 16, 2007 at 03:41:30PM -0700, John Meacham wrote:
I look forward to the day when the OS will notice that a binary was compiled from haskell, and therefore is provably not buggy due to haskells strong type system. So it happily turns off all memory protection and lets it run on the bare hardware at full speed. :)
This is not entirely unreasonable, operating systems with trusted compilers and typed assembly languages are active areas of research.
But then GHC would be faster then JHC! (Nobody cares about jhc, certainly not enough to implement a recognizer for it...)
Ah, but think of how much faster jhc development would be if it didn't take ghc 20 minutes to compile it every time I made a change :) John -- John Meacham - ⑆repetae.net⑆john⑈
| > But then GHC would be faster then JHC! (Nobody cares about jhc, | > certainly not enough to implement a recognizer for it...) | | Ah, but think of how much faster jhc development would be if it didn't | take ghc 20 minutes to compile it every time I made a change :) Oh! A cruel jibe! Simon (Methinks I must attempt to recruit one J Meacham to GHC optimisation duties.)
From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of John Meacham
But then GHC would be faster then JHC! (Nobody cares about jhc, certainly not enough to implement a recognizer for it...)
Ah, but think of how much faster jhc development would be if it didn't take ghc 20 minutes to compile it every time I made a change :)
John
Is JHC not yet self-hosting? (or whatever the appropriate term is for a compiler that can compile itself) If it is, how long does it take to compile itself? Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************
Hi
It is worded as biotech but may as well be molecular computing or nanotech.
biotech machines tend to be inaccurate, but highly parallel. Unfortunately the G machine is very un-parallel and requires 100% precision. Things like speculative evaluation may be more interesting.
To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes.
I think that in a novel machine you aren't going to want to do the traditional methods of garbage collection, or anything else. You'll probably need entirely new methods of doing entirely new things.
Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand.
It would also be a shame if for the G'-machine we have excellent debugging capabilities, but for normal Haskell on a normal computer we're stuck with Debug.Trace... Thanks Neil
Albert Y. C. Lai wrote:
A native G-machine --- physical, or chemical, or biological, but not a repressed simulation over the imperative cpu-memory architecture --- is the dream of every lazy-functional programmer of great devotion. If only it became the dominant computing architecture! People would say, Haskell is high-level assembly because it is the closest to the bare metal (or bare protein) and still supports all sorts of abstractions. People would ask, why is my C program five times slower than Haskell, and people would answer, that's because C is compiled to a stack of seven monad transformers (one of which is ContT to support longjmp), and because you should use more linked lists and fewer arrays. We truely rule the world when C programmers have to consult us for performance tips.
A necessary condition for dominance is existence. Here is my crazy imagination of a native G-machine. It is worded as biotech but may as well be molecular computing or nanotech.
The heap is a soup of nutrients. A node is a molecular structure made from the nutrients. A thunk is a lot of nodes linked up. Nodes and thunks are suspended in the soup. Allocation means constructing nodes and links from nutrients, and deallocation means unlinking nodes and eventually dismantling them back into nutrients. As a side effect, memory upgrade is cheap and convenient: Just go buy a can of Campbell soup (my favourite is the alphabet soup) and pour into your heap. There are 24-hour convenient stores at every street corner --- pervasive computing has never been so pervasive before.
A thunk is nodes linked together and suspended in the soup. A theorem in graph theory asserts that all finite graphs can be embedded without crossing edges in 3D space, and we take advantage of this to space out the nodes in a complicated thunk. Still, it is not easy, being NP-hard and all. There is a relaxation heuristic for this: It simply requires nodes to be a bit repulsive to each other and links to be elastic, and they will sort things out themselves. (When they don't, a bit of shaking up helps tremendously.)
Evaluation is performed by a small organism crawling over a thunk and performing its thunk-rewriting duty as per the G-machine. It applies enzymes to construct and deconstruct nodes and links from nutrients. It performs primitive arithmetic on its own. It maintains its own stack, inside or outside its body (to be investigated). It is possible to unleash several such evaluators for parallel computing. It is possible to enable reproduction to boost parallelism.
To add garbage collection, roots send out a periodic (or sustained) signal to all connected nodes. Nodes receiving the signal do not self-destruct. Nodes not receiving the signal invokes their built-in self-destruct mechanism to dissolve themselves back into nutrients. There may be better schemes.
Interacting with the outside world is open, but Andrew Gordon's thesis contains translations from monadic I/O to other I/O schemes, e.g., continuations, streams, etc. Perhaps one of them can be adapted.
Debugging can be done by making evaluators send radio signals concerning operations they perform; then a second computer can log these and you can review them. You can also use radio signals to instruct the evaluators to perform unusual operations on demand.
The existence of a native G-machine is a necessary but not sufficient condition for world dominance. We still need to make it fast, compact, and cheap. There may also be better but totally different ways to realize a native G-machine.
Amorphous computing (http://www-swiss.ai.mit.edu/projects/amorphous/), including biological computers (http://www-swiss.ai.mit.edu/~rweiss/bio-programming/), an application domain for pure FP (http://www.eecs.harvard.edu/~mdw/proj/mp/) ?
Hmm. I think you're going to have problems with thermodynamics here. While it is possible to perform computations using chemical reactions, an *energy source* is required to drive the process. The word "nutrients" implies a substance containing chemical energy, but in that case no garbage-collected structures are every going to "dissolve into" nutrients; energy would need to be injected at this step somehow. (Not to say it's impossible of course; just to say it's more complicated than you seem to realise.) You can do some amazing things with protiens - they're increadible molecules. But designing one to perform a specific task it currently *way* beyond cutting-edge science. I would suggest that a better approach would be to utilise not individual molecules but small single-celled plants. Genetically engineering such plants to perform useful operations would probably be orders of magnitude easier than trying to design individual molecules to do it. And since these are plants, they can produce their own chemical energy from sunlight. And grow more working units. It wouldn't be trivial by any stretch of the imagination, but given decades and lots of funding, someone might well build organisms that self-organise into a working G-machine. Personally though, I think it would probably be vastly easier to just write some VHDL for chips that understand G-code. ;-) (Actually, I've been thinking about what would happen if instead of having a bunch of memory registers over here, and a bunch of processor logic over there, what if each memory register also had a little bit of processing logic along with it? Then things could get massively parallel... But the more I think about it, the more that idea doesn't really work. The limiting factor would rapidly become "how to we get data between distant registers?" And where would you put a "program" in this system anyway? About the closing working analogue I can think of is ANN chips...) [rambling over]
participants (8)
-
Albert Y. C. Lai -
Andrew Coppin -
Bayley, Alistair -
Derek Elkins -
John Meacham -
Neil Mitchell -
Simon Peyton-Jones -
Stefan O'Rear