Claus,<div><br></div><div>Thanks for your thoughtful response. Let me note that fully abstract semantics for PCF -- a total toy, mind you, just lambda + bools + naturals -- took some 25 years from characterization of the problem to a solution. That would seem to indicate shoe-horning, in my book ;-). Moreover, when i look at proposals to revisit Church versus Parigot encodings for data structures (ala Oliveira's thesis), i think we are still at the very beginnings of an understanding of how data fits into algebraic accounts of computation (such as lambda and ð-calculi). </div>
<div><br></div><div>Obviously, we've come a long way. The relationship between types and pattern-matching, for example, is now heavily exploited and generally a good thing. But, do we really understand what's at work here -- or is this just another 'shut up and calculate' situation, like we have in certain areas of physics. Frankly, i think we are really just starting to understand what types are and how they relate to programs. This really begs fundamental questions. Can we give a compelling type-theoretic account of the separation of program from data?</div>
<div><br></div><div>The existence of such an account has all kinds of implications, too. For example, the current "classification" of notions of quantity (number) is entirely one of history and accident.</div><div>
<ul><li>Naturals</li><li>Rationals</li><li>Constructible</li><li>Algebraic</li><li>Transcendental</li><li>Reals</li><li>Complex</li><li>Infinitessimal</li><li>...</li></ul><div>Can we give a type theoretic reconstruction of these notions (of traditional data types) that would unify -- or heaven forbid -- redraw the usual distinctions along lines that make more sense in terms of applications that provide value to users? Conway's ideas of numbers as games is remarkably unifying and captures all numbers in a single elegant data type. Can this (or something like it) be further rationally partitioned to provide better notions of numeric type? Is there a point where such an activity hits a wall and what we thought was data (real numbers; sequences of naturals; ...) are just too close to programs to be well served by data-centric treatments?</div>
<div><br></div></div><div>Best wishes,</div><div><br></div><div>--greg<br><br><div class="gmail_quote">2008/11/24 Claus Reinke <span dir="ltr"><<a href="mailto:claus.reinke@talk21.com">claus.reinke@talk21.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- i am interested in a first-principles notion of data. Neither lambda<div class="Ih2E3d"><br>
nor ð-calculus come with a criterion for determining which terms represent<br>
data and which programs. You can shoe-horn in such notions -- and it is<br>
clear that practical programming relies on such a separation -- but along<br>
come nice abstractions like generic programming and the boundary starts<br>
moving again. (Note, also that one of the reasons i mention ð-calculus is<br>
because when you start shipping data between processes you'd like to know<br>
that this term really is data and not some nasty little program...)<br>
</div></blockquote>
<br>
I wouldn't call the usual representations of data in lambda shoe-horned<br>
(but perhaps you meant the criterion for distinguishing programs from<br>
data, not the notion of data?). Exposing data structures as nothing but<br>
placeholders for the contexts operating on their components, by making<br>
the structure components parameters to yet-to-be-determined continuations,<br>
seems to be as reduced to first-principles as one can get.<br>
<br>
It is also close to the old saying that "data are just dumb programs"<br>
(does anyone know who originated that phrase?) - when storage<br>
was tight, programmers couldn't always afford to fill it with dead<br>
code, so they encoded data in (the state of executing) their routines.<br>
When data was separated from real program code, associating data<br>
with the code needed to interpret it was still common. When high-level<br>
languages came along, treating programs as data (via reflective meta-<br>
programming, not higher order functions) remained desirable in some<br>
communities. Procedural abstraction was investigated as an alternative<br>
to abstract data types. Shipping an interpreter to run stored code was<br>
sometimes used to reduce memory footprint.<br>
<br>
If your interest is in security of mobile code, I doubt that you want to<br>
distinguish programs and data - "non-program" data which, when<br>
interpreted by otherwise safe-looking code, does nasty things, isn't<br>
much safer than code that does non-safe things directly. Unless you<br>
rule out code which may, depending on the data it operates on, do<br>
unwanted things, which is tricky without restricting expressiveness.<br>
<br>
More likely, you want to distinguish different kinds/types of<br>
programs/data, in terms of what using them together can do (in<br>
terms of pi-calculus, you're interested in typing process communication,<br>
restricting access to certain resources, or limiting communication<br>
to certain protocols). In the presence of suitably expressive type<br>
systems, procedural data abstractions need not be any less "safe"<br>
than dead bits interpreted by a separate program. Or if reasoning<br>
by suitable observational equivalences tells you that a piece of code<br>
can't do anything unsafe, does it matter whether that piece is<br>
program or data?<br>
<br>
That may be too simplistic for your purposes, but I thought I'd put<br>
in a word for the representation of data structures in lambda.<br>
<br>
Claus<br>
<br>
Ps. there have been lots of variation of pi-calculus, including<br>
some targetting more direct programming styles, such as<br>
the blue calculus (pi-calculus in direct style, Boudol et al).<br>
But I suspect you are aware of all that.<br>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>L.G. Meredith<br>Managing Partner<br>Biosimilarity LLC<br>806 55th St NE<br>Seattle, WA 98105<br><br>+1 206.650.3740<br><br><a href="http://biosimilarity.blogspot.com">http://biosimilarity.blogspot.com</a><br>
</div>