<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Nov 11, 2010, at 1:42 PM, Stephen Tetley wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; font-size: medium; ">[*] In case anyone looks up MacGuffin on Wikipedia, I don't think the<br>description there is strictly accurate. A MacGuffin doesn't drive the<br>plot so much as throw the viewer of the scent.</span></blockquote></div><br><div>I think Hitchcock might disagree with you.</div><div><br></div><div>In any case, serializing functions is as easy as you want it to be. But, there is a big caveat: You are basically embedding a compiler into your run-time. It can be pretty minimal, relying only on facts known about recursively enumerable functions:</div><div><br></div><div><font class="Apple-style-span" face="Courier">class Serialize a where </font></div><div><font class="Apple-style-span" face="Courier"></font><font class="Apple-style-span" face="Courier"> serialize </font><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="Courier"> </font></span><font class="Apple-style-span" face="Courier">:: a -> ByteString </font></div><div><font class="Apple-style-span" face="Courier"></font><font class="Apple-style-span" face="Courier"> unSerialize :: ByteString -> Maybe a <span class="Apple-style-span" style="white-space: pre;"> </span></font><font class="Apple-style-span" face="Courier">-- Parsers can fail</font></div><div><font class="Apple-style-span" face="Courier"><br></font></div><div><font class="Apple-style-span" face="Courier">instance (Serialize a) => Serialize [a] where ...</font></div><div><font class="Apple-style-span" face="Courier">instance (Serialize a, Serialize b) => Serialize (a, b) where ...</font></div><div><font class="Apple-style-span" face="Courier"><br></font></div><div><font class="Apple-style-span" face="Courier">-- We can conclude that a and b must be enumerable from the requirement that</font></div><div><font class="Apple-style-span" face="Courier">-- f is recursively enumerable:</font></div><div><span class="Apple-style-span" style="font-family: Courier; ">instance (Serialize a, Enum a, Serialize b, Enum b) => Serialize (a -> b) where</span></div><div><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="Courier"> </font></span><font class="Apple-style-span" face="Courier">serialize f = serialize $ ( zip [minBound..maxBound] </font></div><div><span class="Apple-tab-span" style="white-space:pre"><font class="Apple-style-span" face="Courier"> </font></span><font class="Apple-style-span" face="Courier">(fmap f [minBound..maxBound]) )</font></div><div><font class="Apple-style-span" face="Courier">-- A map instance could be better: we trade some serialization time for more</font></div><div><font class="Apple-style-span" face="Courier">-- deserialization time. </font></div><div><font class="Apple-style-span" face="Courier">instance (Serialize a, Serialize b) => Serialize (Map a b) where ...</font></div><div><font class="Apple-style-span" face="Courier"><br></font></div><div><font class="Apple-style-span" face="Courier">instance (Serialize a, Serialize b) => Serialize (a -> b) where</font></div><div><font class="Apple-style-span" face="Courier"><span class="Apple-tab-span" style="white-space:pre"> </span>serialize f = serialize . fromList $ </font><span class="Apple-style-span" style="font-family: Courier; ">( zip [minBound..maxBound] </span></div><div><span class="Apple-tab-span" style="white-space: pre; "><font class="Apple-style-span" face="Courier"> </font></span><font class="Apple-style-span" face="Courier">(fmap f [minBound..maxBound]) )</font></div><div><font class="Apple-style-span" face="Courier"><span class="Apple-tab-span" style="white-space:pre"> </span>deserialize map = \x -> lookup x (bytestring_decode_map map)</font></div><div><font class="Apple-style-span" face="Courier"><span class="Apple-tab-span" style="white-space:pre"> </span> where bytestring_decode_map = ...</font></div><div><font class="Apple-style-span" face="Courier"><br></font></div><div>There are potentially big problems with this approach: </div><div>(i) Many data types are not instances of Enum (though the really should be. Deriving enumerations is not that hard. I am willing to take one for the team to get GHC to figure out how to derive Enum on arbitrary types, but I'm not sure where to start. Little help?)</div><div>(ii) Time and memory. We're not encoding a series of instructions for computing pure functions, but we're precomputing the results and saving them all for later. This is at least O(size of the domain) * O(of the function on each element). Not big in theoretical terms, but something like that could easily cause a factor of [1, \infty) slowdown in real code.</div><div>(iii) Serialized objects must be pure. In particular, you can't serialize general IO actions. I see this as a plus. It is still easy to write an algebra of serializable tokens and a non-serializable interpreter to generate IO actions from the tokens. We do this kind of thing all the time -- we just don't serialize the tokens usually.</div><div><br></div><div>I think (ii) is the biggest problem. And it is a big one. We basically need something like template haskell for runtime systems in order to do quasi-quoting and compilation at run-time so we can avoid reifying the domain and its image under f.</div><div><br></div><div>The only thing that can serialize an (IO a) is the Haskell runtime, and it does it by running the action (and so putting its sub-steps in a series). </div></body></html>