new-model.text, please comment

new-model.text, please comment

[Marius Vollmer]

Hi,

I have written down my thoughts about an evaluation model that allows
an optimizing ahead-of-time compiler.  It's in CVS:

  guile/workbook/compilation/new-model.text

Please have a look and comment on it.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Tom Lord]

	[ Author: mvo@zagadka.de; Status: very preliminary. ]


Ok... I've read it a couple of times.

Let me put my reply in some context.  I _think_ I'm a bit more
experienced (in some sense) in these areas than you.  Therefore, I
will _pretend_ that I'm qualified to reply as a pedant and, in that
light, trash your document.  TB, at least, is always there to yank on
my leash :-)

Before I do that, a few qualifications:

Thanks for writing this.  Gosh, I wish you'd done this "way back when"
when I was the maintainer.   You're addressing important issues and
clearly have a deep enough mental model of those issues to be
qualified to do so.  Yay!

Ok, let's talk trash:


1) The form of this document is all wrong.

  I was hoping to read this from the perspective of a Scheme compiler
  implementor who knows nothing about Guile.  Probably that wasn't
  your intended audience.  Nevertheless, it's too informal a mixture of
  ideas, in which you try to point out some important abstract
  semantics via a mixture of vaguely descriptive statements and
  implementation-techniques-with-semantic-implications.

  I would advocate for something really ambitious.  For example, start
  with the semantics in RnRS and try to extend those for modules and
  compilation.  Try to also write an operational semantics (e.g. a
  mapping of some of the formal semantics into a stable C API).
  Taking this route has the potential to subject you to the nearly
  boundless abuse of many Scheme experts -- but it also has the
  _potential_ to lead to a very useful and influential document and
  Guile.


2) Compilation isn't special.

  You seem too ready to distinguish "compile time" from "eval time".
  Please don't do that.   That's lisp, not Scheme.

  For example, you write:

	Some attributes of whatever is found when an identifier is
	looked up are expected to carry over to the run-time
	environment.  Whether this is indeed the case should be
	checked when the compiled form is executed and a warning
	should be emitted when a violation is found, or an error when
	there is no way to continue.

  Bleh.  What a cheap, bletcherous hack you advocate there.   Of what
  use is such a warning other than as a notice to the programmer that
  "you lose"?  (And, such a warning may not actually come until
  certain code paths are reached -- possibly well after deployment).

  I'd rather have a system in which some code simply can't be usefully
  compiled (i.e, no significant performance benefit), but in which,
  all compiled code behaves _exactly_ like loading the source into the
  interpreter.  I recognize that this may require some tweaks to the
  interpreted language (e.g. to enable "locked up" modules).

  Rather than defining a semantic "compile time", I'd rather see a
  list of rules that code has to follow if it wants to permit a
  compiler to optimize.

  Here's an example of what I happen to think compilers are good for.
  Suppose I write:

	(define x (lambda (a b) (+ (* a a) (* b b))))

  and, in the same file, a call to the (never assigned to) `x' for
  which it is easy to infer that the arguments are small integers.
  I expect some really tight code for that.

  With such a compiler, as an app writer, I can take special care to
  code performance critical sections in a compiler-friendly way.  If
  that worked well, I wouldn't care too much how significantly more
  complicated code was handled.



As always: nothing _is_ false,
-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Rob Browning]

Marius Vollmer <mvo@zagadka.ping.de> writes:

> I have written down my thoughts about an evaluation model that allows
> an optimizing ahead-of-time compiler.  It's in CVS:
>
>   guile/workbook/compilation/new-model.text
>
> Please have a look and comment on it.

I've read it through once, though I need to do so again, before
commenting much, but one part wasn't completely clear to me:

> The compiler is free to reuse top-level frames for several top-level
> forms, even when executing a form will change the name/module mapping
> used in the next.  You must explicitely tell the compiler that it must
> construct a new top-level frame.  You can do this with the
> 
>   (:module-barrier)                       XXX - need better name
> 
> compiler directive.  The directive guarantees that code prior to it is
> fully executed before top-level frames for forms after it are
> constructed.  The directive must be a top-level form.

Could you provide a bit of elaboration here.  More specifically, what
does "fully executed" mean?  (I tend to start thinking of
"define-macro" when I hear that, though I guess any top-level form,
macro or not could be relevant.)  For example, does the above mean
that given the following code:

  (foo ...)
  (do-something-that-changes-the-current-module!)
  (bar ...)

the results would be undefined because the compiler is within its
rights to presume that do-something *doesn't* change the current
module unless a without a :module-barrier call like so:

  (foo ...)
  (do-something-that-changes-the-current-module!)
  (:module-barrier)
  (bar ...)

This seems to be implied by the later examples of use-modules, etc.,
but I just wanted to make sure I understood what you were stating.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Neil Jerram]

>>>>> "Marius" == Marius Vollmer <mvo@zagadka.ping.de> writes:

    Marius>   guile/workbook/compilation/new-model.text

    Marius> Please have a look and comment on it.

Here are my few thoughts.  I don't have much experience or expertise
in this area, so feel free to explain the obvious to me if that's what
I've asked for :-)

    Marius> The output of the compiler is not specified.  Also,
    Marius> execution of languages other than Scheme is not
    Marius> considered.  It is assumed that additional languages are
    Marius> first translated to Scheme (or whatever variant of Scheme
    Marius> we offer) and then compiled normally."

High level thought -- is all of this new thinking necessary?  Are we
unnecessarily ignoring useful stuff that has already been worked
through on other projects?

    Marius> A module contains a set of bindings, and a binding is a
    Marius> pair consisting of a symbol and another object.  The other
    Marius> object in a binding can be a macro transformer or a
    Marius> variable.

    Marius> When a module is created, the set of bindings is empty.
    Marius> You can add bindings to the set, but you can not remove
    Marius> them.  Existing bindings can not be changed.  There can be
    Marius> at most one binding with a given symbol.

So it is impossible to change an existing macro definition?

    Marius> During compilation of a file that defines a module, that
    Marius> module is partially constructed (via code executed by
    Marius> eval-case).  The constructed module is made the current
    Marius> module, but it is not registered in the system.  Requests
    Marius> for a module with the name of the module-being-compiled
    Marius> will not find the partially constructed module.  When the
    Marius> compiler wants to follow a :module-ref statement with an
    Marius> explicit name, it must check whether that name refers to
    Marius> the partially constructed current module.

Don't understand the point here.  What are you trying to say by "will
not find the partially constructed module"?

Regards,
        Neil



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> > The compiler is free to reuse top-level frames for several top-level
> > forms, even when executing a form will change the name/module mapping
> > used in the next.  You must explicitely tell the compiler that it must
> > construct a new top-level frame.  You can do this with the
> > 
> >   (:module-barrier)                       XXX - need better name
> > 
> > compiler directive.  The directive guarantees that code prior to it is
> > fully executed before top-level frames for forms after it are
> > constructed.  The directive must be a top-level form.
> 
> Could you provide a bit of elaboration here.  More specifically, what
> does "fully executed" mean?

There is no special meaning to "fully" here.  I could have just said
"executed".

> For example, does the above mean that given the following code:
> 
>   (foo ...)
>   (do-something-that-changes-the-current-module!)
>   (bar ...)
> 
> the results would be undefined because the compiler is within its
> rights to presume that do-something *doesn't* change the current
> module unless a without a :module-barrier call like so:
> 
>   (foo ...)
>   (do-something-that-changes-the-current-module!)
>   (:module-barrier)
>   (bar ...)
> 
> This seems to be implied by the later examples of use-modules, etc.,
> but I just wanted to make sure I understood what you were stating.

Yes, this is what I had in mind.  Without this :module-barrier
statement, the compiler would have to assume that any call can change
the module setup (which will make a lot optimizations impossible).  Or
we would have to have a different kind of module system.

We could have also use declarations to communicate the module barrier
to the compiler.  I.e., the variable named
do-something-that-changes-the-current-module! has a declaration that
the compiler understands.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Rob Browning]

Marius Vollmer <mvo@zagadka.ping.de> writes:

> Yes, this is what I had in mind.  Without this :module-barrier
> statement, the compiler would have to assume that any call can
> change the module setup (which will make a lot optimizations
> impossible).  Or we would have to have a different kind of module
> system.
>
> We could have also use declarations to communicate the module
> barrier to the compiler.  I.e., the variable named
> do-something-that-changes-the-current-module! has a declaration that
> the compiler understands.

OK, pretty much what I expected, just wanted to make sure.

Thanks

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Rob Browning]

Neil Jerram <neil@ossau.uklinux.net> writes:

> High level thought -- is all of this new thinking necessary?  Are we
> unnecessarily ignoring useful stuff that has already been worked
> through on other projects?

Well there's a very interesting thread on comp.lang.scheme we should
also investigate as part of this process.  My newsgroup access is dead
at the moment, but it was a *large* thread regarding macros and
compilation.  One impression from skimming it was that the PLT people
(I think it was PLT) feel like they've actually worked this out, and
that they thought that most of the other implementations/solutions
weren't addressing all the complexities yet.  Sorry, but that's about
as good an impression as I can give until I have time to more
thoroughly investigate.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Lynn Winebarger]

On Friday 13 September 2002 17:06, Rob Browning wrote:
> Neil Jerram <neil@ossau.uklinux.net> writes:
> 
> > High level thought -- is all of this new thinking necessary?  Are we
> > unnecessarily ignoring useful stuff that has already been worked
> > through on other projects?
> 
> Well there's a very interesting thread on comp.lang.scheme we should
> also investigate as part of this process.  My newsgroup access is dead
> at the moment, but it was a *large* thread regarding macros and
> compilation.  One impression from skimming it was that the PLT people
> (I think it was PLT) feel like they've actually worked this out, and
> that they thought that most of the other implementations/solutions
> weren't addressing all the complexities yet.  Sorry, but that's about
> as good an impression as I can give until I have time to more
> thoroughly investigate.
> 

http://www.cs.utah.edu/plt/publications/macromod.pdf
seems to be the relevant paper (it's not about units).  I haven't read it
yet, though.

Lynn


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Marius Vollmer]

Neil Jerram <neil@ossau.uklinux.net> writes:

> Here are my few thoughts.  I don't have much experience or expertise
> in this area, so feel free to explain the obvious to me if that's what
> I've asked for :-)

Heh, I'm totally new to this stuff as well...

>     Marius> The output of the compiler is not specified.  Also,
>     Marius> execution of languages other than Scheme is not
>     Marius> considered.  It is assumed that additional languages are
>     Marius> first translated to Scheme (or whatever variant of Scheme
>     Marius> we offer) and then compiled normally."
> 
> High level thought -- is all of this new thinking necessary?  Are we
> unnecessarily ignoring useful stuff that has already been worked
> through on other projects?

Is there much new stuff in it?  I think what I have written down is
quite minimal, and very Guile specific as well.

>     Marius> When a module is created, the set of bindings is empty.
>     Marius> You can add bindings to the set, but you can not remove
>     Marius> them.  Existing bindings can not be changed.  There can be
>     Marius> at most one binding with a given symbol.
> 
> So it is impossible to change an existing macro definition?

Uhh, ohh.  That's what the rules say, but it's not what I intended.  I
think it is OK to change a macro definition, much as you can change a
function definition.  The text doesn't say what a macro transformer
really is.  We could just say that it is some kind of object that
contains a function.  The text does not allow the object to be
replaced by a different object, but the object can be modified (like
variables can be modified).

The alternative would be to change the rules and say that a macro
transformer can be replaced with a different macro transformer, but
that might not be as clean.

>     Marius> During compilation of a file that defines a module, that
>     Marius> module is partially constructed (via code executed by
>     Marius> eval-case).  The constructed module is made the current
>     Marius> module, but it is not registered in the system.  Requests
>     Marius> for a module with the name of the module-being-compiled
>     Marius> will not find the partially constructed module.  When the
>     Marius> compiler wants to follow a :module-ref statement with an
>     Marius> explicit name, it must check whether that name refers to
>     Marius> the partially constructed current module.
> 
> Don't understand the point here.  What are you trying to say by "will
> not find the partially constructed module"?

There is a global mapping from module names to module objects.  When a
module is created by executing a 'define-module' form, it is
registered in that global mapping so that 'use-modules' etc can find
it.  When a module is compiled, we need a compile-time representation
of the module, however, for keeping track of imports and macro
definitions, etc.  That representation can be a real module object,
but it would be wrong to register its name in the global mapping since
the module will only be partially constructed.

When a 'use-modules' form or equivalent is comiled, the referenced
module is loaded just as it would be loaded when the 'use-modules'
form is executed.  When the referenced module in turn references the
module that is currently being compiled, it can not use the partially
constructed compile-time represenation of the module-being-compiled.
The module is then loaded from source or an old compiled version is
used (if it isn't already present in the system anyway).

However, 'module-ref' forms can also refer to the
module-being-compiled by its real name in addition to the special name
'#t'.  That real name needs to be resolved to the compile-time
representation.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Marius Vollmer]

Tom Lord <lord@regexps.com> writes:

> TB, at least, is always there to yank on my leash :-)

:-)

> 1) The form of this document is all wrong.
> 
>   I was hoping to read this from the perspective of a Scheme compiler
>   implementor who knows nothing about Guile.  Probably that wasn't
>   your intended audience.

Right.

>   Nevertheless, it's too informal a mixture of ideas, in which you
>   try to point out some important abstract semantics via a mixture
>   of vaguely descriptive statements and
>   implementation-techniques-with-semantic-implications.

Yes, the interfaces of what I try to describe to the rest of the
'system' needs to be better specified.  That would mostly be the macro
expander and the module system.  Also, some useful declarations need
to be specified.

>   I would advocate for something really ambitious.  For example, start
>   with the semantics in RnRS and try to extend those for modules and
>   compilation.  Try to also write an operational semantics (e.g. a
>   mapping of some of the formal semantics into a stable C API).
>   Taking this route has the potential to subject you to the nearly
>   boundless abuse of many Scheme experts -- but it also has the
>   _potential_ to lead to a very useful and influential document and
>   Guile.

Yeah, that needs to be done, and I hope I have a small first step.

> 2) Compilation isn't special.
> 
>   You seem too ready to distinguish "compile time" from "eval time".
>   Please don't do that.   That's lisp, not Scheme.
> 
>   For example, you write:
> 
> 	Some attributes of whatever is found when an identifier is
> 	looked up are expected to carry over to the run-time
> 	environment.  Whether this is indeed the case should be
> 	checked when the compiled form is executed and a warning
> 	should be emitted when a violation is found, or an error when
> 	there is no way to continue.
> 
>   Bleh.  What a cheap, bletcherous hack you advocate there.   Of what
>   use is such a warning other than as a notice to the programmer that
>   "you lose"?  (And, such a warning may not actually come until
>   certain code paths are reached -- possibly well after deployment).

The alternative would be a 'fool-proof' system where you can't
possibly make a mistake.  Such a system will be no joy to use, I'm
afraid.

Anyway, I actually try to avoid a discussion about what kind of module
system we want, whether it should allow incremental, interactive
modifications, or whether it must allow closed-world compilation ala
Stalin.

I hope that the model allows both.

>   I'd rather have a system in which some code simply can't be usefully
>   compiled (i.e, no significant performance benefit), but in which,
>   all compiled code behaves _exactly_ like loading the source into the
>   interpreter.  I recognize that this may require some tweaks to the
>   interpreted language (e.g. to enable "locked up" modules).

Would one just ave the option of locking a module, or would all
modules be locked?

>   Rather than defining a semantic "compile time", I'd rather see a
>   list of rules that code has to follow if it wants to permit a
>   compiler to optimize.
>
>   Here's an example of what I happen to think compilers are good for.
>   Suppose I write:
> 
> 	(define x (lambda (a b) (+ (* a a) (* b b))))
> 
>   and, in the same file, a call to the (never assigned to) `x' for
>   which it is easy to infer that the arguments are small integers.
>   I expect some really tight code for that.

I don't think we should have the rule that the compiler can assume by
default that a variable will never be assigned to when it is not being
assigned to in the file where it is defined.

We should probably have declarations for the file as well as for
variables, and with them, the 'new-model' can allow block-compilation.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Tom Lord]

       > Anyway, I actually try to avoid a discussion about what kind of module
       > system we want, whether it should allow incremental, interactive
       > modifications, or whether it must allow closed-world compilation ala
       > Stalin.

       > I hope that the model allows both.


Yay.  I think your hope expresses a long-standing Guile design
principle/design pattern, so I'll reinforce it by paraphrase.


One principle/pattern:

	Maximize sensible interactive/dynamic/reflective capability
	(up to but not including features that can crash an
	interpreter).


complemented by a design principle/design pattern that was always in
the back of my head but never came up in the work I did:


	Provide and document sensible subsets to which code can 
	be restricted to support excellent compilation.


In other words: find the really nice interactive, incremental system
of which a stalinesque system is a clearly and usefully defined
subset.


"Blow off native threads and make () == #f" -- from the big list of
pointless advice :-)

-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Tom Lord]

	> I don't think we should have the rule that the compiler can
	> assume by default that a variable will never be assigned to
	> when it is not being assigned to in the file where it is
	> defined.


Perhaps.  I dunno.  Sounds wrong to me.  But: I dunno.

Advice: pick some big app to work on.  Work on that app.  Slow down
work on the guile core -- but revise the core as your experience on
the big app accumulates.

In other words, whether or not there should be such a rule seems to me
to be the kind of question that experience can help you decide.

Write Emacs from scratch, in pure Guile, or something.

Or blow S48 out of the water as a SCSH host by writing Guile
replacements for all of the text and shell utils.

-t




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: new-model.text, please comment

[Marius Vollmer]

Tom Lord <lord@regexps.com> writes:

> 	> I don't think we should have the rule that the compiler can
> 	> assume by default that a variable will never be assigned to
> 	> when it is not being assigned to in the file where it is
> 	> defined.
> 
> Perhaps.  I dunno.  Sounds wrong to me.  But: I dunno.

Maybe a compromise: let's make a declaration that tells the compiler
whether it can make 'the assumption'.  The conservative default for
this declaration is that the assumption can not be made.  When we have
the experience that almost every file carries a declaration to reverse
the default, we can consider reversing the default by default.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel