Kevin Reid's blog

One of the nice things about Common Lisp is the pervasive use of (its notion of) symbol objects for names. For those unfamiliar, I'll give a quick introduction to the relevant parts of their semantics before going on to my actual proposal for a “good parts version”.

A CL symbol is an object (value, if you prefer). A symbol has a name (which is a string). A CL package is a map from strings to symbols (and the string key is always equal to the symbol's name). A symbol may be in zero or more packages. (Note in particular that symbol names need not be unique except within a single package.)

Everywhere in CL that something is named — a variable, a function, a class, etc. — the name is a symbol object. (This is not impractical because the syntax makes it easy to write symbols; in fact, easier than writing strings, because they are unquoted.)

The significance of this is that the programmer need never give significance to characters within a string name in order to avoid collisions. Namespacing of explicitly written symbols is handled by packages; namespacing of programmatically generated symbols is handled by simply never putting them in any package (thus, they are accessible only by passing references); these are known as gensyms.

Now, I don't mean to say that CL is perfect; it fails by way of conflating too many different facilities on a single symbol (lexical variables, dynamic variables, global non-lexical definitions, ...), and some of the multiple purposes motivate programmers to use naming conventions. But I think that there is value in the symbol system because it discourages the mistake of providing an interface which requires inventing unique string names.

(One thinking along capability lines might ask — why use names rather than references at all? Narrowly, think about method names (selectors, for the Smalltalk/ObjC fans) and module exports; broadly, distribution and bootstrapping.)

So, here’s my current thought on a “good parts version”, specifically designed for an E-style language with deep equality/immutability and no global mutable state.

There is a notion of name, which includes three concrete types:

1. A symbol is an object which has a string-valued name, and whose identity depends solely on that string.
2. A gensym also has a name, but has an unique identity (selfish, in E terms). Some applications might reject gensyms since they are not data.
3. A space-name holds two names and its identity depends solely on that combination. (That is, it is a “pair” or “cons” specifically of names.)

Note that these three kinds of objects are all immutable, and use no table structures, and yet can produce the same characteristics of names which I mentioned above. (For implementation, the identity of a name as above defined can be turned into pointer identity using hash consing, a generalization of interning.) Some particular examples and notes:

• A CL symbol in a package corresponds to a pair of two symbols, or perhaps a gensym and a symbol. This correspondence is not exact, of course. (In particular, there is no notion here of the set of exported symbols in a package. But that's the sort of thing you have to be willing to give up to obtain a system without global mutable state. And you can still imagine 'linting' for unexpected symbols.)
• The space-name type means that names can be arbitrary binary trees. If we consistently give the left side a “namespace” interpretation and the right side a “local name” one, then we have a system, I think, where people can carve out all sorts of namespaces without ever fearing collisions or conflicts, should it become necessary. Which probably means it's massively overdesigned (cf. "worse is better").
• Actual use case example: Suppose one wishes to define (for arbitrary use) a subtype of some well-known interface, which adds one method. There is a risk that your choice of name for that method conflicts with someone else's different subtype. Under this system, you can construct a space-name whose two components are a large random number (i.e. a unique ID) acting as the namespace, and a symbol which is your chosen simple name. One can imagine syntax and tools which make it easy to forget about the large random number and merely use the simple name.
• It's unclear to me how these names would be used inside the lexical variable syntax of a language, if they would at all; I suspect the answer is that they would not be, or mostly confined to machine-generated-code cases. The primary focus here is improving the default characteristics of a straightforwardly written program which uses a map from names to values in some way.

(This is all very half-baked — I'm just publishing it on the grounds described in my previous post: in the long run I'll have more ideas than I ever implement, and this is statistically likely to be one of them, so I might as well publish it and hope someone else finds some use for it; if nothing else, I can stop feeling any obligation to remember it in full detail.)

I really haven't been posting very much, have I? It's mostly the job occupying most of my “creative energy”, but I've also been doing a little bit of this and that and not ever finishing something to the point of feeling like writing it up.

On the programming-projects front, I'm attempting to extract two reusable libraries from Cubes for the benefit of other web-based games.

• Measviz takes performance-measurement data (frames per second and whatever else you want) and presents (in HTML) a compact widget with graphs; my excuse for not announcing it is that the API needs revision, and I haven't thought of a good toy example to put in the documentation-and-demo page I'm writing, but if you're willing to deal with later upgrades it's ready to use now.
• The other library, currently in need of a good name, is a generalized keybinding library (generalized in that it also handles gamepads/joysticks, which are completely different). You define the commands in your application, and it handles feeding events into them. Commands can be polled, or you can receive callbacks on press and release, with optional independent autorepeat. It's currently in need of a name, and also of API cleanup.

I've been making some sketches towards a redesign of E (list archive pointer: starting here), basically to take into account everything we've learned over the years without being constrained by compatibility, but it hasn't gotten very far, partly because language syntax is hard — all options are bad. (The current E syntax is pretty good for usability, but it has some particularly verbose/sea-of-punctuation corner cases, and I'd also like to see a simpler syntax, with more facilities moved into code libraries.)

It’s now confirmed that I'm going to be doing the same thing this summer as last summer: working at Google on Caja.

All comments, congratulations, housing recommendations, and activity suggestions are welcome.

One of the things I’ve been procrastinatingah, not had the time to do, being busy with school and other projects, is announcing and working on a job search for this summer. I have posted my resume, but I didn’t even get around to mentioning that. The process really doesn’t excite me that much — it’s essentially research, comparison shopping, which I have never been very fond of.

But, last October, I was contacted out of the blue by a recruiter asking if I was interested in opportunities at — Google. After checking that it wasn’t a spoof I naturally said yes, and after a number of rounds of information exchange and interviews,

This summer, I will be (well, subject to my completing the process of accepting the offer) working as a Software Engineering Intern at Google, with the Caja team, in Mountain View, CA.

So — whoa and yay and other such cheerful words. And thanks to my friends at Google who referred me and nudged the process along.^*

The most uncertain remaining step is finding housing in or near Mountain View (could be as far as San Francisco or San Jose; Google runs a shuttle bus and is convenient to public transportation). Google has provided some general advice-for-interns, but I’d like to hear input from my readers and friends who already live in in the area.

Some parameters:

• I would consider living with other people, but I wouldn’t want to take a chance on a complete unknown. (So if you are someone or know someone with a room...)
• Speaking of taking chances, make the chance of being mugged on the way home in the evening very small, please.
• I am traveling from the east coast, probably by train, so I don’t want to have to transport a lot of stuff, or buy items that I’ll use for only three months — so a furnished space is better.
• I do not own a car, but I know how to drive one.
• I do not own a bicycle, but I used to know how to ride one.
• This will be the first time I have lived outside of my home city for longer than a week’s visit/vacation.

^*Y’know how job search advice is big on saying you should be “networking”? If you’ve thought you’re too much of the non-face-to-face-social non-polite-small-talk would-rather-talk-to-people-through-the-computer sort for that — take me as an example. This opportunity came to me because of other people who knew me entirely through my work on open source projects (E, and thus Caja-CapTP) — I didn’t do anything that I wouldn’t have done for other reasons anyway. I’m not saying you shouldn't do any of the other stuff you might be thinking of — I’m saying this stuff counts.

The previously-mentioned darcs repositories (which are e-aui, e-modules, factor, norsmu) have been moved to my new server at http://switchb.org/darcs/. As far as I recall, I haven't published any links to these except privately and to mailing lists, so I haven’t updated any links for the new location; but if you had the old location, now you know where to go.

Late update on Caja-CapTP:

Google Summer of Code is over. I passed based on revised goals, but I'm not happy with the state of the code and I did not complete any significant part of the original plan.

Regarding the items mentioned in my last update:

• Write more documentation/comments.
• Commit as much of the work-in-progress as I can.
  • ...including the incomplete CapTPConnection, even though its tests don't pass yet, so that the partial work can be counted.

I committed CapTPConnection, and found and fixed enough infrastructure (whenResolved, CommTable, SwissTable, deSubgraphKit, etc.) bugs that it starts up and can do a basic operation or two. It's not useful for anything, but it's a lot closer to running than it was at the time of my last update.

Also, I removed dependencies on 'window' so in principle it will operate on a non-browser (server) JavaScript implementation. This has not been exercised because there is no browserless driver for the test scripts yet.

I stated that I would continue working on Caja-CapTP past the GSoC work period; however, with the time occupied by schoolwork, I have not had time or brain space to do so yet. I am not going to abandon the project.

Had a bit of a breakthrough in debugging facilities: realizing that there's no reason I shouldn't modify my local copy of the Cajita runtime to provide more debug information (and it doesn't matter if it subtly breaks security, even, as long as Caja-CapTP is still compatible with the proper version).

Only a week or so left. I've discussed the matter with MarkM, and he pointed out (again) that I should work toward having useful-to-other-people components even if I haven't finished the one I intended to do.

Toward this end, I am going to work on Data-E (which is already part of the Caja-CapTP project) as a standalone serialization utility (for network and disk) as I understand it will be useful for Shakhar.

Todo items:

• Implement generic literals (description) to make it more JavaScript-natural.
• Implement cyclic object graph handling using Ref promise implementation already done.
• Commit all in-progress work as reasonable changesets (even the tests that don't yet pass).
• Document what works, design decisions, etc.
• Continue to work on CapTP itself as time permits.

I intend to continue working on the Caja-CapTP project beyond GSoC; both simply because it is a project of mine, and to mitigate my failure to complete the planned work on schedule. However, for the next few months it will have to compete with my college work rather than my procrastination.

Common Lisp provides compile-file whose purposes is to convert a CL source file into an (implementation-defined) format which usually has precompiled code and is designed for faster loading into a lisp system.

compile-file takes the pathname of a textual lisp source file. But what if you want to compile some Lisp code that's not in a file already, perhaps because you translated/compiled it from some not-amenable-to-the-Lisp-reader input syntax, or because it contains unREADable literals? You can use a "universal Lisp file", which I know two ways to create (use whichever you find cleaner):

(cl:in-package :mypackage)
#.mypackage::*program*

(cl:in-package :mypackage)
(macrolet ((it () *program*))
  (it))

Suppose this is in "universal.lisp". Then to use it:

(defvar *program*)

(defun compile-to-file (form output-file)
  (let ((*program* form))
    (compile-file #p"universal.lisp"
                  :output-file output-file)))

This is just a minimal example; you'll also want to appropriately handle the return value from compile-file, provide an appropriate pathname to the universal file, etc. For example, here's an excerpt of the relevant code from E-on-CL, where I have used this technique to compile non-CL sources (emakers) into fasls:

(defparameter +the-asdf-system+ (asdf:find-system :e-on-cl))
(defvar *efasl-program*)
(defvar *efasl-result*)
...
(defun compile-e-to-file (expr output-file fqn-prefix opt-scope)
  ...
  (let* (...
         (*efasl-program*
           `(setf *efasl-result*
                  (lambda (...) ...))))
    (multiple-value-bind (truename warnings-p failure-p)
        (compile-file (merge-pathnames
                        #p"lisp/universal.lisp"
                        (asdf:component-pathname +the-asdf-system+))
                      :output-file output-file
                      :verbose nil
                      :print nil)
      (declare (ignore truename warnings-p))
      (assert (not failure-p) () "Compilation for ~A failed." output-file))))

(defun load-compiled-e (file env)
  (let ((*efasl-result* nil)
        ...)
    (load file :verbose nil :print nil)
    (funcall *efasl-result* env)))

Note that the pathname is computed relative to the ASDF system containing the universal file; also note the use of a variable *efasl-result* to simulate a "return value" from the compiled file, and the use of a lambda to provide a nonempty lexical environment, both of which are features not directly provided by the CL compiled file facility.

I completed enough of the E-on-JavaScript improvements, and wrote the beginnings of one Data-E kit in Cajita, together with the Updoc tests for it, and a Makefile to cajole the JavaScript and "animate" the Updoc - convert it into a HTML page that actually runs the tests.

I also improved various readme files and pages, hopefully such that someone else can get it all installed on their own system starting from my project page without too much prior knowledge.

Near-term plan: Put aside the EoJS, and get the Data-E kits working; then the surgeon; then the CapTPConnection; then define, document and implement a CapTP-over-HTTP protocol.

I have been accepted to Google Summer of Code 2009!