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: [email protected] > [mailto:[email protected]] On Behalf Of Jos Koot > Sent: 13 February 2011 09:46 > To: 'Kazimir Majorinc'; [email protected] > 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: [email protected] > > [mailto:[email protected]] On Behalf Of Kazimir Majorinc > > Sent: 13 February 2011 09:00 > > To: [email protected] > > 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 _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
