`or` function in Scheme misbehaving

问题:

I am trying to write an or function in Scheme

(define or
  (lambda (p q) p p q))

If I do (or #t #f) I get #f.

What is the problem in what I am doing?

I saw λpq.ppq in a video on youTube.

回答1:

The correct Lambda Calculus definitions are

(define or (lambda (p q) (p p q)))        ; (or p q) = {p AND p} OR {{NOT p} AND q}

(define xor (lambda (p q) (p (not q) q))) ; (xor p q) = {p AND {NOT q}} OR {{NOT p} AND q}

(define not (lambda (t) (lambda (p q) (t q p))))   ; ((not t) p q) = (t q p)

(note the parens!). But #t and #f won't work with these. They expect

(define true (lambda (p q) p))    ; (true p q) = p

(define false (lambda (p q) q))   ; (false p q) = q

You can check it with

((or true false) #t #f)  ; #t

((xor false false) #t #f) ; #f

((xor true false) #t #f)  ; #t

---

With your definition there's a set of parentheses missing:

(define or (lambda (p q)  p p q  ))
           ;            ^^     ^^

It reduces as:

(or #t #f)
=
(let ([p #t] [q #f])
   p
   p
   q )
=
(let ([p #t] [q #f])
   q )
=
#f

To cause an application of p to p and q we need to enclose the form in parentheses, like this: (p p q). Without them you just have three consecutive expressions, three variables, and only the last one's value is returned, as is, as the overall result. Which is the value of q. Which is #f.