Thursday, June 16, 2005

ClassicJavascript

I've written up a CEKS machine semantics for the essential core of Javascript, which just for fun I'm calling ClassicJavascript. It demonstrates the strange scoping and store semantics of the language, the confusing meaning of this, and the prototype-based inheritance model. It doesn't correctly treat the primitive types like objects in quite the way it's supposed to, but that wouldn't be too hard to add. Oh, I also don't have a rule for starting up the machine, which I ought to, because it would explain the "global" object and create the initial Object and Function objects. I'll do that at some point.

I imagine you could use this to reason about a compiler that generated Javascript, if you were pretty ambitious, but mostly I just did it to help myself understand the language. It would also make it really easy to write an interpreter. A lot easier than trying to write to the spec, which is written in a combination of English prose and BASIC-like pseudocode (ouch).

If I do say so myself, this turned out to be a whole lot more concise than the 75 or so pages of the spec specifying the core semantics of the language (that's the part without any description of the standard library).

4 comments:

Jeff Palm said...

Maybe your semantics capture this, but consider this stupid accumulator:

var j = 1;
function accum() {
var n = 1;
function inc() {return j*n++;}
return inc;
}

j isn't put in inc's closure, n is, but wouldn't your MakeClosure rule put j in the closure for inc? I'm probably missing something. It's here, too.

Jeff Palm said...

I'm retarded Dave, sorry, disregard my other comment...

Felix said...

If you aren't already aware of them, there are some really neat object calculi where extension-via-protoyping and method reference is all you have. And when I say "all", its significant, because all the methods take only one argument, which is (wait for it) this. That's it, no extra arguments.

So how do I code up addition, or anything where you want to take arguments other than this? Yeah, I puzzled over that one too. Its pretty cool stuff.

(I don't know that much about it; Carl is the expert on this stuff at the moment.)

Anonymous said...

http://lists.canonical.org/pipermail/kragen-tol/2005-September/000792.html

I'm responding to the question, "So how do I code up addition, or
anything where you want to take arguments other than this?", from
http://calculist.blogspot.com/2005/06/classicjavascript.html --- with
regard to Abadi and Cardelli's object calculi.

This is explained in a slightly different notation than Abadi and
Cardelli use for their object calculus. I'm leaving out the syntactic
sugar I usually use in order to keep this explanation simple for those
who haven't read Abadi and Cardelli.

{} is an object with no methods.

self.foo = self.bar + 1 is a method whose definition is "call bar
on the same object, then add 1." Abadi and Cardelli write this as
"foo = sigma(self) self.bar + 1".

x.foo = x.bar + 1 is the same method (or, if you prefer, another
method that behaves identically.) This expression lexically binds
the name 'x' within the method definition to the "self" parameter
--- the object the method is called on.

x{ self.foo = self.bar + 1 } is an override expression; it means
"an object exactly like x, except that it has this new foo
method," which is defined as above.

I'll separate methods inside objects or override expressions with
newlines or commas.

I've also added new methods to objects in override expressions
without restraint; you can rewrite this code so that it only ever
overrides existing methods, as in Abadi and Cardelli's work,
without much effort, simply by adding useless method definitions
in objects whose descendants do this.

So here are booleans:

{
booleans.true = {
self.negated = booleans.false
self.ifTrue = { x.then = 1, x.else = 0, x.val = x.then }
self.ifFalse = self.negated.ifTrue
}
booleans.false = booleans.true {
self.negated = booleans.true
self.ifTrue = booleans.ifTrue { x.val = x.else }
}
}

If "hungry" is a variable that might be one of booleans.true or
booleans.false, we can say

hungry.ifTrue{ x.then = "eat", x.else = "don't eat" }.val

Suppose hungry is the above 'true'. This resolves to

{
self.negated = booleans.false
self.ifTrue = { x.then = 1, x.else = 0, x.val = x.then }
self.ifFalse = self.negated.ifTrue
}.ifTrue{ x.then = "eat", x.else = "don't eat" }.val

and then

{
x.then = 1, x.else = 0, x.val = x.then
}{
x.then = "eat", x.else = "don't eat"
}.val

which reduces to

{ x.then = "eat", x.else = "don't eat", x.val = x.then }.val

Which resolves to 'x.then', with 'x' being the above-constructed
object whose 'then' is defined as "eat". Supposing instead that
hungry were 'false'; instead we get

booleans.true {
self.negated = booleans.true
self.ifTrue = booleans.ifTrue { x.val = x.else }
}.ifTrue{ x.then = "eat", x.else = "don't eat" }.val

If we expand out the booleans.true here, we get

{
self.negated = booleans.false
self.ifTrue = { x.then = 1, x.else = 0, x.val = x.then }
self.ifFalse = self.negated.ifTrue
}{
self.negated = booleans.true
self.ifTrue = booleans.ifTrue { x.val = x.else }
}.ifTrue{ x.then = "eat", x.else = "don't eat" }.val

And then if we evaluate the first override expression, we get

{
self.negated = booleans.true
self.ifTrue = booleans.ifTrue { x.val = x.else }
self.ifFalse = self.negated.ifTrue
}.ifTrue{ x.then = "eat", x.else = "don't eat" }.val

since the only method from 'true' not overridden in 'false' is
ifFalse. Now we can evaluate the .ifTrue method call and get:

booleans.ifTrue { x.val = x.else }{ x.then = "eat", x.else = "don't eat" }.val

which expands out to

{
x.then = 1, x.else = 0, x.val = x.then
}{
x.val = x.else
}{
x.then = "eat", x.else = "don't eat"
}.val

We can collapse the first override and get

{
x.then = 1, x.else = 0, x.val = x.else
}{
x.then = "eat", x.else = "don't eat"
}.val

and then the second, and get

{
x.then = "eat", x.else = "don't eat", x.val = x.else
}.val

And that reduces to just 'x.else', which is defined as "don't eat".
This is exactly the same as the last reduction step for when hungry
was 'true', except that we inherited a different definition for
'x.val'.

Now, for numbers. A real implementation of this object-calculus on a
computer would use the CPU's rapid number-handling machinery rather
than implementing its own math primitives, and the method I am about
to explain is a terribly inefficient way of implementing them anyway;
its purpose is to demonstrate that the object-calculus can
theoretically perform any computable computation on its own. The
following technique is just a transliteration of the lambda-calculus's
Church numerals.

Here's an object containing numeric primitives; I assume the earlier
booleans object is available under the name 'booleans'.

{
numbers.zero = {
self.isZero = booleans.true
self.plus = numbers.sum { x.firstArgument = self }
self.succ = self {
succ.isZero = booleans.false
succ.pred = self
}
}
numbers.lessThan = {
self.firstArgument = numbers.zero
self.secondArgument = numbers.zero.succ
self.val = self.secondArgument.isZero.ifTrue {
x.then = booleans.false
x.else = self.firstArgument.isZero.ifTrue {
x.then = booleans.true
x.else = numbers.lessThan {
child.firstArgument = self.firstArgument.pred
child.secondArgument = self.secondArgument.pred
}.val
}.val
}.val
}
numbers.sum = {
self.firstArgument = numbers.zero.succ
self.secondArgument = numbers.zero.succ
self.val = self.firstArgument.isZero.ifTrue {
x.then = self.secondArgument
x.else = self {
child.firstArgument = self.firstArgument.pred
}.val.succ
}.val
}
}

The above definitions should evaluate

numbers.zero.succ.succ.succ.plus {
x.secondArgument = numbers.zero.succ.succ.succ.succ
}.val

to the same thing as numbers.zero.succ.succ.succ.succ.succ.succ.succ.
But I may have made a mistake.

So the short answer is that methods often return an object not derived
from self, but some of whose method definitions are closed over self.

As I've implied previously (in "functional programming for amateurs in
an outliner", before I read Abadi and Cardelli's book --- thank you
David Gibson!) I think this is the theoretical underpinning for
dramatically more usable and productive programming environments.

Links:

> Abadi and Cardelli's object calculus is described in the first three
pages of "A Theory of Primitive Objects" at
http://research.microsoft.com/Users/luca/Papers/PrimObj1stOrder.pdf
> "functional programming for amateurs in an outliner" is at
http://lists.canonical.org/pipermail/kragen-tol/2002-May/000713.html
> "towards a modern programming environment" is at
http://lists.canonical.org/pipermail/kragen-tol/2003-May/000745.html
> Also related is Jonathan Edwards' Subtext:
http://subtextual.org/
> And Wouter van Oortmerssen wants "abstractionless programming", the
same thing:
http://lambda-the-ultimate.org/node/view/17
> And Dynamic Aspects' "domain/object" platform seems to be a larger
idea including the same kernel:
http://www.dynamicaspects.com/