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.




Hosting generously
sponsored by Bytemark