Lambda Calculus Boolean

home1 home2
and the


Boolean values can be defined in the Lambda Calculus, although they are often "built into" programming languages based on Lambda Calculus.

  TRUE  = lambda a. lambda b. a,
  FALSE = lambda a. lambda b. b

in let
  AND   = lambda p. lambda q. p q FALSE,
  OR    = lambda p. lambda q. p TRUE q,
  NOT   = lambda p. lambda a. lambda b. p b a,
  IF    = lambda p. lambda a. lambda b. p a b,
  EQ    = lambda x. lambda y.
            if x = y then TRUE else FALSE

in {simple test:}
  IF TRUE                   1  (-1) ::
  IF FALSE                (-2)   2  ::
  IF (OR  FALSE TRUE)       3  (-3) ::
  IF (AND FALSE TRUE)     (-4)   4  ::
  IF (NOT FALSE)            5  (-5) ::
  IF (EQ 1 1)               6  (-6) ::
  IF (OR (EQ 1 2) (EQ 2 2)) 7  (-7) ::

{\fB Define Boolean From Scratch. \fP}

The example defines `TRUE', `FALSE', `AND', `OR', etc. from first principles but defines `EQ' using the built in `=' which is of course a cheat (to keep the example small). However, the section on integers shows how to define `ISZERO' which could be used to define `EQ' from first principles.

Also see [Ints] and [Lists].

Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

free op. sys.
free office suite
~ free photoshop
web browser

λ ...
:: list cons
nil the [ ] list
null  predicate
hd head (1st)
tl tail (rest)

© L. Allison   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 25-Jul-2024 11:09:19 AEST.