I don't publish as much content in English on the web as in Finnish. -I've got a gemini capsule for you all in English at -gemini://cron4.fi. My contact information can be found there if you -need it. +You might want to check out my git repositories. I've also got a +gemini capsule for you all in English at gemini://cron4.fi. My contact +information can be found there if you need it.

@@ -232,6 +232,10 @@ Here is still an explicit index of the English side of my website. + +A Pythonic FP adventure Designing a horrible implementation for LCM + + Public key Send encrypted data to me or verify my signature diff --git a/generated/en/lcm-python.html b/generated/en/lcm-python.html new file mode 100644 index 0000000..7f3abed --- /dev/null +++ b/generated/en/lcm-python.html @@ -0,0 +1,495 @@ + + + + + + + +A Pythonic FP adventure + + + + + + +

A Pythonic FP adventure +
+Designing a horrible implementation for LCM +

+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: +

return lcm(5, 12) == 60
+

+ +

+Here's the naive function: +

+ +

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
+return lcm(5, 12) == 60
+

+ +

+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. +

+ +

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)
+return lcm(5, 12) == 60
+

+ +

+True
+

+ + +

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

+ +

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)
+return lcm(5, 12) == 60
+

+ +

+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. +

+ +

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)
+return lcm(5, 12) == 60
+

+ +

+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: +

+
+All argument expressions are evaluated before the call is attempted. – https://docs.python.org/3/reference/expressions.html#calls +
+

+ +

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

+ +

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))
+

+ +

+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: +

+ +

fix = lambda f: (
+    (lambda x: f(lambda v: x(x)(v)))
+    (lambda x: f(lambda v: x(x)(v)))
+)
+

+ +

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

+ +

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)
+

+ +

+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. +

+ +

fix = lambda f: (
+    (lambda x: f(lambda v: x(x)(v)))
+    (lambda x: f(lambda v: x(x)(v)))
+)
+
+return fix(lambda factorial:
+           lambda n: 1 if n == 1 else n*factorial(n - 1))(5)
+

+ +

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

+ +

fix = lambda f: (
+    (lambda x: f(lambda v: x(x)(v)))
+    (lambda x: f(lambda v: x(x)(v)))
+)
+
+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)
+)
+
+return lcm(5, 12) == 60
+

+ +

+True
+

+ + +

+Expanding fix to make lcm a pure lambda term gives +

+ +

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)
+)
+
+return lcm(5, 12) == 60
+

+ +

+True
+

@@ -240,7 +240,7 @@ Below there is proof that my new key is legitimate assuming you already trusted my old key.

A Pythonic FP adventure + +Designing a horrible implementation for LCM +

A Pythonic FP adventure +
+Designing a horrible implementation for LCM +