Lambda Calculus Boolean

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

FP
 Lambda
  Introduction
  Examples
   Bool
   Ints
   Lists
  others

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

let
  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) ::
  nil

{\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

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

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

© L. Allison   http://www.allisons.org/ll/   (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, 28-Mar-2024 20:05:16 AEDT.