[racket] First and rest in lambda-calculus

You can even make lists by wrapping each pair in another pair whose first is
true and whose rest is the list proper. For the empty list take a wrapping
pair with first false and rest irrelevant. Add the following to the code I
already sent. Have fun :)

Jos

(define kons (lambda (x) (lambda (y) ((cons true) ((cons x) y)))))
(define null? (lambda (x) (not (first x))))
(define not (lambda (x) ((x false) true)))
(define kar (lambda (x) (first (rest x))))
(define kdr (lambda (x) (rest (rest x))))
(define nil ((cons false) 'any))
(kar ((kons 1) 2))
(kdr ((kons 1) 2))
(((null? nil) 'yes) 'no)
(((null? ((kons 1) 2)) 'yes) 'no) 

> -----Original Message-----
> From: users-bounces at racket-lang.org 
> [mailto:users-bounces at racket-lang.org] On Behalf Of Jos Koot
> Sent: 13 February 2011 09:46
> To: 'Kazimir Majorinc'; users at racket-lang.org
> Subject: Re: [racket] First and rest in lambda-calculus
> 
> 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))
> 
> 
> 
> Jos
> 
> 
> 
> > -----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
> 
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users