Doug McIlroy sent me the following. I am not familiar enough with generators to provide an authoritative answer. Can someone who can post the answer and send a copy to Doug below? Thanks. Ed Feustel -----------------------------------------------------------------------------------------
I've been playing with using Python generators with feedback--a far cry from the elegance of Haskell.
I wondered how the stuff would look in Icon, but I couldn't puzzle out the answer from the sketchy on-line documentation. I'd have to read the book(!)
You probably know the answer. How would you attack the following problem in Icon?
(Essentially all there is to know about python generators is at http://www.python.org/ref/yield.html.)
Doug [EMAIL PROTECTED] ---------------------------------------------------
Python generators and fixed points.
Bowbeer gave a nice Python implementation of data streams in the functional style originated by Landin. (You can find Bowbeer by Googling comp.lang.java.)
Bowbeer eschewed generators, Python's natural stream construct, and not without cause: it's a pain to hook up a network of generators, unless the network is a tree. But it can be done.
Example. The Thue-Morse sequence is the fixed point of the pair of equations
(1) t = zipper(t,complement(t)) (2) t[0] = 0
(zipper(.) interleaves elements from its two inputs in alternation, and complement(.) exchanges 0 and 1. The Thue-Morse sequence is 0110100110010110...)
As it stands, (1) is useless for calculation, because it can't produce t[0] until it has seen t[0]. A small rewrite fixes the problem:
(3) t = [0}+zipper(complement(t), tail(t))
(3) works, because zipper can yield its first result, which becomes t[1], before accessing tail(t), which begins with t[1]. Since zipper produces two items for every one it reads, everything sails along thenceforth.
Here's the deal: thue1(t) below computes the right side of (3), and fix(.) feeds the output of thue1 back to the input to get the fixed point. To keep the code short, zipper and complement are coded in-line.
def thue(): # Thue-Morse generator
def thue1(b):
yield 0
v = b.t.next()
while 1: # zipper loop
yield 1 - v # complement
v = b.t.next() # tail
yield v
return fix(thue1)The dirty little secret of this code is that t, the stream of interest, has to be hidden in a box, b. The fix function passes an empty box to thue1, then reaches in and changes the box's content before the generator is used.
def fix(f):
class box:
t = None
b = box()
b.t = f(b)
b.t, t = split(b.t)
return tThe last detail is split(.), which creates a pair of generators. Each branch takes items from a common queue (linked list) of values from stream t. A new item is appended when a reader hits the queue's end.
def split(t):
class item:
suc = None
def branch(t,q):
while 1:
if q.suc==None:
q.v, q.suc = t.next(), item()
v, q = q.v, q.suc
yield v
q = item()
return (branch(a,q), branch(a,q))----------------------------------------------------
Exercise.
Compute the coefficients of the power series for
the exponential function. Use the fact that the
function satisfies the integral equation
exp = 1 + integral(exp)
and use this generator to integrate the power
series b.t term by term: def integral(b):
n = 0.0
yield 1.0
while 1:
n = n+1
yield b.t.next()/n----------------------------------------------------
Python could make plumbing easier.
The opacity of generator objects drove us to use the ugly boxing trick. Is the opacity justifiable? A generator, after all, can be written as a class object with a next() method. Python's special generator syntax simply lessens the tedium of implementing persistent state.
The arguments of a generator are known to be among its state variables. If they were accessible (as they would be in a hand-written generator class) stream plumbing of all sorts would be simplified.
-------------------------------------------------------
This SF.Net email sponsored by Black Hat Briefings & Training.
Attend Black Hat Briefings & Training, Las Vegas July 24-29 - digital self defense, top technical experts, no vendor pitches, unmatched networking opportunities. Visit www.blackhat.com
_______________________________________________
Unicon-group mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/unicon-group
