fp::lambda - lambda calculus in Perl

  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)

This module implements lambda calculus using plain Perl subroutines as lambda abstractions.

TRUE := &955; x. &955; y. x

FALSE := &955; x. &955; y. x

AND := &955; p. &955; q. p q FALSE

OR := &955; p. &955; q. p TRUE q

NOT := &955; p. p FALSE TRUE

cond := &955; p. &955; x. &955; y. p x y

zero := &955; f. &955; x. x

one := &955; f. &955; x. f x

two := &955; f. &955; x. f (f x)

three := &955; f. &955; x. f (f (f x))

four := &955; f. &955; x. f (f (f (f x)))

five := &955; f. &955; x. f (f (f (f (f x))))

six := &955; f. &955; x. f (f (f (f (f (f x)))))

seven := &955; f. &955; x. f (f (f (f (f (f (f x))))))

eight := &955; f. &955; x. f (f (f (f (f (f (f (f x)))))))

nine := &955; f. &955; x. f (f (f (f (f (f (f (f (f x))))))))

ten := &955; f. &955; x. f (f (f (f (f (f (f (f (f (f x)))))))))

succ := &955; n. &955; f. &955; x. f (n f x)

pred := &955; m. first (m (&955; p. pair (second p) (plus one (second p))) (pair zero zero))

is_zero := &955; n. n (&955; x. FALSE) TRUE

is_equal := &955; m. &955; n. AND (is_zero (m pred n)) (is_zero (n pred m))

plus := &955; m. &955; n. &955; f. &955; x. m f (n f x)

subtract := &955; m. &955; n. n pred m

multiply := &955; m. &955; n. m (plus n) zero

NIL := pair TRUE TRUE

is_NIL := first

is_not_NIL := &955; x. NOT is_NIL

cons := &955; h. &955; t. pair FALSE (pair h t)

head := &955; z. first (second z)

tail := &955; z. second (second z)

size := &955; l. cond (is_not_NIL l) (&955; x. succ (size (tail l))) (&955; l. zero)

sum := &955; l. cond (is_not_NIL l) (&955; x. plus (head l) (sum (tail l))) (&955; l. zero)

append := &955; l1. &955; l2. cond (is_NIL l1) (l2) (cons (head l1) (append (tail l1) l2))

rev := &955; l. cond (is_not_NIL) (NIL) (append rev(tail l) cons((head l) NIL))

nth := &955; n. &955; l. cond (is_NIL l) (NIL) (cond (is_equal n zero) (head l) (nth (pred n)) (tail l)) )

apply := &955; f. &955; l. cond (is_NIL l) (NIL) (cons (f (head l)) (apply f (tail l)))

pair := &955; f. &955; s. &955; b. b f s

first := &955; p p TRUE

second := &955; p p FALSE

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.

See the CODE COVERAGE section of fp for this information.

Types and Programming Languages

http://en.wikipedia.org/wiki/Lambda_calculus

http://www.csse.monash.edu.au/~lloyd/tildeFP/Lambda/

stevan little, <stevan@iinteractive.com>

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.