Home

Streaming Representation-Changers

Jeremy Gibbons (2004). Streaming Representation-Changers. To appear in Mathematics of Program Construction, July 2004.

Unfolds generate data structures, and folds consume them. A hylomorphism is a fold after an unfold, generating then consuming a virtual data structure. A metamorphism is the opposite composition, an unfold after a fold; typically, it will convert from one data representation to another. In general, metamorphisms are less interesting than hylomorphisms: there is no automatic fusion to deforest the intermediate virtual data structure. However, under certain conditions fusion is possible: some of the work of the unfold can be done before all of the work of the fold is complete. This permits streaming metamorphisms, and among other things allows conversion of infinite data representations. We present the theory of metamorphisms and outline some examples.

More origami work from Gibbons.

This paper is related to several previous papers by Gibbons that were mentioned here (e.g., spigot pi, arithmetic coding), and it could be said that it summarizes the main results. I don't think this paper was linked to directly, so here goes.

By Ehud Lamm at 2004-07-20 19:08 | Functional | other blogs | 4700 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I thought that description lo

I thought that description looked familiar. You've gotta trust that deja vu feeling. ;)

Original posting

By ajrw at Wed, 2004-07-21 13:23 | login or register to post comments

Sorry about that

But it's worth a look anyway.

By Ehud Lamm at Wed, 2004-07-21 13:37 | login or register to post comments

Has appeared, actually.

To appear in Mathematics of Program Construction, July 2004.

In Proc. Mathematics of Program Construction, 7th International Conference, MPC 2004, Stirling, Scotland, UK, July 2004.

I was there, and it was a nice talk. In fact, it is likely I will be joining Jeremy's group at Oxford when I finish my thesis.

U. Stirling has a beautiful campus and MPC is the best conference I've been to so far. In particular, there were several interesting talks on nondeterminism, and now I finally understand what "angelic choice" and "demonic choice" mean.

I think LtU readers will also enjoy:

Graham Hutton and Joel Wright. Compiling exceptions correctly. In Proceedings of the 7th International Conference on Mathematics of Program Construction, Lecture Notes in Computer Science volume 3125, Springer, July 2004.
By Frank Atanassow at Wed, 2004-07-21 15:46 | login or register to post comments

I should have noted that

Having tried a couple of times to access the lecutre notes on SpringerLink (to no avail).

it is likely I will be joining Jeremy's group at Oxford when I finish my thesis.

Good news. A good bunch of guys they are.

By Ehud Lamm at Wed, 2004-07-21 16:12 | login or register to post comments