1
$\begingroup$

This question has been handled various ways, but let me show my case.

I want to find out, if the given list is empty with these constraints:

TRUE = (L a b . a)
FALSE = (L a b . b)
NIL = FALSE    
ZERO = FALSE
ONE = (L x y . (x y))
TWO = (L x y . (x (x y)))

PAIR = (L a b s . (s a b))

EMPTY = (PAIR NIL NIL)
EMPTY? = (L l . (l FALSE TRUE))

a. (EMPTY? EMPTY) should give TRUE.

b. (EMPTY? (PAIR ZERO (PAIR ONE (PAIR TWO EMPTY)))) should give FALSE.

I've seen different versions for EMPTY? like (L l . (l (L _ , FALSE) TRUE)) and such, but none of them gives me correct resolution.

So I'd like to know, if there is something on the above definitions, that does not work. Also, to verify that one strategy works, I'd like to see reduction steps for finding out correct answers for a. and b. starting from these expanded forms:

a. (L l . (l (L a b . b) (L a b . a)) (L a b s . (s a b) (L a b . b) (L a b . b)))

b. (L l . (l (L a b . b) (L a b . a)) (L a b s . (s a b) (L a b . b) (L a b s . (s a b) (L x y . (x y)) (L a b s . (s a b) (L x y . (x (x y))) (L a b s . (s a b) (L a b . b) (L a b . b))))))

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.