Re: summary: lilypond, lambda, and local-eval

[David Kastrup]

Mark H Weaver m...@netris.org writes:

 Ideally I'd like to allow the user to specify a precise list of
 variables to capture, and perhaps the other two variants should be
 implemented in terms of this one.

If you have to specify a precise _list_ of variables, the-environment is
pretty pointless since you can always write down an explicit list of
variables yourself.  It would be different if you were able to specify
the _classes_ of variable to capture.

-- 
David Kastrup

Re: summary: lilypond, lambda, and local-eval

[Andy Wingo]

On Sun 18 Dec 2011 08:11, Mark H Weaver m...@netris.org writes:

 So, it turns out that the best place to transform (the-environment) into
 standard scheme code is in the macro expander itself.

Are you certain that it is desirable to transform it into standard
Scheme code?

The statement that the-environment acts as if it were the expression,
(case-lambda ) doesn't mean that you have to implement it that
way.

 Indeed, only the macro expander has enough information to generate an
 optimal list of reachable lexicals, i.e. lexical variables that are
 accessible using normal symbols (as opposed to syntax objects) [more
 on this below].

Are you certain that you want to restrict the set of identifiers?

To me it sounds like an optimization, perhaps premature.

What do you think about having a the-environment tree-il form have a
field for the names and a field for the gensyms of captured lexicals?

 This is great news, because it means that `the-environment' will no
 longer require its own tree-il type, and the compiler will only see the
 standard scheme code that it expands into.

 However, we will need a robust way to either (A) specify, (B) discover,
 or (C) predict the order of the captured lexicals in a closure.

We could compile `the-environment' so that at runtime it yields a record
containing a vector of syntax objects and a vector of corresponding
variable objects.  (When the compiler boxes a variable, it does so in a
variable object, as from make-variable.)  Then you don't introduce
cross-cutting assumptions to the compiler and runtime.

 I have yet to decide which option to take.  Suggestions welcome.

WDYT about mine? :)

 There's also another issue that has come to my attention.  If we must
 support arbitrary syntax-objects to be passed to `local-eval', in many
 (most?) cases this will greatly increase the number of lexicals that
 must be captured, and thus boxed, by (the-environment).

If a tree-il `the-environment' form takes a list of names and gensyms,
then we can provide the possibility in the future to limit the set of
captured bindings.

 So, I'm thinking that (the-environment) should only capture lexical
 variables that are reachable using normal symbols.

I think I disagree here.  It is strictly less useful to capture a subset
of bindings, and it would only be done for efficiency, and it probably
doesn't matter.

So yeah, I guess my arguments here depend on a tree-il the-environment
form.  I wonder if that is the right thing, though; maybe there is a
lower-level concept at work.  The only thing that you need that tree-il
doesn't give you right now is the ability to declare a variable as
boxed, and to capture its identity.

Maybe what we need is a lexical-capture form that evaluates to the
variable corresponding to a bound lexical.  Then `the-environment' could
expand out to

   (make-struct/no-tail lexical-environment
'(name ...)
(list (capture-lexical name) ...))

You would still need support from the expander to get the set of
currently-bound names, but maybe that is a new primitive that we could
add.

Could we do it all with two new low-level primitives?  And then, could
we actually put `the-environment', environment accessors, and everything
else into a module?

Andy
-- 
http://wingolog.org/

Re: summary: lilypond, lambda, and local-eval

[Noah Lavine]

Hello,

 Indeed, only the macro expander has enough information to generate an
 optimal list of reachable lexicals, i.e. lexical variables that are
 accessible using normal symbols (as opposed to syntax objects) [more
 on this below].

 Are you certain that you want to restrict the set of identifiers?

 To me it sounds like an optimization, perhaps premature.

If I understand correctly, Mark wants to restrict the set of variables
you can access to those you could access through normal Scheme code.
This is an issue because psyntax happens to provide a way to access
more variables than standard Scheme. If this is the case, I think we
should absolutely restrict it to standard Scheme, because letting you
access everything psyntax can access a) is not Scheme and b) restricts
our future implementation choices.

 What do you think about having a the-environment tree-il form have a
 field for the names and a field for the gensyms of captured lexicals?

 This is great news, because it means that `the-environment' will no
 longer require its own tree-il type, and the compiler will only see the
 standard scheme code that it expands into.

This actually seems bad to me, although I'm just guessing. Because the
thing is, it's not *really* that Scheme code that you wrote, and so
the compiler is seeing something wrong. It has the same
variable-capture properties as that code, but it's not actually that.
My instinct is that compiling non-accurate code is going to be more
trouble than it's worth, but that's just a guess.

In general, this thread has been very, very impressive. Thanks a lot
to everyone who has been working so hard on this.

Noah

Re: summary: lilypond, lambda, and local-eval

[David Kastrup]

Let me first state that this thread is arguing at a depth where the only
contributions that remain for me to make are syllogisms without an
actual knowledge of what I am talking about.

In order not to appear ungrateful, I will do that, but there will be
little point in expecting me to be of assistance in judging their merit.

Noah Lavine noah.b.lav...@gmail.com writes:

 If I understand correctly, Mark wants to restrict the set of variables
 you can access to those you could access through normal Scheme code.
 This is an issue because psyntax happens to provide a way to access
 more variables than standard Scheme. If this is the case, I think we
 should absolutely restrict it to standard Scheme, because letting you
 access everything psyntax can access a) is not Scheme and b) restricts
 our future implementation choices.

If psyntax accesses more than Scheme can access while doing a task that
is worth doing, what chance would there be in giving Scheme the power to
access what psyntax can?

If exporting enough of the compiler environment to be useful for
implementing multiple compilation units sharing lexical environments is
feasible, what are the implications for splitting a compilation into
separate units when the extent of psyntax is not similarly involved?

In short: where should one draw the line in a way that makes best use of
already done compilations without having to redo too much to be of
practical use?

 In general, this thread has been very, very impressive.  Thanks a lot
 to everyone who has been working so hard on this.

Agreed.

-- 
David Kastrup

Re: summary: lilypond, lambda, and local-eval

[Noah Lavine]

Hello,

 If I understand correctly, Mark wants to restrict the set of variables
 you can access to those you could access through normal Scheme code.
 This is an issue because psyntax happens to provide a way to access
 more variables than standard Scheme. If this is the case, I think we
 should absolutely restrict it to standard Scheme, because letting you
 access everything psyntax can access a) is not Scheme and b) restricts
 our future implementation choices.

 If psyntax accesses more than Scheme can access while doing a task that
 is worth doing, what chance would there be in giving Scheme the power to
 access what psyntax can?

Let me explain what I mean more. Here is a code example:

(let ((x 3))
  (let ((x (* x 5)))
(the-environment)))

At the point of the-environment, there is one Scheme variable around,
'x', and its value is 15. The old value of x is shadowed by the new
one.

But psyntax works by assigning each of these x values a gensym, and
they get different gensyms. So in theory, you could access the outer
value of x (x = 3) if you had a handle on the right gensym.

Supporting this seems weird to me, because I view psyntax as an
implementation detail of Guile, and not something that should affect
programmers. I also think that not supporting it is fine because if
you want to be able to access both values, you can always give your
variables different names. So this isn't giving you more power, but
just a weird way to access it.

 If exporting enough of the compiler environment to be useful for
 implementing multiple compilation units sharing lexical environments is
 feasible, what are the implications for splitting a compilation into
 separate units when the extent of psyntax is not similarly involved?

 In short: where should one draw the line in a way that makes best use of
 already done compilations without having to redo too much to be of
 practical use?

I do not know enough to respond to the rest of your email.

Noah

Re: summary: lilypond, lambda, and local-eval

[Mark H Weaver]

I wrote:
 The compiler-environment would include a list of lexical variable
 names (var ...), which must exactly correspond to the closure slots of
 the `case-lambda', in order to implement `local-eval'.  We _might_ also
 need to include some information about how those variables are stored,

Sorry, this paragraph should have ended here.  The following unfinished
caveat should have been deleted:

 e.g. a flag telling whether they are boxed.  (Usually they will all be
 boxed, but

I was thinking about an edge case where the result of (the-environment)
never escapes the local block, and thus a clever optimizer might be able
to avoid boxing some of the lexicals.  However, I later realized that
this could only happen if the returned environment was never passed to
`local-eval', in which case none of this matters anyway.

 Mark

Re: summary: lilypond, lambda, and local-eval

[David Kastrup]

Andy Wingo wi...@pobox.com writes:

 What are the meanings of these expressions:

I found it amusing to see what my definitions using
with-current-continuation will produce here.

   ;; Toplevel
   (local-eval '(define foo 42) (the-environment))

guile (my-eval '(define foo 42) (my-env))
guile foo
42

   ;; Lexical, tail context
   (local-eval '(define foo 42) (let ((x 100)) (the-environment)))

guile (my-eval '(define foo 42) (let ((x 100)) (my-env)))

Backtrace:
In standard input:
   1: 0* [my-eval (define foo 42) ...
   1: 1*  (let* ((x 100)) (#continuation 1401 @ 9253970 (define foo 42)))
   1: 2   (begin #continuation 1581 @ 9252000)
   1: 3   [#continuation 1401 @ 9253970 ...
   1: 4*   (define foo 42)

standard input:1:11: In procedure memoization in expression (define foo 42):
standard input:1:11: In file standard input, line 0: Bad define placement 
(define foo 42).
ABORT: (syntax-error)
guile 

   ;; Lexical, tail context -- but with a definition
   (local-eval '(begin (define foo 42) foo) (let ((x 100)) (the-environment)))

guile (my-eval '(begin (define foo 42) foo) (let ((x 100)) (my-env)))

Backtrace:
In standard input:
   6: 0* [my-eval (begin (define foo 42) foo) ...
   6: 1*  (let* ((x 100)) (#continuation 1401 @ 9219b38 (begin # foo)))
   6: 2   (begin #continuation 1581 @ 9259a80)
   6: 3   [#continuation 1401 @ 9219b38 ...
   6: 4*   (begin (define foo 42) foo)
   6: 5*   (define foo 42)

standard input:6:18: In procedure memoization in expression (define foo 42):
standard input:6:18: In file standard input, line 5: Bad define placement 
(define foo 42).
ABORT: (syntax-error)
guile 

   ;; Lexical, tail context -- but with a definition, and nested reference
   (local-eval '(begin (define foo 42) (bar))
   (let ((x 100)) (define (bar) foo) (the-environment)))

guile (my-eval '(begin (define foo 42) (bar)) (let ((x 100)) (define (bar) 
foo) (my-env)))

Backtrace:
In standard input:
  13: 0* [my-eval (begin (define foo 42) (bar)) ...
  13: 1*  (let* ((x 100)) (letrec (#) (# #)))
In unknown file:
   ?: 2   (letrec ((bar #)) (#continuation 1401 @ 925e7c0 (begin # #)))
In standard input:
...
  13: 3   [#continuation 1401 @ 925e7c0 ...
  13: 4*   (begin (define foo 42) (bar))
  13: 5*   (define foo 42)

standard input:13:18: In procedure memoization in expression (define foo 42):
standard input:13:18: In file standard input, line 12: Bad define placement 
(define foo 42).
ABORT: (syntax-error)

   ;; Lexical, not a definition context
   (local-eval '(define foo 42) (let ((x 100)) not-a-definition 
 (the-environment)))

guile (my-eval '(define foo 42) (let ((x 100)) hello (my-env)))

Backtrace:
In standard input:
  12: 0* [my-eval (define foo 42) ...
  12: 1*  (let* ((x 100)) hello (#continuation 1401 @ 9253970 (define foo 
42)))
  12: 2   (begin #continuation 1581 @ 9252000)
  12: 3   [#continuation 1401 @ 9253970 ...
  12: 4*   (define foo 42)

standard input:12:11: In procedure memoization in expression (define foo 42):
standard input:12:11: In file standard input, line 11: Bad define placement 
(define foo 42).
ABORT: (syntax-error)
guile 

 What about this one:

   ;; Keeping in mind that `or' expands to (let ((t ...)) (if t t ...)),
   ;; hygienically
   (local-eval 't '(let ((t 42)) (or #f (the-environment 

Assuming that the second quote mark is a typo.

guile (my-eval 't (let ((t 42)) (or #f (my-env
42
guile 

Now of course, the continuation based approach that just hijacks the
expander and jumps in and out of it is not really a measure of how
things should work.  But it makes clear that (the-environment) is a bit
of a chimera: it captures content at a level conceptually relevant for
(define), but returns a value and has to be placed accordingly, like in
a function call or at the providing side of a binding construct.

If those different syntactic aspects prove to be too hard to conciliate,
it might help to look at the kind of interface that some other chimeras
like call-with-values or call-with-current-continuation have taken.

-- 
David Kastrup

Re: summary: lilypond, lambda, and local-eval

[Hans Aberg]

On 16 Dec 2011, at 11:33, Mark H Weaver wrote:

 Here's what I currently see:
 
 scheme@(guile-user) (local-eval #'t (primitive-eval '(let ((t 42)) (or #f 
 (the-environment)
 ERROR: In procedure memoize-variable-access!:
 ERROR: Unbound variable: t
 
 This is the correct behavior, no?

This is what I get when I play around with the following variation of David's 
code in Guile 2.0.3:
(define (xxx)
  (let* ((x 2))
(set! x (+ x 3))
(interaction-environment)))

(eval '(begin (set! x (+ x 5)) x) (xxx))

My guess (correct?) is that one wants some variation of 
(interaction-environment) that can cause x in the eval expression to bind to 
the environment returned by (xxx).

Might eval be changed to accommodate for that (without introducing the name 
local-eval)?

Hans

Re: summary: lilypond, lambda, and local-eval

[Hans Aberg]

On 16 Dec 2011, at 13:43, David Kastrup wrote:

 Here's what I currently see:
 
 scheme@(guile-user) (local-eval #'t (primitive-eval '(let ((t 42))
 (or #f (the-environment)
 ERROR: In procedure memoize-variable-access!:
 ERROR: Unbound variable: t
 
 This is the correct behavior, no?
 
 This is what I get when I play around with the following variation of 
 David's code in Guile 2.0.3:
 (define (xxx)
  (let* ((x 2))
(set! x (+ x 3))
(interaction-environment)))
 
 (eval '(begin (set! x (+ x 5)) x) (xxx))
 
 My guess (correct?) is that one wants some variation of
 (interaction-environment) that can cause x in the eval expression to
 bind to the environment returned by (xxx).
 
 Might eval be changed to accommodate for that (without introducing the
 name local-eval)?
 
 It would likely help with unasking the question of what to do when
 (current-module) is different at the time of local-eval.  I don't know,
 however, what the _lexical_ effects of switching the current module are
 supposed to be.  If it is supposed to be a noop, then lexical
 environments and modules are presumably orthogonal, and eval should
 likely be allowed to take both (currently, local-eval is like taking a
 lexical environment and using primitive-eval in it).

Would you not it work as though you inserted code in the place where then 
environment? - Then the syntactical rules should be captured as well.

In addition, there should be a way to communicate with the surrounding 
environment, wherefrom the code is inserted. The only truly safe way would be 
to make that explicit somehow, if not merely returning a value suffices.

Hans

summary: lilypond, lambda, and local-eval

[Andy Wingo]

Hi,

The delayed evaluation thread is a bit long and confusing, so I would
like to try to summarize it.

Lilypond has a way to embed Lilypond code in Scheme, and Scheme code in
Lilypond code.  The former uses a reader macro, #{#}.  The latter uses
specially-marked variables and expressions, specifically, those preceded
by $ or #.

For example, the following Scheme expression is an embedded lilypond
code fragment:

#{ \displayLilyMusic $p #}

which expands out at read-time to:

(#procedure embedded-lilypond (parser lily-string filename line closures)
 parser
  \\displayLilyMusic $p 
 #f
 0
 (list (cons 20 (lambda () p

Here the procedure is embedded in the output of the reader macro.  We
can see that the $p is translated to (cons 20 (lambda () p)).  Whenever
$p is evaluated, that lambda is run.

Embedded Scheme (via $ or #) has access to Scheme's environment.
Variables in lilypond are in a separate environment (implemented using
modules), so we don't have to be concerned about lilypond accessing or
defining Scheme lexicals.

David hacks on Lilypond.  He notes that the above expression used to
expand out to:

(#procedure embedded-lilypond (parser lily-string filename line closures)
 parser
  \\displayLilyMusic $p 
 #f
 0
 (the-environment))

in 1.8.  Then, whenever lilypond needed to evaluate an embedded Scheme
value, it would use `local-eval' with the captured environment.  It is
clearly much more convenient for lilypond hackers than having to scan
for embedded Scheme beforehand and build up closures for each embedded
Scheme expression.  David noted that while the closure solution works
for him, he wondered if there was something better to use.

It took some time for everyone to understand the problem.  In the end,
there were four workable possibilities.

  1) Keep using closures.

  2) Incorporate local-eval and the-environment into Guile 2.0.

  3) Have lilypond use its own evaluator or compiler.

  4) Have lilypond make the embedded lilypond code expand out to actual
 Scheme.  (It was unclear whether the lilypond grammar allowed
 this.)

Mark and Noah looked at implementing local-eval, and I recommended
staying with the closure solution.  Ludovic noted success with method
(3) in the Skribilo context.

I would like to start a new thread around local-eval, but besides that,
we should probably agree on the summary first.  So please do send any
corrections to this summary to the list.  Thanks :)

Andy
-- 
http://wingolog.org/

Re: summary: lilypond, lambda, and local-eval

[Hans Aberg]

On 15 Dec 2011, at 11:21, Andy Wingo wrote:

 The delayed evaluation thread is a bit long and confusing, so I would
 like to try to summarize it.
 
 Lilypond has a way to embed Lilypond code in Scheme, and Scheme code in
 Lilypond code.  The former uses a reader macro, #{#}.  The latter uses
 specially-marked variables and expressions, specifically, those preceded
 by $ or #.
...
 It took some time for everyone to understand the problem.  In the end,
 there were four workable possibilities.
 
  1) Keep using closures.

When doing a parser on top of Guile, I noticed one must first build an 
unevaluated closure, and only thereafter call the evaluator. Scheme has some 
restrictions forcing this, for example, the lambda cannot appear as a free 
symbol, though it is possible in Guile using scm_sym_lambda. 

It might be useful with a variation of scm_eval_string() that only parses and 
builds the closure, but not calls the evaluator.

Hans

Re: summary: lilypond, lambda, and local-eval

[Hans Aberg]

On 15 Dec 2011, at 18:24, David Kastrup wrote:

 The delayed evaluation thread is a bit long and confusing, so I would
 like to try to summarize it.
 
 Lilypond has a way to embed Lilypond code in Scheme, and Scheme code in
 Lilypond code.  The former uses a reader macro, #{#}.  The latter uses
 specially-marked variables and expressions, specifically, those preceded
 by $ or #.
 ...
 It took some time for everyone to understand the problem.  In the end,
 there were four workable possibilities.
 
 1) Keep using closures.
 
 When doing a parser on top of Guile, I noticed one must first build an
 unevaluated closure, and only thereafter call the evaluator. Scheme
 has some restrictions forcing this, for example, the lambda cannot
 appear as a free symbol, though it is possible in Guile using
 scm_sym_lambda.
 
 It might be useful with a variation of scm_eval_string() that only
 parses and builds the closure, but not calls the evaluator.
 
 I am not sure what you mean with closure here, but just read parses
 a form.

I build them from scratch, using the scm_x calls, with a parser. This way, it 
is possible to a more than within the Scheme paradigm itself. For example,
  scm_list_x(scm_sym_lambda, ...)
gives an unevaluated lambda-expression. Some symbols are not available in 
Guile, so for example, I have in my init():
  SCM list_ = scm_from_locale_symbol(list);

After an expression has been built, the parser calls scm_primitive_eval(). 
However, suppose one wants to insert some Scheme code in to the expression, 
then scm_eval_string() will call the evaluator, enforcing that only complete 
Scheme expressions can be inserted:

Without that restriction it would be possible to have an expression like
  f := x |- scheme (+ x 1)
where only the quote is the actual scheme code and the other handled by the 
external parser, and where the external x binds to the one in the Scheme code 
string (+ x 1). However, when scm_eval_string() calls the evaluator, one gets 
an error, because x is not bound.

Hans

Re: summary: lilypond, lambda, and local-eval

[Mark H Weaver]

Hello all,

Although it has not yet been decided whether `local-eval' will be
accepted into Guile 2, I've decided to proceed with a proper
implementation that is fully integrated into the compiler.

I hope to demonstrate that this feature can be implemented easily
without creating any significant maintenance burden.

Here's an outline of my plan:


How to compile (the-environment)


Most passes of the compiler will pretend that (the-environment) is
replaced by tree-il code corresponding to the following standard scheme
code:

  (make-lexical-environment  ;; a normal procedure (constructor)
(case-lambda  ;; general dispatcher to access or mutate any lexical
  (() #f)
  ((name-XXX);; name-XXX is a gensym
   (case name-XXX
 ((var) var) ;; one clause for each lexical
 ...))
  ((name-XXX value-XXX)  ;; name-XXX and value-XXX are gensyms
   (case name-XXX
 ((var) (set! var value-XXX)) ;; one clause for each lexical
 ...)))
(quote compiler-environment)  ;; simple list structure
(quote expander-environment)  ;; simple list structure
module)  ;; XXX not sure how best to represent this

The expander-environment is extracted from the tree-il node
corresponding to (the-environment), created by the macro expander.
I've already implemented this part in my previous patch.

The compiler-environment would include a list of lexical variable
names (var ...), which must exactly correspond to the closure slots of
the `case-lambda', in order to implement `local-eval'.  We _might_ also
need to include some information about how those variables are stored,
e.g. a flag telling whether they are boxed.  (Usually they will all be
boxed, but

Note that general-purpose dispatcher will not actually be used by
`local-eval'.  Its purpose is primarily to force all of the visible
lexicals to be boxed and included within the closure.  They are also
there to make any fancy optimizers do the right thing.

KEY POINT: Since the general-purpose dispatcher would be sufficient to
implement `local-eval' in standard scheme, it communicates exactly the
right facts to the code analyzers, no matter how clever they are, and it
does so without the analyzers having to know anything about these new
primitives!


How to implement `local-eval'
=

When `local-eval' is called on a lexical environment that was created by
compiled code, it will do the following:

* Macroexpand the local expression within expander-environment.

* Compile the expanded expression within compiler-environment.
  (I'll explain how to do this below)

* Make a copy of the closure from the lexical environment object, but
  replace its code (the dispatcher) with the newly compiled code.

* Call the newly created closure.

So, the trick is to make sure that the newly compiled code accesses the
closure variables in exactly the same way as the general-purpose
dispatcher.

I haven't yet dug deeply enough into the compiler internals to know the
best way to do this.  Ideally I would create a new procedure to handle
this simply and robustly, making use of compiler-environment.

For now, I will describe a method that I suspect would do the right
thing without any new compiler interfaces, though not as efficiently or
robustly: Simply compile the same general-purpose dispatcher as before,
except replace the #f (from the first case-lambda clause) with the
expanded local expression:

  (lambda (var ...)  ;; list of lexicals from compiler-environment
(case-lambda
  (() expanded local expression)
  ((name-XXX);; name-XXX is a gensym
   (case name-XXX
 ((var) var) ;; one clause for each lexical
 ...))
  ((name-XXX value-XXX)  ;; name-XXX and value-XXX are gensyms
   (case name-XXX
 ((var) (set! var value-XXX)) ;; one clause for each lexical
 ...

and then extract the code from the inner `case-lambda'.  As described
above, this code would replace the code portion of the captured closure.

NOTE: This assumes that case-lambda creates only one closure for all
cases.  I confess that I haven't yet verified this suspicion.  If this
is not true, one could replace the case-lambda with the equivalent using
standard scheme.


Again, I don't expect to actually use this hack.  I expect to simply
introduce a new internal compiler interface that essentially does the
same thing, but in a less fragile way.

However, I hope that these draft notes will give confidence that it is
possible to implement `the-environment' and `local-eval' without adding
any additional complexity to the compiler.  No changes should be needed
to the analysis or optimization passes, aside from adding some clauses
to `record-case' for `the-environment' tree-il nodes, and a new
procedure or two to handle `local-eval'.

I intend to implement this soon.  Comments and suggestions solicited.

 Best,
  Mark