What is cosh(List(Bool))? Or beyond algebra: analysis of data types.
Taylor vs. Haskell, 1:0 .
a very occasional diary @ Nikita Danilov
Latest posts
Review of Feminism, Interrupted: Disrupting Power by L. Olufemi
Review of Feminism, Interrupted: Disrupting Power by L. Olufemi, Pluto Press, 2020 “ f eminism means freedom, it means the right to be […] incoherent “, p. 71 Let me state outright, that I won’t be able to provide a critique of the cogent rational argument that forms the core of Ms. Olufemi's book, for the simple fact that even the most diligent search will not find an argument of that sort there.…
Publish or Perish in style.
Joseph Liouville , a famous French mathematician, whom multiple important theorems are named after, was also the founder and the editor of Journal de Mathématiques Pures et Appliquées , universally known as Liouville's journal (still in print, still very prestigious, two centuries later!). Here is the list of the articles Liouville published in his own journal in 1861: And then some more: ... and…
Long [story of] division.
The following text can be viewed as extremely dry and intimidating, or, equally, lightheadedly funny. Let's formally verify the venerable long-division algorithm. uintN_t div(uintN_t n, uintN_t d) { uintN_t q := 0; uintN_t r := 0; int i := N - 1; while (i != -1) { r <<= 1; r |= ((n >> i) & 1); if (r >= d) { r := r - d; q |= 1 << i; } i := i - 1; } return q; } Here uintN_t is the type of unsigned N…
Euclid continuity
Let's talk about one of the simplest, if not trivial, subjects in the oldest and best-established branch of mathematics: rectangle area in elementary Euclid geometry. The story contains two twists and an anecdote. We all know that the area of a rectangle or a parallelogram is a product of its base and height, and the area of a triangle is half of that (areas of a parallelogram, a triangle and a…
When people used to care about the quality of presentation
From Errata to Dijsktra's A Primer of Algol 60 Programming .
usched: update
Update for the previous post about stackswap coroutine implementation usched . To recap, usched is an experimental (and very simple, 120LOC) coroutine implementation different from stackful and stackless models: coroutines are executed on the native stack of the caller and when the coroutine is about to block its stack is copied into a separately allocated ( e.g. , in the heap) buffer. The buffer…
Generating Catalan numbers.
Enumerate all binary trees with N nodes, C++20 way: #include <memory> #include <string> #include <cassert> #include <iostream> #include <coroutine> #include <cppcoro/generator.hpp> struct tnode; using tree = std::shared_ptr<tnode>; struct tnode { tree left; tree right; tnode() {}; tnode(tree l, tree r) : left(l), right(r) {} }; auto print(tree t) -> std::string { return t ? (std::string{"["} +…
A Python: it's dictionaries all the way down.
def drill(): return defaultdict(drill)
usched: stackswap coroutines, neither stackful nor stackless
[Please read the update .] This repository ( https://github.com/nikitadanilov/usched ) contains a simple experimental implementation of coroutines alternative to well-known "stackless" and "stackful" methods. The term "coroutine" gradually grew to mean a mechanism where a computation, which in this context means a chain of nested function calls, can "block" or "yield" so that the top-most caller…
3-lisp: an infinite tower of meta-circular interpreters.
Précis 3-lisp is a dialect of Lisp designed and implemented by Brian C. Smith as part of his PhD. thesis Procedural Reflection in Programming Languages (what this thesis refers to as " reflection " is nowadays more usually called " reification "). A 3-lisp program is conceptually executed by an interpreter written in 3-lisp that is itself executed by an interpreter written in 3-lisp and so on ad…
Treadmill
Treadmill is a "real-time" in-place garbage collection algorithm designed by H. Baker [ 0 ]. It is simple, elegant, efficient and surprisingly little known. Speaking of which, Mr. Baker's Wikipedia page rivals one for an obscure Roman decadent poet in scarcity of information. The general situation of garbage collection is that there is a program (called a mutator in this case) that allocates…
360 years later or „Скрещенья ног“
In 1896 Paul Gauguin completed Te Arii Vahine ( The King’s Wife ): From many similar paintings of his Tahitian period this, together with a couple of preparatory watercolours, is distinguished by artificial legs placement, which can be characterised in Russian by the equally forced line (quoted in this article's title) from a certain universally acclaimed poem. This strange posture is neither a…
A curious case of stacks and queues.
When studying computing science we all learn how to convert an expression in the "normal" (" infix ", "algebraic") notation to " reverse Polish " notation. For example, an expression " a*b + c*d " is converted to " a b * c d * + ". An expression in reverse Polish notation can be seen as a program for a stack automaton : PUSH A PUSH B MUL PUSH C PUSH D MUL ADD Where PUSH pushes its argument on the…
Unexpected isomorphism
Since Cantor's "I see it, but I cannot believe it" (1877), we know that \(\mathbb{R}^n\) are isomorphic sets for all \(n > 0\). This being as shocking as it is, over time we learn to live with it, because the bijections between continua of different dimensions are extremely discontinuous and we assume that if we limit ourselves to any reasonably well-behaving class of maps the isomorphisms will…
Why Go is Not My Favorite Programming Language
Disclaimer : this article shares very little except the title with the classical Why Pascal is Not My Favorite Programming Language . No attempt is made to analyse Go in any systematic fashion. To the contrary, the focus is on one particular, if grave, issue. Moreover, the author happily admits that his experience with Go programming is very limited. Go is a system programming language and a large…
Cographs, cocounts and coconuts.
Abstract : Dual of the familiar construction of the graph of a function is considered. The symmetry between graphs and cographs can be extended to a suprising degree. Given a function \(f : A \rightarrow B\), the graph of f is defined as $$f^* = \{(x, f(x)) \mid x \in A\}.$$ In fact, within ZFC framework, functions are defined as graphs. A graph is a subset of the Cartesian product \(A \times B\).…
Conatus trimetro iambico.
Aloof as stardust rains Are memory dim prints Eliding tensed face By shadows within of All conquering space that Inly trusts each friend Of madness—whose embrace Accept with no delays To take one final look Before you turn Rose ways. A rather rare meter in English, but much easier once you let enjambments in.
Translations.
Licence my roving hands, and let them go, Before, behind, between, above, below. O my America! my new-found-land -- J. Donne, 1633. Блуждающим рукам моим дай разрешенье, Пусти вперед, назад, промеж, и вверх, и вниз, О дивный новый мир, Америка моя! Variant reading reeing instead of roving is even better. I hope that "О дивный новый мир" ( O brave new world ) is not entirely anachronistic.
Zero everywhere.
( студенческая олимпиада МФТИ по математике , 2013, задача 3) Предположим, что \(\forall x\in\mathbb{R}\to f(x) \neq 0\). Возьмем произвольный интервал \([a, b] \subset \mathbb{R}\), \(a \lt b\) и докажем, что на этом интервале есть точка \(x_0\) такая, что \(\lim \limits_{x\to x_0} f(x) \neq 0\). Пусть \(T_n = |f|^{-1}([\frac{1}{n}, +\infty)) \cap [a, b]\), т.е. \(x \in T_n \equiv |f(x)| \ge…
Blindsight spot.
I just realised that in any unital ring commutativity of addition follows from distributivity: \(a + b\) \(=\) \(-a + a + a + b + b - b\) \(=\) \(-a + a\cdot(1 + 1) + b\cdot(1 + 1) - b\) \(=\) \(-a + (a + b)\cdot(1 + 1) - b\) \(=\) \(-a + (a + b)\cdot 1 + (a + b)\cdot 1 - b\) \(=\) \(-a + a + b + a + b - b\) \(=\) \(b + a\) The same holds for unital modules, algebras, vector spaces, &c. Note that…
Whither science (А болт мы сделаем деревянным).
I was recently on a committee, reviewing papers for a computer science conference. The submissions, from all over the world, were in PDF. One submission was actually a Trojan. An executable masking as a PDF file. This by itself is a startling evidence of how widespread spying became (the Trojan came from a respectable university email address), but the really alarming thing is that this was *not*…
Parmigianino's faces
An angel from Madonna with the long neck (1535): An unidentified girl from Antea (1524, survived everything, including Austrian salt mines): Albeit one can argue that the resemblance is due to the stricture of the mannerist canon (see the earlobes, for example), this is undoubtedly the same face. A discovery no less thrilling even though I am definitely not the first to make it.
threads, contexts and doors.
Paul Turner gave a talk about new threading interface, designed by Google, at this year Linux Plumbers Conference : The idea is, very roughly, to implement the ucontext interface with kernel support. This gives the benefits of kernel threads ( e.g. , SMP support), while retaining fast context switches of user threads. switchto_switch(tid) call hands off control to the specified thread without…
Weekend affinity.
Groups usually come with homomorphisms , defined as mappings preserving multiplication: $$f(a\cdot b) = f(a)\cdot f(b)$$ From this definition, notions of subgroup (monomorphism), quotient group (epimorphism, normal subgroup ) and the famous isomorphism theorem follow naturally. The category of groups with homomorphisms as arrows has products and sums, equalizers and coequalizers all well-known and…