Tchoukaillon hooks

2022-03-19, post № 256

mathematics, #discrete, #haskell, #functional-pearl

Ever since watching D. Knuth’s talk “Tchoukaillon numbers” [1] in the Rutgers experimental mathematics seminar back in January of 2022, I was intrigued by the algorithm he presented to iteratively generate the Tchoukaillon arrays ꚓ⁽ⁿ⁾. Their discrete pointwise limit defines a two-dimensional permutation of the natural numbers, whereby pointwise exactly one value is attained more than once. These properties make calculating the discrete limit expressible as a lazy computation:

tcheInf i j = discreteLimit $ \n -> tche n i j

Despite the seeming simplicity of iteratively taking hooks from an \infty\times n-matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide tche n as finite chunks of tcheFlat n :: [Int]:

tcheFlat 1 = [1..]
tcheFlat n = eval (cycle actions) $ tcheFlat (n-1) where
    actions = concat [[flat (n-m), grab (n-m-1,m)] | m <- [1..n-1]]

tche n i j | j <= n    = (chunksOf n $ tcheFlat n) ## i ## j
           | otherwise = -n

Of course left in the dust by the closed-form formula, D. Knuth’s table’s corner element is computationally viably accessible using this method:

*Main> tcheInf 32 32

Source: tche.hs

Extra assets: tche-inefficient.hs

The naïve’s shackles cannot be undone.

2022-02-19, post № 255

web, #security, #hsts

Without the intend to trivialize the world of material possessions, possibly the novelty alone makes the many quirks and unseen effects which occur in the presence of information-centric conduct hard to grasp in its entirety. Most bizarrely, the concept of ownership admits only to a loose analogy: expected algorithmic runtimes to reproduce bit patterns. Yet if these expections are broken or systems otherwise circumvented, stolen goods are merely accurately replicated hunks of data; nothing ever gets moved or removed, only copied against the origin’s will. Still, the sig­nif­i­cance is akin to theft, only securing bits requires more than not losing them.

As such, it is no wonder that a tender technology like the web took a long and winded path before reaching present-day hardened cryptographic ubiquity. But the tolls of time and progress are plentiful: from the fundamentally inextensible to the obsolete and the undying facets kept alive through compatibility shims, one of such shims being HTTP-talking sockets whose only assignment is to appeal to the client’s senses and never to talk with them again, referring to their HTTPS comrades which are in control of the sought after pages.
Yet cannot the clients remember? Should the clients even seek port 80? What does it mean to support SSL? To enforce it? Answers to these questions are given by HSTS, yet it too has morphed over the years; and a server’s adherence is not certain.

Vanishing members

2022-01-22, post № 254

programming, #c++, #template-metaprogramming

Inheritance is all about keeping material possessions in the familly. Thus, a child may access non-private parent members:

#include <iostream>
struct A { int v{5}; };
struct B : A {
    void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }

Even though v has not been declared inside struct B’s declaration, it accesses it through its inheritance ties to struct A. Feeling the need to be polymorphic with regards to the numerical representation, struct A may be changed to a struct template:

#include <iostream>
template<typename T> struct A { T v{5}; };
struct B : A<int> {
    void f() { std::cout << v << std::endl; } };
int main() { B{}.f(); }

Yet hard-baking in the numerical type for the derived struct feels overly restrictive. As such, one might want to build a templated class hierarchy:

#include <iostream>
template<typename T> struct A { T v{5}; };
template<typename T> struct B : A<T> {
    void f() { std::cout << v << std::endl; } };
int main() { B<int>{}.f(); }

What surprised me nearly two weeks ago — when a templated class hierarchy naturally arose — is that the above does not compile.

$ clang++ 2.cpp
2.cpp:4:29: error: use of undeclared identifier 'v'
    void f() { std::cout << v << std::endl; } };
1 error generated.

Winter MMXXI

2021-12-25, post № 253

ascii-art, esolangs, #language-brainfuck, #winter, #tree


Try it online!

Extra assets: tree.ma, tree.bf

Finite Life’s long trajectories

2021-11-27, post № 252

simulation, #cellular-automata

Conway’s Game of Life is classicly played on the infinite two-state grid \mathbb{F}_2^{\mathbb{Z}^2} with only a finite number of cells lit in the starting configuration. Due to its particular rules, Turing machines can be embedded within it, making it equivalently powerful computationally. Paired with the non-existence of a uniform distribution on countably infinite discrete sets, homogenously reasoning about trajetories of all Games of Life is hindered by both an unclear enumeration and fundamental limits of computation.
More tractably, Life can be played on a discrete torus with finitely many states. Because of this global size limitation, Turing completeness is lost since only finitely many world states exist. For host architecture’s compatibility’s sake, I chose to play in an 𝟪 ⨉ 𝟪-sized toric world represented as an uint64_t; with Life’s rules implemented by bit-fiddling. C++20 kindly offers std::pop_count which, paired with bit-wise neighbourhood masks, allows for a clean rule encoding:

const int pc{std::popcount(w & neighbourhood_masks[j])};
if (pc == 3 || (w & (1ULL << j) && pc == 2))
    v |= 1ULL << j;

The corresponding masks are compile-time generated using a constexpr-evaluated lambda returning a std::array<world_t, 64>. Source: fgol-traj.cpp

With finite Life defined and implemented, the question I set out to ask can be posed:

For how long can one play finite Life until revisiting a world state?

In the finite directed graph of all 2^{64} states with edges representing one time step of evolution according to Life’s rules, one seeks to find world states which either take a long time to fall into a cycle or ones which lead into large cycles. In that regard, this maximum time is an indicator of the ‘entropic depth’ of this simulation.

Since the search space is too vast to be exhaustively searched, the 64 bits which make up a state are pseudo-randomly uniformly chosen and evolved. Keeping track of previously simulated initial state’s times, a record is kept. As of now, the longest trajectory length has been 401, achieved by the following starting configuration:

$ ./fgol-traj 0558cdc8400d3b35
world 0558cdc8400d3b35:
[]  []  [][]    
[][]  [][][]    
[]  [][]        
      []    [][]
[]  [][]    [][]
      [][]  []  
[]  []          

trajectory length until first self-colision: 401
periodicity: 132
first point of periodicity: 0000c0b070000000

Before this trajetory length, two states were found with a score of 375: 8e423847408ec519 and 94c0f9892ad05be8.

Yet this method only achieves lower bounds. Starting states which take longer than 300 steps to repeat already seem to be quite rare; finding the above state took multiple hours of searching. And because of this problem’s highly non-continuous nature, a rogue state could be lurking out there in the vastness of thought, waiting to be discovered by someone.

Halloween MMXXI: Uncanny Woods

2021-10-31, post № 251

prose, #halloween

Treading muddied woodland grounds, a squeak did interrupt my slumber: for that I knew I was alone, amidst the grayish silhouettes ahead of me, a dim cinder I could witness. For it was only briefly lit, I felt its simmering prolonged. A frosty gust of air firmly held me grasped in place: a shuffling in the branches sent blockage swiftly my way. I dare not dream a moment shifted, was forced to alter all my venture. It had been long from when I hurried, it would be long to when I rest. Marching ment moving, a certain goal. But arrival was not certain, the path now winded and uncharted. What was it that has led me here, what did I seek, what wish to find? It could be that it was quite near, or ever further gone the more I hoped to clench it tight.
Canopies lifting everso slightly, my future forking akin to the countless branches left behind: should I continue forward, sloping down and narrowed, or should I turn and head on sideways, this path more open though it may be longer? A twig fell down, to guide me it seemed. I wedged my feeble body through the thicking foliage. Slowed down by ever denser flora, drained and worn I stopped. I stood. I listened to the world around me. I slumbered.
Close off my entrance the woodlands did. For I was drowsy, forwards slipped my mind. Where to now? — Another spark. The last remnants of hope mounting, I stepped, misstepped. Leafy branches swept over. The forest rested.

The humble sum should neither necessitate indirection nor be unbounded across package boundaries

2021-10-30, post № 250

language-design, #go

Routinely, I am irked by the effort required in most languages to express algebraic data types — the epitome of information itself. An inert datum is too often occluded by hardware-inspired lingo forcing one to adapt to rigid register-fitted types. Leastways the C lineage supports bytestrings together with their concatenation which, under the previous constraints, are equatable to product types. Though whilst control flow neatly factors through such a type, the categorical dual consistently requires an iffy cast or virtual semantics alltogether: the humble sum is quietly ignored in favor of its dual in whose hulking shadow it sometimes desintegrates out of existence. A far cry from Haskell’s effortless type alternative “|”, C at least supports byte-based type superpositioning. Yet although Go inherits “struct”, the fameless yet in no way inferior “union” is — to me unreasonably — absent.

Consequently, when I implemented miniKanren in Go back in March of 2021 [1], I was flabber­gasted to find a gaping language definition hole where I had expected a sum type. Toying with the idea to one-hot encode S-expressions via

\sum_i\alpha_i\hookrightarrow\prod_i\alpha_i,\quad x_k\mapsto(0_1,\dots,0_{k-1},x_k,0_{k+1},\dots,0_n),

I quickly dismissed it in hopes of a more elegant idiomatic Go approach. What I found was an interpretation of a sum type which conflates object action, dynamic dispatch, undefined control flow and unbounded sums \sum_{i\in\Omega}\alpha_i into a briddle mess of Go lines which can be viewed as indeed implementing a type coproduct. Needless to say, I am dissatisfied with Go’s negligence in this regard.

Hoisting HTTP headers home

2021-10-02, post № 249

web, #http, #header

While developing my new minimalistic HTTP backend — a web server called vanadium —, scourering MDN’s HTTP header documentation and inspecting the headers sent by web servers serving public websites, I first stumbled upon the header “Server” and decided for my server to tell the world its name. Yet most servers send a lot of headers, many of which non-standard and most of unclear purpose to myself. This discovery made me think: HTTP headers may be the most commonly sent textual data virtually invisible to most computer operators due to common web browser’s failure to communicate them. Thus I will in this post shine a light on my findings examining various web server’s initial banter.

Interrogation of web servers hinges on using a capable client, as without the server’s headers, no web browser could fulfill its role as a HTTP client. Yet this communication is often hidden from the user. One client which allows viewing headers is curl, although one has to read its man page thoroughly:

$ curl -fsSLD- -o/dev/null https://...

Above, curl is invoked to fail silently, be silent about its network progress yet still Show errors, follow Location redirects and Dump the HTTP response header to standard output (indicated by a singular dash). Furthermore, the response’s body is output to the null device.
Note that web servers may respond differently to different user agents, about which intel is acquired via the HTTP header “User-Agent” sent by the connecting client. One may specifically remove or set this header using $ curl -A '' or the same with a non-empty flag argument. Since I did neither, curl sent its own name together with its version, for me “curl/7.77.0” and “curl/7.74.0”.

Amusing HTTP headers

Looking at the sometimes dozens of headers sent by various websites, among the cookies and entity tags one finds sparsely sprinkled innocent items of information. Heise for one, a German publishing house operating “heise.de” and “ct.de”, configured some of their Apache and nginx servers to spew a whopping four non-standard inert HTTP headers at unsuspecting surfers:

$ curl -fsSLD- -o/dev/null heise.de | grep ^X
X-Cobbler: servo65.heise.de
X-Pect: The Spanish Inquisition
X-Clacks-Overhead: GNU Terry Pratchett
Jonathan Frech's blog; built 2024/07/06 12:42:51 CEST