From 2eae125c21238a65fc312b09b3d99f5664f3e6cb Mon Sep 17 00:00:00 2001 From: Joel Kronqvist Date: Sun, 14 Jun 2026 21:12:12 +0300 Subject: added lcm-python, fixed links to public keys, actually added the reference to git in en --- en/index.org | 6 +- en/lcm-python.org | 224 +++++++++++++++ en/pgp.org | 6 +- fi/pgp.org | 6 +- generated/en/index.html | 12 +- generated/en/lcm-python.html | 495 ++++++++++++++++++++++++++++++++ generated/en/pgp.html | 10 +- generated/fi/blog/index.html | 2 +- generated/fi/blog/sivujen-uudistus.html | 2 +- generated/fi/index.html | 2 +- generated/fi/pgp.html | 10 +- generated/static/aihe.pdf | Bin 144765 -> 144755 bytes 12 files changed, 749 insertions(+), 26 deletions(-) create mode 100644 en/lcm-python.org create mode 100644 generated/en/lcm-python.html diff --git a/en/index.org b/en/index.org index 1249e5e..84acf2f 100644 --- a/en/index.org +++ b/en/index.org @@ -3,9 +3,9 @@ Welcome to my website! 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 [[https://git.cron4.fi][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. Also, in case you want to send me encrypted messages or verify that I have indeed signed a file, you can find my public key & its diff --git a/en/lcm-python.org b/en/lcm-python.org new file mode 100644 index 0000000..d0d768d --- /dev/null +++ b/en/lcm-python.org @@ -0,0 +1,224 @@ +#+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 + <> +#+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) + <> +#+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) + <> +#+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) + <> +#+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 + <> + + 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 + <> + + 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) + ) + + <> +#+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) + ) + + <> +#+end_src + +#+RESULTS: +: True diff --git a/en/pgp.org b/en/pgp.org index 14a7065..1566981 100644 --- a/en/pgp.org +++ b/en/pgp.org @@ -15,9 +15,9 @@ router IP:s weren't blacklisted so often. It's fingerprint is ~7A8C ECCF 8023 A9D8 D00D BC3B 4437 C378 B657 8281~. Download my public keys from the following links: -- [[/static/pub.key][My public key]] -- [[/static/old.key][My old public key]] -- [[/static/email.key][The public key I use with email]] +- [[../static/pub.key][My public key]] +- [[../static/old.key][My old public key]] +- [[../static/email.key][The public key I use with email]] Below there is proof that my new key is legitimate assuming you already trusted my old key. diff --git a/fi/pgp.org b/fi/pgp.org index 0dbe8c3..1034802 100644 --- a/fi/pgp.org +++ b/fi/pgp.org @@ -14,9 +14,9 @@ sähköpostipalveluntarjoajalleni. Sähköposteja varten käyttämäni avaimen sormenjälki on ~7a8ceccf8023a9d8d00dbc3b4437c378b6578281~. Lataa julkiset avaimeni seuraavista linkeistä: -- [[/static/pub.key][Julkinen avaimeni]] -- [[/static/old.key][Vanha julkinen avaimeni]] -- [[/static/email.key][Sähköpostini julkinen avain]] +- [[../static/pub.key][Julkinen avaimeni]] +- [[../static/old.key][Vanha julkinen avaimeni]] +- [[../static/email.key][Sähköpostini julkinen avain]] Alla on vielä todiste siitä, että uusi julkinen avaimeni on aito. diff --git a/generated/en/index.html b/generated/en/index.html index cf0ca2a..09cf561 100644 --- a/generated/en/index.html +++ b/generated/en/index.html @@ -3,7 +3,7 @@ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> - + Joel Kronqvist @@ -210,9 +210,9 @@ Welcome to my website!

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

+
+Skip to content +FI · EN +
+
+
+

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
+
+
+ + diff --git a/generated/en/pgp.html b/generated/en/pgp.html index e9a3588..a7cabf7 100644 --- a/generated/en/pgp.html +++ b/generated/en/pgp.html @@ -3,7 +3,7 @@ "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> - + Public key @@ -230,9 +230,9 @@ ECCF 8023 A9D8 D00D BC3B 4437 C378 B657 8281. Download my public keys from the following links:

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

-
+
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA256
 
diff --git a/generated/fi/blog/index.html b/generated/fi/blog/index.html
index 4942414..a1f74f0 100644
--- a/generated/fi/blog/index.html
+++ b/generated/fi/blog/index.html
@@ -3,7 +3,7 @@
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
 
 
-
+
 
 
 Blogin sisällys
diff --git a/generated/fi/blog/sivujen-uudistus.html b/generated/fi/blog/sivujen-uudistus.html
index 19ea2c9..4983a9f 100644
--- a/generated/fi/blog/sivujen-uudistus.html
+++ b/generated/fi/blog/sivujen-uudistus.html
@@ -3,7 +3,7 @@
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
 
 
-
+
 
 
 Verkkosivujeni uudistus
diff --git a/generated/fi/index.html b/generated/fi/index.html
index 80390c0..071bd86 100644
--- a/generated/fi/index.html
+++ b/generated/fi/index.html
@@ -3,7 +3,7 @@
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
 
 
-
+
 
 
 Joel Kronqvist
diff --git a/generated/fi/pgp.html b/generated/fi/pgp.html
index 89033e3..f4a7988 100644
--- a/generated/fi/pgp.html
+++ b/generated/fi/pgp.html
@@ -3,7 +3,7 @@
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
 
 
-
+
 
 
 Julkinen avaimeni
@@ -227,16 +227,16 @@ avaimen sormenjälki on 7a8ceccf8023a9d8d00dbc3b4437c378b6578281.
 Lataa julkiset avaimeni seuraavista linkeistä:
 

 
 
 

 Alla on vielä todiste siitä, että uusi julkinen avaimeni on aito.
 

 
-
+
 -----BEGIN PGP SIGNED MESSAGE-----
 Hash: SHA256
 
diff --git a/generated/static/aihe.pdf b/generated/static/aihe.pdf
index dd927b7..2aa5910 100644
Binary files a/generated/static/aihe.pdf and b/generated/static/aihe.pdf differ
-- 
cgit v1.2.3