Is is common for expressions to share expression structure?
e.g. two function-call expressions sharing a common function-
call expression.
Or does eval make this unecessary?
A. Huerter wrote:
> Is is common for expressions to share expression structure?
> e.g. two function-call expressions sharing a common function-
> call expression.
> Or does eval make this unecessary?
It shouldn't make any difference, with one exception: if literal
constants are shared, evaluation and compilation (but not file
compilation) must preserve that.
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> A. Huerter wrote:
>
> > Is is common for expressions to share expression structure?
> > e.g. two function-call expressions sharing a common function-
> > call expression.
> > Or does eval make this unecessary?
>
> It shouldn't make any difference, with one exception: if literal
> constants are shared, evaluation and compilation (but not file
> compilation) must preserve that.
What Paul says is correct as an answer to the literal question , but...
This is one of those questions that reveals a host of likely-incorrect
preconceptions about the way things are supposed to work, both in Lisp
and in the programmer's technique.
What is it that you are trying to achieve, or to avoid?
Can you sketch a piece of code that you are considering using?
Looking at your code and addressing it directly is much more likely to
get you an answer that will carry you into the future.
Sorry, not trying to achieve or avoid anything in particular.
I'm just curious about this situation in general. To clarify,
I'm referring to an interpreted Scheme environment.
I'm developing a new language based on Scheme and
I'm seeing that the program-data identity means it's conceivable
for expressions to share subexpressions; whether this is
common practice or necessary for certain problems is
what I'm unsure about.
va1 wrote:
> I'm seeing that the program-data identity means it's conceivable
> for expressions to share subexpressions; whether this is
> common practice or necessary for certain problems is
> what I'm unsure about.
The point I was edging up to was that (aside from literal constants)
it can't make any difference to the behavior of your program if
parts share structure.
Paul
In article <························@z14g2000cwz.googlegroups.com>,
"va1" <·······@csd.uwo.ca> wrote:
> Sorry, not trying to achieve or avoid anything in particular.
> I'm just curious about this situation in general. To clarify,
> I'm referring to an interpreted Scheme environment.
Then why aren't you asking in comp.lang.scheme?
> I'm developing a new language based on Scheme and
> I'm seeing that the program-data identity means it's conceivable
> for expressions to share subexpressions; whether this is
> common practice or necessary for certain problems is
> what I'm unsure about.
As in Common Lisp, literal data structures are allowed to share
substructure. Since modifying literals is not permitted, the only way
you would be able to detect this sharing is by using EQ in CL or eq? in
Scheme. It shouldn't otherwise have any impact on the behavior of the
program.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
> As in Common Lisp, literal data structures are allowed to share
> substructure. Since modifying literals is not permitted, the only way
> you would be able to detect this sharing is by using EQ in CL or eq? in
> Scheme. It shouldn't otherwise have any impact on the behavior of the
> program.
I know the semantics of the substructure-sharing programs aren't affected;
but is it common practice in metaprogramming for programs to share
subexpressions? Put another way, if we represent programs in a different,
non-sharing, native data type, then would anyone care?
·······@csd.uwo.ca (A. Huerter) writes:
First, let me say that if you're using Scheme, you REALLY should be
discussing this on the comp.lang.scheme newsgroup, not ours.
However, I'm going to respond anyway because there may be
misconceptions about Lisp that underly this, and I'd like to address
them.
> > As in Common Lisp, literal data structures are allowed to share
> > substructure. Since modifying literals is not permitted, the only way
> > you would be able to detect this sharing is by using EQ in CL or eq? in
> > Scheme. It shouldn't otherwise have any impact on the behavior of the
> > program.
>
> I know the semantics of the substructure-sharing programs aren't affected;
> but is it common practice in metaprogramming for programs to share
> subexpressions? Put another way, if we represent programs in a different,
> non-sharing, native data type, then would anyone care?
First, I don't think Scheme promises to ever retain object identity...
In fact, my recollection is that the hygiene-maintaining Kohlbecker
'code painting' algorithm completely invades quoted structure and then
later pastes it back together, prior to syntaxing in a way that would
be quote-aware. [This was why I preferred the syntactic closures
alternative style, back when that was originally discussed.] As a
consequence of environment 'painting', though, it would be surprising
in at least some (if not most or all) implementations if sharing were
maintained at all.
Note, too, that Scheme source is not like CL source. It's usually text.
So it's MUCH harder to set up shared code in the first place because the
ordinary Lispy operations like cons are not involved in the creation of
programs, and it's the controlled creation and sharing of cons'd code that
usually leads to structure sharing in CL (not that such structure sharing
has much effect beyond, as already noted, the treatment of literals in
in-core compilation [COMPILE] or evaluation [EVAL]; the use of compile-file
is more restricted because of the externalization process to files).
Now, here's the real reason I thought it worth replying on this group:
A potential confusion you may have is signaled with your use of the word
"represent" in "if we represent programs in ...".
Neither Common Lisp nor Scheme promises how it represents programs.
They speak of how programs are notated, but once the program has been
syntactically processed, there's already no guarantee that the original
representation is maintained, other than in literal data.
Programs that are compiled, for example, are very likely to be
represented in "different, non-sharing, native data types", since
there's no talk of machine language or byte code or any other target
in the Lisp datastructures. Nor even just of pointers, for that
matter. (Everything having pointer semantics already we just never
bother to say that everything is a pointer, except once in a while for
redundant emphasis.) Even in an interpreted model, nothing says the
results of semantic processing are lists. They might be vectors or
structures or some other thing. Sharing then, could occur, only if
the implementation chooses it. You have no handle on the structure
creation, nor even on the created structure, except indirectly through
a function handle, the veritably only operation on which is to call the
function.
> First, let me say that if you're using Scheme, you REALLY should be
> discussing this on the comp.lang.scheme newsgroup, not ours.
>
Done; could you lend an eye?
>
> A potential confusion you may have is signaled with your use of the
word
> "represent" in "if we represent programs in ...".
I'm referring to the conceptual internal representation of expressions,
as promised by the language semantics.
Kent M Pitman <······@nhplace.com> writes:
> [...]
> Programs that are compiled, for example, are very likely to be
> represented in "different, non-sharing, native data types", [...]
However a compiler could find side-effect-free common sub-expressions
and generate code to compute them only once thus "sharing" them, even
without sharing at the source level.
I think even for non-side-effect-free common sub-expressions, the
compiler could generate them as a local function if they're complex
enough and (declare (space 3)) was given.
> Even in an interpreted model, nothing says the
> results of semantic processing are lists. They might be vectors or
> structures or some other thing. Sharing then, could occur, only if
> the implementation chooses it. You have no handle on the structure
> creation, nor even on the created structure, except indirectly through
> a function handle, the veritably only operation on which is to call the
> function.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
Pascal Bourguignon <····@mouse-potato.com> writes:
> Kent M Pitman <······@nhplace.com> writes:
> > [...]
> > Programs that are compiled, for example, are very likely to be
> > represented in "different, non-sharing, native data types", [...]
>
> However a compiler could find side-effect-free common sub-expressions
> and generate code to compute them only once thus "sharing" them, even
> without sharing at the source level.
Surely, BUT such side-effect free common sub-expressions are not
necessarily sharable just because they are EQ. For example:
(car x)
is side-effect free, yet:
(lambda (x) (car x))
does not always return the same thing. Nor does
(lambda (x) (f x))
and
(lambda (y) (flet ((f (x) (not (f x)))) (f x)))
return the same thing, even though (f x) is in the body. Indeed, in
this latter, there are two (f x)'s which necessarily return values
that are different from one another.
Moreover, in
(lambda (x) (let ((y x)) (print (f x)) (print (f y))))
will print the same thing twice, assuming f is side-effect free, even
though (eq '(f x) '(f y)) => nil while in
(lambda (x) (dotimes (i x) (print (f x))))
the (f x)'s on each iteration are eq, yet return different values.
I could ramble on and on, but my point is that this is not about
datatypes and structure sharing. This is about common subexpression
analysis and dataflow, which are NOT a property of the representation,
but rather of the programming language semantics.
The poster seems to speak as if the representation constrains the
semantics, where, in fact, the semantics are what constrain the
representation.
In fact, since we were recently discussing the issue of MACLISP macro
expansion technology in another thread, I should point out that there
was a notion called MACROMEMO wherein it used to be that sometimes
macros would get cached based on EQUALness. Macroexpansion would do a
hash table lookup prior to application of the macro function, to save
time, but as I recall this led to program bugs because sometimes an EQ
macro form would want to expand differently. Consider:
(macrolet ((f (x) `(+ ,x 1)))
(lambda (x) (+ #1=(f x)
(macrolet ((f (x) `(- ,x 1)))
#1#))))
where the two (f x)'s given by the #1= and the #1# must expand
differently. So the macromemo stuff was, as I recalled, not
something that really worked.
Proper dataflow and common subexpression analysis works no better nor
worse in CL than in other languages. But the point is that it must
not get side-tracked on myths and bad logic about imagined
representational constraints.
I'm trying to get a laptop in time for church camp summer job. Please
help if
you can by using my referal link:
http://www.pctech4free.com/default.aspx?ref=59054
Thanks in advance