eighty-twenty

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.

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?

Recently I've been using Announcements, a framework for a particular style of event pub/sub within a Smalltalk image. Squeak Smalltalk has a handful of different implementations of the same pub/sub pattern in the default image, and Announcements is a nicely designed generalisation of these.

But why would one want to have a particular implementation of such a common design pattern as pub/sub baked in to the image?

One way of thinking about it, that I'm becoming more and more convinced by, is this:

• If Objects are abstract representations of computers, then
• Announcers are abstract representations of networks.

The communication channel between two objects is normally a regular message send. Regular message sends provide Plain Old RPC (with Exceptions). Sometimes, however, you want one or more of the following things to happen:

• a message to be delivered to more than one recipient
• a message to be delivered to an arbitrary or unknown number of recipients
• a message to be delivered asynchronously, or without reply
• a message to be delivered across a real network to some remote object

Combinations of the above are useful and interesting too.

It's in situations like these that having a first-class representation of the medium of communication between objects becomes important. And that's just what Announcers are in the Announcement framework.

One of the too-many things I'm thinking about at the moment is how to generalise Announcers to take into consideration more than just the first two of the four points listed above. Designing and implementing the basic facility seems straightforward, but one runs fairly quickly into issues of concurrency and fault-tolerance.

Today I stumbled across "Guidelines for Choosing A Computer Language: Support For The Visionary Organization" by Patricia K. Lawlis, written back in 1997.

Appendix Q deals with Smalltalk. Here are the categories in which Smalltalk scores well:

• Clarity of source code - Rating: 9
• Complexity management (architecture support) - Rating: 6
• Maintainability - Rating: 7
• Object-oriented programming support - Rating: 10
• Reusability - Rating: 8
• Support for modern engineering methods ¹ - Rating: 7

Here are the categories in which Smalltalk scores poorly:

• Concurrency support - Rating: 2
• Distributed system support - Rating: 0
• Mixed language support - Rating: 3
• Portability - Rating: 3
• Real-time support - Rating: 0
• Reliability - Rating: 3
• Safety - Rating: 0
• Standardization - Rating: 3

Those low scores are ripe for correction!

People often speak of Smalltalk as if it were just another programming language. It is that, of course: Smalltalk the language is pure-object-oriented, class-based, memory safe, reflective, and dynamically typed. However the same name, Smalltalk, also denotes a complete operating system in a virtual machine on top of a traditional OS. Smalltalk's operating-system nature is to blame for its poor performance in the categories shown above.

The (implied) criticisms of the low scores above are absolutely spot on:

• Smalltalk's support for concurrency (isolation of processes; management of processes; isolating failures; transactional behaviour; etc.) is very low-level and old fashioned. Exactly what one would expect from an operating system designed in the early 80s.

• Its support for distributed programming is also not great. (I have a hypothesis about why that is, that I'm researching at the moment.)

• No isolation between processes makes mixed language support difficult.

• Reliability and safety are nonexistent in an environment with no isolation boundaries.

• Smalltalk is a heavily imperative language. Data structures are mutated internally all over the place, giving a straightforward shared-memory concurrency model.

So what can be done? Let's look at another Application Operating System², this one designed with fault-tolerance in mind: Erlang/OTP.

• Erlang's support for concurrency is very strong. Processes are, by default, isolated from one another, in that they share no mutable state, and a failure in one process cannot affect another process in an unstructured way.

• Its support for distributed programming is also very strong. Processes communicate by shared-nothing message passing. Scaling from a non-distributed system to a distributed system starts with the simple substitution of a TCP socket for an in-memory message queue.

• Isolation between processes makes the decision of which language to use to handle received messages within a process an essentially arbitrary one, though in practice Erlang doesn't support anything other than its built-in functional fragment.

• Reliability and safety follow from the strong isolation boundaries between system components and from the structuring principles embodied in the OTP libraries.

• Erlang is a heavily functional language. Data structures are immutable, giving a straightforward shared-nothing message passing concurrency model.

Erlang has its problems, of course: it doesn't support object-oriented programming other than either awkwardly (processes look a bit like objects) or in a trivial sense (function closures and objects are the same thing). As a result, generic programming (e.g. ignoring whether you have a list of numbers or an array of numbers) is poorly supported, syntactically unpleasant, and/or slow. It also enjoys none of the rich reflective support provided by the Smalltalk virtual machine, which makes the monitoring tools feel ad-hoc and not very general.

My instinct is that a system that supported a combination of Smalltalk's smooth generic and reflective programming styles and Erlang's ability to construct robust, concurrent and distributed systems, would make a great foundation for personal computing.

What can be done to Smalltalk's operating-system nature to improve isolation of components within a running system? Mutability is a key concern, as is failure isolation. Can Smalltalk be refactored into a hybrid Smalltalk-Erlang system?

Travis Griggs relates a story of being burned by the use of lazy initialization in Smalltalk. It's an interesting problem, and I sympathise. The way I see it is that the underlying cause is too much reliance on mutable state, and/or not enough declarative specification of intent. This is a general problem in languages like Smalltalk and Java, nothing specific to particular pieces of code anyone writes, of course!

Some other languages and systems supporting lazy initialization (memoization) avoid the problem by detecting circular dependencies. As each initial-value-computing thunk is entered, a bit is set if it isn't already, or an exception is raised if the bit is already set. Any kind of non-cyclic dependency graph ends up computing its result as expected, and cycles are detected and signalled.

The trick is to declaratively let the system know what your intent is.

What would be a good Smalltalk-like way of letting the system know you mean to build a lazy initializer? A few options spring to mind:

• one could use a pragma on methods acting the part of lazily-initializing getters;

• one could mark the initializing closure specially somehow (foo ifNil: [...] lazyInitializer), where the effect of #lazyInitializer is to set up the circularity checks (initial experiments along these lines stalled when I realised I didn't have enough understanding of the way BlockClosures work in Squeak);

• one could set foo initially to some object representing a Promised value, which internally has support for the necessary circularity-checks;

and no doubt many other variations.

(Incidentally, I just tried Haskell, to see what it did with

let a = b + 1; b = a - 2 in a

and unfortunately it suffers from the same infinite recursion problem Travis's code was suffering from: neither a value nor an error is produced.)

Submatching in a pattern, +var@pattern, looks suspiciously similar to recursion in a value, var=value. In each case, we expect a value which is both named and processed, and in each case, a binding is introduced into code. The processing in the submatch case is a further pattern-match operation, and in the recursion case it is a nested evaluation.

The main difference, besides the overall context, between the two forms is the scope of the introduced binding: in the submatch, the pattern variable to the left of the @ sign is bound only in the right-hand-side of the overall pattern, at present, whereas in the recursive value the variable to the left of the = is bound in the right-hand-side of the recursion itself. Another important difference is that in the submatch context, the +var is clearly just a binding form, whereas in the recursion context, var can be seen as acting both as a binding form and a reference to the bound value. Another way of looking at it, though, has the var acting solely as a binding form, with the right-hand-side of the = being the actual result of the expression — the fact that the left and right-hand-sides are equivalent is not relevant, in this interpretation.

What if the two forms were unified, based on their similarities, using either var=pattern-or-value or +var=pattern-or-value for both pieces of syntax? The former seems out-of-place for submatches, since we want to clearly mark bindings that will propagate their bound value into the code on the right-hand-side of an object clause; and the latter seems out-of-place in a recursive value, since +var implies a binding object, which is a first-class datum in ThiNG.

Compare and contrast the following — a string-interleaving routine using the current syntax for both submatch and recursion:

sepList: [+s: loop=[(cons +x +more@(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

The same routine using +var=pattern-or-value for both:

sepList: [+s: +loop=[(cons +x +more=(cons _ _)): (x ++ s ++ loop more)
                     (cons +x _): x
                     _: EmptyString]]

Finally, the same routine using var=pattern-or-value for both:

sepList: [+s: loop=[(cons +x more=(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

Finally, there's the question of scope: if the same syntax is used for both submatch and for recursion, what happens if we adjust the scoping rules to be as similar as possible? It doesn't make sense for recursive-value's scoping rule to be changed to be the same as submatch's scoping rule — there's no right-hand-side in a value for the binding to be visible in! — but the other way around might be worth considering: let the binding introduced as part of a submatch be visible as part of the right-hand-side of the submatch. What happens then? Do we end up with infinite patterns? Do we instead end up with a kind of unification-constraint in which an object matching a submatch that is referred to within that same submatch is constrained to have the same recursive topology as the pattern itself?

[Update: Something I forgot to mention — with the scope rule for submatches as it stands, it's possible to evaluate and then compile patterns ahead of execution time. Changing the scope rule can make compilation of ThiNG code more difficult, forcing the system to be more late-bound than perhaps it needs to be.]

The other day, I noted that my generic-monad-in-Scheme implementation suffered from the flaw of not being able to type-check monad assemblies before any actions had been executed, and that in general such ahead-of-time checking is not possible without abstract interpretation of some kind, because the functional code in the right-hand-side of the bind operator can decide which action to splice into the monad next:

(define (goes-wrong)
  (run-io (mlet* ((val mread))
            (if val ;; if the user entered #f, we break, otherwise we're fine
                (mlet* ((_ (mdisplay "Was true\n"))) (return 'apples))
                'bananas)))) ;; Note: missing "(return ...)"!

Perhaps a partial-evaluator can play the part of a Haskell-type-system-like abstract interpretation well enough to drive the type-safety checks through the code at PE time (loosely equivalent to static-analysis time) for most cases (leaving the remaining cases for runtime-detection, as in the present implementation, and perhaps warning the user)? In order to find out, my next experiment in this direction will be marrying the monad code to the partial-evaluator I implemented some months ago.

I don't know what crack I was smoking the other day, but my implementation of general monads not only does not have the property I claimed for it, viz. that it provides the same level of type-checking as Haskell ahead of execution-time, but it cannot provide such a level of ahead-of-runtime checking, whether the hosting language is eager or lazy.

To see the first, try the following example:

> (run-io (mlet* ((_ (mdisplay "HERE\n"))
                  (_ sget))
            (return 232)))
HERE
wrong monad-class ((mclass #5(struct:<monad-class> io [...]))
      (m #3(struct:<monad> #5(struct:<monad-class> state [...]) [...]))) 

Note how an action is performed before the type error is detected. In general, it is not possible to detect the type-error ahead of time without abstract interpretation of the level of sophistication that Haskell's type-checker provides, as the following example demonstrates:

> (define (goes-wrong)
    (run-io (mlet* ((val mread))
              (if val
                  (mlet* ((_ (mdisplay "Was true\n"))) (return 'apples))
                  'bananas)))) ;; Note: missing "(return ...)"!
> (goes-wrong)
#t
Was true
apples
> (goes-wrong)
#f
<monad>-ref: expects type <struct:<monad>> as 1st argument, given: bananas; other arguments were: 0
[...]

The problem is that the system can decide how to continue based on I/O performed at runtime, and so the composition performed by bind cannot be checked until after the left-hand-side has been fully evaluated. [Aside: the <monad>-ref error was a symptom of the unexpected problem described below — now that the code has been fixed, it instead complains "not a monad bananas", as it should.]

This affects all my monad implementations, not just the IO monad:

> (run-st (mlet* ((a sget)
                  (b (mdisplay "OH NO\n"))
                  (_ (sput 4)))
            (return (+ a 1)))
          2)
OH NO
(3 . 4)

Actually, and this is unexpected ("OH NO" indeed!), here it's even worse than just not catching the type-error before any actions have executed: it isn't catching the error at all. Here's what that mlet* expands into:

(>>= sget
     (lambda (a)
       (>>= (mdisplay "OH NO\n")
            (lambda (b)
              (>>= (sput 4)
                   (lambda (_)
                     (return (+ a 1))))))))

My implementation of >>= isn't "reaching into the lambda" in the case of the IO monad. [Interlude; sounds of programming from behind the curtain.] The problem was my use of the (bad) "delayed monad" idea in implementing the IO monad — I've just replaced that idea with a more explicit representation of a delayed action, and the code now behaves as I expected. How embarrassing! Here's the trace now that I've fixed that problem:

> (mlet* ((a sget)
          (b (mdisplay "OH NO\n"))
          (_ (sput 4)))
    (return (+ a 1)))
#3(struct:<monad> #5(struct:<monad-class> state [...]) [...])

This shows that before we run the monad, it appears to be a well-behaved state monad instance. Running it now causes the error to be detected:

> (run-st (mlet* ((a sget)
                  (b (mdisplay "OH NO\n"))
                  (_ (sput 4)))
            (return (+ a 1)))
          2)
wrong monad-class ((mclass #5(struct:<monad-class> state [...]))
      (m #3(struct:<monad> #5(struct:<monad-class> io [...]) [...]))) 

This demonstrates what I was hoping to show above, before I was derailed by the delayed-monad issue: that the impossibility of using this technique to type-check monad assemblies ahead of any actions being performed applies to all monad kinds, not just the IO monad. Of course, it's less of a problem for non-side-effecting monads, such as the state monad, since performing an action (in the case immediately above, reading the hidden state variable) in such a monad has no effect on the outside world by the time the type-error is detected.

In conclusion, I was mistaken about Scheme's ability to achieve the same level of ahead-of-execution type-checking as Haskell manages — I don't believe it to be possible without essentially Haskell-equivalent abstract-interpretation machinery bolted on to the language. Nonetheless, the library I've developed does catch type errors eventually — so long as the faulty code is eventually run! This is no worse than regular dynamically-typed language code, and is still a useful system, so I'm not completely disappointed. I will still be able to use the idea to structure side-effects in ThiNG.

Just quickly revisiting the article the other day on monads in Scheme: I've just updated my experimental implementation to propagate monad type information both forward from the arguments to the result of the bind operation and backward from the expected result type to the required argument types of the bind. Now Oleg's example (see near the bottom of the page, where there's an expression (put-line "Enter a number: ")) can be translated into the following working code:

(define oleg-example-mixed-monad
  (mlet* ((_ (mdisplay "Enter a number: "))
          (n mread)
          (all-n (return (iota n)))
          (evens (return (run-list (mlet* ((i all-n))
                                     (if (even? i)
                                         (return i)
                                         (fail "odd"))))))
          (_ (mdisplay "Computed "))
          (_ (mdisplay (length evens)))
          (_ (mdisplay " evens\n")))
    (return evens)))

When run with (run-io oleg-example-mixed-monad), it produces sessions like the following (user input in italics):

Enter a number: 33
Computed 17 evens
(0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32)

The system could be sweetened up with a bit of generic-function or other OO sugar, but I'd say even without extra sugar that this experiment has been successful in demonstrating the feasibility of the technique. It looks like I'll be able to use the idea for structuring effects in ThiNG.