As many web platform developer and Firefox users, I believe Mozilla’s mission is instrumental for a better Internet. In a recent Igalia’s chat about the Web Ecosystem Health, participants made the usual observation regarding this important role played by Mozilla on the one hand and the limited development resources and small Firefox’s usage share on the other hand. In this blog post, I’d like to explain an experimental idea we are launching at Igalia to try and make browser development better match the interest of the web developer and user community.
Igalia’s contribution to browser repositories
As mentioned in the past in this blog, Igalia has contributed to different part of Firefox such as multimedia (e.g. <video> support), layout (e.g. Stylo, WebRender, CSS, MathML), scripts (e.g. BigInt, WebAssembly) or accessibility (e.g. ARIA). But is it enough?
Although commit count is an imperfect metric it is also one of the easiest to obtain. Let’s take a look at how Igalia’s commits repositories of the Chromium (chromium, v8), Mozilla (mozilla-central, servo, servo-web-render) and WebKit projects were distributed last year:
As you can see, in absolute value Igalia contributed roughly 3/4 to Chromium, 1/4 to WebKit, with a small remaining amount to Mozilla. This is not surprising since Igalia is a consulting company and our work depends on the importance of browsers in the market where Chromium dominates and WebKit is also quite good for iOS devices and embedded systems.
This suggests a different way to measure our contribution by considering, for each project, the percentage relative to the total amount of commits:
In the WebKit project, where ~80% of the contributions were made by Apple, Igalia was second with ~10% of the total. In the Chromium project, the huge Google team made more than 90% of the contributions and many more companies are involved, but Igalia was second with about 4% of the total. In the Mozilla project, Mozilla is also doing ~90% of the contributions but Igalia only had ~0.5% of the total. Interestingly, the second contributing organization was… the community of unindentified gmail.com addresses! Of course, this shows the importance of volunteers in the Mozilla project where a great effort is done to encourage participation.
Open Prioritization
From the commit count, it’s clear Igalia is not contributing as much to the Mozilla project as to Chromium or WebKit projects. But this is expected and is just reflecting the priority set by large companies. The solid base of Firefox users as well as the large amount of volunteer contributors show that the Mozilla project is nevertheless still attractive for many people. Could we turn this into browser development that is not funded by advertising or selling devices?
Another related question is whether the internet can really be shaped by the global community as defended by the Mozilla’s mission? Is the web doomed to be controlled by big corporations doing technology’s “evangelism” or lobbying at standardization committees? Are there prioritization issues that can be addressed by moving to a more collective decision process?
At Igalia, we internally try and follow a more democratic organization and, at our level, intend to make the world a better place. Today, we are launching a new Open Prioritization experiment to verify whether crowdfunding could be a way to influence how browser development is prioritized. Below is a short (5 min) introductory video:
I strongly recommend you to take a look at the proposed projects and read the FAQ to understand how this is going to work. But remember this is an experiment so we are starting with a few ideas that we selected and tasks that are relatively small. We know there are tons of user reports in bug trackers and suggestions of standards, but we are not going to solve everything in one day !
If the process is successful, we can consider generalizing this approach, but we need to test it first, check what works and what doesn’t, consider whether it is worth pursuing, analyze how it can be improved, etc
Two Crowdfunding Tasks for Firefox
As explained in the previous paragraph, we are starting with small tasks. For Firefox, we selected the following ones:
CSS lab() colors. This is about giving web developers a way to express colors using the CIELAB color space which approximates better the human perception. My colleague Brian Kardell wrote a blog with more details. Some investigations have been made by Apple and Google. Let’s see what we can do for Firefox !
SVG path d attribute. This is about expressing SVG path using the corresponding CSS syntax for example <path style="d: path('M0,0 L10,10,...')">. This will likely involve a refactoring to use the same parser for both SVG and CSS paths. It’s a small feature but part of a more general convergence effort between SVG and CSS that Igalia has been involved in.
Conclusion
Is this crowd-funded experiment going to work? Can this approach solve the prioritization problems or at least help a bit? How can we improve that idea in the future?…
There are many open questions but we will only be able to answer them if we have enough people participating. I’ll personally pledge for the two Firefox projects and I invite you to at least take a look and decide whether there is something there that is interesting for you. Let’s try and see!
Note: This blog post was co-authored by AMP and Igalia teams.
Web developers continue to face challenges with web interoperability issues and a lack of implementation of important features. As an open-source project, the AMP Project can help represent developers and aid in addressing these challenges. In the last few years, we have partnered with Igalia to collaborate on helping advance predictability and interoperability among browsers. Standards and the degree of interoperability that we want can be a long process. New features frequently require experimentation to get things rolling, course corrections along the way and then, ultimately as more implementations and users begin exploring the space, doing really interesting things and finding issues at the edges we continue to advance interoperability.
Both AMP and Igalia are very pleased to have been able to play important roles at all stages of this process and help drive things forward. During the first half of this year, here’s what we’ve been up to…
Default Aspect Ratio of Images
In our previous blog post we mentioned our experiment to implement the intrinsic size attribute in WebKit. Although this was a useful prototype for standardization discussions, at the end there was a consensus to switch to an alternative approach. This new approach addresses the same use case without the need of a new attribute. The idea is pretty simple: use specified width and height attributes of an image to determine the default aspect ratio. If additional CSS is used e.g. “width: 100%; height: auto;”, browsers can then compute the final size of the image, without waiting for it to be downloaded. This avoids any relayout that could cause bad user experience. This was implemented in Firefox and Chromium and we did the same in WebKit. We implemented this under a flag which is currently on by default in Safari Tech Preview and the latest iOS 14 beta.
Scrolling
We continued our efforts to enhance scroll features. In WebKit, we began with scroll-behavior, which provides the ability to do smooth scrolling. Based on our previous patch, it has landed and is guarded by an experimental flag “CSSOM View Smooth Scrolling” which is disabled by default. Smooth scrolling currently has a generic platform-independent implementation controlled by a timer in the web process, and we continue working on a more efficient alternative relying on the native iOS UI interfaces to perform scrolling.
We have also started to work on overscroll and overscroll customization, especially for the scrollend event. The scrollend event, as you might expect, is fired when the scroll is finished, but it lacked interoperability and required some additional tests. We added web platform tests for programmatic scroll and user scroll including scrollbar, dragging selection and keyboard scrolling. With these in place, we are now working on a patch in WebKit which supports scrollend for programmatic scroll and Mac user scroll.
On the Chrome side, we continue working on the standard scroll values in non-default writing modes. This is an interesting set of challenges surrounding the scroll API and how it works with writing modes which was previously not entirely interoperable or well defined. Gaining interoperability requires changes, and we have to be sure that those changes are safe. Our current changes are implemented and guarded by a runtime flag “CSSOM View Scroll Coordinates”. With the help of Google engineers, we are trying to collect user data to decide whether it is safe to enable it by default.
Another minor interoperability fix that we were involved in was to ensure that the scrolling attribute of frames recognizes values “noscroll” or “off”. That was already the case in Firefox and this is now the case in Chromium and WebKit too.
Intersection and Resize Observers
As mentioned in our previous blog post, we drove the implementation of IntersectionObserver (enabled in iOS 12.2) and ResizeObserver (enabled in iOS 14 beta) in WebKit. We have made a few enhancements to these useful developer APIs this year.
Users reported difficulties with observe root of inner iframe and the specification was modified to accept an explicit document as a root parameter. This was implemented in Chromium and we implemented the same change in WebKit and Firefox. It is currently available Safari Tech Preview, iOS 14 beta and Firefox 75.
Another thing that we have been concerned with is how we can give more control and power to authors to more effectively tell the browser how to manage the loading of resources and improve performance.
The lazy image loading implementation in WebKit therefore passes the related WPT tests and is functional and comparable to the Firefox and Chrome implementations. However, as you might expect, as we compare uses and implementation notes it becomes apparent that determining the moment when the lazy image load should start is not defined well enough. Before this can be enabled in releases some more work has to be done on improving that. The related frame lazy loading work has not started yet since the specification is not in place.
We also added an implementation for stale-while-revalidate. The stale-while-revalidate Cache-Control directive allows a grace period in which the browser is permitted to serve a stale asset while the browser is checking for a newer version. This is useful for non-critical resources where some degree of staleness is acceptable, like fonts. The feature has been enabled recently in WebKit trunk, but it is still disabled in the latest iOS 14 beta.
Contributions were made to improve prefetching in WebKit taking into account its cache partitioning mechanism. Before this work can be enabled some more patches have to be landed and possibly specified (for example, prenavigate) in more detail. Finally, various general Fetch improvements have been done, improving the fetch WPT score. Examples are:
There is still a lot to do in scrolling and resource loading improvements and we will continue to focus on the features mentioned such as scrollend event, overscroll behavior and scroll behavior, lazy loading, stale-while-revalidate and prefetching.
As a continuation of the work done for aspect ratio calculation of images, we will consider the more general CSS aspect-ratio property. Performance metrics such as the ones provided by the Web Vitals project is also critical for web developers to ensure that their websites provide a good user experience and we are willing to investigate support for these in Safari.
We love doing this work to improve the platform and we’re happy to be able to collaborate in ways that contribute to bettering the web commons for all of us.
In a previous blog post, I described an oscillating Zeno’s paradox, which can be formalized as follows. Atalanta moves on the real line. She leaves from 0 and at step $n$ she decides to move forward or backward by $\backslash frac\{1\}\{2^\{n+1\}\}$. If $\backslash epsilon\_n\; \backslash in\; \{\backslash \{-1,\; 1\backslash \}\}$ corresponds to the chosen direction then writing $S\_0\; =\; 0$ and
we obtain sequence of Atalatan’s position on the real line.
In the non-oscillating case ($\backslash epsilon\_n\; =\; 1$ for all $n$) then this just corresponds to a geometric series of common ration $\backslash frac\{1\}\{2\}$. $S\_n$ converges to 1 by lower values, with remaining distance being $\backslash frac\{1\}\{2^n\}$. More generally, $S\_n$ is just the partial sum of an absolutely convergent series and so is convergent to a destination $S\_\backslash infty\; =\; \{\backslash sum\_\{n=0\}^\{+\backslash infty\}\; \backslash frac\{\backslash epsilon\_n\}\{2^\{n+1\}\}\}$. It is easy to see that $\backslash left|S\_n\backslash right|\; <\; 1$, $\backslash left|S\_\backslash infty\backslash right|\; \backslash leq\; 1$ and $\{\backslash left|\; S\_\backslash infty\; -\; S\_n\; \backslash right|\; \backslash leq\; \backslash frac\{1\}\{2^n\}\}$. If additionally $\backslash epsilon\_n$ is chosen so that it is not ultimately constant (i.e. Atalatan’s position keeps oscillating) then this becomes a strict inequality $\{\backslash left|\; S\_\backslash infty\; -\; S\_n\; \backslash right|\; <\; \backslash frac\{1\}\{2^n\}\}$.
In theory, it is possible to reach any destination $x\; \backslash in\; \{[-1,1]\}$ using this approach. Just define $\backslash epsilon\_n\; =\; 1$ if and only if $S\_n\; \backslash leq\; x$ (i.e. “move toward $x$”). It is easy to prove by recurrence that $\{\backslash left|\; x\; -\; S\_n\; \backslash right|\; \backslash leq\; \backslash frac\{1\}\{2^n\}\}$ for all $n$ and so $S\_\backslash infty\; =\; x$. However, this assumes we already know $x$ in order to decide the sequence of directions $\backslash epsilon\_n$. Let’s see how to build sequences without knowing the destination.
Avoiding an at most countable subset
Suppose that $X\; \backslash subseteq\; \backslash mathbb\; R$ is at most countable and let $\{(x\_n)\}\_\{n\; \backslash in\; \backslash mathbb\; N\}$ be a sequence of real numbers such that $X\; =\; \backslash left\backslash \{\; x\_n\; :\; n\; \backslash in\; \backslash mathbb\; N\; \backslash right\backslash \}$. We want to find a sequence such that $S\_\backslash infty\; \backslash notin\; X$.
Assuming additionally that it has infinitely many terms above $1$ and infinitely many terms below $-1$, then we obtain a non-ultimately-constant sequence by defining $\backslash epsilon\_n\; =\; 1$ if and only if $S\_n\; \backslash geq\; x\_n$ (i.e. “move away from $x$”). This is because $-1\; <\; S\_n\; <\; 1$ so there are always infinitely many terms in front of and behind Atalanta.
Incidentally, $X\; =\; \backslash mathbb\; N$ with trivial enumeration $x\_n\; =\; n$ shows a simple counter-example with no term below $-1$ and ultimately constant $\backslash epsilon\_n$. In that case, $S\_0\; =\; 0$ and $S\_\{1\}\; =\; \backslash frac\{1\}\{2\}$ and $S\_\{n+1\}\; =\; S\_\{n\}\; -\; \backslash frac\{1\}\{2^\{n+1\}\}$ for $n\; \backslash geq\; 1$. But $S\_\backslash infty\; =\; 0\; \backslash in\; \backslash mathbb\; N$.
To workaround that issue, we can alternatively define the sequence $\backslash epsilon\_\{2n\}\; =\; 1$ if and only if $S\_n\; \backslash geq\; x$ and $\backslash epsilon\_\{2n+1\}\; =\; -\backslash epsilon\_\{2n\}$. This still moves away from all $x\_n$ once, keeps oscillating and does not require additional assumption on $X$.
Whatever the decision chosen, we can show that $S\_\{\backslash infty\}\; \backslash notin\; X$. Otherwise, consider one $N$ such that $\backslash epsilon\_\{N\}$ is defined by moving away from $S\_\{\backslash infty\}$. Then either $\{S\_N\; -\; S\_\backslash infty\}\; \backslash geq\; 0$ and $S\_\{N+1\}\; =\; \{S\_N\; +\; \backslash frac\{1\}\{2^\{N+1\}\}\}\; \backslash geq\; \{S\_\backslash infty\; +\; \backslash frac\{1\}\{2^\{N+1\}\}\}$ or $S\_\{N+1\}\; =\; \{S\_N\; -\; \backslash frac\{1\}\{2^\{N+1\}\}\}\; <\; \{S\_\backslash infty\; -\; \backslash frac\{1\}\{2^\{N+1\}\}\}$. But in any case, we would have $\{\backslash left|\; S\_\backslash infty\; -\; S\_\{N+1\}\; \backslash right|\; \backslash geq\; \backslash frac\{1\}\{2^\{N+1\}\}\}$ which contradicts our strict inequality for not ultimately constant $\backslash epsilon\_n$.
As explained in the previous blog, this shows that $\backslash mathbb\; R$ (or any complete subspace containing $\backslash mathbb\; Q$) is uncountable. Otherwise, we could use a sequence enumerating it to arrive to a contradiction.
Similarly, because $\backslash mathbb\; Q$ is countable then we can find a sequence such that $\backslash left\backslash \{\; x\_n\; :\; n\; \backslash in\; \backslash mathbb\; N\; \backslash right\backslash \}\; =\; \backslash mathbb\; Q$, which gives us an irrational number $S\_\backslash infty$. If instead $X$ is the set of algebraic numbers (which is countable and contains $\backslash mathbb\; Q$) then we obtain a transcendental $S\_\backslash infty$.
An explicit computation
The big difference between the case of $\backslash mathbb\; Q$ and the set of algebraic numbers is that it’s much easier to actually compute a list of $\{(x\_n)\}\_\{n\; \backslash in\; \backslash mathbb\; N\}$ that lists all the $\backslash mathbb\; Q$. For example, a simple way to enumerate the fractions $\backslash frac\{p\}\{q\}$ without trying to avoid duplicate values is, for each $M=0,\; 1,\; 2,\; ...$ to enumerate the integers $p$ and $q\; \backslash neq\; 0$ bounded by $M$ in the lexicographical order. One can similarly enumerate for each $M$ the non-constant polynomial of degree at most $M$ and integer coefficient bounded by $M$ but it’s not obvious how to actually compute their roots.
One can rely on root finding algorithm to estimate the roots $\backslash alpha$ in order to be able to calculate the sign $S\_n\; -\; \backslash alpha$ and so determine $\backslash epsilon\_n$. But in theory, $\backslash alpha$ can be arbitrary close to $S\_n$ so it’s not clear how much precision to request.
Instead, let’s consider $\{(P\_n)\}\_\{n\; \backslash in\; \backslash mathbb\; N\}$ an enumeration of the non-constant polynomial with integer cofficients and define $\backslash epsilon\_n\; =\; 1$ if and only if $\{(P\_n\backslash prime\; P\_n)\}\{(S\_n)\}\; \backslash geq\; 0$. With that new formula, $\backslash epsilon\_n$ can be calculated very easily in $O(\backslash deg\; P\_n)$ from the cofficients of $P\_n$ using Horner’s method.
For any integer $M\; \backslash geq\; 1$, let’s consider $Q\_M^\backslash pm\; =\; \{(X\; \backslash pm\; 2)\}^M$. Then its product with its derivative is $M\; \{(X\; \backslash pm\; 2)\}^\{2M\; -1\}$. Its value at any $x$ has the same sign as $x\; \backslash pm\; 2$ and if $\backslash left|x\backslash right|\; <\; 1$ it just $\backslash pm$. For any $n$, we can find $M$ large enough such that $Q\_M^+$ and $Q\_M^-$ have not been enumerated yet. So $\backslash epsilon\_n$ is not ultimately constant. Alternatively, we could have used the trick from the previous section to force that property.
Now let’s prove that $S\_\backslash infty$ is still algebraic. If that’s not the case, let $n$ such that $\{P\_n(S\_\backslash infty)\}\; =\; 0$. We can choose $n$ such that $P\_n$ is of minimal degree and so $\{P\_n\backslash prime(S\_\backslash infty)\}\; \backslash neq\; 0$. Since $P\_n$ has only finitely many roots, there is $k\; \backslash geq\; n$ such that at maximum distance $\backslash frac\{1\}\{2^k\}$ around $S\_\backslash infty$, $S\_\backslash infty$ is the only root of $P\_n$ and $P\_n\backslash prime$ does not vanish. Let’s $M$ large enough such that the polynomial $R\_M\; =\; P\_n^\{2M+1\}$ has not been enumerated before $P\_k$. Let’s $l$ such that $P\_l\; =\; R\_M$.
In the considered neighbourhood of $S\_\backslash infty$, $P\_l$ has only one root $S\_\backslash infty$, has the same sign as $P\_n$ and its derivative $\{(2M+1)\}P\_n^\{2M\}\; P\_n\backslash prime$ has the same nonzero constant sign as $P\_n\backslash prime$. Analyzing each combination $P\_l\backslash prime$ positive/negative and $S\_l$ greater/smaller than $S\_\backslash infty$, we verify that $\backslash epsilon\_l$ is chosen such that $\{\backslash left|\; S\_\backslash infty\; -\; S\_\{l+1\}\; \backslash right|\; \backslash geq\; \backslash frac\{1\}\{2^\{l+1\}\}\}$ which is obviously also true if $S\_l\; =\; S\_\backslash infty$. This agains contradict our strict inequality. Q.E.D.
A simple variant of Zeno’s paradoxes can be described as follows. Atalanta wishes to walk to the end of a path. When she gets halfway, she still have to walk the remaining half of the path ; When she gets halfway of that remaining half, she still needs to walk the remaining quarter of the path ; When she gets halfway of that remaining quarter, she still needs to walk the remaining eight of the path ; and so on. Hence it seems she will never reach the end of the path, which is paradoxical.
Obviously, this is not true: Atalanta is going to reach the end of the path after a certain amount of time. The issue in the previous reasoning is that (assuming she walks at constant velocity) walking these subpaths also takes her respectively half, a quarter, a eight, etc of the total time she actually needs to arrive to her destination… and the observations are only done for a total time that is less than the one needed.
A modern variant
Now suppose the ground is an infinite real line, itself covered by an infinite treadmill on which Atalanta is walking. This treadmill brings Atalanta in the opposite direction by twice her velocity. She can decide to turn the treadmill on or off, but its state must remain the same during the whole walk of a subpath. In the following schema, the treadmill was enabled when she was on the second subpath:
After the total duration considered in the previous problem, Atalanta has walked exactly the same total distance on the treadmill. The conveyor belt also moves by summing up distances that are twice the distances on subpaths. Because the treadmill can be on or off, the conveyor’s belt position is not following a simple linear function of the time. Let’s admit for a while it still converges to a certain distance when getting closer to the total duration, I will come back to this at the end of the blog post.
With respect to the ground, Atalanta’s position is basically given by her departure position, moved backward by the distance of the conveyor belt with respect to the ground and moved forward by the distance she walked on the treadmill. As a consequence of the previous paragraph, Atalanta is also converging to a destination with respect to the ground.
Modern Zeno’s paradox (with a flaw)
Now consider an enumeration of all the points of the real line. At the beginning the treadmill is off. Before walking the first half of the path, Atalanta picks the first point in that enumeration and enables the treadmill if she can see that point in front of her. Before walking the next quarter of the path, she picks the second point and enables or disables the treadmill according to whether she can see that second point in front of her. She continues that way for each subpath and each point of the real line.
When a given point is picked there are two options. Either it is not in front of her and so she will just walk forward to a certain distance ; or otherwise the the treamill will additionnaly take her backward by twice that distance. In any case, with respect to the ground, she is moving away from the picked point by the distance she walks during that subpath.
At some step, the point of the real line corresponding to Atalanta’s destination will be picked and she will move away from that destination by a certain distance. But the remaining subpaths are half, a quarter, a eight, etc that distance. To have a chance to converge to the destination again she must now always keep the same direction. But so far, only finitely many points have been picked and so there is at least one point beyond the destination that has not been chosen yet (actually infinitely many). This means she will have to change her direction at least once in the future and so will never be able to reach her destination!
Uncountability of the real line
How to solve the paradox in this modern variant?
First, let’s go back to why the distance of the conveyor belt with respect to the ground is convergent. Consider the binary number whose digits describe the sequences of states of the treadmill: 0 if turned off and 1 if turned on. Place the binary point after the first digit to obtain a real number. Then one can check that the distance of the conveyor belt is given by that real number multiplied by Atalanta’s total distance on the treadmill. Of course, one must admit that such a binary number with infinitely many digits after the binary point is well defined!
For a rigorous proof, note that the conveyor belt is always going in the same direction and at most twice Atalanta’s total walking distance on the treadmill. So the convergence of the conveyor belt just comes from the monotone convergence theorem. This assumption was correct.
However, reading more carefully the argumentation, we actually assumed that there is a countable enumeration of all the points of the real line. But Cantor proved at the end of the 19th century that this is wrong, the real line is uncountable!
It is interesting to actually turn this modern Zeno’s paradox into an apparently “elementary” alternative of Cantor’s diagonal argument, in a way that involves only concepts understandable by the Ancient Greeks and no advanced mathematical formalisms. In particular, this is not mentioning explicitly the positional notation invented by Indian mathematicians. As a comparison, Cantor’s proof assumes that a decimal notation with infinitely many digits after the decimal point is well defined (similar to what we used for our proof with binary numbers) ; or it must deal with the edge case of a real number with two different decimal notations (e.g. 0.4999999… = 0.5).
It is also interesting to note that all the moves as well as Atalanta’s total distance on the treadmill are rational numbers. Since the rational numbers are countable, this modern Zeno’s paradox can also be performed by considering only rational points on the ground. In that case, the flaw is then in the assumption that the conveyor belt converges to a rational point: the set of rational numbers is not complete.
More generally, we can also applie this modern Zeno’s paradox to any ordered field since they include a subset isomorphic to the rational numbers. The conclusion becomes that if the field is Cauchy-complete then it is uncountable.
Update 2020/03/10: Added complexity analysis for S.substr(α, N)
In a previous blog post, I defined for each ordinal $\backslash alpha$ a string $S\_\backslash alpha$ (made of the characters for the empty set, comma, opening brace and closing brace) that enumerates the element of $\backslash alpha$. I gave a simple formulas to calculate the length $L\_\backslash alpha$ of this string.
My colleague Ioanna was a bit disappointed that I didn’t provide a script for calculating the infinite $S\_\backslash alpha$ strings. Obviously, the complexity would be “$\backslash Omega(\backslash omega)$” but it is still possible to evaluate the string at a given position: Given $\backslash beta\; <\; L\_\backslash alpha$, what is the character of $S\_\backslash alpha$ at position $\backslash beta$?
Since the initial segments of the strings are compatible, another way to express this is by introducing the class $S\; =\; \backslash bigcup\_\{\backslash alpha\; \backslash in\; \{\backslash mathrm\{Ord\}\}\}\; S\_\backslash alpha$ corresponding to a giant string enumerating the class $\backslash mathrm\{Ord\}$ of all ordinals. Given an ordinal $\backslash alpha$, what is $S[\backslash alpha]$?
A small generalization of this S.charAt(α) operation is S.substr(α, N) calculating the substring of length $N$ starting at $\backslash alpha$.
Example
$S\_\{2\}$ is "∅,{∅}", so
$S[0]$ is the character ∅, $S[1]$ is a comma,
$S[2]$ is an opening brace and $S[4]$ is a closing brace.
$S\_\{\backslash omega+1\}$ is made of
of an $\backslash omega$-concatenation of finite strings
(the character ∅, a comma,
$S\_1$ surrounded by braces, a comma,
$S\_2$ surrounded by braces, a comma,
$S\_4$ surrounded by braces, a comma, etc), followed
by a comma, an opening brace, the same
$\backslash omega$-concatenation of finite strings and finally
a closing brace.
So $S[\backslash omega]$ is a comma,
$S[\backslash omega+1]$ is an opening brace,
$S[\backslash omega+2]$ is the character "∅"
and $S[\backslash omega2]$ is a closing brace.
In the previous example, we have basically analyzed the string $S\_\{\backslash alpha+1\}$ at a given successor ordinal, splitting it into two copies of $S\_\backslash alpha$, comma and braces. This suggests some easy values of $S$:
Lemma
For any $n\; <\; \backslash omega$ and $\backslash beta\; \backslash geq\; 1$, $S[\backslash alpha]$ is:
A comma if $\backslash alpha$ can be written $2^n\; -\; 3$ or $\backslash omega^\backslash beta\; 2^n\; +\; n$
An opening brace if $\backslash alpha$ can be written $2^n\; -\; 2$ or $\backslash omega^\backslash beta\; 2^n\; +\; n\; +\; 1$
A closing brace if $\backslash alpha$ can be written $2^\{n+1\}\; -\; 4$ or $\backslash omega^\backslash beta\; 2^\{n+1\}\; +\; n$
Proof: For any ordinal $\backslash alpha$, by viewing the string $S\_\{\backslash alpha+1\}$
as a concatenation of $S\_\backslash alpha$, a comma, an opening fence, $S\_\backslash alpha$ and
a closing fence, we deduce that:
$\{S\backslash left[L\_\{\backslash alpha\}\backslash right]\}$ is a comma.
$\{S\backslash left[L\_\{\backslash alpha\}\; +\; 1\; \backslash right]\}$ is an opening brace.
$L\_\{\backslash alpha+1\}$ is a successor ordinal and
$\{S\backslash left[L\_\{\backslash alpha+1\}\; -\; 1\; \backslash right]\}$ is a closing brace.
The lemma follows immediately from the calculation of string lengths performed in the previous blog post. □
Warning: The rest of the blog post gives the solution to this puzzle, so you
might want to have fun solving it yourself first and then go back checking
my proposed solution later 😉...
More generally, the proof of the lemma can be extended by saying that if we find $n$ such that $\{2^n\; -\; 1\}\; \backslash leq\; \backslash alpha\; \backslash leq\; \{2^\{n+1\}\; -\; 5\}$ then $\backslash delta\; =\; \{\backslash alpha\; -\; \{(2^n\; -\; 1)\}\}\; \backslash leq\; \{2^n\; -\; 4\}$ is the index of $\{S[\backslash alpha]\}$ in the second substring $S\_\backslash alpha$ of $S\_\{\backslash alpha+1\}$ and so $\{S[\backslash alpha]\}\; =\; \{S[\backslash delta]\}$.
Details will be provided in the theorem below but one can already write a simple JavaScript recursive program to evalute $S$ at finite ordinals:
Script for $\backslash alpha\; <\; \backslash omega$
The character of $S$ at position $\backslash alpha\; =$
is
The following intermediary step will be helpful to evaluate $S$ at infinite ordinal $\backslash alpha$:
Proposition
Let $\backslash alpha$ is infinite and $\backslash beta\; =\; \backslash log\_\{\backslash omega\}(\backslash alpha)\; \backslash geq\; 1$.
Let $1\; \backslash leq\; q\; <\; \backslash omega$ and $0\; \backslash leq\; \backslash rho\; <\; \backslash omega^\backslash beta$ be the quotient
and remainder of the euclidean division of $\backslash alpha$ by $\backslash omega^\backslash beta$.
Let’s define:
A comma if $\backslash alpha\; =\; \{\backslash omega^\{\backslash beta\}\; 2^n\; +\; n\}$
An opening brace if $\backslash alpha\; =\; \{\backslash omega^\{\backslash beta\}\; 2^n\; +\; n\; +\; 1\}$
An closing brace if $\backslash alpha\; =\; \{\backslash omega^\{\backslash beta\}\; 2^\{n+1\}\; +\; n\}$
$S[\backslash delta]$ otherwise where $\backslash delta$ is the unique
ordinal such that $\backslash alpha\; =\; \{\backslash omega^\backslash beta\; 2^n\; +\; n\; +\; 2\; +\; \backslash delta\}$
and $\backslash delta\; <\; \{\backslash omega^\{\backslash beta\}\; 2^n\; +\; n\}$.
Proof: First by construction we have $\backslash alpha\; =\; \{\; \{\backslash omega^\backslash beta\; q\; \}\; +\; \backslash rho\}$.
If the first case of the definition of $n$, $2^n\; \backslash leq\; q\; <\; 2^\{n+1\}$ so we always have $\backslash alpha\; <\; \{\backslash omega^\backslash beta\; \{(q+1)\}\}\; \backslash leq\; \backslash omega^\backslash beta\; 2^\{n+1\}\; \backslash leq\; L\_\{\backslash omega\{\backslash beta\}\; +\; n\; +\; 1\}$.
If additionnaly $q$ is not a power then $2^n\; <\; q$ and so $\backslash alpha\; \backslash geq\; \{\backslash omega^\{\backslash beta\}q\}\; \backslash geq\; \{\backslash omega^\{\backslash beta\}\{(2^n+1)\}\}\; \backslash geq\; L\_\{\backslash omega\{\backslash beta\}\; +\; n\}$. Otherwise $q\; =\; 2^n$ and $n\; \backslash leq\; \backslash rho$ and so again $\backslash alpha\; \backslash geq\; L\_\{\backslash omega\{\backslash beta\}\; +\; n\}$.
In the second case of the definition of $n$, $\backslash left\backslash lfloor\; \{\backslash log\_2(q)\}\; \backslash right\backslash rfloor\; \backslash geq\; \backslash rho\; +\; 1$ so $n\; \backslash geq\; \backslash rho\; \backslash geq\; 0$. $q$ is a power of 2 and more precisely $q\; =\; 2^\{n+1\}\; >\; 2^n$ so we deduce the same way as in the previous case that $\backslash alpha\; \backslash geq\; L\_\{\backslash omega\{\backslash beta\}\; +\; n\}$. Moreover, $\backslash rho\; <\; n\; +\; 1$ so again $\backslash alpha\; =\; \{\backslash omega^\backslash beta\; 2^\{n+1\}\; +\; \backslash rho\}\; <\; L\_\{\backslash omega\{\backslash beta\}\; +\; n\; +\; 1\}$.
We can thus view $S\_\{\backslash omega\; \backslash beta\; +\; n\; +\; 1\}$ as a concatenation of $S\_\{\backslash omega\; \backslash beta+n\}$, a comma, an opening brace, $S\_\{\backslash omega\; \backslash beta+n\}$ and
a closing brace. We assume that $\{\; \{\backslash omega^\{\backslash beta\}\; \{2^n\}\}\; +\; n\; +\; 2\}\; \backslash leq\; \backslash alpha\; <\; \{\backslash omega^\{\backslash beta\}\; 2^\{n+1\}\; +\; n\}$ as the three other cases are handled by the lemma. Then $\backslash delta$ is well-defined and is actually the index of $S[\backslash alpha]$ in the second copy of $S\_\{\backslash omega\; \backslash beta\; +\; n\}$ so $\{S[\backslash alpha]\}\; =\; S\{[\backslash delta]\}$. □
We are now ready to give a nice way to evaluate $S$ at any ordinal $\backslash alpha$:
Theorem
$S[\backslash alpha]$ can be calculated inductively as follows:
If $\backslash alpha\; =\; 0$, $S[\backslash alpha]$ is the character "∅".
If $0\; <\; \backslash alpha\; \backslash leq\; \backslash omega$ then $\backslash right\backslash rfloor\}\}\; -\; 3\}\; \backslash leq\; \backslash alpha\; \backslash leq\; \backslash right\backslash rfloor\; +\; 1\}\}\; -\; 4\}$ and $S[\backslash alpha]$ is equal to:
A comma if $\backslash alpha\; =\; \{2^\{\backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+3)\}\}\; \backslash right\backslash rfloor\}\; -\; 3\}$
An opening brace if $\backslash alpha\; =\; \{2^\{\backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+3)\}\}\; \backslash right\backslash rfloor\}\; -\; 2\}$
A closing brace if $\backslash alpha\; =\; \{2^\{\backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+3)\}\}\; \backslash right\backslash rfloor\; +\; 1\}\}\; -\; 4$
If $\backslash alpha$ is infinite, let $0\; <\; c\_1\; <\; \backslash omega$ be the coefficient
in its Cantor normal form corresponding to the smallest infinite term
and $c\_0\; <\; \backslash omega$ be finite term if there is one, or zero otherwise.
Let $k$ be the exponent corresponding to the smallest nonzero
term in the binary decomposition of $c\_1$.
Then $S[\backslash alpha]$ is equal to:
A closing brace if $c\_0\; \backslash leq\; k\; -\; 1$.
A comma if $c\_0\; =\; k$.
An opening brace if $c\_0\; =\; k\; +\; 1$.
$S[\{c\_0\; -\; \{(k+2)\}\}]$ if $c\_0\; \backslash geq\; k\; +\; 2$.
Proof:
The case $\backslash alpha\; =\; 0$ is clear. Suppose $0\; <\; \backslash alpha\; <\; \backslash omega$ and let $l\; =\; \{\backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+3)\}\}\; \backslash right\backslash rfloor\}$. By definition $2^l\; \backslash leq\; \backslash alpha\; +\; 3\; <\; 2^\{l+1\}$ so $2^l\; -\; 3\; \backslash leq\; \backslash alpha\; \backslash leq\; 2^\{l+1\}\; -\; 4$. Let’s consider the case $2^l\; -\; 1\; \backslash leq\; \backslash alpha\; \backslash leq\; 2^\{l+1\}\; -\; 5$ as the three other cases are already known from the Lemma. $S\_\{l+1\}$ is made of the concatenation of $S\_l$, a comma and $S\_l$ surrounded by braces. $\backslash delta$ is actually the index of $S[\backslash alpha]$ in the second copy of $S\_l$ so $\{S[\backslash alpha]\}\; =\; S\{[\backslash delta]\}$. The first equality is straighforward:
Let’s consider the case of an infinite $\backslash alpha$. For some $N\; \backslash geq\; 1$, $\backslash beta\_N\; >\; \backslash beta\_\{N-1\}\; >\; \backslash dots\; >\; \backslash beta\_1\; \backslash geq\; 1$ and $c\_0\; <\; \backslash omega$ and $0\; <\; c\_1,\; c\_2,\; c\_N\; <\; \backslash omega$, we can write Cantor’s Normal form as:
If $N\; \backslash geq\; 2$, then $\backslash rho$ is infinite and so $n\; =\; \backslash left\backslash lfloor\; \{\backslash log\_2(q)\}\; \backslash right\backslash rfloor$ and we are in the fouth bullet of the proposition. Moreover $q\; \backslash geq\; 2^n$ and we can write:
where $\backslash delta\; =\; \{\backslash omega^\{\backslash beta\}\; \backslash left(q-2^n\backslash right)\}\; +\; \backslash rho$ is infinite and so cancels out the $n\; +\; 2$ term. It follows that $S\{[\backslash alpha]\}\; =\; S\backslash left[\; \{\backslash omega^\{\backslash beta\}\; \backslash left(q-2^n\backslash right)\}\; +\; \backslash rho\; \backslash right]$. Essentially, we have just removed from $c\_\{N\}$ its term of highest exponent in its binary decomposition!
By repeated application of the theorem, we can remove each binary digit of the $c\_i$ for $i$ going from $N$ to $2$. When then arrive at $i\; =\; 1$:
With the notation of the proposition, we now have $\backslash beta\; =\; \backslash beta\_1$, $q\; =\; c\_1$ and $\backslash rho\; =\; c\_0$. If the binary decomposition of $c\_1$ has more than one nonzero digit then so $q$ is not a power of 2. So although $\backslash rho$ is now finite, we are still in the first case of the proposition and $\backslash delta$ remains infinite. So we can remove all but the last digit of $c\_1$ by repeated application of the proposition:
where $k$ is the exponent corresponding to the smallest nonzero term in the binary decomposition of $c\_1$.
Using the lemma, $S[\backslash alpha]$ is a comma if $k\; =\; c\_0$, an opening brace if $k\; =\; c\_0\; -\; 1$ and a closing brace if $k\; =\; c\_0\; +\; 1$.
If $k\; \backslash leq\; c\_0\; -\; 2$ then $k\; =\; \backslash left\backslash lfloor\; \{\backslash log\_2(2^k)\}\; \backslash right\backslash rfloor\; \backslash leq\; c\_0$ and writing
We have essentially decremented $k$ and we can repeat this until we reach the case $k\; =\; c\_0\; +\; 1$ for which we already said that the character is a closing brace. □
As an application of this theorem, here is a few simple exercises:
Exercise 1
$S\backslash left[2^72\; +\; 2\backslash right]$ is an empty set.
$S\backslash left[\backslash omega^72\backslash right]$ is a comma.
$S\backslash left[\backslash omega^72\; 72\; +\; 72\backslash right]$ is a closing brace.
$S\backslash left[\backslash omega^72\; 72\; +\; \backslash omega^42\; 42\; +\; 12\backslash right]$ is an opening brace.
Let $\backslash alpha$ be an ordinal. Let $c\_1\; <\; \backslash omega$ be the coefficient in its Cantor normal form corresponding to the smallest infinite term if there is one, or zero otherwise. Let $c\_0\; <\; \backslash omega$ be its finite term if there is one, or zero otherwise. Then $S[\backslash alpha]$ can be evaluated in:
$O\backslash left(\; \backslash log\_2\{(c\_0+2)\}^2\; +\; \backslash log\_2\{(c\_1+2)\}\; \backslash right)$ elementary arithmetic operations and comparisons on integers.
$O\backslash left(\; \backslash log\_2\{(c\_0+2)\}\backslash right)$ elementary operations if integers are represented in binary and leading/trailing zero counting and bit shifts are elementary operations.
Proof: First note that the “+ 2” is just to workaround for the edge cases $c\_0\; =\; 0$ or $c\_1\; =\; 0$.
For the infinite case $c\_1\; >\; 0$ we need to calculate $k$ that is performing the find first set. A naive implementation can be done in $O(\backslash log\_2\{(c\_1+2)\})$ steps by browsing the digits of $c\_1$ to find the first nonzero for example by calculating the remainder modulo increasing power of 2. Each iteration requires only $O(1)$ elementary integer operations %, * and comparisons. Then returning the result of moving to the finite case requires $O(1)$ integer operations +, − and comparisons.
For the finite case $c\_1\; =\; 0$ and $\backslash alpha\; =\; c\_0$, first notice that we only require $O\backslash left(\; \backslash log\_2\{(c\_0+2)\}\backslash right)$ recursive calls given the inequality:
The case $\backslash alpha\; =\; 0$ only requires one comparison. For the case $\backslash alpha\; >\; 0$, we need to calculate $l\; =\; \{\backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+3)\}\}\; \backslash right\backslash rfloor\}$ which is integer rounding of the binary logarithm or even just $2^l$. As above, we can provide a naive implementation by calculating the quotient modulo increasing power of 2 in $O(l)$ comparisons and elementary integer operations /, *. Then returning the result of moving to a $\backslash delta\; <\; \backslash alpha$ requires only $O(1)$ integer operations and comparisons. In total, complexity is $O\backslash left(\; \backslash log\_2\{(c\_0+2)\}^2\backslash right)$.
Finally, this can be simplified if one calculates $k$ and $l$ by a simple leading/trailing zero counting (or similar) and $2^l$ by a bit shift. □
Script based on Cantor normal form
If the coefficients of Cantor normal form of $\backslash alpha$ corresponding the smallest infinite term and finite term are $c\_1$ = $c\_0$ =
Then the character of $S$ at position $\backslash alpha$ is
Once we have an algorithm for S.charAt(α), it is easy to get an algorithm of $N$ times that complexity for S.substr(α, N) calculating the substring of length $N$ starting at position $\backslash alpha$ by repeated calls to S.charAt(α). Let’s analyze a bit more carefully how we can make this recursive and more efficient:
Corollary 2: Algorithm for S.substr(α, N)
Let $\backslash alpha$ be an ordinal and $N\; <\; \backslash omega$. Then S.substr(α, N) can be calculated as follows:
If $N\; =\; 0$ then it is the empty string.
If $\backslash alpha\; =\; 0$ and $N\; =\; 1$ then it is the character "∅".
If $0\; <\; \backslash alpha\; <\; \backslash omega$, let $l\; =\; \backslash left\backslash lfloor\; \{\backslash log\_2\{(\backslash alpha+N+2)\}\}\; \backslash right\backslash rfloor$. We have $2^l-3\; \backslash leq\; \{\backslash alpha\; +\; N\; -\; 1\}\; \backslash leq\; 2^\{l+1\}\; -\; 4$ and the result is obtained by concatenating the following strings:
If $\backslash alpha\; \backslash leq\; 2^l\; -\; 4$, the substring at offset $\backslash alpha$ and length $2^l\; -\; 3\; -\; \backslash alpha$.
If $\backslash alpha\; \backslash leq\; \{2^l\; -\; 3\}$, a comma.
If $\backslash alpha\; \backslash leq\; \{2^l\; -\; 2\}\; \backslash leq\; \{\backslash alpha\; +\; N\; -\; 1\}$, an opening brace.
If $\{\backslash alpha\; +\; N\; -\; 1\}\; =\; \{2^\{l+1\}\; -\; 4\}$, a closing brace.
If $\backslash alpha$ is infinite, let $0\; <\; c\_1\; <\; \backslash omega$ be the coefficient
in its Cantor normal form corresponding to the smallest infinite term
and $c\_0\; <\; \backslash omega$ be finite term if there is one, or zero otherwise.
Let $k$ be the exponent corresponding to the smallest nonzero
term in the binary decomposition of $c\_1$. Then the result is obtained by a concatenating the following strings:
If $c\_0\; \backslash leq\; k\; \backslash leq\; c\_0\; +\; N\; -\; 1$, a comma.
If $c\_0\; \backslash leq\; k\; +\; 1\; \backslash leq\; c\_0\; +\; N\; -\; 1$, an opening brace.
If $c\_0\; +\; N\; -\; 1\; \backslash geq\; k\; +\; 2$, the substring at offset $\backslash delta\; =\; \backslash mathrm\{max\}\{(\{0,\; \{c\_0\; -\; \{(k\; +\; 2)\}\}\})\}$ and length $c\_0\; +\; N\; -\; \{\backslash mathrm\{max\}\{(c\_0,\; k\; +\; 2)\}\}$.
Moreover, this only adds $O(N)$ compared to the complexity of evaluating to a single offset.
Proof: The algorithm is just direct application of the Theorem. For the case where $\backslash alpha\; \backslash geq\; \backslash omega$, the only change is that we add at most $N$ characters before moving to the finite case. The case $\backslash alpha\; <\; \backslash omega$ is essentially a divide-and-conquer algorithm and we have a relation of the form:
where $L\; =\; 2^l\; =\; \{\backslash Theta\{(\backslash alpha\; +\; N)\}\}$ and $f\{(L)\}$ is $O(1)$ or $O(\backslash log\_2\{L\})$ depending on available operations, but in any case $O\{(\backslash sqrt\{L\})\}$. So from the master theorem, $\{T\{(L)\}\}\; =\; \{O(L)\}\; =\; \{O(\backslash alpha+N)\}$. In general, this bound is not as good as repeating $N$ calls to S.charAt!
However, we note that if we assume that $\backslash alpha\; >\; N\; -\; 4$ then $\{\backslash alpha\; +\; 2\; +\; N\}\; <\; \{2\{(\backslash alpha+3)\}\}$ and so
We can easily discard the edge case where these start/end offsets point to a brace surrounding the right substring of the iterative step and so we get:
which means that the left substring is just empty and so the complexity is not changed compared to S.charAt. Finally, when $\backslash alpha\; \backslash leq\; N\; -\; 4$ the previous bound tells us that the steps are done in $O(N)$. □
Script for S.substr(α, N)
If the coefficients of Cantor normal form of $\backslash alpha$ corresponding the smallest infinite term and finite term are $c\_1$ = $c\_0$ =
Then the character of $S$ substring of length
$N$ =
and offset $\backslash alpha$ is