Trouble with recursive lambda macros, using Y combinator

[Vasily Rybakov]

Hi!

I'm learning Racket and I stumpbled into a couple of problems with macros.

I tried to make macros that implements recursive lambda, but not the classic one (that uses letre), but the one that uses Y combinator.

So it should work like this:

(recursion fact (n)
(if (zero? n)
1
(* n (fact (sub1 n)))))

transforms into

((lambda (x) (x x))
(lambda (fact)
(lambda (n)
(if (zero? n) 1 (* n ((fact fact) (sub1 n)))))))

which produces recursive anonymous function to compute factorial.

So I wrote this macros:

(define-syntax recursion
(syntax-rules ()
[(_ label (args ...) body ...)
((lambda (x) (x x))
(lambda (label)
(lambda (args ...)
(substitute-term label (label label) body) ...)))]))

(substitute-term) macros is helper macros to substitute one piece of code with another, here its fist version:

(define-syntax (substitute-term stx)
(syntax-case stx ()
[(_ term-from term-to body)
(cond
[(null? (syntax-e #'body)) #'(void)]
[(list? (syntax-e #'body)) #`#,(map (lambda (x) (append (syntax-e #'(substitute-term term-from term-to)) (if (list? x) x (list x)))) (syntax-e #'body))]
[else (if (equal? (syntax-e #'body) (syntax-e #'term-from)) #'term-to #'body)])]))

>(substitute-term - + (- 1 2))
3

This works. But

>(substitute-term and or (and #t #f))
or: bad syntax in: or

Macro stepper shows that it expands into

(or (substitute-term and or #t) (substitute-term and or #f))

And after this step is "bad syntax" error. I couldn't figure why is this and how to fix it. It raises "bad syntax" errors with all special forms for some reason. Can somebody explain to me -- why? And how to fix it?

Then I tried rewrite (substitute-term) macro:

(define-syntax (substitute-term-2 stx)
(syntax-case stx ()
[(substitute-term term-from term-to body)
(datum->syntax stx (for-substitute-term (syntax->datum #'term-from) (syntax->datum #'term-to) (syntax->datum #'body)))]))

It uses helper function (define-for-syntax) which do all the work:

(define-for-syntax (for-substitute-term term-from term-to expr)
(cond
[(null? expr) (void)]
[(list? expr) (map (lambda (x) (apply for-substitute-term (list term-from term-to x))) expr)]
[else (if (equal? expr term-from) term-to expr)]))

>(substitute-term-2 and or (and #t #f))
#t

Hurray! But if I use it in my (recursion) macro:

(define-syntax recursion-2
(syntax-rules ()
[(_ label (args ...) body ...)
((lambda (x) (x x))
(lambda (label)
(lambda (args ...)
(substitute-term-2 label (label label) body) ...)))]))

>((recursion-2 fact (n)
(if (zero? n)
1
(* n (fact (sub1 n))))) 5)
n: unbound identifier in module
context...:
other binding...: in: n

Although macro stepper shows that it expands into

((lambda (x) (x x))
(lambda (fact)
(lambda (n)
(substitute-term-2
fact
(fact fact)
(if (zero? n) 1 (* n (fact (sub1 n))))))))

Which if entered in interaction area works as intended. I understand that binding for n is lost when I invoke (substitute-term-2) macro on body. But I couldn't find in documentation -- why? And how to fix it?

I would be grateful, if somebody explained to me what's wrong with my first and my second attempts and how to fix them. Thanks!

[Gustavo Massaccesi]

In the first method, the problem is #%app
https://docs.racket-lang.org/reference/application.html?q=%23%25app
It's hidden by the default configuration of the macro stepper. Try
changing the configuration to show it.

The problem is that the expansion is:

(substitute-term and or (and #t #f))

---> first item is a macro, so apply it

((substitute-term and or and) (substitute-term and or #t)
(substitute-term and or #f))

--> first item is not a macro (it's only something that calls a
macro), so add #%app

(#%app (substitute-term and or and) (substitute-term and or #t)
(substitute-term and or #f))

--> first item is a especial form, so analyze the subexpressions

(#%app *(substitute-term and or and)* (substitute-term and or #t)
(substitute-term and or #f))

--> first item in the second subexpression is a macro, so apply it

(#%app or (substitute-term and or #t) (substitute-term and or #f))

--> no surprises in the other subexpressiosn, I'll skip the repetitive steps

(#%app or #t #f)

--> now everything is expanded, so #%app want's to call the function
that is the first argument, but it's a macro instead of a function.
--> error



To fix it, I think it's necessary that substitute-term does more work,
and tries to replace the first expression directly instead of using
recursion.

(substitute-term and or (and #t #f))

---> first item is a macro, so apply it

(and (substitute-term and or #t) (substitute-term and or #f))

where in the first position, the or->and is replaced directly. I also
think this will be easier if you use syntax-case instead of case and
syntax-e.


************************

The problem with the second method is in the line

(datum->syntax stx (for-substitute-term (syntax->datum #'term-from)
(syntax->datum #'term-to) (syntax->datum #'body)))

This is unhygienic because in the substitution all the
marks/scopes/whatever are lost.

In this case, when #'body is n, the n is not a plain n, is an n that
has a scope that says that it's the argument of the function. When the
macro applies (syntax->datum #'body) then the result is the symbol 'n
without additional information, it's almost a like string of text.
Later when the macro calls (datum->syntax stx (...)) then the symbol
'n get the scopes from the syntax, that are probably the wrong scopes,
so the result is not the n that is the argument of the function but
another n, perhaps the toplevel n that should be defined in the
module.

This explanation is very very very confusing. I'm confused. I'm not
even sure it's 100% accurate, but the general idea is right. Anyway,
the takeaway is "Don't do it!!!!!!!!!!!!". Or to be more precise, only
try this after studding carefully about the hygiene system.

Gustavo

> --
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Jens Axel Søgaard]

Rather than use substitute-term you can bind name to do the right thing.

For example:

#lang racket

(require (for-syntax syntax/parse))

(define-syntax (recursion stx)

  (syntax-parse stx

    [(_recursion name (arg ...) expr)

     #'( (λ (x) (x x))

         (λ (name)

           (λ (arg ...)

             (let ([name (λ args (apply (name name) args))])

               expr))))]))

((recursion fact (n)

            (if (zero? n)

                1

                (* n (fact (sub1 n)))))

 5)

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

--
Jens Axel Søgaard

[Sam Caldwell]

I think the simplest solution to your problem would be to use the *full* (for strict languages, I don't quite remember the name) Y-combinator rather than just self-application, which is what you have right now. Then you can just ditch `substitute-term` completely:

--------------------------

(define Y

  (lambda (f)

    ((lambda (g) (g g))

     (lambda (x) (f (lambda (y) ((x x) y)))))))

(define-syntax recursion

  (syntax-rules ()

    [(_ label (args ...) body ...)

     (Y

      (lambda (label)

        (lambda (args ...)

          body ...)))]))

--------------------------

> (define fact

    (recursion fact (n)

            (if (zero? n)

                1

                (* n (fact (sub1 n))))))
> (fact 0)

1

> (fact 10)

3628800

- Sam Caldwell

[Vasily Rybakov]

Hi, gustavo!

Thanks for your answer, it was very helpful.

So i rewrote my (substitute-term) macro like this:

(define-syntax (substitute-term stx)
(syntax-case stx ()

[(_ term-from term-to (body0 body ...))
#`#,(append (if (equal? (syntax-e #'body0) (syntax-e #'term-from))
(list #'term-to)
(list #'body0))
#'((substitute-term term-from term-to body) ...))]
[(_ term-from term-to body)

(if (equal? (syntax-e #'body)
(syntax-e #'term-from))
#'term-to

#'body)]))

The (syntax-e) parts is kept because (equal? #'body #'term-from) won't yield #t.

Now it works:

>(substitute-term and or (and #t #f))

#t

After a little bit tinkering I returned to (case) form, so it can substitute not only single terms, but whole expressions:

(define-syntax (substitute-syntax stx)

(syntax-case stx ()
[(_ term-from term-to body)
(cond

[(equal? (syntax->datum #'body) (syntax->datum #'term-from)) #'term-to]
[(list? (syntax->datum #'body)) #`#,(append (if (equal? (syntax->datum (car (syntax-e #'body)))
(syntax->datum #'term-from))
(list #'term-to)
(list #`#,(car (syntax-e #'body))))
(map (lambda (x)
(append (syntax-e #'(substitute-syntax term-from term-to))
(list x)))
(cdr (syntax-e #'body))))]
[else #'body])]))

>(substitute-syntax (and #t #f) or ((and #t #f) #f #t))
Expands into (or #t #f)
#t

And my final version of recursion looks like this:
(define-syntax recursion
(syntax-rules ()
[(_ (args ...) body ...)
((lambda (x) (x x))
(lambda (generated-label)
(lambda (args ...)
(substitute-syntax recursion (generated-label generated-label) body) ...)))]

[(_ label (args ...) body ...)
((lambda (x) (x x))
(lambda (label)
(lambda (args ...)

(substitute-syntax label (label label) body) ...)))]))

So it can be used without label, if there are no nested recursions:
>((recursion (n)
(if (zero? n)
1
(* n (recursion (sub1 n))))) 5)
5

Now it works, as intended.

[Vasily Rybakov]

Also thanks to Jens and Sam -- your examples is valuable, I learned from them (for example, how I can use (let) to bind variable that was defined before -- so it keeps previous binding in the definitions part of (let) but uses new binding in the body part of (let)).

[Jens Axel Søgaard]

Hi Vasily,

For completeness sake, note that you can use let-syntax and

make the macro expander do the work of substitute-syntax.

(require (for-syntax syntax/parse))

(define-syntax (recursion stx)

  (syntax-parse stx

    [(_recursion name (arg ...) expr)

     #'( (λ (x) (x x))

         (λ (name)

           (λ (arg ...)

             (let-syntax ([name (λ (stx)

                                  (syntax-parse stx

                                    [(_name . more) #'((name name) . more)]

                                    [other          #'other]))])

               expr))))]))

2016-09-11 17:33 GMT+02:00 Vasily Rybakov <madba...@gmail.com>:

Also thanks to Jens and Sam -- your examples is valuable, I learned from them (for example, how I can use (let) to bind variable that was defined before -- so it keeps previous binding in the definitions part of (let) but uses new binding in the body part of (let)).

--
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gustavo Massaccesi]

Just a comment about how to compare identifiers. In some cases, using
equal? and syntax-e gives the wrong result. It's better to use
free-identifier=? . For example, in this program we can use three
methods to compare identifiers (there are more!).

The program has two macros:

clasify-id: shows the result of three methods to compare identifiers.

show: it creates an unuseful temporal variable, and shows the value of
the "argument" and the value of the unuseful variable.

The problem is that that temporal variable is called temp, so it can
confuse the comparison methods because it has the same name that one
of the module level variables. But if free-identifier=? does a more
thoughtful comparison.

;---
#lang racket

(define-syntax (clasify-id stx)
(syntax-case stx ()
[(_ x y)
(begin
(displayln
(list (equal? #'x #'y)
(equal? (syntax-e #'x) (syntax-e #'y))
(free-identifier=? #'x #'y)))
#'(void))]))

(define-syntax (showln stx)
(syntax-case stx ()
[(_ var)
#'(let ([temp (random)])
(displayln (list temp var))
(clasify-id temp var))]))

(define x 5)
(define temp 5)

(clasify-id x temp) ;==> (#f #f #f)
(clasify-id x x) ;==> (#F #t #t) <-- the first is wrong
(showln x) ;==> (#f #f #f)
(showln temp) ;==> (#f #T #f) <-- the seccond is wrong
;---

Gustavo

[Jos Koot]

When using a macro, always think: "can I do the same without a macro?"
You use the simple auto-applicator (lambda (x) (x x)).
I suggest to use an applicative-order Y-combinator, such as:
(define Y (λ (m) ((λ (f) (f f)) (λ (g) (m (λ (n) ((g g) n)))))))
Now: ((Y (lambda (!) (lambda (n) (if (zero? n) 1 (* n (! (sub1 n))))))) 4) -> 24
There are many more ways to write an applicative-order Y-combinator.
Now is the moment to think about a sugaring macro:

#lang racket
; Let Y work for functions of more than one argument:
(define Y (λ (m) ((λ (f) (f f)) (λ (g) (m (λ args (apply (g g) args)))))))
((Y (lambda (!) (lambda (n) (if (zero? n) 1 (* n (! (sub1 n))))))) 4)
; The sugar:
(define-syntax-rule
 (recursive-lambda (name arg ...) body ...)
 (Y (lambda (name) (lambda (arg ...) body ...))))
((recursive-lambda (! n) (if (zero? n) 1 (* n (! (sub1 n))))) 4)
; Or in tail recursive style
; (I am not sure it is realy tail recursive under Y,
;  but using debug I don't see a growing stack)
((recursive-lambda (! n m) (if (zero? n) m (! (sub1 n) (* n m)))) 4 1)

Jos

--

You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

[Jos Koot]

After you have figured how to make recursive-lambda,

you may want to figure out how to produce two mutually recursive functions.

If, or rather I think 'when', you have more questions, don't hesitate to consult this list,

for I am sure the PLT team and many others agree with this advice.

Jos

---

From: Jos Koot [mailto:jos....@gmail.com]
Sent: lunes, 12 de septiembre de 2016 4:07
To: 'Vasily Rybakov'; 'Racket Users'
Cc: 'Jos Koot'
Subject: RE: [racket-users] Trouble with recursive lambda macros, using Y combinator