[Haskell-cafe] monads with take-out options

[Claus Reinke]

>   - i am interested in a first-principles notion of data. Neither lambda
>   nor π-calculus come with a criterion for determining which terms represent
>   data and which programs. You can shoe-horn in such notions -- and it is
>   clear that practical programming relies on such a separation -- but along
>   come nice abstractions like generic programming and the boundary starts
>   moving again. (Note, also that one of the reasons i mention π-calculus is
>   because when you start shipping data between processes you'd like to know
>   that this term really is data and not some nasty little program...)

I wouldn't call the usual representations of data in lambda shoe-horned
(but perhaps you meant the criterion for distinguishing programs from
data, not the notion of data?). Exposing data structures as nothing but
placeholders for the contexts operating on their components, by making
the structure components parameters to yet-to-be-determined continuations,
seems to be as reduced to first-principles as one can get.

It is also close to the old saying that "data are just dumb programs"
(does anyone know who originated that phrase?) - when storage
was tight, programmers couldn't always afford to fill it with dead
code, so they encoded data in (the state of executing) their routines.
When data was separated from real program code, associating data
with the code needed to interpret it was still common. When high-level
languages came along, treating programs as data (via reflective meta-
programming, not higher order functions) remained desirable in some
communities. Procedural abstraction was investigated as an alternative
to abstract data types. Shipping an interpreter to run stored code was
sometimes used to reduce memory footprint.

If your interest is in security of mobile code, I doubt that you want to
distinguish programs and data - "non-program" data which, when
interpreted by otherwise safe-looking code, does nasty things, isn't
much safer than code that does non-safe things directly. Unless you
rule out code which may, depending on the data it operates on, do
unwanted things, which is tricky without restricting expressiveness.

More likely, you want to distinguish different kinds/types of
programs/data, in terms of what using them together can do (in
terms of pi-calculus, you're interested in typing process communication,
restricting access to certain resources, or limiting communication
to certain protocols). In the presence of suitably expressive type
systems, procedural data abstractions need not be any less "safe"
than dead bits interpreted by a separate program. Or if reasoning
by suitable observational equivalences tells you that a piece of code
can't do anything unsafe, does it matter whether that piece is
program or data?

That may be too simplistic for your purposes, but I thought I'd put
in a word for the representation of data structures in lambda.

Claus

Ps. there have been lots of variation of pi-calculus, including
    some targetting more direct programming styles, such as
    the blue calculus (pi-calculus in direct style, Boudol et al).
    But I suspect you are aware of all that.