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).

## Thursday, June 16, 2005

Subscribe to:
Post Comments (Atom)

## 4 comments:

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.

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

If you aren't already aware of them, there are some really neat object calculi where extension-via-protoyping and method reference is

allyou 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.)

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/

Post a Comment