Pass which outputs to * can't recursively evaluate expressions?

[Tom Cheng]

Hello,

I'm defining a simply language for adding / subtracting numbers, e.g. `(add (sub 3 2) 4)`. Here is the language definition:

(define-language
  Lsrc
  (terminals (number (n)))
  (Expr (e)
        n
        (add e0 e1)
        (sub e0 e1)))

I want to create a pass which will take an Expr and evaluate the result. I had thought the pass would be `Expr (ir) -> * ()`. Here is my pass:

(define-pass
  eval-src : Lsrc (ir) -> * ()
  (Expr : Expr (ir) -> * ()
        (,n n)
        ((add ,(e0) ,(e1)) (+ e0 e1))
        ((sub ,(e0) ,(e1)) (- e0 e1))
        ))

Numbers are just expanded to their value, add/sub expressions are evaluated with racket using `+` and `-`.

However, I get this error when compiling the pass:

compiler.rkt:XXX:15: define-pass: cannot find a transformer that accepts input type Expr and no output type

the line number / char number points here:

        ((add ,(e0) ,(e1)) (+ e0 e1))
---------------^            

It would seem that nanopass struggles to recursively evaluate passes that output to *? I'm assuming this is because whilst `(add Expr Expr)` is defined as a pattern, `(add Expr *)` isn't.

Is there any way to also match (add Expr *), (add * Expr) etc? Or is there a good work-around for this?

Thanks.

[Andy Keep]

Hey,

The issue here is actually one of types.  The cata-morphism system searches based (roughly) on function type.  When you specify a cata-morphism like ,[e0] in a processor that takes an input language and produces no output language form, it will automatically determine the input terminal or non-terminal from the position of the cata-morphism, in this case Expr, and since you have indicated it should produce a single output value, it is looking for a processor that takes an Expr and returns one value (Expr -> scheme-object).  The type signature of your Expr processor takes an Expr and indicates that it produces no value (Expr -> ()).

You can fix this by specifying: Expr : Expr (ir) -> * (x)  or something like that.  (In general the x represents an extra expression that is returned when a clause is auto generated.  in this case you do not have any autogenerated clauses so it doesn't really matter what you put there, but it can be useful for debugging to use a variable that would raise an unbound variable exception if you extend the language and forget to add the value.)

-andy:)

[Giuliano Losa]

Hi Andy,

I ran into the same problem while trying the nanopass framework in Racket and even with your answer it took some tinkering to make it work.

This is not a question, because I did make it work in the end.

I'm just posting my solution and some comments if that can be useful to someone else.

Initially I tried the following, which fails with `cannot auto-generate body for pass with extra return values in: eval-src`.

(define-pass
  eval-src : Lsrc (ir) -> * (n)
  (Expr : Expr (ir) -> * (n)
        (,n n)
        ((add ,[e0] ,[e1]) (+ e0 e1))
        ((sub ,[e0] ,[e1]) (- e0 e1))))

I was a bit puzzled by this error because I couldn't figure out what it was trying to auto-generate. It would be nice if the error message said what it was!

In the end I figured I need to add a body expression and it works:

(define-pass
  eval-src : Lsrc (ir) -> * (n)
  (Expr : Expr (ir) -> * (n)
        (,n n)
        ((add ,[e0] ,[e1]) (+ e0 e1))
        ((sub ,[e0] ,[e1]) (- e0 e1)))
  (Expr ir))

While tinkering before finding the above solution, I found that this works too (without a body expression):

(define-pass
  eval-src : Lsrc (ir) -> * ()
  (Expr : Expr (ir) -> * ()
        (,n n)

        ((add ,[Expr : -> e0] ,[Expr : -> e1]) (+ e0 e1))
        ((sub ,[Expr : -> e0] ,[Expr : -> e1]) (- e0 e1))))

However, the following fails with `eval-src: incorrect arguments for Expr in cata in: (Expr : -> e0)`

(define-pass
  eval-src : Lsrc (ir) -> * (n)
  (Expr : Expr (ir) -> * (n)
        (,n n)
        ((add ,[Expr : -> e0] ,[Expr : -> e1]) (+ e0 e1))
        ((sub ,[Expr : -> e0] ,[Expr : -> e1]) (- e0 e1)))
  (Expr ir))

But the following works:

(define-pass
  eval-src : Lsrc (ir) -> * (n)
  (Expr : Expr (ir) -> * (n)
        (,n (values 0 n))
        ((add ,[Expr : -> z1 e0] ,[Expr : -> z2 e1]) (values 0 (+ e0 e1)))
        ((sub ,[Expr : -> z1 e0] ,[Expr : -> z2 e1]) (values 0 (- e0 e1))))
  (Expr ir))