diff options
Diffstat (limited to 'generated')
| -rw-r--r-- | generated/en/index.html | 12 | ||||
| -rw-r--r-- | generated/en/lcm-python.html | 495 | ||||
| -rw-r--r-- | generated/en/pgp.html | 10 | ||||
| -rw-r--r-- | generated/fi/blog/index.html | 2 | ||||
| -rw-r--r-- | generated/fi/blog/sivujen-uudistus.html | 2 | ||||
| -rw-r--r-- | generated/fi/index.html | 2 | ||||
| -rw-r--r-- | generated/fi/pgp.html | 10 | ||||
| -rw-r--r-- | generated/static/aihe.pdf | bin | 144765 -> 144755 bytes |
8 files changed, 516 insertions, 17 deletions
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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(en . Skip to content)" xml:lang="(en . Skip to content)"> <head> -<!-- 2026-06-14 Sun 16:07 --> +<!-- 2026-06-14 Sun 19:51 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Joel Kronqvist</title> @@ -210,9 +210,9 @@ Welcome to my website! <p> 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 <a href="https://git.cron4.fi">my git repositories</a>. 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. </p> <p> @@ -233,6 +233,10 @@ Here is still an explicit index of the English side of my website. </colgroup> <tbody> <tr> +<td class="org-left"><a href="./lcm-python.html">A Pythonic FP adventure</a> Designing a horrible implementation for LCM</td> +</tr> + +<tr> <td class="org-left"><a href="./pgp.html">Public key</a> Send encrypted data to me or verify my signature</td> </tr> </tbody> 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 @@ +<?xml version="1.0" encoding="utf-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" +"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" lang="(en . Skip to content)" xml:lang="(en . Skip to content)"> +<head> +<!-- 2026-06-14 Sun 19:51 --> +<meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> +<meta name="viewport" content="width=device-width, initial-scale=1" /> +<title>A Pythonic FP adventure</title> +<meta name="author" content="Joel Kronqvist" /> +<meta name="generator" content="Org Mode" /> +<style type="text/css"> + #content { max-width: 60em; margin: auto; } + .title { text-align: center; + margin-bottom: .2em; } + .subtitle { text-align: center; + font-size: medium; + font-weight: bold; + margin-top:0; } + .todo { font-family: monospace; color: red; } + .done { font-family: monospace; color: green; } + .priority { font-family: monospace; color: orange; } + .tag { background-color: #eee; font-family: monospace; + padding: 2px; font-size: 80%; font-weight: normal; } + .timestamp { color: #bebebe; } + .timestamp-kwd { color: #5f9ea0; } + .org-right { margin-left: auto; margin-right: 0px; text-align: right; } + .org-left { margin-left: 0px; margin-right: auto; text-align: left; } + .org-center { margin-left: auto; margin-right: auto; text-align: center; } + .underline { text-decoration: underline; } + #postamble p, #preamble p { font-size: 90%; margin: .2em; } + p.verse { margin-left: 3%; } + pre { + border: 1px solid #e6e6e6; + border-radius: 3px; + background-color: #f2f2f2; + padding: 8pt; + font-family: monospace; + overflow: auto; + margin: 1.2em; + } + pre.src { + position: relative; + overflow: auto; + } + pre.src:before { + display: none; + position: absolute; + top: -8px; + right: 12px; + padding: 3px; + color: #555; + background-color: #f2f2f299; + } + pre.src:hover:before { display: inline; margin-top: 14px;} + /* Languages per Org manual */ + pre.src-asymptote:before { content: 'Asymptote'; } + pre.src-awk:before { content: 'Awk'; } + pre.src-authinfo::before { content: 'Authinfo'; } + pre.src-C:before { content: 'C'; } + /* pre.src-C++ doesn't work in CSS */ + pre.src-clojure:before { content: 'Clojure'; } + pre.src-css:before { content: 'CSS'; } + pre.src-D:before { content: 'D'; } + pre.src-ditaa:before { content: 'ditaa'; } + pre.src-dot:before { content: 'Graphviz'; } + pre.src-calc:before { content: 'Emacs Calc'; } + pre.src-emacs-lisp:before { content: 'Emacs Lisp'; } + pre.src-fortran:before { content: 'Fortran'; } + pre.src-gnuplot:before { content: 'gnuplot'; } + pre.src-haskell:before { content: 'Haskell'; } + pre.src-hledger:before { content: 'hledger'; } + pre.src-java:before { content: 'Java'; } + pre.src-js:before { content: 'Javascript'; } + pre.src-latex:before { content: 'LaTeX'; } + pre.src-ledger:before { content: 'Ledger'; } + pre.src-lisp:before { content: 'Lisp'; } + pre.src-lilypond:before { content: 'Lilypond'; } + pre.src-lua:before { content: 'Lua'; } + pre.src-matlab:before { content: 'MATLAB'; } + pre.src-mscgen:before { content: 'Mscgen'; } + pre.src-ocaml:before { content: 'Objective Caml'; } + pre.src-octave:before { content: 'Octave'; } + pre.src-org:before { content: 'Org mode'; } + pre.src-oz:before { content: 'OZ'; } + pre.src-plantuml:before { content: 'Plantuml'; } + pre.src-processing:before { content: 'Processing.js'; } + pre.src-python:before { content: 'Python'; } + pre.src-R:before { content: 'R'; } + pre.src-ruby:before { content: 'Ruby'; } + pre.src-sass:before { content: 'Sass'; } + pre.src-scheme:before { content: 'Scheme'; } + pre.src-screen:before { content: 'Gnu Screen'; } + pre.src-sed:before { content: 'Sed'; } + pre.src-sh:before { content: 'shell'; } + pre.src-sql:before { content: 'SQL'; } + pre.src-sqlite:before { content: 'SQLite'; } + /* additional languages in org.el's org-babel-load-languages alist */ + pre.src-forth:before { content: 'Forth'; } + pre.src-io:before { content: 'IO'; } + pre.src-J:before { content: 'J'; } + pre.src-makefile:before { content: 'Makefile'; } + pre.src-maxima:before { content: 'Maxima'; } + pre.src-perl:before { content: 'Perl'; } + pre.src-picolisp:before { content: 'Pico Lisp'; } + pre.src-scala:before { content: 'Scala'; } + pre.src-shell:before { content: 'Shell Script'; } + pre.src-ebnf2ps:before { content: 'ebfn2ps'; } + /* additional language identifiers per "defun org-babel-execute" + in ob-*.el */ + pre.src-cpp:before { content: 'C++'; } + pre.src-abc:before { content: 'ABC'; } + pre.src-coq:before { content: 'Coq'; } + pre.src-groovy:before { content: 'Groovy'; } + /* additional language identifiers from org-babel-shell-names in + ob-shell.el: ob-shell is the only babel language using a lambda to put + the execution function name together. */ + pre.src-bash:before { content: 'bash'; } + pre.src-csh:before { content: 'csh'; } + pre.src-ash:before { content: 'ash'; } + pre.src-dash:before { content: 'dash'; } + pre.src-ksh:before { content: 'ksh'; } + pre.src-mksh:before { content: 'mksh'; } + pre.src-posh:before { content: 'posh'; } + /* Additional Emacs modes also supported by the LaTeX listings package */ + pre.src-ada:before { content: 'Ada'; } + pre.src-asm:before { content: 'Assembler'; } + pre.src-caml:before { content: 'Caml'; } + pre.src-delphi:before { content: 'Delphi'; } + pre.src-html:before { content: 'HTML'; } + pre.src-idl:before { content: 'IDL'; } + pre.src-mercury:before { content: 'Mercury'; } + pre.src-metapost:before { content: 'MetaPost'; } + pre.src-modula-2:before { content: 'Modula-2'; } + pre.src-pascal:before { content: 'Pascal'; } + pre.src-ps:before { content: 'PostScript'; } + pre.src-prolog:before { content: 'Prolog'; } + pre.src-simula:before { content: 'Simula'; } + pre.src-tcl:before { content: 'tcl'; } + pre.src-tex:before { content: 'TeX'; } + pre.src-plain-tex:before { content: 'Plain TeX'; } + pre.src-verilog:before { content: 'Verilog'; } + pre.src-vhdl:before { content: 'VHDL'; } + pre.src-xml:before { content: 'XML'; } + pre.src-nxml:before { content: 'XML'; } + /* add a generic configuration mode; LaTeX export needs an additional + (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */ + pre.src-conf:before { content: 'Configuration File'; } + + table { border-collapse:collapse; } + caption.t-above { caption-side: top; } + caption.t-bottom { caption-side: bottom; } + td, th { vertical-align:top; } + th.org-right { text-align: center; } + th.org-left { text-align: center; } + th.org-center { text-align: center; } + td.org-right { text-align: right; } + td.org-left { text-align: left; } + td.org-center { text-align: center; } + dt { font-weight: bold; } + .footpara { display: inline; } + .footdef { margin-bottom: 1em; } + .figure { padding: 1em; } + .figure p { text-align: center; } + .equation-container { + display: table; + text-align: center; + width: 100%; + } + .equation { + vertical-align: middle; + } + .equation-label { + display: table-cell; + text-align: right; + vertical-align: middle; + } + .inlinetask { + padding: 10px; + border: 2px solid gray; + margin: 10px; + background: #ffffcc; + } + #org-div-home-and-up + { text-align: right; font-size: 70%; white-space: nowrap; } + textarea { overflow-x: auto; } + .linenr { font-size: smaller } + .code-highlighted { background-color: #ffff00; } + .org-info-js_info-navigation { border-style: none; } + #org-info-js_console-label + { font-size: 10px; font-weight: bold; white-space: nowrap; } + .org-info-js_search-highlight + { background-color: #ffff00; color: #000000; font-weight: bold; } + .org-svg { } +</style> +<link rel="stylesheet"type="text/css" href="../../static/global.css"> +</head> +<body> +<div id="preamble" class="status"> +<header> +<a id="skiptocontent" href="#content">Skip to content</a> +<a href="/fi/">FI</a> · <a href="/en/">EN</a> +</header> +</div> +<div id="content" class="content"> +<h1 class="title">A Pythonic FP adventure +<br /> +<span class="subtitle">Designing a horrible implementation for LCM</span> +</h1> +<p> +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. +</p> + +<p> +We will test it with the following check: +</p> +<div class="org-src-container"> +<pre class="src src-python" id="orgd663ae3">return lcm(5, 12) == 60 +</pre> +</div> + +<p> +Here's the naive function: +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> + + +<p> +Now we should either try to make the function more readable to +increase maintainability, or if it is causing performance issues, +optimize it. +</p> + +<p> +Allegedly Python supports the functional programming +paradigm. Functional programs are readable and maintainable so let's +try that out. +</p> + +<p> +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. +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> + + +<p> +Now our function technically adheres to the functional paradigm. But +we can do better! The return statements seem quite redundant, right? +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> + + +<p> +I can only guess why if-expressions in Python look like something out +of Perl. +</p> + +<p> +Let's change the inner function to a lambda term as that removes one +return statement. +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> + + +<p> +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. +</p> + +<p> +Fixing this allows us also to remove the last return statement by +turning the whole function into a lambda expression. +</p> + +<p> +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: +</p> +<blockquote> +<p> +All argument expressions are evaluated before the call is attempted. – <a href="https://docs.python.org/3/reference/expressions.html#calls">https://docs.python.org/3/reference/expressions.html#calls</a> +</p> +</blockquote> + +<p> +Here's an example for the factorial function producing stack overflow +even before the number to calculate the factorial for is specified: +</p> + +<div class="org-src-container"> +<pre class="src src-python">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)) +</pre> +</div> + +<p> +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, <code>f</code> is not passed +the arguments directly but rather as a lambda form, which allows for +more lazy evaluation. Let's call this new combinator <code>fix</code>. Here's the +definition I found on several internet forums: +</p> + +<div class="org-src-container"> +<pre class="src src-python" id="org08ab578">fix = lambda f: ( + (lambda x: f(lambda v: x(x)(v))) + (lambda x: f(lambda v: x(x)(v))) +) +</pre> +</div> + +<p> +I couldn't find motivation for the given combinator, so here's proof +it works as expected: +</p> + +<div class="org-src-container"> +<pre class="src src-python">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) +</pre> +</div> + +<p> +<code>fix(g) = g(fix(g))</code> 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. +</p> + +<p> +Let's try it out with the factorial function we saw failing earlier. +</p> + +<div class="org-src-container"> +<pre class="src src-python">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) +</pre> +</div> + +<p> +It works fine. Now we can just use the fixed point operator to define +the recursive inner function. +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> + + +<p> +Expanding fix to make lcm a pure lambda term gives +</p> + +<div class="org-src-container"> +<pre class="src src-python">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 +</pre> +</div> + +<pre class="example"> +True +</pre> +</div> +</body> +</html> 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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(en . Skip to content)" xml:lang="(en . Skip to content)"> <head> -<!-- 2026-06-14 Sun 16:07 --> +<!-- 2026-06-14 Sun 21:10 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Public key</title> @@ -230,9 +230,9 @@ ECCF 8023 A9D8 D00D BC3B 4437 C378 B657 8281</code>. Download my public keys from the following links: </p> <ul class="org-ul"> -<li><a href="file:///static/pub.key">My public key</a></li> -<li><a href="file:///static/old.key">My old public key</a></li> -<li><a href="file:///static/email.key">The public key I use with email</a></li> +<li><a href="../static/pub.key">My public key</a></li> +<li><a href="../static/old.key">My old public key</a></li> +<li><a href="../static/email.key">The public key I use with email</a></li> </ul> <p> @@ -240,7 +240,7 @@ Below there is proof that my new key is legitimate assuming you already trusted my old key. </p> -<pre class="example" id="orge57b8ed"> +<pre class="example" id="org46400e0"> -----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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(fi . Siirry pääsisältöön)" xml:lang="(fi . Siirry pääsisältöön)"> <head> -<!-- 2026-06-14 Sun 16:07 --> +<!-- 2026-06-14 Sun 19:51 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Blogin sisällys</title> 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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(fi . Siirry pääsisältöön)" xml:lang="(fi . Siirry pääsisältöön)"> <head> -<!-- 2026-06-14 Sun 19:48 --> +<!-- 2026-06-14 Sun 19:51 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Verkkosivujeni uudistus</title> 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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(fi . Siirry pääsisältöön)" xml:lang="(fi . Siirry pääsisältöön)"> <head> -<!-- 2026-06-14 Sun 19:44 --> +<!-- 2026-06-14 Sun 19:51 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Joel Kronqvist</title> 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"> <html xmlns="http://www.w3.org/1999/xhtml" lang="(fi . Siirry pääsisältöön)" xml:lang="(fi . Siirry pääsisältöön)"> <head> -<!-- 2026-06-14 Sun 19:44 --> +<!-- 2026-06-14 Sun 21:10 --> <meta http-equiv="Content-Type" content="text/html;charset=utf-8" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <title>Julkinen avaimeni</title> @@ -227,16 +227,16 @@ avaimen sormenjälki on <code>7a8ceccf8023a9d8d00dbc3b4437c378b6578281</code>. Lataa julkiset avaimeni seuraavista linkeistä: </p> <ul class="org-ul"> -<li><a href="file:///static/pub.key">Julkinen avaimeni</a></li> -<li><a href="file:///static/old.key">Vanha julkinen avaimeni</a></li> -<li><a href="file:///static/email.key">Sähköpostini julkinen avain</a></li> +<li><a href="../static/pub.key">Julkinen avaimeni</a></li> +<li><a href="../static/old.key">Vanha julkinen avaimeni</a></li> +<li><a href="../static/email.key">Sähköpostini julkinen avain</a></li> </ul> <p> Alla on vielä todiste siitä, että uusi julkinen avaimeni on aito. </p> -<pre class="example" id="org64bdd01"> +<pre class="example" id="org3586cfe"> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 diff --git a/generated/static/aihe.pdf b/generated/static/aihe.pdf Binary files differindex dd927b7..2aa5910 100644 --- a/generated/static/aihe.pdf +++ b/generated/static/aihe.pdf |