Subject: Lambda Calculus Program to add two bit vectors

From: Shlomi Fish <[email-masked]>
Date: Thu, 10 Jan 2002 22:34:08 +0200 (IST)

You can find it here:

http://vipe.technion.ac.il/~shlomif/lambda-calculus/

In it, integers are converted to bit vectors, and the bit vectors are
added, and then converted back to integers. A few words about the
implementation:

1. The bits are represented as LC's true and false expressions.

2. The bit vector is implemented as a pair tree. I.e: the root has two
branches, and each one has two others, etc. until the bits. The number of
bits is a whole power of 2.

3. The addition is done by adding the cars of each tree, and using the
carry bit to add the cdrs, which contain the more upper bits. This is done
recursively, until a full-adder is used to add two bits and a carry bit.

The code at the moment, is very raw, scarcely documented and not
optimized. But it works.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"