Tail recursive, algebraic definition of a simple cons list in Python, along with some example functions.

lisp.py

def tail_rec(fun):
    '''
    Receive a function `fun` as an argument;
    Return a function which accepts `fun` and runs it in a loop.
    '''
    def tail(fun):
       a = fun
       while callable(a):
          a = a()
       return a
    return (lambda x: tail(fun(fun,*x)))

def Nil():
    def inner(x, y):
        return x()
    return inner

def Cons(h, t):
    def inner(x, y):
        return y(h, t)
    return inner

@tail_rec
def lst_len(f,*args):
    xs = args[0]
    return xs(lambda: 0, lambda h, t: 1 + f(f,t))

@tail_rec
def lst_show(f,*args):
    xs = args[0]
    return xs(lambda: "Nil ", lambda h, t: str(h) + " " + f(f,t))

if __name__=="__main__":
    my_list = Cons(1,
              Cons(2,
              Cons(3,
              Nil())))
    print "List: %s" % (lst_show([my_list]),)
    print "Length: %d" % (lst_len([my_list]),)