jfrech.com
jblog
table of contents

jblog has moved.

2020-09-05, post № 233

internal, #blog movement, #freedom, #politics

Having read Free as in Freedom [1] and being appalled at the digitalization-driven annihilation of once fought for values paired with de-facto government-mandated acceptance of this new brutal reality, I concluded to no longer be morally capable of supporting the web in its current form and thus began work on my own blogging software in April of 2020.
Now, beginning of September 2020, this project has reached a presentable state; having transferred all 232 jblog posts, reformatting and annotating them as well as improving minor syntactically or grammaticallly uneven sections, I can announce my blog’s movement:

https://www.jfrech.com/blog

If you choose to visit my blog, I can assure you that no trackers, cookies or malicious scripts will be employed against you. I will not try to collect a lot of data about your visit and the few inherently technically required data points in form of non-aggregated system logs will not be shared with third parties.

This 233rd post is the last to be published on https://jonathanfrech.wordpress.com, which will be shut down on the 31st of December 2020.
If you are interested in my blog, you can use my RSS feed to get a full list of my blog posts, updated as new are written. RSS is not like other subscription models — there is no server which knows your details and eagerly sends traffic your way to coerce you to a click. RSS requires you, the user, to request a feed and only then will transmit said feed.

Note that this blog’s content is subject to a clearly defined set of licenses specifying the terms and conditions with which it can be used.

Setting Up a HTTPS Backend Using Go and Let’s Encrypt

2020-08-08, post № 232

Go, programming, #backend, #SSL, #systems administration, #VPS, #web

I recently needed to set up a dynamic web backend to both serve dynamically generated files as well as HTTP POST forms. Thus, I thought long and deeply of a solution that is both modern and versatile yet hassle-free to set up — since my systems administration skills are rather sparse. The solution I found is to write a Go webserver; implicitly concurrent and enabling a high level of control.

Of course, nowadays you cannot run a (esp. dynamic) website without HTTPS; every browser worth its salt will display potential visitors a message framing you as a ruthless criminal. Fortunately, Let’s Encrypt gifts you the required bits: an SSL certificate!
Since I need a URL for the upcoming snippet and am personally thinking of switching my own homepage from a webserver to a self-hosted VPS setup, I chose to use www.jfrech.com as an example domain herein.

% # ... installing certbot (for example via `apt update && apt install certbot`) ...
% certbot certonly --standalone --preferred-challenges http -d www.jfrech.com
% # ... cli certbot interaction ...

% # ... installing Go ... (for example via `apt install golang`) ...

% # ... periodically renewing certificates ...

Once certbot has issued a certificate (the URL has to have a DNS entry linked to the current VPS and port 80 has to be unoccupied), incorporating it into the server is made straight forward by http.ListenAndServeTLS:

func handle(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintln(w, `<!doctype html><html><body><p>ip <code>` + template.HTMLEscapeString(r.RemoteAddr) + `</code> requesting <code>` + template.HTMLEscapeString(r.URL.Path) + `</code></p></body></html>`)
}
func main() {
    http.HandleFunc("/", handle)
    log.Fatal(http.ListenAndServeTLS(":443", "/etc/letsencrypt/live/www.jfrech.com/fullchain.pem", "/etc/letsencrypt/live/www.jfrech.com/privkey.pem", nil))
}

Since now the server only listens on port 443, one can add a HTTP-to-HTTPS redirection on port 80:

func handleHTTP(w http.ResponseWriter, r *http.Request) {
    target := "https://" + r.Host + r.URL.Path
    if len(r.URL.RawQuery) > 0 {
        target += "?" + r.URL.RawQuery
    }
    http.Redirect(w, r, target, http.StatusTemporaryRedirect)
}
func main() {
    http.HandleFunc("/", handle)
    go http.ListenAndServe(":80", http.HandlerFunc(handleHTTP))
    log.Fatal(http.ListenAndServeTLS(":443", "/etc/letsencrypt/live/www.jfrech.com/fullchain.pem", "/etc/letsencrypt/live/www.jfrech.com/privkey.pem", nil))
}

One advantage of writing one’s one web server is full control of how the website behaves. One implication, which can be seen as a downside, is that you have to do everything; even the most basic of logging. However, writing your own log files enables you to confidently follow the logging policy you employ.
From a security standpoint, you can exactly control which files are served and which result in a 404 response; avoiding accidently exposing the whole server’s directory structure for the world to see.

Moth

2020-07-11, post № 231

art, ASCII, haiku, poetry, #insect, #night dwelling

       ___       
 __   /  / ___   
/# \  \  \/  /   
\__ \_/   |  \__ 
  _/|__  /  ____\
   _/  \___/ _/  
         _/      

Whoosh — a gust of air.
Although miniscule; it is.
A moth flapped its wings.

Extra assets: moth_development.txt

Measly Mazes

2020-06-13, post № 230

C, games, #generator, #maze

I wanted to create a maze generator for quite some while now and recently picked up the project again, using a naive approach consisting of applying a randomized depth-first search algorithm on a given rectangle. Thus, the resulting maze’s internal path structure is quite shallow, with most path forks having one degenerated short section.
Nevertheless, mazes are generated:

measly-mazes.png
jt maze --ppm 32 32 | convert - -sample 1000% maze.png

You can generate your own mazes either by building maze.c natively or by using my newly developed package manager jt.

Lichen, Extraterrestrials, Diodes #2

2020-05-16, post № 229

art, #LED

lichen-extraterrestrials-diodes-2_2020-05-15_green-led.jpg
lichen-extraterrestrials-diodes-2_2020-05-15_red-led.jpg

Java’s Terseness

2020-04-22, post № 228

Java, programming, #anti-pattern, #anti-patternism

Whilst pondering the lost control one has over pastebin posts as a guest; the inability to remove a text one has published themselves and the entailed virtually temporally unbounded availability to anyone of this text, I decided to look at pastebin’s “archive” site — a chronologically sorted collection of the most recent public pastebin posts.

One interesting post was titled Filter — Stringrid — Delphi and appears to be a Delphi program with German comments accomplishing some two-dimensional array manipulation task.

However, when looking further down the archive, a post published around two minutes earlier caught my attention — exmp1 [1]. This innocuously titled Java source file upon closer contains inspection an impressive 𝟥𝟦𝟫 lines of code. Now, source files of such a line count are not unreasonable (especially when writing Java), however it is not the typical size of an example — as this paste’s title suggests.
Thus, I decided to read it to know what it is meant to accomplish and how it is written — the source’s line count is highly misleading regarding its functionality.

Colorful Time Prompt in zsh

2020-04-18, post № 227

programming, #customization, #prompt, #zsh

I have been using zsh for a while now, and whilst I like its minimalistic approach, I felt that my prompt lacked a certain graphical oomph.
Thus, I built what most graphical environments hide away at the screen’s corner directly into the prompt — a clock. Paired with a time-sensitive rainbow color scheme, I find the result quite visually pleasing.

If you want to try out my prompt, the following installer automatically downloads jprompt.c (Unlanguaged), compiles it and asks if .zshrc should be set up to load my prompt.
Since jblog has moved, the below script might not work.

% curl --silent https://www.jfrech.com/jblog/post227/install.zsh | zsh

Zpr’(h

2020-03-21, post № 226

programming, Zpr'(h, #esolang

I have designed and implemented a new esoteric programming language called Zpr’(h. It is a language built upon iterated symbolic pattern matching, requiring the user to define their own semantics and interpreting them as computations.
Whilst developing Zpr’(h, I implemented a rudimentary standard library, defining semantics for natural numbers, mappings, lists and logic. Furthermore, I used these semantics to define a lazy computation of all prime numbers — albeit executing at a rather slow pace.
Having finalized the language’s specifications I began investigating its computational bounds. After all, testing primality is a primitive recursive relation. Thus, it a priori is not even clear if Zpr’(h is Turing complete — a useful feature for a programming language to have.

Pondering this question, I thought about how to show that Zpr’(h is indeed Turing complete — driven by hope that I have not created a primitively weak language. I briefly thought about implementing a Turing machine but quickly opted to implement a brainfuck interpreter — equivalent, since both can simulate each other.
After having written said brainfuck interpreter (), I proceeded to test it only to realize that using byte-based pattern matching to implement a brainfuck interpreter in a functional manner does not lead to the most efficient implementation. Interpreting the brainfuck program ++[->+++<]>. — that is, multiplying two by three — takes a respectable twenty seconds at 𝟦.𝟢𝟢 GHz. Yet more excruciatingly, adhering to commutativity and interpreting +++[->++<]>. yields the same correct numerical result, although at a steep slowdown to over three minutes.
Time constraints are not the only factor — since the current Zpr’(h implementation does not alias any byte sequences if long byte sequences are duplicated, the memory footprint rises to the unmanageable, easily blowing the 𝟣 GiB provided by default. Increasing the available memory most likely not make much of a difference given the aforementioned exponential behavior.
Thus, testing larger brainfuck programs appears not to be feasible due to computational resource limitations. Nevertheless, I am now fairly certain of Zpr’(h being Turing complete, even though my brainfuck implementation may not be correct.
To input brainfuck source code into the above interpreter, I used this translator.

Not being satisfied with a nigh untestable brainfuck implementation, I attempted to fulfil another classical interpretation of computability; recursive functions. As seen above, primitive recursive functions can already be modelled, leaving only the existence of µ-recursion open; a one-liner using the standard library:

(µ .p) |> (head (filter p |N0))

In conclusio, I am convinced that Zpr’(h is Turing complete, if not very efficient — a common faith of esoteric programming languages.

As a side note, implementing the Ackermann-Peter function is fairly intuitive:
I have also golfed in Zpr’(h; it is not the most terse language out there.

Complete Contact Configurations

2020-02-22, post № 225

C, games, programming, #board game, #Contact, #stochastic analysis

Contact is a board game designed by Ken Garland in which players draw square tiles containing colored connections from a pile, attempting to form matches. Whilst the game is enjoyable to play — allowing the odd trading of cards in unfortunate circumstances — it seldom leads to a complete configuration, meaning a valid contacting arrangement using all available cards.

With the power of stochastically driven brute-force, however, finding such complete configurations turns out to be feasible — at least when playing with the 𝟣𝟦𝟢 cards my Contact version contains. Not surprisingly, many solutions are of rather linear nature since the game only contains two branching cards, i. e. cards where three sides boast connections.
Thus, the search is further narrowed in by demanding a maximum dimension, that is the final configuration has to lie in a card rectangle of a given area. From my testing, a maximum dimension of 𝟧𝟢𝟢 is moderately quickly computed (~ 𝟥𝟢 sec @ 4.00 GHz), whilst lower maximum dimensions appear to be less likely.

complete-contact-configurations-00_tdg-500.png
0complete-contact-configurations-00_tdg-500.png225/complete-contact-configurations-00_tdg-500.pngcomplete-contact-configurations-01_tdg-500.png225/complete-contact-configurations-01_tdg-500.pngcomplete-contact-configurations-02_tdg-500.png225/complete-contact-configurations-02_tdg-500.pngcomplete-contact-configurations-03_tdg-500.png225/complete-contact-configurations-03_tdg-500.pngcomplete-contact-configurations-04_tdg-500.png225/complete-contact-configurations-04_tdg-500.pngcomplete-contact-configurations-05_tdg-500.png225/complete-contact-configurations-05_tdg-500.pngcomplete-contact-configurations-06_tdg-500.png225/complete-contact-configurations-06_tdg-500.pngcomplete-contact-configurations-07_tdg-500.png225/complete-contact-configurations-07_tdg-500.pngcomplete-contact-configurations-08_tdg-500.png225/complete-contact-configurations-08_tdg-500.pngcomplete-contact-configurations-09_tdg-500.png225/complete-contact-configurations-09_tdg-500.pngcomplete-contact-configurations-10_tdg-500.png225/complete-contact-configurations-10_tdg-500.pngcomplete-contact-configurations-11_tdg-500.png225/complete-contact-configurations-11_tdg-500.pngcomplete-contact-configurations-12_tdg-500.png225/complete-contact-configurations-12_tdg-500.pngcomplete-contact-configurations-13_tdg-500.png225/complete-contact-configurations-13_tdg-500.pngcomplete-contact-configurations-14_tdg-500.png225/complete-contact-configurations-14_tdg-500.pngcomplete-contact-configurations-15_tdg-500.png225/complete-contact-configurations-15_tdg-500.pngcomplete-contact-configurations-00_tdg-500.png

From an implementation point of view, a generalized Contact card (defined as four sides, each with three nodes being blank or colored one of three colors) snuggly fits into 𝟤𝟦 bits, allowing for card rotation, reflection and match determination bei ng implemented thru integer bit fiddling.
The stochastic process is driven by an (ideally assumed) uniformly distributed random number generator, being recursively applied until all cards are consumed. Finally, an image is created as a portable pixmap .ppm and resized to a .png using ImageMagick.

Source code: complete-contact-configurations.c (Unlanguaged)

Non-Uniform Shuffling

2020-01-25, post № 224

C, Haskell, mathematics, programming, #algorithms, #false implementation, #probability theory

A shuffle of a finite sequence of length 𝑛 of distinguishable elements refers to an algorithmic process which — modulo pseudo-randomness — can be modeled as a random variable uniformly distributed on the permutations \mathbb{S}_n.
However, most pseudo-random entropy sources provide only a pseudo-uniformly distributed realization of \mathbb{F}_2^\mathbb{N}, leading to the necessity of finding an algorithmic transformation process if one wishes to achieve a shuffle.
In the following, I will assume that a transforming process to a family of independent and uniformly on \{1..n\} distributed random variables is already present for any n\in\mathbb{N}.

One naive and seemingly correct (it is not) approach is to traverse the given sequence, uniformly swapping the current entry with another one, i. e.

void falseShuffle(uint64_t *arr, size_t len) {
    for (size_t j = 0; j < len; j++)
        swap(arr, j, unif(len)); }

as an exemplary C implementation where \texttt{unif}(n) is independent and uniformly distributed on \{0..n-1\}.

Yet, even though sensible on first sight, the above defined random variable is only in the most trivial cases uniformly distributed and — as empirical evidence suggests, see below — horrendously non-uniformly distributed otherwise.
To prove the non-uniformity postulated above, I first present the following number-theoretic result.
Claim. In only three trivial cases does the factorial of a natural number divide its tetration; formally
\forall\,n\in\mathbb{N}_{>2}:n!\nmid n^n.
Proof. Let n\in\mathbb{N}_{>2} be a natural number larger than two. By the definition of the factorial, \prod_{p<n\ \text{prime}}p\mid n! is evident. Assume n!\mid n^n. Adhering to the uniqueness of prime factorizations, \prod_{p<n}p\mid n follows. Observe that n-1>1 has to be prime since \forall\,p<n\ \text{prime}:n-1\equiv -1\not\equiv 0\mod p, implying n-1\mid\prod_{p<n}p\mid n which cannot hold for 𝑛 > 𝟤.
Proof. Now suppose, falseShuffle was indeed non-trivially distributed uniformly. Without loss of generality, all involved probability spaces were finite. Then there had to exist a surjection from this algorithm’s entropic state to \mathbb{S}_n with fibers of the same finite cardinality, implying n!\mid n^n. By the above proven claim, 𝑛 < 𝟥 followed, making the distribution trivial.

One possible reason for the surprising nature of this non-uniformity is the striking source code resemblance to a correct implementation, i. e.

void shuffle(uint64_t *arr, size_t len) {
    for (size_t j = 0; j < len; j++)
        swap(arr, j, j + unif(len - j)); }

as an exemplary C implementation which can be inductively shown to resemble the same structure as \mathbb{S}_n, in each step sprinkling in some uniform randomness and thus being itself uniformly distributed.

To see just how non-uniform falseShuffle is, I have calculated its discrete density for 𝑛 = 𝟦:

[       |                ]
[   |   |||              ]
[   |   |||              ]
[   |   |||              ]
[   ||  ||||||| ||       ]
[||||| |||||||| |||    ||]
[|||||||||||||||||| || ||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
n = 4

If it was uniformly distributed, the discrete density would look like a rectangle; [||||| ... |||||]. Further plots for 𝟢 ≤ 𝑛 ≤ 𝟨 are shown in non-uniform-shuffling.txt (Unlanguaged).

Source code for the analysis and plotting: non-uniform-shuffling.hs (Unlanguaged). Empirical evidence of non-uniformity: non-uniform-shuffling.c (Unlanguaged).

Generating the Prouhet-Thue-Morse sequence in brainfuck

2019-12-28, post № 223

brainfuck, mathematics, programming, #recursive, #Thue-Morse sequence

[-]<<<[-]<<<[-]<<<[-]<<<[-]<<<[-]>>>>>>>>>>>>>>>>>[-]++++++++++++++++++++++++++++++++++++++++++++++++.[-]<[-]>>[-]<[-<+>>+<]>[-<+>]<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>[-]+[>[-]+[<<[-]<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>+<<<-]>>>>>>[-]<<<[->>>+<<<][-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<<<<[-]>>>>>>[<<<<<<+>>>>>>-]<<<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>>>>>>>[-]+<[->[-]<]>[-<+>]<<<<[-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>>>>>>[-]<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>+<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>[-]<<[->>+<<]>>][-]+[<<[-]<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>>>>+<<<<<<-]>>>>>>>>>[-]<<<[->>>+<<<][-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>[-]<<<<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>>>>+<<<<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>>>>[-]<<[->>+<<]>>][-]+[<<[-]<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>>[-]<<<[->>>+<<<]>>>>[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]<<[->+>+<<]>>[-<<+>>]<.<<<<[-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>[-]<<<<<<<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>>>>>>>[-]<<[->>+<<]>>]<]

Try it online.