The Supposed Primacy of Text

As should be obvious to my regular readers, I'm using the Axis of Eval to post raw thoughts. I don't do the work of rigorously thinking these thoughts through. I'm trying to narrate my mental work, in whatever state it is at the moment, with the hope to engage in dialogue with those of you with similar interests.

With this disclaimer out of the way, another take on the text/graphical axis.

In a comment on The Escape from the Tyranny of the Typewriter, John writes:

Okay, I'll play devil's advocate here. Text is the most articulate form of expression we have; it's so potent that even your graphical representation actually resorts to it. If you're going to introduce something else as well, that reduces simplicity, so there should be a very clear reason for it, and what you introduce should be in some sense manifestly The Right Thing.

But the plain text we use with computers is hugely impoverished, compared to pre-computer texts. Compare to Dadaists' use of text (the art at beginning of text) or religious texts, which were widely "scribbled in the margins", and adorned with many graphical features.

Or take mathematical text: it has rich, mostly informal structure for conveying information:



This brings us to computers' favorite: a sequence of code-points. That is simply in no way adequate to represent the exploits of the past, not to speak of the future.

Modern mathematicians are shoehorned into writing their fomulas in LaTex and having them presented to them in ASCII art in their mathematical REPLs.

So let's turn the tables: Plain text is a particular special case of using a general purpose graphical display to display sequences of code points. Furthermore, plain text stored in a file is also just a special case of arbitrary information stored in a file.

Escape from the Tyranny of the Typewriter

One misconception of computing is that plain text is somehow the natural thing for a computer to process. False. It only appears that way, because even the lowest layers of our computing infrastructure are already toolstrapped to work with the bit patterns representing plain text.

Thinking about graphical syntax, combined with the brain stimulating powers of Kernel, it occurred to me that in a fundamental sense,

(+ 1 2) is really just a shorthand for (eval (list + 1 2) (get-current-environment))

(Note that I'm assuming the existence of a Sufficiently Smart Partial Evaluator in all my investigations. As history shows, after the 5 decades it takes for Lisp ideas to become mainstream, it's perfectly possible to implement them efficiently.)

This harks back to my previous post about using and mentioning syntax. The (+ 1 2) is the way we directly use the syntax, whereas (eval (list + 1 2) (get-current-environment)) is the way we use mentioned syntax.

But why have two? Obviously, in a typewriter-based syntax, writing (eval (list + 1 2) (get-current-environment)) all the time would be much too cumbersome. But in a graphical syntax, the difference between the two might be just a different border color for the corresponding widgets.

This means: maybe we don't even need a way to use syntax, and can get by with just a way of mentioning it.

Put differently: In typewriter-based syntax, we cannot afford to work with mentioned syntax all the time, because we would need to wrap it in (eval ... (get-current-environment)) to actually use it. A graphical syntax would make it possible to work solely with mentioned syntax, and indicate use in a far more lightweight way (e.g. a different color).

But maybe that's bull.

What is Lisp syntax, really, and the use-mention distinction

In a recent comment, John Shutt wrote:

I do agree that the success of Lisp depends quite heavily on the fact that it has no syntax dedicated to semantics. But this means that, to the extent that a language introduces syntax dedicated to semantics, to just that extent the language becomes less Lisp.

After a couple of days of thinking about this on and off, in the context of hypercode/graphical syntax, I came to these thoughts:

I think the cornerstone of Lisp, wrt to syntax, is that the barrier between using a piece of syntax and mentioning it is very low.

When I write (+ 1 2), I use the syntax to compute 3. But when I write '(+ 1 2) I just mention it. Note that the difference between use and mention is just one small sign, the quote '.

Let's take a piece of syntax -- corresponding to (let ((x 1) (y 2)) (+ x y)) -- in a hypothetical graphical syntax:

let	x 1 y 2
	+ x y

The green border around the variable bindings, and their gray background is meant to indicate that the set of bindings is not just usual Lisp list-based syntax, but rather that we're using a special widget here, that affords convenient manipulation of name-value mappings.

This point is important. The graphical syntax is not equivalent to (let ((x 1) (y 2)) (+ x y)) -- it doesn't use lists to represent the LET's bindings, but rather a custom widget. The LET itself and the call to + do use "lists", or rather, their graphical analogue, the gray bordered boxes.

So it seems that we have introduced syntax dedicated to semantics, making this language less Lisp, if John's statement is true.

But I believe this is the wrong way to look at it. Shouldn't we rather ask: does this new syntax have the same low barrier between using and mentioning it, as does the existing Lisp syntax?

Which leads to the question: how can we add new (possibly graphical) syntax to Lisp, while keeping the barrier between use and mention low?

In conclusion: my hunch is that we can add syntax to Lisp, without making it less Lisp, as long as the new syntax can be mentioned as naturally as it can be used.

Follow-up: Escape from the Tyranny of the Typewriter.

HN discussion

[Meta] possibly lost comment

If you've posted a comment in the past couple days, and it hasn't showed up, please repost it. Thanks.

(The Blogger GUI showed me that there's an unmoderated comment, but when I clicked on it, it wasn't there, so maybe it got lost somehow.)

Fear and Loathing at the Lisp Syntax-Semantics Interface

You poor fool! Wait till you see those goddamn parentheses.

Recent investigations of xonses and first-class patterns have driven home an important point:

Part of Lisp's success stems from its heavy use of puns.

Take (LET ((X 1) (Y 2)) (+ X Y)) for example. The pun here is that the same syntactic device - parentheses - is used to express two wildly different things: calls to the LET and + combiners on the one hand, and a list of bindings on the other.



Let's step back from Lisp's typewriter-based syntax for a moment, and imagine a graphical 2D syntax and a convenient 2Dmacs hypercode editor. Since we're now fully graphic, fully visual, it makes little sense to construct lists. We construct real widgets. So we would have one widget for "list of bindings" and all kinds of snazzy displays and keyboard shortcuts for working with that particular kind of form.

We don't have that editor yet, but still it makes sense to think about first-class forms. Right now, we restrict ourselves to lists and atoms. But why shouldn't the list of bindings of a LET be a special form, with a special API? E.g. we could write (LET [bindings [binding X 1] [binding Y 2]] (+ X Y)). Of course this is horrible. But look back at the imaginary 2D editor again. There we wouldn't have to write the [bindings [binding ... stuff. We would be manipulating a first-class form, a special GUI widget for manipulating a list of bindings...

Xonses progress report

I have rewritten my interpreter to use xonses throughout. As expected, Lisp code that doesn't use them is unaffected, and continues running as-is.

To recap: xonses are like conses, but in addition to car and cdr, they may have any number of other slots.

() == {} ;; nil is just an empty xons
(a) == { :car a :cdr {} }
(:foo 1) == { :foo 1 }
(:foo 1 2 3) == { :foo 1 :car 2 :cdr { :car 3 :cdr {} } }
(open-file "README" :mode "rw" :create-if-not-exists #t) ==
{ :mode "rw" :create-if-not-exists #t :car "open-file" :cdr { :car "README" :cdr {} } }

The differences between a Lisp/Kernel with conses and one with xonses are mostly:

• There is no longer a separate nil. A xons without car and cdr is treated as nil, even if it has other slots.
• The usual pair? predicate changes from (instance? obj Pair) to (and? (instance? obj Pair) (not? (null? obj)).
  
  (These previous two rules have to do with the fact that xonses are more expressive than conses, and so we lose some "sharpness".)
• Pattern matching is extended, so that not only car and cdr are matched recursively, but all slots.
• Evaluation of arguments is extended: like in Kernel, an applicative cdrs down its operands and evaluates each, building the arguments list. In addition we now also evaluate the other slots of the first xons (Open question: should we also evaluate the other slots of later xonses? Probably yes).

All in all, xonses fit into the usual Lisp framework.

One big problem remains, which is why my new interpreter doesn't work:

In the x-expression (open-file "README" :mode "rw"), the :mode slot gets attached to the first xons, the one whose car is open-file. Per the usual evaluation rule, a combiner uses the cdr -- ("README") -- of the form it appears in as operand, and so it doesn't see the :mode slot.

I think it boils down to this: once we have arbitrary slots and not just car and cdr, it may make sense to remove the usual Lisp rule that the car of a combination contains its combiner. Maybe we need an explicit combiner slot:

(:combiner open-file "README" :mode "rw")

which corresponds to

(:combiner open-file :mode "rw" :car "README" :cdr ())

or abbreviated, using \ for :combiner.

(\open-file "README" :mode "rw")

Mirroring the fact that there's no nil, this also has the nice symmetry that calling a combiner without arguments requires no car and cdr anymore:

(\foo) means simply (:combiner foo), without car and cdr.

Investigating!

First-class patterns

A good sign: xonses are already making me think previously impossible thoughts.

In my Kernel implementation Virtua, every object can potentially act as a left-hand side pattern.

A pattern responds to the message match(lhs, rhs, env) -- where the LHS is the pattern -- performs some computation, and possibly updates env with new bindings. The rules for Kernel's built-ins are:

• #ignore matches anything, and doesn't update the environment.
• Symbols match anything, and update the environment with a new binding from the symbol to the RHS.
• Nil matches only nil, and doesn't update the environment.
• Pairs match only pairs, and recursively match their car and cdr against the RHS's car and cdr, respectively.
• All other objects signal an error when used as a pattern.

With these simple rules one can write e.g. a lambda that destructures a list:
(apply (lambda (a b (c d)) (list a b c d))
       (list 1 2 (list 3 4)))
==> (1 2 3 4)

Now, why stop at these built-ins? Why not add first-class patterns? We only need some way to plug them into the parsing process...

An example: In Common Lisp, we use type declarations in method definitions:

(defmethod frobnicate ((a Foo) (b Bar)) ...)

(a Foo) means: match only instances of Foo, and bind them to the variable a.

Generalizing this, we could write:

(defmethod frobnicate ([<: a Foo] [<: b Bar]) ...)

The square brackets indicate first-class patterns, and in Lisp fashion, every first-class pattern has an operator, <: in this case. The parser simply calls <: with the operands list (a Foo), and this yields a first-class pattern, that performs a type check against Foo, and binds the variable a.

Another example would be an as pattern, like ML's alias patterns or Common Lisp's &whole, that lets us get a handle on a whole term, while also matching its subterms:

(lambda [as foo (a b c)] ...)

binds foo to the whole list of arguments, while binding a, b, and c to the first, second, and third element, respectively.

Another example would be destructuring of objects:
(lambda ([dest Person .name n .age a]) ...)
would be a function taking a single argument that must be an instance of Person, and binds n and a to its name and age, respectively.

With first-class patterns, all of these features can be added in luserland.

Xonses

I think I finally had the breakthrough regarding named parameters and conses: Xonses.

In short:

(open-file "README" :mode "rw" :create-if-not-exists #t)
===
{ :mode "rw" :create-if-not-exists #t :car "open-file" :cdr { :car "README" :cdr {} } }

A bit more here on the klisp group, and I'll keep you posted here, of course.

Programming and boringness

"Computers are useless. They can only give you answers." -- Picasso  

"The use of a program to prove the 4-color theorem will not change mathematics - it merely demonstrates that the theorem, a challenge for a century, is probably not important to mathematics." -- Perlis

Once we can program a computer to solve a problem, that problem becomes boring.

It seems that when something is programmable, computable, it immediately loses its appeal as an endeavour for humans. Something that can be solved by an unthinking machine is no longer worthy of study by humans. (What remains to be of interest to humans are better ways to solve the same problem - write the same program better, more efficiently, more elegantly - but these seem second-order, once we have solved the problem.)

Of course this question opens a whole can of worms about what it means to be computable - e.g. does it have to be economically computable, or does it have to be computable before the end of the universe? But in general, I think that programming is interesting, because it touches upon the interesting issue of what it means to be boring.

Current status

Current status

Kernel Google Group

There's now a klisp Google Group for discussion of the klisp implementation of Kernel, and of Kernel in general. Check it out, there are some interesting posts already.

Also, there are now at least 12 implementations of Kernel and related languages.

[Scheme-reports] Just a load of.. well..

J. A. "Biep" Durieux has posted a highly interesting message to Scheme-reports, that should resonate with the "oh my, Scheme is much too big" crowd. (Which does exist, and does have a point.)

I have excerpted some highlights, and recommend to read it all:

---

Naming the Scheme languages

Therefore I propose "Schemer" for small Scheme, and "Schemest" for large Scheme. The one name clearly indicates its roots, and the other the fact that it is the maximal Scheme. The name "Scheme" would remain as the family name, and the report could be subtitled "Scheme: Schemer, Schemest".

The asymmmetry between multiple inputs and multiple outputs for procedures

This is inherent in Scheme syntax: the receiver of the output of an expression is indicated by the place where this expression occurs - which is necessarily singular: (get-some g1 (provide p1 p2 p3) g2). Repeating the expression would lead to repeated execution: (get-some g1 (provide p1 p2 p3) (provide p1 p2 p3) g2) - apart from being cumbersome.
Prolog has a symmetry in its syntax here that languages with nested expressions simply don't (and I think can't) have. Mark that this is independent of unification: it would be possible to have an unidirectional prolog-like notation, with a group of input variables and a group of output variables, say separated by a hyphen:
(lambda (a b - result rem quot) (quotient+remainder a b - quot rem) (* quot rem - result) (display result -))
Barely possible is "splicing in" multiple results - which would require them to be adjacent. A splicing construct (+ 1 ,@(quotient+remainder 25 4) 6) might do - see Lua for an even more constricting solution.

Tables and environments
This would lead to mutable first-class environments.
Let identifiers be hygienic - translated to locations (or location indicators, as the case may be) at the moment a procedure is defined. So (+ x 1) doesn't change when another x is inserted in a more local environment - or when it is deleted from the original environment. In the latter case the location is not garbage-collected, because this code still refers to it. It is also possible to write (+ (get-location-of 'a) 1), and *that* code is sensitive to environment manipulation.
(There might well be a flag indicating that each mention of an identifier is meant as a call to get-location - some kind of "don't inline" pragma.)
Oh, and environments shouldn't be different from other tables, and should have a way to indicate where to find a location that is not locally available. In that way various schemes of multiple inheritance would become trivially implementable.

Multi-pass compilation
This is like solving a consistency maintenance system (Jon Doyle called that "truth maintenance", some others "reason maintenance"), which is more for constraint satisfaction systems than for Scheme. Single pass with maximal deferment is the Scheme way: variables inside lambdas don't need to be resolved yet, resolution can be deferred until they are called. Without very strong reasons, one should not request different behaviour from syntax transformers. Ease of compilation, or speed of the resulting system are no strong reasons.

Sublanguages
Once there was Lisp/Scheme, which was about lambda. Then a completely different language for macro rewriting was added, and now a (hidden) constraint satisfaction system. I don't like that, it is feature on top of feature. A rewriter can be written in Scheme and then used in macro expansion - great, but let the rewriter then be generally available (because it has other possible uses), and be optional in writing syntax (because there are other ways that sometimes may be better). The same is true for a consistency maintanance or constraint satisfaction language - let them be first-class, explicit languages that one may use or not according to ones liking. That's what libraries are for.

Minimality
Something else is lost here. Scheme was about the right thing, but also about the minimal thing. Scheme provided a basis which was like a semantic assembly language: it provided primitives with which to build. Yes, certain complex systems ease programming - so let's make sure such systems can be written in Scheme, but let's not make them the basis of Scheme! It sounds like old-school anthropology: let's give primitives the right to remain primitive - while making sure they are NOBLE primitives.

Efficiency
Implementability is an issue for Scheme language design, but ease of implementation, or efficiency of implementation ought not to be. (I realise there are fringe issues, such as a theoretical lower limit of 2^2^n in space or time..) Compilability is nice, but never a basis for design decisions.

Macros
The principle of least surprise is already violated with macros. Macros must be bound before use; there is no equivalent to anonymous lambdas. Imagine ((if freevar ) arg ...) - this cannot be in Scheme, because Scheme wants to evaluate the arguments together with the head, whereas the head stipulates whether the arguments need to be evaluated in the first place. I think this evaluation rule reflects a thought error: a seeming symmetry was taken for a real one. Anonymous macros would be a boon, as would be runtime evaluation of expression heads, even if they are or may evaluate to macros. Right now a real symmetry (between procedures and macros) is lost for the sake of a false one.
This is about removing restrictions in the Clinger-sense, I think - having first-class syntactic transformers. Currently they have a status comparable to CL's functions - without the possibility of anonymous transformers or SYNCALL.
There is also no syntactic equivalent of "direct code" as opposed to code stored in a lambda form. Direct syntactic code would of course be immune to later redifinitions of transformers - as the transformation has taken place at the moment the single evaluation pass dealt with that bit of code.

Strings
Wouldn't a Schemish string be a sequence of character objects (soco), where a character object can be complex (base + modifiers)? Just as s-expressions respect the grammatical complexity of expressions, a soco would respect the grammatical complexity of text. If the sequence is a vector, string indexing and string-set! would be O(1). Yes, socos take more space than classical strings, but the same is true for s-expressions as opposed to flat program code.
For Schemes with only ASCII, the set of character objects would be the ASCII set, and the pointers could be 8-bit, i.e. the strings could be the classical string that we all know and love/hate. There's backwards compatibility.
Those who want size-changing substitutions can use some kind of tree representation of the sequence instead of vectors (lists being an extreme kind of unbalanced trees).
The interesting thing would be that people can choose their sequencing level: if you want to reason about code points, use sequences of code points; if you want to reason on the syllable level, make sequences of syllables. It is possible to have several levels: a sequence of words, each of which is a sequence of characters, each of which is a sequence of code points.
In other words: Scheme should not prescribe one crippling string format, but rather a set of specifiers which which people can define the strings they need. A classical ASCII-like one is obligatory, the others are optional.

Nuff said

Writing a Kernel-like language in Atomy and grinning from ear to ear.

— Alex Suraci (@alexsuraci) September 6, 2011

Call for use cases for Dart package system

Call for use cases for Dart package system.

Everybody loves to debate package/namespace management systems. But remember that some of our biggest software successes (C, Emacs, JS) get by fine withoutdon't have them. As Casey McCann says, no management is better than mismanagement.

"should I really take the time to learn fexprs?"

You should take the time to learn fexprs if you answer yes to any of these questions:

• You like Lisp, and want to learn even more about its rhyming scheme. Subjectively, a Lisp with fexprs feels even more Lisp than Lisp.
• You are dissatisfied with either the need for GENSYM, or for a hygienic macro system's complexity. Fexprs require neither.
• You think that everything in a PL should be first-class.
• You'd like to see how a single concept can replace both functions and hygienic macros.
• You want to implement a PL with as little code as possible (since fexprs give you the power of both functions and macros, you don't need to implement a macro system to bootstrap your PL.)
• You like to get your mind blown.
• You like hygienic macros, and want to understand better how they work. Even if you don't use fexprs, understanding them can show you how hygienic macros are really a special case formulation of fexprs.
• You think that PLs should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.

Current status

"I want to understand vau"

Apparently, youse people don't know the R^-1RK by heart yet.

Vau is just like lambda, except it doesn't evaluate its arguments, and receives the lexical environment in which it is called.

Vau's syntax is (vau operands environment . body).

Lambda's syntax is (lambda arguments . body).

((vau x e x) foo) ==> (foo)

((vau x e e) foo) ==> #[environment]

You can also destructure the operands:

((vau (x y z) e z) foo bar baz) ==> baz

And if you want to get at the actual value of an operand, you use eval, which takes a form and an environment as parameters:

(def msg "Hello world!")

((vau (x) e (eval x e)) msg) ==> "Hello world!"

Note: you can try out these expressions at the Virtua REPL.

Why fexprs, part N, or lambda only the penultimate

I now have a bit of experience with Kernel-style fexprs (short for fun expressions, not frankenprogramming expressions), and I must say I am amazed.

While it's true that one can obviously express fexprs easily in plain Scheme/LC through a little bit of encoding - an objection immediately raised by a friend - the converse is also true, as John Shutt explains. In a language with vau (the WOW! combinator), lambda is simply expressed as a fexpr that evaluates the operand tree, yielding a list of arguments, before entering the body. So it seems that neither vau nor lambda is preferable from a theoretical standpoint.

But when it comes to practical matters, IMO vau clearly wins over lambda, making it only the penultimate. Why? Take the (usually smug) Haskell weeniesprogrammers. They like to wax about how lazyness obviates the need for macros, but then they spend all day writing papers about parallelizing the Fibonacci Butt Sort using LaTeX, which is totally based on macros. (You can read more about the Fibonacci Butt Sort here on 4chan /prog/, the second best PLT site.) Not to speak of the use of cpp in the Haskell sources. CPP, FFS!!

So while macros are shunned for theoretical reasons of pureness, they pop up everywhere somebody writes a real program. That's simply a fact, and if you disagree please go back to writing your LaTeX paper about your cpp-processed Haskell program.

Now that we've established that macros are a necessity, we obviously want the best semantics for our macros. Common macros are preprocessors: they take in expressions and spit out expressions. Conceptually, and often also actually, macros are run in a separate phase from runtime, at compile-time. (See my cleverly titled post What's phase separation and when do you want it? for more information on phases.) This has two drawbacks. First, because macros are compile-time entities they don't actually exist as first-class entities at runtime. But wait, that's the smaller drawback. The second, REAL drawback is that because macros run outside the real program, processing its representation as an expression, they have no friggin' clue whatsoever about the structure of the program. This is the root of hygiene problems: what a hygienic macro system does is fake lexical scope at compile-time. This is necessary because at compile-time, the wonderful machinery of lexical scope (that it took us from 1959 to 1975 to discover, and is still rediscovered by peasantsignorami every day) doesn't exist. And this faking produces a huge cost in complexity. One example is that it necessitates a partial expansion step (R6RS, Racket) to find all definitions in a piece of code. This greatly adds complexity to a language. A second example is that if you want clean compilability, you end up with things like negative metalevels. All signs of Ptolemy's epicycles, as Tom Lord will tell you.

Hm, I went off on a tangent there. Where was I? Yes, semantics. We want macros, and we want good semantics for them. And that's what fexprs give us. It's getting late, and I have some Stoli to drink. More next time, Nostrovia!

S, M, L

Quick note: I think in a user interface, objects should have at least three different sizes, or semantic zoom levels: S(mall), M(edium), and L(arge).

In a files-and-folders GUI, S would be the icon, M would be the opened file or folder, and L would be the details/properties dialog of a folder or file, showing even more information.

In a REPL, M would be the normal size for evaluated objects. Sub-objects, e.g. member variables would be displayed as S. Inspecting an object switches it to the L setting.

This is your brain on CBPV

Rob Simmons has written an amazing new post - What does focusing tell us about language design? - on Call-by-Push-Value, an exciting new paradigm that exposes previously hidden fine structure of computation (previously).

I'm a PL dilettante, so I can't follow the theory behind CBPV but it just seems right, and the thinking and writing behind it and articles like Rob's are clear, highly insightful, and practical.

Yet another Kernel interpreter

I wrote another Kernel-ish interpreter in JavaScript: Virtua.

This time, no tail-call optimization or first-class continuations, just plain old pedestrian control flow: LOOP, CATCH, THROW, UNWIND-PROTECT (unexpectedly, this didn't make the interpreter much smaller than the one with TCO and continuations.)

Probably the only interesting thing in there is that everything is fully OOP: EVAL is a message, as is COMBINE, as is MATCH - which means every object can potentially control its own evaluation, act as a combiner, and be used as a left-hand-side pattern in matching.

Again: Kernel is nice and elegant, but the interpretetive overhead of fexprs is killer [Edit: haven't measured it, and see this]. Maybe it doesn't matter for what I want to do: script web GUIs.

Previously: The Kernel Underground.

Algebraic Data Types

Reading this incredibly insightful article The Algebra of Data, and the Calculus of Mutation finally drove home the point to me why FP folks are so in love with their Algebraic Data Types: they connect wonderfully with very old (think B.C.) mathematical ideas - that every one of us has learned in school. The question is still whether that does make them good for programming. (HT Daniel)