Friday, April 29, 2011

on quotation

Some über-obvious notes:

Lisp literals (booleans, numbers, strings, ...) are sometimes called self-evaluating or self-quoting objects.

This is important because it brings to mind that other objects don't evaluate to themselves: a symbol evaluates to the value of the variable it names, and a list evaluates to the result of a call.

To actually get hands on a symbol or list, we need to quote it. Literals need no quoting, they're self-quoting.

While unquoted X looks quite similar to quoted 'X, they're utterly different. X stands for read a variable from memory, while 'X stands for construct a symbol object with the name "X" (leaving interning aside).

And that's really the use-mention distinction.

Thursday, April 28, 2011

A new Cambrian explosion

Three areas that seem to be exploding are new programming languages, new databases, and new content-centric networking protocols.

But I think all of these developments will be dwarfed by the emergence of the browser as the unified display substrate and JavaScript as the new instruction set.

The last time we had a similar event was the introduction of the GUI in the 80's/90's: millions of programmers scrambled to write every imaginable application for this new system

But the GUI explosion will be peanuts compared to the browser+JS explosion! Not only are there far more programmers today, they're also all joined by the internet now. And there's ubiquitous view source. Need I say more??

Millions of programmers are scrambling right now to write every imaginable application for the browser+JS.

If you ain't emittin' HTML and JS, you're gonna miss out on this once-in-a-geological-era event!

R7RS discussion warming up

I would still appreciate pointers as to how to implement this ;-) Anyone can implement Scheme, but only half a dozen people have implemented separate compilation with hygienically introduced toplevel bindings.Andy Wingo of Guile

For example, '幺' (U+5e7a) has Numeric_Type = 'Numeric', since the character means small or young, so it can sometimes mean 1 in some specific context (for Japanese, probably the only place it means '1' is in some Mah-jong terms.) So, when I'm scanning a string and found that char-numeric? returns #t for a character, and that character happens to '幺' (U+5e7a), and then what I do? It is probably a part of other word so I should treat it as an alphabetic character. And even if I want to make use of it, I need a separate database to look up to know what number '幺' is representing.Shiro Kawai of Gauche

Taylor Campbell's blag

Taylor Campbell's blag contains many insightful posts related to programming languages, Scheme in particular.

For example, he clears up my confusion about UNWIND-PROTECT vs Continuations:
The difference [to DYNAMIC-WIND] is in the intent implied by the use
of UNWIND-PROTECT that if control cannot re-enter the protected
extent, the protector can be immediately applied when control exits
the protected extent even if no garbage collection is about
to run finalizers.

Note that one cannot in general reconcile

(1) needing to release the resource immediately after control exits
the extent that uses it, and

(2) enjoying the benefits of powerful control abstractions such as
inversion of control.

However, if (1) is relaxed to

(1') needing to release the resource immediately after control
/returns normally from/ the extent that uses it,

then one can reconcile (1') and (2) by writing

(CALL-WITH-VALUES (LAMBDA () <resource-usage>)
(LAMBDA RESULTS
<resource-release>
(APPLY VALUES RESULTS))), or simply

(BEGIN0 <resource-usage> <resource-release>)

using the common name BEGIN0 for this idiom. (In Common Lisp, this
is called PROG1.)
(And Dorai Sitaram says: UNWIND-PROTECT "cannot have a canonical, once-and-for-all specification in Scheme, making it important to allow for multiple library solutions".)

Wednesday, April 27, 2011

What's a condition system and why do you want one?

This post attempts to explain how Lisp condition systems surpass ordinary exception handling. Condition systems don't unwind the stack by default and thus allow computations to be restarted, which is a useful tool.

Exception handling
try {
throw new Exception();
catch (Exception e) {
... // handler code
}
Everybody knows what this exception handling code in Java does: the THROW searches for a CATCH clause (a handler) that catches subclasses of Exception, unwinds the stack, and calls the handler code with E bound to the exception object.

At the moment the exception is thrown, the stack looks like this:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // middle stack
  • THROW new Exception()
There's an outside stack that doesn't concern us. The middle stack is the stack between the TRY/CATCH and the THROW, which is actually empty in this example, but usually contains a whole lotta function calling going on.

Before the handler is called, the stack is unwound:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // middle stack
  • THROW new Exception()
When the handler is called, the stack looks like this:
  • ... // outside stack
  • TRY/CATCH(Exception e)
  • ... // handler code
Condition systems

Condition systems in the Lisp family are based on the fundamental insight that calling a handler can be decoupled from unwinding the stack.

Imagine the following:
try {
throw new Exception();
} handle(Exception e) {
... // handler code
}
We've added a new keyword to Java, HANDLE. HANDLE is just like CATCH, except that the stack is not unwound when an Exception is thrown.

With this new keyword, the stack looks like this when the handler is called:
  • ... // outside stack
  • TRY/HANDLE(Exception e)
  • ... // middle stack
  • THROW new Exception()
  • ... // handler code
The handler runs inside the THROW statement (Common Lisp would say, during the dynamic extent of the THROW).

For many exceptions it makes sense to simply unwind the stack, like ordinary exception handling does. But for some exceptions, we gain a lot of power from the non-unwinding way condition systems enable.

Restarts

One of the most interesting aspects of not automatically unwinding the stack when an exception occurs is that the we can restart the computation that raised an exception.

Let's imagine two primitive API functions: GETVAL and SETVAL read and write a VAL variable.
Object val = null;
Object getVal() { return val; }
void setVal(Object newVal) { val = newVal; }
Now we want to add the contract that GETVAL should never return null. When VAL is NULL, and GETVAL is called then an exception is raised:
Object getVal() {
if (val == null) throw new NoValException();
else return val;
}
A user of GETVAL may install a handler like this:
try {
getVal();
} handle (NoValException e) { // note use of HANDLE, not CATCH
... // handler code
}
When GETVAL() is called and VAL is null, an exception is thrown, our handler gets called, and the stack looks like this:
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • THROW new NoValException()
  • ... // handler code
As you can see, our handler for NoValException runs, and the exception "isn't over yet", because the stack hasn't been unwound.

Thanks to the non-unwinding nature of condition systems, an application may decide to simply use a default value, when GETVAL is called and VAL is null.

We do this using restarts, which are simply an idiomatic use of non-unwinding exceptions:(1)

We rewrite GETVAL to provide a restart for using a value:
Object getVal() {
try {
if (val == null) throw new NoValException();
else return val;
} catch (UseValRestart r) {
return r.getVal();
}
}
GETVAL can be restarted by throwing a USEVALRESTART whose value will be returned by GETVAL. (Note that we use CATCH and not HANDLE to install the handler for the restart.)

In the application:
try {
getVal();
} handle (NoValException e) {
throw new UseValRestart("the default value");
}
(The USEVALRESTART is simply a condition/exception that can be constructed with a value as argument, and offers a single method GETVAL to read that value.)

Now, when GETVAL() is called and VAL is null, the stack looks like this:
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • TRY/CATCH(UseValRestart r) [1]
  • THROW new NoValException()
  • THROW new UseValRestart("the default value") [2]
The restart at [2] bubbles up, and is returned by the TRY/CATCH for the restart at [1], which means that GETVAL returns "the default value":
  • ... // outside stack
  • TRY/HANDLE(NoValException e)
  • getVal()
  • TRY/CATCH(UseValRestart r)
  • THROW new NoValException()
  • THROW new UseValRestart("the default value")
  • return r.getVal(); // "the default value"

A simple extension would be to offer a restart for letting the user interactively choose a value:
Object getVal() {
try {
if (val == null) throw new NoValException();
else return val;
} catch (UseValRestart r) {
return r.getVal();
} catch (LetUserChooseValRestart r) {
return showValDialog();
}
}
This assumes a function SHOWVALDIALOG that interactively asks the user for a value, and returns that value. The application can now decide to use a default value or let the user choose a value.

Summary

The ability to restart a computation is gained by decoupling calling a handler from unwinding the stack.

We have introduced a new keyword HANDLE, that's like CATCH, but doesn't unwind the stack (HANDLE and CATCH are analogous, but not equal, to Common Lisp's handler-bind and handler-case, respectively).

HANDLE is used to act from inside the THROW statement. We have used this to implement restarts, a stylized way to use exceptions.

I hope this post makes clear the difference between ordinary exception handling, and Lisp condition systems, all of which feature restarts in one form or another.

Further reading:
Footnotes:

(1) This is inspired by Dylan. Common Lisp actually treats conditions and restarts separately.

Tuesday, April 26, 2011

Lisp hype danger



Yesterday, "Lisp was dead".

Today, Lispers are asked to "reproduce their pre-AI Winter achievements" and there's talk of "Lisp geniuses".

I sense danger in the hype cycle!

Hypercode

I just saw this use of HTML lists and tables for syntax, and I liked it. I think that HTML is the future of all UIs, thus also of PLs.

The possibilities of using HTML instead of plain text are huge, and I wish that the syntax-obsessed would focus on HTML instead of plain text.

Monday, April 25, 2011

Original Dylan Manual

Thanks to the Wayback Machine, I just discovered the original 1992 Dylan manual: Dylan (TM) -- An object-oriented dynamic language.

Back then, Dylan still had S-expression syntax, making its CL and Scheme heritage much more obvious.

If you want to see dynamic object-oriented PL design (as opposed to trial and error, plucking out of thin air, or other popular approaches) this is one of the few places to look.

(Here's another URL for the manual.)

Thursday, April 21, 2011

EdgeLisp progress

My hobby Lisp->JS compiler, EdgeLisp (formerly known as CyberLisp) just passed a major milestone: using multiple dispatch, a numeric tower (provided by Danny Yoo's js-numbers), and inline JavaScript, I'm able to write the > generic function as follows:
(defgeneric > (a b))
(defmethod > ((a number) (b number))
#{ jsnums.greaterThan(~a, ~b) #})
Checking it out at the REPL:
(> 200000000000000000000000000000000000000000 100000000000000000000000000000000000000000)
#t
Yay!

EdgeLisp is FAR from usable by anyone but me, but at this point I just had to blog about it. You can check it out here if you want.

Disclaimer: docs are outdated, and the project is in rapid flux.

The more I work on this, the more I respect anybody who's produced a usable PL. The sheer amount of work is unbelievable. :)

Props also to Douglas Crockford's json.js and Chris Double's jsparse.