added lcm-python, fixed links to public keys, actually added the reference to git in en

3 files changed, 230 insertions, 6 deletions

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