NAME
fp::lambda - lambda calculus in Perl
SYNOPSIS
use fp::lambda;
# add two Church numerals together
add(\&two)->(\&two);
# subtract them ...
subtract(\&two)->(\&two);
# check if a Church numeral is zero
is_zero(\&zero);
# build a list of one through five
my $one_through_five = cons(\&one)->(cons(\&two)->(cons(\&three)->(cons(\&four)->(cons(\&five)->(\&NIL)))));
# check it's size
is_equal(size($one_through_five))->(\&five);
# get the sum of the list
sum($one_through_five)); # returns 15 (as a Church numeral)DESCRIPTION
This module implements lambda calculus using plain Perl subroutines as lambda abstractions.
FUNCTIONS
Church Booleans
- TRUE := λ x. λ y. x
- FALSE := λ x. λ y. x
- AND := λ p. λ q. p q FALSE
- OR := λ p. λ q. p TRUE q
- NOT := λ p. p FALSE TRUE
- cond := λ p. λ x. λ y. p x y
Church Numerals
- zero := λ f. λ x. x
- one := λ f. λ x. f x
- two := λ f. λ x. f (f x)
- three := λ f. λ x. f (f (f x))
- four := λ f. λ x. f (f (f (f x)))
- five := λ f. λ x. f (f (f (f (f x))))
- six := λ f. λ x. f (f (f (f (f (f x)))))
- seven := λ f. λ x. f (f (f (f (f (f (f x))))))
- eight := λ f. λ x. f (f (f (f (f (f (f (f x)))))))
- nine := λ f. λ x. f (f (f (f (f (f (f (f (f x))))))))
- ten := λ f. λ x. f (f (f (f (f (f (f (f (f (f x)))))))))
- succ := λ n. λ f. λ x. f (n f x)
- pred := λ m. first (m (λ p. pair (second p) (plus one (second p))) (pair zero zero))
- is_zero := λ n. n (λ x. FALSE) TRUE
- is_equal := λ m. λ n. AND (is_zero (m pred n)) (is_zero (n pred m))
- plus := λ m. λ n. λ f. λ x. m f (n f x)
- subtract := λ m. λ n. n pred m
- multiply := λ m. λ n. m (plus n) zero
List Functions
- NIL := pair TRUE TRUE
- is_NIL := first
- is_not_NIL := λ x. NOT is_NIL
- cons := λ h. λ t. pair FALSE (pair h t)
- head := λ z. first (second z)
- tail := λ z. second (second z)
- size := λ l. cond (is_not_NIL l) (λ x. succ (size (tail l))) (λ l. zero)
- sum := λ l. cond (is_not_NIL l) (λ x. plus (head l) (sum (tail l))) (λ l. zero)
- append := λ l1. λ l2. cond (is_NIL l1) (l2) (cons (head l1) (append (tail l1) l2))
- rev := λ l. cond (is_not_NIL) (NIL) (append rev(tail l) cons((head l) NIL))
- nth := λ n. λ l. cond (is_NIL l) (NIL) (cond (is_equal n zero) (head l) (nth (pred n)) (tail l)) )
- apply := λ f. λ l. cond (is_NIL l) (NIL) (cons (f (head l)) (apply f (tail l)))
Pair Functions
BUGS
None that I am currently aware of. Of course, that does not mean that they do not exist, so if you find a bug, let me know, and I will be sure to fix it.
CODE COVERAGE
See the CODE COVERAGE section of fp for this information.
SEE ALSO
- Types and Programming Languages
- http://en.wikipedia.org/wiki/Lambda_calculus
- http://www.csse.monash.edu.au/~lloyd/tildeFP/Lambda/
AUTHOR
stevan little, <stevan@iinteractive.com>
COPYRIGHT AND LICENSE
Copyright 2005 by Infinity Interactive, Inc.
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.