def stream_tail(stream):
    return tail(stream)()
def stream_ref(s, n):
    return (head(s)
            if n == 0
            else stream_ref(stream_tail(s), n - 1))

def stream_map(f, s):
    return (None
            if is_none(s)
            else pair(f(head(s)),
                      lambda: stream_map(f, stream_tail(s))))

def stream_for_each(fun, s):
    if is_none(s):
        return True
    else:
        fun(head(s))
        return stream_for_each(fun, stream_tail(s))
def make_tableau(transform, s):
    return pair(s, lambda: make_tableau(transform, transform(s)))
def accelerated_sequence(transform, s):
    return stream_map(head, make_tableau(transform, s))
def square(x): return x * x
def memo(fun):
    already_run = False
    result = None
    def memoized():
        nonlocal already_run, result
        if not already_run:
            result = fun()
            already_run = True
            return result
        else:
            return result
    return memoized
def euler_transform(s):
    s0 = stream_ref(s, 0)     # $S_{n-1}$
    s1 = stream_ref(s, 1)     # $S_{n}$
    s2 = stream_ref(s, 2)     # $S_{n+1}$
    return pair(s2 - square(s2 - s1) / (s0 + (-2) * s1 + s2),
                memo(lambda: euler_transform(stream_tail(s))))
max_display = 9
def display_stream(s):
    def display_stream_iter(st, n):
        if is_none(st):
            pass
        elif n == 0:
            display("", "...")
        else:
            display(head(st))
            display_stream_iter(stream_tail(st), n - 1)
    display_stream_iter(s, max_display)
def scale_stream(stream, factor):
    return stream_map(lambda x: x * factor,
                      stream)
def stream_map_2(f, s1, s2):
    return (None
            if is_none(s1) and is_none(s2)
            else error("unexpected argument -- stream_map_2", None)
            if is_none(s1) or is_none(s2)
            else pair(f(head(s1), head(s2)),
                      memo(lambda: stream_map_2(f, stream_tail(s1),
                                                stream_tail(s2)))))
def add_streams(s1, s2):
    return stream_map_2(lambda x1, x2: x1 + x2, s1, s2)
def partial_sums(s):
    return pair(head(s),
                lambda: add_streams(stream_tail(s),
                                    partial_sums(s)))
def pi_summands(n):
    return pair(1 / n, lambda: stream_map(lambda x: -x, pi_summands(n + 2)))

pi_stream = scale_stream(partial_sums(pi_summands(1)), 4)
print(stream_ref(accelerated_sequence(euler_transform, pi_stream),
           6))

# expected: 3.1415926535911765
