## Lambda Calculus Example Composite and Prime Numbers

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

FP
Lambda
Introduction
Examples

Each composite number is the product of at least two prime numbers, and the prime numbers are {2, 3, 4, ...} with the composite numbers removed:

 ``` let rec merge = lambda a. lambda b. {assume a and b infinite and disjoint} let a1=hd a, b1=hd b in if a1 < b1 then a1::(merge (tl a) b) else {a1 > b1} b1::(merge a (tl b)), mult = lambda a. lambda b. (a * hd b)::(mult a tl b), remove = lambda a. lambda b. { a-b, treat lists as sets. PRE: a & b ascending } if hd a < hd b then (hd a)::(remove tl a b) else if hd a > hd b then remove a tl b else remove tl a tl b, from = lambda n. n::(from (n+1)), { n::(n+1)::(n+2):: ... } products = lambda l. { PRE: l ascending } let rec p = (hd l * hd l) :: { & elts coprime } (merge (mult hd l (merge tl l p)) (products tl l)) in p in let rec composites = products primes, primes = 2 :: (remove (from 3) composites) { ! } in primes {\fB Composites and Primes. \fP} ```

See: L. Allison, Circular Programs and Self-Referential Structures, Software Practice and Experience 19(2) pp99-109 Feb 1989.

 let rec merge = lambda a. lambda b. {assume a and b infinite and disjoint} let a1=hd a, b1=hd b in if a1 < b1 then a1::(merge (tl a) b) else {a1 > b1} b1::(merge a (tl b)), mult = lambda a. lambda b. (a * hd b)::(mult a tl b), remove = lambda a. lambda b. { a-b, treat lists as sets. PRE: a & b ascending } if hd a < hd b then (hd a)::(remove tl a b) else if hd a > hd b then remove a tl b else remove tl a tl b, from = lambda n. n::(from (n+1)), { n::(n+1)::(n+2):: ... } products = lambda l. { PRE: l ascending } let rec p = (hd l * hd l) :: { & elts coprime } (merge (mult hd l (merge tl l p)) (products tl l)) in p in let rec composites = products primes, primes = 2 :: (remove (from 3) composites) { ! } in primes {\fB Composites and Primes. \fP}
 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 Monday, 25-Oct-2021 12:43:42 AEDT.