A Different Kind of Uselessness

Small shots of lambda calculus, part III

2007-11-11T19:26:00.001-08:00

Last time, we talked about pairs and more complex arithmetic, and we previously discussed the basics of lambda calculus and simple arithmetic.

This time we’re going to talk about lists.

There are several different ways to define lists in lambda calculus. One way is as a more complicated pair. We use cons and nil to construct lists:

> cons h t f x = f h t
> nil      f x = x

And we use head and tail to get the first item and all but the first items, respectively:

> head_ x l = l (\h t -> h)
> head = head_ 0
> tail_ x l = l (\h t -> t)
> tail = tail_ nil

Here are a few examples of using them in our imaginary lambda calculus interpreter:

>>> cons 1 nil
cons 1 nil

>>> head (cons 1 nil)
1

>>> tail (cons 1 nil)
nil

>>> head nil
0

>>> tail nil
nil

This is all well and good, but it’s kind of boring. These lists are basically no different from pairs and, in order to do anything useful such as mappings and folds, we have to go jump through hoops of complexity.

Perhaps this is best, for otherwise we might’ve been content with this representation for lists and not have found the other viable representation, which I consider to be the most elegant.

An empty list is nil:

> nil f x = x

Note that nil is unchanged, and that nil has the same definition as 0.

To construct the list we use cons:

> cons h t f x = f h (t f x)

This is very similar to the succ function we defined in Part 1. To understand how it works, we should look at some sample lists. (Note our list shorthand: comma separated list of values encased in square brackets.)

>>> [] f x
x

>>> [1] f x
f 1 x

>>> [1,2] f x
f 1 (f 2 x)

>>> [1,2,3] f x
f 1 (f 2 (f 3 x))

Compare this to the way numbers are defined:

>>> 0 f x
x

>>> 1 f x
f x

>>> 2 f x
f (f x)

>>> 3 f x
f (f (f x))

It’s hard to argue that there’s a more natural way of expressing lists in lambda calculus.*

It’s easy to get the head value:

> head_ x l = l (\h v -> h) x
> head = head_ 0

>>> head []
0

>>> head [1]
1

>>> head [1,2]
1

But getting the tail is hard, like getting the predecessor of a number:

> tail_ x l = 1st (l (\h p -> pair (2nd p) (cons h (2nd p))) (pair x nil))
> tail = tail_ nil

>>> tail []
[]

>>> tail [1]
[]

>>> tail [1,2]
[2]

>>> tail [1,2,3]
[2,3]

Actually tail works just like pred, but instead of doing succ each iteration, it does cons h.

Some properties and predicates:

> length l = l (\h n -> succ n) 0
> nil?   l = l (\h b -> false) true
> sum    l = l add 0

>>> length []
0

>>> length [1,2,3,4]
4

>>> nil? []
true

>>> nil? [1,2,3,4]
false

>>> sum []
0

>>> sum [1,2,3,4]
10

We should also define map (which passes a function through all items of a list):

> map f l = l (\h v -> cons (f h) v) nil

>>> map (add 5) []
[]

>>> map (add 5) [3]
[8]

>>> map (\x -> mul x x) [1,2,3,4,5]
[1,4,9,16,25]

That’s it for today. Tell me what else you’d like to know about Lambda Calculus (in the comments on reddit).

Footnotes

* - By the way, this list representation corresponds to Haskell’s foldr.

Small Shots of Lambda Calculus, Part II

2007-09-20T15:22:00.000-07:00

Last time, we talked about simple arithmetic in lambda calculus. Let's expand on that.

We have a successor function, but we don't have a predecessor function. To define it we need a different abstraction though: the pair!

pair a b f = f a b
1st p = p true
2nd p = p false

[We're using Haskell-like syntax now. This means that (bla a = b) is the same as (bla = (\ a -> b)). Oh, and we're using \ at the beginning of lambda expressions, too.]

pair works because you usually only supply 2 arguments -- and when you want to use them, pass a function to them. You can also extract the 1st and 2nd elements using 1st and 2nd, which use true and false to select the correct element, respectively.

A few examples of using pair (in our imaginary lambda calculus interpreter):

> 1st (pair 42 13)
42
> 2nd (pair 42 13)
13
> pair 42 13 add
55
> pair 10 (pair 20 30) (\a b -> pair (pair a (1st b)) (2nd b))
pair (pair 10 20) 30

We can now use pair to create our predecessor function:

pred n = 1st (n (\p -> pair (2nd p) (suc (2nd p))) (pair 0 0))

This is complicated, so I'll go through this with you. You start with (pair 0 0), and apply (\p -> pair (2nd p) (suc (2nd p))), n times. What each of those applications does is, in effect, it transforms the pair (a, b) into the pair (b, b+1). So, by the time you've applied it n times to the pair (0, 0), you get the pair (n - 1, n). Then all you have to do is get the 1st element using 1st. That's it!

If you do (pred 0), it returns 0, but we can make an alternate version of pred that takes care of this:

pred_ x n = 1st (n (\p -> pair (2nd p) (succ (2nd p))) (pair x 0))

Another way to define pred now is:

pred = pred_ 0

We can now do subtraction:

sub a b = a pred b

sub_ x a b = a (pred_ x) b
sub = sub_ 0

For division we need a predicate. Predicates are functions that return either true or false:

not b = b false true
is0? n = n (\x -> false) true
ge? a b = is0? (sub b a)
lt? a b = not (ge? a b)

not inverts a boolean, is0? asks whether or not a number is 0, ge? asks if one number is greater than or equal to the other, and le? asks if a number is less than another. We can now do division and modulo (remainder):

div a b = lt? a b 0 (suc (div (sub a b) b))
mod a b = lt? a b a (mod (sub a b) b)

You learned about pairs, predecessors, predicates, and powerful arithmetic, today. Tomorrow: Lists! Can't wait! :)

Small Shots of Lambda Calculus, Part I

2007-09-19T00:08:00.000-07:00

Lambda calculus was invented by Alonzo Church.

Lambda calculus revolves around the application of anonymous functions -- lambda expressions.

[For the sake of clarity, I'll be using the syntax (a -> b) over (lambda a. b).]

It's best to explain by example.

(a -> b) x becomes b
(a -> a) x becomes x
(a b -> b a) x y becomes y x
(a b -> b a) (a -> b) (a -> a) becomes (a -> a) (a -> b) becomes (a -> b)

Everything is a function in this extremely minimal lambda calculus. I'll introduce you to some of the most important ones:

I = (x -> x)

I doesn't do much -- it just returns its argument.

true = (a b -> a)
false = (a b -> b)

true returns its first argument while false returns its second argument. They're the archetypal Boolean values of lambda calculus.

0 = (f x -> x)
1 = (f x -> f x)
2 = (f x -> f (f x))
3 = (f x -> f (f (f x)))
...

These are called the Church numerals, and they're used to apply a function to an argument a variable number of times. Note the similarity (in fact, equivalence) between 0 and false.

succ = (n f x -> f (n f x))

We can use succ to go from one Church numeral to the next. It is now trivial to do arithmetic on Church numerals.

add = (a b -> a succ b)
mul = (a b -> a (add b) 0)

G'night. Tomorrow: More lambda calculus.

So, is 0 zero?

2007-09-13T16:55:00.000-07:00

Is 0 zero?
Um, yes...

Is 0.0 zero?
Yes...

Is 0.00 zero?
Yes. I don't know where you're going with this, but it better be entertaining.

Hang on and it will be.
It better.

Is 0.000 zero?
Yes. Get on with it!

Okay. If I keep placing 0 at the end of the number, is it still zero?
Yes.

So 0.00000... is zero, then?
Assuming you're using only the digit 0, then yes.

Ah! What happens if we take that assumption away?
Then I don't know if the number is zero or not. You could have some digit other than 0 in there.

Yes. Let's play a game.
Okay. What are the rules?

I think of a digit after the decimal point. You can choose between asking me for the digit, or declaring whether or not the number is zero. If you ask for a digit, I get to think of another digit and the process starts again.
And if I declare whether or not the number is zero

I reveal my digit. If you're right, you win. Otherwise I do.
Heh. Seems like you can win every time.

Whatever, let's play. I've thought of my first digit.
Ask.

3, go.
That's easy! The number is not zero.

Right you are, my next digit was 3.
You let me win.

Yes. Let's play again. Go.
Ask.

0, go.
Ask.

0, go.
Ask.

0, go.
...we're not going anywhere are we? I guess the number is zero.

Bzzzzt! My next digit was 8.
You only say that because I guessed it was zero.

Right you are. Let's modify the rules a little bit. I have to write my digit down on this piece of paper, and show it to you every time you ask [etches something on the paper with a blunt pencil].
Ask.

[Reveals a "0.0", then etches some more onto the paper.] Go.
I guess the number is zero.

[Reveals "0.00".] You win!
That was easier. It seems to me like the only viable thing for you to do is to always write down a zero, or I might ask for it and reveal the obvious truth. I should always guess that it's a zero, at random times.

But what if I write a 1 just when you're about to guess?
You'd win, but there's a pretty slim chance of getting it right.

True.
On the other hand, if I keep asking, you might slip and give me something other than a 0.

But if I don't?
We'd be getting nowhere, and I'd be inclined to guess zero.

And so I'd be inclined to put something other than a 0 the longer it goes on, right?
Right... but that means I can just keep asking and I'll win...

Good, you completely grok the game.
It's weird and pointless. Can I go now?

Nope. So, what did you learn? How do the two games compare?
Well, I always lose on the first game, and I usually win on the second game.

But why?
Because you can't change your mind in the second game?

Exactly. Let's try a simple variation on the second game now.
Oh, not again...

I decide what the number is up-front and write it down, or an equation representing it. You can ask for digits, etc...
Okay.

[Pauses for a moment, then scribbles something down.] Go!
Ask.

1, go.
Not zero. Why did you let me win?

To prove a point. Let's play again. [Scribbles something else down.]
Ask.

0, go.
Ask.

0, go.
Ask.

0, go.
...we're at this again. I guess the number is zero.

[Reveals 0.0001]. Oops! I win! Maybe you could have played better?
You mean I just had to keep asking?

Apparently. Wanna try again? [Scribbles some more.] Go!
Ask.

0, go.
Ask.

0, go.
Ask.

0, go.
Ask.

0, go.
Ask.

0, go.
Oh, whatever... I'm guessing not zero.

[Smiles, and reveals a nice round 0.] Geez, I thought you'd have learnt not to trust me by now.
Hey, that hurts! So... how can I tell if it's a 0?

...you can't! That's my point. You can't tell if it's a zero just by asking digits.
So basically we can both win this game. I can win through perseverance, you can win through cunning. Should I go now?

Wait! We haven't even reflected on this.
It's getting dark outside...

Calm down, nothing bad is going to happen if you learn a little bit more.
Just get on with it.

Kids these days, so hasty... Anyway, you can't tell whether or not my number is a 0 just from looking at the digits individually. What if I tell you what all the digits are?
Sounds simple enough.

Oh really? Here: the nth digit is 0, for all n.
Well, that's obviously 0...

Okay. Try: the nth digit is the same as the n minus one -th digit.
Depends on the first digit. You aren't giving me all the information here.

Fair enough. Suppose I did give you all the information. Would you always be able to tell me whether or not the number is zero?
Of course! If I know every digit of the number, I know what the number is!

Really? I wanna see that. What about this: the nth digit is 0 if n converges to the 1-4-2-1 cycle of the Collatz conjecture, and otherwise is 1.
...oh, I don't know that!

...

...

... I haven't figured out a good way to end this yet.

Introducing... sectorForth!

2007-09-11T21:39:00.000-07:00

sectorForth is extreme, and I mean extreme. I believe it qualifies as esoteric too.

Each sectorForth program consists of up to 128 lines each with at most 5 words (a word being a sequence of characters delimited by whitespace). This means that even the most complicated sectorForth program is, at most, 640 words long.

If a line starts with a word (no whitespace preceding it), then it's a definition. Otherwise, it's a continuation and is only allowed to be 4 words long. I'll give you a little example:

fact    0? drop 1
        dup 1- fact *

That's a little factorial function. The word 0? checks to see if the top item (on the stack) is 0. If it is, it continues execution on that line. Otherwise it goes to the next line and executes that. In plain old forth, this means

: fact (n -- n!) recursive dup 0 = if drop 1 else dup 1- fact * then ;

Needless to say, I prefer sectorForth's way.

sectorForth has up to 128 predefined words. Among these you have:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 32 64 128 256 512 1024 4096 65536 -7 -6 -5 -4 -3 -2 -1
+ - * / 1- 1+ | & ^ >> << 8<<| neg
? 0? _? = != > < >= <= >? <?
dup swap over rot -rot drop { }
emit . open close in out :in :out
@ ! A B :A :B A@ A! B@ B! A@+ A!+ B@+ B!+ @@ !! A@@ A!! B@@ B!! A@@+ A!!+ B@@+ B!!+ word* new free
call cur+

Nifty, but... why?!

The point of sectorForth is to fit one program into 512 bytes (the size of a sector on most disks). This is done by restricting the number of words you can define (up to 128) and the length of each word (up to 4 calls per word). Since you can define 128 words, and you have 128 predefined words... you can have up to 256 distinct calls.

This means you only need one byte to represent a single call. Since a word is 4 calls, you need 32bits (an int by todays standards) for a word. And 128 * 4 = 512. :)

Actual practical uses? Very few. Maybe in an esoteric OS. Hmm...