From: Matt Grice
Subject: Serializing or Marshalling a lambda?
Date:
Message-ID: <31692a12.301231519@news>
I've been playing around with Scheme lately, which has been quite a
learning experience, as I had been previously exposed to only
procedural languages. So, please bear with me if my understanding is
incomplete.
When you enter a list or vector, or any type of data into a Scheme
environment and then modify it programmatically, it is easy to get
that structure out onto the screen for examination and it is not
difficult to imagine that you could write that form to disk and be
able to resurrect that object in another session or even another
computer. It seems that complications would arise with more complex
structures, but examining or serializing such objects does not seem
farfetched at all.
Despite functions being 'first class objects' there is no similar
facility for them. The result of the obvious:
>(define myacl (acl-maker))
>myacl
yields
#[compound-procedure 14]
when I would really like to examine the source code and state of the
function. So far, it seems to me that this is not possible (at least
in portable scheme). However, the implementation of scheme that I use
(MIT Scheme) facilitates examining the source code and local
environment of lambdas for debugging. Most likely other schemes do as
well.
It seems to me that a facility for bundling up a lambda and all of its
internal environment would be very useful. Applications would include
user inspection, programmatic dissection and reassembly, and
persistent objects. I am interested in a discussion of the merits of
this idea (if any :)), existing implementations (in any language) or
potential stumbling blocks. Perhaps I such a facility exists in
scheme and I have just not looked hard enough?
Thanks in advance,
Matt
In article <··················@news> ······@iastate.edu (Matt Grice) writes:
>(define myacl (acl-maker))
>myacl
yields
#[compound-procedure 14]
when I would really like to examine the source code and state of the
function.
See:
----------------------------------------------------------------------
ftp://publications.ai.mit.edu/ai-publications/1000-1499/AITR-1427.ps.Z
----------------------------------------------------------------------
Call Number: MIT/AI/TR 1427 (In Tech Report stacks)
MIT. Artificial Intelligence Lab.
Title: Translucent procedures, abstraction without opacity.
(Ph.D. thesis)
Author: Rozas, Guillermo J.
date Oct. 1993; pp 169
Keywords: reflection
equation
----------------------------------------------------------------------
--
------------------------------------------------------------------------------
Michael R. Blair --. ·····@ai.mit.edu | MIT Artificial Intelligence Lab
(617) 253-0765 \\ ···@lcs.mit.edu | MIT Labor. for Computer Science
,,Lambda Calculus... /\\_ ...uber alles!'' | 545 Technology Square--Room 439
http://www-swiss.ai.mit.edu/~ziggy/ziggy.html| Cambridge, MA USA 02139-3594
······@iastate.edu (Matt Grice) writes:
>It seems to me that a facility for bundling up a lambda and all of its
>internal environment would be very useful.
Well, one thing is, it's not entirely true that lists and so on can be
printed and re-read in Scheme. If the lists are circular, printing them is
likely not to work, and certainly there's no mechanism for reading back in a
circular list.
This point is not unrelated to the one about procedures, since an
environment is a circular structure.
So, all of these problems could be solved, but it would mean putting
in bells and whistles -- a hard sell among Schemers. (See that other
thread about comment strings! :-)
P.S. I expect that someone else might also argue that procedures are
in principle black boxes, and it's wrong to look at their innards.
See, for example, the discussion of the eqv-ness of procedures in R4RS.
Procedures that have the same behavior may be considered equal even
though they look different inside.
··@anarres.CS.Berkeley.EDU (Brian Harvey) wrote:
> Well, one thing is, it's not entirely true that lists and so on can be
> printed and re-read in Scheme. If the lists are circular, printing them is
> likely not to work, and certainly there's no mechanism for reading back in a
> circular list.
Actually, Chez Scheme's reader (and MzScheme's) is capable of printing
and reading circular objects (with the right set of flags). Perhaps
you're aware of this, and mean something more general.
Also, and I realize I may be pounced on by some people from MIT for
saying this (-:, but I really don't think equating the opening up of
procedures with this problem is valid.
'shriram
From: Matt Grice
Subject: Re: Serializing or Marshalling a lambda?
Date:
Message-ID: <316acb6a.1344069@news>
··@anarres.CS.Berkeley.EDU (Brian Harvey) wrote:
>······@iastate.edu (Matt Grice) writes:
>>It seems to me that a facility for bundling up a lambda and all of its
>>internal environment would be very useful.
>
>Well, one thing is, it's not entirely true that lists and so on can be
>printed and re-read in Scheme. If the lists are circular, printing them is
>likely not to work, and certainly there's no mechanism for reading back in a
>circular list.
>
>This point is not unrelated to the one about procedures, since an
>environment is a circular structure.
>
I'm not sure that I understand how an environment is a circular
structure. Any explanation would be appreciated.
>P.S. I expect that someone else might also argue that procedures are
>in principle black boxes, and it's wrong to look at their innards.
Looking at innards was not my original goal, but something has to look
at innards in order to marshal the thing. As long as you are doing
that, why not give some sort of ability to the programmer, too. :)
Adding to the Scheme standard is not a priority for me, so I really do
not care if the 'Scheme elite' think a feature should be added to the
official language or not. What I am interested in is comments on
usefulness and viability, possible pitfalls, and existing
implementations in any language.
For those who are interested, I also received via email from Tom
Lyons:
>"Higher-Order Distributed Objects", Henry Cejtin, Suresh Jagannathan,
>and Richard Kelsey, ACM TOPLAS, volume 17, number 5, September 1995.
>URL http://www.neci.nj.nec.com/PLS/kali.html
>describes an implementation that can implicitly marshal higher-order
>values between address spaces.
······@iastate.edu (Matt Grice) writes:
>I'm not sure that I understand how an environment is a circular
>structure. Any explanation would be appreciated.
What I meant was this: The environment contains bindings of names
to values. In particular, a value can be a procedure. A procedure
includes its text (the stuff in the lambda expression) and the
environment in which it was created (so lexical scope works). So
the environment contains the procedure and the procedure contains
the environment. (Well, those aren't necessarily the same
environment, but they often are.)
Of course this is solvable -- one interesting example is EdScheme,
in which procedures are represented as ordinary lists, examinable
by the user program, that include bindings in the environment but
take special care in the representation so that they aren't
circular lists.
But I think the original question was in the form "why doesn't Scheme..."
and as usual the answer turns out to be "well, some versions of Scheme
do, but it's not in the standard because it's an aesthetic mess"! :-)
Matt Grice wrote:
>
> ··@anarres.CS.Berkeley.EDU (Brian Harvey) wrote:
>
>
> Adding to the Scheme standard is not a priority for me, so I really do
> not care if the 'Scheme elite' think a feature should be added to the
> official language or not. What I am interested in is comments on
> usefulness and viability, possible pitfalls, and existing
> implementations in any language.
>
Well, in Common Lisp there some related facilities:
1. Function-lambda-expression returns the lambda-expression of a
function and a flag indicating whether the function closes over a
non-null lexical environment. Unfortunately:
1. No implementation is required to actually save this information and
make it available. The function is designed merely to provide a
portable means of accessing the information iff it is saved. I assume
that implementations which save source for functions declared inline
will make this information available.
2. The environment flag returned is not necessarilly a representation
of non-nul environments (i.e. it might just be t) and there is no
portable way to access the environment if it is a real one.
2. Macros provide an &environment lambda list keyword which gives access
to the environment. Again, there is no portable way to do anything with
it other than to pass to system utilities such as macroexpand. However,
if you're clever, it does provide enough rope to start hanging yourself
with.
3. ANSI did add some portable environment access utilities such as
variable-information, function-information, declaration-information, and
the releated utilities, enclose and augment-environment. Apparently,
problems arose with the definitions and the functions were removed from
the ANSI spec. You might try looking through the ANSI archives to see
why it was dropped.
From: Steven M. Haflich
Subject: Re: Serializing or Marshalling a lambda?
Date:
Message-ID: <3173FACB.27B5@franz.com>
Howard R. Stearns wrote:
> 3. ANSI did add some portable environment access utilities such as
> variable-information, function-information, declaration-information, and
> the releated utilities, enclose and augment-environment. Apparently,
> problems arose with the definitions and the functions were removed from
> the ANSI spec. You might try looking through the ANSI archives to see
> why it was dropped.
The reason X3J13 retracted the environment access interface (essentially
CLtL2 section 8.5) was simply that there were serious bugs in the design
which none of us on X3J13 thought could be fixed without first doing an
actual implementation. There wasn't time if the standard wasn't to be
further delayed, so we regretfully removed them.
A primary purpose of the environment access interface was to allow other
code walkers to interface as equals with that other important code walker
that is the compiler, both to read and to modify the environment
representation. Providing this would of course be a good thing for the
language.
I don't remember all the specific problems. (I seem to remember some
detail about define-declaration, but I can't for the life of me remember
what it was.) However, there is one obvious problem with
augment-environment. There are two kinds of environment information
that must be represented during, say, file compilation. One is lexical
information, e.g., when a LET form is entered a walker could use
augment-environment on the outer environment to obtain an appropriate
environment for the LET body. When the compiler exits the body it can
resume using the outer environment.
However, the other kind of scoping needed by compile file that is not
provided by augment-environment. Top-level defining forms such as
DEFMACRO and DEFTYPE must be made available to walkers, and should not in
general be established in the global running lisp world. This kind of
environment information accumulates over the duration of a file
compilation, but the proposed system simply didn't provide for this kind
of "scoping".
Fixing this wouldn't he hard, IMO, but it shouldn't be done unless one or
two implementors were willing to build an implementation to make sure all
the details are covered. Again, IMO, this would be something for the
next round of the standard, when it happens.
In article <················@news>, Matt Grice <······@iastate.edu> wrote:
...
> Looking at innards was not my original goal, but something has to look
> at innards in order to marshal the thing. As long as you are doing
> that, why not give some sort of ability to the programmer, too. :)
>
as has been described by others, a naive interpreter can certainly extend
READ/WRITE to handle procedures. difficulties arise with closures, in that
the procedure captures a lexical environment which was created as part of
the dynamic execution:
(define (curried-apply foo)
(lambda (x)
(foo x)))
(extended-write (curried-apply (lambda (x) x)))
the output needs to represent the closure such that if reloaded it will do
the right thing, namely be a procedure which acts as the identity function.
this seems quite easy to do, but what if we capture something else:
(extended-write (curried-apply pair?))
now the READ/WRITE extensions need to do something about primitives, since
they are likely represented differently than user's code in the naive
interpreter. but this still seems manageable, you say? consider instead:
...
(extended-write (call/cc curried-apply))
...
where this call is made halfway through the most complicated Scheme program
you have yet encountered. again, the closure's lexical environment just
contains a procedure, but this procedure represents the entire future of the
computation, necessitating the recursive WRITEing of the entire machine
state (including an interpreter if this is to be a portable facility)!
but this is all conceivable, if inefficient, for a naive symbolic
interpreter, because the source code for each procedure is probably
available from either the user or the implementation itself. the first
potential show-stopper objection: for this to work portably, the
implementation must emit parts of itself which are captured by the closure.
this is a problem if the implementation is not under a public license.
so forget portability, and let the implementation rely on itself to provide
appropriate primitives in the session doing the READ, even when the
top-level environment has been reconfigured by a user. this also gets us
over the hurdle of having source code available, so we can relax the
symbolic interpreter constraint and allow efficiency in our implementation.
the extensions need not express the machine state in terms of Scheme data or
Scheme expressions, and the garbage collector should already know how to
traverse the machine and could assist marshalling.
I think the only adverse effect on optimizing compilers would be the
necessity of some extra (static) bookkeeping to assist the marshalling code
in walking over a machine for which features like static memory-management
and unboxed data are implemented.
however, in his original post ······@iastate.edu wrote:
...
> when I would really like to examine the source code and state of the
> function....
this is Pandora's Box. this is asking for a very powerful debugger, which
complicates the task of an optimizing compiler and/or confuses the user to
no end. the issues are too numerous to list here, but consider that an
optimizing Scheme compiler will likely perform dramatic transformations on
the naive environment model as well as eliminate and/or specialize code to
statically execute parts of the user's code and the naive runtime system.
inclusion of a call to the extended READ or WRITE functions would have
serious performance implications for the rest of the program, akin to
changing the compilation flags to include debugging info and/or preclude
certain optimizations.
karl
--
Karl Czajkowski
Reply-To: ······@cs.berkeley.edu
······@iastate.edu (Matt Grice) wrote:
> I'm not sure that I understand how an environment is a circular
> structure. Any explanation would be appreciated.
One word: LETREC.
> >"Higher-Order Distributed Objects", Henry Cejtin, Suresh Jagannathan,
> >and Richard Kelsey, ACM TOPLAS, volume 17, number 5, September 1995.
> >URL http://www.neci.nj.nec.com/PLS/kali.html
This is a good system. Kali Scheme unfortunately runs atop Scheme 48,
but it does well for its part. Its primitives might appear a tad
low-level, like an assembly language for distribution, but combine
these with Scheme's abstraction power and it's fairly easy to build a
large number of diverse distribution paradigms atop it.
What Kali Scheme lacks the most is proper debugging support in the
presence of distribution. But if nothing else, do read the paper.
'shriram