diff options
Diffstat (limited to 'en')
| -rw-r--r-- | en/index.org | 6 | ||||
| -rw-r--r-- | en/lcm-python.org | 224 | ||||
| -rw-r--r-- | en/pgp.org | 6 |
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 @@ -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. |