#lang racket
(define (churchify e)
;; Convert expressions in the input language to church-encoded expressions
(match e
[(letrec ([x val] ...) body)
(define expanded-bindings
(append (map (lambda (x-val) `(,x (lambda (v) (quasiquote (,x v))))))
(map churchify (list val ...))))
(quasiquote ((lambda ((unquote-splicing (map cdr expanded-bindings)))
(unquote (churchify body)))
(unquote-splicing (map car expanded-bindings))))]
[(let ([x val] ...) body)
(quasiquote ((lambda ((unquote x) ...)
(unquote (churchify body)))
(unquote-splicing (map churchify (list val ...)))))]
[(lambda (args ...) body)
(quasiquote (lambda ((unquote args) ...)
(unquote (churchify body))))]
[(e1 e2 ...)
(quasiquote (((unquote (churchify e1)))
(unquote (map churchify (list e2 ...)))))]
[(and exprs ...)
(quasiquote ((lambda (x)
(unquote (apply (lambda args
(quasiquote (if (unquote-splicing args) #t #f)))
(map churchify (list exprs ...)))))
#t))]
[(or exprs ...)
(quasiquote ((lambda (x)
(unquote (apply (lambda args
(quasiquote (if (unquote-splicing args) #t #f)))
(map churchify (list exprs ...)))))
#f))]
[(if cond then-expr else-expr)
(quasiquote ((lambda (x)
(unquote (if-then-else (churchify cond)
(churchify then-expr)
(churchify else-expr))))
#t))]
[(prim e1 e2)
(quasiquote ((lambda (x)
(unquote (apply (lookup-prim prim)
(map churchify (list e1 e2)))))
#t))]
[(prim e)
(quasiquote ((lambda (x)
(unquote (lookup-prim prim (churchify e))))
#t))]
[(quote ())
(quote ())]
[datum
datum]
[x
x]))
I have tried running that code but it brings out chuclify.rkt:6:5: match: syntax error in pattern in: (letrec ((x val) ...) body) #(130 27) which i dont understand how to solve
The error is indicating that the first pattern in the match form is invalid. When this happens, the way to solve it is to read match's documentation thoroughly to understand the pattern syntax it expects. The documentation on notational conventions is important too.
In this particular case, the first pattern can be corrected as follows.
(define (churchify e)
(match e
[`(letrec ([,x ,val] ...) ,body)
(printf "x: ~s~n" x)
(printf "val: ~s~n" val)
(printf "body: ~s~n" body)]))
> (churchify '(letrec ([a 1] [b 2]) (+ a b)))
x: (a b)
val: (1 2)
body: (+ a b)
The multiple values matched against x are collected in a list bound to x in the match option body. The same happens for val. Consequently, you will need to update other parts of your code as well. For example, (map churchify (list val ...)) should be (map churchify val).
One subtle property of this pattern is that it matches letrec literally, due to letrec appearing within the quasiquote (`) and not being unquoted (,) like x and val are. Without this property, the pattern would match expressions that it shouldn't match, such as the following.
(let ([a 1] [b 2]) (+ a b))
(foo ([a 1] [b 2]) (+ a b))
It might be a good idea to further require each x to be a symbol:
`(letrec ([,(? symbol? x) ,val] ...) ,body)