Representation Invariant

Moving...

2009-09-26T17:44:00.002-04:00

I started this blog before I co-started a company of similar name. To more clearly separate my opinions from my company situation, I'll be posting over at engvhack now. (Where, in the first post, I mention company work; but the parts where I say various people are idiots, you need to understand, are wearing my personal hat, not my professional hat.)

50 in 50: finally on video

2008-11-22T13:17:00.002-05:00

Guy Steele and Richard Gabriel's marvelous performance art programming languages talk "50 in 50" is finally online in video form. I saw this debut at HOPL III a couple years back, and have been wishing for a video ever since. Via Lambda the Ultimate. Yeah, I haven't posted in almost a year. Get used to it.

Per-post comment feeds

2008-01-23T09:39:00.000-05:00

I've just changed the blogspot settings so that posts and comments are separate feeds. That seems to be how most of the cool kids do it these days. Updated: in addition to the per-post comments feeds, there's now a link for an all-comments feed at the bottom of the main page. I wound up hand-editing the blogger template to add that; surely there's a better way...?

Thoughts on Lisp: Things that other languages should take from Lisp

2008-01-22T23:40:00.000-05:00

Things I like about lisp that haven't crossed over into enough mainstream languages yet:

"Bignum" support: language-integers are logical-integers, not fixed-width bitfields. In Scheme and Common Lisp, by default you can't overflow an integer --- the language will dynamically expand the size of the representation as necessary. This guarantees numerical correctness, at the cost of some performance.

In Common Lisp, you can force your code to use fixed-size numbers (fixnums) for efficiency. I like this overall system: the default is automatically "correct", but you can turn the knob toward performance in critical regions. This helps avoid embarrassing explosions.

Ruby and Python, by default, treat language-integers as logical-integers. Java, C, C++, and Perl don't; you have to go out of your way to use a bignum class. The rest of the numeric tower is also nice to have, but far less essential to basic correctness.
Optional type declarations (Common Lisp.) CL allows, but does not require, type declarations. The compiler can use these declarations to improve the speed of compiled code, and you only have to put them in the critical regions to get the performance benefit. The compiler can also use type declarations to perform compile-time typechecking. (Sadly, it isn't required to do this.) I like being able to have a blend of static and dynamic typing in the same programming language. Both have their places.
Proper (unbounded) tail-recursion (Scheme.) If the last statement of a function, F, calls another function, G, there is no need to save space for F on the stack. In Scheme, such tail-recursion really doesn't reserve space. This lets you write tail-recursive algorithms that go arbitrarily deep, without worrying about running out of memory. The Scheme standard requires this to work. In most other languages, the stack space gets saved anyhow, as the language specifications don't forbid it.
Methods with multiple-dispatch (Common Lisp.) In most languages, when a method is invoked, the first argument to that method determines which of several implementations is actually run. In the Common Lisp Object System, any or all of the calling arguments may be used to select the method implementation. There's a lot I don't like about CLOS (perhaps I'll go on at length in some future post), but multiple dispatch is a very handy hammer to have in the toolbox.
Some Lisp implementations are fast. Unlike Ruby, Python, Perl, PHP, and JavaScript, both Common Lisp and Scheme have good native compilers.
Syntactic simplicity (Scheme.) This is a positive view of "syntactic poverty," which I said I don't like in I'm giving Scheme this exception here because it is widely used in teaching. Syntactic simplicity gets students writing code faster than if they're trying to handle a bunch of ideosyncractic syntactic rules. And student code is reliably write-once, read-never-again. Of course, even MIT seems to be replacing Scheme with Python in the undergraduate EECS curriculum. I'm inclined to bow to the wisdom of the practicing teachers on this one. Or perhaps Python is another incarnation of syntactic simplicity.

Coming up next: I'm going to give the Lisp series a break for awhile. I've got some robotics stories I've been meaning to write up forever. Maybe I'll get around to them finally.

The limits of touch-screens

2008-01-11T23:19:00.000-05:00

If a touch-screen is too big to wipe on your shirt sleeve, it's going to get too nasty to use. It's going to be too nasty even to sell, 'cause the floor-model in the shiny-shiny electronics store will be covered with greasy fingerprints.

Thoughts on Lisp: Things other languages took from Lisp

2007-12-08T16:40:00.000-05:00

Lisp has a lot of features that I really like. A number of them have crossed over into modern mainstream languages, e.g. Java, Perl, Python, Ruby, and JavaScript. Some of these features definitely appeared first in Lisp. John McCarthy's History of Lisp paper captures several of those. Other features may have been adopted by Lisp from other languages, but certainly Lisp had them before any other language currently in wide use.

Here are several features of Lisp which I really like, and which have crossed over into modern, mainstream programming languages:

Conditional expressions. (Not to be confused with conditional statements!) McCarthy invented these for Lisp, but now they've spread to every language. For C developers, these are expressions using the
```
(test ? consequent: alternate)
```
form. For Lisp developers, it's just anything using IF.
Garbage collection. The concept of garbage collection preceded Lisp, but was implemented in individual application. Lisp was the first programming language to support GC directly. Nowadays, every mainstream language newer than C++ has GC too. And I hear that even the C++ community has been talking about ways to fit it into the language someday.
Bounds-checked arrays. I don't know where this actually appeared first. I do know that Lisp has had it for a very long time. All the post-C++ mainstream languages have this now, too.
Interactive development via the "Read-Eval-Print Loop" (REPL). These days, developers using Python, Ruby, and even Java (via Eclipse) enjoy the benefits of interactive development.
Lexical scope by default (Scheme and Common Lisp, not Emacs Lisp.) Lexical scope makes possible for the reader of a program's text to figure out where each value comes from. This is an immense aid to human readability, and to static introspection such that as performed by IDEs. Most modern languages use lexical scoping most of the time, although there are certainly ways to use other scopes in, e.g., Perl.
Closures. When what you really want is a callback, a closure is sometimes far more elegant than, say, an object implementing a single method. Closures have crossed over, but the depth of support varies considerably. Perl and Ruby have full closure support. Python lets a closure refer to, but not modify, a lexically-closed-over value. As Dan Weinreb noted just today, Java only has anonymous objects, which are weak substitutes for real closures because they can only refer to 'final' lexically-closed-over values.

I'm sure I've missed more positive features that have crossed over from Lisp to modern languages. Please mention those in the comments. If you know (more of) the history of any particular feature --- and in particular, if you can provide references --- please add a comment as well!

One more assumption

Extending the list of my assumptions and prejudices (perhaps I should have called them values?) in this post, here's one more::

Encapsulation is good. It should be exceedingly difficult, if not downright impossible, to reach into the guts of a complex abstraction and fiddle with it.

On typing (poh-tay-toh) and typing (poh-tah-toh)

One often-heard statement about Lisp is that it requires much less code (that is, less typing) to get something done than Java. I wonder what percentage of that is because everything is done with one type: the pair. More typing requires more typing, as it were.

Does this fit with people's practical experience? How does it fit with other comparison points, e.g. Python?

Coming up next...

Things I like in Lisp that still haven't crossed over

Thoughts on Lisp: Things I don't like about lists

2007-11-25T00:23:00.000-05:00

Lisp, of course, is named because it is a LISt Processing language. So I'll start right at the foundations with a list of things I don't like about Lisp's lists:

"List" isn't a tagged type. A pair (known to Lisp as a cons) is a tagged type. "List" is a term for a pair that happens to obey a content requirement, specifically the second element of the pair is either another "list", or is empty.
Lists don't have identity. A list is identified by its first pair. If you sort "a list", the reordered list may be identified by a different first pair than the unsorted list was.
Two or more lists can share pairs. Now imagine what happens if you sort one of them.
Lists are used where other data structures would be more efficient. In CL, for instance, association lists and property lists are both list structures representing key-value mappings. In CL, each has a distinct search function --- assoc for alists, getf for plists.
Pair-based data-structures must be manually maintained. E.g., it's up to the programmer to maintain an alist such that it continues to fulfill the structural requirements of being an alist.
Pair-based data-structures don't convey intent. Given a particular pair, it may just be a pair, it may be a list, it may be a property list, etc. It may have been intended to denote any of those, or something else --- a tree, an association list, etc. The pair itself doesn't describe the programmer's intent when it's sitting naked in the debugger.
Syntactic poverty. This is the classic "too many parens" complaint. Lisp uses parentheses to denote all code constructs and sub-constructs. This makes Lisp harder to read than Algol-family languages. In part, this is because the meaning of each paren-delimited form is dependent upon its entire lexical context. And in part, this is because specialized syntax is helpful to the human reader, even if it's technically redundant.
Lisp programs are represented as lists. This is why the code is fully-parenthesized: lists are denoted with parens. It is true that this makes Lisp easy to parse. But nobody is having much trouble parsing Python, either. I'm still conflicted about Lisp's structured macros --- that's for a later post --- but I'd like to see the next language that represents its code as data structures use a few more data structures for the representation.
Lisp programs aren't really represented as lists anyhow. A Lisp program is represented as a collection of files. Within a file, yes, there are lists, but there are also comments and whitespace describing and structuring those lists. Code which has been literally reduced to a list is tremendously less readable than the original, commented, formatted source. It's an important distinction to make, but one that is often lost.

So what don't you like about lists in Lisp?

Coming up next...

Things other languages took from Lisp

Thoughts on Lisp: Preface

2007-11-24T23:46:00.001-05:00

Over the last few weeks, I've been making lists for myself. Things I like don't like about Lisp. Things I do like about Lisp. Things that I think are interesting and cool about Lisp, but which I still feel conflicted about. And so on. Over the next little while, I'm going to publish and embellish my lists in a series of posts.

Background

I first met Scheme in 1990. Since it was a big part of my computer science education, I encountered it frequently, and extensively, over the next several years. I came to really like Scheme.

As an Emacs user, I also came to write occasional snippets of Emacs Lisp (Elisp). I never came to like it, but I never did anything large in it, either.

Once or twice, I dabbled briefly in Common Lisp. Until 2006, I didn't do anything substantial with it. But in 2006, I got my chance, and I spent the next eighteen months working in CL.

I had been very excited about the chance to work with Common Lisp. Many of the smartest people I know were and are raving CL fans. Having banged my head against CL on my own without achieving enlightenment, I was hoping to achieve CL nirvana by CL immersion.

No such luck.

Instead, I wound up with a complicated, conflicted, love-hate relationship with Lisp in general. Which relationship will hopefully make this series more interesting than if I was just another unalloyed Lisp fan.

Audience

The intended audience for this series consists of two groups. The first target group is programmers who don't know Lisp, but are curious about it. By and large, the 'net is full of people who either love Lisp without reserve, or who freaked out about Lisp's heavy use of parentheses and never made it to the interesting parts. I hope I represent a more nuanced position.

The second target group is programmers who do know Lisp, and like thinking about how to make the next great Lisp dialect (Lisp 2010?) an improvement on its ancestors.

Specifically omitted are those people to whom some specific dialect of Lisp is the ultimate programming language, never to be improved upon. If you're one of them, stop reading. This series will only raise your blood pressure.

Assumptions and prejudices

My comments on Lisp are explicitly subjective. I'm not saying "this is good," or "that sucks." I'm saying "I like this", and "I don't like that." But to provide some hint of where I'm coming from, here are some of the assumptions that I tend to make:

Code is read more often than it is written.
The basic meaning of a code fragment should be context-independent.
Correctness precedes performance. It's easy to be fast and wrong.
The most important programming nowadays is done by teams.
Development tools should be able to introspect on programs and their source.
Expressivity is good. Clarity is better.
Most clever hacks aren't smart. Most aren't good engineering, either.

Coming up next...

"Things I don't like about lists."

Theory as software architecture (or the other way around)

2007-10-22T14:32:00.000-04:00

I read Scientific American magazines out of order. I just read the March '06 edition wherein I encountered a piece called "The Limits of Reason", by Gregory Chaitin. Early in his article, Chaitin paraphrases Leibnitz as essentially stating that "a theory has to be simpler than the data it explains, otherwise it does not explain anything." Chaitin goes on to say, a bit further on, "Leibniz's insight, cast in modern terms [is that] if a theory is the same size in bits as the data it explains, then it is worthless, because even the most random of data has a theory of that size. A useful theory is a compression of the data; comprehension is compression. You compress things into computer programs, into concise algorithmic descriptions. The simpler the theory, the better you understand something."

These observations struck me as an interesting lens through which to view software development.

We start development with a problem to solve. In top-down and spiral development, we develop a high-level architecture to guide initial development. This architecture is typically an explicit, abstract depiction of the structure of the software we intend to build, along with some specifications of other essential properties, e.g. performance.

This high-level architecture is actually a theory. The theory claims that there exists at least one program with the specified structure (and other essential properties) which solves the initial problem. Of course, this theory (architecture) may or may not be correct. To find out, we attempt, via programming, to discover a representative of the type of program predicted by the theory.

 Problem statement ->  Theory (architecture) -> Existence proof (program)

If our programming efforts succeed, we prove the theory. If we fail, however, this does not, a priori, invalidate the theory; our empirical search is hardly exhaustive. However, often we discover things in programming that solidly disprove some element of our theory.

On a good day, we use these discoveries to generate a new theory similar to the first one, but accomodating the new facts. This is, of course, spiral development. With our revised theory in place, we can begin the search for a proof once again. This is spiral development, of course, and a successful outcome will eventually give us both a high-level architecture/theory, and a program/existence proof whose structure and other essential properties are accurately described/predicted by the architecture/theory.

On a bad day, we aren't doing spiral development. We're in a hurry, and so the theory (architecture) is abandoned, and the programming turns into a search for a program whose existence proves a much less stringent theory, to wit: there exists a program which solves the original problem.

 Problem statement -> Program

Unfortunately, if we succeed only at generating a program that solves the problem, we have no theory to tells us something about the structure of the program. The program we generate this way will be a classic example of big-ball-of-mud architecture: everything is connected to everything else, and no compressed description --- no theory, no architecture --- of the program's structure or other essential properties can be derived. This program is highly entropic in both a practical and an information-theoretic sense.

Confronted with such a program and some time to make things right, we might attempt refactoring. In the "architecture as theory" metaphor, refactoring is a heuristic search through program-space for a more-compressible program. Given a compressible program, we can derive an architecture --- a theory --- after-the-fact, as it were.

So why do we care if we have an architecture for a program? If it solves the problem, isn't that good enough?

A theory predicts properties and behaviors of, well, whatever it is the theory describes. Correspondingly, a high-level software architecture predicts the properties and behaviors of the system it describes. This isn't just useful for understanding the software itself --- although that is extraordinarily valuable. It's also useful in reasoning whether or not the program really solves the original problem.

In top-down development, we make a theory which explicitly says things about the program we intend to write. But the theory also implicitly encodes a lot of information about the problem we're trying to solve --- or at least, our understanding of the problem.

When we start with a big ball of mud, though, we don't have an implicit encoding of the problem which is smaller than the program itself. So through refactoring, we're not only trying to discover a program for which we can manifest an underlying theory, but we're also deriving a compressed description of the problem this program is solving. This compressed representation gives us a much better chance of detecting mismatches between the problem actually being solved, and the problem we want to solve.

One final thought on the implications of this metaphor: architecture is generating a theory. Coding is searching for a proof for the theory. The more incorrect the initial theory, the longer it will take to iterate to a correct one. This process is at least as much science, in the laboratory research sense, as it is engineering. Is it any wonder it's hard to predict how long a piece of software will take to write?

I'll wrap up with credit where it's due: my thinking in this post has been heavily informed by papers posted by Scott Rosenberg in his "Code Reads" series. If you've read this far without falling asleep, you clearly like this stuff and you should definitely be reading his blog if you're not already.

Book review: Learning JavaScript, by Shelley Powers

2007-09-11T22:55:00.000-04:00

I don't usually bother with book reviews, but Learning Javascript, by Shelley Powers, is an exceptionally bad technical book.

I could write a page-by-page critique, but I'll limit myself to five things that illustrate the problems with this book:

Most blatant, the publisher's confirmed errata runs to 9 printed pages. It includes 83 distinct items. That's an acknowledged error every 4 pages.
The book is full of imprecisions and subtle errors that aren't captured in the errata. For instance, on page 221, the book states "Instead of using prototype, I could have added the trim function directly to a string instance (variable)... Only if the property or method is not found in the global object as part of the basic object or via the prototype collection, does the engine search for it locally, attached to the variable."

There is an important distinction between a variable and its contents. But the author first conflates them, saying "...instance (variable)...", and then says "variable", where in both cases "instance" is correct and any mention of "variable" is wrong.
Oh, and by the way, the order described is back-asswards: in actuality, local properties trump prototype properties, not the other way around.
Here is an excerpt from the much better book, Javascript: The Definitive Guide, 5th edition by David Flanagan:
When the JavaScript interpreter starts up, one of the first things it does, before executing any JavaScript code, is create a global object. The properties of this object are the global variables of JavaScript programs. When you declare a global JavaScript variable, what you are actually doing is defining a property of the global object.
The JavaScript interpreter initializes the global object with a number of properties that refer to predefined values and functions. For example, the Infinity, parseInt, and Math properties refer to the number infinity, the predefined parseInt( ) function, and the predefined Math object, respectively...
In client-side JavaScript, the Window object serves as the global object for all JavaScript code contained in the browser window it represents. This global Window object has a self-referential window property that can be used instead of this to refer to the global object. The Window object defines the core global properties, such as parseInt and Math, and also global client-side properties, such as navigator and screen. ...
JavaScript implementations may allow multiple global execution contexts, each with a different global object. (Although, in this case, each global object is not entirely global.) ...Client-side JavaScript code in each frame or window runs in its own execution context and has its own global object. However, these separate client-side global objects have properties that link them. Thus, JavaScript code in one frame might refer to another frame with the expression parent.frames...

Unless I really missed something, the "global object," its relationship to scope, and the possibility of having several instances of it at once, are never clearly discussed in Learning JavaScript. Certainly the "global object" doesn't appear in the discussion of global variables; neither is it mentioned in the chapter on objects; nor is it mentioned in the index. The section on frames mentions the use of "parent", but doesn't explain that "parent" is, again, a property on the local "global object."

Which brings me to my next item:
The index is barely 7 pages long. In its brevity it omits innumerable important keywords, functions, and concepts.
Finally, the book is poorly organized. For instance, the section on error handling appears in the middle of the chapter on "Creating Custom Javascript Objects."

Overall, if you make it through Learning JavaScript you'll probably be able muddle through some JavaScript, but you're not going to have a good mental model of what it is you're actually doing. I say go straight for Javascript: The Definitive Guide: it's well-written, has great technical accuracy, and is much more comprehensive than Learning JavaScript

Coming soon...

2007-05-23T00:49:00.001-04:00

My original plan for this blog was to post a longish post once a month or so. That's still the plan, I'm just behind schedule. Coming soon: the first in an occasional series on what is still interesting, novel, or otherwise distinguishing about Common Lisp; and following that, a geeky tale from my previous job on how clear water killed a robot submarine. Stay tuned...

Oracle: Unbreakable 'cause it's already broken

2007-03-18T00:54:00.000-04:00

Nothing original here, just a rant: "Imagine issuing a query and getting unexpected results." Why? Because SQL can execute in the wrong schema. Thank you, Oracle. May I have another? (This bit us hard at work.) Seriously, how did this get out the door? Do these people have a QA process? Do banks and brokerages actually rely on Oracle to keep track of money? This is apparently bug 5458753, metalink note 392673.1. Am I overreacting? Jeremy

Universal search and select

2007-03-11T00:16:00.000-05:00

I'm a long-term Emacs user. I keep trying to use other tools, but they come up short on two critical points. Universal search: Every window should feature incremental search. Every editor is searchable, sure, but I want to be able to search the class hierarchy, the debugging backtrace, and, most importantly, the help-screen that displays all the keybindings. I want to do all of this without a dialog window popping up. Furthermore, the search interface should be consistent. Eclipse, for instance, lets me search most of its windows, but the interface is different for the editor (fragment matching, with dialog), the Debug view (wildcard matching, with dialog), and the Outline view (match from beginning of line only, with text-entry-box in the same window.) Universal selection: All text should be selectable/copyable, in whole or in part. I don't ever want to see a filename that I can't highlight, a class name that I can't copy, an error message that I can't xerox into a bug report. In the ideal world, even tooltip text would be selectable. Again, the interface shoujld be consistent. To pick on Eclipse once more, the interface for selection varies by view: in Editor and Console views, I can select arbitrary text, but in Outline and Debug, I can only select an entire line at a time. Of course, I should be able to perform both searching and selection without using the mouse. Emacs makes a mighty ugly GUI toolkit. To its credit, though, you can search every window, and you can select any* contiguous text-fragment. The interface to search and select is identical regardless of which application you're using. It never pops up dialog windows. It's easy to drive from the keyboard. Why aren't all the whizzy new GUIs at least this good? Jeremy [*] The mode-line seems to be an exception to this rule. How irritating.