ラムダがあれば何でもできる！元気ｄ（ｒｙ

ただ（型なし）ラムダ計算を用いて形式的に記述してゆくだけの遊びです。
言語はSchemeを選択しました。（途中までPythonを使っていたのは秘密）

(define true  (lambda (x y) x))
(define false (lambda (x y) y))
(define if_   (lambda (p x y) (p x y)))
;; マクロで遅延評価。（マクロは式の変換だから使ってもOK？）
(define-syntax if.
  (syntax-rules ()
    ((if. p x y)
     ((if_ p (lambda () x) (lambda () y))) )))

(define and. (lambda (p q) (if. p q false)))
(define or.  (lambda (p q) (if. p true q)))
(define not. (lambda (p) (if. p false true)))

;; 部分適用できないので、手動でカリー化
(define pair (lambda (x y)
               (lambda (f) (f x y)) ))
(define fst  (lambda (p) (p true)))
(define snd  (lambda (p) (p false)))

(define nil   (lambda (x) x))
(define null  fst)
(define cons. (lambda (x y) (pair false (pair x y))))
(define hd    (lambda (x) (fst (snd x))))
(define tl    (lambda (x) (snd (snd x))))

;; ただのIコンビネータ
(define I nil)

(define lisp
  (lambda (f lst end)
    (if. (null lst)
         end
         (cons. (f (hd lst)) (lisp f (tl lst) end)) )))

(define append. (lambda (x y) (lisp I x y)))
(define map.    (lambda (f lst) (lisp f lst nil)))

(define fold-left
  (lambda (f e lst)
    (if. (null lst)
         e
         (fold-left f (f e (hd lst)) (tl lst)) )))
         
;; ネストしたリストには対応してない
(define (print-list x)
  (if. (null x)
       (display "nil")
       (begin (display (hd x))
              (display " ")
              (print-list (tl x)) )))

;; 本当はチャーチ数を使うべきだけど割愛！
(define (list*2 x)
    (map. (lambda (x) (* 2 x)) x) )

(define (length. x)
    (fold-left + 0 (map. (lambda (_) 1) x)) )

;; tests
(define a (cons. 1 (cons. 2 nil)))
(define b (cons. 3 (cons. 4 nil)))
(define c (append. a b))
(define d (list*2 c))
(define e (length. c))

> (print-list c)

1 2 3 4 nil

> (print-list d)

2 4 6 8 nil

> e

4