Counting elements in a pass, and more.

[Simon Stapleton]

Hello

So, I've been fiddling with nanopass some more, found myself with a need to label expressions.  It occurred to me that, for a given language, the order of expression traversal could be used as an implicit label, if I could somehow get "this is the nth expression encountered" during a pass, I could use that instead of an explicit labelling pass and a whole new language.

The extra arguments given to a pass looked like a hopeful place to do this.  The "obvious" way to do this is to have a counter and increment it in every transformer; that requires manually writing every transformer, however, including those for terminals.  Another option would be using the "default" for extra arguments, viz:

(Expr : Expr (ir, [i (incremented-counter)] -> Expr () …)

where incremented-counter increments the counter, and then allowing i to default on every transformer.  Unfortunately, that fails as incremented-counter is evaluated once at the top level, and its return value used in its place.  Which kinda makes sense depending on which way you look at things, but doesn't help me.

Now, it seems fairly obvious that providing explicit labelling is a pretty common need (think, for example, generating live intervals for variables during register allocation), but I think the ability to run some arbitrary code at the start / end of every transformer, whether manually written or auto-generated, might be a more generally useful thing.

I can think of a few ways to do this, and will continue experimenting, unless I've missed something extremely obvious (more than likely).

I also think I've found a bug in pass.ss, around line 1297 in `build-args`...

(cond

                   [(null? callee-fml*) '()]

                   [(and (fxzero? required-cnt) (null? caller-fml*))

                    (cons (car callee-init*)

                      (f required-cnt (cdr callee-fml*) (cdr callee-init*) caller-fml*))]

                   [(fxzero? required-cnt)

                    (cons (car caller-fml*)

                      (f required-cnt (cdr callee-fml*) (cdr callee-init*) (cdr caller-fml*)))]

                   [else (cons (car caller-fml*)

                           (f (fx- required-cnt 1) (cdr callee-fml*) callee-init*  (cdr caller-fml*)))])

surely the second condition will never be met?

Regards

Simon

[Simon Stapleton]

Forgot to mention, also, that the documentation won't build, missing scheme.sty and a few bits of makefile stuff.

[Andy Keep]

Hey Simon,

I’ve not encountered this in the context of what I’ve done with the nanopass framework, but I have used it when working on various abstract-abstract machine implementations for doing abstract interpretation.

We do not have any particular facility for doing this with the nanopass framework, and depending on how you structure the the language and where you place the counters, I would imagine that nanopass framework would not be able to help much with boiler plate code, since the input language and output language would have very few productions that have exactly the same form, which is what drives the nanopass framework.

All of that said, adding something like this might not be too hard, if I understand what you are looking for correctly.

If I understand what you are looking for, if you had a language like:

(define-language L

  (terminals

    (symbol (x)))

  (Expr (e)

    x

    (e0 e1)

    (lambda (x) e)))

You would label it with a language something like:

(define-language L-labelled

  (extends L)

  (entry lab-e)

  (terminals

    (+ (label (l))))

  (LabelExpr (lab-e)

    (+ (label l e))))

or

(define-language L-labelled-alt

  (extends L)

  (terminals

    (+ (label (l)))

  (Expr (e)

    (- x

       (lambda (x) e)

       (e0 e1))

    (+ (ref l x)

        (lambda l (x) e)

        (call l e0 e1))))

It seems like it should be possible to write a macro that makes use of the compile-time record representation of the language to generate a new language and a set of passes for going between the original language and the labeled language and vice versa, especially if the labelling can be done systematically.

Is that something like what you had in mind?

As a side node, you can do live-analysis without any need for labels.  Have a look at the Chez Scheme (github.com/cisco/ChezScheme ) liveness passes to see how we compute the conflict graph without it.

Note about your bug below:

The second condition is met when you write a transformer with no input language that may or may not have an output language.  For instance:

(define-pass foo : L0 (x) -> L1 ()
  ---
  (Expr : * () -> Expr ()
    (cond
      [e0 `(---)]
      [e1 `(---)]
      [else `(---)]))
  ---)

The nanopass framework is actually setup to generalize to simple scheme functions, so you can define a pass or transformer with a * -> * type, which degrades to a normal scheme function with no particular extras built upon it.

It may not come up very often, but there is no particularly good reason to restrict it either.

-andy:)

Regards

Simon

--
You received this message because you are subscribed to the Google Groups "nanopass-framework" group.
To unsubscribe from this group and stop receiving emails from it, send an email to  nanopass-framew...@googlegroups.com .
To post to this group, send email to  nanopass-...@googlegroups.com .
To view this discussion on the web visit  https://groups.google.com/d/msgid/nanopass-framework/57f73a09-5ea7-4b57-a21f-5664a2156737%40googlegroups.com .
For more options, visit  https://groups.google.com/d/optout .

[Andy Keep]

On April 10, 2016 at 3:11:48 AM, Simon Stapleton (simon.s...@gmail.com) wrote:

Forgot to mention, also, that the documentation won't build, missing scheme.sty and a few bits of makefile stuff.

Thanks for the note.  This is because until very recently stex, the system I used to write this, was not readily available.  You will notice there is a user-guide.pdf in the doc directory, this is generated from the user-guilde.stex file.

Now that stex is available (github.com/dybvig/stex) along with Chez Scheme (github.com/cisco/ChezScheme) for that matter, it should be possible to get this working, though there is a bit of clean-up that needs to be done to make this easy, since there are a handful of prerequisites and it would be nice to have a configure script to determine if there are any missing pieces.

I’ve added an issue in the github issue tracker for this.  Thanks again!

-andy:)

--
You received this message because you are subscribed to the Google Groups "nanopass-framework" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nanopass-framew...@googlegroups.com.
To post to this group, send email to nanopass-...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/nanopass-framework/6eeb83ae-5b65-497c-8a2e-22786fa95d61%40googlegroups.com.

[Simon Stapleton]

> It seems like it should be possible to write a macro that makes use of the compile-time record representation of the language to generate a new language and a set of passes for going between the original language and the labeled language and vice versa, especially if the labelling can be done systematically.
>
> Is that something like what you had in mind?

Not entirely, I was hoping to avoid having to make a labelled language entrely, keeping the labelling implicit. That said, explicitly labelling is probably a far more sensible way to go.

> As a side node, you can do live-analysis without any need for labels. Have a look at the Chez Scheme (github.com/cisco/ChezScheme ) liveness passes to see how we compute the conflict graph without it.

Funnily enough, I’ve got my nose buried in that at the moment...

>
> Note about your bug below:

It lies in my grey matter. I’d conflated callee-fml* and caller-fml* because I’m an idiot :)

Simon

[Andy Keep]

On May 1, 2016 at 2:02:47 AM, Simon Stapleton (simon.s...@gmail.com) wrote:

> It seems like it should be possible to write a macro that makes use of the compile-time record representation of the language to generate a new language and a set of passes for going between the original language and the labeled language and vice versa, especially if the labelling can be done systematically. 
> 
> Is that something like what you had in mind? 

Not entirely, I was hoping to avoid having to make a labelled language entrely, keeping the labelling implicit. That said, explicitly labelling is probably a far more sensible way to go. 

It depends a bit on what you’re looking for in implicit labelling.  If you simply want to differentiate expression A from expression B, each expression is “implicitly labelled” by its position in memory, and you can use eq? to determine when two expressions are the same or different.  Potentially you could even use this to recover some of the explicit properties you are looking for by using an eq-hashtable to map expressions in your language to explicit labels.  You can get ordering and properties like that from building your hash table.  One caveat with this approach is that if you have terminals that would be eq to each other without representing the same “labelled” position you’d need to come up with some way to handle this (potentially by wrapping your terminal in a record or only using nonterminals to represent it.

As I mentioned, I think it should be possible to write a macro to make some of the explicit labelling work easier, with one caveat: if you are hoping to know that expression A will be evaluated before expression B, it will be necessary to tell the macro what the order of things are.  As a for instance, if the language has the following forms:

(call e0 e* …)

(if e0 e1 e2)

(begin e* … e)

(my-awesome-production a b c d e)

What order should it be labelled? The nanopass framework understands the grammar, but doesn’t know anything about the order the things happen, so we’d need a way to communicate that additional information.

> As a side node, you can do live-analysis without any need for labels. Have a look at the Chez Scheme (github.com/cisco/ChezScheme ) liveness passes to see how we compute the conflict graph without it. 

Funnily enough, I’ve got my nose buried in that at the moment... 

It is fun that this is out there now :)

-andy:)