Chinese whisper problem

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Michał Ptaszek
I guess you all know about Chinese whispers.

You send a whispered message round a circle and see if you get the same
message back.

The computer variant is as follows:

Send a complex data structure round a circle, and see if you get the same
message back.

The circle is a ring of processes written in *different* programming
languages.
The message is a complex message, containing primitives such as integers,
booleans
and strings and constructed types "sequence of" "tuple of" etc.

Messages are sent over sockets. I want each language to unpack the message
into the
internal form that is appropriate for that form, and then reconstruct the
message from the internal form.

This is something that I think *should be very easy* but is in fact very
difficult.

In a previous post I outlined how Erlang could talk to javascript but this
method is not  simple
and not compete - it would break done, for example if the integers were
bignums.

What should we use for the internal form? JSON is untyped so will give us
lots of problems.
ASN.1 is great but badly supported in many PLs - xml? - but the schemas are
horrible.
Thrift? - Google protocol buffers ... some kind of self-describing binary
format would seem
appropriate - bert for example.

I really would be nice to solve this problem is the simplest possible way
so that it
was very easy to send whispers round a circle and get back what you sent.

/Joe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111125/04ce5a28/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Attila Rajmund Nohl-2
2011/11/25, Joe Armstrong <erlang>:
[...]
> In a previous post I outlined how Erlang could talk to javascript but this
> method is not  simple
> and not compete - it would break done, for example if the integers were
> bignums.

As a consequence, the "over the network" format should specify the
types in details.

> What should we use for the internal form? JSON is untyped so will give us
> lots of problems.
> ASN.1 is great but badly supported in many PLs - xml? - but the schemas are
> horrible.
> Thrift? - Google protocol buffers ... some kind of self-describing binary
> format would seem
> appropriate - bert for example.

What about CORBA? Maybe an overkill, but the IDL specification is quite strict.


Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Bob Ippolito-2
In reply to this post by Michał Ptaszek
On Friday, November 25, 2011, Joe Armstrong <erlang> wrote:
> I guess you all know about Chinese whispers.
> You send a whispered message round a circle and see if you get the same
> message back.
> The computer variant is as follows:
> Send a complex data structure round a circle, and see if you get the same
message back.
> The circle is a ring of processes written in *different* programming
languages.
> The message is a complex message, containing primitives such as integers,
booleans
> and strings and constructed types "sequence of" "tuple of" etc.
> Messages are sent over sockets. I want each language to unpack the
message into the
> internal form that is appropriate for that form, and then reconstruct the
message from the internal form.
> This is something that I think *should be very easy* but is in fact very
difficult.
> In a previous post I outlined how Erlang could talk to javascript but
this method is not  simple
> and not compete - it would break done, for example if the integers were
bignums.
> What should we use for the internal form? JSON is untyped so will give us
lots of problems.
> ASN.1 is great but badly supported in many PLs - xml? - but the schemas
are horrible.
> Thrift? - Google protocol buffers ... some kind of self-describing binary
format would seem
> appropriate - bert for example.
> I really would be nice to solve this problem is the simplest possible way
so that it
> was very easy to send whispers round a circle and get back what you sent.

If you simply consider JSON to not support bignums, then there is no data
lost in the interchange once you've given up on representations that don't
have a 1:1 mapping to JSON. JSON isn't really the problem, it is typed it
just doesn't have all of the types you may want in the spec but that
doesn't stop you from extending objects to carry other types (see
JSON-RPC), Bert does this a bit too. The problem is then simply how to
meaningfully deal with these things in N languages, but for your use case
you could cheat and not try and do anything meaningful.

I can't imagine an interchange format that was everything to every
language, but you can certainly define subsets that represent a common
denominator that is good enough for many purposes. For example, in Python
it's valid to have a loop in your object graph and serialize it with
marshal or pickle, but there's not an obvious representation for that in a
functional language like Erlang. Consider: lst = []; lst.append(lst)

-bob
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111125/38b2f7fe/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Samuel Elliott
Has anyone taken a look at BSON? It was created by the mongodb project
to overcome some of the problems they were having with regular JSON
(like not enough data types).

I don't know if there's a parser for it in every language, but there
is in quite a few (there are two erlang ones they say on
http://bsonspec.org/ )

Sam

On Fri, Nov 25, 2011 at 8:49 PM, Bob Ippolito <bob> wrote:

> On Friday, November 25, 2011, Joe Armstrong <erlang> wrote:
>> I guess you all know about Chinese whispers.
>> You send a whispered message round a circle and see if you get the same
>> message back.
>> The computer variant is as follows:
>> Send a complex data structure round a circle, and see if you get the same
>> message back.
>> The circle is a ring of processes written in *different* programming
>> languages.
>> The message is a complex message, containing primitives such as integers,
>> booleans
>> and strings?and constructed types "sequence of" "tuple of" etc.
>> Messages are sent over sockets. I want each language to unpack the message
>> into the
>> internal form that is appropriate for that form,?and then reconstruct the
>> message from the internal form.
>> This is something that I think *should be very easy* but is in fact very
>> difficult.
>> In a previous post I outlined how Erlang could talk to javascript but this
>> method is not ?simple
>> and not compete - it would break done, for example if the integers were
>> bignums.
>> What should we use for the internal form? JSON is untyped so will give us
>> lots of problems.
>> ASN.1 is great but badly supported in many PLs - xml? - but the schemas
>> are horrible.
>> Thrift? - Google protocol buffers ... some kind of self-describing binary
>> format would seem
>> appropriate - bert for example.
>> I really would be nice to solve this problem is the simplest possible way
>> so that it
>> was very easy to send whispers round a circle and get back what you sent.
>
> If you simply consider JSON to not support bignums, then there is no data
> lost in the interchange once you've given up on representations that don't
> have a 1:1 mapping to JSON. JSON isn't really the problem, it is typed it
> just doesn't have all of the types you may want in the spec but that doesn't
> stop you from extending objects to carry other types (see JSON-RPC), Bert
> does this a bit too. The problem is then simply how to meaningfully deal
> with these things in N languages, but for your use case you could cheat and
> not try and do anything meaningful.
>
> I can't imagine an interchange format that was everything to every language,
> but you can certainly define subsets that represent a common denominator
> that is good enough for many purposes. For example, in Python it's valid to
> have a loop in your object graph and serialize it with marshal or pickle,
> but there's not an obvious representation for that in a functional language
> like Erlang. Consider: lst = []; lst.append(lst)
>
> -bob
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions
>
>



--
Samuel Elliott
sam
http://lenary.co.uk/
+44 (0)7891 993 664


Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Robert Virding-5
In reply to this post by Michał Ptaszek
Joe, do you expect all the data to have meaning in all the languages it passes through? Or would it be enough to jut be able to pass on that which cannot be understood?

Robert

----- Original Message -----

> I guess you all know about Chinese whispers.

> You send a whispered message round a circle and see if you get the
> same
> message back.

> The computer variant is as follows:

> Send a complex data structure round a circle, and see if you get the
> same message back.

> The circle is a ring of processes written in *different* programming
> languages.
> The message is a complex message, containing primitives such as
> integers, booleans
> and strings and constructed types "sequence of" "tuple of" etc.

> Messages are sent over sockets. I want each language to unpack the
> message into the
> internal form that is appropriate for that form, and then reconstruct
> the message from the internal form.

> This is something that I think *should be very easy* but is in fact
> very difficult.

> In a previous post I outlined how Erlang could talk to javascript but
> this method is not simple
> and not compete - it would break done, for example if the integers
> were bignums.

> What should we use for the internal form? JSON is untyped so will
> give us lots of problems.
> ASN.1 is great but badly supported in many PLs - xml? - but the
> schemas are horrible.
> Thrift? - Google protocol buffers ... some kind of self-describing
> binary format would seem
> appropriate - bert for example.

> I really would be nice to solve this problem is the simplest possible
> way so that it
> was very easy to send whispers round a circle and get back what you
> sent.

> /Joe

> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111127/4de74d4a/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

Anthony Molinaro
In reply to this post by Michał Ptaszek
On Fri, Nov 25, 2011 at 04:18:09PM +0100, Joe Armstrong wrote:
> I guess you all know about Chinese whispers.
>
> You send a whispered message round a circle and see if you get the same
> message back.
>
> The computer variant is as follows:
>
> Send a complex data structure round a circle, and see if you get the same
> message back.

Sorry I'm late to the party with this one, but was out of town for a bit.

I have used thrift, protobuffs and lwes to do binary multi-language
message exchange, which is not quite the whispers problem but close.
They all contain serializers and deserializers and each support different
sorts of things.

Thrift is mainly meant for RPC, so if all you want is a binary serialization
format, it's a bit tricky (mostly in erlang, less so in java), in that you
have to create a memory serializer and construct the terms then do a
term_to_binary on them, to get a binary you could do what you want with.
On the other hand it supports many languages (include erlang and javascript),
and several protocols (sockets and http being the most common).  It can have
fairly complex structures like maps (which become dict's in erlang), lists,
different sized ints, floats, etc.

Protobufs also off fairly complex structures (although not maps, you sort of
have to do those yourself with repeated structures which will become lists
of records, so not quite as useful), as well as strings, ints, floats and
binary data.  It does not include any RPC based mechanism, and you basically
get serializers/deserializers which get/give binaries, so you can use it
with whatever you want.  Riak uses this as its faster interface via a socket
and I've implemented server to server communication over HTTP which is
easy.

LWES (http://lwes.github.com/) is a system and protocol I first developed
in 1998 and which was open sourced in 2008.  It's mostly meant for passing
maps in a fire and forget fashion over UDP (or multicast UDP), it's a bit
bulkier on the wire than thrift and protobuffs as the serialization format
is self describing (key names are sent along with values).  It also only
has support in java for floats and arrays (but those will probably make
their way into the other languages as time permits).  It currently
has native bindings for C, erlang, java, and .Net, as well as SWIG based
bindings for perl, python and ruby.  It's a great system for quickly
passing maps between different programming languages where you can afford
to loose some data here or there.  Also, unlike thrift/protobuff it does
not require any precompilation of modules.  While we don't have a javascript
version yet, we may be developing one soon (although it most likely won't
be able to do UDP from a javascript client which is unfortunate).  LWES
is extremely stable and has been in production systems serving trillions
of events for almost 13 years (every penny ever made by Goto/Overture/Yahoo's
search advertising system was via lwes).

I've used all three of these systems in production web systems so can attest
that they all work and at large scale (ten's of thousands to hundred's of
thousands of requests per second).

I've not used Bert, BSON, Avro, MessagePack or Etch all of which do
similiar things but offer slightly different feature sets.

Hope that helps,

-Anthony

--
------------------------------------------------------------------------
Anthony Molinaro                           <anthonym>


Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

envelopes envelopes-2
I remember there is also messagepack that supports erlang, It has good
performance.

In addition, there is Avro.
On Nov 30, 2011 3:07 PM, "Anthony Molinaro" <anthonym>
wrote:

> On Fri, Nov 25, 2011 at 04:18:09PM +0100, Joe Armstrong wrote:
> > I guess you all know about Chinese whispers.
> >
> > You send a whispered message round a circle and see if you get the same
> > message back.
> >
> > The computer variant is as follows:
> >
> > Send a complex data structure round a circle, and see if you get the same
> > message back.
>
> Sorry I'm late to the party with this one, but was out of town for a bit.
>
> I have used thrift, protobuffs and lwes to do binary multi-language
> message exchange, which is not quite the whispers problem but close.
> They all contain serializers and deserializers and each support different
> sorts of things.
>
> Thrift is mainly meant for RPC, so if all you want is a binary
> serialization
> format, it's a bit tricky (mostly in erlang, less so in java), in that you
> have to create a memory serializer and construct the terms then do a
> term_to_binary on them, to get a binary you could do what you want with.
> On the other hand it supports many languages (include erlang and
> javascript),
> and several protocols (sockets and http being the most common).  It can
> have
> fairly complex structures like maps (which become dict's in erlang), lists,
> different sized ints, floats, etc.
>
> Protobufs also off fairly complex structures (although not maps, you sort
> of
> have to do those yourself with repeated structures which will become lists
> of records, so not quite as useful), as well as strings, ints, floats and
> binary data.  It does not include any RPC based mechanism, and you
> basically
> get serializers/deserializers which get/give binaries, so you can use it
> with whatever you want.  Riak uses this as its faster interface via a
> socket
> and I've implemented server to server communication over HTTP which is
> easy.
>
> LWES (http://lwes.github.com/) is a system and protocol I first developed
> in 1998 and which was open sourced in 2008.  It's mostly meant for passing
> maps in a fire and forget fashion over UDP (or multicast UDP), it's a bit
> bulkier on the wire than thrift and protobuffs as the serialization format
> is self describing (key names are sent along with values).  It also only
> has support in java for floats and arrays (but those will probably make
> their way into the other languages as time permits).  It currently
> has native bindings for C, erlang, java, and .Net, as well as SWIG based
> bindings for perl, python and ruby.  It's a great system for quickly
> passing maps between different programming languages where you can afford
> to loose some data here or there.  Also, unlike thrift/protobuff it does
> not require any precompilation of modules.  While we don't have a
> javascript
> version yet, we may be developing one soon (although it most likely won't
> be able to do UDP from a javascript client which is unfortunate).  LWES
> is extremely stable and has been in production systems serving trillions
> of events for almost 13 years (every penny ever made by
> Goto/Overture/Yahoo's
> search advertising system was via lwes).
>
> I've used all three of these systems in production web systems so can
> attest
> that they all work and at large scale (ten's of thousands to hundred's of
> thousands of requests per second).
>
> I've not used Bert, BSON, Avro, MessagePack or Etch all of which do
> similiar things but offer slightly different feature sets.
>
> Hope that helps,
>
> -Anthony
>
> --
> ------------------------------------------------------------------------
> Anthony Molinaro                           <anthonym>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111130/0c33bfc5/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Chinese whisper problem

邢森-2
protobufs, thrift and other "human-readable binary protocol" is the
best choice,small
message packets,decoding and encoding fast speed is fast.

2011/12/1 envelopes envelopes <sunwood360>

> I remember there is also messagepack that supports erlang, It has good
> performance.
>
> In addition, there is Avro.
> On Nov 30, 2011 3:07 PM, "Anthony Molinaro" <anthonym>
> wrote:
>
>> On Fri, Nov 25, 2011 at 04:18:09PM +0100, Joe Armstrong wrote:
>> > I guess you all know about Chinese whispers.
>> >
>> > You send a whispered message round a circle and see if you get the same
>> > message back.
>> >
>> > The computer variant is as follows:
>> >
>> > Send a complex data structure round a circle, and see if you get the
>> same
>> > message back.
>>
>> Sorry I'm late to the party with this one, but was out of town for a bit.
>>
>> I have used thrift, protobuffs and lwes to do binary multi-language
>> message exchange, which is not quite the whispers problem but close.
>> They all contain serializers and deserializers and each support different
>> sorts of things.
>>
>> Thrift is mainly meant for RPC, so if all you want is a binary
>> serialization
>> format, it's a bit tricky (mostly in erlang, less so in java), in that you
>> have to create a memory serializer and construct the terms then do a
>> term_to_binary on them, to get a binary you could do what you want with.
>> On the other hand it supports many languages (include erlang and
>> javascript),
>> and several protocols (sockets and http being the most common).  It can
>> have
>> fairly complex structures like maps (which become dict's in erlang),
>> lists,
>> different sized ints, floats, etc.
>>
>> Protobufs also off fairly complex structures (although not maps, you sort
>> of
>> have to do those yourself with repeated structures which will become lists
>> of records, so not quite as useful), as well as strings, ints, floats and
>> binary data.  It does not include any RPC based mechanism, and you
>> basically
>> get serializers/deserializers which get/give binaries, so you can use it
>> with whatever you want.  Riak uses this as its faster interface via a
>> socket
>> and I've implemented server to server communication over HTTP which is
>> easy.
>>
>> LWES (http://lwes.github.com/) is a system and protocol I first developed
>> in 1998 and which was open sourced in 2008.  It's mostly meant for passing
>> maps in a fire and forget fashion over UDP (or multicast UDP), it's a bit
>> bulkier on the wire than thrift and protobuffs as the serialization format
>> is self describing (key names are sent along with values).  It also only
>> has support in java for floats and arrays (but those will probably make
>> their way into the other languages as time permits).  It currently
>> has native bindings for C, erlang, java, and .Net, as well as SWIG based
>> bindings for perl, python and ruby.  It's a great system for quickly
>> passing maps between different programming languages where you can afford
>> to loose some data here or there.  Also, unlike thrift/protobuff it does
>> not require any precompilation of modules.  While we don't have a
>> javascript
>> version yet, we may be developing one soon (although it most likely won't
>> be able to do UDP from a javascript client which is unfortunate).  LWES
>> is extremely stable and has been in production systems serving trillions
>> of events for almost 13 years (every penny ever made by
>> Goto/Overture/Yahoo's
>> search advertising system was via lwes).
>>
>> I've used all three of these systems in production web systems so can
>> attest
>> that they all work and at large scale (ten's of thousands to hundred's of
>> thousands of requests per second).
>>
>> I've not used Bert, BSON, Avro, MessagePack or Etch all of which do
>> similiar things but offer slightly different feature sets.
>>
>> Hope that helps,
>>
>> -Anthony
>>
>> --
>> ------------------------------------------------------------------------
>> Anthony Molinaro                           <anthonym>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions
> http://erlang.org/mailman/listinfo/erlang-questions
>
>


--
??blog
http://blog.sina.com.cn/xingsen
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111201/dfdb1a89/attachment.html>