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.k...@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



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 

-----Original Message----- 
From: racket-users@googlegroups.com [ <mailto:racket-users@googlegroups.com> 
mailto:racket-users@googlegroups.com] On Behalf Of
Vasily Rybakov 
Sent: domingo, 11 de septiembre de 2016 5:54 
To: Racket Users 
Subject: [racket-users] Trouble with recursive lambda macros, using Y 
combinator 

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!

-- 
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+unsubscr...@googlegroups.com.

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

-- 
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply via email to