Serialization of (a -> b) and IO a

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
43 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Serialization of (a -> b) and IO a

Jesse Schalken
Is it possible to serialize and deserialize a function to/from binary form, perhaps using Data.Binary, for example? What about an IO action? If so, is there a way the serialized representation could be architecture-independent?

I have been shown how useful it can be to store functions inside data structures, and while looking at data serialization for the purpose of persistence I wondered "since functions are just values in Haskell, why can't we persist them, too?".

To me the idea has interesting implications. For example, an arbitrary program could simply be represented by a serialization of `IO ()`. In fact, you could load any program into memory from a file and use Control.Concurrent.forkIO to run it, and later kill it, giving you the beginnings of an operating environment. If such a serialization is architecture independent then to my understanding you have the beginnings of a virtual machine. You could break your program into pieces and store them in a database and load them when needed, or even pull updates to each piece individually from down the web etc, enabling interesting methods of software distribution. It would make very cool stuff possible.

I have had a look at hs-plugins, but it is unclear how to derive a simple pair of functions `(a -> b) -> ByteString` and `ByteString -> Either ParseError (a -> b)`, for example, from the functionality it provides, if it is possible at all. I guess such a thing requires thorough digging into the depths of GHC, (or maybe even LLVM if an architecture independent representation is sought, but I don't know enough to say.). Perhaps this is more a question for those interested and knowledgable in Haskell compilation (and, to some extent, decompilation).

If not Haskell, are there any languages which provide a simple serialization and deserialization of functions?

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Luke Palmer-2
On Thu, Nov 11, 2010 at 12:53 AM, Jesse Schalken
<[hidden email]> wrote:

> I have had a look at hs-plugins, but it is unclear how to derive a simple
> pair of functions `(a -> b) -> ByteString` and `ByteString -> Either
> ParseError (a -> b)`, for example, from the functionality it provides, if it
> is possible at all. I guess such a thing requires thorough digging into the
> depths of GHC, (or maybe even LLVM if
> an architecture independent representation is sought, but I don't know
> enough to say.). Perhaps this is more a question for those interested and
> knowledgable in Haskell compilation (and, to some extent, decompilation).
> If not Haskell, are there any languages which provide a simple serialization
> and deserialization of functions?

As far as I know, GHC has no support for this.  There are issues with
the idea that will come out pretty fast, such as:

    (1) Those cannot be pure functions, because it differentiate
denotationally equal functions.  So it would have to be at least (a ->
b) -> IO ByteString.
    (2) What if you tried to serialize a filehandle or an FFI Ptr?

But my answers are "Ok" and "Then you get a runtime error",
respectively.  It is by no means impossible, IIRC Clean does it.   I
think it's pretty dumb that we don't have support for this yet.
Purely functional languages have a unique disposition to be very good
at this.  But oh well, there aren't enough tuits for everything.

A more elaborate answer to (2) is "you get a runtime error when you
try to *use* the thing that was impossible to serialize".  This makes
sure that you don't get an error if you are trying to serialize \x ->
const x a_filehandle_or_something, which is just the identity
function.

Luke
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Alberto G. Corona
In reply to this post by Jesse Schalken
There are some straighforward tricks using the package eval (or hint)l.

This is more or less the idea in pseudocode:

type FuncExpr= String

data F a = F FuncExpr a

apply (F _ f) x= f x

instance Show (F a) where show (F str _)= str

instance Read (F a) where read (F str f)= eval f >>= F str



2010/11/11 Jesse Schalken <[hidden email]>
Is it possible to serialize and deserialize a function to/from binary form, perhaps using Data.Binary, for example? What about an IO action? If so, is there a way the serialized representation could be architecture-independent?

I have been shown how useful it can be to store functions inside data structures, and while looking at data serialization for the purpose of persistence I wondered "since functions are just values in Haskell, why can't we persist them, too?".

To me the idea has interesting implications. For example, an arbitrary program could simply be represented by a serialization of `IO ()`. In fact, you could load any program into memory from a file and use Control.Concurrent.forkIO to run it, and later kill it, giving you the beginnings of an operating environment. If such a serialization is architecture independent then to my understanding you have the beginnings of a virtual machine. You could break your program into pieces and store them in a database and load them when needed, or even pull updates to each piece individually from down the web etc, enabling interesting methods of software distribution. It would make very cool stuff possible.

I have had a look at hs-plugins, but it is unclear how to derive a simple pair of functions `(a -> b) -> ByteString` and `ByteString -> Either ParseError (a -> b)`, for example, from the functionality it provides, if it is possible at all. I guess such a thing requires thorough digging into the depths of GHC, (or maybe even LLVM if an architecture independent representation is sought, but I don't know enough to say.). Perhaps this is more a question for those interested and knowledgable in Haskell compilation (and, to some extent, decompilation).

If not Haskell, are there any languages which provide a simple serialization and deserialization of functions?

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Alberto G. Corona
nstance Read (F a) where read str= eval str >>= F str

sorry

2010/11/11 Alberto G. Corona <[hidden email]>
There are some straighforward tricks using the package eval (or hint)l.

This is more or less the idea in pseudocode:

type FuncExpr= String

data F a = F FuncExpr a

apply (F _ f) x= f x

instance Show (F a) where show (F str _)= str

instance Read (F a) where read (F str f)= eval f >>= F str



2010/11/11 Jesse Schalken <[hidden email]>
Is it possible to serialize and deserialize a function to/from binary form, perhaps using Data.Binary, for example? What about an IO action? If so, is there a way the serialized representation could be architecture-independent?

I have been shown how useful it can be to store functions inside data structures, and while looking at data serialization for the purpose of persistence I wondered "since functions are just values in Haskell, why can't we persist them, too?".

To me the idea has interesting implications. For example, an arbitrary program could simply be represented by a serialization of `IO ()`. In fact, you could load any program into memory from a file and use Control.Concurrent.forkIO to run it, and later kill it, giving you the beginnings of an operating environment. If such a serialization is architecture independent then to my understanding you have the beginnings of a virtual machine. You could break your program into pieces and store them in a database and load them when needed, or even pull updates to each piece individually from down the web etc, enabling interesting methods of software distribution. It would make very cool stuff possible.

I have had a look at hs-plugins, but it is unclear how to derive a simple pair of functions `(a -> b) -> ByteString` and `ByteString -> Either ParseError (a -> b)`, for example, from the functionality it provides, if it is possible at all. I guess such a thing requires thorough digging into the depths of GHC, (or maybe even LLVM if an architecture independent representation is sought, but I don't know enough to say.). Perhaps this is more a question for those interested and knowledgable in Haskell compilation (and, to some extent, decompilation).

If not Haskell, are there any languages which provide a simple serialization and deserialization of functions?

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Stephen Tetley-2
In reply to this post by Jesse Schalken
> If not Haskell, are there any languages which provide a simple serialization
> and deserialization of functions?

Napier88 was a persistent language that also had higher-order
functions. I've no experience other than reading about it but as its
persistence was "orthogonal persistence" I'd expect HOFs to be
persistent. The implementation of Napier88 produced a substantial
runtime / persistent store that was used for other languages - I think
one was Persistent Haskell, certainly one was Staple which was a
higher order language.

Tycoon2 was a similar persistent language - it was heavily influenced
by ML so potentially it had HOFs.

PolyML has a persistent store, though this may have been just for the
top-level to freeze bindings I've no idea whether it supported
serializing HOFs.

Clean supports serialized HOFs as does Oz, see the paper below. Kali
Scheme supported migration of running code between networked computers
- as it was a Scheme I'd expect it to be higher order (the migration
would mandate serialization).


http://www-systems.cs.st-andrews.ac.uk/wiki/Napier88
http://www.polyml.org/FAQ.html
http://www.st.cs.ru.nl/papers/2003/verm2003-LazyDynamicIO.pdf
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Thomas Davie
In reply to this post by Luke Palmer-2

On 11 Nov 2010, at 08:36, Luke Palmer wrote:

> On Thu, Nov 11, 2010 at 12:53 AM, Jesse Schalken
> <[hidden email]> wrote:
>> I have had a look at hs-plugins, but it is unclear how to derive a simple
>> pair of functions `(a -> b) -> ByteString` and `ByteString -> Either
>> ParseError (a -> b)`, for example, from the functionality it provides, if it
>> is possible at all. I guess such a thing requires thorough digging into the
>> depths of GHC, (or maybe even LLVM if
>> an architecture independent representation is sought, but I don't know
>> enough to say.). Perhaps this is more a question for those interested and
>> knowledgable in Haskell compilation (and, to some extent, decompilation).
>> If not Haskell, are there any languages which provide a simple serialization
>> and deserialization of functions?
>
> As far as I know, GHC has no support for this.  There are issues with
> the idea that will come out pretty fast, such as:
>
>    (1) Those cannot be pure functions, because it differentiate
> denotationally equal functions.  So it would have to be at least (a ->
> b) -> IO ByteString.

I don't think I agree, I didn't see a rule f == g => serialise f == serialise g anywhere.

Bob_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Max Rabkin-2
On Thu, Nov 11, 2010 at 11:25, Bob <[hidden email]> wrote:
> I don't think I agree, I didn't see a rule f == g => serialise f == serialise g anywhere.

The rule a == b => f a == f b is called referential transparency (for
denotational equality, not Eq) and is (perhaps the most important)
part of what is meant by "purely functional".

--Max
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Dan Doel
In reply to this post by Thomas Davie
On Thursday 11 November 2010 4:25:46 am Thomas Davie wrote:
> I don't think I agree, I didn't see a rule f == g => serialise f ==
> serialise g anywhere.

That equal things can be substituted for one another is one of the fundamental
ideas of equality (the other is that anything is equal to itself). In fact, in
second order logic, equality can be *defined* as (roughly):

  (x = y) means (forall P. P x -> P y)

That is, x is equal to y if all predicates satisfied by x are also satisfied
by y. Using this, one can derive other typical laws for equality. Transitivity
is pretty easy, but surprisingly, even symmetry can be gotten:

  If P z is z = x, using substitution we get x = x -> y = x,
  and x = x is trivially true.

And of course, we also get congruence:

  Given a function f, let P z be f x = f z,
  substitution yields f x = f x -> f x = f y,
  where f x = f x is again trivial.

The equality that people typically expect to hold for Haskell expressions is
that two such expressions are equal if they denote the same thing, as Max
said. Expressions with function type denote mathematical functions, and so if
we have something like:

  serialize :: (Integer -> Integer) -> String

it must be a mathematical function. Further, its arguments will denote
functions, to, and equality on mathematical functions can be given point-wise:

  f = g iff forall x. f x = g x

Now, here are two expressions with type (Integer -> Integer) that denote equal
functions:

  \x -> x + x
  \x -> 2 * x

So, for all this to work out, serialize must produce the same String for both
of those. But in general, it isn't possible to decide if two functions are
point-wise equal, let alone select a canonical representative for each
equivalence class of expressions that denote a particular function. So there's
no feasible way to implement serialize without breaking Haskell's semantics.

How making serialize :: (Integer -> Integer) -> IO String solves this? Well,
that's another story.

-- Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Sjoerd Visscher-2
> The equality that people typically expect to hold for Haskell expressions is
> that two such expressions are equal if they denote the same thing, as Max
> said. Expressions with function type denote mathematical functions, and so if
> we have something like:
>
>  serialize :: (Integer -> Integer) -> String
>
> it must be a mathematical function. Further, its arguments will denote
> functions, to, and equality on mathematical functions can be given point-wise:
>
>  f = g iff forall x. f x = g x
>
> Now, here are two expressions with type (Integer -> Integer) that denote equal
> functions:
>
>  \x -> x + x
>  \x -> 2 * x
>
> So, for all this to work out, serialize must produce the same String for both
> of those.

What I'm wondering is if it would actually break things if serialize would not produce the same String for these functions. The reasoning above is used regularly to shoot down some really useful functionality. So what would go wrong if we chose to take the practical path, and leave aside the theoretical issues?

Also, the above two functions might not be exactly denotationally equal if the type is (Float -> Float), or the speed or memory use might be different. Could it not be that requiring them to be equal could just as well break things?

greetings,
Sjoerd Visscher




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Gábor Lehel
On Thu, Nov 11, 2010 at 12:22 PM, Sjoerd Visscher <[hidden email]> wrote:

>> The equality that people typically expect to hold for Haskell expressions is
>> that two such expressions are equal if they denote the same thing, as Max
>> said. Expressions with function type denote mathematical functions, and so if
>> we have something like:
>>
>>  serialize :: (Integer -> Integer) -> String
>>
>> it must be a mathematical function. Further, its arguments will denote
>> functions, to, and equality on mathematical functions can be given point-wise:
>>
>>  f = g iff forall x. f x = g x
>>
>> Now, here are two expressions with type (Integer -> Integer) that denote equal
>> functions:
>>
>>  \x -> x + x
>>  \x -> 2 * x
>>
>> So, for all this to work out, serialize must produce the same String for both
>> of those.
>
> What I'm wondering is if it would actually break things if serialize would not produce the same String for these functions. The reasoning above is used regularly to shoot down some really useful functionality. So what would go wrong if we chose to take the practical path, and leave aside the theoretical issues?

Yeah, my sense -- but correct my if I'm reading the original post
incorrectly -- is that the whole thing with function equality is a
distraction and not really relevant here.

It is true that (a) per Luke Palmer, if we could serialize equal
functions to equal representations then we could we could decide
whether two pure functions were equal, which (if not done in the IO
monad) would(?) break purity; and (b) per Dan Doel, if we wanted to
implement our serialization in a way so that equal functions get equal
representations, we couldn't do it, because it's an impossible
problem.

But these sort of cancel each other out, because (a) it's an
impossible problem, and (b) we don't want to do it.

A function which does "x+x" would simply be serialized as doing x+x,
and a function which does "x*2" would be serialized as doing x*2, and
when deserialized the resulting functions would continue to do those
things, and it would be completely agnostic and indifferent as to
whether or not they are in fact equal.

Obviously there are questions here with regards to the functions which
the to-be-serialized function makes use of -- should they be
serialized along with it? Required to be present when it is
deserialized? Is it OK for the function to do something different when
it is loaded compared to when it was stored if its environment is
different, or not OK?

>
> Also, the above two functions might not be exactly denotationally equal if the type is (Float -> Float), or the speed or memory use might be different. Could it not be that requiring them to be equal could just as well break things?
>
> greetings,
> Sjoerd Visscher
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



--
Work is punishment for failing to procrastinate effectively.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Jesse Schalken
2010/11/11 Gábor Lehel <[hidden email]>
Obviously there are questions here with regards to the functions which
the to-be-serialized function makes use of -- should they be
serialized along with it? Required to be present when it is
deserialized? Is it OK for the function to do something different when
it is loaded compared to when it was stored if its environment is
different, or not OK?

I would have say Yes, No, No. At the moment, when you serialise data structure A which references data structure B which references data structure C, using Data.Binary for example, the whole lot (A, B, and C) gets serialised, so that the resulting deserialization of A is denotationally equivalent to the original, regardless of the environment. I don't see why this shouldn't be the case for functions also. 

So a serialized function should include all its direct and indirect callees. This might result in potentially simple functions ending up enormous when serialized, simply because the call graph, including all it's libraries and their libraries etc, is that size, but such would be pure function serialization.

This raises the question of what is left. The assembled machine code? For the architecture of the serializer or of the deserializer? Or LLVM IR for architecture independence? C--? Core? I don't know, but it would be awesome for the serialized representation to be both low-level and architecture independent, then having it JIT compiled when it is deserialized. To me, this means a virtual machine, which I guess is what you need when you want fast mobile code, but I'm just musing here as I know little about programming language implementation. 

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Gábor Lehel
On Thu, Nov 11, 2010 at 2:15 PM, Jesse Schalken <[hidden email]> wrote:

> 2010/11/11 Gábor Lehel <[hidden email]>
>>
>> Obviously there are questions here with regards to the functions which
>> the to-be-serialized function makes use of -- should they be
>> serialized along with it? Required to be present when it is
>> deserialized? Is it OK for the function to do something different when
>> it is loaded compared to when it was stored if its environment is
>> different, or not OK?
>
> I would have say Yes, No, No. At the moment, when you serialise data
> structure A which references data structure B which references data
> structure C, using Data.Binary for example, the whole lot (A, B, and C) gets
> serialised, so that the resulting deserialization of A is
> denotationally equivalent to the original, regardless of the environment. I
> don't see why this shouldn't be the case for functions also.
> So a serialized function should include all its direct and indirect callees.
> This might result in potentially simple functions ending up enormous when
> serialized, simply because the call graph, including all it's libraries and
> their libraries etc, is that size, but such would be pure function
> serialization.
> This raises the question of what is left. The assembled machine code? For
> the architecture of the serializer or of the deserializer? Or LLVM IR
> for architecture independence? C--? Core? I don't know, but it would be
> awesome for the serialized representation to be both low-level and
> architecture independent, then having it JIT compiled when it is
> deserialized. To me, this means a virtual machine, which I guess is what you
> need when you want fast mobile code, but I'm just musing here as I know
> little about programming language implementation.

I'm not an expert here either, I'll just note that LLVM is only
platform independent to a degree. Or rather, I believe the situation
is that it *is* architecture independent, but it doesn't abstract
anything else besides the architecture -- so if you have any other
differences, it's not going to work. LLVM IR doesn't do #ifdefs.

> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>



--
Work is punishment for failing to procrastinate effectively.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Malcolm Wallace-2
> I'll just note that LLVM is only
> platform independent to a degree. Or rather, I believe the situation
> is that it *is* architecture independent, but it doesn't abstract
> anything else besides the architecture

In particular, imagine how you might serialise a Haskell function  
which is an FFI binding to some external platform-specific library  
(e.g. Posix, Win32, Gtk+, WPF), such that you could save it on a  
Windows machine, copy to Linux or Mac, and start it running again.

Regards,
     Malcolm
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Gábor Lehel
On Thu, Nov 11, 2010 at 2:29 PM, Malcolm Wallace <[hidden email]> wrote:
>> I'll just note that LLVM is only
>> platform independent to a degree. Or rather, I believe the situation
>> is that it *is* architecture independent, but it doesn't abstract
>> anything else besides the architecture
>
> In particular, imagine how you might serialise a Haskell function which is
> an FFI binding to some external platform-specific library (e.g. Posix,
> Win32, Gtk+, WPF), such that you could save it on a Windows machine, copy to
> Linux or Mac, and start it running again.

...and FFI imports are something you definitely can't serialize, so
that's one case where you either have it say "call the linked-in
function with the name 'whatever'" and hope it's the same one, or just
disallow it entirely.


>
> Regards,
>    Malcolm
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



--
Work is punishment for failing to procrastinate effectively.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Dan Doel
In reply to this post by Sjoerd Visscher-2
On Thursday 11 November 2010 6:22:06 am Sjoerd Visscher wrote:
> What I'm wondering is if it would actually break things if serialize would
> not produce the same String for these functions.

Yes. It would break the (usual) mathematical underpinnings of Haskell.

> The reasoning above is used regularly to shoot down some really useful
> functionality. So what would go wrong if we chose to take the practical
> path, and leave aside the theoretical issues?

You would lose many uses of equational reasoning in your programs. Have you
every substituted 'x * 2' for the expression 'x + x' in one of your programs,
or vice versa? You can no longer do that, because someone may be serializing
the function you're writing, checking how it's implemented, and relying it.

You'd lose the whole notion of 'the category of haskell types and functions'
goodbye, too. Does f . id = f? Not if the former serializes as "f . id". We
already have a weak case of this, since (\x -> undefined x) can be
distinguished from undefined using seq, but that can be hand-waved away by not
worrying about bottoms so much. That isn't going to work for serialize. There
does exist practical Haskell stuff from category theory inspired people.

As a digression... When you get into things like dependent type theory,
equality is actually incorporated into the language in a much more direct way.
And there are various sorts of equality you can add to your type theory. Two
common choices are:

  intensional equality: two values are provably equal if they evaluate to the
  same normal form

  extensional equality: this incorporates non-computational rules, like the
  point-wise equality of functions.

Now, in a type theory where equality is intensional, I cannot prove:

  (forall x. f x = g x) -> f = g

However, both these equalities (and others in between and on either side) are
*compatible*, in that I cannot disprove the above theorem in an intensional
theory.

What seq and serialize do is break from extensional equality, and allow us to
disprove the above (perhaps not for seq within a hypothetical theory, since
the invalidating case involves non-termination, but certainly for serialize).
And that's a big deal, because extensional equality is handy for the above
reasoning about programs.

> Also, the above two functions might not be exactly denotationally equal if
> the type is (Float -> Float), or the speed or memory use might be
> different. Could it not be that requiring them to be equal could just as
> well break things?

I would not be at all surprised if they are unequal for Float -> Float,
considering how ugly floating point types are. That doesn't justify breaking
equality for every other type.

Speed and memory use are typically disregarded for equality of (expressions
denoting) functions. Merge sort and bubble sort are two algorithms for
computing the same function, even though they vary wildly in these two
characteristics. If you want a calculus for precisely reasoning about resource
usage, then you would not necessarily be able to consider these equal.

But, Haskell is simply not such a calculus, and I don't think, "what if it
were," is a good argument for actively breaking extensional equality in such a
dramatic way (since the breakage would have nothing to do with precise
reasoning about resource usage).

Gábor Lehel wrote:

> It is true that (a) per Luke Palmer, if we could serialize equal
> functions to equal representations then we could we could decide
> whether two pure functions were equal, which (if not done in the IO
> monad) would(?) break purity; and (b) per Dan Doel, if we wanted to
> implement our serialization in a way so that equal functions get equal
> representations, we couldn't do it, because it's an impossible
> problem.
>
> But these sort of cancel each other out, because (a) it's an
> impossible problem, and (b) we don't want to do it.

They do not cancel each other out. Rather, it goes like this:

a) Serializing functions gives you a decision procedure for function equality.
b) It is impossible to decide extensional equality of functions.

Together, these mean that any serialization procedure you define is *wrong*,
in that it violates the semantics of pure Haskell expressions (the resulting
decision procedure will answer 'False' for some pair of extensionally equal
expressions f and g).

The way IO can get around this is that when you have:

  serialize (\x -> x + x :: Integer) :: IO String
  serialize (\x -> 2 * x :: Integer) :: IO String

you can say that the two IO actions are equal in the following sense:

  1) There is an equivalence class of expressions denoting the function in
     question. This equivalence class contains (\x -> x + x) and
     (\x -> 2 * x)
  2) The IO action produced by serialize selects a string representation
     for one of these expressions at random*.
    *) You probably won't ever observe "\x -> x + x" being the output of
       (serialize (\x -> 2 * x)), but that's just a coincidence.

This explanation is not available if serialize has type
(Integer -> Integer) -> String, however. Those have to be mathematical
functions (of a sort) that select a unique representation for each equivalence
class, or else we have to get a completely different (and much less nice)
denotational semantics for Haskell.

----

Perhaps I missed it, but: has anyone explained why:

  (a -> b) -> IO String

is an unacceptable type? Why does it need to be just String? Folks often ask,
"what benefit is purity?" Well, what is the benefit of making this function
impure? GHC has a lot of normally impure functionality incorporated in a way
that is mathematically sound (though not ideal). What are the things that have
been shot down? Or does IO, ST, etc. qualify as getting shot down?

-- Dan
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Ketil Malde-5
Dan Doel <[hidden email]> writes:

> You'd lose the whole notion of 'the category of haskell types and functions'
> goodbye, too. Does f . id = f? Not if the former serializes as "f . id".

..and you are able to tell the difference.  Am I wrong in thinking that
this could be made to work if serialization was to/from an opaque type
instead of (Byte)String, so that the *only* operations would be
serialization and deserialization (and possibly storing to/from file)?

-k
--
If I haven't seen further, it is by standing in the footprints of giants
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Casey McCann-2
On Thu, Nov 11, 2010 at 10:53 AM, Ketil Malde <[hidden email]> wrote:
> ..and you are able to tell the difference.  Am I wrong in thinking that
> this could be made to work if serialization was to/from an opaque type
> instead of (Byte)String, so that the *only* operations would be
> serialization and deserialization (and possibly storing to/from file)?

This was my first thought as well! However, reading to/from a file
would of course be in IO, at which point you'd be free to read the
file back in through normal means to get at the representation. So in
that respect, this is equivalent to (a -> b) -> IO String.

Outside of IO, it would pretty much have to be limited to serializing
and deserializing. You'd be able to create opaque tokens representing
functions, pass them around, and/or extract the function in order to
apply it. Conveniently, it turns out that Haskell already has support
for this, you can implement it as follows:

> module Serialize.Pure (OpaqueFunction, serialize, deserialize) where
>
> newtype OpaqueFunction a b = Opaque { deserialize :: a -> b }
>
> serialize = Opaque

Toss in some existential types as desired, if you want to hide the
function's actual type.

I suppose one could object that this isn't actually serializing
anything at all; to which I would respond that, in pure code, how do
you expect to tell the difference?

- C.
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Sjoerd Visscher-2
In reply to this post by Dan Doel
On Nov 11, 2010, at 3:36 PM, Dan Doel wrote:

> On Thursday 11 November 2010 6:22:06 am Sjoerd Visscher wrote:
>
>> The reasoning above is used regularly to shoot down some really useful
>> functionality. So what would go wrong if we chose to take the practical
>> path, and leave aside the theoretical issues?
>
> You would lose many uses of equational reasoning in your programs. Have you
> every substituted 'x * 2' for the expression 'x + x' in one of your programs,
> or vice versa? You can no longer do that, because someone may be serializing
> the function you're writing, checking how it's implemented, and relying it.


Yes, but it would not break any existing code. It would only break code that knowingly did the wrong thing.

> We already have a weak case of this, since (\x -> undefined x) can be
> distinguished from undefined using seq, but that can be hand-waved away by not
> worrying about bottoms so much. That isn't going to work for serialize.

Why not?

--
Sjoerd Visscher
http://w3future.com




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

John Lato-2
In reply to this post by Jesse Schalken
From: Sjoerd Visscher <[hidden email]>

On Nov 11, 2010, at 3:36 PM, Dan Doel wrote:

> On Thursday 11 November 2010 6:22:06 am Sjoerd Visscher wrote:
>
>> The reasoning above is used regularly to shoot down some really useful
>> functionality. So what would go wrong if we chose to take the practical
>> path, and leave aside the theoretical issues?
>
> You would lose many uses of equational reasoning in your programs. Have you
> every substituted 'x * 2' for the expression 'x + x' in one of your programs,
> or vice versa? You can no longer do that, because someone may be serializing
> the function you're writing, checking how it's implemented, and relying it.


Yes, but it would not break any existing code. It would only break code that knowingly did the wrong thing.

> We already have a weak case of this, since (\x -> undefined x) can be
> distinguished from undefined using seq, but that can be hand-waved away by not
> worrying about bottoms so much. That isn't going to work for serialize.

Why not?

I don't know to what extent it would apply in this hypothetical situation, but ghc (and probably other compilers) rely upon Haskell's semantics in performing various code transformations.  If you break the semantics some transformations become invalid, resulting in incorrect code.

I've experienced this with code that violated ref. transparency.  The program behavior changed depending on the compiler's optimization settings.  I'm not keen to go back to that.

I think the only way this would work would be if you consider functions to be equal only to themselves, i.e. "x+x" and "2*x" are not equal.  That's not a trade-off I would be willing to make.

John

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Serialization of (a -> b) and IO a

Sjoerd Visscher-2

On Nov 11, 2010, at 6:34 PM, John Lato wrote:

> I don't know to what extent it would apply in this hypothetical situation, but ghc (and probably other compilers) rely upon Haskell's semantics in performing various code transformations.  If you break the semantics some transformations become invalid, resulting in incorrect code.
>
> I've experienced this with code that violated ref. transparency.  The program behavior changed depending on the compiler's optimization settings.  I'm not keen to go back to that.

Then don't do that. Being able to serialize functions is just as dangerous as having unsafePerformIO. If you don't use it, you don't have problems.

--
Sjoerd Visscher
http://w3future.com




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
123