[racket] First and rest in lambda-calculus

From: Kazimir Majorinc (kazimir at chem.pmf.hr)
Date: Sun Feb 13 03:00:29 EST 2011

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

Posted on the users mailing list.