04-08.rkt

#lang racket

;; Tuesday, April 8, 2025
;; CIS352

(define (λ-expr? e)
  (match e
    [(? symbol? x) #t]
    [`(lambda (,(? symbol? x)) ,(? λ-expr? e-b)) #t]
    [`(,(? λ-expr? e0) ,(? λ-expr? e1)) #t]
    [_ #f]))


(define (nat->church n)
  (define (helper n) (match n [0 'x] [_ `(f ,(helper (- n 1)))]))
  `(lambda (f) (lambda (x) ,(helper n))))

;; I have to output an S-expression that is the
;; encoded version of the input.
;;
;; Most important aspect to understand: in this project
;; I'm building a *compiler*, whose job is to output
;; something that satisfies λ-expr? 
(define/contract (encode e)
  (-> any/c λ-expr?)
  (pretty-print e)
  (match e
    [(? nonnegative-integer? n)
     ;; I want to return the λ-calculus encoding of this n
     (nat->church n)]
    [`(let ([,x ,e]) ,e-b)
     (encode `((lambda (,x) ,e-b) ,e))]
    [`(let () ,e-b) (encode e-b)]
    [`(let ([,xs ,es] ...) ,e-b) 'todo]
    [`(lambda (,x) ,e)
     `(lambda (,x) ,(encode e))]
    [`(lambda (,x ,y) ,e)
     `(lambda (,x) (lambda (,y) ,(encode e)))]
    [`(lambda (,x ,args ...) ,e) 'todo]
    [`(,f ,e)
     `(,(encode f) ,(encode e))]
    [`(,f ,e0 ,e1)
     (encode `((,f ,e0) ,e1))]
    [`(,f ,e-args ...)
     'todo]
    [(? symbol? x) x]
    #;(encode `(lambda (,x) (lambda (,y) ,e)))
    [_ (error "I don't know how to encode this")]))

(encode 2)
;'(λ (f) (λ (x) (f (f x))))

;; When I have a Church-encoded number, I can get
;; back an arabic numeral by just doing this
(define (church-num->racket e)
  ((e add1) 0))

;; testcases
(church-num->racket (eval (encode 2) (make-base-namespace)))

(church-num->racket (eval (encode 50) (make-base-namespace)))