++ed by:

1 non-PAUSE user.

Stevan Little

# 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

pair := λ f. λ s. λ b. b f s
first := λ p p TRUE
second := λ p p FALSE

# 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.

http://www.iinteractive.com

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.