[racket] First and rest in lambda-calculus

From: Jos Koot (jos.koot at telefonica.net)
Date: Sun Feb 13 03:45:37 EST 2011

You can make pairs.

#lang racket
(define true (lambda (x) (lambda (y) x)))
(define false (lambda (x) (lambda (y) y)))
(define cons (lambda (x) (lambda (y) (lambda (z) ((z x) y)))))
(define first (lambda (x) (x true)))
(define rest (lambda (x) (x false))) 
(first ((cons 1) 2))
(rest ((cons 1) 2))


> -----Original Message-----
> From: users-bounces at racket-lang.org 
> [mailto:users-bounces at racket-lang.org] On Behalf Of Kazimir Majorinc
> Sent: 13 February 2011 09:00
> To: users at racket-lang.org
> Subject: [racket] First and rest in lambda-calculus
> Is it possible to define these two in lambda calculus? I believe it is
> not. For example, for every lambda-expression FIRST
> (FIRST ((^x.x) a)) => (FIRST a)
> (^x.x) cannot be reconstructed, and by Church-Rosser, it cannot by any
> other order of reductions. Is it right? Is it important difference
> between Lisp and lambda-calculus? Is there a publication that
> discussed that issue?
> Kazimir Majorinc
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users

Posted on the users mailing list.