lazy function calling?

[Robin Becker]

In article <380202B7.ADF0E803 at GermanLloyd.org>, Berthold Hoellmann <hoel at GermanLloyd.org> writes
>Hello,
>
>I think I can remember a Python extension module, posted or announced
>here a while ago, where it was possible to make functions callable lazy.
>This means I could call a function spam just writing spam instead of
>spam(). Was I just dreaming or is it real. And if it's real, where can I
>get it :-)?
>
>Thanks
>
>Berthold
From: Joe Bowbeer <joeb at go2net.com> displayed some stuff based on lazy streams I think his
python implementation of

Structure and Interpretation of Computer Programs
Abelson and Sussman
http://mitpress.mit.edu/sicp/

I saved this with some hacks to memoized things

#From: Joe Bowbeer <joeb at go2net.com>
#Fya.
#I was doing a little investigating with Python's lambda expressions and
#it looks like they are indeed powerful enough to create some of my
#favorite beasts: infinitely long streams [*].

#If we define a stream to be a 'pair' of the form (head, tail), where
#head is the first element and tail is a function that returns the rest
#of the stream (which is itself a stream), then we can define 'head' and
#'tail' functions in Python as follows:

def head(s): # return first element in stream
        return s and s[0]

def tail(s): # return remainder of stream
        return s and s[1] and s[1]()

#We create a new stream given a head element and a tail stream as
#follows:

s = (head, lambda : tail)

# I'd use a 'special form' or macro above if Python had them..

#Here are two more functions that operate on streams. (I'd implement
#these tail-recursively if it were more efficient.)

def nthStream(s, n): # return nth element of stream s
        while n > 0:
                s, n = tail(s), n-1
        return head(s)

def printStream(s, n): # print first n elements of stream s
        while n > 0:
                print head(s),
                s, n = tail(s), n-1
        print

def mapStream(f,s):
        return (apply(f,[head(s)]), lambda f=f, s=s: mapStream(f,tail(s)))

#Now things start to get interesting:

# print 10 from an infinite stream of ones
ones = (1, lambda : ones)
printStream(ones, 10)

def addStreams(si, sj): # add corres. elements of two streams
        if not si: return sj
        if not sj: return si
        tailsum = lambda ti=si, tj=sj : addStreams(tail(ti), tail(tj))
        return (head(si) + head(sj), tailsum)

# infinitely many integers
integers = (0, lambda : addStreams(ones, integers))
printStream(integers, 10)

# infinite stream of Fibonacci numbers
fibs = (0, lambda : (1, lambda : addStreams(tail(fibs), fibs)))
printStream(fibs, 10)

# Too bad 'int' can only represent a finite number of digits...

#Better performance can be achieved by memo-izing the functions that
#evaluate the tails. A simple Memo class can be defined as follows. It
#lazily evaluates the 'thunk' function and then memorizes the result:

class Memo: # memoized call-by-need thunk
        def __init__(self, thunk):
                self.result, self.thunk = None, thunk
        def eval(self):
                if self.thunk:
                        self.result, self.thunk = self.thunk(), None
                return self.result

#Memo-ized streams are created as follows:
s = (head, Memo(lambda : tail))

#And the tail function becomes:
def tail(s): # return remainder of stream
        return s and s[1] and s[1].eval()

def addStreams(si, sj): # add corres. elements of two streams
        if not si: return sj
        if not sj: return si
        return (head(si) + head(sj), Memo(lambda ti=si, tj=sj : addStreams(tail(ti), tail(tj))))

ones = (1, Memo(lambda : ones))
printStream(ones, 10)

# infinitely many integers
integers = (0, Memo(lambda : addStreams(ones, integers)))
printStream(integers, 10)

# infinite stream of Fibonacci numbers
fibs = (0, Memo(lambda : (1, Memo(lambda : addStreams(tail(fibs), fibs)))))
printStream(fibs, 10)

#----
#*SICP:

#       Structure and Interpretation of Computer Programs
#       Abelson and Sussman
#       http://mitpress.mit.edu/sicp/

#----
#Joe Bowbeer

-- 
Robin Becker