Lazy evaluation and declarative approach in Python

About me

• CTO at Kitapps Inc.
• CPython contributor
• Production experience: Python, Erlang, Scala, Go, Clojure, Java, JS, C
• Looked at: Haskell, Lisp, Scheme

Goals

• Short functional paradigm presentation
• Other point of view on algorithmic problems
• Python iterators/generators: advanced usage
• Lazy sequences to work with infinite data structures

More How, less Why

(read this presentation only with code samples!)

About declarative programming

• Imperative programming (С/C++, Java)
• Declarative programming
  • Functional programming (Haskell, Scheme, OCaml)
  • Logic programming (Prolog, Clojure core.logic)

• IP = computation in terms of statements that change a program state
• FP = computation as the evaluation of mathematical functions and avoids state and mutable data

Programming task

Calculate partially invalid string with operations: "28*32***32**39"

Programming task

Imperative style = actions that change state from initial state to result

expr, res = "28*32***32**39", 1
for t in expr.split("*"):
    if t != "":
        res *= int(t)

print res

"28*32***32**39", 1
"28", 1
"32", 28
"", 896
"", 896
"32", 896
"", 28672
"39", 28672
1118208

Programming task

Functional style = apply transformation (and compositions)

from operator import mul
expr = "28*32***32**39"
print reduce(mul, map(int, filter(bool, expr.split("*"))), 1)

"28*32***32**39"
["28","32","","","32","","39"]
["28","32","32","39"]
[28,32,32,39]
1118208

Functional is about...

• Avoid state
• Immutable data
• First-class, higher-order functions
• Purity
• Recursion, tail recursion
• Iterators, sequences
• Lazy evaluation
• Pattern matching, monads....

(our focus in red)

Wikipedia: Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing)

Wikipedia: Lazy evaluation

Benefits:

• Performance increases
• The ability to construct potentially infinite data structures
• The ability to define control flow

"Pouring water problem"

Code

• declare initial state
• declare moves and path
• declare all possible moves

lazy_evaluation.py

Code: immutable operations on list

We need: create new list, change element at position

In [1]: update
Out[1]: function __main__.update

In [2]: update([1,2,3], (0, 10))
Out[2]: [10, 2, 3]

In [3]: update([1,2,3], (0, 10), (1, 20), (3, 30))
Out[3]: [10, 20, 3]

Code: immutable operations on list

Implementation. Think twice!

def update(container, *pairs):
  """
  Create copy of given container, chagning one (or more) elements.

  Creating of new list is necessary here, cause we don't want to
  deal with mutable data structure in current situation - it 
  will be too problematic to keep everything working with many 
  map/reduce operations if data will be mutable.
  """ 
  def pair(left, right):
      pos, el = right
      # todo: use takewhile/dropwhile or write "split-at" helper
      return [(s if i != pos else el) for i, s in enumerate(left)]
  return reduce(pair, pairs, container)

Code: "lazy" wrapper

We need: wrap generator to "reuse" yields

In [4]: def gen():
   ...:     yield 1
   ...:     yield 2
   ...:     yield 3
   ...:     

In [5]: g = gen()
In [6]: list(g)
Out[6]: [1, 2, 3]
In [7]: list(g)
Out[7]: []

In [11]: glazy = lazy(gen)
In [12]: list(glazy)
Out[12]: [1, 2, 3]
In [13]: list(glazy)
Out[13]: [1, 2, 3]

Code: "lazy" wrapper

Implementation

class lazy:
    def __init__(self, origin, state=None):
        self._origin = origin() if callable(origin) else origin
        self._state = state or []
        self._finished = False
    def __iter__(self):
        return self if not self._finished else iter(self._state)
    def __next__(self):
        try:
            n = next(self._origin)
        except StopIteration as e:
            self._finished = True
            raise e
        else:
            self._state.append(n)
            return n

Code

• end state declaration and folding
• solution declaration
• hint: Path class

lazy_evaluation.py

What's for Python 2.*?

• itertools.imap instead of map
• itertools.ifilter instead of filter
• reduce instead of functools.reduce
• def pair(left, (pos, el)) is possible
• for _ in _: yield _ instead of yield from

Fibonacci in Haskell

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Usage:

Prelude> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]
Prelude> take 20 fibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]

Fibonacci in Clojure

user> (def fib (lazy-cat [0 1] (map + fib (rest fib))))
user> (take 10 fib)
(0 1 1 2 3 5 8 13 21 34)
user> (take 20 fib)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

Fibonacci in Scala

def fibs: Stream[Int] = 
    0 #:: 1 #:: fibs.zip(fibs.tail).map{case (a,b) => a + b} 

Usage:

scala> fibs(10)
res0: Int = 55
scala> fibs.take(10).toArray
res1: Array[Int] = Array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
scala> fibs.take(20).toArray
res2: Array[Int] = Array(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181)

Fibonacci in Python

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

Usage:

>>> from itertools import islice
>>> print list(islice(fib(), 10))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> print list(islice(fib(), 20))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Lazy, imperative

Advanced: Declarative fibonacci

Our goal:

f = Stream()
fib = f << [0, 1] << map(add, f, drop(1, f))

assert list(take(10, fib)) == [0,1,1,2,3,5,8,13,21,34]
assert fib[20] == 6765
assert fib[30:35] == [832040,1346269,2178309,3524578,5702887]

Lazy, declarative

Stream implementation:

stream.py

Conclusions

Pro

• conciseness
• possible parallel execution

Con

• immutability doesn't supported

The end

Thank you for attention!

• Alexey Kachayev
• Email: kachayev@gmail.com
• Twitter: @kachayev
• Github: kachayev

This presentation:

https://github.com/kachayev/talks/kharkivpy#6