How to pass let and named-let to the backend

Asked by higepon(Taro Minowa) on 2009-08-24

Hi.

I use your psyntax for Mosh Scheme.

Since Mosh's backend has let and named-let optimization,
I want to pass them to the backend. (Now, they are converted to lambda and letrec by psyntax).

On expander.ss, I defined core-macro for as follows.
But got unbound identifier error for named-let's name (ex loop, f or rec).

(lambda (e r mr)
      (syntax-match e ()
        ((_ ((lhs* rhs*) ...) b b* ...)
         (if (not (valid-bound-ids? lhs*))
             (invalid-fmls-error e lhs*)
             (let ((lex* (map gen-lexical lhs*))
                   (lab* (map gen-label lhs*)))
               (let ((rib (make-full-rib lhs* lab*))
                     (r (add-lexicals lab* lex* r)))
                 (let ((body (chi-internal
                               (add-subst rib (cons b b*)) r mr))
                       (rhs* (chi-expr* (map (lambda (x) (add-subst rib x))
                                             rhs*) r mr)))
                   (build-let no-source lex* rhs* body))))))
        ((_ loop ((lhs* rhs*) ...) b b* ...)
         (if (not (valid-bound-ids? lhs*))
             (invalid-fmls-error e lhs*)
             (let ((lex* (map gen-lexical lhs*))
                   (lab* (map gen-label lhs*)))
               (let ((rib (make-full-rib lhs* lab*))
                     (r (add-lexicals lab* lex* r)))
                 (let ((body (chi-internal
                               (add-subst rib (cons b b*)) r mr))
                       (rhs* (chi-expr* (map (lambda (x) (add-subst rib x))
                                             rhs*) r mr)))
                   (build-named-let no-source (gen-lexical loop) lex* rhs* body))))))))

Will you please teach me what's wrong?

Cheers.

Question information

Language:
English Edit question
Status:
Solved
For:
r6rs-libraries Edit question
Assignee:
No assignee Edit question
Solved by:
higepon(Taro Minowa)
Solved:
2009-08-25
Last query:
2009-08-25
Last reply:
higepon(Taro Minowa) (higepon) said : #1

the following code works well.

Thank you!

(define let-transformer
    (lambda (e r mr)
      (syntax-match e ()
        ((_ ((lhs* rhs*) ...) b b* ...)
         (if (not (valid-bound-ids? lhs*))
             (invalid-fmls-error e lhs*)
             (let ((lex* (map gen-lexical lhs*))
                   (lab* (map gen-label lhs*))
                   (rhs* (chi-expr* rhs* r mr)))
               (let ((rib (make-full-rib lhs* lab*))
                     (r (add-lexicals lab* lex* r)))
                 (let ((body (chi-internal
                               (add-subst rib (cons b b*)) r mr)))
                   (build-let no-source lex* rhs* body))))))
        ((_ loop ((lhs* rhs*) ...) b b* ...)
         (if (not (valid-bound-ids? lhs*))
             (invalid-fmls-error e lhs*)
             (let ((lex* (map gen-lexical lhs*))
                   (lab* (map gen-label lhs*))
                   (rhs* (chi-expr* rhs* r mr))
                   (loop-lex (gen-lexical loop))
                   (loop-lab (gen-label loop)))
               (let ((rib (make-full-rib (cons loop lhs*) (cons loop-lab lab*)))
                     (r (add-lexicals (cons loop-lab lab*) (cons loop-lex lex*) r)))
                 (let ((body (chi-internal
                               (add-subst rib (cons b b*)) r mr)))
                   (build-named-let no-source loop-lex lex* rhs* body)))))))))

Abdulaziz Ghuloum (aghuloum) said : #2

You should have two ribs: one for the lhs*, and one for the loop variable.
You don't want to add them all into the same rib since the loop variable may have the same name as one of the lhs*, and this violates the invariant that all identifiers in a rib are disjoint (according to bound-identifier=?).

I also completely recommend that you make the Mosh compiler/interpreter translate
((lambda (lhs* ...) body) rhs* ...)
to
(let ((lhs* rhs*) ...) body)
itself, instead of adding other core forms. This (1) catches all expansions of let, and (2) catches the cases when the user has written the ((lambda ...) ...) himself (possibly by writing his own macro of let for example).

This is how most compilers work (I hope!), and this is why psyntax does not provide a special let/named-let forms at all.

Aziz,,,

leppie (leppie) said : #3

> I also completely recommend that you make the Mosh compiler/interpreter translate
> ((lambda (lhs* ...) body) rhs* ...)
> to
> (let ((lhs* rhs*) ...) body)

I was going to suggest that too, as it is easy to do.

The named let is a bit harder. Personally, I feel letrec is easier to to work with, and you would have the same constraints as you would have for a named let. You could probably apply your named let optimization to letrec :)

Cheers

leppie

leppie (leppie) said : #4

As silly as it sounds, you have to optimize for cases like:

(let-values ((a (values 1 2 3))) a)

I think the Scheme programmer relies a lot on the Scheme compiler to optimize any extra fluff away.

higepon(Taro Minowa) (higepon) said : #5

Abdulaziz Ghuloum wrote:
> You should have two ribs: one for the lhs*, and one for the loop variable.
> You don't want to add them all into the same rib since the loop variable may have the same name as one of the lhs*

Thank you. Fixed as follows.

((_ loop ((lhs* rhs*) ...) b b* ...)
         (if (not (valid-bound-ids? lhs*))
             (invalid-fmls-error e lhs*)
             (let ((lex* (map gen-lexical lhs*))
                   (lab* (map gen-label lhs*))
                   (rhs* (chi-expr* rhs* r mr))
                   (loop-lex (gen-lexical loop))
                   (loop-lab (gen-label loop)))
               (let ((loop-rib (make-full-rib (list loop) (list loop-lab))) ;; loop rib
                     (rib (make-full-rib lhs* lab*)) ;; loop rib
                     (r (add-lexicals (cons loop-lab lab*) (cons loop-lex lex*) r)))
                 (let ((body (chi-internal
                               (add-subst loop-rib (add-subst rib (cons b b*))) r mr)))
                   (build-named-let no-source loop-lex lex* rhs* body))))))

> I also completely recommend that you make the Mosh compiler/interpreter translate

I aggree this is compilers work.
Actually the problem is named-let, our compiler detects named-let and do some optimization for it (like goto loop).
Of course the compiler can convert leterec to named-let, but it is tough.

leppie wrote:
> apply your named let optimization to letrec :)

You're right, but a little bit difficult for an implementation reason.

> As silly as it sounds, you have to optimize for cases like:
> (let-values ((a (values 1 2 3))) a)

BTW, since Mosh VM has receive (srfi-8) instruction and values registers,
converting let-values to lambda call is unnecesary.

Cheers.