My views on NeoHaskell

My views on NeoHaskell

Recently Nick Seagull has announced a NeoHaskell project which (I believe) has generated some controversy. My first run-in with NeoHaskell was this post on cohost criticizing the NeoHaskell project and a few of my friends within the Haskell community have expressed concern about the NeoHaskell project. My gut reaction is also critical, but I wanted to do a more thorough investigation before speaking publicly against NeoHaskell so I figured I would dig into the project more first. Who knows, maybe my gut reaction is wrong? 🤷��♀�

Another reason NeoHaskell is relevant to me is that I think a lot about marketing and product management for the Haskell community, and even presented a talk on How to market Haskell mainstream programmers so I’m particularly keen to study NeoHaskell through that lens to see if he is trying to approach things in a similar way or not.

I also have credentials to burnish in this regard. I have a lot of experience with product management and technical product management for open source projects via my work on Dhall. Not only did I author the original implementation of Dhall but I singlehandedly built most of the language ecosystem (including the language standard, documentation, numerous language bindings, and the command-line tooling) and mentored others to do the same.

Anyway, with that out of the way, on to NeoHaskell:

What is NeoHaskell?

I feel like this is probably the most important question to answer because unless there is a clear statement of purpose for a project there’s nothing to judge; it’s “not even wrong� because there’s no yardstick by which to measure it and nothing to challenge.

So what is NeoHaskell?

I’ll break this into two parts: what NeoHaskell is right now and what NeoHaskell aspires to be.

Based on what I’ve gathered, right now NeoHaskell is:

• A set of user experience requirements

  … tracked as issues in this GitHub repository

• A website

  … which informally summarizes some of the headline requirements (such as Python interop and mobile support)

• An announcement post

However, it’s not clear what NeoHaskell aspires to be from studying the website, the issue tracker, or announcement:

• Is this going to be a new programming language inspired by Haskell?

  In other words, will this be a “clean room� implementation of a language which is Haskell-like?

• … or this going to be a fork of Haskell (more specifically: ghc) to add the desired features?

  In other words, will the relationship of NeoHaskell to Haskell be similar to the relationship between NeoVim and Vim? (The name seems to suggest as much)

• … or this going to be changes to the command-line Haskell tooling?

  In other words, will this be kind of like stack and promote a new suite of tools for doing Haskell development?

• … or this going to be improvements to the Haskell package ecosystem?

  In other words, will this shore up and/or revive some existing packages within the Haskell ecosystem?

Here’s what I think NeoHaskell aspires to be based on carefully reading through the website and all of the issues in the issue tracker and drawing (I believe) reasonable inferences:

NeoHaskell is not going to be a fork of ghc and is instead proposing to implement the following things:

• A new command-line tool (neo) similar in spirit to stack
  • It is proposing some new features not present in stack but it reads to me as similar to stack.
• A GHC plugin that would add:
  • new language features (none proposed so far, but it aims to be a Haskell dialect)
  • improved error messages
  • some improvements to the UX (e.g. automatic hole filling)
• An attempt to revive the work on a mobile (ARM) backend for Haskell
• An overhaul of Haskell’s standard libraries similar in spirit to foundation
• TemplateHaskell support for the cpython package for more ergonomic Python interop
• A set of documentation for the language and some parts of the ecosystem
• An event sourcing framework
  • … and a set of template applications based on that framework

And in addition to that concrete roadmap Nick Seagull is essentially proposing the following governance model for the NeoHaskell project (and possibly the broader Haskell ecosystem if NeoHaskell gains traction):

• Centralizing product management in himself as a benevolent dictator

  I don’t believe I’m exaggerating this. Here is the relevant excerpt from the announcement post, which explicitly references the BDFL model:

  I believe that in order for a product to be successful, the design process must be centralized in a single person. This person must listen to the users, the other designers, and in general must have an open mind to always cherry-pick all possible ideas in order to improve the product. I don’t believe that a product should be guided by democracy, and neither it should implement all suggestions by every user. In other words, I’ll be the one in charge of generating and listening to discussions, and prioritizing the features of the project.

  I understand that this comes with some risk, but at the same time I believe that all programming tools like Python and Ruby that are very loved by their communities are like that because of the BDFL model

• Organizing work via the NeoHaskell discord and NeoHaskell GitHub issue tracker

I feel like it should have been easier to gather this concrete information about NeoHaskell’s aspirational goals, if only so that the project is less about vibes and more a discussion on a concrete roadmap.

Alright, so now I’ll explain my general impression of this project. I’ll start with the positive feedback followed by the negative feedback and I’ll be a bit less reserved and more emotionally honest in my feedback.

Positive feedback

Welcome contributions

I’m not the kind of person who will turn down someone willing to do work to make things better as long as they don’t make things worse. A new mobile backend for Haskell sounds great! Python interop using TemplateHaskell sounds nice! Documentation? Love it!

A GHC plugin is a good approach

I think the approach of implementing this as a GHC plugin is a much better idea than forking ghc. This sidesteps the ludicrous amount of work that would be required to maintain a fork of ghc.

Moreover, implementing any Haskell dialect as a GHC plugin actually minimizes ecosystem fragmentation because (similar to an alternate Prelude) it doesn’t “leakâ€�. If one of your dependencies uses a GHC plugin for the NeoHaskell dialect then your package doesn’t have to use that same dialect (you can still build that dependency and code your package in non-Neo Haskell). cabal can handle that sort of thing transparently.

Haskell does need better product management

I think the Haskell foundation was supposed to be this (I could be wrong) but that didn’t really seem to pan out.

Either way, I think a lot of us know what good product management is and it is strikingly absent from the ecosystem.

Negative feedback

Benevolent dictator

I think it’s ridiculous that someone who hasn’t made significant contributions to the Haskell ecosystem wants to become a benevolent dictator for a project aspiring to make an outsized impact on the Haskell ecosystem. I know that this is harsh and a personal attack on Nick and I’m also mindful that there’s a real person behind the avatar. HOWEVER, when you propose to be a benevolent dictator you are inherently making things personal. A proposal to become a benevolent dictator is essentially a referendum on you as a person.¹

And it’s not just a matter of fairness or whatever. Nick’s lack of Haskell credentials directly impact his ability to actually meaningfully improve upon prior art if he doesn’t understand the current state of the art. Like, when Michael Snoyman created stack it did lead to a lot of fragmentation in the Haskell tooling but at least I felt like he was justified in his attempt because he had an impressive track record and a deep understanding of the Haskell ecosystem and toolchain.

I do not get anything remotely resembling that impression from Nick Seagull. He strikes me as a dilettante in this area and not just due to his lack of Haskell credentials but also due to some of his questionable proposed changes. This brings me to:

Unwelcome contributions

Not all contributions benefit the ecosystem². I think proposing a new neo build tool is likely to fragment the tooling in a way similar to stack. I have worked pretty extensively with all three of cabal, stack and Nix throughout my career and my intuition based on that experience is that the only improvement to the Haskell command-line experience that is viable and that will “winâ€� in the long run is one that is directly upstreamed into cabal. It’s just that nobody wants to do that because it’s not as glamorous as writing your own build tool.

Similarly, I think his proposed vision of “event source all the Haskell applicationsâ€� (including command-line scripts) is poorly thought out. I firmly subscribe to the principle of least power which says that you should use the simplest type or abstraction available that gets the job done instead of trying to shoehorn everything into the same “god typeâ€� or “god abstractionâ€�. I learned this the hard way when I tried to shoehorn everything into my pipes package and realized that it was a huge mistake, so it’s not like I’m innocent in this regard. Don’t make the same mistake I did.

And it matters that some of these proposed changes are counterproductive because if he indeed plays a role as a benevolent dictator you’re not going to get to pick and choose which changes to keep and which changes to ignore. You’re getting the whole package, like it or not.

Not good product management

I don’t believe NeoHaskell is the good product management we’re all looking for. “Haskell dialect + python interop + event sourcing + mobile backend� is not a product. It’s an odd bundle of features that don’t have a clear market or vertical or use case to constrain the design and navigate tradeoffs. The NeoHaskell roadmap comes across to me as a grab bag of unrelated features which individually sound good but that is not necessarily good product management.

To make this concrete: what is the purpose of bundling both python interop and a mobile backend into NeoHaskell’s roadmap? As far as I know there is no product vertical that requires both of those things.

The overall vibe is bad

My initial impression of NeoHaskell was that it struck me as bullshit. Carefully note that I’m not saying that Nick is a bullshitter, but if he wants to be taken seriously then he needs to rethink how he presents his ideas. Everything from the tone of the announcement post (including the irrelevant AI-generated images), the complete absence of any supporting code or mockups, and the wishy washy statement of purpose all contributed to the non-serious vibes.

Conclusion

Anyway, I don’t hate Nick and I’m pretty sure I’d get along with him great in person in other contexts. He also seems like a decently accomplished guy in other respects. However, I think nominating himself as a benevolent dictator for an ambitious ecosystem is a bit irresponsible. However, we all make mistakes and can learn from them.

And I don’t endorse NeoHaskell. I don’t think it’s any more likely to succeed than Haskell absent some better product management. “I like simple Haskell tailored to blue collar engineers� is a nice vibe but it’s not a product.

by Gabriella Gonzalez (noreply@blogger.com) at October 02, 2023 05:36 PM

Irish logarithm forward instead of backward

Yesterday I posted about the so-called “Irish logarithm”, Percy Ludgate's little algorithm for single-digit multiplication.

Hacker News user sksksfpuzhpx said:

There's a much simpler way to derive Ludgate's logarithms

and referred to Brian Coghlan's aticle “Percy Ludgate's Logarithmic indices”.

Whereas I was reverse-engineering Ludgate's tables with a sort of ad-hoc backtracking search, if you do it right you can do it it more easily with a simple greedy search.

Uh oh, I thought, I will want to write this up before I move on to the thing I planned to do next, which made it all the more likely that I never would get to the thing I had planned to do next. But Shreevatsa R. came to my rescue and wrote up the Coghlan thing at least as well as I could have myself. Definitely check it out.

Thank you, Shreevatsa!

by Mark Dominus (mjd@plover.com) at October 02, 2023 03:33 PM

Improving GHC's configuration logic and cross-compilation support with ghc-toolchain

Rodrigo worked on an internship with the GHC team at Well-Typed this summer. In this post he reports on his progress improving GHC’s configuration tooling as a step towards better cross-compiler support.

GHC, like most high-level language compilers, depends upon a set of tools like assemblers, linkers, and archivers for the production of machine code. Collectively these tools are known as a toolchain and capture a great deal of platform-dependent knowledge.

Traditionally, developers generate a ./configure script using the venerable autoconf tool, then users execute this script when they install a GHC binary distribution. The ./configure script determines the location of programs (such as the C compiler) and which options GHC will need to pass them.

While this autoconf-centric model of toolchain configuration has served GHC well, it has two key issues:

• For cross-compiling to a different platform, it would be highly valuable to users if GHC would become a runtime-retargetable compiler (like rustc and go). That is, the user should be able to download a single GHC binary distribution and use it to compile not only for their local machine, but also any other targets that GHC supports.

• The ten-thousand-line sh file that is GHC’s ./configure script has historically been challenging to maintain and test. Modifications to the ./configure script are among the most risky changes routinely made to the compiler, because it is easy to introduce a bug on some specific toolchain configuration, and infeasible to test all possible configurations in CI.

To address these issues, we are introducing ghc-toolchain, a new way to configure the toolchain for GHC, which will eventually replace the existing toolchain configuration logic in the ./configure script. Its main goal is to allow new compilation toolchains to be configured for GHC at any point in time, notably after the compiler has been installed. For example, calling ghc-toolchain --triple=x86_64-w64-mingw32 will configure a compilation toolchain on the host machine capable of producing code for an x86_64 machine running Windows using MinGW. This is an important step towards making GHC runtime-retargetable, and since ghc-toolchain is implemented in Haskell, it will be much easier to modify and test than the ./configure script.

In this post we explain in more detail how GHC interacts with the system toolchain and how ghc-toolchain facilitates our future goal of making GHC a runtime-retargetable compiler.

Compiler Toolchains

GHC cannot produce executables from Haskell programs in isolation – it requires a correctly configured toolchain to which it can delegate some responsibilities. For example, GHC’s native code generator backend is capable of generating assembly code from a Haskell program, however, producing object code from that assembly, and linking the objects into an executable, are all tasks done by the compilation toolchain, which is invoked by GHC using the flags that were configured for it.

Configuring a compiler toolchain is about locating the set of tools required for compilation, the base set of flags required to invoke each tool, and properties of these tools. For example, this might include:

• determining various characteristics of the platform (e.g. the word size).
• probing to find which tools are available (the C compiler, linker, archiver, object merging tool, etc.),
• identifying which flags GHC should pass to each of these tools,
• determining whether the tools support response files to work around command-line length limits, and
• checking for and working around bugs in the toolchain.

At the moment, when a GHC binary distribution is installed, the ./configure script will perform the above steps and store the results in a settings file. GHC will then read this file so it can correctly invoke the toolchain programs when compiling Haskell executables.

To cross-compile a Haskell program, a user must build GHC from source as a cross-compiler (see the GHC wiki). This requires configuring a cross-compilation toolchain, that is, a toolchain that runs on the machine compiling the Haskell program but that produces executables to run on a different system. It is currently a rather involved process.

The runtime-retargetable future of GHC

A key long-term goal of this work is to allow GHC to become runtime-retargetable. This means being able to call ghc --target=aarch64-apple-darwin and have GHC output code for an AArch64 machine, or call ghc --target=javascript-ghcjs to generate Javascript code, regardless of the platform ghc is being invoked on.

Crucially, this requires the configuration step to be repeated at a later point, rather than only when the GHC binary distribution is installed. Once GHC is fully runtime-retargetable, this will allow you to use multiple different toolchains, potentially targeting different platforms, with the same installed compiler.

• At the simplest level, you might just have two different toolchains for your host platform (for example, a gcc-based toolchain and a clang-based toolchain), or you might just configure a toolchain which uses the new mold linker rather than ld.gold.

• In a more complex scenario, you may have a normal compiler toolchain as well as several different cross-compiler toolchains. For example, a toolchain which produces Javascript, a toolchain which produces WebAssembly, a toolchain which produces AArch64 object code and so on.

The idea is that the brand new ghc-toolchain will be called once to configure the toolchain that GHC will use when compiling for a target, then ghc --target=<triple> can be called as many times as needed. For example, if you have an x86 Linux machine and wish to produce code for AArch64 devices, the workflow could look something like:

# Configure the aarch64-apple-darwin target first
# (We only need to do this once!)
ghc-toolchain --triple=aarch64-apple-darwin --cc-opt="-I/some/include/dir" --cc-linker-opt="-L/some/library/dir"

# Now we can target aarch64-apple-darwin (as many times as we'd like!)
ghc --target=aarch64-apple-darwin -o MyAwesomeTool MyAwesomeTool.hs
ghc --target=aarch64-apple-darwin -o CoolProgram CoolProgram.hs

Introducing ghc-toolchain

ghc-toolchain is a standalone tool for configuring a toolchain. It receives as input a target triplet (e.g. x86_64-deb10-linux) and user options, discovers the configuration, and outputs a “target description” (.target file) containing the configured toolchain.

At the moment, .target files generated by ghc-toolchain can be used by GHC’s build system (Hadrian) by invoking ./configure with --enable-ghc-toolchain. Otherwise, Hadrian reads the configuration from a .target file generated by ./configure itself.

In the future, ghc-toolchain will be shipped in binary distributions to allow new toolchains to be added after the compiler is installed (generating new .target files). GHC will then be able to choose the .target file for the particular target requested by the user.

From a developer standpoint, ghc-toolchain being written in Haskell makes it easier to modify in future, especially when compared to the notoriously difficult to write and debug ./configure scripts.

Migration to ghc-toolchain

We are migrating to ghc-toolchain in a staged manner, since toolchain configuration logic is amongst the most sensitive things to change in the compiler. We want to ensure that the configuration logic in ghc-toolchain is correct and agrees with the logic in ./configure. Therefore, in GHC 9.10 ghc-toolchain will be shipped and validated but not enabled by default.

To validate ghc-toolchain, GHC will generate .target files with both ./configure and ghc-toolchain and compare the outputs against each other, emitting a warning if they differ. This means we will be able to catch mistakes in ghc-toolchain (and in ./configure too!) before we make ghc-toolchain the default method for configuring toolchains in a subsequent release. This mechanism has already identified plenty of issues to resolve.

Future work

Despite ghc-toolchain bringing us closer to a runtime-retargetable GHC, there is still much work left to be done (see #11470). The next step is to instruct GHC to choose between multiple available .target files at runtime, instead of reading the usual settings file (tracked in #23682).

Beyond that, however, there are many open questions still to resolve:

• How will the runtime system, and core libraries such as base, be provided for the multiple selected targets?
• How will this fit into ghcup’s installation story?
• How will cabal handle multiple targets?

At the moment, binary distributions include the RTS/libraries already compiled for a single target. Instead, we are likely to need some mechanism for users to recompile the RTS/libraries when they configure a new target, or to download ready-built versions from upstream.

Moreover, accommodating TemplateHaskell under runtime retargetability is particularly nontrivial, and needs more design work.

Conclusion

ghc-toolchain is a new tool for configuring toolchains and targets. It improves on GHC’s existing ./configure-based configuration workflow by allowing multiple targets’ toolchains to be configured at any time, and by making maintenance and future updates to the toolchain configuration logic much easier. However, toolchain configuration is a challenging part of the compiler, so we’re being conservative in migrating to ghc-toolchain, and carefully validating it before making it the default.

Moreover, ghc-toolchain is an important step towards making a runtime-retargetable GHC a reality, though there is still much work left to do. We are grateful to all the GHC developers involved in working towards runtime-retargetability.

Well-Typed is able to work on GHC, HLS, Cabal and other core Haskell infrastructure thanks to funding from various sponsors. If your company might be able to contribute to this work, sponsor maintenance efforts, or fund the implementation of other features, please read about how you can help or get in touch.

by rodrigo at October 02, 2023 12:00 AM

The Irish logarithm

The Wikipedia article on “Irish logarithm” presents this rather weird little algorithm, invented by Percy Ludgate. Suppose you want to multiply and , where both are single-digit numbers .

Normally you would just look it up on a multiplication table, but please bear with me for a bit.

To use Ludgate's algorithm you need a different little table:

$$ \begin{array}{rl} T_1 = & \begin{array}{cccccccccc} \tiny\color{gray}{0} & \tiny\color{gray}{1} & \tiny\color{gray}{2} & \tiny\color{gray}{3} & \tiny\color{gray}{4} & \tiny\color{gray}{5} & \tiny\color{gray}{6} & \tiny\color{gray}{7} & \tiny\color{gray}{8} & \tiny\color{gray}{9} \\ 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 & 14 \\ \end{array} \end{array} $$

and a different bigger one:

$$ \begin{array}{rl} T_2 = & % \left( \begin{array}{rrrrrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, & 3, & 6, & 12, \\ {\tiny\color{gray}{10}} & 24, & 48, & 0, & 0, & 9, & 18, & 36, & 72, & 0, & 0, \\ {\tiny\color{gray}{20}} & 0, & 27, & 54, & 5, & 10, & 20, & 40, & 0, & 81, & 0, \\ {\tiny\color{gray}{30}} & 15, & 30, & 0, & 7, & 14, & 28, & 56, & 45, & 0, & 0, \\ {\tiny\color{gray}{40}} & 21, & 42, & 0, & 0, & 0, & 0, & 25, & 63, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 35, & 0, & 0, & 0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, & 0, & 0, & 49\hphantom{,} \end{array} % \right) \end{array} $$

I've formatted in rows for easier reading, but it's really just a zero-indexed list of numbers. So for example is .

The tiny gray numbers in the margin are not part of the table, they are counting the elements so that it is easy to find element .

Ludgate's algorithm is simply:

$$ ab = T_2(T_1(a) + T_1(b)) $$

Let's see an example. Say we want to multiply . We first look up and in , and get and , which we add, getting . Then is , which is the correct answer.

This isn't useful for paper-and-pencil calculation, because it only works for products up to , and an ordinary multiplication table is easier to use and remember. But Ludgate invented this for use in a mechanical computing engine, for which it is much better-suited.

The table lookups are mechanically very easy. They are simple one-dimensional lookups: to find you just look at entry in the table, which can be implemented as a series of ten metal rods of different lengths, or something like that. Looking things up in a multiplication table is harder because it is two-dimensional.

The single addition in Ludgate's algorithm can also be performed mechanically: to add and , you have some thingy that slides up by units, and then by more, and then wherever it ends up is used to index into to get the answer. The table doesn't have to be calculated on the fly, it can be made up ahead of time, and machined from brass or something, and incorporated directly into the machine. (It's tempting to say “hardcoded”.)

The tables look a little uncouth at first but it is not hard to figure out what is going on. First off, is the inverse of in the sense that $$T_2(T_1(n)) = n\tag{$\color{darkgreen}{\spadesuit}$}$$

whenever is in range — that is when .

is more complex. We must construct it so that

$$T_2(T_1(a) + T_1(b)) = ab.\tag{$\color{purple}{\clubsuit}$}$$

for all and of interest, which means that .

If you look over the table you should see that the entry is often followed by . That is, , at least some of the time. In fact, this is true in all the cases we care about, where for some single digits .

The second row could just as well have started with , but Ludgate doesn't need the entries, so he made them zero, which really means “I don't care”. This will be important later.

The algorithm says that if we want to compute , we should compute $$ \begin{align} 2n & = T_2(T_1(2) + T_1(n)) && \text{Because $\color{purple}{\clubsuit}$} \\ & = T_2(1 + T_1(n)) \\ & = 2T_2(T_1(n)) && \text{Because moving one space right doubles the value}\\ & = 2n && \text{Because $\color{darkgreen}{\spadesuit}$} \end{align} $$

when .

I formatted in rows of because that makes it easy to look up examples like , and because that's how Wikipedia did it. But this is very misleading, and not just because it makes appear to be a table when it's really a vector. is actually more like a compressed version of a table.

Let's reformat the table so that the rows have length instead of :

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 5, & 10, & 20, & 40, & 0, \\ {\tiny\color{gray}{28}} & 81, & 0, & 15, & 30, & 0, & 7, & 14, \\ {\tiny\color{gray}{35}} & 28, & 56, & 45, & 0, & 0, & 21, & 42, \\ {\tiny\color{gray}{42}} & 0, & 0, & 0, & 0, & 25, & 63, & 0, \\ {\tiny\color{gray}{49}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{56}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{63}} & 0, & 0, & 0, & 49 \\ \end{array} $$

We have already seen that moving one column right usually multiplies the entry by . Similarly, moving down by one row is seen to triple the value — not always, but in all the cases of interest. Since the rows have length , moving down one row from gets you to , and this is why : to compute , one does:

$$ \begin{align} 3n & = T_2(T_1(3) + T_1(n)) && \text{Because $\color{purple}{\clubsuit}$} \\ & = T_2(7 + T_1(n)) \\ & = 3T_2(T_1(n)) && \text{Because moving down triples the value}\\ & = 3n && \text{Because $\color{darkgreen}{\spadesuit}$} \end{align} $$

Now here is where it gets clever. It would be straightforward easy to build as a stack of tables, with each layer in the stack having entries quintuple the layer above, like this:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, & 0, & 0, & 0, & 0, & 0, & 0, \\ \\ {\tiny\color{gray}{35}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{42}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{49}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{56}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{63}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ \\ {\tiny\color{gray}{70}} & 25, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{77}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{84}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{91}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{98}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ \end{array} $$

This works, if we make the correct offset, which is . But it wastes space, and the larger is, the more complicated and expensive is the brass thingy that encodes it. The last six entries of the each layer in the stack are don't-cares, so we can just omit them:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\tiny\color{gray}{58}} & 25, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{65}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{72}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{79}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{86}} & 0\hphantom{,} \\ \end{array} $$

And to compensate we make instead of : you now move down one layer in the stack by skipping entries forward, instead of .

The table is still missing all the multiples of , but we can repeat the process. The previous version of can now be thought of as a table, and we can stack another table below it, with all the entries in the new layer being times the original one:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\tiny\color{gray}{58}} & 25, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{65}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{72}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{79}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{86}} & 0, \\ \\ \hline \\ {\tiny\color{gray}{87}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color{gray}{94}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{101}} & 63, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{108}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{115}} & 0, \\ \\ {\tiny\color{gray}{116}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{123}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{130}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{137}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{144}} & 0, \\ \\ {\tiny\color{gray}{145}} & 0, & 0, & 0, & 0, & 0, & 0, & \ldots \\ \\ \hline \\ {\tiny\color{gray}{174}} & 49\hphantom{,} \\ \end{array} $$

Each layer in the stack has entries, so we could take and it would work, but the last entries in every layer are zero, so we can discard those and reduce the layers to entries each.

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{43}} & 45, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{50}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{57}} & 0, \\ \\ {\tiny\color{gray}{58}} & 25, \\ \\ \hline \\ {\tiny\color{gray}{59}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color{gray}{66}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{73}} & 63, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{80}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{87}} & 0, \\ \\ {\tiny\color{gray}{88}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{95}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{102}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{109}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{116}} & 0, \\ \\ {\tiny\color{gray}{117}} & 0, \\ \\ \hline \\ {\tiny\color{gray}{118}} & 49\hphantom{,} \\ \end{array} $$

Doing this has reduced the layers from to elements each, but Ludgate has another trick up his sleeve. The last few numbers in the top layer are and a lot of zeroes. If he could somehow finesse and , he could trim the top two layers all the way back to only 38 entries each:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 80, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, \\ \\ \hline \\ {\tiny\color{gray}{38}} & 7, & 14, & 28, & 56, & 0, & 0, & 0, \\ {\tiny\color{gray}{45}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{52}} & 63, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{59}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{66}} & 0, \\ \\ {\tiny\color{gray}{67}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{74}} & 0, & 0, \\ \hline \\ {\tiny\color{gray}{76}} & 49\hphantom{,} \\ \end{array} $$

We're now missing and we need to put it back. Fortunately the place we want to put it is , and that slot contains a zero anyway. And similarly we want to put at position , also empty:

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{28}} & 81, \\ \\ {\tiny\color{gray}{29}} & 5, & 10, & 20, & 40, & 0, & 0, & 0, \\ {\tiny\color{gray}{36}} & 15, & 30, \\ \\ \hline \\ {\tiny\color{gray}{38}} & 7, & 14, & 28, & 56, & 0, & \color{purple}{45}, & 0, \\ {\tiny\color{gray}{45}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{52}} & 63, & 0, & 0, & 0, & 0, & 0, & \color{purple}{25}, \\ {\tiny\color{gray}{59}} & 0, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{66}} & 0, \\ \\ {\tiny\color{gray}{67}} & 35, & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{74}} & 0, & 0, \\ \\ \hline \\ {\tiny\color{gray}{76}} & 49\hphantom{,} \\ \end{array} $$

The arithmetic pattern is no longer as obvious, but property still holds

We're not done yet! The table still has a lot of zeroes we can squeeze out. If we change from to , the group will slide backward to just after the , and the will move to the row below that.

We will also have to move the other multiples of . The itself moved back by six entries, and so did everything after that in the table, including the (from position to ) and the (from position to ) so those are still in the right places. Note that this means that has moved from position to position , so we now have .

But the is giving us trouble. It needed to move back twice as far as the others, from to , and unfortunately it now collides with which is currently at position .

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & \color{purple}{5}, & \color{purple}{10}, & \color{purple}{20}, & \color{purple}{40}, & 0, \\ {\tiny\color{gray}{28}} & 81, & 0, & \color{purple}{15} & \color{purple}{30}, \\ \\ \hline \\ {\tiny\color{gray}{32}} & 7, & 14, & 28, & 56, & 0, & \color{darkgreen}{45}, & 0, \\ {\tiny\color{gray}{39}} & 21, & 42, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{46}} & {63\atop\color{darkred}{¿25?}} & 0, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{53}} & 0, & 0, & \color{darkgreen}{35}, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, \\ \\ \hline \\ {\tiny\color{gray}{64}} & 49\hphantom{,} \\ \end{array} $$

We need another tweak to fix . is currently at position . We can't move any farther back to the left without causing more collisions. But we can move it forward, and if we move it forward by one space, the will move up one space also and the collision with will be solved. So we insert a zero between and , which moves up from position to :

$$ \begin{array}{rrrrrrrr} {\tiny\color{gray}{0}} & 1, & 2, & 4, & 8, & 16, & 32, & 64, \\ {\tiny\color{gray}{7}} & 3, & 6, & 12, & 24, & 48, & 0, & 0, \\ {\tiny\color{gray}{14}} & 9, & 18, & 36, & 72, & 0, & 0, & 0, \\ {\tiny\color{gray}{21}} & 27, & 54, & 5, & 10, & 20, & 40, & 0, \\ {\tiny\color{gray}{28}} & 81, & 0, & 15 & 30, \\ \\ \hline \\ {\tiny\color{gray}{32}} & \color{purple}{0}, & \color{darkgreen}{7}, & \color{darkgreen}{14}, & \color{darkgreen}{28}, & \color{darkgreen}{56}, & 45, & 0, \\ {\tiny\color{gray}{39}} & 0, & \color{darkgreen}{21}, & \color{darkgreen}{42}, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{46}} & 25,& \color{darkgreen}{63}, & 0, & 0, & 0, & 0, & 0, \\ {\tiny\color{gray}{53}} & 0, & 0, & 0, & \color{darkgreen}{35}, & 0, & 0, & 0, \\ {\tiny\color{gray}{60}} & 0, & 0, & 0, & 0, \\ \\ \hline \\ {\tiny\color{gray}{64}} & \color{purple}{0}, & \color{purple}{0}, & \color{darkgreen}{49}\hphantom{,} \\ \end{array} $$

All the other multiples of moved up by one space, but not the non-multiples and . Also had to move up by two, but that's no problem at all, since it was at the end of the table and has all the space it needs.

And now we are done! This is exactly Ludgate's table, which has the property that

$$T_2(p + 7q + 23r + 33s) = 2^p3^q5^r7^s$$

whenever for some . Moving right by one space multiplies the entry by , at least for the entries we care about. Moving right by seven spaces multiplies the entry by . To multiply by or we move right by or or by , respectively.

These are exactly the values in the table:

$$\begin{align} T_1(2) & = 1\\ T_1(3) & = 7\\ T_1(5) & = 23\\ T_1(7) & = 33 \end{align}$$

The rest of the table can be obtained by remembering , that , so for example because . Or we can get by multiplication, using : multiplying by is the same as multiplying by and then by , which means you move right by and then by , for a total of . Here's again for reference:

$$ \begin{array}{rl} T_1 = & \begin{array}{cccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 50 & 0 & 1 & 7 & 2 & 23 & 8 & 33 & 3 & 14 \\ \end{array} \end{array} $$

(Actually I left out a detail: . Ludgate wants for all . So we need for each in . is the smallest value that works. This is rather painful, because it means that the -item table aboveis not sufficient. Ludgate has to extend all the way out to items in order to handle the seemingly trivial case of . But the last 35 entries are all zeroes, so the the brass widget probably doesn't have to be too much more complicated.)

Wasn't that fun? A sort of mathematical engineering or a kind that has not been really useful for at least fifty years.

But actually that was not what I planned to write about! (Did you guess that was coming?) I thought I was going to write this bit as a brief introduction to something else, but the brief introduction turned out to be 2500 words and a dozen complicated tables.

We can only hope that part 2 is forthcoming. I promise nothing.

[ Update 20231002: Rather than the ad-hoc backtracking approach I described here, one can construct and in a simpler and more direct way. Shreevatsa R. explains. ]

by Mark Dominus (mjd@plover.com) at October 01, 2023 08:30 AM

How I use Emacs

I've recently written two posts about my attempts to use a slimmed down Emacs setup for some very specific use cases. I'be put both posts on Reddit, here and here, and in both cases the majority of comments have been telling me that I should use emacsclient. I know they have good intentions – they want to share insight they've gained and benefit from on a daily basis. However, no matter how many Emacs devotees point out the benefits of emacsclient I'm not about to start using it. This post is an attempt to answer why that is.

Up front I want to clarify a few things:

1. Yes, I know how to use emacsclient, and
2. yes, I know it is a good way to, in a way, improve Emacs startup time,¹ and
3. yes, I know how to turn on server-mode in Emacs, and finally
4. yes, I know how to run Emacs using a user unit for SystemD.

With that out of the way, here are the two ways I use Emacs

1. As my starting point for work, i.e. writing code, keeping notes, tracking time, and writing my daily work journal.
2. As my editor of ephemeral files.²

The next two sections explain more about these two distinct ways I use Emacs

As my starting point for work

Number of packages	162
Init time (emacs-init-time)	1.883483s
Config size (by du -bch)	68K

Much of what I do on a daily basis starts in Emacs. I typically have one instance of Emacs open and I always keep it on the second virtual desktop. I always run it in the GUI. When I write code I start with opening a new tab, then I open a dired buffer in the project's folder (by using consult-projectile). When I need a terminal I open it from Emacs using on of terminal-here-project-launch or terminal-here. Occasionally I open a shell prompt inside Emacs using shell-pop.

Back when I used Vim as my main editor I always started a terminal first and then opened files from there. Since switching to Emacs I've completely stopped doing that. Over the last 8 or so years of Emacs usage there's only been a handful of times when I've wanted to open a file from the terminal and I've run M-x server-start and used emacsclient. The last time was more than a year ago.

As I typically keep exactly one Emacs open, and I start it soon after logging in, I'm not too concerned with startup time. I think under 2s is more than fast enough given the functionality I have in my setup.

This setup I use for taking notes and writing my daily work journal, as well as reading email, and programming in a half-dozen languages. I have a large-ish set of keybindings that I've set up using general.el, inspired by Spacemacs at first but by now it's started to gain its own character.

As my editor of ephemeral files ($EDITOR)

Number of packages	22
Init time (emacs-init-time)	0.209298s
Config size (by du -bch)	6.7K

Ephemeral files are files I tend to edit for less than 30 seconds, maybe a minute at most. There are three main use cases for ephemeral files:

1. Searching the scrollback buffer in zellij, and copying bits to the clipboard for various uses.
2. Editing files when running git from the command line. It's not something I do very often, but it happens.
3. Editing shell commands. When they get a little too large to handle conveniently using ZSH directly I invoke edit-command-line.

For a few reasons I decided to make a second, completely separate configuration just to handle ephemeral files.

• It will only be used in a terminal.
• I want to be able to have some special keybindings that suit a specific use, e.g. for the scrollback buffer I've bound `SPC Y` to copy the selected text to the clipboard and then exit Emacs. It's a thing that I use all the time with the scrollback buffer, but never otherwise.
• I have no need, nor any desire, to switch from editing a commit message, or searching a scrollback buffer, to reading email or editing an org-mode file. The complete separation is a feature.

With a startup time of less than a quarter of a second it is well within the acceptable, and there is absolutely no need to use emacsclient just to speed things up. Given my desire for separation, I wouldn't want to use my main Emacs instance as a server and edit ephemeral files anyway.

Conclusion

I've found a setup that seems to work really well and tick all the requirements I have when it comes to separation between use cases and ability to have custom keybindings for them. Also, Emacs is starting up very fast with my slimmed down configuration. If starting Emacs with the slimmed configuration starts taking too long I'm more likely to go back to using Neovim than complicate things with emacsclient.

So no, I am not going to start using emacsclient any time soon.

Footnotes:

¹

I write "in a way" as it actually does nothing for Emacs startup time, it just shifts it to a point in time so you don't have to sit and wait for it to start.

²

I used to use Neovim, without any config, for most of this until recently.

Tags: emacs

October 01, 2023 05:13 AM

Using rsync for backups

Blimey, almost exactly a year since my last post. I guess that’s what happens when you have a full-time job at a start-up.

I’ve run my own servers for 15 years or so. Regardless of the technologies used, servers have mutable state, and that needs backing up, ideally regularly. Whenever I have to do a lot of sysadmin work, e.g. major OS upgrades, or changing hosting provider, I always look at what backup services are provided, but they’re never super great. Even if they are offsite, accessing them can be tricky, and it seems unwise to trust that they would be available if the hosting company goes under. So I’ve basically just winged it, for roughly 15 years. And it’s been fine.

A few stories in the news recently, and having a spare weekend, made me consider whether maybe I should finally try to improve this situation. I have a machine here at home which would be a suitable backup destination. What follows here is more or less what I’ve done. From a security point-of-view, if anyone gets into any of my servers, or my home machines, it’s game-over, so provided nothing I’ve done here weakens the security of any of those machines, then that’s good enough for me.

Creating a backup needs to occur as root on the servers: it needs to access all sorts of files and directories all over the machine, regardless of their user. The question to answer is: should the backup be initiated on the backup machine, and pull data from the server; or should it be initiated on the server, and push data to the backup machine. I don’t want to add setuid binaries to the servers, and I don’t want to allow root to log-in via ssh on the servers. So really that means the backup must be initiated on the server, and push data out.

I have WireGuard connections between the backup machine and my servers, so connectivity is simple: there’s nothing fancy to do to get the servers to be able to connect to my backup machine.

So, initial setup:

1. On the backup machine, create a new user, backup.
2. Make sure root on the server has an ssh key-pair (ssh-keygen -t ed25519 etc).
3. Make sure the public key side of that is in the authorized_keys for the backup user on the backup machine.

Authorized keys

A while ago, I learnt that you can put a lot of extra stuff in ~/.ssh/authorized_keys (man sshd). So for the backup user on the backup machine, the ~/.ssh/authorized_keys file looks rather like this:

command="/home/backup/bin/checkssh.sh",no-port-forwarding,no-X11-forwarding,no-agent-forwarding,no-pty ssh-ed25519 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA comment

This ensures that the server cannot request various network forwarding, nor a terminal. Yes, earlier I said I’m not overly concerned with security provided I don’t make things worse, so these restrictions are something of a belt-and-braces approach. At the end of the day, if the server is compromised, then there’s probably nothing I can do to guarantee the integrity of the backups either. Now because I’m going to be using rsync, I want to stop the server from being able to overwrite ~backup/.ssh/authorized_keys, as that would also be bad. So on the backup machine:

chown -R root:backup ~backup/.ssh
chmod u=rx,g=rx,o= ~backup/.ssh
chmod u=r,g=r,o= ~backup/.ssh/authorized_keys

But, going back to the authorized_keys line, what’s that command="/home/backup/bin/checkssh.sh" bit? Well, that file started out as this:

#!/bin/bash
if [ -n "$SSH_ORIGINAL_COMMAND" ]; then
    if [[ "$SSH_ORIGINAL_COMMAND" =~ ^rsync\  ]]; then
        echo "`/bin/date`: $SSH_ORIGINAL_COMMAND" >> $HOME/ssh-command-log
        exec $SSH_ORIGINAL_COMMAND
    else
        echo "`/bin/date`: DENIED $SSH_ORIGINAL_COMMAND" >> $HOME/ssh-command-log
    fi
fi

As the man-page says, command="command" specifies that the command is executed whenever this key is used for authentication. And also, the command originally supplied by the client is available in the SSH_ORIGINAL_COMMAND environment variable. So, this script is always run whenever the key is used for authentication, and we can check that the original command supplied is rsync. That’s a command that the server is requesting be run on the backup machine. I.e. it’s a binary under the control of the backup machine, it needs to be in the PATH etc.

With all of this in place, from the server:

• trying to do a plain ssh backup@backup.wireguard.local should fail (due to no terminal being allowed).
• doing something like ssh backup@backup.wireguard.local ls should fail silently because ls is not rsync (though we should have an entry in the ~backup/ssh-command-log file now saying DENIED ls).
• but ssh backup@backup.wireguard.local rsync -h should work - you should get the help text from rsync back.

Again, I want to make sure rsync can’t overwrite the checkssh.sh script, so:

chown -R root:backup ~backup/bin
chmod u=rx,g=rx,o= ~backup/bin
chmod u=r,g=rx,o= ~backup/bin/checkssh.sh

Running rsync

With all that done, from the server I should be able to do:

rsync -az --stats /important/data/ backup@backup.wireguard.local:/home/backup/server/important/data/

It does work. However, because on the backup machine, rsync isn’t running as root (it’s running as our backup user), all the ownership data of all the files and directories gets lost. This is rubbish. I want to keep using rsync, because of its ability to do incremental backups and general efficiency. But I don’t want to lose file ownership or permissions. It’s just data after all - it can’t be that hard to get it kept! The problem is that rsync is using the normal file-system on the backup machine, and its ability to set arbitrary owners and groups is limited as a consequence of running as the backup user.

So I started thinking about can I get rsync to write into a loop-back device? Something where the host OS isn’t going to interfere? After a bit of searching, it turns out loop-back is wrong, but a user namespace is right.

Namespaces, and unshare

These days, because of the rise and rise of containers, Linux supports a lot of different namespaces. E.g. from within one pid namespace, you can’t see the processes of another pid namespace. Similarly, the users and groups of one user namespace are isolated from the users and groups of a different user namespace. As a normal, unprivileged user, I can create (and enter) a new user namespace. I can even be root in that new user namespace! Thankfully, the root in this new namespace is very different to the root in the actual host, so I can’t do terrifying damage. But it is enough to be able to set arbitrary users, groups and permissions on files that I create within this namespace.

Let’s play around with this a bit.

backup@~/> touch foo
backup@~/> ls -l foo
-rw------- 1 backup backup 0 Sep 30 10:16 foo
backup@~/> unshare --user --map-auto --map-root-user
root@~/> ls -l foo
-rw------- 1 root root 0 Sep 30 10:16 foo
root@~/> touch bar
root@~/> ls -l bar
-rw------- 1 root root 0 Sep 30 10:17 foo
root@~/> ls -l /root
ls: cannot open directory '/root': Permission denied
root@~/> exit
backup@~/> ls -l foo bar
-rw------- 1 backup backup 0 Sep 30 10:16 foo
-rw------- 1 backup backup 0 Sep 30 10:17 bar

So, I created a file as the simple backup user. I used the unshare command to create and enter a new user namespace, and I became root within it. Files that I previously owned were still owned by me; but it seems like I am root! If I create new files as root, then when I exit the namespace, they’re owned by the normal backup user. Thankfully, even as this new root, it looks like I can’t access things that are restricted to the real host root, like /root!

Do I gain any new super-powers as this new root?

backup@~/> ls -l foo
-rw------- 1 backup backup 0 Sep 30 10:16 foo
backup@~/> chown 1111 foo
chown: changing ownership of 'foo': Operation not permitted
backup@~/> unshare --user --map-auto --map-root-user
root@~/> ls -l foo
-rw------- 1 root root 0 Sep 30 10:16 foo
root@~/> chown 1111 foo
root@~/> ls -l foo
-rw------- 1 1111 root 0 Sep 30 10:16 foo
root@~/> exit
backup@~/> ls -l foo
-rw------- 1 297718 backup 0 Sep 30 10:16 foo

Woah, yes I do! So the numeric 1111 user-id inside the namespace gets mapped to some other user-id outside of the namespace (you can configure this: see the man-pages for subuid and subgid). But yes, as root inside my new namespace, I have permission to use arbitrary user-ids!

If I go back in, it’s still all good – the mapping is stable and persistent:

backup@~/> ls -l foo
-rw------- 1 297718 backup 0 Sep 30 10:16 foo
backup@~/> unshare --user --map-auto --map-root-user
root@~/> ls -l foo
-rw------- 1 1111 root 0 Sep 30 10:16 foo
root@~/> exit

This is exactly what I need then. I just need to edit that checkssh.sh script so that the rsync command is run within its own user namespace:

#!/bin/bash
if [ -n "$SSH_ORIGINAL_COMMAND" ]; then
    if [[ "$SSH_ORIGINAL_COMMAND" =~ ^rsync\  ]]; then
        echo "`/bin/date`: $SSH_ORIGINAL_COMMAND" >> $HOME/ssh-command-log
        exec unshare --user --map-auto --map-root-user $SSH_ORIGINAL_COMMAND
    else
        echo "`/bin/date`: DENIED $SSH_ORIGINAL_COMMAND" >> $HOME/ssh-command-log
    fi
fi

So now, from the server, the full rsync command looks like:

rsync -az --stats --numeric-ids --delete --chmod=o= \
   -M --log-file="/home/backup/rsync-$(date --rfc-3339=ns | sed -e 's/ /_/g').log" \
   /important/data/ backup@backup.wireguard.local:/home/backup/server/important/data/

A few other options have appeared here; the man-page for rsync is your best guide, but in brief:

• --delete: if a file exists on the backup machine that doesn’t on the server then delete it. This means that the backup should be a snapshot of the server (more or less).
• --chmod=o=: no files on the backup machine should be accessible in any way to other. Yes, this is throwing away a little of the data I’ve just worked hard to preserve. But still, I generally don’t want any of these files globally accessible.
• -M --log-file="/home/backup/rsync-$(date --rfc-3339=ns | sed -e 's/ /_/g').log" This creates a log file on the backup machine of what it did. Could be handy one day. Doesn’t exactly hurt.

All done: using good old rsync for its fairly efficient incremental backups, with the reasonably new namespace capabilities and unshare, to ensure ownership and permissions are not lost, without having to allow root-logins anywhere.

September 30, 2023 04:01 PM

Using Emacs as $EDITOR

Continuing on from my experiment with using Emacs as for scrollback in my terminal multiplexer I thought I'd try to use it as my $EDITOR as well.

The two main cases where I use $EDITOR is

1. The occasional use of git on the command line, rebasing or writing a commit message, and
2. Use of ZSH's edit-command-line functionality.

To make sure Emacs is starting up quickly enough I'm using the same small setup I created for the scrollback editing, so I'm now setting EDITOR like this

export EDITOR="emacs -nw --init-directory ~/.se.d"

Now that I want to use the same setup for editing I can't really jump into view-mode every time Emacs starts so I have to be a bit more clever. The following bit won't do

(add-hook 'find-file-hook #'view-mode)

I need to somehow find out what starts Emacs and then only modify the hook when needed. Unfortunately I haven't found anything that reveals that Emacs is started by zellij. Creating a separate little script that zellij uses would be an option, of course, but for now I've opted to make it the default and instead refrain from adding the hook in the other two use cases.

ZSH doesn't make it easy to find out that it's edit-command-line either, but as I've observed that the command line sometimes doesn't look right after leaving the editor I wanted to call redisplay to fix it up. That means I need to have a function anyway, so using an environment variable becomes an easy way to check if Emacs is being used to edit the command line.

function se-edit-command-line() {
    export SE_SKIP_VIEW=y
    zle edit-command-line
    unset SE_SKIP_VIEW
    zle redisplay
}
zle -N se-edit-command-line

bindkey -M vicmd '^V' se-edit-command-line
bindkey -M viins '^V' se-edit-command-line

Unfortunately is seems zle edit-command-line doesn't pass on non-exported environment variables, hence the explicit export and unset.

When git starts an editor it sets a few environment variables so it was easy to just pick one that is set in both cases I care about. I picked GIT_EXEC_PATH.

With these things in place I changed the slim setup to only add the hook when neither of the environment variables are present

(unless (or (getenv "SE_SKIP_VIEW")
            (getenv "GIT_EXEC_PATH"))
  (add-hook 'find-file-hook #'view-mode))

Hopefully this works out well enough that I won't feel a need to go back to using Neovim as my $EDITOR.

Tags: emacs zsh

September 30, 2023 01:24 PM

Implementing kind inference

In previous articles we talked about how to write an implementation of a type inference algorithm. One that can infer the type of complex expressions without type annotation and can provide a validation layer on top of our code for no effort on the user's part.

What we talked about was for validating expressions and expression definitions. But what about type definitions? How can we help the user catch errors when the types they define are inconsistent or don't make sense?

We want to be able to catch errors such as:

Tree a =
  | Node a Tree Tree
    -- ^ should be: Node a (Tree a) (Tree a)

And:

Rec f a =
  | Rec f (f a)
    -- ^ f is used both as a saturated type and a type that takes a parameter

And more, while still allowing the user to define complex types without annotation, such as:

Cofree f a =
  | Cofree a (f (Cofree f a))

As we'll soon see, we can use the exact same unification-based constraint solving approach to type inference we covered in this article to infer the type of a type, or as we call them in the Haskell world, the kind of a type.

Getting started

�If you prefer to skip the explanations and jump straight to the code, click here.

In this article we will implement a kind inference engine in Haskell for a simple type system. We'll start by adding the relevant imports and language definitions for our Haskell module:

#!/usr/bin/env cabal
{- cabal:
build-depends: base, mtl, containers, uniplate
ghc-options: -Wall
-}

This first part lets us run this file as a script if we have ghc and cabal installed. Just chmod +x kinds.hs and run it.

We will use the GHC2021 set of extensions and LambdaCase, as well as a few additional modules that will come into play later.

-- | An example of a kind inference for data types using
-- unification-based constraint solving.
--
-- See the blog post:
-- <https://gilmi.me/blog/post/2023/09/30/kind-inference>

{-# Language GHC2021 #-}
{-# Language LambdaCase #-}

import Data.Data (Data)
import GHC.Generics (Generic)
import Data.Tuple (swap)
import Data.Maybe (listToMaybe)
import Data.Foldable (for_)
import Data.Traversable (for)
import Control.Monad (foldM)
import Control.Monad.State qualified as Mtl
import Control.Monad.Except qualified as Mtl
import Data.Generics.Uniplate.Data qualified as Uniplate (universe, transformBi)
import Data.Map qualified as Map

Models

Now we can start by defining our models. What are types? What do type definitions look like? What are kinds?

Let's start with a data type definition. We'll support ML style data definitions like the ones in Haskell. For example, the following data type:

Option a =
  | Some a
  | None

A data type definition starts with the type's name, its type parameters, and a list of variants where each has a constructor name and potentially several types.

We'll represent that using the following types:

-- | The representation of a data type definition.
data Datatype a
  = Datatype
    { -- | A place to put kind annotation in.
      dtAnn :: a
    , -- | The name of the data type.
      dtName :: TypeName
    , -- | Type parameters.
      dtParameters :: [TypeVar]
    , -- | Alternative variants.
      dtVariants :: [Variant a]
    }
  deriving (Show, Eq, Data, Generic, Functor, Foldable, Traversable)

-- | A Variant of a data type definition.
data Variant a
  = Variant
    { -- | A type constructor.
      vTypeConstructor :: String
    , -- | A list of types.
      vTypes :: [Type a]
    }
  deriving (Show, Eq, Data, Generic, Functor, Foldable, Traversable)

-- | A name of known types.
newtype TypeName = MkTypeName { getTypeName :: String }
  deriving (Show, Eq, Ord, Data, Generic)

-- | A type variable.
newtype TypeVar = MkTypeVar { getTypeVar :: String }
  deriving (Show, Eq, Ord, Data, Generic)

That polymorphic a is going to be used for our kind annotation.

The shape of the types that we are going to support in our type system are fairly simple. We support type names, such as Int and Option, type variables, such as a and t, and type application, which lets us apply higher kinded types such as Option with other types, such as Option Int, Either e a and f a.

-- | A representation of a type with a place for kind annotation.
data Type a
  = -- | A type variable.
    TypeVar a TypeVar
  | -- | A named type.
    TypeName a TypeName
  | -- | An application of two types, of the form `t1 t2`.
    TypeApp a (Type a) (Type a)
  deriving (Show, Eq, Data, Generic, Functor, Foldable, Traversable)

For example, the data type Option we defined earlier will be represented as a Datatype in the following way:

option =
  Datatype ()
    (MkTypeName "Option")
    [MkTypeVar "a"]
    [ Variant "Some" [TypeVar () $ MkTypeVar "a"]
    , Variant "None" []
    ]

And now lets talk about kinds. As we said before, kinds are the types of types. They represent their whether they can be applied with other types, what their arity should be, and kind of types can be placed in each slot.

For example Option has the kind Type -> Type, it can be applied with a type that has the kind Type, such as Int, but cannot be applied with Option, or with two Ints.

There are also scenarios where a type variable can have any kind, for example in the following data type:

Proxy t =
  | Proxy

Since t is not used anywhere, we can apply any type to Proxy. We can have Proxy Int, but also Proxy Option. Let's define this as a data type:

-- | A representation of a kind.
data Kind
  = -- | For types like `Int`.
    Type
  | -- | For types like `Option`.
    KindFun Kind Kind
  | -- | For polymorphic kinds.
    KindVar KindVar
  | -- | For closing over polymorphic kinds.
    KindScheme [KindVar] Kind
  deriving (Show, Eq, Data, Generic)

-- | A kind variable.
newtype KindVar = MkKindVar { getKindVar :: String }
  deriving (Show, Eq, Ord, Data, Generic)

These types represent the module of our language. During inference, we take a list of data types and a mapping from named types that might appear in these data types to their kinds, and we infer the kinds of these data types and return the data types annotated with their kinds, or we return an error if there was a problem.

We can capture this operation in this type signature:

infer :: Map.Map TypeName Kind -> [Datatype ()] -> Either Error [Datatype Kind]

Let's dive-in and see how we can implement infer.

Kind Inference

Our kind inference algorithm, like our previous type inference algorithm, has 6 important parts:

1. Topologically order definitions and group those that depend on one another (which we will not cover here).
2. Elaboration and constraint generation
3. Constraint solving
4. Instantiation
5. Substitution
6. Generalization

The general process is as follows: we sort and group definitions by their dependencies, we elaborate the data types by giving each type we meet a unique kind variable and collect constraints on those kind variables according to their usage and placement. We then solve these constraints using unification, instatiating the polymorphic kinds we run into, and create a substitution which is a mapping from kind variables to kinds. We then substitute the kind variables we gave to each type in the elaboration stage with their mapped kinds from the substitution in the data type definitions. Then we generalize the kinds of data type definitions and close over their free variables.

This looks somewhat like this:

-- | Infer the kind of a group of data types that should be solved together
--   (because they are mutually recursive).
infer :: Map.Map TypeName Kind -> [Datatype ()] -> Either Error [Datatype Kind]
infer kindEnv datatypes =
  -- initialize our `InferenceM` which is State + Except
  flip Mtl.evalState (initialState kindEnv) $ Mtl.runExceptT $ do
    -- Invent a kind variable for each data type
    for_ datatypes $ \(Datatype _ name _ _) -> do
      kindvar <- freshKindVar
      declareNamedType name kindvar
    -- Elaborate all of the data types
    datatypes' <- traverse elaborate datatypes
    -- Solve the constraints
    solveConstraints
    for datatypes' $ \(Datatype kindvar name vars variants) -> do
      -- Substitute the kind variable for a kind
      -- for the data type
      kind <- lookupKindVarInSubstitution kindvar
      -- ... and for all types
      variants' <- for variants $ traverse lookupKindVarInSubstitution
      -- generalize the data type's kind, and return.
      pure (Datatype (generalize kind) name vars variants')

Lets unpack all of that, step by step.

InferenceM

A couple of capabilities that are going to help us write less verbose code are managing State and throwing Exceptions. We will define a type that merges and provides these capabilities:

-- | We combine the capabilities of Except and State
--   For our kind inference code.
type InferenceM a = Mtl.ExceptT Error (Mtl.State State) a

And the types representing the errors we can throw, and the state we keep throughout the inference process:

-- | The errors that can be thrown in the process.
data Error
  = UnboundVar TypeVar
  | UnboundName TypeName
  | UnificationFailed Kind Kind
  | OccursCheckFailed (Maybe (Type ())) KindVar Kind
  deriving (Show)

-- | The state we keep during an inference cycle
data State = State
  { -- | Mapping from named types or type variables to kind variables.
    -- When we declare a new data type or a type variable, we'll add it here.
    -- When run into a type variable or a type name during elaboration,
    -- we search its matching kind here.
    env :: Map.Map (Either TypeName TypeVar) KindVar
  , -- | Mapping from existing named types to their kinds.
    -- Kinds for types that are supplied before the inference process can be found here.
    kindEnv :: Map.Map TypeName Kind
  , -- | Used for generating fresh kind variables.
    counter :: Int
  , -- | When we learn information about kinds during elaboration, we'll add it here.
    constraints :: [Constraint]
  , -- | The constraint solving process will generate this mapping from
    -- the kind variables we collected to the kind they should represent.
    -- If we don't find the kind variable in the substitution, that means
    -- it is a free variable we should close over.
    substitution :: Map.Map KindVar Kind
  }
  deriving (Show, Eq, Data, Generic)

-- | The state at the start of the process.
initialState :: Map.Map TypeName Kind -> State
initialState kindEnv =
  State mempty kindEnv 0 mempty mempty

-- | A constraint on kinds.
data Constraint
  = Equality Kind Kind
    -- ^ The two kinds should unify.
    -- If one of the kinds is a kind scheme, we will instantiate it, and
    -- add an equality constraint of the other kind with the instantiated kind.
  deriving (Show, Eq, Data, Generic)

We'll later write special utilities functions for interacting with this state when we run into them.

Elaboration and constraint generation

In this section we want to traverse a data type, annotate the types with fresh kind variables, and generate constraints according to the types' location and usage.

-- | Invent kind variables for types we don't know and add constraints
--   on them according to their usage.
elaborate :: Datatype () -> InferenceM (Datatype KindVar)
elaborate (Datatype _ datatypeName vars variants) = do
  -- We go over each of the data type parameters and
  -- generate a fresh kind variable for them.
  varKinds <- for vars $ \var -> do
    kindvar <- freshKindVar
    declareTypeVar var kindvar
    pure kindvar

  -- We go over the variants, elaborate each field,
  -- and return the elaborated variants.
  variants' <- for variants $ \(Variant name fields) -> do
    Variant name <$>
      for fields
        ( \field -> do
          field' <- elaborateType field
          -- a constraint on fields: their kind must be `Type`.
          newEqualityConstraint (KindVar $ getAnn field') Type
          pure field'
        )

  -- We grab the kind variable of the data type
  -- so we can add a constraint on it.
  datatypeKindvar <- lookupNameKindVar datatypeName
  -- A type of the form `T a b c ... =` has the kind:
  -- `aKind -> bKind -> cKind -> ... -> Type`.
  -- We add that as a constraint.
  let kind = foldr KindFun Type $ map KindVar varKinds
  newEqualityConstraint (KindVar datatypeKindvar) kind

  -- We return the elaborated data type after annotating
  -- all types with kind variables and generating constraints.
  pure (Datatype datatypeKindvar datatypeName vars variants')

There are a couple of utility functions we've used in the last snippet:

We generate fresh kind variables for type variables declare. After constraint solving we'll find the kind variable again and learn what the actual kind should be in its place.

We'll also save the kind variable we generated for the type variable in the environment, so we can find it later when it is used.

-- | Generate a fresh kind variables.
freshKindVar :: InferenceM KindVar
freshKindVar = do
  s <- Mtl.get
  let kindvar = MkKindVar ("k" <> show (counter s))
  Mtl.put s { counter = 1 + counter s }
  pure kindvar

-- | Insert declared type variables into the environment.
declareTypeVar :: TypeVar -> KindVar -> InferenceM ()
declareTypeVar var kindvar =
  Mtl.modify $ \s ->
    s { env = Map.insert (Right var) kindvar (env s) }

We've used freshKindVar and the following declareNamedType before in infer when we ran into the data type declaration.

-- | Insert declared type names into the environment.
declareNamedType :: TypeName -> KindVar -> InferenceM ()
declareNamedType name kindvar =
  Mtl.modify $ \s ->
    s { env = Map.insert (Left name) kindvar (env s) }

We also fetch the kind we annotated a type with using getAnn:

-- | Get the annotation of a type.
getAnn :: Type a -> a
getAnn = \case
  TypeVar a _ -> a
  TypeName a _ -> a
  TypeApp a _ _ -> a

Another important utility function is for adding constraints:

-- | Add a new equality constraint to the state.
newEqualityConstraint :: Kind -> Kind -> InferenceM ()
newEqualityConstraint k1 k2 =
  Mtl.modify $ \s ->
    s { constraints = Equality k1 k2 : constraints s }

Elaborating types

The next part is elaborating types. As a reminder, we support named types, type variables, and applications of a type to a type.

For type variables, we added them to the environment previously when we saw them declared. We look them up. If they are not there, that's an error.

-- | Find the kind variable of a type variable in the environment.
lookupVarKindVar :: TypeVar -> InferenceM KindVar
lookupVarKindVar var =
  maybe
    (Mtl.throwError $ UnboundVar var)
    pure
    . Map.lookup (Right var)
    . env =<< Mtl.get

For named types, either they were supplied to the inference stage, and in that case we invent a new kind variable for them for this particular use, or they were declared as part of this data types group, in which case we look them up in the environment.

-- | Find the kind variable of a named type in the environment.
lookupNameKindVar :: TypeName -> InferenceM KindVar
lookupNameKindVar name = do
  state <- Mtl.get
  -- We first look the named type in the supplied kind env.
  case Map.lookup name (kindEnv state) of
    -- If we find it, we generate a new kind variable for it
    -- and constraint it to be this type, so that each use has it own
    -- type variable (later used for instantiation).
    Just kind -> do
      kindvar <- freshKindVar
      newEqualityConstraint (KindVar kindvar) kind
      pure kindvar
    -- If it's not a supplied type, it means we are actively inferring it,
    -- and we need to use the same kind variable for all uses.
    -- We'll look it up in our environment of declared types.
    Nothing ->
      maybe
        -- If we still can't find it, we error.
        (Mtl.throwError $ UnboundName name)
        pure
        . Map.lookup (Left name)
        $ env state

And for a type application of t1 and t2, we elaborate both types, invent a kind variable for the type application, then constrain the applied type t1 to be equal to a kind that takes the kind of t2 and returns the kind of the type application.

This is the rest of the code for elaborating types:

-- | Elaborate a type with a kind variable and add constraints
--   according to usage.
elaborateType :: Type () -> InferenceM (Type KindVar)
elaborateType = \case
  -- for type variables and type names,
  -- we lookup the kind variables we generated when we ran into
  -- the declaration of them.
  TypeVar () var ->
    fmap (\kindvar -> TypeVar kindvar var) (lookupVarKindVar var)

  TypeName () name ->
    fmap (\kindvar -> TypeName kindvar name) (lookupNameKindVar name)

  -- for type application
  TypeApp () t1 t2 -> do
    -- we elaborate both types
    t1Kindvar <- elaborateType t1
    t2Kindvar <- elaborateType t2
    -- then we generate a kind variable for the type application
    typeAppKindvar <- freshKindVar
    -- then we constrain the type application kind variable
    -- it should unify with `t2Kind -> typeAppKind`.
    newEqualityConstraint
      (KindVar $ getAnn t1Kindvar)
      (KindFun (KindVar $ getAnn t2Kindvar) (KindVar typeAppKindvar))

    pure (TypeApp typeAppKindvar t1Kindvar t2Kindvar)

And that's it for the elaboration phase. After giving each type a kind variable and collecting some constraints about them, we are ready to the next stage where we can ignore the data type definition and focus on the constraints we generated.

Constraint solving and generating a substitution

In this phase we go one constraint at a time and decide whether it is trivial (equality between Type and Type), or if it needs to be reduced to simpler constraints that will be checked (like matching the two first parts and the two second parts of two KindFuns).

When we run into kind variables, we will substitute them with the other kind in the rest of the equality constraints and in a mapping we'll keep on the side which we'll call a "substitution" and keep going.

When we run into a kind scheme, we instantiate it (give it a new unique instance) and constrain it with the other kind in the constraint.

When we run into two kinds that cannot be unified (Type and KindFun), we throw an error.

When there are no more constraints left to solve, we are done and succeeded on our task!

-- | Solve constraints according to logic.
--   this process is iterative. We continue fetching
--   the next constraint and try to solve it.
--
--   Each step can either reduce or increase the number of constraints,
--   and we are done when there are no more constraints to solve,
--   or if we ran into a constraint that cannot be solved.
solveConstraints :: InferenceM ()
solveConstraints = do
  -- Pop the next constraint we should solve.
  constraint <- do
    c <- listToMaybe . constraints <$> Mtl.get
    Mtl.modify $ \s -> s { constraints = drop 1 $ constraints s }
    pure c

  case constraint of
    -- If we have two 'Type's, the unify. We can skip to the next constraint.
    Just (Equality Type Type) -> solveConstraints
    -- We have an equality between two kind functions.
    -- We add two new equality constraints matching the two firsts
    -- with the two seconds.
    Just (Equality (KindFun k1 k2) (KindFun k3 k4)) -> do
      Mtl.modify $ \s ->
        s { constraints = Equality k1 k3 : Equality k2 k4 : constraints s }
      solveConstraints
    -- When we run into a kind scheme, we instantiate it
    -- (we look at the kind and replace all closed kind variables
    -- with fresh kind variables), and add an equality constraint
    -- between the other kind and the instantiated kind.
    Just (Equality (KindScheme vars kind) k) -> do
      kind' <- instantiate kind vars
      Mtl.modify $ \s ->
        s { constraints = Equality k kind' : constraints s }
      solveConstraints
    -- Same as the previous scenario.
    Just (Equality k (KindScheme vars kind)) -> do
      kind' <- instantiate kind vars
      Mtl.modify $ \s ->
        s { constraints = Equality kind' k : constraints s }
      solveConstraints
    -- If we run into a kind variable on one of the sides,
    -- we replace all instances of it with the other kind and continue.
    Just (Equality (KindVar var) k) -> do
      replaceInState var k
      solveConstraints
    -- The same as the previous scenario, but the kind var is on the other side.
    Just (Equality k (KindVar var)) -> do
      replaceInState var k
      solveConstraints
    -- If we have an equality constraint between a 'Type' and
    -- a 'KindFun', we cannot unify the two, and unification fails.
    Just (Equality k1@Type k2@KindFun{}) -> Mtl.throwError (UnificationFailed k1 k2)
    Just (Equality k1@KindFun{} k2@Type) -> Mtl.throwError (UnificationFailed k1 k2)
    -- If there are no more constraints, we are done. Good job!
    Nothing -> pure ()

Let's talk about a few of these operations.

Instantiating kind schemes

When we run into a kind scheme (where a kind contains polymorphic kind variables) in a constraint, we actually want to work with an instance of that kind scheme. So we take the kind scheme and produce a kind where all of the type variables in it are fresh kind variables.

-- | Instantiate a kind.
--   We look at the kind and replace all closed kind variables
--   with fresh kind variables.
instantiate :: Kind -> [KindVar] -> InferenceM Kind
instantiate = foldM replaceKindVarWithFreshKindVar

-- | Replace a kind variable with a fresh variable in the kind.
replaceKindVarWithFreshKindVar :: Kind -> KindVar -> InferenceM Kind
replaceKindVarWithFreshKindVar kind var = do
  kindvar <- freshKindVar
  -- Uniplate.transformBi lets us perform reflection and
  -- apply a function to all instances of a certain type
  -- in a value. Think of it like `fmap`, but for any type.
  --
  -- It is a bit slow though, so it's worth replacing it with
  -- hand rolled recursion or a functor, but its convenient.
  pure $ flip Uniplate.transformBi kind $ \case
    kv | kv == var -> kindvar
    x -> x

Note: We are using the uniplate with the interface that works for every type that has an instance of Data from Data.Data. It lets us use generic traversals and transformations with very little effort, but it is fairly slower than hand-writting things so for real kind inference implementation you probably want to hand-write the traversals.

Replacing kind variables

When we run into a kind variable, we replace it with the kind on the other side of the equality constraint in the substitution and in the rest of the constraints, and we then add it to the substitution.

We change it in the rest of the constraints so that if we have the following two constraints:

1. Equality (KindVar "k1") Type
2. Equality (KindVar "k1") (Type -> Type)

When we replace KindVar "k1" with Type in the rest of the constraints, instead of the next constraint being (2), it will be:

Equality Type (Type -> Type)

Which does not unify, and we catch the bug.

We also change the kind variable in the substitution and later add it to it so we can later look up the kind variable we placed on each type in the elaboration phase and find their kinds.

-- | Replace every instance of 'KindVar var' in our state with 'kind'.
--   And add it to the substitution.
replaceInState :: KindVar -> Kind -> InferenceM ()
replaceInState var kind = do
  occursCheck var kind
  s <- Mtl.get
  let
    -- Uniplate.transformBi lets us perform reflection and
    -- apply a function to all instances of a certain type
    -- in a value. Think of it like `fmap`, but for any type.
    --
    -- Note that we are changing all instances of `Kind` of the form
    -- `KindVar v | v == var` in all of `State`! This includes both the
    -- `substitution` and the remaining `constraints`,
    --
    -- It is a bit slow though, so it's worth replacing it with
    -- hand rolled recursion or a functor, but its convenient.
    s' =
      flip Uniplate.transformBi s $ \case
        KindVar v | v == var -> kind
        x -> x
  Mtl.put $ s' { substitution = Map.insert var kind (substitution s') }

But one important thing we need to check about the kind variable and the kind is that the kind does not contain the kind variable, which means we have an "infinite" kind. This is called an occurs check.

-- | We check that the kind variable does not appear in the kind
--   and throw an error if it does.
occursCheck :: KindVar -> Kind -> InferenceM ()
occursCheck var kind =
  if KindVar var == kind || null [ () | KindVar v <- Uniplate.universe kind, var == v ]
    then pure ()
    else do
      -- We try to find the type of the kind variable by doing reverse lookup,
      -- but this might not succeed before the kind variable might be generated
      -- during constraint solving.
      -- We might be able to find the type if we look at the substitution as well,
      -- but for now lets leave it at this "best effort" attempt.
      reverseEnv <- map swap . Map.toList . env <$> Mtl.get
      let typ = either (TypeName ()) (TypeVar ()) <$> lookup var reverseEnv
      Mtl.throwError (OccursCheckFailed typ var kind)

Once again we use the universe function from the uniplate library, which returns all values of the same type that appear in a value, so we find all of the kinds inside our kind and select the kind variables specifically.

Other errors

If we run into an equality constraint between a Type and a KindFun, we throw an error, since we can't unify them.

Substitution

Once we finish with constraint solving, we'll have a substitution ready for us in State.

All we need to do now is look up the kind produced by the substitution for each kind variable.

-- | Look up what the kind of a kind variable is in the substitution
--   produced by constraint solving.
--   If there was no constraint on the kind variable, it won't appear
--   in the substitution, which means it can stay a kind variable which
--   we will close over later.
lookupKindVarInSubstitution :: KindVar -> InferenceM Kind
lookupKindVarInSubstitution kindvar =
  maybe (KindVar kindvar) id . Map.lookup kindvar . substitution <$> Mtl.get

Generalization

When we are done with elaborating, solving constraints, and substituting over data types, we need to look at the kind produced for each data type, and close over the free kind variables.

Again, using Uniplate.universe to find all of the type variables and include them in the kind scheme.

-- | Close over kind variables we did not solve.
generalize :: Kind -> Kind
generalize kind = KindScheme [var | KindVar var <- Uniplate.universe kind] kind

Examples

That's pretty much it! We can now define data types and observe the kinds we produce.

option :: Datatype ()
option =
  Datatype ()
    (MkTypeName "Option")
    [MkTypeVar "a"]
    [ Variant "Some" [TypeVar () $ MkTypeVar "a"]
    , Variant "None" []
    ]

main :: IO ()
main = do
  print $ map dtAnn <$> infer mempty [option]

Will output:

Right [KindScheme [] (KindFun Type Type)]

As promised, our kind inference engine is able to infer the kind of this type:

Cofree f a =
  | Cofree a (f (Cofree f a))

As expected:

Cofree : (Type -> Type) -> Type -> Type
Cofree f a =
  | Cofree a (f (Cofree f a))

And can catch errors such as:

Tree a =
  | Node a Tree Tree

And produce the error:

Unification failed between the following kinds:
  * k1 -> Type
  * Type

You can find other examples in the gist.

Summary

Kind inference using unification-based constraint solving works on data types the in same way type inference with the same methods works on expressions. While it can be a bit tricky, implementing a somewhat powerful kind inference engine is relatively straightforward.

You can find the source code in this gist. It includes pretty printing code, additional examples, and a lot of comments.

September 30, 2023 12:00 AM

GHC 9.8.1-rc1 is now available

GHC 9.8.1-rc1 is now available

bgamari - 2023-09-29

The GHC developers are very pleased to announce the availability of the release candidate of GHC 9.8.1. Binary distributions, source distributions, and documentation are available at downloads.haskell.org.

GHC 9.8 will bring a number of new features and improvements, including:

• Preliminary support the TypeAbstractions language extension, allowing types to be bound in type declarations TypeAbstractions.

• Support for the ExtendedLiterals extension, providing syntax for non-word-sized numeric literals in the surface language extended-literals

• Improved rewrite rule matching behavior, allowing limited matching of higher-order patterns

• Better support for user-defined warnings by way of the WARNING pragma warnings

• The introduction of the new GHC.TypeError.Unsatisfiable constraint, allowing more predictable user-defined type errors unsatisfiable

• Implementation of the export deprecation proposal, allowing module exports to be marked with DEPRECATE pragmas deprecated-exports

• The addition of build semaphore support for parallel compilation; with coming support in cabal-install this will allow better use of parallelism in multi-package builds jsem

• More efficient representation of info table provenance information, reducing binary sizes by over 50% in some cases when -finfo-table-map is in use

A full accounting of changes can be found in the release notes. This candidate includes roughly 20 new commits relative to alpha 4, including what we believe should be nearly the last changes to GHC’s boot libraries. As always, GHC’s release status can be found on the GHC Wiki status.

We would like to thank GitHub, IOG, the Zw3rk stake pool, Well-Typed, Tweag I/O, Serokell, Equinix, SimSpace, the Haskell Foundation, and other anonymous contributors whose on-going financial and in-kind support has facilitated GHC maintenance and release management over the years. Finally, this release would not have been possible without the hundreds of open-source contributors whose work comprise this release.

As always, do give this release a try and open a ticket if you see anything amiss.

Happy compiling,

Ben

by ghc-devs at September 29, 2023 12:00 AM

GHC 9.6.3 is now available

GHC 9.6.3 is now available

Bryan Richter - 2023-09-25

The GHC developers are happy to announce the availability of GHC 9.6.3. Binary distributions, source distributions, and documentation are available on the release page.

This release is primarily a bugfix release addressing a few issues found in the 9.6 series. These include:

• Disable Polymorphic Specialisation (a performance optimisation) by default. It was discovered that Polymorphic Specialisation as currently implemented in GHC can lead to hard to diagnose bugs resulting in incorrect runtime results. Users wishing to use this optimisation despite the caveats will now have to explicitly enable the new -fpolymorphic-specialisation flag. For more details see #23469 as well as #23109, #21229, #23445.

• Improve compile time and code generation performance when -finfo-table-map is enabled (#23103).

• Make the recompilation check more robust when code generation flags are changed (#23369).

• Addition of memory barriers that improve soundness on platforms with weak memory ordering.

• And dozens of other fixes.

A full accounting of changes can be found in the release notes. As some of the fixed issues do affect correctness users are encouraged to upgrade promptly.

We would like to thank Microsoft Azure, GitHub, IOG, the Zw3rk stake pool, Well-Typed, Tweag I/O, Serokell, Equinix, SimSpace, Haskell Foundation, and other anonymous contributors whose on-going financial and in-kind support has facilitated GHC maintenance and release management over the years. Finally, this release would not have been possible without the hundreds of open-source contributors whose work comprise this release.

As always, do give this release a try and open a ticket if you see anything amiss.

Enjoy!

-Bryan

by ghc-devs at September 25, 2023 12:00 AM

Defining a formatter for Cabal files

For Haskell code I can use lsp-format-buffer and lsp-format-region to keep my file looking nice, but I've never found a function for doing the same for Cabal files. There's a nice command line tool, cabal-fmt, for doing it, but it means having to jump to a terminal. It would of course be nicer to satisfy my needs for aesthetics directly from Emacs. A few times I've thought of writing the function myself, I mean how hard can it be? But then I've forgotten about it until then next time I'm editing a Cabal file.

A few days ago I noticed emacs-reformatter popping up in my feeds. That removed all reasons to procrastinate. It turned out to be very easy to set up.

The package doesn't have a recipe for straight.el so it needs a :straight section. Also, the naming of the file in the package doesn't fit the package name, hence the slightly different name in the use-package declaration:¹

(use-package reformatter
  :straight (:host github
             :repo "purcell/emacs-reformatter"))

Now the formatter can be defined

(reformatter-define cabal-format
  :program "cabal-fmt"
  :args '("/dev/stdin"))

in order to create functions for formatting, cabal-format-buffer and cabal-format-region, as well as a minor mode for formatting on saving a Cabal file.

Footnotes:

¹

I'm sure it's possible to use :files to deal with this, but I'm not sure how and my naive guess failed. It's OK to be like this until I figure it out properly.

Tags: emacs haskell

September 24, 2023 08:20 AM

Behind the scenes with FawltyDeps v0.13.0: Matching imports with dependencies

We have previously introduced FawltyDeps, a tool to help Python projects avoid the dreaded, and seemingly unavoidable state, where dependencies declared in the configuration do not match those actually imported in the code¹. FawltyDeps is the perfect addition to your CI, your pre-commit hooks, or your dependency management arsenal.

Curious to know how FawltyDeps works its magic? In this sequel we’ll delve into an essential component of FawltyDeps: how it matches imports and dependencies behind the scenes, and why it is important to get this matching right.

We’ve been busy working on an improved mapping strategy that combines versatility with simplicity, and we have come a long way from the quite limited version we presented in our first announcement. By the end of this post, you’ll have a solid understanding of FawltyDeps’ brand new mapping options and how to tailor them to your project’s unique context and needs.

Matching imports and dependencies

Simply put, FawltyDeps extracts imports from your code, and dependencies declared in your project configuration, and matches them against each other:

• the imports that are not present in your declared dependencies are reported as undeclared dependencies
• the declared dependencies that are not imported in your code are reported as unused dependencies.

When matching imports and dependencies, we first assume that a dependency (specifically: the package it references) and an import have the same name. This approximation works well for many Python packages. numpy is a good example: in your code, you write import numpy, and to install it you run pip install numpy, or you list numpy in your requirements.txt (or wherever you list your project dependencies).

Problem solved! So why are we even writing this post?

It turns out that, as always, things are not that simple™. Many packages provide import names that are different from the package name. For example:

• You depend on the pyyaml package, but you import yaml (as seen in Figure 1).
• You depend on the scikit-learn package, but you import sklearn.
• You depend on the setuptools package, but you import either pkg_resources or some other import, as setuptools exposes multiple imports.

Clearly our first approximation (hereafter referred to as the identity mapping) is not good enough. To solve this, we need a smarter mapping: a way to figure out which packages correspond to which imports. In practice, there are a few different ways to acquire these mappings, each having its advantages and limitations. Our main goal here is to lay out the mappings we support in FawltyDeps, and explain how they can be used individually or together to resolve packages into their respective imports.

Mapping from already-installed packages

Arguably, the only correct way for FawltyDeps to match packages to imports is to actually ask each package what imports it provides. FawltyDeps can do this³, but it first needs to find where the packages are installed, and that turns out to be more complicated than one might think.

In the first versions of FawltyDeps, we had not yet properly drilled into this issue. Instead, we only looked at the Python environment in which FawltyDeps itself was already running, and we simply assumed that your project dependencies should be installed into the same environment ⁴. If a dependency of your project was not found in this environment, we would fall back to the identity mapping.

This meant simply pushing the problem onto the user, however, and making FawltyDeps harder to use. What we wanted instead was for FawltyDeps to resolve the dependencies wherever they may be installed. This is where things can get very complicated: In general, there is a bewildering variety of ways to install dependencies in the Python world.

We are not going to open the entire Pandora’s box of Python packaging and dependency management in this blog post, except as to note some different examples of where Python packages (specifically: your project’s 3rd-party dependencies) can typically be found:

• System-wide package locations, like those found under /usr/lib/python* or /usr/local/lib/python* (whether installed by your system’s package manager or system-wide pip install).
• User-specific packages, installed by tools like pipx install or pip install --user.
• Virtual environments (from venv, virtualenv, Poetry, PDM, etc.), located either within your project, or somewhere else.
• Other, less common, methods or locations⁵ that resemble any of the above.

We would like to have FawltyDeps work with as many of these as possible, and furthermore, when it’s possible: to have FawltyDeps automatically discover and use them by default.

As of v0.13.0 we have come a long way towards realizing this vision: We support the kinds of Python environments mentioned above (for FawltyDeps’ purpose, a “Python environment” really means any directory in which Python packages could be installed), and the following diagram outlines how FawltyDeps determines which Python environments are used to look up the project’s dependencies:

In other words:

• The --pyenv option lets you point to one or more Python environments. All of these environments will be used when matching dependencies to imports
• If --pyenv is not used, FawltyDeps will automatically find and use Python environments that exist within your project directories (i.e. within any directory that is passed as a positional argument to FawltyDeps, aka. “basepath”, or the current directory by default).
• If no Python environment is found by the two methods above, FawltyDeps will fall back to using the environment in which it’s running.

There is still some way to go until all the details are perfect here⁶, but we believe this approach covers most common cases well.

Temporarily installing dependencies to complete the mapping

There is an elephant in the room that we have not yet talked about: Sometimes you may be running FawltyDeps on a project where the project dependencies are not installed at all! Then what can you do? (Assuming that you don’t want to go through the bother of installing packages manually.) Until recently FawltyDeps would simply fall back to the identity mapping for any packages that it could not find locally, with the undeclared/unused report provided by FawltyDeps suffering as a result.

With the new --install-deps option introduced in v0.13.0, we are now able to provide a better alternative: With this option FawltyDeps will not fall back to the identity mapping, instead it will automatically use pip install to install the unresolved dependencies (from PyPI, by default⁷) into a temporary virtualenv⁸, and it will then use this as an additional source for the dependency-to-import mapping. For dependencies that are not found locally, this allows FawltyDeps to come up with the correct mapping (and hence produce a much better undeclared/unused report) rather than relying on the imperfect identity mapping.

Since this is a potentially expensive strategy we have chosen to hide it behind the --install-deps command-line option. If you want to always enable this option, you can set the corresponding install_deps configuration variable to true in the [tool.fawltydeps] section of your pyproject.toml.

Note that there is no guarantee that we’re able to resolve all dependencies with this method: For example, there could be a typo in your declared dependency that means it will never be found on PyPI, or there could be other circumstances (e.g. network issues) that prevent this strategy from working at all. What happens with such unresolved dependencies will be covered below.

User-defined mapping

The mappings discussed above have FawltyDeps look into packages that are actually installed (whether in an existing local environment or temporarily by FawltyDeps). But this might not always be achievable in practice. You might want to run FawltyDeps in your CI, possibly on multiple libraries, without having to either set up a local environment or access packages from outside sources (like PyPI).

A simple solution to this is to provide FawltyDeps with your own custom mapping.⁹ We have chosen not to ship any database with the code as it needs to be frequently updated, with no guarantee of it covering all Python packages. Instead, we allow users to provide their own custom TOML mapping. This mapping does not have to be complete and it can be used in conjunction with the other mappings discussed in this article. We talk more about how FawltyDeps combines different mappings in the following section.

Putting it together: FawltyDeps’ mapping strategy

Now that we have gathered all these mappings, let’s see how to best combine them.

Overall, we have three guiding principles in this endeavor:

• Completeness: we should be able to resolve all dependencies extracted from a project into associated import names, as otherwise we cannot reach any conclusions about undeclared or unused dependencies.
• Correctness: some mappings offer a higher level of correctness than others. Identity mapping, for example, is correct for many - but certainly not all - packages. Resolving a dependency via a locally installed package offers a higher guarantee of correctness.
• Transparency: we should be able to trace back what mapping was used to resolve any given dependency. This allows users to discover where they may improve the information passed to FawltyDeps (e.g. using --pyenv to point at the most appropriate Python environments). It also makes it much easier for us to diagnose where FawltyDeps itself might be improved.

First, let’s start by repeating our available strategies:

• Identity mapping: The simplest strategy, but also the worst. We would like to avoid using it as much as possible.
• Looking at locally installed packages: Our best option in terms of correctness, but not always complete: sometimes we have to concede that not all dependencies are available in a local Python environment, so we still need a fallback strategy.
• Installing packages (from PyPI) into a temporary virtualenv: The ultimate fallback solution, but quite heavy-weight, and not always suitable (e.g. in a restricted CI environment). Hence, we put this behavior behind the --install-deps option.
• Custom/user-defined mapping: Allow the user to have the final say in how dependencies are mapped into imports. This strategy should override the other strategies, but we expect few users will want to go through the fuss of defining their own mapping, so we cannot rely on this being used commonly.

Now, we need to figure out how to combine these strategies in the best way.

We have chosen to organize them in the sequence shown in Figure 3 below. Each strategy - when given the name of a dependency - can either return a successful mapping of that dependency name (into a corresponding set of import names), or return nothing (when a dependency is not found by that strategy). Dependencies that are not resolved by a strategy are passed onto the next strategy in the sequence. Since a dependency is mapped by only one strategy, that is, the first that returns something, we need to organize our strategies in order of decreasing preference. In other words:

• The user-defined mapping, when provided, should always override other mappings. It thus comes first in the sequence.
• Next, we want to look at the locally installed packages.
• Finally, if we have not been able to find the dependency in either of the above, we want to use a fallback strategy:
  • If the user has enabled --install-deps, we attempt to install packages (subject to pip configuration, but from PyPI by default). If any of these packages fail to install, we abort the entire process and raise an error, as we do not expect the user wants a further fallback to the inaccurate identity mapping.
  • Otherwise, our fallback is the identity mapping, that is, we assume any unresolved dependency points to a package (as yet unseen) that provides a single import of the same name. Although this strategy is always “successful” (in terms of mapping to an import name), it is crucially not always correct!

To illustrate:

To bring this back into the overall context of FawltyDeps: once we have resolved the dependencies through the above mapping strategies, we now have an overall mapping of dependency names to provided import names, and this is the basis for the final report:

• Any import found in the project that is not covered by any dependency is reported as an undeclared dependency.
• Any dependency found to only provide imports that are never imported from anywhere is reported as a possibly unused dependency.

The table below provides a summary of the available mappings, sorted in the order FawltyDeps processes them, along with options to customize them.

Priority	Mapping strategy	Options
1	User-defined mapping	Provide a custom mapping in TOML format via --custom-mapping-file or a [tool.fawltydeps.custom_mapping] section in pyproject.toml. Default: No custom mapping
2	Mapping from installed packages	Point to one or more environments via --pyenv. Default: auto-discovery of Python environments under the project’s basepath. If none are found, default to the Python environment in which FawltyDeps itself is installed.
3a	Mapping via temporary installation of packages	Activated with the --install-deps option.
3b	Identity mapping	Active by default. Deactivated when --install-deps is used.

Examples

This section dives into some practical scenarios. Suppose you have a simple requirements.txt file:

numpy>=1.25.0
scikit-learn
pyyaml

We assume that these packages are already imported in some_script.py as

import numpy
import sklearn
import yaml

As we can see, our project has defined all its dependencies as it should, so FawltyDeps should ideally not report any problems. But let’s also assume that we’re running FawltyDeps in an incomplete environment - one where pyyaml is not installed - to see how this affects FawltyDeps.

Example 1: running with default options

When running with default options, like so:

fawltydeps

FawltyDeps will run through the default sequence of mappings, as shown in Figure 4:

In particular:

• No custom mapping is provided.
• FawltyDeps automatically finds local environments or defaults to its own environment. In this example it finds scikit-learn and numpy in the local environment, and we can see that scikit-learn is correctly resolved to the sklearn import name.
• Identity mapping is used to resolve any dependencies not resolved via previous mappers. In this example, pyyaml was not found above, and was therefore incorrectly resolved by the identity mapping to pyyaml.

The resulting output from FawltyDeps is:

These imports appear to be undeclared dependencies:
- 'yaml'

These dependencies appear to be unused (i.e. not imported):
- 'pyyaml'

For a more verbose report re-run with the `--detailed` option.

This first example shows a common pitfall of the identity mapping. Next, we can see how --install-deps improves on these situations:

Example 2: running with custom options

Let’s now take advantage of some advanced FawltyDeps options by running the following command:

fawltydeps --custom-mapping-file my_mapping.toml --pyenv venv --install-deps

Figure 5 shows the path FawltyDeps takes through the sequence of mappings:

In particular:

• We provide a partial custom mapping. (e.g. via --custom-mapping-file). In this example, the custom mapping is defined in my_mapping.toml.

  scikit-learn = ["sklearn"]

• We point to a local virtual environment (with --pyenv) where some dependencies are installed. (In this example, only numpy is installed in venv.)
• We pass --install-deps, to ask FawltyDeps to temporarily install and resolve any remaining dependencies.

FawltyDeps returns the following result:

No undeclared or unused dependencies detected.

As expected, FawltyDeps now returns a better result:

The --install-deps option downloads the pyyaml PyPI package and makes it available to the resolver, so it can now map the yaml import to the correct pyyaml dependency declaration.

Customizing your FawltyDeps’ mappers

These examples demonstrate two extremes and we expect most usage to fall somewhere in between.

With the --json flag, the resulting package-to-imports mapping is exposed in the output under the .resolved_deps key. Using a command like this:

fawltydeps --custom-mapping-file my_mapping.toml --pyenv venv --install-deps --json | jq .resolved_deps

you can see which mappings are used to resolve a package into a set of imports, and further iterate on the mapping options to help FawltyDeps perform its best on your codebase.

Conclusion

FawltyDeps has come a long way from the version we presented in our first announcement. While it was initially limited to resolving packages from its own environment and falling back to the identity mapping, it now supports arbitrary local environments, custom user mappings and it can temporarily install and resolve packages on its own. On top of that, it can also automatically discover virtual environments inside the analyzed project.²

We strive to provide a default behavior that makes sense for most projects, and to offer a customizable yet simple interface for advanced users that wish to take control over the mapping process. We believe the result is a powerful tool that delivers a complete, correct and transparent matching of your project’s dependencies and imports.

As always, we would be happy to hear your feedback! Try out the latest version of FawltyDeps and reach out to us with any problems or questions on our Github repository.

---

1. The recent publication of Computational reproducibility of Jupyter notebooks from biomedical publications highlights that missing dependencies is a frequent occurrence in repositories hosting scientific computational experiments and has a detrimental effect on reproducibility.↩

2. We depend on functionality from the excellent importlib_metadata library to extract imports exposed in locally installed packages.↩

3. This assumption was made no matter whether FawltyDeps was installed in a virtualenv or as part of the system-wide Python installation, and we only documented that FawltyDeps had to be installed into the same environment as your project dependencies. One example of where this did not work out well is when you installed FawltyDeps with pipx install fawltydeps: This makes fawltydeps available everywhere (via your $PATH), but pipx installs it into its own, separate, virtualenv that is isolated from your project, meaning that FawltyDeps would almost always fall back to the identity mapping, and yield poor results.↩

4. Some less common locations of Python packages:

   • __pypackages__ directories (even though PEP582 was recently rejected, these still occur in the wild).
   • Conda and other environment managers (not yet explicitly supported, although it’s on our radar).
   • Nix closures containing Python packages, like those produced by poetry2nix.

   ↩

5. One open issue is that FawltyDeps currently does not look at package versions. This usually does not cause problems in practice, but there are corner cases where it might: Consider, for example, a package_foo that used to provide two import names module_a and module_b, but starting from version 2, it only provides module_a. Now, if your project declares a dependency on package_foo>=2, but you still happen to import module_b in your code, this should be reported by FawltyDeps as an undeclared dependency (because you’re declaring a dependency on a version of package_foo where module_b no longer exists). However, if package_foo version 1 (not version 2) happens to be installed in your project’s environment, FawltyDeps will simply believe that package_foo (whichever version) provides both module_a and module_b, and the error won’t be flagged.↩

6. To customize automatic installation (for example, to use a different package index), you can use pip’s environment variables.↩

7. Note that the PyPI API does not currently expose imports of the hosted packages (see here and here for relevant discussions). Downloading and unpacking these packages is therefore necessary.↩

8. Some tools rely on custom mappings. A notable example is the Pants build system, which relies on static mappings provided by the user. Another example is the pipreqs library, which keeps a static database mapping packages to the import names they expose.↩

9. For completeness, here is an overview of the changes we’ve made to our mapping strategy over the last releases, and that together realize the picture presented in this blog post:

   • v0.7 introduces the --pyenv option to allow FawltyDeps to look up packages in a different Python environment than the one in which FawltyDeps is running.
   • v0.9 adds the user-defined mapping.
   • v0.10 adds support for __pypackages__ directories.
   • v0.11 introduces support for multiple --pyenv options.
   • v0.12 revamps our project traversal, allowing Python environments to be automatically found inside the project.
   • v0.13 introduces the --install-deps option allowing missing project dependencies to be mapped correctly instead of using the identity mapping.

   ↩

September 21, 2023 12:00 AM

Haskell webassembly in the browser

live demo

As far as I know this is the first Haskell program compiled to Webassembly (WASM) with mainline ghc and using the browser DOM.

ghc's WASM backend is solid, but it only provides very low-level FFI bindings when used in the browser. Ints and pointers to WASM memory. (See here for details and for instructions on getting the ghc WASM toolchain I used.)

I imagine that in the future, WASM code will interface with the DOM by using a WASI "world" that defines a complete API (and browsers won't include Javascript engines anymore). But currently, WASM can't do anything in a browser without calling back to Javascript.

For this project, I needed 63 lines of (reusable) javascript (here). Plus another 18 to bootstrap running the WASM program (here). (Also browser_wasi_shim)

But let's start with the Haskell code. A simple program to pop up an alert in the browser looks like this:

{-# LANGUAGE OverloadedStrings #-}

import Wasmjsbridge

foreign export ccall hello :: IO ()

hello :: IO ()
hello = do
    alert <- get_js_object_method "window" "alert"
    call_js_function_ByteString_Void alert "hello, world!"

A larger program that draws on the canvas and generated the image above is here.

The Haskell side of the FFI interface is a bunch of fairly mechanical functions like this:

foreign import ccall unsafe "call_js_function_string_void"
    _call_js_function_string_void :: Int -> CString -> Int -> IO ()

call_js_function_ByteString_Void :: JSFunction -> B.ByteString -> IO ()
call_js_function_ByteString_Void (JSFunction n) b =
      BU.unsafeUseAsCStringLen b $ \(buf, len) ->
                _call_js_function_string_void n buf len

Many more would need to be added, or generated, to continue down this path to complete coverage of all data types. All in all it's 64 lines of code so far (here).

Also a C shim is needed, that imports from WASI modules and provides C functions that are used by the Haskell FFI. It looks like this:

void _call_js_function_string_void(uint32_t fn, uint8_t *buf, uint32_t len) __attribute__((
        __import_module__("wasmjsbridge"),
        __import_name__("call_js_function_string_void")
));

void call_js_function_string_void(uint32_t fn, uint8_t *buf, uint32_t len) {
        _call_js_function_string_void(fn, buf, len);
}

Another 64 lines of code for that (here). I found this pattern in Joachim Breitner's haskell-on-fastly and copied it rather blindly.

Finally, the Javascript that gets run for that is:

call_js_function_string_void(n, b, sz) {
    const fn = globalThis.wasmjsbridge_functionmap.get(n);
    const buffer = globalThis.wasmjsbridge_exports.memory.buffer;
    fn(decoder.decode(new Uint8Array(buffer, b, sz)));
},

Notice that this gets an identifier representing the javascript function to run, which might be any method of any object. It looks it up in a map and runs it. And the ByteString that got passed from Haskell has to be decoded to a javascript string.

In the Haskell program above, the function is document.alert. Why not pass a ByteString with that through the FFI? Well, you could. But then it would have to eval it. That would make running WASM in the browser be evaling Javascript every time it calls a function. That does not seem like a good idea if the goal is speed. GHC's javascript backend does use Javascript`FFI snippets like that, but there they get pasted into the generated Javascript hairball, so no eval is needed.

So my code has things like get_js_object_method that look up things like Javascript functions and generate identifiers. It also has this:

call_js_function_ByteString_Object :: JSFunction -> B.ByteString -> IO JSObject

Which can be used to call things like document.getElementById that return a javascript object:

getElementById <- get_js_object_method (JSObjectName "document") "getElementById"
canvas <- call_js_function_ByteString_Object getElementById "myCanvas"

Here's the Javascript called by get_js_object_method. It generates a Javascript function that will be used to call the desired method of the object, and allocates an identifier for it, and returns that to the caller.

get_js_objectname_method(ob, osz, nb, nsz) {
    const buffer = globalThis.wasmjsbridge_exports.memory.buffer;
    const objname = decoder.decode(new Uint8Array(buffer, ob, osz));
    const funcname = decoder.decode(new Uint8Array(buffer, nb, nsz));
    const func = function (...args) { return globalThis[objname][funcname](...args) };
    const n = globalThis.wasmjsbridge_counter + 1;
    globalThis.wasmjsbridge_counter = n;
    globalThis.wasmjsbridge_functionmap.set(n, func);
    return n;
},

This does mean that every time a Javascript function id is looked up, some more memory is used on the Javascript side. For more serious uses of this, something would need to be done about that. Lots of other stuff like object value getting and setting is also not implemented, there's no support yet for callbacks, and so on. Still, I'm happy where this has gotten to after 12 hours of work on it.

I might release the reusable parts of this as a Haskell library, although it seems likely that ongoing development of ghc will make it obsolete. In the meantime, clone the git repo to have a play with it.

---

This blog post was sponsored by unqueued on Patreon.

September 20, 2023 01:48 PM

GHC plugin for HLint

GHC plugin for HLint

At work I was recently experimenting with running hlint (the widely used Haskell linting program) as a GHC plugin. One reason why I was interested in this is because we have a large (6000+ module) Haskell codebase at work, and I wanted to see if this would make it cheaper to run hlint on our codebase. Ultimately it did not work out but I built something that we could open source so I polished it up and released it in case other people find it useful. You can find the plugin (named hlint-plugin) on Hackage and on GitHub.

This post will explain the background and motivation behind this work to explain why such a plugin might be potentially useful to other Haskell users.

Introduction to hlint

If you’ve never heard of hlint before, it’s a Haskell source code linting tool that is pretty widely used in the Haskell ecosystem. For example, if you run hlint on the following Haskell file:

main :: IO ()
main = (mempty)

… then you’ll get the following hlint error message:

Main.hs:2:8-15: Warning: Redundant bracket
Found:
  (mempty)
Perhaps:
  mempty
  
1 hint

… telling the user to remove the parentheses¹ from around the mempty.

Integrating hlint

However, hlint is a tool that is not integrated into the compiler, meaning that you have to run it out of band from compilation for it to catch errors. There are a few ways that one can fix this, though:

• Create a script that builds your program and then runs hlint

  This is the simplest possible thing that one can do, but it works and some people do this. It’s the “low-tech” solution.

• Use haskell-language-server or some IDE that plugin that auto-runs hlint

  This is a bit nicer for developers because now they can get rapid feedback (in their editor) as they are authoring the code. For example, haskell-language-server supports an hlint plugin² for this purpose.

• A GHC plugin (what this post is about)

  If you turn hlint into a GHC plugin, then ALL GHC-based Haskell tools automatically incorporate hlint suggestions. For example, ghcid would automatically include hlint suggestions in its output, something that doesn’t work with other approaches to integrate hlint. Similarly, all cabal commands (including cabal build and cabal repl) and all stack commands benefit from a GHC plugin.

Alternatives

I’m not the first person who had this idea of turning hlint into a GHC plugin. The first attempt to do this was hlint-source-plugin, but that was a pretty low-tech solution; it basically ran hlint as an executable on the Haskell source file being processed even though the GHC plugin already has access to the parsed syntax tree.

The second attempt was the splint package. This GHC plugin was really well done (it’s basically exactly how I envisioned this was supposed to work) and the corresponding announcement post does a great job of motivating why hlint benefits from being run as a GHC plugin.

However, the problem is that the splint package was recently abandoned and the last version of GHC it supports is GHC 9.2. Since we use GHC 9.6 at work I decided to essentially revive the splint package so I created the hlint-plugin package which is essentially the successor to splint.

Improvements

hlint-plugin is not too different from what splint did, but the main improvements that hlint-plugin brings are:

• Support for newer versions of GHC

  splint supports GHC versions 8.10, 9.0, and 9.2 whereas hlint-plugin supports GHC versions 9.0, 9.2, 9.4, and 9.6.

• Known-good cabal/stack/nix builds for the plugin

  … see the next section for more details.

• A test suite to verify that the plugin works

  hlint-plugin’s CI actually checks that the plugin works for all supported versions of GHC.

• A simpler work-around to GHC issue #18261

  Basically, I independently stumbled upon the exact same problem that splint encountered, but worked around it in a simpler way. I won’t go into too much detail here other than to point out that you can compare how splint works around this bug with how hlint-plugin works around the bug.

Also, when stress testing hlint-plugin on our internal codebase I discovered an hlint bug which affected some of our modules, and fixed that, so the fix will be in the next release of hlint.

Tricky build stuff

Unfortunately, both splint and hlint-plugin are tricky to correctly install. Why? Because, by default hlint (and ghc-lib-parser-ex) use the ghc-lib and ghc-lib-parser packages by default instead of the ghc API. This is actually a pain in the ass because a GHC plugin needs to be created using the ghc API (i.e. it needs to be a value of type ghc:GHC.Plugins.Plugin). Like, you can use hlint to create a ghc-lib:GHC.Plugins.Plugin and everything will type-check and build, but then when you try to actually run the plugin it will fail.

There is a way to get hlint and ghc-lib-parser-ex to use the ghc API, though! However, you have to build them with non-default cabal configure flags. Specifically, you have to configure hlint with the -f-ghc-lib option and configure ghc-lib-parser-ex with the -fno-ghc-lib option.

To ease things for users I provided a cabal.project file and a flake.nix file⁴ with working builds for hlint-plugin that set all the correct configuration options.

Performance

I mentioned in the introduction that I was hoping for some performance improvements from switching to a plugin but those improvements didn’t materialize. I’ll talk a bit about what I thought would work and why it didn’t pan out for us (even though it still might help for you).

So there are up to three ways that hlint could potentially be faster as a GHC plugin:

• Not having to re-lint modules that haven’t changed

  This is nice (especially when your codebase has 6000+ modules like ours). When you turn hlint into a GHC plugin you only run it whenever GHC recompiles a module and you don’t have to run hlint over your entire codebase after every change.

  However, this was actually not a significant benefit to our company because we already have some scripts which take care of only running hlint on the modules that have changed (according to git). However, it’s still a “nice to have” because it’s architecturally simpler (no need to write that clever script if GHC can take care of detecting changes for us).

• Not having to parse the Haskell code twice

  This is likely a minor performance improvement since parsing is (in my experience) typically not the bottleneck for compiling Haskell code.

• Running hlint while GHC is compiling modules

  What I mean by this is that if hlint is a GHC plugin then it can begin running while the GHC build is ongoing! In large builds (like ours) there are often a large number of cores that go unused and the hlint plugin could potentially exploit those idle cores to do work before the build is done.

  However, in practice this benefit did not pan out and our build didn't really get faster when we enabled hlint-plugin. The time it took to build our codebase with the plugin was essentially the same amount of time as running hlint in a separate step.

Future directions

The hlint-source-plugin repository notes that if hlint were implemented as a GHC plugin (which it now is) then it would fix some of the hacks that hlint has to use:

Currently this plugin simply hooks into the parse stage and calls HLint with a file path. This means HLint will re-parse all source code. The next logical step is to use the actual parse tree, as given to us by GHC, and HLint that. This means that HLint can lose the special logic to run CPP, along with the hacky handling of fixity resolution (we get that done correctly by GHC’s renaming phase).

… because of this I sort of feel that hlint really should be a GHC plugin. It’s understandable why hlint was not initially implemented in this way (since I believe the GHC plugin system didn’t exist back then), but now it sort of feels like a GHC plugin is a much more natural way of integrating hlint.

---

1. I refuse to call parentheses “brackets”.↩︎

2. Note that this is a plugin for haskell-language-server, which is a different type of plugin than a GHC plugin. A haskell-language-server plugin only works with haskell-language-server whereas a GHC plugin works with anything that uses GHC. The two types of plugins are also installed and set up in different ways.↩︎

3. Note that this is a plugin for haskell-language-server, which is a different type of plugin than a GHC plugin. A haskell-language-server plugin only works with haskell-language-server whereas a GHC plugin works with anything that uses GHC. The two types of plugins are also installed and set up in different ways.↩︎

4. I tried to create a working stack.yaml and failed to get it working, but I’d accept a pull request adding a working stack build if someone else has better luck than I did.↩︎

by Gabriella Gonzalez (noreply@blogger.com) at September 19, 2023 09:16 PM

ZuriHac 2023 and GHC Contributors' Workshop: Summary and Materials

Many of us at Well-Typed enjoyed travelling to Zurich earlier this year for ZuriHac 2023 and the GHC Contributors’ Workshop. Thanks to the organisers of both these events, and to all those who attended for the great discussions.

The videos of our sessions as well as the materials used in them are available online, so those who could not attend can watch the talks by following the links below.

ZuriHac Workshop: Lazy Evaluation by Andres Löh

Watch video on YouTube | Slides | Code repository

As in previous years, Well-Typed were happy to support ZuriHac by offering a free training workshop:

In this workshop, we are going to take a deep dive into lazy evaluation, looking at several examples and reasoning about how they get evaluated. The goal is to develop a strong understanding of how Haskell’s evaluation strategy works. Hopefully, we will see why laziness is a compelling idea with a lot of strong points, while also learning how some common sources of space leaks can be avoided.

The workshop will be accessible to anyone who has mastered the basics of Haskell and is looking to understand the language in more depth, whether they are a student or professional developer. We are not going to use any advanced features of the language, and you do not have to be a Haskell expert to attend!

Check out the ZuriHac 2023 YouTube playlist for more great talks from ZuriHac.

GHC Contributors’ Workshop

The GHC Contributors’ Workshop was organised by the Haskell Foundation as a way to introduce people to GHC development. As sponsors of the Haskell Foundation and regular contributors to GHC, Well-Typed sent several speakers to the event:

• Ben Gamari: GHC’s runtime system (video, slides)
• Duncan Coutts: The GHC packaging ecosystem (video, slides)
• Sam Derbyshire: GHC’s renamer (video, slides)
• Zubin Duggal: Haskell Language Server (video, slides)

The GHC Contributor’s Workshop playlist has all the talks from a variety of other GHC contributors. You can also read the retrospective report from David Christiansen.

More from Well-Typed

Why not check out the Haskell Unfolder, our YouTube series about all things Haskell? Or you can find talks presented by all our consultants by subscribing to our YouTube Channel.

If you are interested in our courses or other services, check our Training page, Consultancy page, or just send us an email.

by christine, adam, andres, ben, duncan, sam, zubin at September 19, 2023 12:00 AM

GHC 9.8.1-alpha4 is now available

GHC 9.8.1-alpha4 is now available

bgamari - 2023-09-19

The GHC developers are very pleased to announce the availability of the fourth alpha prerelease of GHC 9.8.1. Binary distributions, source distributions, and documentation are available at downloads.haskell.org.

GHC 9.8 will bring a number of new features and improvements, including:

• Preliminary support the TypeAbstractions language extension, allowing types to be bound in type declarations.

• Support for the ExtendedLiterals extension, providing more consistent support for non-word-sized numeric literals in the surface language

• Improved rewrite rule matching behavior, allowing limited matching of higher-order patterns

• Better support for user-defined warnings by way of the WARNING pragma

• The introduction of the new GHC.TypeError.Unsatisfiable constraint, allowing more predictable user-defined type errors

• Implementation of the export deprecation proposal, allowing module exports to be marked with DEPRECATE pragmas

• The addition of build semaphore support for parallel compilation, allowing better use of parallelism across GHC builds

• More efficient representation of info table provenance information, reducing binary sizes by nearly 80% in some cases when -finfo-table-map is in use

A full accounting of changes can be found in the release notes. This alpha includes roughly 40 new commits relative to alpha 3, including what we believe should be nearly the last changes to GHC’s boot libraries.

We would like to thank GitHub, IOG, the Zw3rk stake pool, Well-Typed, Tweag I/O, Serokell, Equinix, SimSpace, the Haskell Foundation, and other anonymous contributors whose on-going financial and in-kind support has facilitated GHC maintenance and release management over the years. Finally, this release would not have been possible without the hundreds of open-source contributors whose work comprise this release.

As always, do give this release a try and open a ticket if you see anything amiss.

by ghc-devs at September 19, 2023 12:00 AM

Setting up emacs-openai/chatgpt

Yesterday I decided to try to make more use of the ChatGPT account I have. What prompted it mostly was that I recalled that my employer has a paid subscription and that if we use it enough they'll get us access to ChatGPT4.

After a bit of research¹ I decided to start with emacs-open/chatgpg. However, as I found the instructions slightly lacking I'm sharing my setup.

The instructions for straight.el fail to mention that one needs the openai package too.

(use-package openai
  :straight (openai :type git :host github :repo "emacs-openai/openai"))

The complete declaration for use-package ended up looking like this:

(use-package chatgpt
  :straight (chatgpt :type git :host github :repo "emacs-openai/chatgpt")
  :requires openai
  :config
  (setq openai-key #'openai-key-auth-source))

Oh, and don't forget to put an entry into `~/.authinfo.gpg`. Something like this should do it

machine api.openai.com login <anything> password <your key>

Footnotes:

¹

I found Alex Kehayias' note to be a good starting point.

Tags: emacs openai chatgpt

September 16, 2023 04:22 AM

Horizontal and vertical complexity

Note: The jumping-off place for this article is a conference talk which I did not attend. You should understand this article as rambling musings on related topics, not as a description of the talk or a response to it or a criticism of it or as a rebuttal of its ideas.

---

A co-worker came back from PyCon reporting on a talk called “Wrapping up the Cruft - Making Wrappers to Hide Complexity”. He said:

The talk was focussed on hiding complexity for educational purposes. … The speaker works for an educational organisation … and provided an example of some code for blinking lights on a single board machine. It was 100 lines long, you had to know about a bunch of complexity that required you to have some understanding of the hardware, then an example where it was the initialisation was wrapped up in an import and for the kids it was as simple as selecting a colour and which led to light up. And how much more readable the code was as a result.

The better we can hide how the sausage is made the more approachable and easier it is for those who build on it to be productive. I think it's good to be reminded of this lesson.

I was on fully board with this until the last bit, which gave me an uneasy feeling. Wrapping up code this way reduces horizontal complexity in that it makes the top level program shorter and quicker. But it increases vertical complexity because there are now more layers of function calling, more layers of interface to understand, and more hidden magic behavior. When something breaks, your worries aren't limited to understanding what is wrong with your code. You also have to wonder about what the library call is doing. Is the library correct? Are you calling it correctly? The difficulty of localizing the bug is larger, and when there is a problem it may be in some module that you can't see, and that you may not know exists.

Good interfaces successfuly hide most of this complexity, but even in the best instances the complexity has only been hidden, and it is all still there in the program. An uncharitable description would be that the complexity has been swept under the carpet. And this is the best case! Bad interfaces don't even succeed in hiding the complexity, which keeps leaking upward, like a spreading stain on that carpet, one that warns of something awful underneath.

Advice about how to write programs bangs the same drum over and over and over:

• Reduce complexity
• Do the simplest thing that could possibly work
• You ain't gonna need it
• Explicit is better than implicit

But here we have someone suggesting the opposite. We should be extremely wary.

There is always a tradeoff. Leaky abstractions can increase the vertical complexity by more than they decrease the horizontal complexity. Better-designed abstractions can achieve real wins.

It’s a hard, hard problem. That’s why they pay us the big bucks.

Ratchet effects

This is a passing thought that I didn't consider carefully enough to work into the main article.

A couple of years ago I wrote an article called Creeping featurism and the ratchet effect about how adding features to software, or adding more explanations to the manual, is subject to a “ratcheting force”. The benefit of the change is localized and easy to imagine:

You can imagine a confused person in your head, someone who happens to be confused in exactly the right way, and who is miraculously helped out by the presence of the right two sentences in the exact right place.

But the cost of the change is that the manual is now a tiny bit larger. It doesn't affect any specific person. But it imposes a tiny tax on everyone who uses the manual.

Similarly adding a feature to software has an obvious benefit, so there's pressure to add more features, and the costs are hidden, so there's less pressure in the opposite direction.

And similarly, adding code and interfaces and libraries to software has an obvious benefit: look how much smaller the top-level code has become! But the cost, that the software is 0.0002% more complex, is harder to see. And that cost increases imperceptibly, but compounds exponentially. So you keep moving in the same direction, constantly improving the software architecture, until one day you wake up and realize that it is unmaintainable. You are baffled. What could have gone wrong?

Kent Beck says, “design isn't free”.

Anecdote

The original article is in the context of a class for beginners where the kids just want to make the LEDs light up. If I understand the example correctly, in this context I would probably have made the same choice for the same reason.

But I kept thinking of an example where I made the opposite choice. I taught an introduction to programming in C class about thirty years ago. The previous curriculum had considered pointers an advanced topic and tried to defer them to the middle of the semester. But the author of the curriculum had had a big problem: you need pointers to deal with scanf. What to do?

The solution chosen by the previous curriculum was to supply the students with a library of canned input functions like

    int get_int(void);   /* Read an integer from standard input */

These used scanf under the hood. (Under the carpet, one might say.) But all the code with pointers was hidden.

I felt this was a bad move. Even had the library been a perfect abstraction (it wasn't) and completely bug-free (it wasn't) it would still have had a giant flaw: Every minute of time the students spent learning to use this library was a minute wasted on something that would never be of use and that had no intrinsic value. Every minute of time spent on this library was time that could have been spent learning to use pointers! People programming in C will inevitably have to understand pointers, and will never have to understand this library.

My co-worker from the first part of this article wrote:

The better we can hide how the sausage is made the more approachable and easier it is for those who build on it to be productive.

In some educational contexts, I think this is a good idea. But not if you are trying to teach people sausage-making!

by Mark Dominus (mjd@plover.com) at September 13, 2023 01:48 PM

The Haskell Unfolder Episode 11: Haskell at ICFP

Today, 2023-09-13, at 1830 UTC (11:30 am PDT, 2:30 pm EDT, 7:30 pm BST, 20:30 CEST, …) we are streaming the eleventh episode of the Haskell Unfolder live on YouTube.

The Haskell Unfolder Episode 11: Haskell at ICFP

In this episode, Andres and Edsko will talk about Edsko’s visit to ICFP (the International Conference on Functional Programming), the Haskell Symposium, and HIW (the Haskell Implementors’ Workshop) from 4-9 September 2023 in Seattle. We will highlight a few select papers from these events.

About the Haskell Unfolder

The Haskell Unfolder is a YouTube series about all things Haskell hosted by Edsko de Vries and Andres Löh, with episodes appearing approximately every two weeks. All episodes are live-streamed, and we try to respond to audience questions. All episodes are also available as recordings afterwards.

We have a GitHub repository with code samples from the episodes.

And we have a public Google calendar (also available as ICal) listing the planned schedule.

by andres, edsko at September 13, 2023 12:00 AM

Graphs, Kites and Darts – and Theorems

We continue our exploration of properties of Penrose’s aperiodic tilings with kites and darts using Haskell and Haskell Diagrams.

In this blog we discuss some interesting properties we have discovered concerning the , , and operations along with some proofs.

Index

1. Quick Recap (including operations , , on Tgraphs)
2. Composition Problems and a Compose Force Theorem (composition is not a simple inverse to decomposition)
3. Perfect Composition Theorem (establishing relationships between , , )
4. Multiple Compositions (extending the Compose Force theorem for multiple compositions)
5. Proof of the Compose Force Theorem (showing is total on forced Tgraphs)

1. Quick Recap

Haskell diagrams allowed us to render finite patches of tiles easily as discussed in Diagrams for Penrose tiles. Following a suggestion of Stephen Huggett, we found that the description and manipulation of such tilings is greatly enhanced by using planar graphs. In Graphs, Kites and Darts we introduced a specialised planar graph representation for finite tilings of kites and darts which we called Tgraphs (tile graphs). These enabled us to implement operations that use neighbouring tile information and in particular operations , , and .

For ease of reference, we reproduce the half-tiles we are working with here.

Figure 1 shows the right-dart (RD), left-dart (LD), left-kite (LK) and right-kite (RK) half-tiles. Each has a join edge (shown dotted) and a short edge and a long edge. The origin vertex is shown red in each case. The vertex at the opposite end of the join edge from the origin we call the opp vertex, and the remaining vertex we call the wing vertex.

If the short edges have unit length then the long edges have length (the golden ratio) and all angles are multiples of (a tenth turn) with kite halves having a two 2s and a 1, and dart halves having a 3 and two 1s. This geometry of the tiles is abstracted away from at the graph representation level but used when checking validity of tile additions and by the drawing functions.

There are rules for how the tiles can be put together to make a legal tiling (see e.g. Diagrams for Penrose tiles). We defined a Tgraph (in Graphs, Kites and Darts) as a list of such half-tiles which are constrained to form a legal tiling but must also be connected with no crossing boundaries (see below).

As a simple example consider kingGraph (2 kites and 3 darts round a king vertex). We represent each half-tile as a TileFace with three vertex numbers, then apply makeTgraph to the list of ten Tilefaces. The function makeTgraph :: [TileFace] -> Tgraph performs the necessary checks to ensure the result is a valid Tgraph.

kingGraph :: Tgraph
kingGraph = makeTgraph 
  [LD (1,2,3),RD (1,11,2),LD (1,4,5),RD (1,3,4),LD (1,10,11)
  ,RD (1,9,10),LK (9,1,7),RK (9,7,8),RK (5,7,1),LK (5,6,7)
  ]

To view the Tgraph we simply form a diagram (in this case 2 diagrams horizontally separated by 1 unit)

  hsep 1 [drawjLabelled kingGraph, draw kingGraph]

and the result is shown in figure 2 with labels and dashed join edges (left) and without labels and join edges (right).

The boundary of the Tgraph consists of the edges of half-tiles which are not shared with another half-tile, so they go round untiled/external regions. The no crossing boundary constraint (equivalently, locally tile-connected) means that a boundary vertex has exactly two incident boundary edges and therefore has a single external angle in the tiling. This ensures we can always locally determine the relative angles of tiles at a vertex. We say a collection of half-tiles is a valid Tgraph if it constitutes a legal tiling but also satisfies the connectedness and no crossing boundaries constraints.

Our key operations on Tgraphs are , , and which are illustrated in figure 3.

Figure 3 shows the kingGraph with its decomposition above it (left), the result of forcing the kingGraph (right) and the composition of the forced kingGraph (bottom right).

Decompose

An important property of Penrose dart and kite tilings is that it is possible to divide the half-tile faces of a tiling into smaller half-tile faces, to form a new (smaller scale) tiling.

Figure 4 illustrates the decomposition of a left-dart (top row) and a left-kite (bottom row). With our Tgraph representation we simply introduce new vertices for dart and kite long edges and kite join edges and then form the new faces using these. This does not involve any geometry, because that is taken care of by drawing operations.

Force

Figure 5 illustrates the rules used by our operation (we omit a mirror-reflected version of each rule).

In each case the yellow half-tile is added in the presence of the other half-tiles shown. The yellow half-tile is forced because, by the legal tiling rules, there is no choice for adding a different half-tile on the edge where the yellow tile is added.

We call a Tgraph correct if it represents a tiling which can be continued infinitely to cover the whole plane without getting stuck, and incorrect otherwise. Forcing involves adding half-tiles by the illustrated rules round the boundary until either no more rules apply (in which case the result is a forced Tgraph) or a stuck tiling is encountered (in which case an incorrect Tgraph error is raised). Hence is a partial function but total on correct Tgraphs.

Compose: This is discussed in the next section.

2. Composition Problems and a Theorem

Compose Choices

For an infinite tiling, composition is a simple inverse to decomposition. However, for a finite tiling with boundary, composition is not so straight forward. Firstly, we may need to leave half-tiles out of a composition because the necessary parts of a composed half-tile are missing. For example, a half-dart with a boundary short edge or a whole kite with both short edges on the boundary must necessarily be excluded from a composition. Secondly, on the boundary, there can sometimes be a problem of choosing whether a half-dart should compose to become a half-dart or a half-kite. This choice in composing only arises when there is a half-dart with its wing on the boundary but insufficient local information to determine whether it should be part of a larger half-dart or a larger half-kite.

In the literature (see for example 1 and 2) there is an often repeated method for composing (also called inflating). This method always make the kite choice when there is a choice. Whilst this is a sound method for an unbounded tiling (where there will be no choice), we show that this is an unsound method for finite tilings as follows.

Clearly composing should preserve correctness. However, figure 6 (left) shows a correct Tgraph which is a forced queen, but the kite-favouring composition of the forced queen produces the incorrect Tgraph shown in figure 6 (centre). Applying our function to this reveals a stuck tiling and reports an incorrect Tgraph.

Our algorithm (discussed in Graphs, Kites and Darts) detects dart wings on the boundary where there is a choice and classifies them as unknowns. Our composition refrains from making a choice by not composing a half dart with an unknown wing vertex. The rightmost Tgraph in figure 6 shows the result of our composition of the forced queen with the half-tile faces left out of the composition (the remainder faces) shown in green. This avoidance of making a choice (when there is a choice) guarantees our composition preserves correctness.

Compose is a Partial Function

A different composition problem can arise when we consider Tgraphs that are not decompositions of Tgraphs. In general, is a partial function on Tgraphs.

Figure 7 shows a Tgraph (left) with its sucessful composition (centre) and the half-tile faces that would result from a second composition (right) which do not form a valid Tgraph because of a crossing boundary (at vertex 6). Thus composition of a Tgraph may fail to produce a Tgraph when the resulting faces are disconnected or have a crossing boundary.

However, we claim that is a total function on forced Tgraphs.

Compose Force Theorem

Theorem: Composition of a forced Tgraph produces a valid Tgraph.

We postpone the proof (outline) for this theorem to section 5. Meanwhile we use the result to establish relationships between , , and in the next section.

3. Perfect Composition Theorem

In Graphs, Kites and Darts we produced a diagram showing relationships between multiple decompositions of a dart and the forced versions of these Tgraphs. We reproduce this here along with a similar diagram for multiple decompositions of a kite.

In figure 8 we show separate (apparently) commuting diagrams for the dart and for the kite. The bottom rows show the decompositions, the middle rows show the result of forcing the decompositions, and the top rows illustrate how the compositions of the forced Tgraphs work by showing both the composed faces (black edges) and the remainder faces (green edges) which are removed in the composition. The diagrams are examples of some commutativity relationships concerning , and which we will prove.

It should be noted that these diagrams break down if we consider only half-tiles as the starting points (bottom right of each diagram). The decomposition of a half-tile does not recompose to its original, but produces an empty composition. So we do not even have in these cases. Forcing the decomposition also results in an empty composition. Clearly there is something special about the depicted cases and it is not merely that they are wholetile complete because the decompositions are not wholetile complete. [Wholetile complete means there are no join edges on the boundary, so every half-tile has its other half.]

Below we have captured the properties that are sufficient for the diagrams to commute as in figure 8. In the proofs we use a partial ordering on Tgraphs (modulo vertex relabelling) which we define next.

Partial ordering of Tgraphs

If and are both valid Tgraphs and consists of a subset of the (half-tile) faces of we have

which gives us a partial order on Tgraphs. Often, though, is only isomorphic to a subset of the faces of , requiring a vertex relabelling to become a subset. In that case we write

which is also a partial ordering and induces an equivalence of Tgraphs defined by

in which case and are isomorphic as Tgraphs.

Both and are monotonic with respect to meaning:

We also have is monotonic, but only when restricted to correct Tgraphs. Also, when restricted to correct Tgraphs, we have is non decreasing because it only adds faces:

and is idempotent (forcing a forced correct Tgraph leaves it the same):

Composing perfectly and perfect compositions

Definition: A Tgraph composes perfectly if all faces of are composable (i.e there are no remainder faces of when composing).

We note that the composed faces must be a valid Tgraph (connected with no crossing boundaries) if all faces are included in the composition because has those properties. Clearly, if composes perfectly then

In general, for arbitrary where the composition is defined, we only have

Definition: A Tgraph is a perfect composition if composes perfectly.

Clearly if is a perfect composition then

(We could use equality here because any new vertex labels introduced by will be removed by ). In general, for arbitrary ,

Lemma 1: is a perfect composition if and only if has the following 2 properties:

1. every half-kite with a boundary join has either a half-dart or a whole kite on the short edge, and
2. every half-dart with a boundary join has a half-kite on the short edge,

(Proof outline:) Firstly note that unknowns in (= ) can only come from boundary joins in . The properties 1 and 2 guarantee that has no unknowns. Since every face of has come from a decomposed face in , there can be no faces in that will not recompose, so will compose perfectly to . Conversely, if is a perfect composition, its decomposition can have no unknowns. This implies boundary joins in must satisfy properties 1 and 2.

(Note: a perfect composition may have unknowns even though its decomposition has none.)

It is easy to see two special cases:

1. If is wholetile complete then is a perfect composition.

   Proof: Wholetile complete implies no boundary joins which implies properties 1 and 2 in lemma 1 which implies is a perfect composition.

2. If is a decomposition then is a perfect composition.

   Proof: If is a decomposition, then every half-dart has a half-kite on the short edge which implies property 2 of lemma 1. Also, any half-kite with a boundary join in must have come from a decomposed half-dart since a decomposed half-kite produces a whole kite with no boundary kite join. So the half-kite must have a half-dart on the short edge which implies property 1 of lemma 1. The two properties imply is a perfect composition.

We note that these two special cases cover all the Tgraphs in the bottom rows of the diagrams in figure 8. So the Tgraphs in each bottom row are perfect compositions, and furthermore, they all compose perfectly except for the rightmost Tgraphs which have empty compositions.

In the following results we make the assumption that a Tgraph is correct, which guarantees that when is applied, it terminates with a correct Tgraph. We also note that preserves correctness as does (provided the composition is defined).

Lemma 2: If is a forced, correct Tgraph then

(Proof outline:) The proof uses a case analysis of boundary and internal vertices of . For internal vertices we just check there is no change at the vertex after using figure 11 (plus an extra case for the forced star). For boundary vertices we check local contexts similar to those depicted in figure 10 (but including empty composition cases). This reveals there is no local change of the boundary at any boundary vertex, and since this is true for all boundary vertices, there can be no global change. (We omit the full details).

Lemma 3: If is a perfect composition and a correct Tgraph, then

(Proof outline:) The proof is by analysis of each possible force rule applicable on a boundary edge of and checking local contexts to establish that (i) the result of applying to the local context must include the added half-tile, and (ii) if the added half tile has a new boundary join, then the result must include both halves of the new half-tile. The two properties of perfect compositions mentioned in lemma 1 are critical for the proof. However, since the result of adding a single half-tile may break the condition of the Tgraph being a pefect composition, we need to arrange that half-tiles are completed first then each subsequent half-tile addition is paired with its wholetile completion. This ensures the perfect composition condition holds at each step for a proof by induction. [A separate proof is needed to show that the ordering of applying force rules makes no difference to a final correct Tgraph (apart from vertex relabelling)].

Lemma 4 If composes perfectly and is a correct Tgraph then

Proof: Assume composes perfectly and is a correct Tgraph. Since is non-decreasing (with respect to on correct Tgraphs)

and since is monotonic

Since composes perfectly, the left hand side is just , so

and since is monotonic (with respect to on correct Tgraphs)

For the opposite direction, we substitute for in lemma 3 to get

Then, since , we have

Apply to both sides (using monotonicity)

For any for which the composition is defined we have so we get

Now apply to both sides and note to get

Combining this with (*) above proves the required equivalence.

Theorem (Perfect Composition): If composes perfectly and is a correct Tgraph then

Proof: Assume composes perfectly and is a correct Tgraph. By lemma 4 we have

Applying to both sides, gives

Now by lemma 2, with , the right hand side is equivalent to

which establishes the result.

Corollaries (of the perfect composition theorem):

1. If is a perfect composition and a correct Tgraph then

   

   Proof: Let (so ) in the theorem.

   [This result generalises lemma 2 because any correct forced Tgraph is necessarily wholetile complete and therefore a perfect composition, and .]

2. If is a perfect composition and a correct Tgraph then

   

   Proof: Apply to both sides of the previous corollary and note that

   

   provided the composition is defined, which it must be for a forced Tgraph by the Compose Force theorem.

3. If is a perfect composition and a correct Tgraph then

   

   Proof: Apply to both sides of the previous corollary noting is monotonic and idempotent for correct Tgraphs

   

   From the fact that is non decreasing and and are monotonic, we also have

   

   Hence combining these two sub-Tgraph results we have

   

   

It is important to point out that if is a correct Tgraph and is a perfect composition then this is not the same as composes perfectly. It could be the case that has more faces than and so could have unknowns. In this case we can only prove that

As an example where this is not an equivalence, choose to be a star. Then its composition is the empty Tgraph (which is still a pefect composition) and so the left hand side is the empty Tgraph, but the right hand side is a sun.

Perfectly composing generators

The perfect composition theorem and lemmas and the three corollaries justify all the commuting implied by the diagrams in figure 8. However, one might ask more general questions like: Under what circumstances do we have (for a correct forced Tgraph )

Definition A generator of a correct forced Tgraph is any Tgraph such that and .

We can now state that

Corollary If a correct forced Tgraph has a generator which composes perfectly, then

Proof: This follows directly from lemma 4 and the perfect composition theorem.

As an example where the required generator does not exist, consider the rightmost Tgraph of the middle row in figure 9. It is generated by the Tgraph directly below it, but it has no generator with a perfect composition. The Tgraph directly above it in the top row is the result of applying which has lost the leftmost dart of the Tgraph.

We could summarise this section by saying that can lose information which cannot be recovered by a subsequent and, similarly, can lose information which cannot be recovered by a subsequent . We have defined perfect compositions which are the Tgraphs that do not lose information when decomposed and Tgraphs which compose perfectly which are those that do not lose information when composed. Forcing does the same thing at each level of composition (that is it commutes with composition) provided information is not lost when composing.

4. Multiple Compositions

We know from the Compose Force theorem that the composition of a Tgraph that is forced is always a valid Tgraph. In this section we use this and the results from the last section to show that composing a forced, correct Tgraph produces a forced Tgraph.

First we note that:

Lemma 5: The composition of a forced, correct Tgraph is wholetile complete.

Proof: Let where is a forced, correct Tgraph. A boundary join in implies there must be a boundary dart wing of the composable faces of . (See for example figure 4 where this would be vertex 2 for the half dart case, and vertex 5 for the half-kite face). This dart wing cannot be an unknown as the half-dart is in the composable faces. However, a known dart wing must be either a large kite centre or a large dart base and therefore internal in the composable faces of (because of the force rules) and therefore not on the boundary in . This is a contradiction showing that can have no boundary joins and is therefore wholetile complete.

Theorem: The composition of a forced, correct Tgraph is a forced Tgraph.

Proof: Let for some forced, correct Tgraph , then is wholetile complete (by lemma 5) and therefore a perfect composition. Let , so composes perfectly (). By the perfect composition theorem we have

We also have

Applying to both sides, noting that is monotonic and the identity on forced Tgraphs, we have

Applying to both sides, noting that is monotonic, we have

By (**) above, the left hand side is equivalent to so we have

but since we also have ( being non-decreasing)

we have established that

which means is a forced Tgraph.

This result means that after forcing once we can repeatedly compose creating valid Tgraphs until we reach the empty Tgraph.

We can also use lemma 5 to establish the converse to a previous corollary:

Corollary If a correct forced Tgraph satisfies:

then has a generator which composes perfectly.

Proof: By lemma 5, is wholetile complete and hence a perfect composition. This means that composes perfectly and it is also a generator for because

5. Proof of the Compose Force theorem

Theorem (Compose Force): Composition of a forced Tgraph produces a valid Tgraph.

Proof: For any forced Tgraph we can construct the composed faces. For the result to be a valid Tgraph we need to show no crossing boundaries and connectedness for the composed faces. These are proved separately by case analysis below.

Proof of no crossing boundaries

Assume is a forced Tgraph and that it has a non-empty set of composed faces (we can ignore cases where the composition is empty as the empty Tgraph is valid). Consider a vertex v in the composed faces of and first take the case that v is on the boundary of . We consider the possible local contexts for a vertex v on a forced Tgraph boundary and the nature of the composed faces at v in each case.

Figure 10 shows local contexts for a boundary vertex v in a forced Tgraph where the composition is non-empty. In each case v is shown as a red dot, and the composition is shown filled yellow. The cases for v are shown in rows: the first row is for dart origins, the second row is for kite origins, the next two rows are for kite wings, and the last two rows are for kite opps. The dart wing cases are a subset of the kite opp cases, so not repeated, and dart opp vertices are excluded because they cannot be on the boundary of a forced Tgraph. We only show left-hand versions, so there is a mirror symmetric set for right-hand versions.

It is easy to see that there are no crossing boundaries of the composed faces at v in each case. Since any boundary vertex of any forced Tgraph (with a non-empty composition) must match one of these local context cases around the vertex, we can conclude that a boundary vertex of cannot become a crossing boundary in .

Next take the case where v is an internal vertex of .

Figure 11 shows relationships between the forced Tgraphs of the 7 (internal) vertex types (plus a kite at the top right). The red faces are those around the vertex type and the black faces are those produced by forcing (if any). Each forced Tgraph has its composition directly above with empty compositions for the top row. We note that a (forced) star, jack, king, and queen vertex remains an internal vertex in the respective composition so cannot become a crossing boundary vertex. A deuce vertex becomes the centre of a larger kite and is no longer present in the composition (top right). That leaves cases for the sun vertex and ace vertex (=fool vertex). The sun Tgraph (sunGraph) and fool Tgraph (fool) consist of just the red faces at the respective vertex (shown top left and top centre). These both have empty compositions when there is no surrounding context. We thus need to check possible forced local contexts for sunGraph and fool.

The fool case is simple and similar to a duece vertex in that it is never part of a composition. [To see this consider inverting the decomposition arrows shown in figure 4. In both cases we see the half-dart opp vertex (labelled 4 in figure 4) is removed].

For the sunGraph there are only 7 local forced context cases to consider where the sun vertex is on the boundary of the composition.

Six of these are shown in figure 12 (the missing one is just a mirror reflection of the fourth case). Again, the relevant vertex v is shown as a red dot and the composed faces are shown filled yellow, so it is easy to check that there is no crossing boundary of the composed faces at v in each case. Every forced Tgraph containing an internal sun vertex where the vertex is on the boundary of the composition must match one of the 7 cases locally round the vertex.

Thus no vertex from can become a crossing boundary vertex in the composed faces and since the vertices of the composed faces are a subset of those of , we can have no crossing boundary vertex in the composed faces.

Proof of Connectedness

Assume is a forced Tgraph as before. We refer to the half-tile faces of that get included in the composed faces as the composable faces and the rest as the remainder faces. We want to prove that the composable faces are connected as this will imply the composed faces are connected.

As before we can ignore cases where the set of composable faces is empty, and assume this is not the case. We study the nature of the remainder faces of . Firstly, we note:

Lemma (remainder faces)

The remainder faces of are made up entirely of groups of half-tiles which are either:

1. Half-fools (= a half dart and both halves of the kite attached to its short edge) where the other half-fool is entirely composable faces, or
2. Both halves of a kite with both short edges on the () boundary (so they are not part of a half-fool) where only the origin is in common with composable faces, or
3. Whole fools with just the shared kite origin in common with composable faces.

These 3 cases of remainder face groups are shown in figure 13. In each case the border in common with composable faces is shown yellow and the red edges are necessarily on the boundary of (the black boundary could be on the boundary of or shared with another reamainder face group). [A mirror symmetric version for the first group is not shown.] Examples can be seen in e.g. figure 12 where the first Tgraph has four examples of case 1, and two of case 2, the second has six examples of case 1 and two of case 2, and the fifth Tgraph has an example of case 3 as well as four of case 1. [We omit the detailed proof of this lemma which reasons about what gets excluded in a composition after forcing. However, all the local context cases are included in figure 14 (left-hand versions), where we only show those contexts where there is a non-empty composition.]

We note from the (remainder faces) lemma that the common boundary of the group of remainder faces with the composable faces (shown yellow in figure 13) is just a single vertex in cases 2 and 3. In case 1, the common boundary is just a single edge of the composed faces which is made up of 2 adjacent edges of the composable faces that constitute the join of two half-fools.

This means each (remainder face) group shares boundary with exactly one connected component of the composable faces.

Next we establish that if two (remainder face) groups are connected they must share boundary with the same connected component of the composable faces. We need to consider how each (remainder face) group can be connected with a neighbouring such group. It is enough to consider forced contexts of boundary dart long edges (for cases 1 and 3) and boundary kite short edges (for case 2). The cases where the composition is non-empty all appear in figure 14 (left-hand versions) along with boundary kite long edges (middle two rows) which are not relevant here.

We note that, whenever one group of the remainder faces (half-fool, whole-kite, whole-fool) is connected to a neighbouring group of the remainder faces, the common boundary (shared edges and vertices) with the compososable faces is also connected, forming either 2 adjacent composed face boundary edges (= 4 adjacent edges of the composable faces), or a composed face boundary edge and one of its end vertices, or a single composed face boundary vertex.

It follows that any connected collection of the remainder face groups shares boundary with a unique connected component of the composable faces. Since the collection of composable and remainder faces together is connected ( is connected) the removal of the remainder faces cannot disconnect the composable faces. For this to happen, at least one connected collection of remainder face groups would have to be connected to more than one connected component of composable faces.

This establishes connectedness of any composition of a forced Tgraph, and this completes the proof of the Compose Force theorem.

References

[1] Martin Gardner (1977) MATHEMATICAL GAMES. Scientific American, 236(1), (pages 110 to 121). http://www.jstor.org/stable/24953856

[2] Grünbaum B., Shephard G.C. (1987) Tilings and Patterns. W. H. Freeman and Company, New York. ISBN 0-7167-1193-1 (Hardback) (pages 540 to 542).

by readerunner at September 12, 2023 01:33 PM

The Killer Whale Dagger

Last month Toph and I went on vacation to Juneau, Alaska. I walked up to look at the glacier, but mostly we just enjoyed the view and the cool weather. But there were some surprises.

One day we took a cab downtown, and our driver, Edwell John, asked where we were visiting from, as cab drivers do. We said we were from Philadelphia, and he told us he had visited Philadelphia himself.

“I was repatriating Native artifacts,” he said.

Specifically, he had gone to the University of Pennsyvania Museum, to take back the Killer Whale Dagger named Keet Gwalaa. This is a two foot long dagger that was forged by Tlingit people in the 18th century from meteorite steel.

This picture comes from the Penn Museum. (I think this isn't the actual dagger, but a reproduction they had made after M. John took back the original.)

This was very exciting! I asked “where is the dagger now?” expecting that it had been moved to a museum in Angoon or something.

“Oh, I have it,” he said.

I was amazed. “What, like on you?”

“No, at my house. I'm the clan leader of the Killer Whale clan.”

Then he took out his phone and showed us a photo of himself in his clan leader garb, carrying the dagger.

Here's an article about M. John visiting the Smithsonian to have them 3-D scan the Killer Whale hat. Then the Smithsonian had a replica hat made from the scan.

by Mark Dominus (mjd@plover.com) at September 10, 2023 05:04 PM

Using emacs for the scrollback in terminal multiplexers

I should start with saying that I still don't really know if this is a good idea or not, but it feels like it's worth trying out at least.

An irritating limitation in Zellij, and a possible solution

After seeing it mentioned in an online community I thought it might be worth trying out. I'm not really disappointed with tmux, I've been using it for years but I actually only use a small part of what it can do. I create tabs, sometimes create panes, and I regularly use the scollback functionality to copy output of commands I've run earlier.

Unfortunately, as is reported in a ticket, Zellij can't select and copy using the keyboard. From the discussion in that ticket it seems unlikely it ever will be able to. After finding that out I resigned to staying with Tmux – I'm not ready to go back to using a pointing device to select and copy text in my terminal!

When I was biking to the pool yesterday I realised a thing though: I'm already using a tool that is very good at manipulating text using the keyboard. Of course I'm talking about Emacs! So if I can just make Emacs start up quickly enough I ought to be able to use it for searching, selecting and copying from the scrollback buffer. I haven't found a way to do this in Tmu= yet, but Zellij has EditScrollBack so I can at least try it out.

A nice benefit is that I can cut back on the number of different shortcuts I use daily.

My slimmed down Emacs config

My current Emacs config starts up in less than 2s, which is good enough as I normally start Emacs at most a few times per day. However, if I have to wait 2s to open the scrollback buffer I suspect I'll tire very quickly and abandon the experiment. So I took my ordinary config and slimmed it down. Cutting away things that weren't related to navigation and searching.

The list of packages is not very long:

• straight
• use-package
• evil
• general
• which-key
• vertico
• orderless
• marginalia
• consult

The first 5 are for usability in general, and the last 4 are bring in the functions I use for searching through text.

The resulting config starts in less than ¼s. That's more than acceptable, I find.

Copying to the Wayland clipboard

It turns out that copying with `y` in evil does the right thing by default and the copied text ends up in the clipboard without any special configuration.

From Tmux I'm used to being thrown out of copy-mode after copying something. While that's sometimes irritating, it's at other times exactly what I want. Given that evil-yank does the right thing it was easy to write a function for it:

(defun se/yank-n-kill (beg end)
  (interactive "r")
  (evil-yank beg end)
  (kill-emacs))

The config files

I'm keeping my dot-files in a private repo, but I put a snapshot of the Emacs and Zellij config in a snippet.

Tags: emacs tmux zellij

September 10, 2023 11:17 AM

Owned values and Futures in Rust

Let's write a simple tokio-powered program that will download the contents of an HTTP response body using reqwest and print it to stdout. We'll take the URL to download on the command line using clap. This might look something like the following:

use anyhow::Result;
use clap::Parser;

#[derive(clap::Parser)]
struct Opt {
    url: String,
}

#[tokio::main]
async fn main() -> Result<()> {
    let Opt { url } = Opt::parse();
    let body = reqwest::get(url).await?.text().await?;
    println!("{body}");
    Ok(())
}

All good, but let's (arguably) improve our program by extracting the logic for the download-and-print to a helper function:

#[tokio::main]
async fn main() -> Result<()> {
    let Opt { url } = Opt::parse();
    download_and_print(&url).await?;
    Ok(())
}

async fn download_and_print(url: &str) -> Result<()> {
    let body = reqwest::get(url).await?.text().await?;
    println!("{body}");
    Ok(())
}

I've followed general best practices here and taken the url as a string slice instead of an owned string. Now, it's really easy to extend this program to support multiple URLs:

#[derive(clap::Parser)]
struct Opt {
    urls: Vec<String>,
}

#[tokio::main]
async fn main() -> Result<()> {
    let Opt { urls } = Opt::parse();
    for url in urls {
        download_and_print(&url).await?;
    }
    Ok(())
}

But now, let's kick it up a notch and introduce some parallelism. We're going to use a JoinSet to allow us to spawn off a separate task per URL provided and wait on all of them returning. If anything fails along the way, we'll exit the entire program and abort ongoing activities.

#[tokio::main]
async fn main() -> Result<()> {
    let Opt { urls } = Opt::parse();
    let mut set = tokio::task::JoinSet::new();

    for url in urls {
        set.spawn(download_and_print(&url));
    }

    while let Some(result) = set.join_next().await {
        match result {
            Ok(Ok(())) => (),
            Ok(Err(e)) => {
                set.abort_all();
                return Err(e);
            }
            Err(e) => {
                set.abort_all();
                return Err(e.into());
            }
        }
    }
    Ok(())
}

While the parallelism going on here is OK, the spawning of the new tasks themselves fails:

error[E0597]: `url` does not live long enough
  --> src/main.rs:15:38
   |
14 |     for url in urls {
   |         --- binding `url` declared here
15 |         set.spawn(download_and_print(&url));
   |                   -------------------^^^^-
   |                   |                  |
   |                   |                  borrowed value does not live long enough
   |                   argument requires that `url` is borrowed for `'static`
16 |     }
   |     - `url` dropped here while still borrowed

This is a common failure mode in async (and, for that matter, multithreaded) Rust. The issue is that the String we want to pass is owned by the main task, and we're trying to pass a reference to it with no guarantee that the main task will outlive the child task. You might argue that the main task will always outlive all other tasks, but (1) there's no static proof of that within the code, and (2) it's entirely possible to slightly refactor this program so that the spawning occurs in a subtask instead.

The question is: how do you fix this compile time error? We'll explore a few options.

Take a String

Arguably the simplest solution is to change the type of the download_and_print function so that it takes an owned String instead of a reference:

async fn download_and_print(url: String) -> Result<()> {
    let body = reqwest::get(url).await?.text().await?;
    println!("{body}");
    Ok(())
}

Now, at the call site, we're no longer borrowing a reference to the main task's String. Instead, we pass in the entire owned value, transferring ownership to the newly spawned task:

for url in urls {
    // Note the lack of & here!
    set.spawn(download_and_print(url));
}

On the one hand, this feels dirty. We're violating best practices and taking an owned String where one isn't needed. However, this may be considered a small price to pay for the code simply working. However, if the download_and_print`` function will be used in other parts of the code base where passing a reference will work fine, forcing an owned String`` will cause an unnecessary allocation for those use cases, and we may want to look for a better solution.

Adjust the callsite with async move

Another possibility is to leave our download_and_print function as-is taking a reference, and modify our call site as follows:

for url in urls {
    set.spawn(async move { download_and_print(&url).await });
}

By introducing an async move block, what we've done is created a new Future that will be passed to set.spawn. That new Future itself owns the String, not the main task. Therefore, borrowing a reference to url and passing it to download_and_print works just fine.

This is a great solution when you're using a library function that you cannot modify, or when most of your code doesn't run into this lifetime issue. But it can be a bit tedious to have to rewrite code in this way.

impl AsRef

Our final approach today will be to modify the function to accept a more general url type:

async fn download_and_print(url: impl AsRef<str>) -> Result<()> {
    let body = reqwest::get(url.as_ref()).await?.text().await?;
    println!("{body}");
    Ok(())
}

This type means "I'll accept anything that can be converted into a &str." This will work for an owned String as well as a string slice, leaving the decision entirely to the caller. If we leave our call site as passing in a reference, we'll still get the lifetime error above. But if instead we pass in url directly, our program once again works.

This is the approach I'd probably recommend in general. It takes a bit of practice to get used to these impl AsRef parameters, but the payoff is worth it in my opinion.

Improvements

The code above is not perfect. I'm sure others will find other limitations, but two things that jump out at me are:

1. Instead of using reqwest::get, we should be creating a single reqwest::Client and sharing it throughout the application.
2. For a large number of incoming URLs, we wouldn't want to spawn a separate task per URL, but instead have a fixed number of workers and have them all pop work items from a shared queue. This would help with avoiding rate limiting from servers and from overwhelming our application. But the number of URLs we'd have to be requesting would need to be pretty high to run into either of these issues in practice.

Fortunately, both of these are relatively easy to implement thanks to the simplicity of the JoinSet API:

use anyhow::Result;
use async_channel::Receiver;
use clap::Parser;

#[derive(clap::Parser)]
struct Opt {
    urls: Vec<String>,
    #[clap(long, default_value_t = 8)]
    workers: usize,
}

#[tokio::main]
async fn main() -> Result<()> {
    let Opt { urls, workers } = Opt::parse();
    let mut set = tokio::task::JoinSet::new();
    let client = reqwest::Client::new();
    let (send, recv) = async_channel::bounded(workers * 2);

    set.spawn(async move {
        for url in urls {
            send.send(url).await?;
        }
        Ok(())
    });

    for _ in 0..workers {
        set.spawn(worker(client.clone(), recv.clone()));
    }

    while let Some(result) = set.join_next().await {
        match result {
            Ok(Ok(())) => (),
            Ok(Err(e)) => {
                set.abort_all();
                return Err(e);
            }
            Err(e) => {
                set.abort_all();
                return Err(e.into());
            }
        }
    }
    Ok(())
}

async fn worker(client: reqwest::Client, recv: Receiver<String>) -> Result<()> {
    while let Ok(url) = recv.recv().await {
        download_and_print(&client, &url).await?;
    }
    Ok(())
}

async fn download_and_print(client: &reqwest::Client, url: impl AsRef<str>) -> Result<()> {
    let body = client.get(url.as_ref()).send().await?.text().await?;
    println!("{body}");
    Ok(())
}

September 10, 2023 12:00 AM

My favorite luxurious office equipment is low-tech

This is about the stuff I have in my office that I could live without but wouldn't want to. Not stuff like “a good chair” because a good chair is not optional. And not stuff like “paper”. This is the stuff that you might not have thought about already.

The back scratcher at right cost me about $1 and brings me joy every time I use it. My back is itchy, it is distracting me from work, aha, I just grab the back scratcher off the hook and the problem is solved in ten seconds. Not only is it a sensual pleasure, but also I get the satisfaction of a job done efficiently and effectively.

Computer programmers often need to be reminded that the cheap, simple, low-tech solution is often the best one. Perfection is achieved not when there is nothing more to add, but when there is nothing more to take away. I see this flawlessly minimal example of technology every time I walk into my office and it reminds me of the qualities I try to put into my software.

These back scratchers are available everywhere. If your town has a dollar store or an Asian grocery, take a look. I think the price has gone up to $2.

When I was traveling a lot for ZipRecruiter, I needed a laptop stand. (Using a laptop without a stand is bad for your neck.) I asked my co-workers for recommendations and a couple of them said that the Roost was nice. It did seem nice, but it cost $75. So I did Google search for “laptop stand like Roost but cheap” and this is what I found.

This is a Nexstand. The one in this picture is about ten years old. It has performed flawlessly. It has never failed. There has never been any moment when I said “ugh, this damn thing again, always causing problems.”

It folds up and deploys in seconds.

It weighs eight ounces. That's 225 grams.

It takes up the smallest possible amount of space in my luggage. Look at the picture at left. LOOK AT IT I SAY.

The laptop height is easily adjustable.

The Nexstand currently sells for $25–35. (The Roost is up to $90.)

This is another “there is nothing left to take away” item. It's perfect the way it is. This picture shows it quietly doing its job with no fuss, as it does every day.

This last item has changed my life. Not drastically, but significantly, and for the better.

This is a Vobaga electric mug warmer. You put your mug on it, and the coffee or tea or whatever else is in the mug stays hot, but not too hot to drink, indefinitely.

The button on the left turns the power on and off. The button on the right adjusts the temperature: blue for warm, purple for warmer, and red for hot. (The range is 104–149°F (40–65°C). I like red.) After you turn off the power, the temperature light blinks for a while to remind you not to put your hand on it.

That is all it does, it is not programmable, it is not ⸢smart⸣, it does not require configuration, it does not talk to the Internet, it does not make any sounds, it does not spy on me, it does not have a timer, it does do one thing and it does it well, and I never have to drink lukewarm coffee.

The power cord is the only flaw, because it plugs into wall power and someone might trip on it and spill your coffee, but it is a necessary flaw. You can buy a mug warmer that uses USB power. When I first looked into mug warmers I was puzzled. Surely, I thought, a USB connection does not deliver enough power to keep a mug of coffee warm? At the time, this was correct. USB 2 can deliver 5V at up to 0.5A, a total of 2.5 watts of power. That's only 0.59 calorie per second. Ridiculous. The Vobaga can deliver 20 watts. That is enough.

Vobaga makes this in several colors (not that anything is wrong with black) and it costs around $25–30. The hot round thing is 4 inches in diameter (10 cm) and neatly fits all my mugs, even the big ones. It does not want to go in the dishwasher but easily wipes clean with a damp cloth. I once spilled the coffee all over it but it worked just fine once it dried out because it is low tech.

It's just another one of those things that works, day in and day out, without my having to think about it, unless I feel like gloating about how happy it makes me.

[ Addendum: I have no relationship with any of these manufacturers except as a satisfied customer of their awesome products. Do I really need to say that? ]

by Mark Dominus (mjd@plover.com) at September 09, 2023 02:02 PM

Abstract nonsense

I’ve been reading The Joy of Abstraction, by Eugenia Cheng. Very accessible. Would recommend. It’s doing good stuff to my mind.

---

Abstraction, food for thought

Two apples are the same as two apples.

Two apples are not the same as two oranges.

Two ripe apples are not the same as two rotten apples, even though they are both two apples and two apples.

Two fruits are the same as two fruits, even though they could be two apples and two oranges.

by Lysxia at September 05, 2023 12:00 AM

Applicatives should usually implement Semigroup and Monoid

lift-monoid

The gist of this post is that any type constructor F that implements Applicative:

instance Applicative F where
    …

… should usually also implement the following Semigroup and Monoid instances:

instance Semigroup a => Semigroup (F a) where
    (<>) = liftA2 (<>)

instance Monoid a => Monoid (F a) where
    mempty = pure mempty

… which one can also derive using the Data.Monoid.Ap type, which was created for this purpose:

deriving (Semigroup, Monoid) via (Ap F a)

Since each type constructor that implements Monad also implements Applicative, this recommendation also applies for all Monads, too.

Why are these instances useful?

The above instances come in handy in conjunction with utilities from Haskell’s standard library that work with Monoids.

For example, a common idiom I see when doing code review is something like this:

instance Monad M where
    …

example :: M [B]
example = do
    let process :: A -> M [B]
        process a = do
            …
            return bs

    let inputs :: [A]
        inputs = …

    bss <- mapM process inputs

    return (concat bss)

… but if you implemented the suggested Semigroup and Monoid instances then you could replace this:

    bss <- mapM process inputs

    return (concat bss)

… with this:

    foldMap process inputs

These instances also come in handy when you need to supply an empty action or empty handler for some callback.

For example, the lsp package provides a sendRequest utility which has the following type:

sendRequest
    :: MonadLsp config f
    => SServerMethod m
    -> MessageParams m
    -> (Either ResponseError (ResponseResult m) -> f ())
    -- ^ This is the callback function
    -> f (LspId m)

I won’t go into too much detail about what the type means other than to point out that this function lets a language server send a request to the client and then execute a callback function when the client responds. The callback function you provide has type:

Either ResponseError (ResponseResult m) -> f ()

Sometimes you’re not interested in the client’s response, meaning that you want to supply an empty callback that does nothing. Well, if the type constructor f implements the suggested Monoid instance then the empty callback is: mempty.

mempty :: Either ResponseError (ResponseResult m) -> f ()

… and this works because of the following three Monoid instances that are automatically chained together by the compiler:

instance Monoid ()

-- The suggested Monoid instance that `f` would ideally provide
instance Monoid a => Monoid (f a)

instance Monoid b => Monoid (a -> b)

In fact, certain Applicative/Monad-related utilites become special cases of simpler Monoid-related utilities once you have this instance. For example:

• You can sometimes replace traverse_ / mapM_ with the simpler foldMap utility

  Specifically, if you specialize the type of traverse_ / mapM_ to:

  traverse_ :: (Foldable t, Applicative f) => (a -> f ()) -> t a -> f ()
  mapM_     :: (Foldable t, Monad       f) => (a -> f ()) -> t a -> f ()

  … then foldMap behaves the same way when the Applicative f implements the suggested instances:

  foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

• You can sometimes replace sequenceA_ / sequence_ with the simpler fold utility

  Specifically, if you specialize the type of sequenceA_ / sequence_ to:

  sequenceA_ :: (Foldable t, Applicative f) -> t (f ()) -> f ()
  sequence_  :: (Foldable t, Monad       f) -> t (f ()) -> f ()

  … then fold behaves the same way when the Applicative f implements the’ suggested instances:

  fold :: (Foldable t, Monoid m) => t m -> m

• You can sometimes replace replicateM_ with mtimesDefault

  Specifically, if you specialize the type of replicateM_ to:

  replicateM_ :: Applicative f => Int -> f () -> f ()

  … then mtimesDefault behaves the same way when the Applicative f implements the suggested instances:

  mtimesDefault :: Monoid m => Int -> m -> m

And you also gain access to new functionality which doesn’t currently exist in Control.Monad. For example, the following specializations hold when f implements the suggested instances:

-- This specialization is similar to the original `foldMap` example
fold :: Applicative f => [f [b]] -> f [b]

-- You can combine two handlers into a single handler
(<>) :: Applicative f => (a -> f ()) -> (a -> f ()) -> (a -> f ())

-- a.k.a. `pass` in the `relude` package
mempty :: Applicative f => f ()

When should one not do this?

You sometimes don’t want to implement the suggested Semigroup and Monoid instances when other law-abiding instances are possible. For example, sometimes the Applicative type constructor permits a different Semigroup and Monoid instance.

The classic example is lists, where the Semigroup / Monoid instances behave like list concatenation. Also, most of the exceptions that fall in this category are list-like, in the sense that they use the Semigroup / Monoid instances to model some sort of element-agnostic concatenation.

I view these “non-lifted” Monoid instances as a missed opportunity, because these same type constructors will typically also implement the exact same behavior for their Alternative instance, too, like this:

instance Alternative SomeListLikeType where
    empty = mempty

    (<|>) = (<>)

… which means that you have two instances doing the exact same thing, when one of those instances could have potentially have been used to support different functionality. I view the Alternative instance as the more natural instance for element-agnostic concatenation since that is the only behavior the Alternative class signature permits. By process of elimination, the Monoid and Semigroup instances should in principle be reserved for the “lifted” implementation suggested by this post.

However, I also understand it would be far too disruptive at this point to change these list-like Semigroup and Monoid instances and expectations around them, so I think the pragmatic approach is to preserve the current Haskell ecosystem conventions, even if they strike me as less elegant.

Why not use Ap exclusively?

The most commonly cited objection to these instances is that you technically don’t need to add these lifted Semigroup and Monoid instances because you can access them “on the fly” by wrapping expressions in the Ap newtype before combining them.

For example, even if we didn’t have a Semigroup and Monoid instance, we could still write our original example using foldMap, albeit with more newtype-coercion boilerplate:

    fmap getAp (foldMap process (map Ap inputs))

… or perhaps using the newtype package on Hackage:

    ala Ap foldMap process inputs

This solution is not convincing to me for a few reasons:

• It’s unergonomic in general

  There are some places where Ap works just fine (such as in conjunction with deriving via), but typically using Ap directly within term-level code is a solution worse than the original problem; the newtype wrapping and unwrapping boilerplate more than counteracts the ergonomic improvements from using the Semigroup / Monoid instances.

• In my view, there’s no downside to adding Semigroup and Monoid instances

  … when only one law-abiding implementation of these instances is possible. See the caveat in the previous section.

• This line of reasoning would eliminate many other useful instances

  For example, one might remove the Applicative instance for list since it’s not the only possible instance and you could in theory always use a newtype to select the desired instance.

Proof of laws

For completeness, I should also mention that the suggested Semigroup and Monoid instances are guaranteed to always be law-abiding instances. You can find the proof in Appendix B of my Equational reasoning at scale post.

by Gabriella Gonzalez (noreply@blogger.com) at September 03, 2023 03:56 PM

Certainty by Construction Progress Report 9

The following is a progress report for Certainty by Construction, a new book I’m writing on learning and effectively wielding Agda. Writing a book is a tedious and demoralizing process, so if this is the sort of thing you’re excited about, please do let me know!

---

It is now the wee hours of Sept 2, and it’s safe to say I did not make the deadline. The book is not yet finished come hell or high water. Damn. Here’s the state of the world:

• Everything up to page 203/296 has been aggressively edited, in terms of prose, code, general presentation, and overall topic order. There are still a few TODOs to write chapter summaries, but those aren’t the end of the world if they don’t happen.
• It’s now possible to build semi-readable epubs. Needing to run everything through the Agda compiler makes build pipelines surprisingly hard, but I think this should only require a couple of hours to get it into a good place.
• I have commissioned a contest of potential covers for the book; no results yet, but I expect to to have some things to look at by the end of this week.
• Since my last update, I realized I had accidentally lost the chapter on ring solving when doing my big refactor. I’ve since found it, but it’s no longer particularly motivated and is rather out of place, so I think it’s going to get cut. Kill your darlings and all that.

All in all, I’m bummed I didn’t make the deadline, but the quality of the book is exponentially better, so I think it’s a worthwhile trade. I’ve got three/four chapters left to edit (depending on if ring solving gets cut), and I need to write a closing chapter to make the end less jarring.

On a personal note, although the book is much longer in content than my other books, it’s packed much tighter and thus is going to be physically smaller when I get it printed. For some reason that is holding a lot of space in my head right now, and steering me away from cutting too much. I suppose I shouldn’t fret too much; there’s still an index and glossary I need to add which will probably add a bit of length. Also I know this doesn’t matter, but I care about it nevertheless.

So why didn’t I get this done on time? The reason seems to be just that it was too ambitious a goal. I definitely underestimated the amount of polish required here. This month I put 65 hours of honest-to-goodness work into the book, which if you measure in terms of the 2.9h average hours of work that an officer worker does in a day is more than a full time job. It’s very late and I don’t know if that makes sense but I think it might.

Anyway, here’s the plan going forwards—I’ve got some of this week to work on the book before getting married and starting grad school. The goal is to just keep on at this pace for as long as I possibly can until I die or real life gets in the way. It sucks and I’m exhausted and would like to be finished with this thing, but it’s not done with me yet. And so we go on.

But maybe I’ll take tomorrow off because I need to sort out getting married, and I don’t think this kind of extreme focus is good for my mental health. It’s a bit of a balancing act though, because life is only going to get more busy after next week.

Sorry for the bleak trail off here. I should go to bed.

September 02, 2023 12:00 AM

Well Typed collaborates with the Haskell Community to support HLS development

Well-Typed has been collaborating with the Haskell Language Server (HLS) development team thanks to funding from Mercury, Hasura and the HLS Open Collective to support HLS development. This includes work on performance, release management and support for newer GHC releases, as well as taking advantage of new GHC features such as Multiple Home Units and serializing Core to improve performance.

HLS releases

HLS is heavily tied to GHC and the GHC API, so to use HLS with a Haskell project, you must use an HLS executable compiled with the exact same GHC that you use to compile your project. Not doing so can often lead to strange and inscrutable errors.¹ Thus HLS and the GHCup installation tool distribute a matrix of HLS binaries that exactly match the corresponding GHC binaries installed by GHCup. To ensure that HLS binaries corresponding to new GHC releases are promptly available for developers to use, we must provide new HLS releases whenever new major or minor releases of GHC are made.

Thanks to the generous donations of the Haskell Community to the HLS Open Collective and in collaboration with Julian Ospald and the HLS maintainers, Well-Typed has been working to ensure that new HLS releases promptly follow the GHC release cycle, that the release CI responsible for actually producing HLS binary distributions is robust and easy to use, and that the metadata necessary for GHCup to provide HLS binaries is updated along with the release.

This has involved producing HLS releases including the 1.7.0.0, 1.8.0.0, 1.9.0.0, 1.10.0.0 and 2.0.0.0 HLS releases. For the future, we hope to encourage volunteers to create more releases, while ensuring that someone from Well-Typed is always available as a backup to ensure timely releases.

HLS support for new major GHC versions

HLS is a big and complex project with many sub packages and dependencies, and is a prominent client of the notoriously unstable GHC API. As such, it can be quite a task to upgrade it to work new GHC versions.

As part of our work on HLS, we also use it as a staging ground for features that eventually make their way into GHC, such as serializing Core to improve performance. We also implement GHC features to make HLS work better (such as Multiple Home Units). These also require adapting so that HLS can work seamlessly with newer or older GHC versions.

Well-Typed has worked to upgrade HLS to have support for the GHC 9.2, 9.4 and 9.6 release series. We have also added ghcide (the core of HLS) to head.hackage to ensure that it is kept up to date with changes in GHC, and to make future porting efforts easier.

This work was supported by a combination of funding from the HLS Open Collective (for 9.4 support for HLS plugins, in particular adapting to various ghc-exactprint changes), Hasura (for 9.2 and 9.4 and Multiple Home Unit support) and Mercury (for 9.6 support).

Of course, this work would be impossible without the help of the many volunteers who contribute to HLS as well as all the maintainers and contributors to the many packages and dependencies that HLS relies upon.

Performance and memory usage improvements

We previously implemented improvements to recompilation avoidance and startup time as part of our ongoing work for Mercury. Recently, we have made efforts to reduce the memory usage of HLS so that it is more feasible to use it on larger projects and memory constrained systems.

While HLS builds on the GHC API, it faces a different set of design constraints than a compiler like GHC which is traditionally used in batch mode. Rather than being a fire and forget program, HLS sessions are typically quite long lasting. Additionally, HLS is optimised for interactive use, aiming to provide low latency results to assist developers in a timely fashion as they write their programs. It is also heavily incremental, resuing old results as much as possible rather than restarting compilation from scratch, and making use of out of date results to provide low latency information even at the cost of not always being strictly correct.

As such, it needs to keep track of a lot of additional information for these purposes that a typical GHC or even GHCi session does not, which has a cost in terms of memory usage. The memory usage of HLS has been a bone of contention for a while on large projects, which is why Mercury asked us to investigate and reduce the memory usage.

Through a combination of profiling HLS using info table profiling along with careful investigation using ghc-debug, we have managed to significantly reduce the memory used by HLS, and make further improvements to the startup time. Check out Finley’s recent post on reducing Haddock’s memory usage for an introduction to the techniques involved.

Some of these improvements included:

• Increased sharing of internal identifiers that HLS uses to keep track of different build products and intermediate results.

• More compact datastructures to track definition locations for symbols.

• Discarding unneeded global name resolution information.

• Lazily resolving completion information only when a user actually highlights an individual completion item, instead of doing this upfront for all possible completions.

• Avoiding duplicated work when constructing module graphs.

• Adding strictness annotations.

• Bug fixes to recompilation avoidance.

• More efficient unloading of dynamically linked objects to improve reloading performance.

• Using compact interned strings in GHC interface files.

As a result of all this work, the heap usage of HLS on Mercury’s codebase went from 12 GB down to 7 GB when starting from scratch (with no disk cache), and from 8 GB down to 3.5 GB when starting with a warm disk cache. Moreover, startup times went from over 4 minutes to around 30 seconds.

Future work

In GHC 9.4, we added support for Multiple Home Units to the GHC API, allowing you to load multiple packages simultaneously into a single GHC API session. Recently, Matthew worked on Cabal to allow loading multiple components into a single GHCi session. We have a work-in-progress PR to allow HLS to exploit this feature so that users can work seamlessly across multiple packages in a single HLS session.

We plan to:

• continue investigating and improving HLS memory usage, performance and usability,

• help upgrade HLS to newer GHC versions where needed, and

• support the volunteer community in promptly providing HLS releases corresponding to GHC releases.

Many thanks to Hasura, Mercury and the donors to the HLS Open Collective for their support in making these improvements possible, and to the whole community of Haskell developers on whose volunteer efforts this work depends.

If you would like to support this work, please consider contributing to the HLS Open Collective. Alternatively, Well-Typed are always interested in projects and looking for funding to improve GHC, HLS, Cabal and other Haskell tools. Please contact info@well-typed.com if we might be able to work with you!

---

1. Inscrutable errors such as RTS panics or segfaults, especially when Template Haskell is involved.↩︎

by zubin at September 01, 2023 12:00 AM

The Haskell Unfolder Episode 10: generalBracket

Today, 2023-08-30, at 1830 UTC (11:30 am PDT, 2:30 pm EDT, 7:30 pm BST, 20:30 CEST, …) we are streaming the tenth episode of the Haskell Unfolder live on YouTube.

The Haskell Unfolder Episode 10: generalBracket

Exception handling is difficult, especially in the presence of asynchronous exceptions. In this episode we will revise the basics of bracket and why it’s so important. We will then discuss its generalisation generalBracket and its application in monad stacks.

About the Haskell Unfolder

The Haskell Unfolder is a YouTube series about all things Haskell hosted by Edsko de Vries and Andres Löh, with episodes appearing approximately every two weeks. All episodes are live-streamed, and we try to respond to audience questions. All episodes are also available as recordings afterwards.

We have a GitHub repository with code samples from the episodes.

And we have a public Google calendar (also available as ICal) listing the planned schedule.

by andres, edsko at August 30, 2023 12:00 AM

Using cabal-install's dependency solver as a SAT solver!?

Posted on 2023-08-30 by Oleg Grenrus

Dependency resolution in Haskell ecosystem is a hard computational problem. While I'm unsure how hard problem is to picking individual package versions without any additional features, selecting assignment of automatic package flags seems to be very hard: it seems we encode arbitrary boolean satisfiablity problems, SAT, into automatic package flag selection problem.

Real world flag selection problems are easy. Yet, I wanted to try how well cabal-install's solver copes with problems it haven't been tuned for.

Boolean satisfiability problems

From Wikipedia:

In logic and computer science, the Boolean satisfiability problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.

The problems are given to solvers in conjunctive normal form:

(x₁ ∨ x₂) ∧ (x₃ ∨ x₄)

and solvers job is to find an assignment making the formula true. In the example above there are many solutions, e.g. setting all variables to true.

Sudoku

One of go to examples of what you can do with a SAT solvers is solving sudoku puzzles.

Our running example will be a very simple 2×2 sudoku puzzle.

┌─────┬─────┐
│   1 │ 4   │
│   3 │   2 │
├─────┼─────┤
│     │ 3   │
│     │     │
└─────┴─────┘

Problem encoding is somewhat of art form, but for sudoku its quite simple.

The problem variables are numbers in cells i, j. We can encode each number using four variables, x(i,j,k), and requiring that exactly one is true. We could also use only two "bits" to encode four options (so called binary encoding), but using one-bit per option makes easier to encode the sudoku rules.

Recall the sudoku rules: each number have to occur exactly once in each row, column and subsquare.

With our number encoding the puzzle rules are easy to encode. For example for each row i and number k we require that exactly one literal in x(i,j,k), j <- [1..4] is true And similarly for columns and subsquares.

For what it's worth, sudoku can be very neatly encoded using Applicatives and Traversables. See the StackOverflow answer by Conor McBride.

SAT solvers consume a DIMACS format which looks like:

p cnf 64 453
-60 -64 0
-48 -64 0
-48 -60 0
-44 -64 0
-44 -60 0
-44 -48 0
44 48 60 64 0
-59 -63 0
-47 -63 0
-47 -59 0
-43 -63 0
-43 -59 0
-43 -47 0
43 47 59 63 0
-58 -62 0
...

Borrowing the DIMACS format explanation from varisat's documentation:

A DIMACS file begins with a header line of the form p cnf <variables> <clauses>. Where <variables> and <clauses> are replaced with decimal numbers indicating the number of variables and clauses in the formula. Following the header line are the clauses of the formula. The clauses are encoded as a sequence of decimal numbers separated by spaces and newlines. For each clause the contained literals are listed followed by a 0.

The above is beginning of encoding of our sudoku problem. There are 4 × 4 cells and each number uses 4 variables, so in total there are 64 variables.

The exactly once encoding I used is done using naive (binomial) at most one encoding. You can see a pattern:

-60 -64 0
-48 -64 0
-48 -60 0
-44 -64 0
-44 -60 0
-44 -48 0
44 48 60 64 0

The last line is requiring that at least one of four variables (44, 48, 60, 64) is true. The first 6 lines are pairwise requirements that at most one of the variables is true: n over 2 i.e. 6 pairs. All of sudoku rules are such exactly one of four constraints, which we have 64 in total: 16 for digits, 4 rows, columns and subsquares with four numbers, That is 7 × 64 = 448 clauses.

The final 5 clauses are initial value constraints. As we know 5 numbers, we tell that the following bits must be true.

The sudoku.cnf file indeed ends with five unit clauses:

...
43 0
30 0
23 0
12 0
5 0

When we run the SAT solver, e.g. z3 -dimacs sudoku.cnf it will immediately give a solution which looks something like

sat
-1 2 -3 -4 5 -6 -7 -8 -9 -10 -11 12 -13 -14 15 -16
-17 -18 -19 20 -21 -22 23 -24 25 -26 -27 -28 -29 30 -31 -32
33 -34 -35 -36 -37 38 -39 -40 -41 -42 43 -44 -45 -46 -47 48
-49 -50 51 -52 -53 -54 -55 56 -57 58 -59 -60 61 -62 -63 -64 

For each of 64 variables it prints whether the satisfying assignment for that variable is true (positive) or false (negative).

When we decode the solution we'll get a solution to our sudoku puzzle:

┌─────┬─────┐
│ 2 1 │ 4 3 │
│ 4 3 │ 1 2 │
├─────┼─────┤
│ 1 2 │ 3 4 │
│ 3 4 │ 2 1 │
└─────┴─────┘

Encoding as cabal automatic flags

So how can we encode a SAT problem as flag selection one?

It is hopefully obvious that each variable will be represented by an automatic flag, i.e. a flag which solver can (should) choose an assignment for:

flag 1
  manual: False
  default: False

(Yes, flag names can be "numbers", they are still treated as strings).

The default value shouldn't matter, but it's probably better to pick False as most variables in sudoku problem are indeed false.

Let's next think how to encode clauses. When the CNF is satisfiable each clause should evaluate to true. When CNF is unsatisfiable it's enough that any clause evaluate to false. Recall clauses are disjunctions of literals:

x₁ ∨ ¬ x₂ ∨ ¬ x₃ ∨ x₄

Then we can encode such clause as a conditional in a component stanza of .cabal file. There shouldn't be an install plan if a clause value if false:

if !(flag(1) || !flag(2) || !flag(3) || flag(4))
  build-depends: unsatisfiable <0

or equivalently:

if !flag(1) && flag(2) && flag(3) && !flag(4))
  build-depends: unsatisfiable <0

The library stanze in the resulting sudoku.cabal file looks like

library
  if flag(60) && flag(64)
    build-depends: unsatisfiable <0

  if flag(48) && flag(64)
    build-depends: unsatisfiable <0

  if flag(48) && flag(60)
    build-depends: unsatisfiable <0

  if flag(44) && flag(64)
    build-depends: unsatisfiable <0

  if flag(44) && flag(60)
    build-depends: unsatisfiable <0

  if flag(44) && flag(48)
    build-depends: unsatisfiable <0

  if !flag(44) && !flag(48) && !flag(60) && !flag(64)
    build-depends: unsatisfiable <0

...

  if !flag(43)
    build-depends: unsatisfiable <0

  if !flag(30)
    build-depends: unsatisfiable <0

  if !flag(23)
    build-depends: unsatisfiable <0

  if !flag(12)
    build-depends: unsatisfiable <0

  if !flag(5)
    build-depends: unsatisfiable <0
...

And we can ask cabal-install to construct an install plan with

cabal build --dry-run

On my machine it took 17 seconds to complete. (I actually didn't know what to expect, I'd say 17 seconds is not bad).

cabal-install writes out plan.json file which contains the build plan. It's a JSON file which can be inspected directly or queried with cabal-plan utility.

cabal-plan topo --show-flags

shows

sudoku-0 -1 -10 -11 +12 -13 -14 +15 -16 -17 -18 -19 +2 +20 -21 -22 +23
  -24 +25 -26 -27 -28 -29 -3 +30 -31 -32 +33 -34 -35 -36 -37 +38 -39 -4
  -40 -41 -42 +43 -44 -45 -46 -47 +48 -49 +5 -50 +51 -52 -53 -54 -55
  +56 -57 +58 -59 -6 -60 +61 -62 -63 -64 -7 -8 -9

there is only one package in the install plan, and we asked cabal-plan to also show the flag assignment, which it does. The output is almost the same as from z3!

If we decode this solution, we get the same answer:

┌─────┬─────┐
│ 2 1 │ 4 3 │
│ 4 3 │ 1 2 │
├─────┼─────┤
│ 1 2 │ 3 4 │
│ 3 4 │ 2 1 │
└─────┴─────┘

Conclusion

We successfully used cabal-install dependency solver as a SAT solver. It is terribly slow, but it's probably still faster at solving 2×2 sudoku puzzle than myself. The code is available on GitHub if you want to play with it.

However, it is not unheard that we need to encode some logical constraints in cabal file.

For example transformers-compat encodes which transformers version it depends on using kind of unary encoding: each bucket is encoded using single flag: Removing some unrelated bits:

...

  if flag(four)
    build-depends: transformers >= 0.4.1 && < 0.5
  else
    build-depends: transformers < 0.4 || >= 0.5

  if flag(three)
    build-depends: transformers >= 0.3 && < 0.4
  else
    build-depends: transformers < 0.3 || >= 0.4

...

The choice of transformers versions forces assignments to the automatic flags (four, three, ...) and then we can alter build info of a package based on that.

That is an indirect way of writing (encoding!) something like

  if build-depends(transformers >= 0.4.1 && <0.5)
    ...

  if build-depends(transformers >= 0.3 && <0.4)
    ...

A common example in the past was adding old-locale dependency when the old version of time library was picked:

  if flag(old-locale)
    build-depends:
        old-locale  >=1.0.0.2 && <1.1
      , time        >=1.4     && <1.5

  else
    build-depends: time >=1.5 && <1.7

which could be written as

  build-depends: time >=1.4 && <1.7
  if build-depends(time < 1.5)
    build-depends: old-locale >=1.0.0.2 && <1.1

Another example is functor-classes-compat which also encodes transformers and base version subsets, but it is using binary encoding of four options. There the implied constraints are also (hopefully) disjoint making flag assignment deterministic.

I think that automatic flags are good feature to have. It is a basic building block, but is a "low-level" feature. On the other hand if build-depends(...) construct is more difficult to use wrong, and probably covers 99% of the use cases for automatic flags. If you are mindful that you encoding if build-depends (...) constraint, then you'll probably use cabal's automatic flags correctly. Conversely, if you are using automatic flags to encode something else, like solving general SAT problems, most likely you are doing something wrong.

August 30, 2023 12:00 AM

Type Safety Doesn't Matter

I'm a huge believer in using strongly typed languages and leveraging type level protections in my codebases. But I'd like to clarify my new, somewhat modified stance on this:

Type safety does not matter.

What I mean is that, on its own, type safety is not important. It's only useful because of what it accomplishes: moving errors from runtime to compile time. Even that isn't a goal on its own. The real goal is reducing runtime errors. Type safety is one of the best methods of achieving these cascading goals, but it's far from the only one.

This may sound pedantic and click-baity, but in my opinion it's a vitally important distinction with real world ramifications. For example, when discussing architecture of code or reviewing a pull request, I will often times push back on changes that add more complexity in the type system. The reason is because, even if a change adds "type safety," this extra complexity is only warranted if it achieves our primary goal, namely reducing runtime errors.

Such an assessment is largely speculative, subjective, and risk-based. By that last point, I'm tapping into my actuarial background. The idea is that, when considering a code change, the question will always be: do I think there's a high likelihood that this change will meaningfully reduce bug count in the long term more so than other activities I could be spending this time on? And if you watched my talk the economic argument for functional programming (or read the slides), you may be familiar with this way of thinking as the opportunity cost of spending more time on type safety.

This is why languages that provide for strong typing with type inference end up working out so well. There's relatively little cost for basic type safety mechanisms with significant gain. It's the 80/20 rule. I continue to believe that the vast majority of the value I've received from strongly typed languages like Rust, Haskell, and even TypeScript come from the "simplest" features like enums/ADTs and pattern matching.

Bug reduction is not the only benefit of strong typing. There's also: easier codebase maintainability, simplicity of refactoring, new engineering onboarding, potentially performance gains, and probably a few other things I missed. But for me, reduction in bugs is still the primary benefit.

This paradigm of assessing the value in bug reduction from type safety lets us broaden our scope a bit. If we want to reduce bugs in production, and we believe that moving bugs from runtime to compile time is a good way to do it, we can naturally find some related techniques. An obvious one is "static code analysis." But I'll simplify that with the 80/20 rule as well to linting tools. Using linting tools is a great way to get lots of benefits with little cost.

Just to prove this isn't only about types, let's take a concrete example from everyone's favorite language, JavaScript. If I'm writing a React application in JavaScript, I get virtually no type safety. (TypeScript is a different story, and it's the only thing that keeps me sane when working on frontend code.) Consider this bit of almost-correct React code:

const { userName, gameLevel } = props
const [userScore, setUserScore] = useState()

useEffect(() => {
    const helper = async () => {
        const res = await fetchUserScore(userName, gameLevel)
        const body = await res.json()
        setUserScore(body.score)
    }
    helper()
}, [userName, setUserScore])

For those not familiar: useEffect allows me to run some kind of an action, in this case an asynchronous data load from a server. This is a common pattern in React. As the user is using this application and changes the game level, I want to perform an action to load up their current score from the server and set it in a local store that can be used by the rest of the application. useEffect takes two arguments: the function to perform, and the list of dependencies to use. When one of those dependencies changes, the effect is rerun.

There are plenty of improvements to be made in this code, but there's one blatant bug: my useEffect dependency list does not include gameLevel. This would be a bug at runtime: once the user's score is loaded for a level, we would never reload it despite moving on to other levels. This would be the kind of bug that is easy to miss during manual testing, and could end up in production pretty easily.

Automated testing, unit tests, QA acceptance guidelines... basically everything around quality assurance will help ameliorate bugs like this. But static analysis arguably does even better here. The above code will immediately trigger lints saying "hey, I see you used gameLevel in your function, but you didn't list it in your dependencies." This is a prime example of moving a bug from runtime to compile time (or at least development time), preventing an entire class of bugs from occurring, and it didn't need any type safety to do it. Sure, it doesn't eliminate every potential bug, but it does knock down a whole bunch of them.

As you might imagine, this blog post was inspired by a specific set of problems I was running into at work. I thought about getting into those details here, and if there's interest I can write a follow-up blog post, but honestly the specific case isn't terribly interesting. My point here is the general principles:

1. Understand why you're trying to use type safety. Is it preventing some kind of a bug from occurring? Is the time you're spending on implementing the type-safe solution paying off in bug reduction and other benefits?
2. There are lots of other techniques worth considering for bug reduction. Static analysis is one I mentioned. Automated testing falls into this category as well. Don't be ideologically driven in which approaches you use. Choose the tool with the best power-to-weight ratio for what you're dealing with right now.

August 28, 2023 12:00 AM

GHC 9.4.7 is now available

GHC 9.4.7 is now available

Zubin Duggal - 2023-08-25

The GHC developers are happy to announce the availability of GHC 9.4.7. Binary distributions, source distributions, and documentation are available at downloads.haskell.org.

This release is primarily a bugfix release addressing some issues found in 9.4.7. These include:

• A bump to bytestring-0.11.5.2 allowing GHC to be bootstrapped on systems where the bootstrap compiler is built with the pthread_condattr_setclock symbol available (#23789).
• A number of bug fixes for scoping bugs in the specialiser, preventing simplifier panics (#21391, #21689, #21828, #23762).
• Distributing dynamically linked alpine bindists (#23349, #23828).
• A bug fix for the release notes syntax, allowing them to built on systems with older python and sphinx versions (#23807, #23818).
• … and a few more. See the release notes for a full accounting.

We would like to thank Microsoft Azure, GitHub, IOG, the Zw3rk stake pool, Well-Typed, Tweag I/O, Serokell, Equinix, SimSpace, Haskell Foundation, and other anonymous contributors whose on-going financial and in-kind support has facilitated GHC maintenance and release management over the years. Finally, this release would not have been possible without the hundreds of open-source contributors whose work comprise this release.

As always, do give this release a try and open a ticket if you see anything amiss.

Happy compiling,

• Zubin

by ghc-devs at August 25, 2023 12:00 AM

Certainty by Construction Progress Report 8

The following is a progress report for Certainty by Construction, a new book I’m writing on learning and effectively wielding Agda. Writing a book is a tedious and demoralizing process, so if this is the sort of thing you’re excited about, please do let me know!

---

Eight days away from my deadline. How’s it going? Hectic.

I’ve been in a flurry of editing for the last two weeks. As of right now, I’m currently editing page 138/252. At this rate, it’s not looking promising, but I did just buy a flat of Red Bull, so you never know.

Besides editing, what’s new? Lots of minor typesetting stuff, like which paragraphs should be indented. I also did a pass through all the Agda modules with their new, final names, in easy searchable format. Along with that, the end of each chapter now has an explicit export list, which subsequent chapters import (rather than getting it from the stdlib.) This means you can see at a glance whether a chapter has prerequisites you need to read first! Minor stuff, but Nintendo polish nevertheless.

I had to rewrite a good chunk of chapter 2, and a lot of the prose in chapter 3 is from a very early edition of the book, and doesn’t have the shine as the rest of it. So that’s getting reworked too. My hope is that the later chapters were written more recently, and therefore will require less elbow grease. It’s plausible, and would be greatly appreciated. But I fear that the setoids chapter needs a lot of work, and I’m just trying my best to ignore it. For now.

In other news, I’m now uploading nightly builds to Leanpub in order to keep myself honest. There’s no indication of which half of the book has been edited and which hasn’t, but that seems like a good idea I should adopt for the next build. That way particularly dedicated readers could follow along and see just how quickly I can get material cleaned up. And it will prevent me from accidentally forgetting where I was and re-editing it all again. Which has happened several times, somehow.

Okay that’s enough of an update. Back to the grind. Love y’all.

August 23, 2023 12:00 AM

GHC 9.8.1-alpha3 is now available

GHC 9.8.1-alpha3 is now available

bgamari - 2023-08-23

The GHC developers are very pleased to announce the availability of the third alpha prerelease of GHC 9.8.1. Binary distributions, source distributions, and documentation are available at downloads.haskell.org.

GHC 9.8 will bring a number of new features and improvements, including:

• Preliminary support the TypeAbstractions language extension, allowing types to be bound in type declarations.

• Support for the ExtendedLiterals extension, providing more consistent support for non-word-sized numeric literals in the surface language

• Improved rewrite rule matching behavior, allowing limited matching of higher-order patterns

• Better support for user-defined warnings by way of the WARNING pragma

• The introduction of the new GHC.TypeError.Unsatisfiable constraint, allowing more predictable user-defined type errors

• Implementation of the export deprecation proposal, allowing module exports to be marked with DEPRECATE pragmas

• The addition of build semaphore support for parallel compilation, allowing better use of parallelism across GHC builds

• More efficient representation of info table provenance information, reducing binary sizes by nearly 80% in some cases when -finfo-table-map is in use

A full accounting of changes can be found in the release notes. This alpha includes roughly a dozen changes relative to alpha 2, including what we believe should be nearly the last changes to GHC’s boot libraries.

We would like to thank GitHub, IOG, the Zw3rk stake pool, Well-Typed, Tweag I/O, Serokell, Equinix, SimSpace, the Haskell Foundation, and other anonymous contributors whose on-going financial and in-kind support has facilitated GHC maintenance and release management over the years. Finally, this release would not have been possible without the hundreds of open-source contributors whose work comprise this release.

As always, do give this release a try and open a ticket if you see anything amiss.

by ghc-devs at August 23, 2023 12:00 AM

Swarm 0.4 release

The Swarm development team is very proud to announce the latest release of the game. This should still be considered a development/preview release—you still can’t save your games—but it’s made some remarkable progress and there are lots of fun things to try.

What is it?

As a reminder, Swarm is a 2D, open-world programming and resource gathering game with a strongly-typed, functional programming language and a unique upgrade system. Unlocking language features is tied to collecting resources, making it an interesting challenge to bootstrap your way into the use of the full language. It has also become a flexible and powerful platform for constructing programming challenges.

A few of the most significant new features are highlighted below; for full details, see the release notes. If you just want to try it out, see the installation instructions.

Expanded design possibilities

The default play mode is the open-world, resource-gathering scenario—but Swarm also supports “challenge scenarios”, where you have to complete one or more specific objectives with given resources on a custom map. There are currently 58 scenarios and counting—some are silly proofs of concept, but many are quite fun and challenging! I especially recommend checking out the Ranching and Sokoban scenarios, as well as A Frivolous Excursion (pictured below). And creating new scenarios is a great way you can contribute to Swarm even if you don’t know Haskell, or aren’t comfortable hacking on the codebase.

Recently, a large amount of work has gone into expanding the possibilities for scenario design:

• Structure templates allow you to design map tiles and then reuse them multiple times within a scenario.
• Waypoints and portals provide a mechanism for automatically navigating and teleporting around the world.
• Scenarios can have multiple subworlds besides the main “overworld”, connected by portals. For example you could go “into a building” and have a separate map for the building interior.
• There are a slew of new robot commands, many to do with different sensing modalities: stride, detect, sniff, chirp, resonate, watch, surveil, scout, instant, push, density, use, halt, and backup.
• A new domain-specific language for describing procedurally generated worlds. The default procedurally generated world used to be hardcoded, but now it is described externally via the new DSL, and you can design your own procedurally generated worlds without editing the Swarm source code.
• The key input handler feature allows you to program robots to respond to keyboard input, so you can e.g. drive them around manually, or interactively trigger more complex behaviors. This makes it possible to design “arcade-style” challenges, where the player needs to guide a robot and react to obstacles in real time—but they get to program the robot to respond to their commands first!
• A new prototype integrated world editor lets you design worlds interactively.

UI improvements

In the past, entity and goal descriptions were simply plain text; recently, we switched to actually parsing Markdown. Partly, this is just to make things look nice, since we can highlight code snippets, entity names, etc.:

But it also means that we can now validate all code examples and entity names, and even test that the tutorial is pedagogically sound: any command used in a tutorial solution must be mentioned in a previous tutorial, or else our CI fails!

There are also a number of other small UI enhancements, such as improved type error messages, inventory search, and a collapsible REPL panel, among others.

Scoring metrics

We now keep track of a number of metrics related to challenge scenario solutions, such as total time, total game ticks, and code size. These metrics are tracked and saved across runs, so you can compete with yourself, and with others. For now, see these wiki pages:

• Swarm speedrunning
• Swarm code golf

In the future, perhaps there will eventually be some kind of social website with leaderboards and user-uploaded scenarios.

Debugging

Last but not least, we now have an integrated single-stepping and debugging mode (enabled by the tweezers device).

Give it a try!

To install, check out the installation instructions: you can download a binary release (for now, Linux only, but MacOS binaries should be on the horizon), or install from Hackage. Give it a try and send us your feedback, either via a github issue or IRC!

Future plans & getting involved

We’re still hard at work on the game. Fun upcoming things include:

• Saving and loading games
• New world features like aliens and cities
• New language features like recursive types, arrays, inter-robot communication, and a proper import construct

Of course, there are also tons of small things that need fixing and polishing too! If you’re interested in getting involved, check out our contribution guide, come join us on IRC (#swarm on Libera.Chat), or take a look at the list of issues marked “low-hanging fruit”.

Brought to you by the Swarm development team:

• Brent Yorgey
• Karl Ostmo
• Ondřej Šebek

With contributions from:

• Alexander Block
• Brian Wignall
• Chris Casinghino
• Daniel Díaz Carrete
• Huw Campbell
• Ishan Bhanuka
• Jacob
• Jens Petersen
• José Rafael Vieira
• Joshua Price
• lsmor
• Noah Yorgey
• Norbert Dzikowski
• Paul Brauner
• Ryan Yates
• Sam Tay
• Steven Garcia
• Tamas Zsar
• Tristan de Cacqueray
• Valentin Golev

…not to mention many others who gave valuable suggestions and feedback. Want to see your name listed here in the next release? See how you can contribute!

by Brent at August 22, 2023 05:37 PM

What does it mean for a monad to be strong?

This is something I put on github years ago but I probably should have put it here.

Here's an elementary example of the use of the list monad:

> test1 = do
>   x <- [1, 2]
>   y <- [x, 10*x]
>   [x*y]

We can desugar this to:

> test2 = [1, 2] >>= \x -> [x, 10*x] >>= \y -> [x*y]

It looks like we start with a list and then apply a sequence (of length 2) of functions to it using bind (>>=). This is probably why some people call monads workflows and why the comparison has been made with Unix pipes.

But looks can be deceptive. The operator (>>=) is right associative and test2 is the same as test3:

> test3 = [1, 2] >>= (\x -> [x, 10*x] >>= \y -> [x*y])

You can try to parenthesise the other way:

> -- test4 = ([1, 2] >>= \x -> [x, 10*x]) >>= \y -> [x*y]

We get a "Variable not in scope: x" error. So test1 doesn't directly fit the workflow model. When people give examples of how workflow style things can be seen as monads they sometimes use examples where later functions don't refer to variables defined earlier. For example at the link I gave above the line m >>= x-> (n >>= y-> o) is transformed to (m >>= x-> n) >>= y-> o which only works if o makes no mention of x. I found similar things to be true in a number of tutorials, especially the ones that emphasise the Kleisli category view of things.

But we can always "reassociate" to the left with a little bit of extra work. The catch is that the function above defined by y-> ... "captures" x from its environment. So it's not just one function, it's a family of functions parameterised by x. We can fix this by making the dependence on x explicit. We can then pull the inner function out as it's no longer implicitly dependent on its immediate context. When compilers do this it's called lambda lifting.

Define (the weirdly named function) strength by

> strength :: Monad m => (x, m y) -> m (x, y)
> strength (x, my) = do
>   y <- my
>   return (x, y)

It allows us to smuggle x "into the monad".

And now we can rewrite test1, parenthesising to the left:

> test5 = ([1, 2] >>= \x -> strength (x, [x, 10*x])) >>= \(x, y) -> [x*y]

This is much more like a workflow. Using strength we can rewrite any (monadic) do expression as a left-to-right workflow, with the cost of having to throw in some applications of strength to carry along all of the captured variables. It's also using a composition of arrows in the Kleisli category.

A monad with a strength function is called a strong monad. Clearly all Haskell monads are strong as I wrote strength to work with any Haskell monad. But not all monads in category theory are strong. It's a sort of hidden feature of Haskell (and the category Set) that we tend not to refer to explicitly. It could be said that we're implicitly using strength whenever we refer to earlier variables in our do expressions.

See also nlab.

> main = do
>   print test1
>   print test2
>   print test3
>   -- print test4
>   print test5

by sigfpe (noreply@blogger.com) at August 21, 2023 03:23 PM

Orwell was right

 

A short comic by Mike Dawson. Stick to the end for a valid point.

by Philip Wadler (noreply@blogger.com) at August 16, 2023 12:32 PM

Certainty by Construction Progress Report 7

The following is a progress report for Certainty by Construction, a new book I’m writing on learning and effectively wielding Agda. Writing a book is a tedious and demoralizing process, so if this is the sort of thing you’re excited about, please do let me know!

---

Where has this dingus Sandy been?? Busy busy busy! I’m in the middle of planning a wedding (my own), as well as just finished being the best man at my friend’s wedding. Plus getting the tax man’s records all sorted out for him, and a bunch of other things that fell into the “urgent” AND “important” categories.

Yeesh. Enough excuses though. I’m back and haven’t given up on any of this!

These days I’m calling the book “essentially done,” and all that is required is extensive editing. Which I’ve been doing. Every day on the bus I’m reading my PDF copy and making notes in the margin. Then I get home and go through the notes and clean up the prose.

It’s slow going, but that’s the way of the world. The prose is getting dramatically tightened up, however. It’s kind of fun to go through, be aware of the point I’m trying to make, and realize that I haven’t actually made it. I’m not calling this “rewriting,” but most paragraphs are changing dramatically.

Today I also sat down and hashed out a bunch of the technical pipeline issues I’ve been putting off for a year. Like getting section references working. So now instead of saying “as in sec:propeq?”, the prose now says “as in section 3.2”. The annotations have always been there, but getting the build to actually put in the text has taken away several hours of my life.

More excitingly, I also managed to get inline code snippets properly highlighted—and, even better, broken code now also highlights. This is a resounding achievement, because the whole idea of literate Agda is that it must compile. And the compiler is what generates the syntax highlighting. It’s a terrifying marvel of engineering, but it does work.

So that’s all. I’m just going to push on this book thing until it’s done. Or until September 1. Whichever comes sooner. That’s a terrifying thought, so I guess I’d better get back to it.

August 12, 2023 12:00 AM

Supercharging your Rust static executables with mimalloc

Why link statically against musl?

Have you ever faced compatibility issues when dealing with Linux binary executables? The culprit is often the libc implementation, glibc. Acting as the backbone of nearly all Linux distros, glibc is the library responsible for providing standard C functions. Yet, its version compatibility often poses a challenge. Binaries compiled with a newer version of glibc may not function on systems running an older one, creating a compatibility headache.

So, how can we circumvent this issue?

The approach we’ll focus on today involves the creation of static executables. These executables are self-contained and do not dynamically load libc, thereby offering enhanced portability.

However, we’re not out of the woods yet. Glibc is not well-suited for static linking because it heavily relies on dynamic loading of locale data and DNS service plugins. That’s where musl, a lightweight alternative libc implementation, shines. Musl is highly proficient at creating portable, static Linux executables.

But, when it comes to musl, there’s a certain performance trap: its allocator does not perform well in multi-core environments. Do we have to live with it? Absolutely not! By replacing musl’s malloc implementation with a cutting-edge allocator like mimalloc, we can supercharge its performance in multi-core setups.

In this blog post, I’ll take you on a deep dive into this performance-enhancing strategy using a real-world Rust project as an example. We’ll also take a look at some intriguing benchmark results that demonstrate the significant improvement this change can drive.

Are you ready to turbocharge your Rust static executables? Let’s dive right in!

Creating Rust static executables based on musl

Let’s explore how to compile wasmtime into a static Linux executable that links with musl. For those who aren’t familiar, wasmtime is a standalone runtime for WebAssembly. Although the upstream repo doesn’t distribute static wasmtime executables yet, I’ve found myself needing a version of wasmtime that functions across all distros, including those not based on glibc, like Alpine.

Luckily, wasmtime is written in Rust, a language known for its toolchain being particularly friendly to cross-compiling. Here’s how to compile wasmtime to a static executable in an Ubuntu 23.04 work environment:

$ sudo apt install -y musl-tools # Needed only if the Rust project has C dependencies
$ rustup target add x86_64-unknown-linux-musl # Downloads a static build of musl to be linked later
$ cargo build --target x86_64-unknown-linux-musl --release --bin wasmtime # Time for a short break

With just these commands, you can generate a static wasmtime executable from the checked out repo.

Testing our result shows it is indeed a static executable:

$ ./target/x86_64-unknown-linux-musl/release/wasmtime --version
wasmtime-cli 11.0.0
$ ldd ./target/x86_64-unknown-linux-musl/release/wasmtime
        statically linked

However, before we celebrate, there’s a catch. While the executable works, its performance leaves something to be desired. In fact, the performance of this static wasmtime falls short when compared to ordinary wasmtime builds that link against the system-wide glibc. In the next section, we’ll explore why this happens and how to improve the performance.

A static executable based on musl may be ssllooww

In order to compare the performance of different wasmtime builds, we will execute a simple benchmark using a small tool called bench. This tool runs the same command multiple times and outputs statistical data such as mean time and variance.

The benchmark involves compiling and running a large hello.wasm module. This module is around 26MiB in size, large enough to demonstrate the difference in wasmtime run-time performance.

The benchmark is executed with wasmtime run --disable-cache, as wasmtime caches JIT-compiled code by default. However, we want different runs to be independent from each other.

The test is performed on a server with 48 logical cores and 128GiB memory. When wasmtime does JIT compilation and optimization, it automatically uses all CPU cores by default.

Here’s the result for an ordinary wasmtime build that dynamically links against system-wide glibc:

benchmarking /workspace/wasmtime/target/release/wasmtime run --disable-cache hello.wasm
time                 4.311 s    (4.106 s .. 4.714 s)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 4.452 s    (4.341 s .. 4.599 s)
std dev              145.8 ms   (49.87 ms .. 198.2 ms)
variance introduced by outliers: 19% (moderately inflated)

Next, here’s the result for the static wasmtime build produced earlier:

benchmarking /workspace/wasmtime/target/x86_64-unknown-linux-musl/release/wasmtime run --disable-cache hello.wasm
time                 93.07 s    (91.75 s .. 93.74 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 92.16 s    (91.35 s .. 92.60 s)
std dev              790.0 ms   (79.30 ms .. 1.017 s)
variance introduced by outliers: 19% (moderately inflated)

So, on a machine with many cores, a static wasmtime build can take 20x more time to compile and run a wasm module! Clearly, this is not the type of build we want.

malloc contention is the culprit

Let’s observe htop while the static wasmtime build is struggling and consuming all the CPU cores. The CPU bars are filled with red, which is undesirable. This color signifies that CPU time is wasted in kernel mode, when we ideally want the green color that indicates CPU time is properly spent in user mode, doing useful work.

A common cause of the above symptom is thread contention: multiple threads are fighting to acquire the same resource instead of doing useful work. Although it’s better than deadlock or livelock, since the application runs to completion, it’s still a significant waste of CPU.

To confirm this hypothesis, we rerun the benchmark with --disable-parallel-compilation. Here are the numbers for the glibc build:

benchmarking /workspace/wasmtime/target/release/wasmtime run --disable-cache --disable-parallel-compilation hello.wasm
time                 41.24 s    (40.59 s .. 41.82 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 41.40 s    (41.30 s .. 41.55 s)
std dev              146.4 ms   (37.24 ms .. 194.9 ms)
variance introduced by outliers: 19% (moderately inflated)

And here are the numbers for the musl build:

benchmarking /workspace/wasmtime/target/release/wasmtime run --disable-cache --disable-parallel-compilation hello.wasm
time                 41.32 s    (40.99 s .. 41.55 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 41.38 s    (41.32 s .. 41.41 s)
std dev              47.04 ms   (16.59 ms .. 63.66 ms)
variance introduced by outliers: 19% (moderately inflated)

Now the numbers are comparable, and interestingly, the musl build performs much faster than when all CPU cores are used. Therefore, it’s indeed a thread contention issue. Inappropriate use of locks in user code can lead to thread contention. However, this is not the case in wasmtime, as the glibc build shows significant speedup when operating in multi-core mode.

The real source of thread contention is in the malloc implementation of musl. A malloc implementation must be thread-safe, as multiple threads may allocate memory at once or even free memory allocated in other threads. Thus, the thread synchronization logic could become a bottleneck.

Although I have not deep-dived into the musl malloc codebase to locate the contention, replacing it with a cutting-edge malloc implementation like mimalloc is sufficient to rectify the problem and enhance performance. Mimalloc minimizes contention and enhances multi-threaded performance. In fact, this replacement can make the application run even faster than the default glibc build.

Building mimalloc and linking against it

First, checkout the latest release of mimalloc and apply this patch, which accomplishes several things:

• Disables -fPIC when building libmimalloc.a to prioritize performance in our static build. The -fPIC option can create unnecessary overhead.
• Turns off the override of C++ new/delete operators. The original implementation will still invoke malloc/free in libmimalloc.a, so overriding these is unnecessary and could trigger linker errors when linking with C++.
• Ensures the __libc_ wrappers are also created when compiling for musl, these wrappers are indeed used by musl internally.

Now, you can build libmimalloc.a using the command below:

$ cmake \
    -Bout \
    -DCMAKE_BUILD_TYPE=Release \
    -DCMAKE_C_COMPILER=x86_64-linux-musl-gcc \
    -DMI_BUILD_SHARED=OFF \
    -DMI_BUILD_OBJECT=OFF \
    -DMI_BUILD_TESTS=OFF \
    .
$ cmake --build out

The next challenge is to link libmimalloc.a into wasmtime, ensuring it overrides musl’s default malloc implementation.

In a C/C++ project, you may pass -Wl,--push-state,--whole-archive,/workspace/mimalloc/out/libmimalloc.a,--pop-state to the linker arguments. This works well for glibc, since symbols like malloc are defined as weak symbols so they can be easily overridden by malloc defined in user code.

However, messing with linker commands doesn’t work so well for musl. It defines malloc as strong symbols, so overriding malloc may or may not work depending on where the build system places the above line in the list of linker arguments. Bad news for us, it doesn’t work in cargo:

RUSTFLAGS="-C link-arg=-Wl,--push-state,--whole-archive,/workspace/mimalloc/out/libmimalloc.a,--pop-state" cargo build \
  --target x86_64-unknown-linux-musl \
  --release \
  --bin wasmtime
...
/usr/bin/ld: /workspace/mimalloc/out/libmimalloc.a(alloc.c.o): in function `posix_memalign':
          alloc.c:(.text+0x1b0): multiple definition of `posix_memalign'; /home/gitpod/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/x86_64-unknown-linux-musl/lib/self-contained/libc.a(posix_memalign.lo):/build/musl-cross-make/build/local/x86_64-linux-musl/obj_musl/../src_musl/src/malloc/posix_memalign.c:5: first defined here
...

Patching musl libc.a in-place

Could we patch the musl sources, replace the existing malloc implementation with mimalloc and rebuild the entire thing? Yes, that can work, but there is a faster way: we can patch the musl libc.a shipped by rustup in-place!

$ LIBC_PATH=$(find ~/.rustup -name libc.a)
$ {
    echo "CREATE libc.a"
    echo "ADDLIB $LIBC_PATH"
    echo "DELETE aligned_alloc.lo calloc.lo donate.lo free.lo libc_calloc.lo lite_malloc.lo malloc.lo malloc_usable_size.lo memalign.lo posix_memalign.lo realloc.lo reallocarray.lo valloc.lo"
    echo "ADDLIB out/libmimalloc.a"
    echo "SAVE"
  } | ar -M
$ mv libc.a $LIBC_PATH

The above commands uses ar scripts to strip the original malloc implementation completely and replaces it with object files from libmimalloc.a.

ar scripts is a legacy feature that originates in the era of Motorola 68000 assembly, whose toolchain contains a scriptable “librarian” program that creates archives from object files. The language is self-explanatory, you may take a look at the documentation in either gnu ar or llvm-ar for more details.

Despite being a historical artifact, the script interface does provide one feature absent in the command-line interface: the ADDLIB command, which allows appending all members of an archive to the result, instead of appending the archive file as a member, which is exactly what we want in this use case.

Another interesting question is: where did the list of objects to be deleted from the original libc.a come from? Thankfully, the musl codebase is organized in a fine-grained manner, with roughly one C source file implementing one C standard library function. So I simply did a local musl build, checked defined symbols in each object file and found these object files. There’s no collateral damage to remove them, libmimalloc.a provides the same allocator with conforming ABI.

Anyway, now that libc.a has been patched, the original build command that targets musl will be capable of building a performant static executable:

benchmarking /workspace/wasmtime/target/x86_64-unknown-linux-musl/release/wasmtime run --disable-cache hello.wasm
time                 3.734 s    (3.537 s .. 3.878 s)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 3.825 s    (3.763 s .. 3.936 s)
std dev              106.5 ms   (2.226 ms .. 129.0 ms)
variance introduced by outliers: 19% (moderately inflated)

See, it’s even faster than the build that links against glibc!

Conclusion

The practice of statically linking against musl commonly enhances the portability of Linux executables. However, for substantial multi-core performance, it’s vital to substitute the malloc implementation with a more efficient one. While patching libc.a in-place might seem unconventional, it proves to be the most straightforward solution:

• It eliminates concerns about duplicate symbol errors during linking.
• There is no need to interfere with linker arguments in high-level build systems like cargo.
• This same technique can be used with Alpine’s own /usr/lib/libc.a, allowing mimalloc to function automatically with other languages such as C, C++, or Haskell.

mimalloc also comes in the form of a Rust crate and can be utilized to replace the Rust global allocator. In languages like Rust, C++, Zig, and potentially others, the heap allocator features an interface defined in the same language and can be overridden. This requires additional adjustments in the user’s project but is suitable for scenarios that don’t involve intensive interoperation with C.

Nonetheless, there could be unusual situations that assume the Rust/C heaps are identical, and the C side might free pointers that originate from the other side. In such circumstances, it’s advisable to override the global libc allocator and allow mimalloc to manage everything, utilizing the trick introduced in this blog post.

We also have a repo that provides a Dockerfile, it layers upon the official rust:alpine image and performs the patching logic described in this post. You could build and use the image per se in your CI pipelines in order to build static C/C++/Rust executables, or adopt the build script for your own needs. Happy hacking!

August 10, 2023 12:00 AM

The Meaning of Monad in MonadTrans

At work, someone noticed that they got a compiler warning for a derived instance of MonadTrans.

newtype FooT m a = FooT { unFooT :: StateT Int m a }
    deriving newtype
        (Functor, Applicative, Monad, MonadTrans)

GHC complained about a redundant Monad constraint. After passing -ddump-deriv, I saw that GHC was pasting in basically this instance:

instance MonadTrans FooT where
    lift :: Monad m => m a -> t m a
    lift = coerce (lift :: m a -> StateT Int m a)

The problem was that the Monad m constraint there is redundant - we’re not actually using it. However, it’s a mirror for the definition of the class method.

In transformers < 0.6, the definition of MonadTrans class looked like this:

class MonadTrans t where
    lift :: Monad m => m a -> t m a

In transformers-0.6, a quantified superclass constraint was added to MonadTrans:

class (forall m. Monad m => Monad (t m)) => MonadTrans t where
    lift :: Monad m => m a -> t m a

I’m having a bit of semantic satiation with the word Monad, which isn’t an unfamiliar phenomenon for a Haskell developer. However, while explaining this behavior, I found it to be a very subtle distinction in what these constraints fundamentally mean.

What is a Constraint?

A Constraint is a thing in Haskell that GHC needs to solve in order to make your code work. Solving a constraint is similar to proving a proposition in constructive logic - GHC needs to find evidence that the claim holds, in the form of a type class instance.

When we write:

foo :: Num a => a -> a
foo x = x * 2

We’re saying:

I have a polymorphic function foo which can operate on types, if those types are instances of the class Num.

If is the big thing here - it’s a way of making a conditional expression. For a totally polymorphic function, like id :: a -> a, there are no conditions. You can call it with any type you want. But a conditional polymorphic function expresses some requirements, or constraints, upon the input.

If you ask for constraints you don’t need, then you can get a warning by enabling -Wredundant-constraints.

woops :: (Bounded a, Num a) => a -> a
woops x = x + 5

GHC will happily warn us that we don’t actually use the Bounded a constraint, and it’s redundant. We should delete it. Indeed, there are many Num that aren’t Bounded, and by requiring Bounded, we are reducing the potential types we could call this function on for no reason.

Constraints Liberate

(from Constraints Liberate, Liberties Constrain)

A constraint is a perspective on what is happening - it is the perspective of the caller of a function. It’s almost like I see a function type:

someCoolFunction :: _ => a -> b

And think - “Ah hah! I can call this at any type a and b that I want!” Only to find that there’s a bunch of constraints on a and b, and now I am constrained in the types I can call this function at.

However, a constraint feels very different from the implementer of a function. Let’s look at the classic identity function:

id :: a -> a
id a = a

As an implementer, I have quite a few constraints! Indeed, I can’t really do anything here. I can write equivalent functions, or much slower versions of this function, or I can escape hatch with unsafe behavior - but my options are really pretty limited.

id' :: a -> a
id' a = repeat a !! 1000

id'' :: a -> a
id'' a = let y = a in y

id''' :: a -> a
id''' a = iterate id' a !! 1000

However, a Constraint means that I now have some extra power.

foo :: Num a => a -> a

With this signature, I now have access to the Num type class methods, as well as any other function that is polymorphic over Num. The constraint is a liberty - I have gained the power to do stuff with the input.

The Two Monads

Back to MonadTrans -

class
    (forall m. Monad m => Monad (t m))
  =>
    MonadTrans t
  where
    lift :: Monad m => m a -> t m a

Method Constraint

Let’s talk about that lift constraint.

    lift :: Monad m => m a -> t m a

This constraint means that the input to lift must prove that it is a Monad. This means that, as implementers of lift, we can use the methods on Monad in order to make lift work out. We often don’t need it - consider these instances.

newtype IdentityT m a = IdentityT (m a)

instance MonadTrans IdentityT where
    lift action = IdentityT action

IdentityT can use the constructor directly, and does not require any methods at all to work with action.

newtype ReaderT r m a = ReaderT (r -> m a)

instance MonadTrans (ReaderT r) where
    lift action = ReaderT $ \_ -> action

ReaderT uses the constructor and throws away the r.

newtype ExceptT e m a = ExceptT (m (Either e a))

instance MonadTrans (ExceptT e) where
    lift action = ExceptT $ fmap Right action

Ah, now we’re using the Functor method fmap in order to make the inner action fit. We’re given an action :: m a, and we need an m (Either e a). And we’ve got Right :: a -> Either e a and fmap to make it work. We are allowed to call fmap here because Monad implies Applicative implies Functor, and we’ve been given the Monad m constraint as part of the method.

Superclass Constraint

Let’s talk about the quantified superclass constraint (wow, what a fancy phrase).

    (forall m. Monad m => Monad (t m))

This superclass constraint means that the type t m a is a Monad if m is a Monad, and this is true for all m, not just a particular one. Prior to this, if you wanted to write a do block thta was arbitrary in a monad transformer, you’d have to write:

ohno :: (Monad (t m), Monad m, MonadTrans t) => m a -> t m a
ohno action = do
    lift action
    lift action

What’s more annoying is that, if you had a few different underlying type parameters, you’d need to request the Monad (t m) for each one - Monad (t m), Monad (t n), Monad (t f). Boring and redundant. Obviously, if m is a Monad, and t is a MonadTransformer, then t m must also be a Monad - otherwise it’s not a valid MonadTransformer!

So this Constraint is slightly different. The first perspective on Constraint is the user of a function:

I am constrained in the types I can use a function with

The second perspective on Constraint is the implementer of a function:

By constraining my inputs, I gain knowledge and power over them

But this superclass constraint is a bit different. It doesn’t seem to be about requiring anything from our users. It also doesn’t seem to be about allowing more power for implementers.

Instead, it’s a form of evidence propagation. We’re saying:

GHC, if you know that m is a Monad, then you may also infer that t m is a Monad.

Type classes form a compositional tool for logic programming. Constraints like these are a conditional proposition that allow GHC to see more options for solving and satisfying problems.

The Koan of Constraint

Four blind monks touch a Constraint, trying to identify what it is.

The first exclaims “This is a tool for limiting people.” The second laughs and says, “No, this is a tool for empowering people!” The third shakes his head solemnly and retorts, “No, this is a tool for clarifying wisdom.”

The fourth says “I cannot satisfy this.”

August 10, 2023 12:00 AM

The Problem with Counterfeit People

 

A sensible proposal in The Atlantic from philosopher Daniel Dennett. Is anyone campaigning for a law or regulation to this effect?

Creating counterfeit digital people risks destroying our civilization. Democracy depends on the informed (not misinformed) consent of the governed. By allowing the most economically and politically powerful people, corporations, and governments to control our attention, these systems will control us. Counterfeit people, by distracting and confusing us and by exploiting our most irresistible fears and anxieties, will lead us into temptation and, from there, into acquiescing to our own subjugation.

There may be a way of at least postponing and possibly even extinguishing this ominous development, borrowing from the success—limited but impressive—in keeping counterfeit money merely in the nuisance category for most of us (or do you carefully examine every $20 bill you receive?).

As [historian Yuval Noah] Harari says, we must “make it mandatory for AI to disclose that it is an AI.” How could we do that? By adopting a high-tech “watermark” system like the EURion Constellation, which now protects most of the world’s currencies. The system, though not foolproof, is exceedingly difficult and costly to overpower—not worth the effort, for almost all agents, even governments. Computer scientists similarly have the capacity to create almost indelible patterns that will scream FAKE! under almost all conditions—so long as the manufacturers of cellphones, computers, digital TVs, and other devices cooperate by installing the software that will interrupt any fake messages with a warning.

by Philip Wadler (noreply@blogger.com) at August 07, 2023 09:38 PM

Will A.I. become the new McKinsey?

Ted Chiang, ever thoughtful, suggests a new metaphor for A.I. Published in The New Yorker.

So, I would like to propose another metaphor for the risks of artificial intelligence. I suggest that we think about A.I. as a management-consulting firm, along the lines of McKinsey & Company. Firms like McKinsey are hired for a wide variety of reasons, and A.I. systems are used for many reasons, too. But the similarities between McKinsey—a consulting firm that works with ninety per cent of the Fortune 100—and A.I. are also clear. Social-media companies use machine learning to keep users glued to their feeds. In a similar way, Purdue Pharma used McKinsey to figure out how to “turbocharge” sales of OxyContin during the opioid epidemic. Just as A.I. promises to offer managers a cheap replacement for human workers, so McKinsey and similar firms helped normalize the practice of mass layoffs as a way of increasing stock prices and executive compensation, contributing to the destruction of the middle class in America.

A former McKinsey employee has described the company as “capital’s willing executioners”: if you want something done but don’t want to get your hands dirty, McKinsey will do it for you. That escape from accountability is one of the most valuable services that management consultancies provide. Bosses have certain goals, but don’t want to be blamed for doing what’s necessary to achieve those goals; by hiring consultants, management can say that they were just following independent, expert advice. Even in its current rudimentary form, A.I. has become a way for a company to evade responsibility by saying that it’s just doing what “the algorithm” says, even though it was the company that commissioned the algorithm in the first place.

by Philip Wadler (noreply@blogger.com) at August 07, 2023 09:09 PM

Our Labor Built AI

 

An introduction for laymen from The Nib. By Dan Nott and Scott Cambo.

by Philip Wadler (noreply@blogger.com) at July 31, 2023 12:53 PM

Diagrams for Penrose Tiles

Penrose Kite and Dart Tilings with Haskell Diagrams

Revised version (no longer the full program in this literate Haskell)

Infinite non-periodic tessellations of Roger Penrose’s kite and dart tiles.

As part of a collaboration with Stephen Huggett, working on some mathematical properties of Penrose tilings, I recognised the need for quick renderings of tilings. I thought Haskell diagrams would be helpful here, and that turned out to be an excellent choice. Two dimensional vectors were well-suited to describing tiling operations and these are included as part of the diagrams package.

This literate Haskell uses the Haskell diagrams package to draw tilings with kites and darts. It also implements the main operations of compChoices and decompPatch which are essential for constructing tilings (explained below).

Firstly, these 5 lines are needed in Haskell to use the diagrams package:

{-# LANGUAGE NoMonomorphismRestriction #-}
{-# LANGUAGE FlexibleContexts          #-}
{-# LANGUAGE TypeFamilies              #-}

import Diagrams.Prelude
import Diagrams.Backend.SVG.CmdLine

and we will also import a module for half tiles (explained later)

import HalfTile

Legal tilings

These are the kite and dart tiles.

The red line marking here on the right hand copies, is purely to illustrate rules about how tiles can be put together for legal (non-periodic) tilings. Obviously edges can only be put together when they have the same length. If all the tiles are marked with red lines as illustrated on the right, the vertices where tiles meet must all have a red line or none must have a red line at that vertex. This prevents us from forming a simple rombus by placing a kite top at the base of a dart and thus enabling periodic tilings.

All edges are powers of the golden section which we write as phi.

phi::Double
phi = (1.0 + sqrt 5.0) / 2.0

So if the shorter edges are unit length, then the longer edges have length phi. We also have the interesting property of the golden section that and so , and .

All angles in the figures are multiples of tt which is 36 deg or 1/10 turn. We use ttangle to express such angles (e.g 180 degrees is ttangle 5).

ttangle:: Int -> Angle Double
ttangle n = (fromIntegral (n `mod` 10))*^tt
             where tt = 1/10 @@ turn

Pieces

In order to implement compChoices and decompPatch, we need to work with half tiles. We now define these in the separately imported module HalfTile with constructors for Left Dart, Right Dart, Left Kite, Right Kite

data HalfTile rep = LD rep -- defined in HalfTile module
                  | RD rep
                  | LK rep
                  | RK rep

where rep is a type variable allowing for different representations. However, here, we want to use a more specific type which we will call Piece:

type Piece = HalfTile (V2 Double)

where the half tiles have a simple 2D vector representation to provide orientation and scale. The vector represents the join edge of each half tile where halves come together. The origin for a dart is the tip, and the origin for a kite is the acute angle tip (marked in the figure with a red dot).

These are the only 4 pieces we use (oriented along the x axis)

ldart,rdart,lkite,rkite:: Piece
ldart = LD unitX
rdart = RD unitX
lkite = LK (phi*^unitX)
rkite = RK (phi*^unitX)

Perhaps confusingly, we regard left and right of a dart differently from left and right of a kite when viewed from the origin. The diagram shows the left dart before the right dart and the left kite before the right kite. Thus in a complete tile, going clockwise round the origin the right dart comes before the left dart, but the left kite comes before the right kite.

When it comes to drawing pieces, for the simplest case, we just want to show the two tile edges of each piece (and not the join edge). These edges are calculated as a list of 2 new vectors, using the join edge vector v. They are ordered clockwise from the origin of each piece

pieceEdges:: Piece -> [V2 Double]
pieceEdges (LD v) = [v',v ^-^ v'] where v' = phi*^rotate (ttangle 9) v
pieceEdges (RD v) = [v',v ^-^ v'] where v' = phi*^rotate (ttangle 1) v
pieceEdges (RK v) = [v',v ^-^ v'] where v' = rotate (ttangle 9) v
pieceEdges (LK v) = [v',v ^-^ v'] where v' = rotate (ttangle 1) v

Now drawing lines for the 2 outer edges of a piece is simply

drawPiece:: Piece -> Diagram B
drawPiece = strokeLine . fromOffsets . pieceEdges

It is also useful to calculate a list of the 4 tile edges of a completed half-tile piece clockwise from the origin of the tile. (This is useful for colour filling a tile)

wholeTileEdges:: Piece -> [V2 Double]
wholeTileEdges (LD v) 
   = pieceEdges (RD v) ++ map negated (reverse (pieceEdges (LD v)))
wholeTileEdges (RD v) 
   = tileEdges (LD v)
wholeTileEdges (LK v)
   = pieceEdges (LK v) ++ map negated (reverse (pieceEdges (RK v)))
wholeTileEdges (RK v)
   = tileEdges (LK v)

To fill whole tiles with colours, darts with dcol and kites with kcol we can use leftFillDK. This uses only the left pieces to identify the whole tile and ignores right pieces so that a tile is not filled twice.

leftFillDK:: Colour Double -> Colour Double -> Piece -> Diagram B
leftFillDK dcol kcol c =
  case c of (LD _) -> (strokeLoop $ glueLine $ fromOffsets $ tileEdges c)
                       # fc dcol
            (LK _) -> (strokeLoop $ glueLine $ fromOffsets $ tileEdges c)
                        # fc kcol
            _      -> mempty

To fill half tiles separately, we can use fillPiece which fills without drawing edges of a half tile.

fillPiece:: Colour Double -> Piece -> Diagram B
fillPiece col piece = drawJPiece piece # fc col # lw none

drawJPiece:: Piece -> Diagram B
drawJPiece = strokeLoop . closeLine . fromOffsets . pieceEdges

For an alternative fill operation  we can use fillDK which fills darts and kites with given colours and draws the edges with drawPiece.

fillDK:: Colour Double -> Colour Double -> Piece -> Diagram B
fillDK dcol kcol piece = drawPiece piece <> fillPiece col piece where
    col = case piece of (LD _) -> dcol
           (RD _) -> dcol
           (LK _) -> kcol
           (RK _) -> kcol

By making Pieces transformable we can reuse generic transform operations. These 4 lines of code are required to do this

type instance N (HalfTile a) = N a
type instance V (HalfTile a) = V a
instance Transformable a => Transformable (HalfTile a) where
    transform t ht = fmap (transform t) ht

So we can also scale a piece  and rotate a piece by an angle. (Positive rotations are in the anticlockwise direction.)

scale :: Double -> Piece -> Piece
rotate :: Angle Double -> Piece -> Piece

Patches

A patch is a list of located pieces (each with a 2D point)

type Patch = [Located Piece]

To turn a whole patch into a diagram using some function pd for drawing the pieces, we use

drawPatchWith:: (Piece -> Diagram B) -> Patch -> Diagram B 
drawPatchWith pd patch = position $ fmap (viewLoc . mapLoc pd) patch

Here mapLoc applies a function to the piece in a located piece – producing a located diagram in this case, and viewLoc returns the pair of point and diagram from a located diagram. Finally position forms a single diagram from the list of pairs of points and diagrams.

The common special case drawPatch uses drawPiece on each piece

drawPatch = patchWith drawPiece

Patches are automatically inferred to be transformable now Pieces are transformable, so we can also scale a patch, translate a patch by a vector, and rotate a patch by an angle.

scale :: Double -> Patch -> Patch
rotate :: Angle Double -> Patch -> Patch
translate :: V2 Double -> Patch -> Patch

As an aid to creating patches with 5-fold rotational symmetry, we combine 5 copies of a basic patch (rotated by multiples of ttangle 2 successively).

penta:: Patch -> Patch
penta p = concatMap copy [0..4] 
            where copy n = rotate (ttangle (2*n)) p

This must be used with care to avoid nonsense patches. But two special cases are

sun,star::Patch         
sun =  penta [rkite `at` origin, lkite `at` origin]
star = penta [rdart `at` origin, ldart `at` origin]

This figure shows some example patches, drawn with drawPatch The first is a star and the second is a sun.

The tools so far for creating patches may seem limited (and do not help with ensuring legal tilings), but there is an even bigger problem.

Correct Tilings

Unfortunately, correct tilings – that is, tilings which can be extended to infinity – are not as simple as just legal tilings. It is not enough to have a legal tiling, because an apparent (legal) choice of placing one tile can have non-local consequences, causing a conflict with a choice made far away in a patch of tiles, resulting in a patch which cannot be extended. This suggests that constructing correct patches is far from trivial.

The infinite number of possible infinite tilings do have some remarkable properties. Any finite patch from one of them, will occur in all the others (infinitely many times) and within a relatively small radius of any point in an infinite tiling. (For details of this see links at the end)

This is why we need a different approach to constructing larger patches. There are two significant processes used for creating patches, namely compChoices and decompPatch.

To understand these processes, take a look at the following figure.

Here the small pieces have been drawn in an unusual way. The edges have been drawn with dashed lines, but long edges of kites have been emphasised with a solid line and the join edges of darts marked with a red line. From this you may be able to make out a patch of larger scale kites and darts. This is a composed patch arising from the smaller scale patch. Conversely, the larger kites and darts decompose to the smaller scale ones.

Decomposition

Since the rule for decomposition is uniquely determined, we can express it as a simple function on patches.

decompPatch :: Patch -> Patch
decompPatch = concatMap decompPiece

where the function decompPiece acts on located pieces and produces a list of the smaller located pieces contained in the piece. For example, a larger right dart will produce both a smaller right dart and a smaller left kite. Decomposing a located piece also takes care of the location, scale and rotation of the new pieces.

decompPiece lp = case viewLoc lp of
  (p, RD vd)-> [ LK vd  `at` p
               , RD vd' `at` (p .+^ v')
               ] where v'  = phi*^rotate (ttangle 1) vd
                       vd' = (2-phi) *^ (negated v') -- (2-phi) = 1/phi^2
  (p, LD vd)-> [ RK vd `at` p
               , LD vd' `at` (p .+^ v')
               ]  where v'  = phi*^rotate (ttangle 9) vd
                        vd' = (2-phi) *^ (negated v')  -- (2-phi) = 1/phi^2
  (p, RK vk)-> [ RD vd' `at` p
               , LK vk' `at` (p .+^ v')
               , RK vk' `at` (p .+^ v')
               ] where v'  = rotate (ttangle 9) vk
                       vd' = (2-phi) *^ v' -- v'/phi^2
                       vk' = ((phi-1) *^ vk) ^-^ v' -- (phi-1) = 1/phi
  (p, LK vk)-> [ LD vd' `at` p
               , RK vk' `at` (p .+^ v')
               , LK vk' `at` (p .+^ v')
               ] where v'  = rotate (ttangle 1) vk
                       vd' = (2-phi) *^ v' -- v'/phi^2
                       vk' = ((phi-1) *^ vk) ^-^ v' -- (phi-1) = 1/phi

This is illustrated in the following figure for the cases of a right dart and a right kite.

The symmetric diagrams for left pieces are easy to work out from these, so they are not illustrated.

With the decompPatch operation we can start with a simple correct patch, and decompose repeatedly to get more and more detailed patches. (Each decomposition scales the tiles down by a factor of but we can rescale at any time.)

This figure illustrates how each piece decomposes with 4 decomposition steps below each one.

thePieces =  [ldart, rdart, lkite, rkite]  
fourDecomps = hsep 1 $ fmap decomps thePieces # lw thin where
        decomps pc = vsep 1 $ fmap drawPatch $ take 5 $ decompositionsP [pc `at` origin] 

We have made use of the fact that we can create an infinite list of finer and finer decompositions of any patch, using:

decompositionsP:: Patch -> [Patch]
decompositionsP = iterate decompPatch

We could get the n-fold decomposition of a patch as just the nth item in a list of decompositions.

For example, here is an infinite list of decomposed versions of sun.

suns = decompositionsP sun

The coloured tiling shown at the beginning is simply 6 decompositions of sun displayed using leftFillDK

sun6 = suns!!6
filledSun6 = drawPatchWith (leftFillDK red blue) sun6 # lw ultraThin

The earlier figure illustrating larger kites and darts emphasised from the smaller ones is also sun6 but this time drawn with

experimentFig = drawPatchWith experiment sun6 # lw thin

where pieces are drawn with

experiment:: Piece -> Diagram B
experiment pc = emph pc <> (drawJPiece pc # dashingN [0.002,0.002] 0
                            # lw ultraThin)
  where emph pc = case pc of
   -- emphasise join edge of darts in red
          (LD v) -> (strokeLine . fromOffsets) [v] # lc red
          (RD v) -> (strokeLine . fromOffsets) [v] # lc red 
   -- emphasise long edges for kites
          (LK v) -> (strokeLine . fromOffsets) [rotate (ttangle 1) v]
          (RK v) -> (strokeLine . fromOffsets) [rotate (ttangle 9) v]

Compose Choices

You might expect composition to be a kind of inverse to decomposition, but it is a bit more complicated than that. With our current representation of pieces, we can only compose single pieces. This amounts to embedding the piece into a larger piece that matches how the larger piece decomposes. There is thus a choice at each composition step as to which of several possibilities we select as the larger half-tile. We represent this choice as a list of alternatives. This list should not be confused with a patch. It only makes sense to select one of the alternatives giving a new single piece.

The earlier diagram illustrating how decompositions are calculated also shows the two choices for embedding a right dart into either a right kite or a larger right dart. There will be two symmetric choices for a left dart, and three choices for left and right kites.

Once again we work with located pieces to ensure the resulting larger piece contains the original in its original position in a decomposition.

compChoices :: Located Piece -> [Located Piece]
compChoices lp = case viewLoc lp of
  (p, RD vd)-> [ RD vd' `at` (p .+^ v')
               , RK vk  `at` p
               ] where v'  = (phi+1) *^ vd       -- vd*phi^2
                       vd' = rotate (ttangle 9) (vd ^-^ v')
                       vk  = rotate (ttangle 1) v'
  (p, LD vd)-> [ LD vd' `at` (p .+^ v')
               , LK vk `at` p
               ] where v'  = (phi+1) *^ vd        -- vd*phi^2
                       vd' = rotate (ttangle 1) (vd ^-^ v')
                       vk  = rotate (ttangle 9) v'
  (p, RK vk)-> [ LD vk  `at` p
               , LK lvk' `at` (p .+^ lv') 
               , RK rvk' `at` (p .+^ rv')
               ] where lv'  = phi*^rotate (ttangle 9) vk
                       rv'  = phi*^rotate (ttangle 1) vk
                       rvk' = phi*^rotate (ttangle 7) vk
                       lvk' = phi*^rotate (ttangle 3) vk
  (p, LK vk)-> [ RD vk  `at` p
               , RK rvk' `at` (p .+^ rv')
               , LK lvk' `at` (p .+^ lv')
               ] where v0 = rotate (ttangle 1) vk
                       lv'  = phi*^rotate (ttangle 9) vk
                       rv'  = phi*^rotate (ttangle 1) vk
                       rvk' = phi*^rotate (ttangle 7) vk
                       lvk' = phi*^rotate (ttangle 3) vk

As the result is a list of alternatives, we need to select one to make further composition choices. We can express all the alternatives after n steps as compNChoices n where

compNChoices :: Int -> Located Piece -> [Located Piece]
compNChoices 0 lp = [lp]
compNChoices n lp = do
    lp' <- compChoices lp
    compNChoices (n-1) lp'

This figure illustrates 5 consecutive choices for composing a left dart to produce a left kite. On the left, the finishing piece is shown with the starting piece embedded, and on the right the 5-fold decomposition of the result is shown.

fiveCompChoices = hsep 1 $ fmap drawPatch [[ld,lk'], multiDecomp 5 [lk']] where 
-- two separate patches
       ld  = (ldart `at` origin)
       lk  = compChoices ld  !!1
       rk  = compChoices lk  !!1
       rk' = compChoices rk  !!2
       ld' = compChoices rk' !!0
       lk' = compChoices ld' !!1

Finally, at the end of this literate haskell program we choose which figure to draw as output.

fig::Diagram B
fig = filledSun6

main = mainWith fig

That’s it. But, What about composing whole patches?, I hear you ask. Unfortunately we need to answer questions like what pieces are adjacent to a piece in a patch and whether there is a corresponding other half for a piece. These cannot be done easily with our simple vector representations. We would need some form of planar graph representation, which is much more involved. That is another story.

Many thanks to Stephen Huggett for his inspirations concerning the tilings. A library version of the above code is available on GitHub

Further reading on Penrose Tilings

As well as the Wikipedia entry Penrose Tilings I recommend two articles in Scientific American from 2005 by David Austin Penrose Tiles Talk Across Miles and Penrose Tilings Tied up in Ribbons.

There is also a very interesting article by Roger Penrose himself: Penrose R Tilings and quasi-crystals; a non-local growth problem? in Aperiodicity and Order 2, edited by Jarich M, Academic Press, 1989.

More information about the diagrams package can be found from the home page Haskell diagrams

by readerunner at July 31, 2023 09:05 AM

Yamaha vs NS Design Electric Cellos

I’ve been learning cello again recently. The omnipresent advice for novices is to rent a cello from a reputable violin shop, which is great - my cello would be $2,700 new, but I’m renting it for $50/mo. And I can tell I’ll outgrow it, and I don’t know how to properly evaluate an acoustic cello for great suitability yet.

I’ve got a practice mute, but it’s still rather loud - I can’t practice at night or early in the morning without waking someone up in my house. This led me to look at electric cellos for practice. There are essentially three options:

• Shitty Cecilio electrics
• Yamaha silent cellos
• NS Design electric cellos

I had the opportunity to visit Luther Strings this past weekend to try the Yamaha and NS Design cellos.

Avoid Cecilio

First of all, the prices on the Yamaha and NS Design are high - you may be tempted to shop elsewhere for your first instrument. The Cecilio seems like a good deal at $530, but it isn’t. A friend of mine purchased one in college (budgets, hey). The electronics are awful - bad sound, noisy, connections are inconsistent and cut out. I lined it with tin foil and resoldered most of the joints, which helped. It wouldn’t hold tune, so I installed geared bass tuners. The bridge needs to be shorter and the fingerboard needs to be planed, which I can’t reasonably DIY and the luthiers want $100s to do it. The strings are uncomfortable, too, and they don’t sound good. It’ll cost about as much to get the instrument in usable condition as it does to buy it.

You could start on this, but you’d quickly be dismayed at the difficulty in pressing the strings down, the noise from the electronics, and the impossibility of drawing a good tone from it. You’re far better off saving more money to buy a nicer one, or seeing if anyone nearby can rent one of these - a string shop that carries electrics may be willing to do that.

Yamaha

Yamaha makes a range of silent practice cellos. They happen to be electric, but the clear intended purpose is for silent practice. They have body shapes that make it feel like a traditional cello - there’s a shoulder where you’d expect to go into thumb position, a frame for your legs, and a metal bit that rests on your chest. The electronics are all active, and have an A/C adapter - they have headphone outputs and reverb built-in. They also have a hookup for an auxiliary input, which would allow you to plug an MP3 player and listen to a backing track while you play.

The cheapest option is the Yamaha SVC-50 at $2,100.

NS Design

NS Design makes a range of electric cellos. They happen to be quiet, but the clear intended purpose is for playing electric cello. The shape is highly non-traditional - the neck is unobstructed throughout, and there’s nothing but a stick on the cello itself. You can play with an included adjustable tripod to find the right position, or you can purchase a frame/end-pin mount, or a strap system for standing upright. On the low end, the electronics are simple - a passive pickup, a switch for arco or pizzicato playing, a volume know, and a tone knob - much like you’d find on an electric guitar or bass.

The cheapest option is the NS Design WAV4 at $1,259 (though Shar Music has one for $999). While this is significantly cheaper than the Yamaha, you’ll probably want the cello endpin stand at $385, and maybe the frame strap system at $259, or the thumbstop for $116. The cost is now $1,759, and you still can’t plug headphones directly into the instrument - for that, you need to go up to the CR series, which are around $4,000 (but have active electronics and a headphone jack).

Comparison

These are two pretty different items. However, they have a lot of overlap - and so deciding between them may be a challenge.

Cost

The NS Design WAV4 has a much lower entry price - at $999 from Shar, it’s a fantastic deal, and even the $1,259 from other retailers is good. However, the endpin stand is expensive and necessary to get the mobility and feel of a traditional cello, which would be an important purchase if the intent is to practice for traditional cello. The WAV4 also only has passive electronics and an instrument output - you need an amplifier of some sort to drive headphones.

The Yamaha is $2,100, but it is fully loaded. You buy it, and you’ll be able to practice cello silently with a backing track right now. You don’t need anything else.

Once you’ve bought the accessories you need to make these equivalent, the cost ends up around the same. This is defrayed a bit if you already have some of the amplifier/headphone gear for the NS cello from playing electric guitar.

Playing vs Traditional Cello

The Yamaha silent cello feels like a traditional cello. The chest stop feels right, and the two leg frames feel right. You can move the cello with your knees to get different string angles and to aide expressive playing. The shoulder of the cello indicates when you’d need to shift to thumb position on a traditional cello. Unfortunately, I found the fingerboard to be oddly shaped, and the strings were a bit high. It was far better than the Cecilio I’ve played, but I do still feel like a proper setup from a luthier would help dramatically. I’d say it feels like a $1,000 cello with $1,000 of electronics.

The NS Design doesn’t feel like a traditional cello at all. On the stock tripod, there’s no chest or leg support. The instrument sits in a fixed position. This doesn’t feel natural coming from an acoustic cello. I didn’t try the endpin stand, as the shop didn’t have it. The lack of shoulder means you have no indication when you’d need to shift into thumb position. There’s a single brass dot on the back of the neck that’s roughly where fourth position is.

The Yamaha clearly feels more like a traditional cello.

Playing as an Electric Cello

Yamaha’s intent is to allow you to pretend you are playing a real acoustic cello. Yamaha makes a comparable guitar - it’s their SLG200S silent acoustic guitar. The Yamaha silent cello doesn’t really feel like an instrument I’d want to play on. I definitely wouldn’t want to write music for it, or perform with. It’s for practice, and it lives in the shadow of the acoustic cello. You never want to play the Yamaha - you’d rather be playing your acoustic - but sometimes, hey, this is good enough, and better than nothing.

NS Design can sacrifice a lot of the engineering and design that the Yamaha needs for this in order to produce an instrument that stands alone. In the same way that a Fender Stratocaster or Gibson Les Paul are different instruments than an acoustic guitar, the NS Cello isn’t trying to be something that it isn’t. The tripod is sturdy and would work fine on stage. The frame strap allows you to stand and walk while playing - something the Yamaha simply cannot do, not even with The Block Strap, since the instrument is designed differently. The lack of a shoulder bout means you don’t have an indicator on when to shift - but that really just opens up the range of the upper end of the cello significantly. Just like how a classical guitar often has the shoulder bout on the 12th fret, but electric guitars can go up to 24 frets.

The NS Design cello simply feels much better to play. It’s easier to play double stops and sound notes. The neck has a nice feel to it. I can easily imagine playing this instrument for itself - writing music, performing with it, recording with it, etc.

Sound Quality

Electronics absolutely dominate the tone of an electric instrument.

The Yamaha cello is slightly noisy. You can hear a static hiss in the background. There’s no tone knob or onboard EQ, so the sound you get is what you get. In my opinion, it doesn’t sound great. However, it is a complete practice solution - and if you’re just practicing, the richness of tone doesn’t really matter. You can hear your technique just fine.

Now, I did not try the WAV4. I tried a 5 string CR, with active electronics - volume, switch, and an active EQ knob for bass and treble. The NS Design sounds great. The arco/pizzo switch yields some interesting tone combinations - while everything sounds great on the arco setting, the pizzicato setting brings out much more sustain, similar to a guitar. The electronics are quiet - no detectable noise. I found it easy to produce a tone that sounded good - you wouldn’t confuse it for an acoustic cello, but you wouldn’t think it sounded bad at all.

The WAV4 has the same pickup as the CR, but the electronics are passive. This means you only get a treble roll-off knob and a volume knob, plus the arco/pizzicato switch. I tend to prefer passive electronics anyway - both the Yamaha and NS Design cellos ran out of battery power during my trial, and produced some gnarly bad tone.

In my opinion, the NS Design wins here.

Overall fit/finish/feel

The NS Design CR cello feels fantastic. The craftsmanship is superb. Everything is sturdy and feels great. I think it looks nice, too - a quality wood finish and a pattern of dots on the fingerboard provide some visual interest for what is otherwise just a stick.

The Yamaha feels a bit like a toy. The aesthetics are pretty bare - it’s a black shape with some stuff sticking out. The tuners are kinda cheap looking. I didn’t get a great feeling for it.

Conclusion

Well, the Yamaha is clearly a better instrument for practicing traditional acoustic cello. No question about it. If all you care about is an all-in-one travel cello and the ability to practice without bothering anyone, then the Yamaha is the winner.

However, the NS Design has a lot of compelling points in it’s favor. It’s an instrument in-and-of-itself. It’s not trying to be an acoustic cello but quiet, and this allows it to have many advantages over the Yamaha. The sound is better than the Yamaha. In many ways, playing the NS Cello is even easier than an acoustic cello, and certainly much better feeling than the Yamaha.

Overall, I feel compelled by the advantages of the NS cello. I’ll need to invest in the endpin stand, and I may try to fashion a detachable shoulder bout so I know when to practice thumb position. I’ve been intending on getting a music studio going, which would satisfy the headphone amp problem, and I could also use any electric guitar amp.

I may regret the decision and decide that I don’t actually care about the electric cello features, and what I really did want was just a practice cello. But we’ll see!

July 31, 2023 12:00 AM

Graphs, Kites and Darts

Graphs, Kites and Darts

Non-periodic tilings with Penrose’s kites and darts

(An updated version, since original posting on Jan 6, 2022)

We continue our investigation of the tilings using Haskell with Haskell Diagrams. What is new is the introduction of a planar graph representation. This allows us to define more operations on finite tilings, in particular forcing and composing.

Previously in Diagrams for Penrose Tiles we implemented tools to create and draw finite patches of Penrose kites and darts (such as the samples depicted in figure 1). The code for this and for the new graph representation and tools described here can be found on GitHub https://github.com/chrisreade/PenroseKiteDart.

To describe the tiling operations it is convenient to work with the half-tiles: LD (left dart), RD (right dart), LK (left kite), RK (right kite) using a polymorphic type HalfTile (defined in a module HalfTile)

data HalfTile rep 
 = LD rep | RD rep | LK rep | RK rep   deriving (Show,Eq)

Here rep is a type variable for a representation to be chosen. For drawing purposes, we chose two-dimensional vectors (V2 Double) and called these Pieces.

type Piece = HalfTile (V2 Double)

The vector represents the join edge of the half tile (see figure 2) and thus the scale and orientation are determined (the other tile edges are derived from this when producing a diagram).

Finite tilings or patches are then lists of located pieces.

type Patch = [Located Piece]

Both Piece and Patch are made transformable so rotate, and scale can be applied to both and translate can be applied to a Patch. (Translate has no effect on a Piece unless it is located.)

In Diagrams for Penrose Tiles we also discussed the rules for legal tilings and specifically the problem of incorrect tilings which are legal but get stuck so cannot continue to infinity. In order to create correct tilings we implemented the decompose operation on patches.

The vector representation that we use for drawing is not well suited to exploring properties of a patch such as neighbours of pieces. Knowing about neighbouring tiles is important for being able to reason about composition of patches (inverting a decomposition) and to find which pieces are determined (forced) on the boundary of a patch.

However, the polymorphic type HalfTile allows us to introduce our alternative graph representation alongside Pieces.

Tile Graphs

In the module Tgraph.Prelude, we have the new representation which treats half tiles as triangular faces of a planar graph – a TileFace – by specialising HalfTile with a triple of vertices (clockwise starting with the tile origin). For example

LD (1,3,4)       RK (6,4,3)

type Vertex = Int
type TileFace = HalfTile (Vertex,Vertex,Vertex)

When we need to refer to particular vertices from a TileFace we use originV (the first vertex – red dot in figure 2), oppV (the vertex at the opposite end of the join edge – dashed edge in figure 2), wingV (the remaining vertex not on the join edge).

originV, oppV, wingV :: TileFace -> Vertex

Tgraphs

The Tile Graphs implementation uses a type Tgraph which has a list of tile faces and a maximum vertex number.

data Tgraph = Tgraph { maxV  :: Vertex
                     , faces :: [TileFace]
                     }  deriving (Show)

For example, fool (short for a fool’s kite) is a Tgraph with 6 faces and 7 vertices, shown in figure 3.

fool = Tgraph { maxV = 7
              , faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
                        ,LK (6,3,2),RK (6,4,3),LK (6,7,4)
                        ]
              }

(The fool is also called an ace in the literature)

With this representation we can investigate how composition works with whole patches. Figure 4 shows a twice decomposed sun on the left and a once decomposed sun on the right (both with vertex labels). In addition to decomposing the right Tgraph to form the left Tgraph, we can also compose the left Tgraph to get the right Tgraph.

After implementing composition, we also explore a force operation and an emplace operation to extend tilings.

There are some constraints we impose on Tgraphs.

• No spurious vertices. The vertices of a Tgraph are the vertices that occur in the faces of the Tgraph (and maxV is the largest number occurring).

• Connected. The collection of faces must be a single connected component.

• No crossing boundaries. By this we mean that vertices on the boundary are incident with exactly two boundary edges. The boundary consists of the edges between the Tgraph faces and exterior region(s). This is important for adding faces.

• Tile connected. Roughly, this means that if we collect the faces of a Tgraph by starting from any single face and then add faces which share an edge with those already collected, we get all the Tgraph faces. This is important for drawing purposes.

In fact, if a Tgraph is connected with no crossing boundaries, then it must be tile connected. (We could define tile connected to mean that the dual graph excluding exterior regions is connected.)

Figure 5 shows two excluded graphs which have crossing boundaries at 4 (left graph) and 13 (right graph). The left graph is still tile connected but the right is not tile connected (the two faces at the top right do not have an edge in common with the rest of the faces.)

Although we have allowed for Tgraphs with holes (multiple exterior regions), we note that such holes cannot be created by adding faces one at a time without creating a crossing boundary. They can be created by removing faces from a Tgraph without necessarily creating a crossing boundary.

Important We are using face as an abbreviation for half-tile face of a Tgraph here, and we do not count the exterior of a patch of faces to be a face. The exterior can also be disconnected when we have holes in a patch of faces and the holes are not counted as faces either. In graph theory, the term face would generally include these other regions, but we will call them exterior regions rather than faces.

In addition to the constructor Tgraph we also use

checkedTgraph:: [TileFace] -> Tgraph

which creates a Tgraph from a list of faces, but also performs checks on the required properties of Tgraphs. We can then remove or select faces from a Tgraph and then use checkedTgraph to ensure the resulting Tgraph still satisfies the required properties.

selectFaces, removeFaces  :: [TileFace] -> Tgraph -> Tgraph
selectFaces fcs g = checkedTgraph (faces g `intersect` fcs)
removeFaces fcs g = checkedTgraph (faces g \\ fcs)

Edges and Directed Edges

We do not explicitly record edges as part of a Tgraph, but calculate them as needed. Implicitly we are requiring

• No spurious edges. The edges of a Tgraph are the edges of the faces of the Tgraph.

To represent edges, a pair of vertices (a,b) is regarded as a directed edge from a to b. A list of such pairs will usually be regarded as a directed edge list. In the special case that the list is symmetrically closed [(b,a) is in the list whenever (a,b) is in the list] we will refer to this as an edge list rather than a directed edge list.

The following functions on TileFaces all produce directed edges (going clockwise round a face).

type Dedge = (Vertex,Vertex)

joinE  :: TileFace -> (Vertex,Vertex)
  -- join edge - dashed in figure 2
shortE :: TileFace -> (Vertex,Vertex)
  -- the short edge which is not a join edge
longE  :: TileFace -> (Vertex,Vertex)
  -- the long edge which is not a join edge
faceDedges :: TileFace -> [(Vertex,Vertex)]
  -- all three directed edges clockwise from origin

For the whole Tgraph, we often want a list of all the directed edges of all the faces.

graphDedges :: Tgraph -> [(Vertex,Vertex)]
graphDedges g = concatMap faceDedges (faces g)

Because our graphs represent tilings they are planar (can be embedded in a plane) so we know that at most two faces can share an edge and they will have opposite directions of the edge. No two faces can have the same directed edge. So from graphDedges g we can easily calculate internal edges (edges shared by 2 faces) and boundary directed edges (directed edges round the external regions).

internalEdges, boundaryDedges :: Tgraph -> [(Vertex,Vertex)]

The internal edges of g are those edges which occur in both directions in graphDedges g. The boundary directed edges of g are the missing reverse directions in graphDedges g.

We also refer to all the long edges of a Tgraph (including kite join edges) as phiEdges (both directions of these edges).

phiEdges :: Tgraph -> [(Vertex, Vertex)]

This is so named because, when drawn, these long edges are phi times the length of the short edges (phi being the golden ratio which is approximately 1.618).

Drawing Tgraphs (Patches and VPatches)

The module Tgraph.Convert contains functions to convert a Tgraph to our previous vector representation (Patch) defined in TileLib so we can use the existing tools to produce diagrams.

However, it is convenient to have an intermediate stage (a VPatch = Vertex Patch) which contains both faces and calculated vertex locations (a finite map from vertices to locations). This allows vertex labels to be drawn and for faces to be identified and retained/excluded after the location information is calculated.

data VPatch = VPatch { vLocs :: VertexLocMap
                     , vpFaces::[TileFace]
                     } deriving Show

The conversion functions include

makeVP   :: Tgraph -> VPatch
dropLabels :: VPatch -> Patch -- discards vertex information

For drawing purposes we introduced a class Drawable which has a means to create a diagram when given a function to draw Pieces.

class Drawable a where
  drawWith :: (Piece -> Diagram B) -> a -> Diagram B

This allows us to make Patch, VPatch and Tgraph instances of Drawable, and we can define special cases for the most frequently used drawing tools.

draw :: Drawable a => a -> Diagram B
draw = drawWith drawPiece

drawj :: Drawable a => a -> Diagram B
drawj = drawWith dashjPiece

We also need to be able to create diagrams with vertex labels, so we also use

class DrawableLabelled a where
  drawLabelledWith :: (Piece -> Diagram B) -> a -> Diagram B

Both VPatch and Tgraph are made instances (but not Patch as this no longer has vertex information). The most common drawing cases with labelling are then

drawLabelled :: DrawableLabelled a => a -> Diagram B
drawLabelled = drawLabelledWith drawPiece

drawjLabelled :: DrawableLabelled a => a -> Diagram B
drawjLabelled = drawLabelledWith dashjPiece

One consequence of using abstract graphs is that there is no unique predefined way to orient or scale or position the VPatch (and Patch) arising from a Tgraph representation. Our implementation selects a particular join edge and aligns it along the x-axis (unit length for a dart, philength for a kite) and tile-connectedness ensures the rest of the VPatch (and Patch) can be calculated from this.

We also have functions to re-orient a VPatch and lists of VPatchs using chosen pairs of vertices. [Simply doing rotations on the final diagrams can cause problems if these include vertex labels. We do not, in general, want to rotate the labels – so we need to orient the VPatch before converting to a diagram]

Decomposing Graphs

We previously implemented decomposition for patches which splits each half-tile into two or three smaller scale half-tiles.

decompPatch :: Patch -> Patch

We now have a Tgraph version of decomposition in the module Tgraphs:

decompose :: Tgraph -> Tgraph

Graph decomposition is particularly simple. We start by introducing one new vertex for each long edge (the phiEdges) of the Tgraph. We then build the new faces from each old face using the new vertices.

As a running example we take fool (mentioned above) and its decomposition foolD

*Main> foolD = decomposeG fool

*Main> foolD
Tgraph { maxV = 14
       , faces = [LK (1,8,3),RD (2,3,8),RK (1,3,9)
                 ,LD (4,9,3),RK (5,13,2),LK (5,10,13)
                 ,RD (6,13,10),LK (3,2,13),RK (3,13,11)
                 ,LD (6,11,13),RK (3,14,4),LK (3,11,14)
                 ,RD (6,14,11),LK (7,4,14),RK (7,14,12)
                 ,LD (6,12,14)
                 ]
       }

which are best seen together (fool followed by foolD) in figure 6.

Composing Tgraphs, and Unknowns

Composing is meant to be an inverse to decomposing, and one of the main reasons for introducing our graph representation. In the literature, decomposition and composition are defined for infinite tilings and in that context they are unique inverses to each other. For finite patches, however, we will see that composition is not always uniquely determined.

In figure 7 (Two Levels) we have emphasised the larger scale faces on top of the smaller scale faces.

How do we identify the composed tiles? We start by classifying vertices which are at the wing tips of the (smaller) darts as these determine how things compose. In the interior of a graph/patch (e.g in figure 7), a dart wing tip always coincides with a second dart wing tip, and either

1. the 2 dart halves share a long edge. The shared wing tip is then classified as a largeKiteCentre and is at the centre of a larger kite. (See left vertex type in figure 8), or
2. the 2 dart halves touch at their wing tips without sharing an edge. This shared wing tip is classified as a largeDartBase and is the base of a larger dart. (See right vertex type in figure 8)

[We also call these (respectively) a deuce vertex type and a jack vertex type later in figure 10]

Around the boundary of a Tgraph, the dart wing tips may not share with a second dart. Sometimes the wing tip has to be classified as unknown but often it can be decided by looking at neighbouring tiles. In this example of a four times decomposed sun (sunD4), it is possible to classify all the dart wing tips as a largeKiteCentre or a largeDartBase so there are no unknowns.

If there are no unknowns, then we have a function to produce the unique composed Tgraph.

compose:: Tgraph -> Tgraph

Any correct decomposed Tgraph without unknowns will necessarily compose back to its original. This makes compose a left inverse to decompose provided there are no unknowns.

For example, with an (n times) decomposed sun we will have no unknowns, so these will all compose back up to a sun after n applications of compose. For n=4 (sunD4 – the smaller scale shown in figure 7) the dart wing classification returns 70 largeKiteCentres, 45 largeDartBases, and no unknowns.

Similarly with the simpler foolD example, if we classsify the dart wings we get

largeKiteCentres = [14,13]
largeDartBases = [3]
unknowns = []

In foolD (the right hand Tgraph in figure 6), nodes 14 and 13 are new kite centres and node 3 is a new dart base. There are no unknowns so we can use compose safely

*Main> compose foolD
Tgraph { maxV = 7
       , faces = [RD (1,2,3),LD (1,3,4),RK (6,2,5)
                 ,RK (6,4,3),LK (6,3,2),LK (6,7,4)
                 ]
       }

which reproduces the original fool (left hand Tgraph in figure 6).

However, if we now check out unknowns for fool we get

largeKiteCentres = []
largeDartBases = []
unknowns = [4,2]    

So both nodes 2 and 4 are unknowns. It had looked as though fool would simply compose into two half kites back-to-back (sharing their long edge not their join), but the unknowns show there are other possible choices. Each unknown could become a largeKiteCentre or a largeDartBase.

The question is then what to do with unknowns.

Partial Compositions

In fact our compose resolves two problems when dealing with finite patches. One is the unknowns and the other is critical missing faces needed to make up a new face (e.g the absence of any half dart).

It is implemented using an intermediary function for partial composition

partCompose:: Tgraph -> ([TileFace],Tgraph) 

partCompose will compose everything that is uniquely determined, but will leave out faces round the boundary which cannot be determined or cannot be included in a new face. It returns the faces of the argument Tgraph that were not used, along with the composed Tgraph.

Figure 9 shows the result of partCompose applied to two graphs. [These are force kiteD3 and force dartD3 on the left. Force is described later]. In each case, the excluded faces of the starting Tgraph are shown in pale green, overlaid by the composed Tgraph on the right.

Then compose is simply defined to keep the composed faces and ignore the unused faces produced by partCompose.

compose:: Tgraph -> Tgraph
compose = snd . partCompose 

This approach avoids making a decision about unknowns when composing, but it may lose some information by throwing away the uncomposed faces.

For correct Tgraphs g, if decompose g has no unknowns, then compose is a left inverse to decompose. However, if we take g to be two kite halves sharing their long edge (not their join edge), then these decompose to fool which produces an empty Tgraph when recomposed. Thus we do not have g = compose (decompose g) in general. On the other hand we do have g = compose (decompose g) for correct whole-tile Tgraphs g (whole-tile means all half-tiles of g have their matching half-tile on their join edge in g)

Later (figure 21) we show another exception to g = compose (decompose g) with an incorrect tiling.

We make use of

selectFacesVP    :: [TileFace] -> VPatch -> VPatch
removeFacesVP    :: [TileFace] -> VPatch -> VPatch
selectFacesGtoVP :: [TileFace] -> Tgraph -> VPatch
removeFacesGtoVP :: [TileFace] -> Tgraph -> VPatch

for creating VPatches from selected tile faces of a Tgraph or VPatch. This allows us to represent and draw a subgraph which need not be connected nor satisfy the no crossing boundaries property provided the Tgraph it was derived from had these properties.

Forcing

When building up a tiling, following the rules, there is often no choice about what tile can be added alongside certain tile edges at the boundary. Such additions are forced by the existing patch of tiles and the rules. For example, if a half tile has its join edge on the boundary, the unique mirror half tile is the only possibility for adding a face to that edge. Similarly, the short edge of a left (respectively, right) dart can only be matched with the short edge of a right (respectively, left) kite. We also make use of the fact that only 7 types of vertex can appear in (the interior of) a patch, so on a boundary vertex we sometimes have enough of the faces to determine the vertex type. These are given the following names in the literature (shown in figure 10): sun, star, jack (=largeDartBase), queen, king, ace, deuce (=largeKiteCentre).

The function

force :: Tgraph -> Tgraph

will add some faces on the boundary that are forced (i.e new faces where there is exactly one possible choice). For example:

• When a join edge is on the boundary – add the missing half tile to make a whole tile.
• When a half dart has its short edge on the boundary – add the half kite that must be on the short edge.
• When a vertex is both a dart origin and a kite wing (it must be a queen or king vertex) – if there is a boundary short edge of a kite half at the vertex, add another kite half sharing the short edge, (this converts 1 kite to 2 and 3 kites to 4 in combination with the first rule).
• When two half kites share a short edge their common oppV vertex must be a deuce vertex – add any missing half darts needed to complete the vertex.
• …

Figure 11 shows foolDminus (which is foolD with 3 faces removed) on the left and the result of forcing, ie force foolDminus on the right which is the same Tgraph we get from force foolD (modulo vertex renumbering).

foolDminus = 
    removeFaces [RD(6,14,11), LD(6,12,14), RK(5,13,2)] foolD

Figures 12, 13 and 14 illustrate the result of forcing a 5-times decomposed kite, a 5-times decomposed dart, and a 5-times decomposed sun (respectively). The first two figures reproduce diagrams from an article by Roger Penrose illustrating the extent of influence of tiles round a decomposed kite and dart. [Penrose R Tilings and quasi-crystals; a non-local growth problem? in Aperiodicity and Order 2, edited by Jarich M, Academic Press, 1989. (fig 14)].

In figure 15, the bottom row shows successive decompositions of a dart (dashed blue arrows from right to left), so applying compose to each dart will go back (green arrows from left to right). The black vertical arrows are force. The solid blue arrows from right to left are (force . decompose) being applied to the successive forced Tgraphs. The green arrows in the reverse direction are compose again and the intermediate (partCompose) figures are shown in the top row with the remainder faces in pale green.

Figure 16 shows the forced graphs of the seven vertex types (with the starting Tgraphs in red) along with a kite (top right).

These are related to each other as shown in the columns. Each Tgraph composes to the one above (an empty Tgraph for the ones in the top row) and the Tgraph below is its forced decomposition. [The rows have been scaled differently to make the vertex types easier to see.]

Adding Faces to a Tgraph

This is technically tricky because we need to discover what vertices (and implicitly edges) need to be newly created and which ones already exist in the Tgraph. This goes beyond a simple graph operation and requires use of the geometry of the faces. We have chosen not to do a full conversion to vectors to work out all the geometry, but instead we introduce a local representation of relative directions of edges at a vertex allowing a simple equality test.

Edge directions

All directions are integer multiples of 1/10th turn (mod 10) so we use these integers for face internal angles and boundary external angles. The face adding process always adds to the right of a given directed edge (a,b) which must be a boundary directed edge. [Adding to the left of an edge (a,b) would mean that (b,a) will be the boundary direction and so we are really adding to the right of (b,a)]. Face adding looks to see if either of the two other edges already exist in the Tgraph by considering the end points a and b to which the new face is to be added, and checking angles.

This allows an edge in a particular sought direction to be discovered. If it is not found it is assumed not to exist. However, the search will be undermined if there are crossing boundaries. In such a case there will be more than two boundary directed edges at the vertex and there is no unique external angle.

Establishing the no crossing boundaries property ensures these failures cannot occur. We can easily check this property for newly created Tgraphs (with checkedTgraph) and the face adding operations cannot create crossing boundaries.

Touching Vertices and Crossing Boundaries

When a new face to be added on (a,b) has neither of the other two edges already in the Tgraph, the third vertex needs to be created. However it could already exist in the Tgraph – it is not on an edge coming from a or b but from another non-local part of the Tgraph. We call this a touching vertex. If we simply added a new vertex without checking for a clash this would create a non-sensible Tgraph. However, if we do check and find an existing vertex, we still cannot add the face using this because it would create a crossing boundary.

Our version of forcing prevents face additions that would create a touching vertex/crossing boundary by calculating the positions of boundary vertices.

No conflicting edges

There is a final (simple) check when adding a new face, to prevent a long edge (phiEdge) sharing with a short edge. This can arise if we force an incorrect Tgraph (as we will see later).

Implementing Forcing

Our order of forcing prioritises updates (face additions) which do not introduce a new vertex. Such safe updates are easy to recognise and they do not require a touching vertex check. Surprisingly, this pretty much removes the problem of touching vertices altogether.

As an illustration, consider foolDMinus again on the left of figure 11. Adding the left dart onto edge (12,14) is not a safe addition (and would create a crossing boundary at 6). However, adding the right dart RD(6,14,11) is safe and creates the new edge (6,14) which then makes the left dart addition safe. In fact it takes some contrivance to come up with a Tgraph with an update that could fail the check during forcing when safe cases are always done first. Figure 17 shows such a contrived Tgraph formed by removing the faces shown in green from a twice decomposed sun on the left. The forced result is shown on the right. When there are no safe cases, we need to try an unsafe one. The four green faces at the bottom are blocked by the touching vertex check. This leaves any one of 9 half-kites at the centre which would pass the check. But after just one of these is added, the check is not needed again. There is always a safe addition to be done at each step until all the green faces are added.

Boundary information

The implementation of forcing has been made more efficient by calculating some boundary information in advance. This boundary information uses a type BoundaryState

data BoundaryState
  = BoundaryState
    { boundary    :: [Dedge]
    , bvFacesMap  :: Mapping Vertex [TileFace]
    , bvLocMap    :: Mapping Vertex (Point V2 Double)
    , allFaces    :: [TileFace]
    , allVertices :: [Vertex]
    , nextVertex  :: Vertex
    } deriving (Show)

This records the boundary directed edges (boundary) plus a mapping of the boundary vertices to their incident faces (bvFacesMap) plus a mapping of the boundary vertices to their positions (bvLocMap). It also keeps track of all the faces and vertices. The boundary information is easily incremented for each face addition without being recalculated from scratch, and a final Tgraph with all the new faces is easily recovered from the boundary information when there are no more updates.

makeBoundaryState  :: Tgraph -> BoundaryState
recoverGraph  :: BoundaryState -> Tgraph

The saving that comes from using boundary information lies in efficient incremental changes to the boundary information and, of course, in avoiding the need to consider internal faces. As a further optimisation we keep track of updates in a mapping from boundary directed edges to updates, and supply a list of affected edges after an update so the update calculator (update generator) need only revise these. The boundary and mapping are combined in a ForceState.

type UpdateMap = Mapping Dedge Update
type UpdateGenerator = BoundaryState -> [Dedge] -> UpdateMap
data ForceState = ForceState 
       { boundaryState:: BoundaryState
       , updateMap:: UpdateMap 
       }

Forcing then involves using a specific update generator (allUGenerator) and initialising the state, then using the recursive forceAll which keeps doing updates until there are no more, before recovering the final Tgraph.

force:: Tgraph -> Tgraph
force = forceWith allUGenerator

forceWith:: UpdateGenerator -> Tgraph -> Tgraph
forceWith uGen = recoverGraph . boundaryState . 
                 forceAll uGen . initForceState uGen

forceAll :: UpdateGenerator -> ForceState -> ForceState
initForceState :: UpdateGenerator -> Tgraph -> ForceState

In addition to force we can easily define

wholeTiles:: Tgraph -> Tgraph
wholeTiles = forceWith wholeTileUpdates 

which just uses the first forcing rule to make sure every half-tile has a matching other half.

We also have a version of force which counts to a specific number of face additions.

stepForce :: Int -> ForceState -> ForceState

This proved essential in uncovering problems of accumulated inaccuracy in calculating boundary positions (now fixed).

Some Other Experiments

Below we describe results of some experiments using the tools introduced above. Specifically: emplacements, sub-Tgraphs, incorrect tilings, and composition choices.

Emplacements

The finite number of rules used in forcing are based on local boundary vertex and edge information only. We thought we may be able to improve on this by considering a composition and forcing at the next level up before decomposing and forcing again. This thus considers slightly broader local information. In fact we can iterate this process to all the higher levels of composition. Some Tgraphs produce an empty Tgraph when composed so we can regard those as maximal compositions. For example compose fool produces an empty Tgraph.

The idea was to take an arbitrary Tgraph and apply (compose . force) repeatedly to find its maximally composed (non-empty) Tgraph, before applying (force . decompose) repeatedly back down to the starting level (so the same number of decompositions as compositions).

We called the function emplace, and called the result the emplacement of the starting Tgraph as it shows a region of influence around the starting Tgraph.

With earlier versions of forcing when we had fewer rules, emplace g often extended force g for a Tgraph g. This allowed the identification of some new rules. However, since adding the new rules we have not found Tgraphs where the result of force had fewer faces than the result of emplace.

[As an important update, we have now found examples where the result of force strictly includes the result of emplace (modulo vertex renumbering).

Sub-Tgraphs

In figure 18 on the left we have a four times decomposed dart dartD4 followed by two sub-Tgraphs brokenDart and badlyBrokenDart which are constructed by removing faces from dartD4 (but retaining the connectedness condition and the no crossing boundaries condition). These all produce the same forced result (depicted middle row left in figure 15).

However, if we do compositions without forcing first we find badlyBrokenDart fails because it produces a graph with crossing boundaries after 3 compositions. So compose on its own is not always safe, where safe means guaranteed to produce a valid Tgraph from a valid correct Tgraph.

In other experiments we tried force on Tgraphs with holes and on incomplete boundaries around a potential hole. For example, we have taken the boundary faces of a forced, 5 times decomposed dart, then removed a few more faces to make a gap (which is still a valid Tgraph). This is shown at the top in figure 19. The result of forcing reconstructs the complete original forced graph. The bottom figure shows an intermediate stage after 2200 face additions. The gap cannot be closed off to make a hole as this would create a crossing boundary, but the channel does get filled and eventually closes the gap without creating a hole.

Incorrect Tilings

When we say a Tgraph g is correct (respectively: incorrect), we mean g represents a correct tiling (respectively: incorrect tiling). A simple example of an incorrect Tgraph is a kite with a dart on each side (referred to as a mistake by Penrose) shown on the left of figure 20.

*Main> mistake
Tgraph { maxV = 8
       , faces = [RK (1,2,4),LK (1,3,2),RD (3,1,5)
                 ,LD (4,6,1),LD (3,5,7),RD (4,8,6)
                 ]
       }

If we try to force (or emplace) this Tgraph it produces an error in construction which is detected by the test for conflicting edge types (a phiEdge sharing with a non-phiEdge).

*Main> force mistake
... *** Exception: doUpdate:(incorrect tiling)
Conflicting new face RK (11,1,6)
with neighbouring faces
[RK (9,1,11),LK (9,5,1),RK (1,2,4),LK (1,3,2),RD (3,1,5),LD (4,6,1),RD (4,8,6)]
in boundary
BoundaryState ...

In figure 20 on the right, we see that after successfully constructing the two whole kites on the top dart short edges, there is an attempt to add an RK on edge (1,6). The process finds an existing edge (1,11) in the correct direction for one of the new edges so tries to add the erroneous RK (11,1,6) which fails a noConflicts test.

So it is certainly true that incorrect Tgraphs may fail on forcing, but forcing cannot create an incorrect Tgraph from a correct Tgraph.

If we apply decompose to mistake it produces another incorrect Tgraph (which is similarly detected if we apply force), but will nevertheless still compose back to mistake if we do not try to force.

Interestingly, though, the incorrectness of a Tgraph is not always preserved by decompose. If we start with mistake1 which is mistake with just two of the half darts (and also incorrect) we still get a similar failure on forcing, but decompose mistake1 is no longer incorrect. If we apply compose to the result or force then compose the mistake is thrown away to leave just a kite (see figure 21). This is an example where compose is not a left inverse to either decompose or (force . decompose).

Composing with Choices

We know that unknowns indicate possible choices (although some choices may lead to incorrect Tgraphs). As an experiment we introduce

makeChoices :: Tgraph -> [Tgraph]

which produces alternatives for the 2 choices of each of unknowns (prior to composing). This uses forceLDB which forces an unknown to be a largeDartBase by adding an appropriate joined half dart at the node, and forceLKC which forces an unknown to be a largeKiteCentre by adding a half dart and a whole kite at the node (making up the 3 pieces for a larger half kite).

Figure 22 illustrates the four choices for composing fool this way. The top row has the four choices of makeChoices fool (with the fool shown embeded in red in each case). The bottom row shows the result of applying compose to each choice.

In this case, all four compositions are correct tilings. The problem is that, in general, some of the choices may lead to incorrect tilings. More specifically, a choice of one unknown can determine what other unknowns have to become with constraints such as

• a and b have to be opposite choices
• a and b have to be the same choice
• a and b cannot both be largeKiteCentres
• a and b cannot both be largeDartBases

This analysis of constraints on unknowns is not trivial. The potential exponential results from choices suggests we should compose and force as much as possible and only consider unknowns of a maximal Tgraph.

For calculating the emplacement of a Tgraph, we first find the forced maximal Tgraph before decomposing. We could also consider using makeChoices at this top step when there are unknowns, i.e a version of emplace which produces these alternative results (emplaceChoices)

The result of emplaceChoices is illustrated for foolD in figure 23. The first force and composition is unique producing the fool level at which point we get 4 alternatives each of which compose further as previously illustrated in figure 22. Each of these are forced, then decomposed and forced, decomposed and forced again back down to the starting level. In figure 23 foolD is overlaid on the 4 alternative results. What they have in common is (as you might expect) emplace foolD which equals force foolD and is the graph shown on the right of figure 11.

Future Work

I am collaborating with Stephen Huggett who suggested the use of graphs for exploring properties of the tilings. We now have some tools to experiment with but we would also like to complete some formalisation and proofs.

It would also be good to establish whether it is true that g is incorrect iff force g fails.

We have other conjectures relating to subgraph ordering of Tgraphs and Galois connections to explore.

by readerunner at July 30, 2023 05:01 PM