Defining a stack data structure and its main operations in lambda calculus

Question

I'm trying to define a stack data structure in lambda calculus, using fixed point combinators. I am trying to define two operations, insertion and removal of elements, so, push and pop, but the only one I've been able to define, the insertion, is not working properly. The removal I could not figure out how to define.

This is my approach on the push operation, and my definition of a stack:

Stack definition:
STACK = \y.\x.(x y)
PUSH = \s.\e.(s e)

My stacks are initialize with an element to indicate the bottom; I'm using a 0 here:

stack = STACK 0 = \y.\x.(x y) 0 = \x.(x 0)       // Initialization
stack = PUSH stack 1 = \s.\e.(s e) stack 1 =     // Insertion
    = \e.(stack e) 1 = stack 1 = \x.(x 0) 1 =
    = (1 0)

But now, when I try to insert another element, it does not work, as my initial structure has be deconstructed.

How do I fix the STACK definition or the PUSH definition, and how do I define the POP operation? I guess I'll have to apply a combinator, to allow recursion, but I couldn't figure out how to do it.

Reference: http://en.wikipedia.org/wiki/Combinatory_logic

Any further explanation or example on the definition of a data structure in lambda calculus will be greatly appreciated.

Answer 1

A stack in the lambda calculus is just a singly linked list. And a singly linked list comes in two forms:

nil  = λz. λf. z
cons = λh. λt. λz. λf. f h (t z f)

This is Church encoding, with a list represented as its catamorphism. Importantly, you do not need a fixed point combinator at all. In this view, a stack (or a list) is a function taking one argument for the nil case and one argument for the cons case. For example, the list [a,b,c] is represented like this:

cons a (cons b (cons c nil))

The empty stack nil is equivalent to the K combinator of the SKI calculus. The cons constructor is your push operation. Given a head element h and another stack t for the tail, the result is a new stack with the element h at the front.

The pop operation simply takes the list apart into its head and tail. You can do this with a pair of functions:

head = λs. λe. s e (λh. λr. h)
tail = λs. λe. s e (λh. λr. r nil cons)

Where e is something that handles the empty stack, since popping the empty stack is undefined. These can be easily turned into one function that returns the pair of head and tail:

pop = λs. λe. s e (λh. λr. λf. f h (r nil cons))

Again, the pair is Church encoded. A pair is just a higher-order function. The pair (a, b) is represented as the higher order function λf. f a b. It's just a function that, given another function f, applies f to both a and b.

Answer 2

By defining a combinator, which:

is defined as a lambda term with no free variables, so by definition any combinator is already a lambda term,

you can define, for example, a list structure, by writing:

Y = (list definition in lambda calculus)
Y LIST = (list definition in lambda calculus) LIST
Y LIST = (element insertion definition in lambda calculus)

Intuitively, and using a fixed point combinator, a possible definition is -- consider \ = lambda:

• a list is either empty, followed by a trailing element, say 0;
• or a list is formed by an element x, that may be another list inside the former one.

Since it's been defined with a combinator -- fixed point combinator --, there's no need to perform further applications, the following abstraction is a lambda term itself.

Y = \f.\y.\x.f (x y)

Now, naming it a LIST:

Y LIST = (*\f*.\y.\x.*f* (x y)) *LIST* -- applying function name
LIST = \y.\x.LIST (x y), and adding the trailing element "0"
LIST = (\y.\x.LIST (x y) ) 0
LIST = (*\y*.\x.LIST (x *y*) ) *0*
LIST = \x.LIST (x 0), which defines the element insertion abstraction.

The fixed point combinator Y, or simply combinator, allows you to consider the definition of LIST already a valid member, with no free variables, so, with no need for reductions.

Then, you can append/insert elements, say 1 and 2, by doing:

LIST = (\x.LIST (x 0)) 1 2 =
    = (*\x*.LIST (*x* 0)) *1* 2 =
    = (LIST (1 0)) 2 =

But here, we know the definition of list, so we expand it:

    = (LIST (1 0)) 2 =
    = ((\y.\x.LIST (x y)) (1 0)) 2 =
    = ((*\y*.\x.LIST (x *y*)) *(1 0)*) 2 =
    = ( \x.LIST (x (1 0)) ) 2 =

Now, inserting elemenet 2:

    = ( \x.LIST (x (1 0)) ) 2 =
    = ( *\x*.LIST (*x* (1 0)) ) *2* =
    = LIST (2 (1 0))

Which can both be expanded, in case of a new insertion, or simply left as is, due to the fact that LIST is a lambda term, defined with a combinator.

Expanding for future insertions:

    = LIST (2 (1 0)) =
    = (\y.\x.LIST (x y)) (2 (1 0)) =
    = (*\y*.\x.LIST (x *y*)) *(2 (1 0))* =
    = \x.LIST (x (2 (1 0))) =
    = ( \x.LIST (x (2 (1 0))) ) (new elements...)

I'm really glad I've been able to derive this myself, but I'm quite sure there must be some good bunch of extra conditions, when defining a stack, a heap, or some fancier structure.

Trying to derive the abstraction for a stack insertion/removal -- without all the step-by-step:

Y = \f.\y.\x.f (x y)
Y STACK 0 = \x.STACK (x 0)
STACK = \x.STACK (x 0)

To perform the operation upon it, let's name an empty stack -- allocating a variable (:

stack = \x.STACK (x 0)

// Insertion -- PUSH STACK VALUE -> STACK
PUSH = \s.\v.(s v)
stack = PUSH stack 1 =
    = ( \s.\v.(s v) ) stack 1 =
    = ( \v.(stack v) ) 1 =
    = ( stack 1 ) = we already know the steps from here, which will give us:
    = \x.STACK (x (1 0))

stack = PUSH stack 2 =
    = ( \s.\v.(s v) ) stack 2 =
    = ( stack 2 ) =
    = \x.STACK x (2 (1 0))

stack = PUSH stack 3 =
    = ( \s.\v.(s v) ) stack 3 =
    = ( stack 3 ) =
    = \x.STACK x (3 (2 (1 0)))

And we, once again, name this result, for us to pop the elements:

stack = \x.STACK x (3 (2 (1 0)))

// Removal -- POP STACK -> STACK
POP = \s.(\y.s (y (\t.\b.b)))
stack = POP stack =
    = ( \s.(\y.s y (\t.\b.b)) ) stack =
    = \y.(stack (y (\t.\b.b))) = but we know the exact expansion of "stack", so:
    = \y.((\x.STACK x (3 (2 (1 0))) ) (y (\t.\b.b))) =
    = \y.STACK y (\t.\b.b) (3 (2 (1 0))) = no problem if we rename y to x (:
    = \x.STACK x (\t.\b.b) (3 (2 (1 0))) =
    = \x.STACK x (\t.\b.b) (3 (2 (1 0))) = someone guide me here, if i'm wrong
    = \x.STACK x (\b.b) (2 (1 0)) =
    = \x.STACK x (2) (1 0) =
    = \x.STACK x (2 (1 0))

For what, hopefully, we have the element 3 popped.

I've tried to derive this myself, so, if there's any restriction from lambda calculus I didn't followed, please, point it out.