Digging into Arc In 24 Macros Or Less

OK, so Paul Graham has a subtle way of getting me sucked into his much-anticipated language: he includes a tempting "hello, world" web application one-liner at the end of the tutorial that gives me a very (this is for you, Todd) pedestrian error message, and suddenly I'm knee deep in his world of macros trying to figure out what could possibly go wrong. Quick and dirty indeed.

So, what we're doing in this post is tracing through some of the Arc source code, finding the answer to why it doesn't work in Windows, and providing a patch. The source is from the arc0 distribution released Tuesday, January 29, 2008. This post is meant to be read in conjunction with the language description from the tutorial.

The one-liner in question is the first line in this snippet from the tutorial:

arc> (defop hello req (pr "hello world"))
#
arc> (asv)
ready to serve port 8080

Cool, that would be nice to define a function-like form that takes a web request and has its standard output get interpreted as an HTTP response.

However, I get this on executing (asv) on Windows:

arc> (asv)
The syntax of the command is incorrect.
The syntax of the command is incorrect.
Error: "open-output-file: cannot open output file: \"c:\\apps\\arc0\\arc/hpw\" (The system cannot find the path specified.; errno=3)"

This seems to happen only on Windows. On Ubuntu Linux the server runs, though there's another error for me in serving the page.

I was just curious to look at the line of code that seemed to be Unix-specific, or understand the source of this error.

For the record, and since the documentation is just a shade sketchy, this is how I'm installing and setting things up:

1. Install MzScheme version 352 as recommended
2. Put MzScheme's bin directory on the path
3. From the arc0 directory, run the command mzscheme -m -f as.scm, as recommended

Debugging asv, the Arc Server

The definition for asv is in app.arc:

(def asv ((o port 8080))
  (load-userinfo)
  (serve port))

The (o port 8080) means asv takes an optional argument port with a default value of 8080. Brevity is certainly a hallmark of the Arc dialect.

Let's dig into load-userinfo, since is first and sounds like it would be using the file system:

(def load-userinfo ()
  (= hpasswords*   (safe-load-table hpwfile*)
     admins*       (map string (errsafe (readfile adminfile*)))
     cookie->user* (safe-load-table cookfile*))
  (maptable (fn (k v) (= (user->cookie* v) k))
            cookie->user*))

The safe-load-table of hpwfile* sounds like a likely place to look when getting error involving an hpw directory.

The definition of hpwfile* at the top of app.arc is "arc/hpw", so we are evaluating (safe-load-table "arc/hpw").

Evaluating (safe-load-table "arc/hpw")

safe-load-table is in arc.arc and defined as

(def safe-load-table (filename)
  (or (errsafe (load-table filename))
      (table)))

Here we get the or function which evaluates arguments until one is true and returns that. Remembering that filename is bound to "arc/hpw", we need to look at (errsafe (load-table "arc/hpw").

Evaluating (errsafe (load-table "arc/how"))

The definition of errsafe shows we have arrived at our first macro:

(mac errsafe (expr)
  `(on-err (fn (c) nil)
           (fn () ,expr)))

The backtick (`) means quote the expression.

The comma preceding expr means to evaluate expr, but I wasn't sure of the order of evaluation, so I played with it a little bit:

arc> (mac m (expr)
  `(do (prn "m started")
       ,expr))
*** redefining m
#3(tagged mac #)
arc> (m  5)
m started
5
arc> (m (do (prn "evaluating expr") 5))
m started
evaluating expr
5

This clearly shows the evaluation happening at the point where expr is encountered in the macro. If expr appears twice in the macro, it would be evaluated twice:

arc> (mac m2 (expr)
  `(do (prn "m2 started")
       ,expr
       (prn "m2 discarded first expr")
       ,expr))
#3(tagged mac #)
arc> (m2 5)
m2 started
m2 discarded first expr
5
arc> (m2 (do (prn "evaluating expr") 5))
m2 started
evaluating expr
m2 discarded first expr
evaluating expr
5

At this point I have to stop and thank PG for reacquainting me with Lisp macros. It's been... a long while since I've used these.

Getting back to the thread of execution, the expression (errsafe (load-table "arc/hpw") means this:

(on-err (fn (c) nil)
        (fn () (load-table "arc/hpw"))))

Where we now know that (load-table "arc/hpw") may or may not be evaluated based on what the wrapping entity, on-err, does.

Definition of on-err

We find on-err defined in ac.scm. Since that's a Scheme file, not an arc source, that makes it essentially a language primitive defined thus:

; If an err occurs in an on-err expr, no val is returned and code
; after it doesn't get executed.  Not quite what I had in mind.

(define (on-err errfn f)
((call-with-current-continuation
  (lambda (k)
    (lambda ()
      (with-handlers ((exn:fail? (lambda (c)
                                   (k (lambda () (errfn c))))))
                     (f)))))))
(xdef 'on-err on-err)

First, the easy part: xdef is a macro call that puts this Scheme code into the initial environment of Arc. Second, let's interpret the sometimes formidable call-with-current-continuation.

Presuming a bit the behavior of MzScheme's with-handlers, we start by asking to evaluate the thunk f, which was the second argument to on-err, the (load-table "arc/hpw" in our case. In case evaluating f raises any Scheme exceptions, by invoking the current continuation k we return from on-err saying that it evaluated to whatever (errfn c) evaluates to, where errfn is the first argument to on-err and c is a representation of the error condition itself.

Example of on-err

We can see an example usage of on-err at the top-level of the Arc prompt earlier in ac.scm:

(define (tl2)
(display "arc> ")
(on-err (lambda (c)
         (set! last-condition* c)
         (display "Error: ")
         (write (exn-message c))
         (newline)
         (tl2))
 (lambda ()
   (let ((expr (read)))
     (if (eqv? expr ':a)
         'done
         (let ((val (arc-eval expr)))
           (write (ac-denil val))
           (namespace-set-variable-value! '_that val)
           (namespace-set-variable-value! '_thatexpr expr)
           (newline)
           (tl2)))))))

This defines what to do at the top level if an error is encountered.

Now that We Know How on-err Works...

We were trying to understand what (safe-load-table "arc/hpw") does, thinking it would explain why we get an error related to a missing hpw directory only in Windows.

That led us to the definition of safe-load-table as

(def safe-load-table (filename)
  (or (errsafe (load-table filename))
      (table)))

which led us to the errsafe macro, which in our case expanded to

(on-err (fn (c) nil)
        (fn () (load-table "arc/hpw"))))

We now can interpret how to evaluate it. We now know the second argument to on-err is evaluated, so we do need to know what (load-table "arc/hpw") does. If that causes an exception in the underlying MzScheme implementation, the error handler (fn (c) nil) will be invoked, and the whole expression will therefore return nil. That would be treated as false by the or in the safe-load-table above. In that event the second argument, (table), would be evaluated, and I take it mean return a default-constructed table.

But we need to look at load-table. We should wonder if the special with-handlers expression in on-err's definition is missing an exception that is being thrown by an underlying Scheme implementation.

Definition of load-table

We find load-table in arc.arc:

(def load-table (file (o eof))
  (w/infile i file (read-table i eof)))

There is an optional argument eof but no value is given in the call site, so apparently it defaults to nil:

arc> (def f (x (o y)) (list x y))
#
arc> (f 1)
(1 nil)
arc> (f 1 2)
(1 2)

The w/infile macro definition is also in arc.arc, defined with a few other macros sharing a macro helper named expander and another macro after:

(mac after (x . ys)
`(protect (fn () ,x) (fn () ,@ys)))

(let expander
  (fn (f var name body)
    `(let ,var (,f ,name)
       (after (do ,@body) (close ,var))))

(mac w/infile (var name . body)
 (expander 'infile var name body))

(mac w/outfile (var name . body)
 (expander 'outfile var name body))

(mac w/instring (var str . body)
 (expander 'instring var str body))
)

The . body notation, as I had to remind myself, lets body stand for the list of whatever arguments remain from the call site. For example:

> (define (f x y . z) (list x y z))
> (f 1 2)
(1 2 ())
> (f 1 2 3)
(1 2 (3))

At any rate, at this point since I'm trying to get the post out, I'm not going to pretend I understand the evaluation order of how and when the expander definition gets substituted into the macro body.

I tried for a while without success to understand why the variable i doesn't get evaluated too early. The fact that expander is an ordinary function and not a macro leads me to believe that its arguments, which certainly include the undefined i, should be evaluated before being passed to expander so it can create its backquoted let form.

So instead, we'll assume that what appears to be the intent is the case, that (w/infile i file (read-table i eof)) is expanded to this:

(expander 'infile i file ((read-table i eof)))

and then this:

(let i (infile file)
  (after (do (read-table i eof)) (close i)))

and finally this, when the symbols file and eof are evaluated:

(let i (infile "arc/hpw")
  (after (do (read-table i nil)) (close i)))

The function infile is the next candidate.

Is infile the end?

As it happens, infile in Arc is directly tied to MzScheme's open-input-file, defined in ac.scm:

(xdef 'infile  open-input-file)

So, we try this in MzScheme directly, and reproduce the error:

$ mzscheme
Welcome to MzScheme version 352, Copyright (c) 2004-2006 PLT Scheme Inc.
> (define i (open-input-file "arc/hpw"))
open-input-file: cannot open input file: "c:\Apps\arc0\arc/hpw" (The system cannot find the path specified.; errno=3)

This is all very interesting, but as it turns out this is not the source of the errors.

If you evaluate (load-userinfo) in the top level, you don't get an error message.

Getting a Clue

So I erred a little bit on the depth-first side here. After some simple debugging you find that (load-userinfo) runs fine.

What doesn't run fine is the (serve port) call, the code of which is in srv.arc:

(def serve ((o port 8080))
  (nil! quitsrv*)
  (ensure-install)
  (let s (open-socket port) 
    (prn "ready to serve port " port) ; (flushout)
    (= currsock* s)
    (after (while (no quitsrv*) 
             (if breaksrv* 
                 (handle-request s)
                 (errsafe (handle-request s))))
           (close s)
           (prn "quit server"))))

And what doesn't work here is ensure-install:

(def ensure-install ()
  (ensure-dir arcdir*)
  (ensure-dir logdir*)
  (when (empty hpasswords*)
    (create-acct "frug" "frug")
    (writefile1 'frug adminfile*))
  (load-userinfo))

And what doesn't work here is ensure-dir, defined in arc.arc:

(def ensure-dir (path)
  (unless (dir-exists path)
    (system (string "mkdir " path))))

And finally our search is at an end.

Arc is shelling out to perform the directory create. MzScheme does provide the directory-exists? function portably (it detected my E:/ drive), but why is Arc executing mkdir? MzScheme defines a make-directory function.

Patching Arc

This has not been a total loss. Now we know enough to fix Arc so it works in Windows.

In ac.scm, at line 873 after the definition of dir-exists, define mkdir:

 (xdef 'mkdir (lambda (path)
                     (make-directory path)))

In arc.arc, at line 1202, replace the system call with the call to our new mkdir function:

      (mkdir path)))

And finally we have enough to retry the Hello, World one-liner:

arc> (defop hello req (pr "hello world"))
#
arc> (asv)
ready to serve port 8080
srv thread took too long
user break

 === context ===
c:\apps\mzscheme\collects\mzlib\process.ss:149:2: system*/exit-code
c:\apps\mzscheme\collects\mzlib\process.ss:190:2: system*
c:\apps\arc0\ac.scm:808:20
 date
 memodate
 srvlog
 gs899
 handle-request-thread

OK, so it timed out after 5 seconds.

Conclusion

This Arc release actually got me moving from thinking about Lisp/Scheme to actually using it, and appreciating macros. I do admit that I enjoy the brevity of the keywords and design of the syntactic forms, and if that's all Arc ever is it's still value-added.

Releasing a version before things were polished may be a good thing for Lisp as a whole, and the project in general. I recall the initial Java releases had just enough of a standard library to get people's attention immediately, and when you looked closely at it you could see how it could be built out. I think that combination may prove irresistible for hackers, who have always been Paul's intended audience.

Which Lisa?

A little get-to-know-you game you can play with friends this weekend:



Would you rather buy a jar of luscious apple chutney for $6?

Or a working Apple Lisa for $500 (plus $120 shipping)?

And what does that say about you?


(While it lasts, here's the link.)

How Many Cycles Can You Burn Doing This

What's the sweet spot between development time and performance in extracting the 24 from this XML string:

<eltname formatid="24" someotherattribute="xyz" ... />

The eltname varies, and while the formatid is usually in this front spot, it isn't guaranteed.

Presented with this problem, I settled on this pseudocode:
1. Try a regular expression pattern match
2. If the match succeeds, use the value it extracted
3. Otherwise run a SAX parser that looks up the desired attribute in the first startElement call and then aborts the parse.

Using SAX is clearly indicated for this over DOM, mainly because we don't need the parser to scan the whole input. With SAX we can abort the parse ourselves (apparently the way to do this is to intentionally throw an exception) in the startElement callback, after the opening element tag has been read. This may read more attributes than we need, but typically (for me anyway) most of the input is not in the start tag.

I liked this approach, since it looked like the presumably faster pattern match would usually work, and even if it didn't there was a reasonably performing option for getting the right answer. But once I started thinking about performance, I had to see what we would actually get. And by the way, I was working with Java on this problem.

I was horrified to find that the SAX parsing, using Xerces2, was taking from 0.750ms up to a millisecond to run on a 3.2GHz machine. The pattern match, while much better, was not super great, even though it was a compiled pattern returned by Pattern.compile.

So at this point, I just had to see what would happen if I hand-rolled a regular expression parser. It took a while, and increases the technical risk, but it seemed manageable. Here are the results I got:

<eltname formatid="24" someotherattribute="xyz" ... />

1. Hand-rolled parser: 0.9 microseconds
2. Compiled reg-exp match: 15 microseconds
3. Xerces2 SAX parser: 760 microseconds

This is for running each method on a single test string (typical for my intended purpose) of about 350 characters long, to extract the 24 from this form, on a machine with a 3.2GHz CPU (that's a clock period of around 0.3 nanoseconds).

I consulted the Xerces Performance FAQ list and found Xerces Performance Clue Number One:

Avoid creating a new parser each time you parse; reuse parser instances. A pool of reusable parser instances might be a good idea if you have multiple threads parsing at the same time.

Yes. Do that, what the blockquote said. Heeding this advice made the SAX parse align a little better with the other methods:

1. Hand-rolled parser: 0.9 microseconds
2. Compiled reg-exp match: 15 microseconds
3. Xerces2 SAX parser with parser reuse: 52 microseconds

I peeped a little into just what takes 710 microseconds to execute new SAXParser() and it's a landscape littered with rattling across classloaders, checking for Xerces configuration files on the file system, checking the last modified time of the configuration file in case it's changed, almost like a makefile. Very, very flexible, and pretty heavy.

Overall, it looked like the compiled reg-exp match is acceptable, and if I do find this code getting called more often than I expected, I can switch to the hand-rolled parser.

Minor Python Oddity: Rename and Copy in Different Modules?

As part of my learn-as-I-go strategy to picking up new languages, I tried a Python script for a task I've been frequently doing.

I'd written a short Python script last week that did something more aggressive and was pleased with how compact it was (once I rewrote my loops with list comprehensions), as well as snappy fast.

This script was dirt simple, it needs to ensure a a file is copied/moved to two other locations (the original file should. Normally I would have used a Bourne shell script:

src="/path/foo"
dest1="/path2"
dest2="/path3"
cp $src $dest1
mv $src $dest2

Maybe a slight improvement to check if it's needed:

src="/path/foo"
dest1="/path2"
dest2="/path3"
if [ -r $src ] ; then
  cp $src $dest1
  mv $src $dest2
fi

Anyway, so the result looks pretty similar:

import sys
import os
import shutil

src="/path/foo"
dest1="/path2"
dest2="/path3"

if os.access(src, os.R_OK):
    shutil.copy(src, dest1)
    os.renames(src, dest2)

It seemed odd that copy and move are in different modules: the os module has rename, but in order to get copy I need the shutil module. I was annoyed because it took me a while to locate the copy documentation. Maybe I'm just rationalizing my annoyance, but aren't these modules are little overzealously partitioned? And isn't shutil just a really silly name?

What is the logic to this that puts file stat, list directory, change directory, make directory, remove directory, file name, create symlink, and just about every other straightforward directory/file operation in one module, but copying in another?

Ah well, I recognize this as just a bump in learning a different library system. I wonder if the reason I'm annoyed is from my ambiguity intolerance: even though the difference is minor practically (I can easily learn to import shutil) I don't understand the reason behind the structure, and that bothers me. Ambiguity tolerance is an interesting phenomenon and I was taught in (human) linguistics courses that a lack of tolerance for ambiguity can be a hindrance to language acquisition. I seriously consider the same may hold true for adapting new programming languages and tools: aside from other considerations, if people can't understand and navigate the structure and logic behind your system, and they have a measure of ambiguity intolerance, they may quickly brush it off. Just a thought.

Gradual Typing

There was a nice exchange on the TYPES list a couple days ago announcing a new paper "Gradual Typing with Unification-based Inference" (GTUBI hereafter) by Jeremy Siek & Manish Vachharajani at Colorado.edu. It drew remarks from Tim Sweeney, the only game programmer I know who gives invited POPL talks, and Phil Wadler.

While I was aware of rumblings to add type inference to dynamic languages like Ruby with enhancements to RDT/Aptana and Python with Pysco, I had not been following the academic developments. Aside from its contributions of adding type inference to gradual typing (as well as discussing some approaches that do not work), this paper opened my eyes to the notion of gradual typing making its way through the theoretical programming language crowd.

Which Time to Run: The Raging Debate

Run-time or Compile-time? That is the question. I've been watching Raganwald chronicle this debate from time and time, and it's at least productive in finding out what worth each approach has. I'm still back on the compile-time side, if you didn't notice. GTUBI (the paper we're talking about, remember?) has this characterization:

Dynamic languages such as Perl, Ruby, Python, and Javascript are popular for scripting and web applications where rapid development and prototyping is prized above other features. The problem with dynamic languages is that they forego the benefits of static typing: there is no machine checked documentation, execution is less efficient, and errors are caught only at runtime, often after deployment.
--Siek & Vachharajani, GTUBI

While I can't claim to appreciate dynamic typing, I do acknowledge that with all those Javascript errors flooding my browser error console have somehow not stopped me from basically doing what I need to do on the web.

What Makes it Gradual

I always like to know the origin of a name. In this case, gradual refers to the idea that in a gradually typed language, you can gradually add type annotations to what is otherwise a dynamically typed program.

Dynamic Typing is Not Typeless

The static type folks like to point out that dynamic languages are not typeless -- they're just languages with one type. In GTUBI, they write this type as ?; in Wadler's paper it's written Dyn. Rightly or wrongly, I typically think of this type as "expression," influenced by the LISP notion of everything as an S-expression.

What's Essential in Gradual Typing

One essential element of a dynamic language is the business of type conversions or coercions: since x+3.14159 isn't statically compiled to know which + operator to use (int+int, real+real, string+string), the types are examined at runtime (when the + function is applied) and applicable conversions take place. Conversions in dynamic languages are thus usually implicit, but you could have explicit conversions (the Ruby to_s method). GTUBI states

Allowing implicit conversions (e.g. from ? to int) that may fail is the distinguishing feature of gradual typing and gives it the flavor of dynamic typing.
--Siek & Vachharajani, GTUBI

Type Consistency

The main idea, say the GTUBI authors in their review of Gradual Typing, is to replace type equality in the type checker, with a relation called type consistency written as ~. Their examples:

int ~ int   (int is consistent with int)
int !~ bool (int is not consistent with bool)
? ~ int     (the unknown type is consistent with int)
int ~ ?     (int is consistent with the unknown type)
(int -> ?) ~ (? -> int)
            (function from int to the unknown type
             is consistent with 
             a function from the unknown type to int)
(int -> ?) ~ (? -> bool)
            (function from int to the unknown type
             is consistent with 
             a function from the unknown type to bool)
(int -> ?) !~ (bool -> ?)
            (these two function aren't consistent,
             as their arguments aren't consistent)
(int -> int) !~ (? -> bool)
            (these two function aren't consistent,
             as their return types aren't consistent)

Update: fixed last two examples to state !~
They then give the rules for the ~ relation, noting it is reflexive and symmetric but not transitive.

Conclusion

The Gradual Typing system is interesting, and I would probably give a language using it a whirl. One thing I don't think it addresses is the eval function present in the well-known dynamic languages that allow symbols to be redefined dynamically. That appears to me to kill any hope of the usual static type checking assurances.

Presenting Step-by-Step Evaluations

For the past few posts, such as Pairs and Y, I've been wanting to present my pen and paper lambda calculus derivations with the aid of a program. Rather than encoding an evaluator to reduce a lambda calculus expression to normal form, I wanted to imitate the pen and paper process:

1. Write an expression
2. Identify how you want to transform it, and justify
3. Write the transformed expression and repeat as needed

The idea is to provide a set of tools so that you can write sequences like

line1 = expr
display(line1, "Beta reduce by replacing body of Y combinator with argument")
line2 = betaReduce(line1)
display(line2,"Call this form Ybound for future reference.")

Do I have a set of tree modifying functions like betaReduce, or abstract everything into a do-it-all function, like reduceOnce? That would show which subexpression needs to be evaluated next, and emits the reduced expression. But I'd like to add human comments on a line by line basis. I'd like to show currently uninteresting subexpressions in abbreviated form, and control that on a line by line basis.

The thing is you can't just have "betaReduce(expr)", you'd like to give an expression and somehow identify which subexpression to beta-reduce. Every lambda calculus expression may have more than one application ready to be reduced, and as the proof writer you'd like to pick which to work on.

Another issue is the symbol/definition issue. I've noticed is sometimes in my pen and paper proofs, I'd like to write a symbol like 1, Y, or fixtup for clarity, and expand to its full lambda calculus expression at need. This especially happens with Y and its forms which keep recreating themselves :).

My pipe dream vision of this is something pretty graphical, where each expression has some buttons (show free variables, alpha convert, beta reduce), and there's a notes section below expressions where you can comment on. The undo/redo stack then is the serialized form of your derivation and can be rendered to a nice little movie.

Pairs and Y

While preparing Subtleties of Instance Variable Initialization and Recursive Records and Instance Variable Initialization, I wanted to work out what actually happens in lambda calculus to recursive records. I decided to settle for recursive pairs as an equivalent but more practical endeavor.

Pairs get constructed:

pair = λx.λy.λz.z x y

And destructed:

fst = λp.p(λx.λy.x)
snd = λp.p(λx.λy.y)

How does this pair constructor work? Give it the first and second elements, and it returns a "visitor" function, if you will:

p1 = pair 1 2 = λz. z 1 2

Now p1 is a function (of course) taking a visitor z. The function z is written so as to get both values of p1 to do with whatever it needs. The destructors are example visitors:

  fst p1                  Replace fst with its definition
= (λp.p(λx.λy.x)) p1      Beta reduce, replacing p with p1 in λ body
= p1(λx.λy.x)             Replace p1 with its definition
= (λz. z 1 2)(λx.λy.x)    Beta reduce, replacing z with p1 in λ body
= (λx.λy.x) 1 2           Beta reduce, replacing x with 1 in λ body
= (λy.1) 2                Beta reduce is trivial since y never occurs
= 1

Armed with that, and the definition of the Y combinator below, can you show what happens to this recursive tuple:

Given Y = λf. (λx.f(λy.x x y)) (λx.f(λy.x x y)),
what happens to

Y (λthis. pair 1 (+ (fst this) 1))
?

If you don't know, try whipping up these encodings (including Church numerals for the ints) in your favorite language and evaluating the example.

Recursive Records and Instance Variable Initialization

In Subtleties of Instance Variable Initialization we looked at the curious difficulty in initializing instance variables defined in terms of each other. If in reading that you felt some flicker of recognition when we talked about call-by-value versus call-by-name, you may be on the right track to connecting this all together. In this post we'll trace this difficulty all the way down to the divergence of the fixed point operator in non-function fields of recursive records in call-by-value languages. Are you up for it? Then you're the CS equivalent of a hard-core spelunker. Let's go, you're responsible for your own safety.

Review of the Problem

The problem is how a language implementer provides instance variable initialization, giving an initialization expression when a field is declared, when the expressions can refer to other instance variables of the same object. How do you sort out the "bootstrap" dependence graph, or do you? If not, what's your algorithm for the constructor? It turns out this is more or less the same question as how to encode the fixed point operator on records.

This Javascript program illustrates the use case:

// Construct an object with two different orderings depending on its argument
function DynamicDependence(state)
{
 return {
   x : (state? 1 : this.y-1),
   y : (state? this.x+1 : 2)
 }
}
var dd = new DynamicDependence(true)
document.write('x='+dd.x+' y='+dd.y+'<br/>')
var dd2 = new DynamicDependence(false)
document.write('x='+dd2.x+' y='+dd2.y+'<br/>')

You'll get this output:

x=1 y=NaN
x=NaN y=2

A note about terminology. The {x : expr, ...} is Javascript syntax for an "associative array", but that is basically identical to the notion of a "record" in a lot of the academic literature on programming languages. When we say record here, we mean something close to the Javascript meaning, which generalizes to the way objects can be viewed in every object-oriented language I've seen. Whether the fields are ordered are not, syntactic details about how to access fields, and some other aspects, are unimportant to this discussion.

Possible Solutions

Of course with the Javascript example, or in Ruby or most languages, the programmer could control the ordering by writing the constructor with explicit assignments (this.x=1; this.y=this.x+1), but that goes outside the problem being addressed. If we allow instance variable initialization at all, what happens with references to other instance variables? How are they treated? As an example solution, in Javascript, the algorithm appears to be as follows:

1. Allocate (associative array) object, call it "this".
2. Evaluate initialization expressions, store them aside.
   References to fields in this are undefined.
3. Bind the evaluated expressions to the "this."
   After this point, references to instance variables work with the given initial values.

The Java constructor algorithm appears to be something more like this:

1. Allocate object, call it "this".
2. Initialize each field to its native type
   (Object initialized to null, int to 0, boolean to false, etc.).
3. For each declared field, in order they're declared:
   Evaluate the initializer expression and assign it

As we saw with the BreakJava example in the previous post, forward references are prevented by the compiler, so typical programs that compiled won't have forward references, but it's possible there still are some via method calls, and in that case the reference will get the value from step 2, the default value for its core Java type.

These are some ways to deal with the problem, but let's dig a little deeper and see where the problem comes from in the first place.

This is the Crux of the Problem

In all these examples, notice the problem comes about because of dependences between instance variables. Did you ever wonder how you can even express that dependence?

It all has to do with the magical this variable (also known as self in Smalltalk et. al). And this is none other than the implicit argument to the function you pass to the fixed point operator (known in connection with its most famous embodiment, the Y Combinator).

Yep - every class definition in every object language out there is implicitly wrapped in an expression, something like:
fix (λ this . { ERROR=1, WARN=2, DEBUG=3, level=this.DEBUG })

"What the...?" You're thinking. "I thought the fixed point operator was only for functions." The snarky answer to that is "everything is a function" (see Church encoding). But really, from the fixed point on functions to records is not a far leap.

How to Think About Recursive Records

The way to think about the fixed point operator on a record (object)
is similar to how we think about it for functions.

The way we think about it for functions,
is that you start with a recursive function:

function fact(n) {
 return (n<2)? 1 : fact(n-1)
}

but you
1. make it anonymous
2. wrap it in another function, and
3. replace the recursive call with the name of the outer function's argument:

function(self) {
 function(n) { return (n<2)? 1 : self(n-1) }
}

(I've used self instead of this since I'm giving Javascript code and want to avoid confusion.)

The fix operator will take your function and return a function that has the effect of the original recursive definition.

The way to think about the fixed point operator on a record (object)
is that we write a recursive record
(referring to the record itself as this or self)
but we
1. make it anonymous,
2. wrap it in another function, and
3. replace the "recursive" reference
with the name of the outer function's argument:

newobj = function(self) { return { DEBUG : 3, level : self.DEBUG } }

We pass it to fix, and it returns the a record having the same effect as the desired recursive definition:

{ DEBUG : 3, level : this.DEBUG }

The funny thing about this: what stops the recursion?

The Problem with Recursive Records

As alluded to last time, we run into problems initializing instance variables for two reasons: (1) when there are dependent expressions ({x=1, y=this.x+1}) and (2) when the language uses the near-universal call-by-value evaluation strategy. Now we can clearly see that the dependence comes from the recursive reference, i.e. the reference to this.

When you think about recursive functions, you typically don't write them with direct recursion:

function killit() {
 return killit()
}

That would typically be stupid. (There are cases where you want infinite recursion, as with server loops, but those generally call an operating system function that effectively does the busy waiting in hardware.) Instead, the recursive call is nearly always inside an if statement:

function loop(n) {
 if (n<1)
   return true
 else
   return loop(n-1)
}

And guess what -- in order to be effective, if statements in every call-by-value language are in effect special functions that use call-by-name evaluation. In other words, the if "function" doesn't evaluate both the if case and the else case (every normal function evaluates all its arguments before executing the function body), but only the one that it "needs" to evaluate, based on the test expression.

But with recursive records, I think what we're effectively asking with cases like
{ x : 1, y : this.x } is to eagerly evaluate the value of this in the act of computing what this is supposed to be, just the same as killit above wants the value of killit. We say the derivation of these fixed points diverges, or fails to converge to the fixed point.

Fixed Point for Records

In Ila, I had to actually implement the fix operator for records to support the mutual recursion between record fields at all: the typical case where methods can call each other. And as with Javascript, Java, Ruby and others, initializing instance variables is done at your own risk, and happens to work if the fix operator evaluates fields in the proper order. The approach taken there was this:

public static Object fix__rec =
 // fix : (T->T) -> T
 new Ila_Lambda_OO()
 {
   public Object applyOO(Object f)
   {
     return new FixedRecord((Ila_Lambda_OO)f);
   }
 };

where the FixedRecord constructor was like this:

public FixedRecord(LAO__OZ f)
{
 super();
 m_creationFn = f;
 Ila_Record temp = (Ila_Record)f.applyOO(this);
 this.copyFields(temp);
}

The two key lines are the f.applyOO(this) and the this.copyFields(temp). We evaluate the given function, passing it the Java object reference for the new object which will be recursive by the time we get done with it. The given function returns a record, where recursive definitions have been bound to the recursive record we will return. The problem is that this record returned from the function is not itself the recursive record. We then simply copy each field in the record back to the recursive record:

public Ila_Record copyFields(Ila_Record src)
{
 Enumeration en = src.keys();
 while(en.hasMoreElements())
 {
   Object key = en.nextElement();
   this.put(key,src.get(key));
 }
 return this;
}

---

While I've seen this area discussed in academic circles (e.g. in connection with Didier Rémy and OCAML), for some reason I've never seen this topic addressed in more mainstream programming language forums.

About the Author

JFKBits is written by Joel F. Klein, who has worn many hats: day jobs in embedded systems and object-relational database frameworks for web applications; being a Teaching Assistant for computer architecture courses; studying under Uday Reddy at the University of Illinois; and always looking for better (or worse, depending on which is better) ways to program.

Disclosure: Mr. Klein is currently employed by Wolfram Research, makers of Mathematica, though he does not speak for Wolfram Research.

Subtleties of Instance Variable Initialization

One of the more mundane corners of programming with objects is the constructor, in particular the initializing of instance variables. In this post we'll find that behind this pedestrian feature are some subtle questions to be answered by implementers.

Consider the following Java class:

public class R
{
 public int x = 1;
 public int y = x+1;
}

Pretty clear that x is 1 and y is 2, right? What if you switch the order of the declarations?

public class R
{
 public int y = x+1;
 public int x = 1;
}

This one won't compile. Pretty clear that the intent is the same, x=1 and y=2, but Java won't allow forward references to data members when initializing. Why?

The short answer is because Java evaluates the instance initialization in a certain order. But why is that?

Before answering that, let's compare this example with a couple of dynamic languages. First, Javascript:

// Construct an object with two different orderings depending on its argument
function DynamicDependence(state)
{
 return {
    x : (state? 1 : this.y-1),
    y : (state? this.x+1 : 2)
 }
}
var dd = new DynamicDependence(true)
document.write('x='+dd.x+' y='+dd.y+'<br/>')
var dd2 = new DynamicDependence(false)
document.write('x='+dd2.x+' y='+dd2.y+'<br/>')

You'll get this output:

x=1 y=NaN
x=NaN y=2

Javascript is cool with this in the sense that we get no errors. But we do get NaN, not just for the first example (x=1, then y=x+1) but for both orderings.

Can you begin to spot some subtleties in the way objects are constructed? There's something going on, and it happens when there's a dependence between the instance variables. Let's look at Ruby:

class DynamicDependence
 attr_accessor :x, :y
 def initialize()
  @x = $state? 1 : @y-1
  @y = $state? @x+1 : 2
 end
 def to_s()
  "{x=#{@x}, y=#{@y}}\n"
 end
end

$state = true
dd = DynamicDependence.new
puts dd
# Emits {x=1,y=2}

$state = false
dd2 = DynamicDependence.new
puts dd2
# DynamicDependence.rb:4:in `initialize': undefined method `-' for nil:NilClass (NoMethodError)

In Ruby, the first ordering works, as it did for Java, and the second ordering fails.

The nice thing, for clarity's sake here, about Ruby is that it doesn't offer the option of "implicit initialization" that Java does -- you spell out all initialization in a sequence determined by you in the constructor. The convenient initializers in Java and Javascript have to be done some algorithmic way, which is nice unless the algorithm isn't in the order you particularly wanted. When spelled out as it is in Ruby, we can see that the question of what happens when initializing these members depends on how the "uninitialized" instance variable is viewed by the language. Notice I didn't try this example in C++.

Let's now return to the question of why order of initialization matters. After all, you and I can figure out that when stating "mathematically" that x=1 and y=x+1 it doesn't matter what order you specify these, it means that x=1 and y=2.

What if we wrote the original example this way instead:

public class R
{
 public int x() {return 1;}
 public int y() {return x()+1;}
}

Suddenly we get the behavior we want, and we can switch the order of declaration. We can declare the y method first, and we get no problems when evaluating x or y.

The trick to all of this is that Java, Javascript, Ruby and virtually every other language out there uses call-by-value, or eager, evaluation of the expressions supplied to the instance initialization. The reason an order needs to be imposed is that in order to supply a value for a field (instance variable), the language needs to evaluate the expression supplied, and it needs to do it at construction time, not later when it's actually used.

Even initializing fields in a certain order is not enough to prohibit problems. For example, we can fool Java's forward declaration checker:

public class BreakJava implements BreakJavaInterface
{
 public int x = wreck(this);
 // Halting Problem =>
 // compiler can't in general tell wreck(this) refers to y
 // so this call is allowed even though it will cause problems
 public int y = 2;
 public int gety() {return y;}

 private static int wreck(BreakJavaInterface b)
 {
   return 2 / b.gety(); // div-by-zero exception at runtime
 }

 public static void main(String[] args)
 {
   BreakJava bj = new BreakJava(); // div-by-zero
 }
}

interface BreakJavaInterface
{
 abstract int gety();
}

Voila, the foolish programmer was able to hang himself yet again.

I know, you've been thinking "who cares" about these funny examples, right? You care if you're designing or implementing an object-based language (with call-by-value evaluation), because you need to think what happens when initializing the instance variables. Maybe you say "fine, I'm implementing Ruby, where I don't need to support an instance initialization syntax, and the usual variable assignment work gets me the desired behavior for free." Fine, the decision is up to you, but there is a decision to be made, because these subtle differences between languages didn't occur by accident. Even so, I can give you a perfectly natural, non-contrived example of instance initialization with dependences:

// Dirt simple Javascript logger
function Logger(name)
{
return {
   ERROR : 1,
   WARN : 2,
   DEBUG : 3,
   TRACE : 4,
   id : name,
   level : this.DEBUG,
   log : function(lvl,msg) {
      if(lvl > this.level)
         return
      document.write(this.id+' '+this.level+' '+msg)
   }
}
}
var logger = new Logger('example')

We would love to define these constants ERROR, WARN, etc. that go with the class, and we'd also like to initialize this.level to DEBUG. But in this case, level is going to be undefined even though it looks like it could work.

There's some deeper magic going on here that I hope to explore next time. In the meantime, ask yourself what rules you would like there to be for instance variable (non-method) initialization, and how you would implement them.