path: root/en/lcm-python.org

#+TITLE: A Pythonic FP adventure
#+SUBTITLE: Designing a horrible implementation for LCM
#+AUTHOR: Joel Kronqvist

Let's write a naive function to find the largest common multiple of
two integers in Python. As usual in Python, there is only one obvious
solution.

We will test it with the following check:
#+NAME: code:test
#+begin_src python :exports code
  return lcm(5, 12) == 60
#+end_src

Here's the naive function:

#+begin_src python :noweb yes :exports both
  def lcm(a: int, b: int) -> int:
      m = 1
      n = 1
      while abs(m*a) != abs(n*b):
          if abs(m*a) < abs(n*b):
              m += 1
          else:
              n += 1
      return m*a
  <<code:test>>
#+end_src

#+RESULTS:
: True

Now we should either try to make the function more readable to
increase maintainability, or if it is causing performance issues,
optimize it.

Allegedly Python supports the functional programming
paradigm. Functional programs are readable and maintainable so let's
try that out.

First we want to turn the loop into a recursive call. Because we do
not want to change the type of the function, we need to introduce an
inner function.

#+begin_src python :noweb yes :exports both
  def lcm(a: int, b: int) -> int:
      def inner(m, n):
          if abs(m*a) < abs(n*b):
              return inner(m + 1, n)
          elif abs(n*b) < abs(m*a):
              return inner(m, n + 1)
          else:
              return m*a
      return inner(1, 1)
  <<code:test>>
#+end_src

#+RESULTS:
: True

Now our function technically adheres to the functional paradigm. But
we can do better! The return statements seem quite redundant, right?

#+begin_src python :noweb yes :exports both
  def lcm(a: int, b: int) -> int:
      def inner(m, n):
          return (inner(m + 1, n) if abs(m*a) < abs(n*b) else
                  inner(m, n + 1) if abs(n*b) < abs(m*a) else
                  m*a)
      return inner(1, 1)
  <<code:test>>
#+end_src

#+RESULTS:
: True

I can only guess why if-expressions in Python look like something out
of Perl.

Let's change the inner function to a lambda term as that removes one
return statement.

#+begin_src python :noweb yes :exports both
  def lcm(a: int, b: int) -> int:
      inner = lambda m: lambda n: (
          inner(m + 1)(n) if abs(m*a) < abs(n*b) else
          inner(m)(n + 1) if abs(n*b) < abs(m*a) else
          m*a
      )
      return inner(1)(1)
  <<code:test>>
#+end_src

#+RESULTS:
: True

In the process I also curried the inner function to make it closer to
a true lambda term. Though it is not yet a true lambda term as its
definition is self-referential.

Fixing this allows us also to remove the last return statement by
turning the whole function into a lambda expression.

The fix seems easy at first -- just use fixed point recursion. The
problem is that Haskell Curry's classic Y-combinator, when implemented
directly in Python, gives rise to a stack overflow once any function
is passed to it. Python gets stuck evaluating the Y-combinator as the
argument is evaluated eagerly:
#+BEGIN_QUOTE
All argument expressions are evaluated before the call is attempted. -- [[https://docs.python.org/3/reference/expressions.html#calls]]
#+END_QUOTE

Here's an example for the factorial function producing stack overflow
even before the number to calculate the factorial for is specified:

#+begin_src python :results none :exports code
  Y = (lambda f: (lambda x: f(x(x)))
                 (lambda x: f(x(x))))
  Y(lambda factorial:
    lambda n: 1 if n == 1 else n*factorial(n - 1))
#+end_src

Luckily Python can be tricked into not evaluating the argument as
eagerly with a different version of the Y-combinator. The main
difference seems to be that inside the combinator, ~f~ is not passed
the arguments directly but rather as a lambda form, which allows for
more lazy evaluation. Let's call this new combinator ~fix~. Here's the
definition I found on several internet forums:

#+NAME: code:fix-def
#+begin_src python :results none :exports code
  fix = lambda f: (
      (lambda x: f(lambda v: x(x)(v)))
      (lambda x: f(lambda v: x(x)(v)))
  )
#+end_src

I couldn't find motivation for the given combinator, so here's proof
it works as expected:

#+begin_src python :eval never :exports code
  fix(g)

  = (lambda f: (
      (lambda x: f(lambda v: x(x)(v))) # By rewriting
      (lambda x: f(lambda v: x(x)(v))) # definition above
  ))(g)

  = (lambda x: g(lambda v: x(x)(v)))   # By invoking the function
    (lambda x: g(lambda v: x(x)(v)))   # application (lambda f: ...)(g)

  = g(lambda v:
      (lambda x: g(lambda v: x(x)(v))) # By rewriting x in 'x(x)' with
      (lambda x: g(lambda v: x(x)(v))) # the argument 'lambda x: ...'.
      (v))                             # This is a function application.

  = g((lambda v: fix(g))(v))           # By rewriting the equality
                                       # fix(g) = (lambda x: ...)(lambda x: ...)
                                       # proven in the first two steps

  = g(fix(g))                          # By function application
                                       # (lambda v: ...)(v)
#+end_src

~fix(g) = g(fix(g))~ means that the return value of fix(g) is such a
value that calling g repeatedly on it doesn't change the result,
ie. it is a fixed point of g.

Let's try it out with the factorial function we saw failing earlier.

#+begin_src python :noweb yes
  <<code:fix-def>>

  return fix(lambda factorial:
             lambda n: 1 if n == 1 else n*factorial(n - 1))(5)
#+end_src

#+RESULTS:
: 120

It works fine. Now we can just use the fixed point operator to define
the recursive inner function.

#+begin_src python :noweb yes :exports both
  <<code:fix-def>>

  lcm = lambda a, b: (
      fix(lambda inner:
          lambda m: lambda n: (
              inner(m + 1)(n) if m*a < n*b else
              inner(m)(n + 1) if n*b < m*a else
              m*a
          )
      )(1)(1)
  )

  <<code:test>>
#+end_src

#+RESULTS:
: True

Expanding fix to make lcm a pure lambda term gives

#+begin_src python :noweb yes :exports both
  lcm = lambda a, b: (
      (lambda f: (
          (lambda x: f(lambda v: x(x)(v)))
          (lambda x: f(lambda v: x(x)(v)))
      ))
      (lambda inner:
          lambda m: lambda n: (
              inner(m + 1)(n) if m*a < n*b else
              inner(m)(n + 1) if n*b < m*a else
              m*a
          )
      )(1)(1)
  )

  <<code:test>>
#+end_src

#+RESULTS:
: True