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
On Sun, Sep 11, 2016 at 9:15 AM, Jens Axel Søgaard <[email protected]>
wrote:
> 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)
>
>
> 2016-09-11 5:54 GMT+02:00 Vasily Rybakov <[email protected]>:
>
>> 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 [email protected].
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> --
> Jens Axel Søgaard
>
> --
> 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 [email protected].
> For more options, visit 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 [email protected].
For more options, visit https://groups.google.com/d/optout.
