eighty-twenty

Here are the steps I followed to build Racket from a git checkout on a fresh Windows 7 installation.

• Installed Visual Studio Express 2008 (not 2010 or 2012). This is hard to find on Microsoft's website; this stackoverflow question linked to the Visual Studio Express 2008 ISO directly.

• Used Virtual Clone Drive from SlySoft to mount the ISO in order to install Visual Studio, since Microsoft thoughtfully omitted ISO-mounting functionality from the core operating system.

• Installed MASM32 to get a working assembler, since Microsoft thoughtfully omitted an assembler from their core compiler suite. (I am informed that later and/or non-Express editions of Visual Studio do actually include an assembler.)

• Added the following directories to the system path:

  • C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\bin, for cl.exe etc.
  • C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\IDE, for VCExpress.exe
  • C:\Program Files (x86)\Microsoft Visual Studio 9.0\Common7\Tools, for vsvars32.bat
  • C:\masm32\bin, for ml.exe

  They do have to appear in that order, in particular with the MASM directory last, since it includes a link.exe that will otherwise conflict with the Visual Studio linker.

• Installed Github for Windows and checked out Racket.

• Opened a cmd.exe shell. NOTE not a PowerShell instance. Somehow environment variables are propagated differently in PowerShell from in cmd.exe! You want to only try to use cmd.exe to build Racket with.

• Ran vsvars32.bat in that shell. This step is important, as otherwise the start of the xform stage in the build will fail to find stdio.h.

• Navigated to my Racket checkout within that shell, and from there to src/worksp. Ran build.bat.

Following these steps will in principle lead to a fresh Racket.exe living in the root directory of your Racket checkout. There are many, many things that could go wrong however. Good luck!

Racket and many other languages have the concept of optional arguments at the receiver side:

(define (a-procedure mandatory-arg #:foo [foo 123])
  ;; Use mandatory-arg and foo as normal
  ...)

(a-procedure mandatory-value #:foo 234) ;; override foo
(a-procedure mandatory-value) ;; leave foo alone

Here, the procedure is offering its caller the option of supplying a value for foo, and if the caller does not do so, uses 123 as the value for foo. The caller is permitted not to care (or even to know!) about the #:foo option.

Almost no language that I know of has the symmetric case: an optional argument at the caller side (and because the feature doesn't exist, I'm having to invent syntax to show what I mean):

(define (run-callback callback)
  (callback mandatory-value [#:foo 234]))

(run-callback (lambda (mandatory-arg) ...)) ;; ignores the extra value
(run-callback (lambda (mandatory-arg #:foo [foo 123]) ...)) ;; uses it

The intent here is that the procedure is permitted not to care (or even to know) about the additional value its caller supplies.

This would be useful for callbacks and other situations where the code invoking a procedure has potentially-useful information that the specific (and statically-unknown) procedure being called may or may not care about.

I said above that almost no languages have this feature: it turns out that Squeak and Pharo have something similar in their BlockClosure>>#cull: methods. The following code works when given a closure accepting zero, one or two arguments:

someBlock cull: 1 cull: 2 cull: 3

(Update: @msimoni points out that Common Lisp's allow-other-keys is similar, too. It still requires the callee to declare something extra, though.)

I've just been reading "Type-Safe Modular Hash-Consing" (Filliâtre & Conchon, 2006, http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.pdf) and it got me thinking about the relationship between finding a canonical element of a set via some equivalence and simply deciding the equivalence itself.

In order to hashcons, according to the paper, you need an equivalence predicate T × T → Bool and a hash function T → Int. They have to line up. This lining up seems interesting. The hash function is naming an equivalence class of Ts - or at least it would be if it weren't permitted to spuriously identify things sometimes! So it's a rough equivalence class.

But my main idea is that say we were hashconsing append-lists, defined by

T ::= Nil | T ++ T | [T]

We'd want our equivalence predicate and our hash function to honour t ++ Nil ≡ t. But while it's doing so, there's also the opportunity for it to pick a canonical element: in this case it should choose just t rather than t ++ Nil, since it is structurally smaller.

So perhaps hashconsing should be expressed using a canonicalization function T → T and a hash function T → Int, rather than referring to an equivalence predicate at all?

In some sense a hashcons operator (per the paper taking T → Hashconsed T) is a kind of canonicalizing function, of course, but slightly weird in that it has links to the resource management facility of the underlying VM rather than simply expressing an object-level equivalence.

I wonder what would be a good way of writing a canonicalization function. It feels a lot like a standard reduction, with the notion of reduction being rules like t ++ Nil → t, Nil ++ t → t etc.

So a hashconsing system is a kind of VM-supported normal-form-finding interpreter. For data, rather than programs. Huh.

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.

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.

Hee hee! This paper, on Scheme Program Documentation Tools, references docscm :-)

(Update: Shortly after I posted this, I contacted the working-group chair, and he quickly replied to let me know that the group's settings have been changed. It's now possible to subscribe to group activity as a spectator. Posting is still restricted to group members, of course, but now others can follow along, which makes me happy.)

It's almost impossible to follow the scheme-reports-wg1 Google Group, because

• you can't join the google-group unless you're part of the working group itself (no joining as a spectator)
• the interfaces available to non-google-group members are insufficient:
  • the RSS/Atom feeds truncate posts, meaning you have to click through to the google-group webpage for reading threads
  • the thread-reading pages themselves are not easy to catch up on (compare Thunderbird, an NNTP client, or even Google Reader here)
• the volume of the list is very high at the moment.

I'd be happy if there were

• a full-content RSS/Atom feed somewhere (for some reason I don't trust that the existing feed (or perhaps Google Reader) is doing well in keeping posts in chronological order, either); or,
• an NNTP feed of the group (!); or,
• a regular mailman-style mailing list for the group.

The current setup really doesn't work well for me at all, which is disappointing, as lots of the discussions I've overcome the awkwardness of the interface to read are really very interesting.

I've just finished taking scheme-pg version 0.4.0, which is intended for MzScheme version 299.30, and updating it (1) so that it builds on MacOS X, thanks to Geoffrey Knauth's patches (slightly edited to undo some kind of whitespace mangling probably introduced by the HTML mailing-list archiver); and (2) so that it builds with MzScheme v299.400. The only change to the Scheme code is in sql.ss — MzScheme v299.400 seems to have sprouted versions of string-upcase, string-titlecase, and string-downcase that conflict with SRFI-13's versions of the same procedures.

My revised scheme-pg package is available at http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/. That's both a browseable snapshot, and a darcs repository that you can retrieve with

darcs get http://www.eighty-twenty.org/~tonyg/Darcs/scheme-pg/

This afternoon I implemented a simple partial evaluator for a Scheme-like language, based on the paper "Partial Evaluator as a Compiler for Reflective Languages" (Asai, Masuhara, Matsuoka and Yonezawa, 1995). So far I've restricted myself to an IO-free, side-effect free language, but by using the notion of preactions I ought to easily be able to add support for IO. I'd like to explore extending the simple system I have now to cope with the Composable Memory Transactions of Harris et al instead of supporting Scheme's destructive updates.

The addition of pattern-matching data-destructuring will help the partial evaluator out, too, in the same way it makes dealing with primitive data easier for the Spineless Tagless G-Machine (see section 4.7). For example, using the partial evaluator to specialize the expression

(fold + 0 a)

I currently get

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
                  (GOTO g17
                        (if (pair? x)
                          (PRIMcdr x)
                          (error '"Not a pair in cdr" x))
                        (+ (if (pair? x)
                             (PRIMcar x)
                             (error '"Not a pair in car" x))
                           acc))))))
  (g17 a '0))

(Ignore the strange GOTO syntax — I'm also experimenting with identifying the places I can transform recursive procedures into iterative loops.) Note that the type test (pair? x) is repeated twice. If some kind of match clause were used instead, we would see the test lifted to wrap the (GOTO g17 ...) expression, leaving us with something more like

(letrec ((g17 (lambda (x acc)
                (if (null? x)
                  acc
                  (if (pair? x)
                      (GOTO g17 (PRIMcdr x) (+ (PRIMcar x) acc))
                      (error '"Not a pair in match" x))))))
  (g17 a '0))

which, when compiled, is about as efficient as you will get with a statically compiled Scheme. Lots of the optimizations developed in the Self system apply to dynamically compiled variants, of course, potentially leading to further efficiencies.

On this page about syntactic closures, we see the definition of an anaphoric-if macro that doesn't transmit the "it" binding to the alternative clause — just to the consequent. This is pretty sophisticated. I immediately began to think about how you could do the same with syntax-case (as clearly others had before me) and it turns out to actually be easier. The only real downside is the introduction of another binding — but of course the mythical Sufficiently Smart Compiler will optimise that away immediately anyway.