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.
