[erlang-questions] zlib design flaw?
Richard A. O'Keefe
Thu Sep 25 06:11:14 CEST 2014
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 :-)
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
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.
More information about the erlang-questions