[erlang-questions] zlib design flaw?

[Richard A. O'Keefe]

On 25/09/2014, at 5:46 AM, Tony Rogvall wrote:
> 
> Thanks. Cool stuff :-)
> 
> The following is also a fun version ( I am not the only one to blame for api design faults :-)

[[billion laughs]]

Wikimedia markup has the same problem.

For that matter, templates make the C++ type language
a Turing-complete (but seriously ugly) functional programming
language, and the various features that have been added to
the Haskell type system since 2010 make that a Turing-complete
logic programming language, so you can write a fairly short
C++ or Haskell program that takes as long to type-check as
you please.

The Erlang binary term representation is just on the safe side
of this kind of attack.  The fact that backreferences can only
be used to refer to *atoms* keeps it safe.

I'm a little bit sad that this seems like a good reason not
to make the binary representation "smarter".

Oh heck.  The binary format I use to provide persistence for
Smalltalk has precisely this kind of problem, but if I
*didn't* allow backreferences to arbitrary objects I would not
be able to handle cyclic object graphs.

I console myself: UBF(A) is on the wrong side of the safety
line.  The term you get by decoding n UBF(a) bytes will be
O(n) in size, but it may take O(2**n) time to traverse it.