SICP "streams as signals" in Python -
i have found nice examples (here, here) of implementing sicp-like streams in python. still not sure how handle example integral found in sicp 3.5.3 "streams signals."
the scheme code found there is
(define (integral integrand initial-value dt) (define int (cons-stream initial-value (add-streams (scale-stream integrand dt) int))) int) what tricky 1 returned stream int defined in terms of (i.e., stream int used in definition of stream int).
i believe python have expressive , succinct... not sure how. question is, analogous stream-y construct in python? (what mean stream subject of 3.5 in sicp, briefly, construct (like python generator) returns successive elements of sequence of indefinite length, , can combined , processed operations such add-streams , scale-stream respect streams' lazy character.)
there 2 ways read question. first simply: how use stream constructs, perhaps ones second link, recursive definition? can done, though little clumsy in python.
in python can represent looped data structures not directly. can't write:
l = [l] but can write:
l = [none] l[0] = l similarly can't write:
def integral(integrand,initial_value,dt): int_rec = cons_stream(initial_value, add_streams(scale_stream(integrand,dt), int_rec)) return int_rec but can write:
def integral(integrand,initial_value,dt): placeholder = stream(initial_value,lambda : none) int_rec = cons_stream(initial_value, add_streams(scale_stream(integrand,dt), placeholder)) placeholder._compute_rest = lambda:int_rec return int_rec note need clumsily pre-compute first element of placeholder , fix recursion rest of stream. work (alongside appropriate definitions of rest of code - i'll stick @ bottom of answer).
however, second part of question seems asking how naturally in python. ask "analogous stream-y construct in python". answer generator. generator naturally provides lazy evaluation of stream concept. differs not being naturally expressed recursively python not support scheme, see.
in other words, strict stream concept can expressed in python (as in link , above) idiomatic way use generators.
it more or less possible replicate scheme example kind of direct mechanical transformation of stream generator (but avoiding built-in int):
def integral_rec(integrand,initial_value,dt): def int_rec(): x in cons_stream(initial_value, add_streams(scale_stream(integrand,dt),int_rec())): yield x x in int_rec(): yield x def cons_stream(a,b): yield x in b: yield x def add_streams(a,b): while true: yield next(a) + next(b) def scale_stream(a,b): x in a: yield x * b the tricky thing here realise need eagerly call recursive use of int_rec argument add_streams. calling doesn't start yielding values - creates generator ready yield them lazily when needed.
this works nicely small integrands, though it's not pythonic. scheme version works optimising tail recursion - python version exceed max stack depth if integrand long. not appropriate in python.
a direct , natural pythonic version this, think:
def integral(integrand,initial_value,dt): value = initial_value yield value x in integrand: value += dt * x yield value this works efficiently , correctly treats integrand lazily "stream". however, uses iteration rather recursion unpack integrand iterable, more python way.
in moving natural python have removed stream combination functions - example, replaced add_streams +=. still use them if wanted sort of halfway house version:
def accum(initial_value,a): value = initial_value yield value x in a: value += x yield value def integral_hybrid(integrand,initial_value,dt): x in accum(initial_value,scale_stream(integrand,dt)): yield x this hybrid version uses stream combinations scheme , avoids tail recursion. still pythonic , python includes various other nice ways work iterables in itertools module. "respect streams' lazy character" ask.
finally here code first recursive stream example, of taken berkeley reference:
class stream(object): """a lazily computed recursive list.""" def __init__(self, first, compute_rest, empty=false): self.first = first self._compute_rest = compute_rest self.empty = empty self._rest = none self._computed = false @property def rest(self): """return rest of stream, computing if necessary.""" assert not self.empty, 'empty streams have no rest.' if not self._computed: self._rest = self._compute_rest() self._computed = true return self._rest def __repr__(self): if self.empty: return '<empty stream>' return 'stream({0}, <compute_rest>)'.format(repr(self.first)) stream.empty = stream(none, none, true) def cons_stream(a,b): return stream(a,lambda : b) def add_streams(a,b): if a.empty or b.empty: return stream.empty def compute_rest(): return add_streams(a.rest,b.rest) return stream(a.first+b.first,compute_rest) def scale_stream(a,scale): if a.empty: return stream.empty def compute_rest(): return scale_stream(a.rest,scale) return stream(a.first*scale,compute_rest) def make_integer_stream(first=1): def compute_rest(): return make_integer_stream(first+1) return stream(first, compute_rest) def truncate_stream(s, k): if s.empty or k == 0: return stream.empty def compute_rest(): return truncate_stream(s.rest, k-1) return stream(s.first, compute_rest) def stream_to_list(s): r = [] while not s.empty: r.append(s.first) s = s.rest return r def integral(integrand,initial_value,dt): placeholder = stream(initial_value,lambda : none) int_rec = cons_stream(initial_value, add_streams(scale_stream(integrand,dt), placeholder)) placeholder._compute_rest = lambda:int_rec return int_rec = truncate_stream(make_integer_stream(),5) print(stream_to_list(integral(a,8,.5))) 
Comments
Post a Comment