[148949] in cryptography@c2.net mail archive
Re: [Cryptography] defaults, black boxes, APIs,
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Mon Jan 6 12:25:42 2014
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <52C9FF19.2010401@panix.com>
Date: Mon, 6 Jan 2014 07:46:37 -0500
To: Albert Lunde <atlunde@panix.com>
Cc: Cryptography Mailing List <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============0228542687320299383==
Content-Type: multipart/alternative; boundary="Apple-Mail=_19AD02B7-D89C-4E3B-9532-9A45A5B2500F"
--Apple-Mail=_19AD02B7-D89C-4E3B-9532-9A45A5B2500F
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=us-ascii
On Jan 5, 2014, at 7:55 PM, Albert Lunde wrote:
>> They looked to the promised land of HTML5 as a way to do Flash-like
>> stuff without a plug-in and without Flash. But just what reason does
>> anyone have to think that HTML5 implementations will be any better =
than
>> Flash?
>=20
> HTML5 plus CSS is said to be Turing Complete
>=20
> An example of the effect of creeping featurism... :-(
A tale for the newbies: Algol 68 had an extensible type system which =
implied and extensible syntax. The Algol 68 report describe the =
language using W-grammers (W for their developer, Adriaan van =
Wijngaarden). W-grammars were intended to provide just enough of a step =
beyond context-free grammars to represent the context sensitivity =
implied by Algol 68's type system.
It was a great embarrassment to all involved when it turned out that =
W-grammars were, in fact, universal. As was pointed out at the time, =
this implied that you could not solve the termination problem for an =
Algol 68 compiler, so if it ran for a very long time, you couldn't tell =
if it had a bug or just really needed the time.
(I learned about this many years ago, probably from Alan Perlis. One =
thing I hadn't heard - I found it just now in the Wikipedia article =
about W-grammars - is that Don Knuth was working on attribute grammars =
at about the same time, for similar purposes, and that there are some =
underlying similarities in the approaches. Knuth apparently spoke to =
the Algol 68 committee about this. Attribute grammars survived, while =
W-grammars faded away. But most compilers to this day use ad hoc =
semantic techniques - i.e., reference to a symbol table - to handle the =
non-context free aspects of their languages during parsing - for =
example, the type names that typedef produces in C.)
Years later, we've learned to embrace the inner universality in our =
languages. For example, the C++ template language is universal. (This =
kind of thing is most often shown these days by implementing the lambda =
calculus, which tends to be straightforward in anything that has =
recursion plus macro-like substitution. TeX is easily seen to be =
universal through that mechanism - in fact, there are implementations of =
the lambda calculus that are used to build useful TeX macros.) We seem =
to have forgotten about the downsides.
But ... bringing this back to security: There's some recent work that =
makes the point that our network protocols are too complex for us to =
prove much about them - but they formalize this by looking at it from =
the view of language complexity theory. Nice work that I need to find =
some more time to read more about - see =
http://www.cs.dartmouth.edu/~sergey/langsec/. (I *may* have found this =
a while back through a message on this list. If you posted it =
previously - thanks.)
-- Jerry
--Apple-Mail=_19AD02B7-D89C-4E3B-9532-9A45A5B2500F
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><head></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><div><div>On Jan 5, 2014, at 7:55 PM, Albert Lunde =
wrote:</div><blockquote type=3D"cite"><div><blockquote type=3D"cite">They =
looked to the promised land of HTML5 as a way to do =
Flash-like<br></blockquote><blockquote type=3D"cite">stuff without a =
plug-in and without Flash. But just what reason =
does<br></blockquote><blockquote type=3D"cite">anyone have to think that =
HTML5 implementations will be any better =
than<br></blockquote><blockquote =
type=3D"cite">Flash?<br></blockquote><br>HTML5 plus CSS is said to be =
Turing Complete<br><br>An example of the effect of creeping featurism... =
:-(<br></div></blockquote></div>A tale for the newbies: Algol 68 =
had an extensible type system which implied and extensible syntax. =
The Algol 68 report describe the language using W-grammers (W for =
their developer, Adriaan van Wijngaarden). W-grammars were =
intended to provide just enough of a step beyond context-free grammars =
to represent the context sensitivity implied by Algol 68's type =
system.<div><br><div>It was a great embarrassment to all involved when =
it turned out that W-grammars were, in fact, universal. As was =
pointed out at the time, this implied that you could not solve the =
termination problem for an Algol 68 compiler, so if it ran for a very =
long time, you couldn't tell if it had a bug or just really needed the =
time.</div><div><br></div><div>(I learned about this many years ago, =
probably from Alan Perlis. One thing I hadn't heard - I found it =
just now in the Wikipedia article about W-grammars - is that Don Knuth =
was working on attribute grammars at about the same time, for similar =
purposes, and that there are some underlying similarities in the =
approaches. Knuth apparently spoke to the Algol 68 committee about =
this. Attribute grammars survived, while W-grammars faded away. =
But most compilers to this day use ad hoc semantic techniques - =
i.e., reference to a symbol table - to handle the non-context free =
aspects of their languages during parsing - for example, the type names =
that typedef produces in C.)</div></div><div><br></div><div>Years later, =
we've learned to embrace the inner universality in our languages. =
For example, the C++ template language is universal. (This =
kind of thing is most often shown these days by implementing the lambda =
calculus, which tends to be straightforward in anything that has =
recursion plus macro-like substitution. TeX is easily seen to be =
universal through that mechanism - in fact, there are implementations of =
the lambda calculus that are used to build useful TeX macros.) We =
seem to have forgotten about the downsides.</div><div><br></div><div>But =
... bringing this back to security: There's some recent work that =
makes the point that our network protocols are too complex for us to =
prove much about them - but they formalize this by looking at it from =
the view of language complexity theory. Nice work that I need to =
find some more time to read more about - see <a =
href=3D"http://www.cs.dartmouth.edu/~sergey/langsec/">http://www.cs.dartmo=
uth.edu/~sergey/langsec/</a>. (I *may* have found this a while =
back through a message on this list. If you posted it previously - =
thanks.)</div><div><div> =
=
=
-- Jerry</div></div><div><br></div></body></html>=
--Apple-Mail=_19AD02B7-D89C-4E3B-9532-9A45A5B2500F--
--===============0228542687320299383==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============0228542687320299383==--
