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.