eighty-twenty

In the last few weeks, a bit of discussion of John Shutt’s Fexpr-based programming language, Kernel, has sprung up in various circles. I read Shutt’s PhD thesis, implemented a couple of toy Kernel-inspired interpreters (in Javascript and Racket), and became simultaneously excited about the simplicity, hygiene and power of the approach and apprehensive about the strong possibility that there was something fundamental I was overlooking. After all, the theory of Fexprs is trivial.

Calling Kernel’s Fexprs “trivial” doesn’t seem quite right to me; perhaps calling them “inscrutable” would be a better fit.

Three serious problems with Kernel and $vau

After a discussion with a friend earlier this week, I think it’s important to note three serious problems with Kernel and the underlying $vau calculi Shutt proposes:

1. It’s not possible even to compute the free variables of a term in $vau-calculus in general.¹ This makes compilation, automatic refactoring, and cross-referencing impossible in general.

2. There are too many contexts that tell terms apart; contextual equivalence is too fine. Consider these two terms:

    ($lambda (f) (f (+ 3 4)))
    ($lambda (f) (f (+ 4 3)))
   

   These two terms are not contextually equivalent, because if you pass an operative² as the argument to the function, the operative can inspect the syntactic structure of the program.

3. This over-fine contextual equivalence is a problem in practice, not just a theoretical concern. Consider this following definition of a foldr function:

    ($define! foldr
      ($lambda (c n xs)
        ($if (null? xs)
             n
             (c (car xs) (foldr c n (cdr xs))))))
   

   See how c has control over whether and when the recursive case is evaluated, because it is not required to evaluate its arguments! Compare this to the same definition where the last line is replaced with

    ($let ((ys (foldr c n (cdr xs)))) (c (car xs) ys))
   

   By introducing the intermediate $let, we take control over the recursion away from c, forcing evaluation of the recursive case.

   To show concretely why this is a problem, the call (foldr $and #t some-list) will either be a short-circuiting “and” or not, depending on an implementation detail of the foldr function!

Taken together, we see that purely local reasoning about Kernel programs is impossible; or at least, getting useful results from such reasoning is impossible in general. Only whole-program analysis can give us enough stability to let us reach useful conclusions about our programs.

On the other hand, it’s possible to mitigate these problems somewhat.

First of all, it might be possible to use online partial evaluation to compute the various static properties of terms we’re used to from the lambda-calculus in many (but certainly not all) situations. Undecidable situations might be able to be warned about. This might make the language stable enough to work in practice.

Secondly, by shifting one’s perspective, the inequivalence of the two variants of foldr given above might be able to be seen as a feature: applicatives, after all, are not operatives in Kernel. Personally, I find it unsettling, but that could be my Scheme heritage showing. Documentation for Kernel applicatives would need to specify what possible computations any higher-order parameters might receive as arguments. The foldr given above can be simultaneously CPS and non-CPS, when given operative and applicative arguments, respectively.

Both these possible mitigations are speculative and weak.

Reasons to be cheerful

I think that the core idea of separating argument evaluation from argument transmission (or function call; I’m unsure what to call it) is a very powerful one. Consider a distributed system: evaluation of arguments has to happen on the sending side, and transmission of the results of evaluation to the receiving side (where instantiation of the function body happens) is a separate operation.

I also think the simplicity of implementation of a Kernel-style Fexpr based system is worth paying attention to, especially given that it makes writing hygienic “macros” effortless, and in the process handily avoids the thorny problem of exactly what “hygiene” is in the first place. Achieving such ease-of-use takes heavy-duty macrology in languages like Scheme that lack first-class macros or Fexprs.

Having our cake and eating it, while also enjoying improved security

Consider securing Kernel in the same way that a capability-based approach can secure Scheme. To secure Kernel as it stands, each applicative has to guard against possibly receiving some operative as an argument.

To make it easier to secure, we might make the system signal an error when an attempt is made to pass an operative as an argument to an applicative.

This makes Fexprs/operatives/”macros” second-class, just as they are in Scheme. I conjecture that doing so has the following effects:

1. it makes contextual equivalence useful again, making the two variants of foldr given above indistinguishable³, but

2. it simultaneously makes the system exactly equivalent in power to Scheme with, say, a syntax-case macro system.

So by doing this, we’ve given up most of Kernel’s approach, seemingly in exchange for, well, familiar old Scheme. We haven’t lost everything, though: we’ve retained the simplicity and power of Kernel’s approach to hygiene.

Conclusions

Without quite a bit of further research, I don’t think Kernel-style languages can be used to build secure or efficiently compiled systems. Making changes necessary to build a secure variant of Kernel may destroy many of the properties that make the language interesting in the first place, but doing so might leave us in a familiar setting seen through new eyes: Scheme.

Recently I wanted to dust off some old code I’d written for GNU Smalltalk, and found that Homebrew’s formula for it didn’t build cleanly in 64-bit mode, and wouldn’t include LibSDL or Cairo support in 32-bit mode. So I rolled up my sleeves and checked out the git repository. UPDATE: I’ve updated the Homebrew formula in my fork of Homebrew; see below.

It turned out to be straightforward, after I made a few false starts. Here’s how I got it built and working, including SDL and Cairo support.

Prerequisites

GNU Smalltalk, when built from Git, depends on libffi and libsigsegv. Fortunately, Homebrew’s formulas for these work well:

$ brew install libffi
$ brew install libsigsegv

GNU Smalltalk itself

Check the code out from Git:

$ git clone https://github.com/bonzini/smalltalk.git smalltalk
$ cd smalltalk

If you’re on Snow Leopard, you’ll have autoconf version 2.61 and automake version 1.10. The GNU Smalltalk source code requests newer versions of these tools, but will build just fine with the versions shipped with Snow Leopard’s XCode. Edit configure.ac so that it has the line AC_PREREQ(2.61) instead of AC_PREREQ(2.63), and edit Makefile.am so that it has the line AUTOMAKE_OPTIONS = gnu 1.10.

(These changes are summarised in this patch.)

Once configure.ac and Makefile.am have been edited, carry on as you usually would for an autotools project:

$ autoreconf -fvi
$ ./configure --prefix=/opt/gnu-smalltalk PKG_CONFIG_PATH=/usr/local/Cellar/libffi/3.0.9/lib/pkgconfig
$ make
$ make install

The PKG_CONFIG_PATH variable definition on the ./configure line is necessary to let GNU Smalltalk’s configuration script find libffi, which is a keg-only Homebrew formula for Snow Leopard.

Updated Homebrew

2 Oct: I’ve just updated the Homebrew gnu-smalltalk formula to follow the steps above. It now builds from git HEAD rather than from a numbered release. My changes haven’t been accepted into the main branch of Homebrew yet, but for now you can see my formula here.

The system browser in Cuis, a dialect of Squeak Smalltalk, looks like this:

Notice that there is no UI for creating new methods!

There’s a strange and subtle shift in UI design thinking in effect here. Instead of the purpose of the code pane being to “edit some little snippet of code already associated with the current class”, thereby necessitating UI for creating new methods, its purpose is to “interpret any submitted piece of code in the context of the current class”, thereby permitting both definition of new methods and updates to existing methods.

Whenever you type new text into the code pane and accept the changes (by pressing M-s), it compiles whatever text is present as if it were a method definition in the selected class. If that happens to be a new variation on saveTo:, so be it; if it’s an entirely new method, no problem, a new method is compiled and inserted into the class’s method dictionary.

The code pane is really a procedure, accepting arbitrary method source code and having the side effect of compiling that code in the context of the currently-selected class.

The system browser has been this way in Smalltalk since 1980. It’s eye-opening to contrast it with the rigidly file-oriented editors present in IDEs from other systems, from Emacs and Vi up through IntelliJ IDEA and Eclipse.

John Shutt’s PhD thesis introduces the Kernel programming language. Kernel includes an $if, which is treated as a built-in primitive.

It doesn’t have to be primitive, though: in Kernel a construct that does the same thing as the primitive $if operation (in well-typed programs) can be constructed.

In Scheme, one needs to make use of the macro facility to construct an if if there’s not one built-in:

(define true (lambda (first second) first))
(define false (lambda (first second) second))
(define-syntax if
  (syntax-rules ()
    ((_ test if-true if-false)
     ((test (lambda () if-true) (lambda () if-false))))))

In Kernel, we use fexprs instead:

($define! true ($lambda (first second) first))
($define! false ($lambda (first second) second))
($define! $if
  ($vau (test if-true if-false) env
    (eval ((eval test env) if-true if-false) env)))

Here we can see the central opposition between Scheme and Kernel: Scheme’s evaluation of forms is implicit, and we use lambda to postpone evaluation; Kernel’s evaluation of forms is explicit, and we use eval to cause evaluation.

Expressions used as tests absolutely must evaluate to true or false, and nothing else, for these definitions to work. One of the benefits of treating $if as primitive is that one can provide for a separation between Booleans and the rest of the universe that’s not possible otherwise. It’s nice to know, though, that $if can be dispensed with if necessary.

Yesterday, while experimenting with Diffie-Hellman key exchange as done by the SSH protocol, I discovered (after quite a bit of confusion) that the 1024-bit and 2048-bit parameter groups included with OpenSSL’s Diffie-Hellman implementation are not the same as the 1024-bit “group 2” from RFC 2409 and the 2048-bit “group 14” from RFC 3526! They’re completely unrelated.

Once I discovered this, I spent some time figuring out how to construct PEM files containing the right values formatted appropriately for use with OpenSSL.

If you need to use the “Second Oakley Group” (1024-bit MODP group) from RFC 2409 with OpenSSL, you should load the following parameter file, oakley-group-2.pem, using OpenSSL’s PEM_read_DHparams function:

-----BEGIN DH PARAMETERS-----
MIGHAoGBAP//////////yQ/aoiFowjTExmKLgNwc0SkCTgiKZ8x0Agu+pjsTmyJRSgh5jjQE
3e+VGbPNOkMbMCsKbfJfFDdP4TVtbVHCReSFtXZiXn7G9ExC6aY37WsL/1y29Aa37e44a/ta
iZ+lrp8kEXxLH+ZJKGZR7OZTgf//////////AgEC
-----END DH PARAMETERS-----

If you need to use the 2048-bit MODP group from RFC 3526 with OpenSSL, load the following parameter file, oakley-group-14.pem:

-----BEGIN DH PARAMETERS-----
MIIBCAKCAQEA///////////JD9qiIWjCNMTGYouA3BzRKQJOCIpnzHQCC76mOxObIlFKCHmO
NATd75UZs806QxswKwpt8l8UN0/hNW1tUcJF5IW1dmJefsb0TELppjftawv/XLb0Brft7jhr
+1qJn6WunyQRfEsf5kkoZlHs5Fs9wgB8uKFjvwWY2kg2HFXTmmkWP6j9JM9fg2VdI9yjrZYc
YvNWIIVSu57VKQdwlpZtZww1Tkq8mATxdGwIyhghfDKQXkYuNs474553LBgOhgObJ4Oi7Aei
j7XFXfBvTFLJ3ivL9pVYFxg5lUl86pVq5RXSJhiY+gUQFXKOWoqsqmj//////////wIBAg==
-----END DH PARAMETERS-----

Running the files through openssl asn1parse shows that the contents are the same as the numbers given in the RFCs:

$ openssl asn1parse < oakley-group-2.pem 
0:d=0  hl=3 l= 135 cons: SEQUENCE          
3:d=1  hl=3 l= 129 prim: INTEGER           :FFFFFFFFFFFFFFFFC90FDAA22168C234
C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B
302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF
  135:d=1  hl=2 l=   1 prim: INTEGER           :02

$ openssl asn1parse < oakley-group-14.pem 
0:d=0  hl=4 l= 264 cons: SEQUENCE          
--------------------------------------------------------------------------------
4:d=1  hl=4 l= 257 prim: INTEGER           :FFFFFFFFFFFFFFFFC90FDAA22168C234
C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B
302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED
EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A
69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804
F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9
DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
  265:d=1  hl=2 l=   1 prim: INTEGER           :02

The AMQP 1.0.0 draft of 2011-07-04 contains the following language defining the meaning of its 64-bit “timestamp” data type:

Encodes a point in time using a 64 bit signed integer representing milliseconds since Midnight Jan 1, 1970 UTC. For the purpose of this representation, milliseconds are taken to be (1/(24*60*60*1000))th of a day.

This language is broken.¹

The first sentence there makes it a fixed offset from TAI, which is good. The second sentence there is totally bogus and can have no purpose beyond confusing the crap out of anyone trying to work from this definition. It’d be massively improved by just removing the second sentence:

Encodes a point in time using a 64 bit signed integer representing milliseconds since Midnight Jan 1, 1970 UTC.

For clarity, you might want to add the word “elapsed” and also reconfirm that it’s TAI being discussed here:

Encodes a point in time using a 64 bit signed integer representing elapsed milliseconds since Midnight Jan 1, 1970 UTC. Note that time stamps change in lockstep with TAI, not UTC nor Unix time.

Using a TAI-based metric instead of Unix time (time_t) is good because the Unix time_t definition is a bad design: see this page. Furthermore, UTC, which time_t is an encoding of, cannot be used to talk precisely about moments beyond 6 months in the future, because of the leap-second table that it needs.

TAI-based metrics are almost perfect except that they’re damned awkward to use right on most computer systems out there, because most systems use Unix time. Worse, using TAI but offset so that second zero is the time_t epoch gives a number currently within 30s or so of time_t, which could lead to a lot of confusion.

Choosing a representation of an instant for use in a new protocol is hard. You get a tradeoff between:

• time_t: ambiguous representation and lack of accuracy when referring to moments more than 6mo in the future; on the plus side, wide support and low potential for making mistakes (other than those caused by the inherent flaws in the definition).

• UTC, but not encoded as a count of seconds since some epoch: unambiguous representation, but lack of accuracy with future dates still and also poor library support plus the hassle of defining some new representation.

• TAI offset to be based at the time_t epoch: unambiguous representation, fully accurate, but looks so similar to Unix time that people will probably make mistakes. (Will the mistakes be harmful though? How harmful is being off by 30s? You might ask the Mars Climate Orbiter.)

• Seconds since 2000-01-01T00:00:00Z, in lockstep with TAI: unambiguous representation, fully accurate, looks dissimilar enough that it won’t be mistaken for Unix time, but jolly weird and still needs a leap-second table for display purposes, like any other TAI-based metric.

• Chronological Julian Days in GMT: unambiguous representation, fully accurate, but difficult to convert back and forth to Unix time without a full calendar package.

Additionally, if you ever want to simply subtract one timestamp from another to get some idea of the interval between them, Julian Days and Unix time don’t work; TAI-based metrics are the only ones that give accurate results for this use.

Ideally we want these timestamps to be able to be accurate up to and beyond 50 years in the future or so. If it were me, I’d use TAI either with its own built-in epoch, 1958-01-01T00:00:00Z, or with a suitable easy-to-remember epoch such as 2000-01-01T00:00:00Z.

(Thanks to @ciphergoth, @simonmacm, @squaremobius and @michaeljforster for an informative discussion of this issue.)

Dmitry Chestnykh has collected implementations of the echo command from UNIX V5, OpenBSD, Plan 9, FreeBSD, and GNU coreutils.¹

From this you might conclude that the GNU implementation has excessive bloat. But what’s really going on is (a) feature creep and (b) the inclusion of documentation within the source code of the program itself. UNIX has evolved away from having a command (with no built-in documentation) with a separate manpage toward having not just a detailed separate manpage but also having quick-reference documentation included in the command itself.

The feature creep leads to a perceived need for the quick-reference documentation. The source to the UNIX V5 implementation is its own reference card! There’d be nothing to write in a usage message.

Both the feature-creep and the awkwardly-placed documentation are signs of an ill-factored system. A better factoring would keep commands single-purpose and as simple as possible, with documentation managed consistently across the whole system.

I think UNIX V5 and Smalltalk are much better-factored than modern Unixes. Factoring out common functionality and assembling the pieces using scripting is the way things are done in both cases. Smalltalk has an advantage in that the scripting language is the systems programming language, but the core philosophies of the two systems have a lot in common.

Removing the inline quick-reference documentation from the GNU program lops 60 lines off the total. The remainder of the growth can be attributed to the baked-in extra features (GNU supports multiple command-line syntaxes, where UNIX V5 supports… nothing) and to premature² optimisation (Plan 9 and FreeBSD avoid multiple writes, where UNIX V5 goes for TSTTCPW).

To my mind, either of the UNIX V5 or OpenBSD implementations are perfectly acceptable. The remainder are signs of a sick ecosystem: there’s nothing wrong with them intrinsically, but when they’re seen as part of a larger whole things start to look unhealthy.

I am logged in to IRC, and wish to step away from the keyboard to do the dishes, without missing anything addressed to me. I’d like for the computer to read out loud any messages arriving over IRC that mention my IRC handle.

My personal computing system should permit me to:

1. Gain an interactive representation of my IRC session,
2. extract an object representing the stream of incoming utterances,
3. feed that stream into a new process, within which I
4. filter the stream for mentions of my IRC handle, and
5. pipe utterances mentioning my handle through the say command-line utility.

I’d then be able to leave that running while I did the dishes, terminating it upon returning to the keyboard.

My personal computing system can’t do that right now. Squeak Smalltalk could do it, in theory, but it’s not yet ready for use as my main system for a number of reasons beyond those given in the linked article.

High-speed trading has been growing out of control in recent years—or at least, that’s what it looks like from here. (I don’t know anyone working in that sector of the industry at the moment.) Articles like this, this and this discuss the benefits and problems associated with practices such as co-location.

Assuming, for the moment, that it’s unfair to permit such low-latency decision-making, how could a system be set up to keep bandwidth high, but make latency much less important?

What about saying “these trades will settle at an instant chosen uniformly at random from the next three seconds”? Would that make people unable to keep their latencies ultra-low more able to stay competitive in the market?

Introductory CS courses seldom use Smalltalk as the teaching language, preferring instead Scheme, Python, or Java, even though Smalltalk seems (to me at least) to have strong advantages over these languages. Why isn’t Smalltalk taught?

At least one reason might be that there’s no self-contained syntax: you can’t write down whole programs. In situations like exams and quizzes, where students are asked to longhand program text solutions to problems, Smalltalk doesn’t fit well, requiring a browser as it does.

Source code in files means that your programs aren’t atomised as they are when viewed in a browser. I wonder if GNU Smalltalk’s syntax for file-based Smalltalk programs would make sense in a teaching context?