In January 2007 I posted an article on my web site titled “Regular Expression Matching Can Be Simple And Fast.” I intended this to be the first of three; the second would explain how to do submatching using automata, and the third would explain how to make a really fast DFA. These were inspired by my work on Google Code Search.

Today, the fourth article in my three-part series is available, accompanied by source code (as usual). This one describes how Code Search worked.

stanleylieber posted a photo:

caerwyn posted a photo:

caerwyn posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

code.google.com/p/plan9front/source/detail?r=18198808ffaa...

thanks, cinap!

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

well, almost.

stanleylieber posted a photo:

stanleylieber posted a photo:

fixed: code.google.com/p/plan9front/source/detail?r=6283b22c37cf

{-# OPTIONS_GHC -XTypeOperators #-}
{- Recursive types in haskell. -}
module Main where
import Prelude hiding ( Maybe, Just, Nothing, maybe, sum, succ, map )

---- Pairs
data Pair a b = Pair a b

pair :: (a -> b -> c) -> Pair a b -> c
pair f (Pair a b) = f a b

instance Functor (Pair a) where
    fmap f (Pair a b) = Pair a (f b)


---- Optional type
data Maybe a = Nothing | Just a

maybe :: c -> (a -> c) -> Maybe a -> c
maybe f _ Nothing = f
maybe _ g (Just x) = g x

instance Functor Maybe where
    fmap f = maybe Nothing (Just . f)


---- Recursive types
newtype Mu a = In { mu :: (a (Mu a)) }

cata :: Functor f => (f a -> a) -> Mu f -> a
cata f = f . fmap (cata f) . mu


---- recursive peano numbers
--type Peano = Mu Maybe

zero = In $ Nothing
succ n = In $ Just n

mkNat 0 = In $ Nothing
mkNat n | n == 0 = zero
        | n > 0  = succ $ mkNat (n - 1)
        | n < 0  = error "bad natural"

unNat = cata $ maybe 0 (+ 1)

add x = cata $ maybe x succ
mul x = cata $ maybe zero $ add x


---- Composition of functors
newtype (g :. f) a = O { unO :: g (f a) }

instance (Functor f, Functor g) => Functor (g :. f) where
    fmap f (O x) = O . (fmap . fmap) f $ x


---- proto recursive lists
type ListX a = Maybe :. Pair a

listx :: c -> (a -> b -> c) -> ListX a b -> c
listx f g = maybe f (pair g) . unO 


---- recursive lists (ie. of ints)
--type ListI = Mu (ListX Int)

nil = In . O $ Nothing
cons x xs = In . O . Just $ Pair x xs

mkList [] = nil
mkList (x:xs) = cons x $ mkList xs

unList = cata $ listx [] (:)

sum = cata $ listx 0 (+)
map f = cata $ listx [] (\a b -> f a : b)


---- test it out...
main = do
    let p m x = putStrLn (m ++ ": " ++ show x)
    --
    p "nat" $ unNat $ mkNat 5
    p "add" $ unNat $ add (mkNat 5) (mkNat 3)
    p "mul" $ unNat $ mul (mkNat 5) (mkNat 3)
    --
    p "list" $ unList $ mkList [1,2,3,4,5]
    p "sum" $ sum $ mkList [1,2,3,4,5]
    p "map" $ map (*2) $ mkList [1,2,3,4,5]

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

Halfway There

void memcpy(char *p, char *q, int n)
{
    if(n > 0) {
        p[0] = q[0];
        memcpy(p+1, q+1, n-1);
    }
}

   // alloc(p[0..n]), init(q[0..n]), n >= 0
1: void memcpy(char *p, char *q, int n)
2: {
       // alloc(p[0..n]), init(q[0..n]), n >= 0
3:     if(n > 0) {
           // alloc(p[0..n]), init(q[0..n]), n > 0
4:         p[0] = q[0]; // safe
5:         memcpy(p+1, q+1, n-1);
6:     } else {
7:     }
8: }

   // alloc(p[0..n]), init(q[0..n]), n >= 0
1: void memcpy(char *p, char *q, int n)
2: {
       // alloc(p[0..n]), init(q[0..n]), n >= 0
3:     if(n > 0) {
           // alloc(p[0..n]), init(q[0..n]), n > 0
4:         p[0] = q[0];
           // p[0] = q[0], init(p[0]), 
           // alloc(p[0..n]), init(q[0..n]), n > 0
5:         memcpy(p+1, q+1, n-1);
6:     } else {
           // n = 0, p[0..n] = q[0..n]
7:     }
       // p[0..n] = q[0..n]?
8: }

   // alloc(p[0..n]), init(q[0..n]), n >= 0
1: void memcpy(char *p, char *q, int n)
2: {
       // alloc(p[0..n]), init(q[0..n]), n >= 0
3:     if(n > 0) {
           // alloc(p[0..n]), init(q[0..n]), n > 0
4:         p[0] = q[0];
           // p[0] = q[0], init(p[0]), 
           // alloc((p+1)[0..n-1]), init((q+1)[0..n-1]), 
           // (n-1) >= 0
5:         memcpy(p+1, q+1, n-1);
           // p[0] = q[0], init(p[0]),
           // p[1..n] = q[1..n], init(p[1..n])
6:     } else {
           // n = 0, init(p[0..n]), p[0..n] = q[0..n]
7:     }
       // init(p[0..n]), p[0..n] = q[0..n]
8: }

   // alloc(p[0..n]), init(q[0..n]), n >= 0
1: void memcpy(char *p, char *q, int n)
2: {
       // alloc(p[0..n]), init(q[0..n]), n >= 0
3:     if(n > 0) {
4:         p[0] = q[0]; // safe since n > 0
5:         memcpy(p+1, q+1, n-1); // precond met
           // p[0] = q[0] and p[1..n] = q[1..n]
6:     }
       // init(p[0..n]), p[0..n] = q[0..n]
7: }

What's Next?

// find the last dot, copy everything up to the dot.
p = strrchr(name, '.');
if(p && idx < sizeof(namebuf) - 1) {
    int idx = p - name;
    strncpy(namebuf, name, idx);
    namebuf[idx] = 0;
}

strncpy(namebuf, name, sizeof namebuf-1);
namebuf[sizeof namebuf - 1] = 0;

The memcpy function

1: void memcpy(char *p, char *q, int n)
2: {
3:     while(n--)
4:         *p++ = *q++;
5: }

Some notation

Safety

1:  void memcpy(char *p, char *q, int n)
2:  {
3:      while(1) {
4:          int oldn = n;
5:          n--;
6:          if(!oldn)
7:              break;
8:          char c = *q;
9:          *p = c;
10:         p++;
11:         q++;
12:     }
13: }

    { n >= 0, alloc(p[0..n]), init(q[0..n]) }
1:  void memcpy(char *p, char *q, int n)
2:  {   
        { n >= 0, alloc(p[0..n]), init(q[0..n]) }
3:      while(1) {
4:          int oldn = n;
5:          n--;
6:          if(!oldn)
7:              break;
8:          char c = *q;
9:          *p = c;
10:         p++;
11:         q++;
12:     }
13: }

    { n >= 0, alloc(p[0..n]), init(q[0..n]) }
1:  void memcpy(char *p, char *q, int n)
2:  {
        { n >= 0, alloc(p[0..n]), init(q[0..n]) }
3:      while(1) {
            { n >= 0, alloc(p[0..n]), init(q[0..n]) }?
4:          int oldn = n;
5:          n--;
6:          if(!oldn)
7:              break;
8:          char c = *q;
9:          *p = c;
10:         p++;
11:         q++;
12:     }
13: }

 
            { n >= 0, alloc(p[0..n]), init(q[0..n]) }?
4:          int oldn = n;
            { oldn >= 0, n >= 0, 
              alloc(p[0..n]), init(q[0..n]) }?
5:          n--;
            { oldn >= 0, n >= -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }?
6:          if(!oldn)
                { oldn == 0, n = -1, 
                  alloc(p[0..n+1]), init(q[0..n+1]) }?
7:              break;

 
7:              break;
            { oldn != 0, n > -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }?
8:          char c = *q;
            { oldn != 0, n > -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }?
9:          *p = c;
            { oldn != 0, n > -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }?
10:         p++;
            { oldn != 0, n > -1,
              alloc(p[-1..n]), init(q[0..n+1]) }?
11:         q++;
            { oldn != 0, n > -1,
              alloc(p[-1..n]), init(q[-1..n]) }?

    { n >= 0, alloc(p[0..n]), init(q[0..n]) }
1:  void memcpy(char *p, char *q, int n)
2:  {   
        { n >= 0, alloc(p[0..n]), init(q[0..n]) }
3:      while(1) {
            { n >= 0, alloc(p[0..n]), init(q[0..n]) }
4:          int oldn = n;
            { oldn >= 0, n >= 0, 
              alloc(p[0..n]), init(q[0..n]) }
5:          n--;   // no overflow(n-1) by n >=0
            { oldn >= 0, n >= -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }
6:          if(!oldn)
                { oldn == 0, n == -1 }
7:              break;
            { oldn != 0, n > -1,
              alloc(p[0..n+1]), init(q[0..n+1]) }
8:          char c = *q; // read q[0] valid by
                         // init(q[0..n+1]) and n >= 0
            { oldn != 0, n > -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }
9:          *p = c; // write p[0] valid by 
                    // alloc(p[0..n+1]) and n >= 0
             { oldn != 0, n > -1, 
              alloc(p[0..n+1]), init(q[0..n+1]) }
10:         p++;          // can overflow(p+1) of n == 0!
            { oldn != 0, n > -1, 
              alloc(p[-1..n]), init(q[0..n+1]) }
11:         q++;          // can overflow(q+1) if n == 0!
            { n >= 0, alloc(p[0..n]), init(q[0..n]) }
12:     }
        { n == -1 }
13: }

Correctness

    { n >= 0, alloc(p[0..n]), init(q[0..n]) }
1:  void memcpy(char *p, char *q, int n)
2:  {
        { d = 0, d+n = n_arg, n >= 0, 
          init(p[0..0]), p[0..0] = q[0..0] }
3:      while(1) {
            { d+n=n_arg, n >= 0, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
4:          int oldn = n;
            { d+n=n_arg, oldn >= 0, n >= 0, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
5:          n--;
            { d+n+1 = n_arg, oldn >= 0, n >= -1, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
6:          if(!oldn)
                { oldn = 0, n = -1, d=n_arg, 
                  init(p[-d..0]), p[-d..0] = q[-d..0] }
7:              break;
            { d+n+1 = n_arg, oldn != 0, n > -1, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
8:          char c = *q;
            { d+n+1 = n_arg, n >= 0, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
9:          *p = c;       // now p[0] = q[0]
            { d+n+1 = n_arg, n >= 0, 
              init(p[-d..1], p[-d..1] = q[-d..1] }
10:         p++;          // now d is one larger
            { d+n = n_arg, n >=0, 
              init(p[-d..0], p[-d..0] = q[-d+1..1] }
11:         q++;
            { d+n = n_arg, n >= 0, 
              init(p[-d..0]), p[-d..0] = q[-d..0] }
12:     }
        { n = -1, init(p[-n_arg..0], 
          p[-n_arg..0] = q[-n_arg..0] }
13: }

Can't we simplify?

   // precond: alloc(p[0..n]), init(q[0..n]), n >= 0
1: void memcpy(char *p, char *q, int n)
2: {
       //  invariant: alloc(p[-d..n']), init(q[-d..n']),
       //     p[-d..0] = q[-d..0], n' >= 0
       // where n' is n before the postdecrement
       // and d = p-p_arg, d = q-q_arg. 
3:     while(n--) {
           // n' > 0
4:         *p++ = *q++;
5:     }
       // d = n_arg, p[-d..0] = q[-d..]
       // so p_arg[0..n_arg] = q_arg[0..n]
6: }

What's a proof worth?

Try your own

What Next?

stanleylieber posted a photo:

stanleylieber posted a photo:

This article walks through building a trivial example of lex source
code into C, and then compiling the generated C source code into
object files and an executable in a different directory. The point is
to demonstrate using dodep to generate and customize build scripts
and list dependencies, and credo to execute the build process.

Lines which start with ; are shell commands; lines without are output.
Key commands are displayed in red text.

Starting state

We start with the files lorem, src/dcr.l, src/header.c, src/lex.h,
and an empty obj directory. Each line of lorem ends with a
carriage return (not usually printed), which we want to strip.
header.c is an ordinary C source file to compile and link.
lex.h gives us a local header to look for.

Generate source code

; cd src
; echo flex > dcr.c.lex.env

We first go into the src directory, and set the lex shell variable to flex,
to specify which lexer to use. To demonstrate an unusual feature,
that would be valid across ports to different operating systems,¹
we’ll capture it with this command.
¹ Inferno and Plan 9 store variables by name in the directory /env,
different for each process. This gives it a definite advantage in
capturing dependencies on variables, since we can just list the name
of the shell-variable file as a dependency.

src/dcr.c.lex.env:1: flex

This setting applies (is transformed into a shell variable) when credo
processes the target dcr.c, if dcr.c depends on /env/lex.

; dodep (c lex l c) dcr.c
credo dcr.c

We ask dodep to generate a shell script and list of dependencies with
this command. The content of these files comes from a library,
indexed by the four parameters given before the name of the file we
want to build. In this case, we want to look in the “c” namespace,
at the command “lex”, to translate an “l” file to a “c” file.

The generated dependency list includes the name of the lex source file,
and references to the variables lex and lflags.

src/dcr.c.dep:1: 0 dcr.l
src/dcr.c.dep:2: 0 /env/lex
src/dcr.c.dep:3: 0 /env/lflags

Credo passes the name of its target, the C source file, to the shell script,
which prints the name of the C source file if it was able to create it.

src/dcr.c.do:1: #!/dis/sh
src/dcr.c.do:2: c = $1
src/dcr.c.do:3: (sum l) = `{grep '\.l$' $c^.dep}
src/dcr.c.do:4:
src/dcr.c.do:5: if {no $lex} {lex = lex}
src/dcr.c.do:6:
src/dcr.c.do:7: if {
src/dcr.c.do:8: flag x +
src/dcr.c.do:9: os -T $lex $lflags $l
src/dcr.c.do:10: mv lex.yy.c $c
src/dcr.c.do:11: } {
src/dcr.c.do:12: echo $c
src/dcr.c.do:13: }

The hosted-Inferno command os calls host-OS commands. Under Cygwin,
it calls Cygwin or Windows commands.

Dodep finally prints a credo command to build the requested target.

; credo dcr.c
credo dcr.l
credo dcr.c
os -T flex dcr.l
mv lex.yy.c dcr.c
dcr.c

Credo builds all its non-/env dependencies in parallel. Once these
are complete, it determines whether the checksum of each file on which
it depends is different than the checksum stored for that file the
last time credo built this target.

This credo command creates a build-avoidance marker file dcr.l.redont,
which tells further runs of credo that the file dcr.l does not need
any processing, so exit early. It calls the host’s flex program,
on the path set when the Inferno environment started, to create the
target file dcr.c.

It updates the check sums in the file dcr.c.dep, to reflect content at
the time of compilation. This means that each target has its own view
of its dependencies, and any change to any file on which it depends,
or a change to the list of files on which it depends, prompts the
target to rebuild.

src/dcr.c.dep:1: 79f9925952d9cfb5a58270c0e2b67691 dcr.l
src/dcr.c.dep:2: 897a779351421523cadbafccdce22efe /env/lex
src/dcr.c.dep:3: 0 /env/lflags

It creates these checksum files to detect any changes to the target’s
dependencies or build script.

src/dcr.c.dep.sum:1: c33129421847b7d897d4e244caf1b8c0 dcr.c.dep

src/dcr.c.do.sum:1: 71d94d651922bd5ff5b543bba52f47d0 dcr.c.do

It also checksums the target file itself. If credo finds, the next
time it runs, that the current checksum of the target does not match,
then it assumes that the target was changed by hand, and will not
overwrite it.

src/dcr.c.sum:1: 2fed3667f390fd80993e090a7eb92c75 dcr.c

Compile objects and executable

We now have all the source, so we go to the object-file and executable
directory, and ask dodep to provide do and dep files to build dcr.exe.
From the “c”-language toolset, we use “cc” to compile an “o”bject file
into an “exe”cutable.

; cd ../obj
; dodep (c cc o exe) dcr.exe
credo dcr.exe

This time the dodep command created two *.do files, dcr.exe.dep.do and
dcr.exe.do, instead of a do and dep file for the target dcr.exe.

obj/dcr.exe.dep.do:1: #!/dis/sh
obj/dcr.exe.dep.do:2: dep = $1
obj/dcr.exe.dep.do:3: exe = `{echo $dep | sed 's,\.dep,,'}
obj/dcr.exe.dep.do:4: (stem ext o) = `{crext o $exe}
obj/dcr.exe.dep.do:5:
obj/dcr.exe.dep.do:6: adddep $exe /env/ars /env/cc /env/cflags /env/ldflags /env/objs
obj/dcr.exe.dep.do:7: adddep $exe $o
obj/dcr.exe.dep.do:8: adddep $exe `{/lib/do/c/coneed $o}

dcr.exe.dep.do creates the dependency list dcr.exe.dep for the target
dcr.exe by adding a set of credo-specific (ars and objs) and standard
(cc, cflags, and ldflags) shell variables; the primary object file,
named for the executable; and any other object files which the primary
one needs. The tool coneed does this last bit of analysis by compiling
the primary object file, looking for unresolved symbols in available
source code, compiling the source code to make sure, and printing the
set of matching object files.

obj/dcr.exe.do:1: #!/dis/sh
obj/dcr.exe.do:2: exe = $1
obj/dcr.exe.do:3: if {no $cc} {cc = cc}
obj/dcr.exe.do:4: if {
obj/dcr.exe.do:5: flag x +
obj/dcr.exe.do:6: os -T $cc $cflags -o $exe $objs $ars $ldflags
obj/dcr.exe.do:7: } {
obj/dcr.exe.do:8: echo os -T ./$exe
obj/dcr.exe.do:9: }

To gather enough information to compile the executable, credo relays
information from dependencies back to calling targets through *.relay
files, which are shell scripts that set the environment for calling targets.

Finally, to start the build process, we locate the source code,
record which compilation tools to use, and again call credo.

; srcdir = ../src/
; echo cpp-3 > default.cpp.env
; echo -I../src/ > default.cppflags.env
; echo gcc-3 > default.cc.env
; credo dcr.exe
credo dcr.exe.dep
os -T gcc-3 -I../src/ -c ../src/dcr.c
os -T gcc-3 -I../src/ -c ../src/header.c
credo dcr.o.dep
credo dcr.o
credo header.o.dep
credo header.o
credo dcr.exe
os -T gcc-3 -o dcr.exe dcr.o header.o
os -T ./dcr.exe

Credo first runs dcr.exe.dep.do to find and store the dependencies of
dcr.exe in dcr.exe.dep. dcr.exe.dep is an implicit dependency of dcr.exe,
so credo runs its *.do script automatically.

obj/dcr.exe.dep:1: 0 /env/ars
obj/dcr.exe.dep:2: 131eb9ab2f6a65b34e0158de1b321e3c /env/cc
obj/dcr.exe.dep:3: 0 /env/cflags
obj/dcr.exe.dep:4: 0 /env/ldflags
obj/dcr.exe.dep:5: 84a1a3c306e006dd723bebe9df29ee6c /env/objs
obj/dcr.exe.dep:6: 3f0d90c1c7483ad1805080cf9e48d050 dcr.o
obj/dcr.exe.dep:7: 1db618b791dc87ac0bd5504f69434273 header.o

Coneed uses $srcdir to find dcr.c, and the setting of cppflags in
default.cppflags.env to find lex.h. Once coneed compiles dcr.o,
it finds the unresolved symbol for the header function, finds a
definition of header() in header.c, and compiles header.o to verify
that it defines the symbol. Coneed finds no other unresolved symbols
supplied by other source code in $srcdir (c.f. printf), so it stops.
Coneed uses “dodep (c cc c o)” to compile the source code in $srcdir
into object files in the current directory (obj). This generates
*.o.dep.do and *.o.do for each source file: those for dcr are shown,
the ones for header are identical.

obj/dcr.o.dep.do:1: #!/dis/sh
obj/dcr.o.dep.do:2: dep = $1
obj/dcr.o.dep.do:3: o = `{echo $dep | sed 's,\.dep,,'}
obj/dcr.o.dep.do:4: (stem ext c) = `{crext c $srcdir^$o}
obj/dcr.o.dep.do:5:
obj/dcr.o.dep.do:6: adddep $o /env/cc /env/cflags /env/cppflags
obj/dcr.o.dep.do:7: adddep $o $c
obj/dcr.o.dep.do:8: adddep $o `{/lib/do/c/findh $c}

obj/dcr.o.do:1: #!/dis/sh
obj/dcr.o.do:2: o = $1
obj/dcr.o.do:3: (sum c) = `{grep '\.c$' $o^.dep}
obj/dcr.o.do:4:
obj/dcr.o.do:5: if {no $cc} {cc = cc}
obj/dcr.o.do:6:
obj/dcr.o.do:7: if {
obj/dcr.o.do:8: flag x +
obj/dcr.o.do:9: os -T $cc $cflags $cppflags -c $c
obj/dcr.o.do:10: } {
obj/dcr.o.do:11: echo 'objs = $objs '^$o > $o^.relay
obj/dcr.o.do:12: }

Before credo runs dcr.o.do it runs dcr.o.dep.do to generate dcr.o.dep
(header.o likewise). To find the paths to C header files it calls findh,
which gathers header-file #includes from the C source files,
and searches for them in local and system directories using cppflags
and the search list printed by $cpp -v.

obj/dcr.o.dep:1: 131eb9ab2f6a65b34e0158de1b321e3c /env/cc
obj/dcr.o.dep:2: 0 /env/cflags
obj/dcr.o.dep:3: 9134215aef7b4657beb5c4bb7a20d4a1 /env/cppflags
obj/dcr.o.dep:4: 2fed3667f390fd80993e090a7eb92c75 ../src/dcr.c
obj/dcr.o.dep:5: feea1fa232f248baa7a7d07743ee86c4 ../src/lex.h
obj/dcr.o.dep:6: fb584676de41ee148c938983b2338f5b /n/C/cygwin/usr/include/stdio.h
obj/dcr.o.dep:7: f6409b1008743b1866d4ad8e53f925cc /n/C/cygwin/usr/include/string.h
obj/dcr.o.dep:8: 468b1dd86fef03b044dceea020579940 /n/C/cygwin/usr/include/errno.h
obj/dcr.o.dep:9: 4e6678324ba6b69666eba8376069c950 /n/C/cygwin/usr/include/stdlib.h
obj/dcr.o.dep:10: c7575313e03e7c18f8c84a5e13c01118 /n/C/cygwin/usr/include/inttypes.h
obj/dcr.o.dep:11: a8fd5fa102b8f74d1b96c6c345f0e22d /n/C/cygwin/usr/include/unistd.h

obj/header.o.dep:1: 131eb9ab2f6a65b34e0158de1b321e3c /env/cc
obj/header.o.dep:2: 0 /env/cflags
obj/header.o.dep:3: 9134215aef7b4657beb5c4bb7a20d4a1 /env/cppflags
obj/header.o.dep:4: ecd87752a211e69078e6bc37afbb561b ../src/header.c
obj/header.o.dep:5: feea1fa232f248baa7a7d07743ee86c4 ../src/lex.h
obj/header.o.dep:6: fb584676de41ee148c938983b2338f5b /n/C/cygwin/usr/include/stdio.h

At this point credo has the dependencies for dcr.exe, so it works
through them, calling the *.relay files—generated by the object files’
do scripts—to gather object names in $objs.

obj/dcr.o.relay:1: objs = $objs dcr.o

obj/header.o.relay:1: objs = $objs header.o

There’s not much to do since coneed already compiled the object files,
so it links them, and prints an os command to run the executable,
since Inferno can’t directly run a Cygwin executable.

Clean up

To clean up, we remove generated files in the src and obj directories.

; rm -f *.redoing *.redont *.renew *.reold *.sum

This removes all the temporary state files created by credo.
Once this is done credo will rebuild from scratch, and reconstruct
each target’s view of its dependencies.

; rm -f `{lsdo | sed 's,^c?redo ,,'}

This removes all the targets created by do scripts. The lsdo command
(called by credo with no targets) prints credo commands for all the
credo targets in the current directory. For example:

; cd src; credo
credo dcr.c

; cd obj; credo
credo dcr.exe
credo dcr.exe.dep
credo dcr.o
credo dcr.o.dep
credo header.o
credo header.o.dep

Once the targets are removed, credo will unconditionally generate them.

; rm -f *.do *.dep *.relay

This removes all the instructions credo uses to build files.
These may usually be regenerated by dodep, adddep (which adds
to the given target’s dependency list the given files), and
rmdep (which removes the given files).

A single library script is provided to remove the state, target,
and dodep files.

; rm -f *.env

This removes default and per-target environment settings.

Once we remove these sets of files, the directories contain only the
files present in their starting state.

Floating point to decimal conversions have a reputation for being difficult. At heart, they're really very simple and straightforward. To prove it, I'll explain a working implementation. It only formats positive numbers, but expanding it to negative numbers, zero, infinities and NaNs would be very easy.

An IEEE 64-bit binary floating point number is an integer v in the range [2⁵², 2⁵³) times a power of two: f = v × 2^e. Constraining the fractional part of the unpacked float64 to the range [2⁵², 2⁵³) makes the representation unique. We could have used any range that spans a multiplicative factor of two, but that range is the first one in which all the values are integers.

In Go, math.Frexp unpacks a float64 into f = fr × 2^exp where fr is in the range [½, 1). (C's frexp does too.) Converting to our integer representation is easy:

fr, exp := math.Frexp(f)
v := int64(fr * (1<<53))
e := exp - 53

To convert the integer to decimal, we'll use strconv.Itoa64 out of laziness; you know how to write the direct code.

buf := make([]byte, 1000)
n := copy(buf, strconv.Itoa64(v))

The allocation of buf reserves space for 1000 digits. In general 1/2^e requires about 0.7e non-zero decimal digits to write in full. For a float64, the smallest positive number is 1/2¹⁰⁷⁴, so 1000 digits is plenty. The second line sets n to the number of bytes copied in from the string representation of the (integer) v. Throughout, n will be the number of digits in buf. Note that we're working with ASCII decimal digits '0' to '9', not bytes 0-9.

Now we've got the decimal for v stored in buf. Since f = v × 2^e, all that remains is to multiply or divide buf by 2 the appropriate number of times (e or -e times).

Here's the loop to handle positive e:

for ; e > 0; e-- {
    δ := 0
    if buf[0] >= '5' {
        δ = 1
    }
    x := byte(0)
    for i := n-1; i >= 0; i-- {
        x += 2*(buf[i] - '0')
        x, buf[i+δ] = x/10, x%10 + '0'
    }
    if δ == 1 {
        buf[0] = '1'
        n++
    }
}
dp := n

Each iteration of the inner loop overwrites buf with twice buf. To start, the code determines whether there will be a new digit (δ = 1), which happens when the leading digit is at least 5. Then it runs up the number from right to left, just as you learned in grade school, multiplying each digit by two and using x to carry the result. The digit buf[i] moves into buf[i+δ]. At the end, if the code needs to insert an extra digit, it does. Run e times.

After the loop finishes, we record in dp the current location of the decimal point. Since buf is still an integer (it started as an integer and we've only doubled things), the decimal point is just past all the digits.

Of course, e might have started out negative, in which case we've done nothing and still need to halve buf e times:

for ; e < 0; e++ {
    if buf[n-1]%2 != 0 {
        buf[n] = '0'
        n++
    }
    δ, x := 0, byte(0)
    if buf[0] < '2' {
        δ, x = 1, buf[0] - '0'
        n--
        dp--
    }
    for i := 0; i < n; i++ {
        x = x*10 + buf[i+δ] - '0'
        buf[i], x = x/2 + '0', x%2
    }
}

Dividing by two needs an extra digit if the last digit is odd, to store the final half; in that case we add a 0 to buf so that we'll have room to store a completely precise answer.

After adding the 0, we can set up for the division itself. If the first digit is less than 2, it's going to become a zero; in the interest of avoiding leading zeros we use an initial partial value x and move digits up (δ = 1) during the division. The multiplication ran from right to left copying from buf[i] to buf[i+δ]. The division runs left to right copying from buf[i+δ] to buf[i].

Now buf[0:n] has all the non-zero digits in the exact decimal representation of our f, and dp records where to put the decimal point. We could stop now, but we might as well implement correct rounding while we're here.

The interesting case is when we have more digits than requested (n > ndigit). To make the decision, just like in grade school, we look at the first digit being removed. If it's less than 5, we round down by truncating. If it's greater than 5, we round up by incrementing what's left after truncation. If it's equal to 5, we have to look at the rest of the digits being dropped. If any of the rest of the digits are nonzero, then rounding up is more accurate. Otherwise we're right on the line. In grade school I was taught to handle this case by rounding up: 0.5 rounds to 1. That's a simple rule to teach, but breaking this tie by rounding to the nearest even digit has better numerical properties, because it rounds up and down equally often, and it is the usual rule employed in real calculations.

This all results in the thunderclap rounding condition:

buf[prec] > '5' ||
buf[prec] == '5' && (nonzero(buf[prec+1:n]) || buf[prec-1]%2 == 1)

You can see why children are taught buf[prec] >= '5' instead.

Anyway, if we have to increment after the truncation, we're still working in decimal, so we have to handle carrying incremented 9s ourselves:

i := prec-1
for i >= 0 && buf[i] == '9' {
    buf[i] = '0'
    i--
}
if i >= 0 {
    buf[i]++
} else {
    buf[0] = '1'
    dp++
}

The loop handles the 9s. The if increments what's left, or, if we turned the whole string into zeros, it simulates inserting a 1 at the beginning by changing the first digit to a 1 and moving the decimal place.

Having done that and set n = prec, we can piece together the actual number:

return fmt.Sprintf("%c.%se%+d", buf[0], buf[1:n], dp-1)

That prints the first digit, then a decimal point, then the rest of the digits, and finally the e±N suffix. The exponent must adjust the number by dp−1 because we are printing all but the first digit after the decimal point.

That's all there is to it. To print f = v × 2^e you write v in decimal, multiply or divide the decimal by 2 the right number of times, and print what you're left holding.

The Plan 9 C library and the Go library both use variants of the approach above. On my laptop, the code above does 100,000 conversions per second, which is plenty for most uses, and the code is easy to understand.

Why are some converters more complicated than this? Because you can make them a little faster. On my laptop, glibc's sprintf(buf, "%.50e", M_PI) is about 15 times faster than an equivalent print using the code above, because the implementation of sprintf uses much more sophisticated mathematics to speed the conversion.

If you have a stomach for pages of equations, there are many interesting papers that discuss how to do this conversion and its inverse more quickly:

• William Clinger, “How to Read Floating Point Numbers Accurately”, PLDI 1990.
• Guy L. Steele Jr. and Jon L. White, “How to Print Floating Point Numbers Accurately”, PLDI 1990.
• David M. Gay, “Correctly Rounded Binary-Decimal and Decimal-Binary Conversions”, AT&T Bell Laboratories, 1990.
• Vern Paxson, “A Program for Testing IEEE Decimal-Binary Conversion”, May 1991.
• Robert Burger and R. Kent Dybvig, “Printing Floating-Point Numbers Quickly and Accurately”, SIGPLAN 1996.
• Florian Loitsch, “Printing Floating-Numbers Quickly and Accurately With Integers”, PLDI 2010.

Just remember: The conversion is easy. The optimizations are hard.

Code

The full program is available in this Gist or you can try it using the Go playground.

package main

import (
    "fmt"
    "math"
    "strconv"
)

func ftoa(f float64, prec int) string {
    fr, exp := math.Frexp(f)
    v := int64(fr * (1<<53))
    e := exp - 53
    
    buf := make([]byte, 1000)
    n := copy(buf, strconv.Itoa64(v))

    for ; e > 0; e-- {
        δ := 0
        if buf[0] >= '5' {
            δ = 1
        }
        x := byte(0)
        for i := n-1; i >= 0; i-- {
            x += 2*(buf[i] - '0')
            x, buf[i+δ] = x/10, x%10 + '0'
        }
        if δ == 1 {
            buf[0] = '1'
            n++
        }
    }
    dp := n

    for ; e < 0; e++ {
        if buf[n-1]%2 != 0 {
            buf[n] = '0'
            n++
        }
        δ, x := 0, byte(0)
        if buf[0] < '2' {
            δ, x = 1, buf[0] - '0'
            n--
            dp--
        }
        for i := 0; i < n; i++ {
            x = x*10 + buf[i+δ] - '0'
            buf[i], x = x/2 + '0', x%2
        }
    }

    if prec > 0 {
        if n > prec {
            if buf[prec] > '5' || buf[prec] == '5' && (nonzero(buf[prec+1:n]) || buf[prec-1]%2 == 1) {
                    i := prec-1
                    for i >= 0 && buf[i] == '9' {
                        buf[i] = '0'
                        i--
                    }
                    if i >= 0 {
                        buf[i]++
                    } else {
                        buf[0] = '1'
                        dp++
                    }
            }
            n = prec
        }
        for n < prec {
            buf[n] = '0'
            n++
        }
    }
    return fmt.Sprintf("%c.%se%+d", buf[0], buf[1:n], dp-1)
}

func nonzero(buf []byte) bool {
    for _, c := range buf {
        if c != '0' {
            return true
        }
    }
    return false
}

// Difficult boundary cases, derived from tables given in
//    Vern Paxson, A Program for Testing IEEE Decimal-Binary Conversion
//    ftp://ftp.ee.lbl.gov/testbase-report.ps.Z
//
var ftoaTests = []struct{
    N int
    F float64
    A string
}{
    // Table 3: Stress Inputs for Converting 53-bit Binary to Decimal, < 1/2 ULP
    {0, math.Ldexp(8511030020275656, -342), "9.e-88"},
    {1, math.Ldexp(5201988407066741, -824), "4.6e-233"},
    {2, math.Ldexp(6406892948269899, +237), "1.41e+87"},
    {3, math.Ldexp(8431154198732492, +72), "3.981e+37"},
    {4, math.Ldexp(6475049196144587, +99), "4.1040e+45"},
    {5, math.Ldexp(8274307542972842, +726), "2.92084e+234"},
    {6, math.Ldexp(5381065484265332, -456), "2.891946e-122"},
    {7, math.Ldexp(6761728585499734, -1057), "4.3787718e-303"},
    {8, math.Ldexp(7976538478610756, +376), "1.22770163e+129"},
    {9, math.Ldexp(5982403858958067, +377), "1.841552452e+129"},
    {10, math.Ldexp(5536995190630837, +93), "5.4835744350e+43"},
    {11, math.Ldexp(7225450889282194, +710), "3.89190181146e+229"},
    {12, math.Ldexp(7225450889282194, +709), "1.945950905732e+229"},
    {13, math.Ldexp(8703372741147379, +117), "1.4460958381605e+51"},
    {14, math.Ldexp(8944262675275217, -1001), "4.17367747458531e-286"},
    {15, math.Ldexp(7459803696087692, -707), "1.107950772878888e-197"},
    {16, math.Ldexp(6080469016670379, -381), "1.2345501366327440e-99"},
    {17, math.Ldexp(8385515147034757, +721), "9.25031711960365024e+232"},
    {18, math.Ldexp(7514216811389786, -828), "4.198047150284889840e-234"},
    {19, math.Ldexp(8397297803260511, -345), "1.1716315319786511046e-88"},
    {20, math.Ldexp(6733459239310543, +202), "4.32810072844612493629e+76"},
    {21, math.Ldexp(8091450587292794, -473), "3.317710118160031081518e-127"},

    // Table 4: Stress Inputs for Converting 53-bit Binary to Decimal, > 1/2 ULP
    {0, math.Ldexp(6567258882077402, +952), "3.e+302"},
    {1, math.Ldexp(6712731423444934, +535), "7.6e+176"},
    {2, math.Ldexp(6712731423444934, +534), "3.78e+176"},
    {3, math.Ldexp(5298405411573037, -957), "4.350e-273"},
    {4, math.Ldexp(5137311167659507, -144), "2.3037e-28"},
    {5, math.Ldexp(6722280709661868, +363), "1.26301e+125"},
    {6, math.Ldexp(5344436398034927, -169), "7.142211e-36"},
    {7, math.Ldexp(8369123604277281, -853), "1.3934574e-241"},
    {8, math.Ldexp(8995822108487663, -780), "1.41463449e-219"},
    {9, math.Ldexp(8942832835564782, -383), "4.539277920e-100"},
    {10, math.Ldexp(8942832835564782, -384), "2.2696389598e-100"},
    {11, math.Ldexp(8942832835564782, -385), "1.13481947988e-100"},
    {12, math.Ldexp(6965949469487146, -249), "7.700366561890e-60"},
    {13, math.Ldexp(6965949469487146, -250), "3.8501832809448e-60"},
    {14, math.Ldexp(6965949469487146, -251), "1.92509164047238e-60"},
    {15, math.Ldexp(7487252720986826, +548), "6.898586531774201e+180"},
    {16, math.Ldexp(5592117679628511, +164), "1.3076622631878654e+65"},
    {17, math.Ldexp(8887055249355788, +665), "1.36052020756121240e+216"},
    {18, math.Ldexp(6994187472632449, +690), "3.592810217475959676e+223"},
    {19, math.Ldexp(8797576579012143, +588), "8.9125197712484551899e+192"},
    {20, math.Ldexp(7363326733505337, +272), "5.58769757362301140950e+97"},
    {21, math.Ldexp(8549497411294502, -448), "1.176257830728540379990e-119"},

    {3, 12345000, "1.234e+7"},
}

func main() {
    fmt.Printf("%s\n", ftoa(math.Pi, 50))  // 50 digits of math.Pi (not 50 digits of π)
    //fmt.Printf("%s\n", ftoa(math.Nextafter(0, 1), 0))
    for _, tt := range ftoaTests {
        if a := ftoa(tt.F, tt.N+1); a != tt.A {
            fmt.Printf("ftoa(%g, %d) = %q, want %q\n", tt.F, tt.N+1, a, tt.A)
        }
    }
}

28. That's the minimum number of AND or OR operators you need in order to write any Boolean function of five variables. Alex Healy and I computed that in April 2010. Until then, I believe no one had ever known that little fact. This post describes how we computed it and how we almost got scooped by Knuth's Volume 4A which considers the problem for AND, OR, and XOR.

A Naive Brute Force Approach

Any Boolean function of two variables can be written with at most 3 AND or OR operators: the parity function on two variables X XOR Y is (X AND Y') OR (X' AND Y), where X' denotes “not X.” We can shorten the notation by writing AND and OR like multiplication and addition: X XOR Y = X*Y' + X'*Y.

For three variables, parity is also a hardest function, requiring 9 operators: X XOR Y XOR Z = (X*Z'+X'*Z+Y')*(X*Z+X'*Z'+Y).

For four variables, parity is still a hardest function, requiring 15 operators: W XOR X XOR Y XOR Z = (X*Z'+X'*Z+W'*Y+W*Y')*(X*Z+X'*Z'+W*Y+W'*Y').

The sequence so far prompts a few questions. Is parity always a hardest function? Does the minimum number of operators alternate between 2ⁿ−1 and 2ⁿ+1?

I computed these results in January 2001 after hearing the problem from Neil Sloane, who suggested it as a variant of a similar problem first studied by Claude Shannon.

The program I wrote to compute a(4) computes the minimum number of operators for every Boolean function of n variables in order to find the largest minimum over all functions. There are 2⁴ = 16 settings of four variables, and each function can pick its own value for each setting, so there are 2¹⁶ different functions. To make matters worse, you build new functions by taking pairs of old functions and joining them with AND or OR. 2¹⁶ different functions means 2¹⁶·2¹⁶ = 2³² pairs of functions.

The program I wrote was a mangling of the Floyd-Warshall all-pairs shortest paths algorithm. That algorithm is:

// Floyd-Warshall all pairs shortest path
func compute():
    for each node i
        for each node j
            dist[i][j] = direct distance, or ∞
    
    for each node k
        for each node i
            for each node j
                d = dist[i][k] + dist[k][j]
                if d < dist[i][j]
                    dist[i][j] = d
    return

The algorithm begins with the distance table dist[i][j] set to an actual distance if i is connected to j and infinity otherwise. Then each round updates the table to account for paths going through the node k: if it's shorter to go from i to k to j, it saves that shorter distance in the table. The nodes are numbered from 0 to n, so the variables i, j, k are simply integers. Because there are only n nodes, we know we'll be done after the outer loop finishes.

The program I wrote to find minimum Boolean formula sizes is an adaptation, substituting formula sizes for distance.

// Algorithm 1
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each function f
            for each function g
                d = size[f] + 1 + size[g]
                if d < size[f OR g]
                    size[f OR g] = d
                    changed = true
                if d < size[f AND g]
                    size[f AND g] = d
                    changed = true
        if not changed
            return

Algorithm 1 runs the same kind of iterative update loop as the Floyd-Warshall algorithm, but it isn't as obvious when you can stop, because you don't know the maximum formula size beforehand. So it runs until a round doesn't find any new functions to make, iterating until it finds a fixed point.

The pseudocode above glosses over some details, such as the fact that the per-function loops can iterate over a queue of functions known to have finite size, so that each loop omits the functions that aren't yet known. That's only a constant factor improvement, but it's a useful one.

Another important detail missing above is the representation of functions. The most convenient representation is a binary truth table. For example, if we are computing the complexity of two-variable functions, there are four possible inputs, which we can number as follows.

The functions are then the 4-bit numbers giving the value of the function for each input. For example, function 13 = 1101₂ is true for all inputs except X=false Y=true. Three-variable functions correspond to 3-bit inputs generating 8-bit truth tables, and so on.

This representation has two key advantages. The first is that the numbering is dense, so that you can implement a map keyed by function using a simple array. The second is that the operations “f AND g” and “f OR g” can be implemented using bitwise operators: the truth table for “f AND g” is the bitwise AND of the truth tables for f and g.

That program worked well enough in 2001 to compute the minimum number of operators necessary to write any 1-, 2-, 3-, and 4-variable Boolean function. Each round takes asymptotically O(2²ⁿ·2²ⁿ) = O(2²ⁿ⁺¹) time, and the number of rounds needed is O(the final answer). The answer for n=4 is 15, so the computation required on the order of 15·2²⁵ = 15·2³² iterations of the innermost loop. That was plausible on the computer I was using at the time, but the answer for n=5, likely around 30, would need 30·2⁶⁴ iterations to compute, which seemed well out of reach. At the time, it seemed plausible that parity was always a hardest function and that the minimum size would continue to alternate between 2ⁿ−1 and 2ⁿ+1. It's a nice pattern.

Exploiting Symmetry

Five years later, though, Alex Healy and I got to talking about this sequence, and Alex shot down both conjectures using results from the theory of circuit complexity. (Theorists!) Neil Sloane added this note to the entry for the sequence in his Online Encyclopedia of Integer Sequences:

%E A056287 Russ Cox conjectures that X₁ XOR ... XOR X_n is always a worst f and that a(5) = 33 and a(6) = 63. But (Jan 27 2006) Alex Healy points out that this conjecture is definitely false for large n. So what is a(5)?

Indeed. What is a(5)? No one knew, and it wasn't obvious how to find out.

In January 2010, Alex and I started looking into ways to speed up the computation for a(5). 30·2⁶⁴ is too many iterations but maybe we could find ways to cut that number.

In general, if we can identify a class of functions f whose members are guaranteed to have the same complexity, then we can save just one representative of the class as long as we recreate the entire class in the loop body. What used to be:

for each function f
    for each function g
        visit f AND g
        visit f OR g

can be rewritten as

for each canonical function f
    for each canonical function g
        for each ff equivalent to f
            for each gg equivalent to g
                visit ff AND gg
                visit ff OR gg

That doesn't look like an improvement: it's doing all the same work. But it can open the door to new optimizations depending on the equivalences chosen. For example, the functions “f” and “¬f” are guaranteed to have the same complexity, by DeMorgan's laws. If we keep just one of those two on the lists that “for each function” iterates over, we can unroll the inner two loops, producing:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f OR g
        visit ¬f AND g
        visit f OR ¬g
        visit f AND ¬g
        visit ¬f OR ¬g
        visit ¬f AND ¬g

That's still not an improvement, but it's no worse. Each of the two loops considers half as many functions but the inner iteration is four times longer. Now we can notice that half of tests aren't worth doing: “f AND g” is the negation of “¬f OR ¬g,” and so on, so only half of them are necessary.

Let's suppose that when choosing between “f” and “¬f” we keep the one that is false when presented with all true inputs. (This has the nice property that f ^ (int32(f) >> 31) is the truth table for the canonical form of f.) Then we can tell which combinations above will produce canonical functions when f and g are already canonical:

for each canonical function f
    for each canonical function g
        visit f OR g
        visit f AND g
        visit ¬f AND g
        visit f AND ¬g

That's a factor of two improvement over the original loop.

Another observation is that permuting the inputs to a function doesn't change its complexity: “f(V, W, X, Y, Z)” and “f(Z, Y, X, W, V)” will have the same minimum size. For complex functions, each of the 5! = 120 permutations will produce a different truth table. A factor of 120 reduction in storage is good but again we have the problem of expanding the class in the iteration. This time, there's a different trick for reducing the work in the innermost iteration. Since we only need to produce one member of the equivalence class, it doesn't make sense to permute the inputs to both f and g. Instead, permuting just the inputs to f while fixing g is guaranteed to hit at least one member of each class that permuting both f and g would. So we gain the factor of 120 twice in the loops and lose it once in the iteration, for a net savings of 120. (In some ways, this is the same trick we did with “f” vs “¬f.”)

A final observation is that negating any of the inputs to the function doesn't change its complexity, because X and X' have the same complexity. The same argument we used for permutations applies here, for another constant factor of 2⁵ = 32.

The code stores a single function for each equivalence class and then recomputes the equivalent functions for f, but not g.

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g
            visit ff OR g
            visit ff AND g
            visit ¬ff AND g
            visit ff AND ¬g

In all, we just got a savings of 2·120·32 = 7680, cutting the total number of iterations from 30·2⁶⁴ = 5×10²⁰ to 7×10¹⁶. If you figure we can do around 10⁹ iterations per second, that's still 800 days of CPU time.

The full algorithm at this point is:

// Algorithm 2
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    loop
        changed = false
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g
                    d = size[ff] + 1 + size[g]
                    changed |= visit(d, ff OR g)
                    changed |= visit(d, ff AND g)
                    changed |= visit(d, ff AND ¬g)
                    changed |= visit(d, ¬ff AND g)
        if not changed
            return

func visit(d, fg):
    if size[fg] != ∞
        return false
    
    record fg as canonical

    for each function ffgg equivalent to fg
        size[ffgg] = d
    return true

The helper function “visit” must set the size not only of its argument fg but also all equivalent functions under permutation or inversion of the inputs, so that future tests will see that they have been computed.

Methodical Exploration

There's one final improvement we can make. The approach of looping until things stop changing considers each function pair multiple times as their sizes go down. Instead, we can consider functions in order of complexity, so that the main loop builds first all the functions of minimum complexity 1, then all the functions of minimum complexity 2, and so on. If we do that, we'll consider each function pair at most once. We can stop when all functions are accounted for.

Applying this idea to Algorithm 1 (before canonicalization) yields:

// Algorithm 3
func compute()
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each function f
            for each function g of size k − size(f) − 1
                if size[f AND g] == ∞
                    size[f AND g] = k
                    nsize++
                if size[f OR g] == ∞
                    size[f OR g] = k
                    nsize++
        if nsize == 22n
            return

Applying the idea to Algorithm 2 (after canonicalization) yields:

// Algorithm 4
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    for k = 1 to ∞
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)
        if nvisited == 22n
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

The original loop in Algorithms 1 and 2 considered each pair f, g in every iteration of the loop after they were computed. The new loop in Algorithms 3 and 4 considers each pair f, g only once, when k = size(f) + size(g) + 1. This removes the leading factor of 30 (the number of times we expected the first loop to run) from our estimation of the run time. Now the expected number of iterations is around 2⁶⁴/7680 = 2.4×10¹⁵. If we can do 10⁹ iterations per second, that's only 28 days of CPU time, which I can deliver if you can wait a month.

Our estimate does not include the fact that not all function pairs need to be considered. For example, if the maximum size is 30, then the functions of size 14 need never be paired against the functions of size 16, because any result would have size 14+1+16 = 31. So even 2.4×10¹⁵ is an overestimate, but it's in the right ballpark. (With hindsight I can report that only 1.7×10¹⁴ pairs need to be considered but also that our estimate of 10⁹ iterations per second was optimistic. The actual calculation ran for 20 days, an average of about 10⁸ iterations per second.)

Endgame: Directed Search

A month is still a long time to wait, and we can do better. Near the end (after k is bigger than, say, 22), we are exploring the fairly large space of function pairs in hopes of finding a fairly small number of remaining functions. At that point it makes sense to change from the bottom-up “bang things together and see what we make” to the top-down “try to make this one of these specific functions.” That is, the core of the current search is:

for each canonical function f
    for each function ff equivalent to f
        for each canonical function g of size k − size(f) − 1
            visit(k, ff OR g)
            visit(k, ff AND g)
            visit(k, ff AND ¬g)
            visit(k, ¬ff AND g)

We can change it to:

for each missing function fg
    for each canonical function g
        for all possible f such that one of these holds
                * fg = f OR g
                * fg = f AND g
                * fg = ¬f AND g
                * fg = f AND ¬g
            if size[f] == k − size(g) − 1
                visit(k, fg)
                next fg

By the time we're at the end, exploring all the possible f to make the missing functions—a directed search—is much less work than the brute force of exploring all combinations.

As an example, suppose we are looking for f such that fg = f OR g. The equation is only possible to satisfy if fg OR g == fg. That is, if g has any extraneous 1 bits, no f will work, so we can move on. Otherwise, the remaining condition is that f AND ¬g == fg AND ¬g. That is, for the bit positions where g is 0, f must match fg. The other bits of f (the bits where g has 1s) can take any value. We can enumerate the possible f values by recursively trying all possible values for the “don't care” bits.

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

It doesn't matter which 1 bit we choose for the recursion, but finding the rightmost 1 bit is cheap: it is isolated by the (admittedly surprising) expression “any AND −any.”

Given find, the loop above can try these four cases:

Rewriting the Boolean expressions to use only the four OR forms means that we only need to write the “adding bits” version of find.

The final algorithm is:

// Algorithm 5
func compute():
    for each function f
        size[f] = ∞
    
    for each single variable function f = v
        size[f] = 0
    
    // Generate functions.
    for k = 1 to max_generate
        for each canonical function f
            for each function ff equivalent to f
                for each canonical function g of size k − size(f) − 1
                    visit(k, ff OR g)
                    visit(k, ff AND g)
                    visit(k, ff AND ¬g)
                    visit(k, ¬ff AND g)

    // Search for functions.
    for k = max_generate+1 to ∞
        for each missing function fg
            for each canonical function g
                fsize = k − size(g) − 1
                if fg OR g == fg
                    if f = find(fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if fg OR ¬g == fg
                    if f = find(fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR g == ¬fg
                    if f = find(¬fg AND ¬g, g, fsize) succeeds
                        visit(k, fg)
                        next fg
                if ¬fg OR ¬g == ¬fg
                    if f = find(¬fg AND g, ¬g, fsize) succeeds
                        visit(k, fg)
                        next fg
        if nvisited == 22n
            return

func visit(d, fg):
    if size[fg] != ∞
        return
    
    record fg as canonical

    for each function ffgg equivalent to fg
        if size[ffgg] != ∞
            size[ffgg] = d
            nvisited += 2  // counts ffgg and ¬ffgg
    return

func find(x, any, xsize):
    if size(x) == xsize
        return x
    while any != 0
        bit = any AND −any  // rightmost 1 bit in any
        any = any AND ¬bit
        if f = find(x OR bit, any, xsize) succeeds
            return f
    return failure

To get a sense of the speedup here, and to check my work, I ran the program using both algorithms on a 2.53 GHz Intel Core 2 Duo E7200.

The bracketed times are estimates based on the work involved: I did not wait that long for the intermediate search steps. The search algorithm is quite a bit worse than generate until there are very few functions left to find. However, it comes in handy just when it is most useful: when the generate algorithm has slowed to a crawl. If we run generate through formulas of size 22 and then switch to search for 23 onward, we can run the whole computation in just over half a day of CPU time.

The computation of a(5) identified the sizes of all 616,126 canonical Boolean functions of 5 inputs. In contrast, there are just over 200 trillion canonical Boolean functions of 6 inputs. Determining a(6) is unlikely to happen by brute force computation, no matter what clever tricks we use.

Adding XOR

We've assumed the use of just AND and OR as our basis for the Boolean formulas. If we also allow XOR, functions can be written using many fewer operators. In particular, a hardest function for the 1-, 2-, 3-, and 4-input cases—parity—is now trivial. Knuth examines the complexity of 5-input Boolean functions using AND, OR, and XOR in detail in The Art of Computer Programming, Volume 4A. Section 7.1.2's Algorithm L is the same as our Algorithm 3 above, given for computing 4-input functions. Knuth mentions that to adapt it for 5-input functions one must treat only canonical functions and gives results for 5-input functions with XOR allowed. So another way to check our work is to add XOR to our Algorithm 4 and check that our results match Knuth's.

Because the minimum formula sizes are smaller (at most 12), the computation of sizes with XOR is much faster than before:

Knuth does not discuss anything like Algorithm 5, because the search for specific functions does not apply to the AND, OR, and XOR basis. XOR is a non-monotone function (it can both turn bits on and turn bits off), so there is no test like our “if fg OR g == fg” and no small set of “don't care” bits to trim the search for f. The search for an appropriate f in the XOR case would have to try all f of the right size, which is exactly what Algorithm 4 already does.

Volume 4A also considers the problem of building minimal circuits, which are like formulas but can use common subexpressions additional times for free, and the problem of building the shallowest possible circuits. See Section 7.1.2 for all the details.

Code and Web Site

The web site boolean-oracle.swtch.com lets you type in a Boolean expression and gives back the minimal formula for it. It uses tables generated while running Algorithm 5; those tables and the programs described in this post are also available on the site.

Postscript: Generating All Permutations and Inversions

The algorithms given above depend crucially on the step “for each function ff equivalent to f,” which generates all the ff obtained by permuting or inverting inputs to f, but I did not explain how to do that. We already saw that we can manipulate the binary truth table representation directly to turn f into ¬f and to compute combinations of functions. We can also manipulate the binary representation directly to invert a specific input or swap a pair of adjacent inputs. Using those operations we can cycle through all the equivalent functions.

To invert a specific input, let's consider the structure of the truth table. The index of a bit in the truth table encodes the inputs for that entry. For example, the low bit of the index gives the value of the first input. So the even-numbered bits—at indices 0, 2, 4, 6, ...—correspond to the first input being false, while the odd-numbered bits—at indices 1, 3, 5, 7, ...—correspond to the first input being true. Changing just that bit in the index corresponds to changing the single variable, so indices 0, 1 differ only in the value of the first input, as do 2, 3, and 4, 5, and 6, 7, and so on. Given the truth table for f(V, W, X, Y, Z) we can compute the truth table for f(¬V, W, X, Y, Z) by swapping adjacent bit pairs in the original truth table. Even better, we can do all the swaps in parallel using a bitwise operation. To invert a different input, we swap larger runs of bits.

Being able to invert a specific input lets us consider all possible inversions by building them up one at a time. The Gray code lets us enumerate all possible 5-bit input codes while changing only 1 bit at a time as we move from one input to the next:

This minimizes the number of inversions we need: to consider all 32 cases, we only need 31 inversion operations. In contrast, visiting the 5-bit input codes in the usual binary order 0, 1, 2, 3, 4, ... would often need to change multiple bits, like when changing from 3 to 4.

To swap a pair of adjacent inputs, we can again take advantage of the truth table. For a pair of inputs, there are four cases: 00, 01, 10, and 11. We can leave the 00 and 11 cases alone, because they are invariant under swapping, and concentrate on swapping the 01 and 10 bits. The first two inputs change most often in the truth table: each run of 4 bits corresponds to those four cases. In each run, we want to leave the first and fourth alone and swap the second and third. For later inputs, the four cases consist of sections of bits instead of single bits.

Being able to swap a pair of adjacent inputs lets us consider all possible permutations by building them up one at a time. Again it is convenient to have a way to visit all permutations by applying only one swap at a time. Here Volume 4A comes to the rescue. Section 7.2.1.2 is titled “Generating All Permutations,” and Knuth delivers many algorithms to do just that. The most convenient for our purposes is Algorithm P, which generates a sequence that considers all permutations exactly once with only a single swap of adjacent inputs between steps. Knuth calls it Algorithm P because it corresponds to the “Plain changes” algorithm used by bell ringers in 17th century England to ring a set of bells in all possible permutations. The algorithm is described in a manuscript written around 1653!

We can examine all possible permutations and inversions by nesting a loop over all permutations inside a loop over all inversions, and in fact that's what my program does. Knuth does one better, though: his Exercise 7.2.1.2-20 suggests that it is possible to build up all the possibilities using only adjacent swaps and inversion of the first input. Negating arbitrary inputs is not hard, though, and still does minimal work, so the code sticks with Gray codes and Plain changes.

stanleylieber posted a photo:

stanleylieber posted a photo:

Python introduced a named capturing form in its regular expressions: (?P<x>...) is like (...) but you refer to it as \k'x' instead of \1. Perl and .NET picked it up without the Pythonic P. They also let you say (?'x'...) instead of (?<x>...). (Perl: there's more than one way to do it!)

You can use these during the match just like any backreference; the value of \k'x' is the most recent text matched by (?<x>...). So (?<d>[0-9])+\k'd' matches any digit string in which the last two digits are the same.

.NET introduces a variant on the named capture, (?<-x>...), which, during the match, deletes the last captured substring for x, exposing the one that was there before. This implies that the named captures are stored on an internal per-name stack and it lets you do nested matching: (?<d>[0-9])+(\k'd'(?<-d>))+ matches the longest prefix of an even-length palindrome of digits, so 12345543 in 1234554399.

There's a Perl addition that appears to have snuck into .NET undocumented, which is that you can say (?(cond)then|else) or just (?(cond)then) as a conditional expression: if cond is true, then it tries to match then, else else (or the empty string). The condition 1 means that there was a match for \1. In Perl the condition <name> means that there was a match for the named back-reference \k'name'. In .NET it appears that the syntax is just name, by closer analogy with the numbered backreferences.

If you want full palindromes, you can insert a condition that there must be no matches left for d on the stack, by using d as the condition and (?!) - which cannot match anything - as the true branch. The final thunderclap, then, is:

I haven't tried this, since I don't have easy access to .NET.

This post expands on the technique to match well-formed XML.

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

stanleylieber posted a photo:

plan9.bell-labs.com/sources/contrib/aiju/paint.c

drawn with thinkpad x61 tablet using aiju's wacom and paint software.

stanleylieber posted a photo:

plan9.bell-labs.com/sources/contrib/aiju/paint.c

stanleylieber posted a photo:

plan9.bell-labs.com/sources/contrib/aiju/paint.c

stanleylieber posted a photo:

plan9.bell-labs.com/sources/contrib/aiju/paint.c

stanleylieber posted a photo:

plan9.bell-labs.com/sources/contrib/aiju/paint.c

stanleylieber posted a photo:

fixed?:
code.google.com/p/plan9front/source/detail?r=404c02526ade...

stanleylieber posted a photo:

code.google.com/p/plan9front/issues/detail?id=14&cols...

stanleylieber posted a photo:

code.google.com/p/plan9front/issues/detail?id=14&cols...

stanleylieber posted a photo:

code.google.com/p/plan9front/issues/detail?id=14&cols...

stanleylieber posted a photo:

intel wifi, vesa 1024x768x32.

stanleylieber posted a photo:

the x41 has no internal optical drive. broadcom ethernet and atheros wifi are not supported. vesa 1024x768x32. booted from the docking station.

stanleylieber posted a photo:

thinkpad t23 running plan 9 native. thanks to fgb's equis x11 server and cinap_lenrek's linuxemu, it is possible to run a reasonably modern web browser on plan 9.

stanleylieber posted a photo:

code.stanleylieber.com/1oct1993.com

I've been writing about Go internals, which I'll keep doing, but I also want to spend some time on Go programs. Go's reflect package implements data reflection. Any value can be passed to reflect.NewValue (its argument type is interface{}, the empty interface) and then manipulated and examined by looking at the result, a reflect.Value. Typically, you use a type switch to determine what kind of value it is—a *IntValue, a *StructValue, a *PtrValue, and so on—and then walk it further. This is how fmt.Print prints arbitrary data passed to it.

Go allows programs to tag the fields in struct definitions with annotation strings. These annotations have no effect on the compilation but are recorded in the run-time type information and can be examined via reflection. The annotations can be hints for reflection-driven code traversing the data structures. This blog post shows two examples of such code: an XML parser that writes directly into data structures, and a template-based output generator that reads from them.

An XML Linked List

The Go XML package implements a function Unmarshal which parses XML directly into data structures. As a contrived but illustrative example, here is an XML encoding of a linked list:

var encoded = `
   <list><value>a</value>
       <list><value>b</value>
           <list><value>c</value>
           </list>
       </list>
   </list>
`

(That's a backquoted multi-line Go string literal.)

Given this Go data structure definition:

// http://gopaste.org/view/private:7v2CQ
type List struct {
   Value string
   List *List
}

func (l *List) String() string {
if l == nil {
 return "nil"
}
return l.Value + " :: " + l.List.String()
}

we can invoke xml.Unmarshal to turn the XML above into an instance of this data structure:

func main() {
var l *List
if err := xml.Unmarshal(strings.NewReader(encoded), &l); err != nil {
 log.Exit("xml.Unmarshal: ", err)
}
fmt.Println(l)
}

This program prints a :: b :: c :: nil. The call to xml.Unmarshal walked the XML and the data structure at the same time, matching the XML tags <value> and <list> against the names of the structure fields and allocating pointers where necessary.

There are decisions to be made when matching XML against the data structure that aren't easily expressed with just the usual struct information. For example, we might want to make the value an attribute instead of a sub-element. Because attributes and sub-elements might use the same names, the XML package requires struct fields holding attributes to be tagged with "attr". This data structure and XML encoding would also work in the program above:

// http://gopaste.org/view/private:2yR7E
type List struct {
   Value string "attr"
   List *List
}

var encoded = `
   <list value="a">
       <list value="b">
           <list value="c"/>
       </list>
   </list>
`

If a field has type string, it gets the character data from the element with that name, but sometimes you need to accumulate both character data and sub-elements. To do this, you can tag a field with "chardata". This data structure and XML encoding would also work:

// http://gopaste.org/view/private:U3ews
type List struct {
    Value string "chardata"
    List *List
}

var encoded = `<list>a<list>b<list>c</list></list></list>`

The annotations are trivial but important: where the encoding and the data structures are not a perfect match (and they rarely are), the annotations provide the hints necessary for the XML package to make them work together anyway.

Code Search Client

Let's look at real XML data. Google's Code Search provides regular expression search over the world's public source code. The search [file:/usr/sys/ken/slp.c expected] returns a single, famous result. Instead of using the web interface, though, we can issue the same query using the Code Search GData API and get this XML back (simplified and highlighted for structure):

<?xml version="1.0" encoding="UTF-8"?>
<feed xmlns="http://www.w3.org/2005/Atom"
     xmlns:gcs="http://schemas.google.com/codesearch/2006"
     xml:base="http://www.google.com">
 <id>http://www.google.com/codesearch/feeds/search?q=file:/usr/sys/ken/slp.c+expected</id>
 <updated>2009-12-04T23:49:22Z</updated>
 <title type="text">Google Code Search</title>
  <generator version="1.0" uri="http://www.google.com/codesearch">Google Code Search</generator>
 <entry>
   <gcs:package name="http://www.tuhs.org" uri="http://www.tuhs.org"></gcs:package>
   <gcs:file name="Archive/PDP-11/Trees/V6/usr/sys/ken/slp.c"></gcs:file>
   <gcs:match lineNumber="325" type="text/html">&lt;pre&gt;  * You are not &lt;b&gt;expected&lt;/b&gt; to understand this.
&lt;/pre&gt;</gcs:match>
 </entry>
</feed>

From the API documentation or just by eyeballing, we can write data structures for the information we'd like to extract:

type Feed struct {
   XMLName    xml.Name "http://www.w3.org/2005/Atom feed"
   Entry []Entry
}

type Entry struct {
   XMLName xml.Name "http://www.w3.org/2005/Atom entry"
   Package Package
   File File
   Match []Match
}

type Package struct {
   XMLName xml.Name "http://schemas.google.com/codesearch/2006 package"
   Name string "attr"
   URI string "attr"
}

type File struct {
   XMLName xml.Name "http://schemas.google.com/codesearch/2006 file"
   Name string "attr"
}

type Match struct {
   XMLName xml.Name "http://schemas.google.com/codesearch/2006 match"
   LineNumber string "attr"
   Type string "attr"
   Snippet string "chardata"
}

The XMLName fields are not required. The XML package records the XML tag name in them. If there is a string annotation (as there is here), then the XML package requires that the XML element being considered has the given name space and tag name. That is, the annotation is both documentation and an assertion about what kind of XML goes into this structure.

A full Atom GData feed has many other fields, but these are the only ones that we care about. The XML parser will throw away data that doesn't fit into our structures.

We can fetch the feed via HTTP and unmarshal the HTTP response data directly into the data structures:

r, _, err := http.Get(`http://www.google.com/codesearch/feeds/search?q=` +
   http.URLEscape(flag.Arg(0)))
if err != nil {
   log.Exit(err)
}

var f Feed
if err := xml.Unmarshal(r.Body, &f); err != nil {
   log.Exit("xml.Unmarshal: ", err)
}

and then print the results:

for _, e := range f.Entry {
   fmt.Printf("%s\n", e.Package.Name)
   for _, m := range e.Match {
       fmt.Printf("%s:%s:\n", e.File.Name, m.LineNumber)
       fmt.Printf("%s\n", cutHTML(m.Snippet))
   }
   fmt.Printf("\n")
}

(The cutHTML function returns its argument with HTML tags stripped: the m.Snippet is HTML but we just want to print text.)

Compared to the xml.Unmarshal, that loop with all the fmt.Printf calls sure looks clunky. We can use a reflection-driven process to print the data too. The template package is a Go implementation of json-template. We can write a template like:

var tmpl = `{.repeated section Entry}
{Package.Name}
{.repeated section Match}
{File.Name}:{LineNumber}:
{Snippet|nohtml}
{.end}

{.end}`

and then print the data using that template:

t := template.MustParse(tmpl, template.FormatterMap{"nohtml": nohtml})
t.Execute(&f, os.Stdout)

The formatter map definitions arrange that the {Snippet|nohtml} in the template run the data through the nohtml function when printing. Both variants of our program produce the same output:

http://www.tuhs.org
Archive/PDP-11/Trees/V6/usr/sys/ken/slp.c:325:
 * You are not expected to understand this.

Full source code is at http://gopaste.org/view/private:7ybCj

Parsing HTML

I still have three more tricks up my sleeve.

First, in a pinch and if the HTML is mostly well formatted or you're just lucky, the XML parser can handle HTML too. Second, when the XML parser walks into a struct field, if the field is a pointer and is nil, it allocates a new value, as we saw in the linked list example. But if the field is a non-nil pointer already, the parser just follows the pointer. The same goes for growing slices. Third, if the XML parser cannot find a struct field for a particular subelement, before giving up it looks for a field named Any and uses that field instead.

Combined, these three rules mean that this structure:

type Form struct {
   Input []Field
   Any *Form
}

type Field struct {
   Name string "attr"
   Value string "attr"
}

can be used to save a tree of form and other information from a web page. When you unmarshal into it, you get a tree showing the structure of the web page, with each element becoming a *Form because the parser used the Any field.

But who wants to walk that tree just to find the form fields? Instead, we can set the Any pointer to point back at the Form it is in. Then as the XML parser thinks it is walking the data structure, in fact it will be visiting the same Form struct over and over. Each time it finds an <input>, the parser will append it to the Input slice.

// http://gopaste.org/view/private:b8Ya2
func main() {
    r, _, err := http.Get(`http://code.google.com/p/go/`)
    if err != nil {
        log.Exit(err)
    }

    var f Form
    f.Any = &f

    p := xml.NewParser(r.Body)
    p.Strict = false
    p.Entity = xml.HTMLEntity
    p.AutoClose = xml.HTMLAutoClose
    if err := p.Unmarshal(&f, nil); err != nil {
        log.Exit("xml.Unmarshal: ", err)
    }

    for _, fld := range f.Input {
        fmt.Printf("%s=%q\n", fld.Name, fld.Value)
    }
}

This program prints:

q=""
projectsearch="Search projects"

Further Reading

There are a few more examples of this technique in the standard Go libraries. The net package's DNS client uses this technique to build generic packing and unpacking routines for DNS packets. The JSON package provides approximately the same functionality as the XML package, but with JSON as the wire format. In fact, JSON is arguably more suited to the task. (Remember: “the essence of XML is this: the problem it solves is not hard, and it does not solve the problem well.”) The ASN1 package also works this way, though its generality is limited: it implements just enough to parse SSL/TLS certificates. There are also other ways to use reflection, which will have to wait for future posts.

It's actually a little surprising how often this technique gets used in the Go libraries. Part of the reason is that it's a shiny new hammer, but it seems to be a very useful shiny new hammer, because so much of modern programming is talking to other programs over a variety of wire encodings.

Unmarshalling directly into data structures via reflection, with just a few necessary hints as annotations, can be implemented in other languages, but the examples I've seen are not nearly as elegant or as concise as the Go versions.

Apologies to Jon Bentley.

Go's interfaces—static, checked at compile time, dynamic when asked for—are, for me, the most exciting part of Go from a language design point of view. If I could export one feature of Go into other languages, it would be interfaces.

This post is my take on the implementation of interface values in the “gc” compilers: 6g, 8g, and 5g. Over at Airs, Ian Lance Taylor has written two posts about the implementation of interface values in gccgo. The implementations are more alike than different: the biggest difference is that this post has pictures.

Before looking at the implementation, let's get a sense of what it must support.

Usage

Go's interfaces let you use duck typing like you would in a purely dynamic language like Python but still have the compiler catch obvious mistakes like passing an int where an object with a Read method was expected, or like calling the Read method with the wrong number of arguments. To use interfaces, first define the interface type (say, ReadCloser):

type ReadCloser interface {
    Read(b []byte) (n int, err os.Error)
    Close()
}

and then define your new function as taking a ReadCloser. For example, this function calls Read repeatedly to get all the data that was requested and then calls Close:

func ReadAndClose(r ReadCloser, buf []byte) (n int, err os.Error) {
    for len(buf) > 0 && err == nil {
        var nr int
        nr, err = r.Read(buf)
        n += nr
        buf = buf[nr:]
    }
    r.Close()
    return
}

The code that calls ReadAndClose can pass a value of any type as long as it has Read and Close methods with the right signatures. And, unlike in languages like Python, if you pass a value with the wrong type, you get an error at compile time, not run time.

Interfaces aren't restricted to static checking, though. You can check dynamically whether a particular interface value has an additional method. For example:

type Stringer interface {
    String() string
}

func ToString(any interface{}) string {
    if v, ok := any.(Stringer); ok {
        return v.String()
    }
    switch v := any.(type) {
    case int:
        return strconv.Itoa(v)
    case float:
        return strconv.Ftoa(v, 'g', -1)
    }
    return "???"
}

The value any has static type interface{}, meaning no guarantee of any methods at all: it could contain any type. The “comma ok” assignment inside the if statement asks whether it is possible to convert any to an interface value of type Stringer, which has the method String. If so, the body of that statement calls the method to obtain a string to return. Otherwise, the switch picks off a few basic types before giving up. This is basically a stripped down version of what the fmt package does. (The if could be replaced by adding case Stringer: at the top of the switch, but I used a separate statement to draw attention to the check.)

As a simple example, let's consider a 64-bit integer type with a String method that prints the value in binary and a trivial Get method:

type Binary uint64

func (i Binary) String() string {
    return strconv.Uitob64(i.Get(), 2)
}

func (i Binary) Get() uint64 {
    return uint64(i)
}

A value of type Binary can be passed to ToString, which will format it using the String method, even though the program never says that Binary intends to implement Stringer. There's no need: the runtime can see that Binary has a String method, so it implements Stringer, even if the author of Binary has never heard of Stringer.

These examples show that even though all the implicit conversions are checked at compile time, explicit interface-to-interface conversions can inquire about method sets at run time. “Effective Go” has more details about and examples of how interface values can be used.

Interface Values

Languages with methods typically fall into one of two camps: prepare tables for all the method calls statically (as in C++ and Java), or do a method lookup at each call (as in Smalltalk and its many imitators, JavaScript and Python included) and add fancy caching to make that call efficient. Go sits halfway between the two: it has method tables but computes them at run time. I don't know whether Go is the first language to use this technique, but it's certainly not a common one. (I'd be interested to hear about earlier examples; leave a comment below.)

As a warmup, a value of type Binary is just a 64-bit integer made up of two 32-bit words (like in the last post, we'll assume a 32-bit machine; this time memory grows down instead of to the right):

Interface values are represented as a two-word pair giving a pointer to information about the type stored in the interface and a pointer to the associated data. Assigning b to an interface value of type Stringer sets both words of the interface value.

(The pointers contained in the interface value are gray to emphasize that they are implicit, not directly exposed to Go programs.)

The first word in the interface value points at what I call an interface table or itable (pronounced i-table; in the runtime sources, the C implementation name is Itab). The itable begins with some metadata about the types involved and then becomes a list of function pointers. Note that the itable corresponds to the interface type, not the dynamic type. In terms of our example, the itable for Stringer holding type Binary lists the methods used to satisfy Stringer, which is just String: Binary's other methods (Get) make no appearance in the itable.

The second word in the interface value points at the actual data, in this case a copy of b. The assignment var s Stringer = b makes a copy of b rather than point at b for the same reason that var c uint64 = b makes a copy: if b later changes, s and c are supposed to have the original value, not the new one. Values stored in interfaces might be arbitrarily large, but only one word is dedicated to holding the value in the interface structure, so the assignment allocates a chunk of memory on the heap and records the pointer in the one-word slot. (There's an obvious optimization when the value does fit in the slot; we'll get to that later.)

To check whether an interface value holds a particular type, as in the type switch above, the Go compiler generates code equivalent to the C expression s.tab->type to obtain the type pointer and check it against the desired type. If the types match, the value can be copied by by dereferencing s.data.

To call s.String(), the Go compiler generates code that does the equivalent of the C expression s.tab->fun[0](s.data): it calls the appropriate function pointer from the itable, passing the interface value's data word as the function's first (in this example, only) argument. You can see this code if you run 8g -S x.go (details at the bottom of this post). Note that the function in the itable is being passed the 32-bit pointer from the second word of the interface value, not the 64-bit value it points at. In general, the interface call site doesn't know the meaning of this word nor how much data it points at. Instead, the interface code arranges that the function pointers in the itable expect the 32-bit representation stored in the interface values. Thus the function pointer in this example is (*Binary).String not Binary.String.

The example we're considering is an interface with just one method. An interface with more methods would have more entries in the fun list at the bottom of the itable.

Computing the Itable

Now we know what the itables look like, but where do they come from? Go's dynamic type conversions mean that it isn't reasonable for the compiler or linker to precompute all possible itables: there are too many (interface type, concrete type) pairs, and most won't be needed. Instead, the compiler generates a type description structure for each concrete type like Binary or int or func(map[int]string). Among other metadata, the type description structure contains a list of the methods implemented by that type. Similarly, the compiler generates a (different) type description structure for each interface type like Stringer; it too contains a method list. The interface runtime computes the itable by looking for each method listed in the interface type's method table in the concrete type's method table. The runtime caches the itable after generating it, so that this correspondence need only be computed once.

In our simple example, the method table for Stringer has one method, while the table for Binary has two methods. In general there might be ni methods for the interface type and nt methods for the concrete type. The obvious search to find the mapping from interface methods to concrete methods would take O(ni × nt) time, but we can do better. By sorting the two method tables and walking them simultaneously, we can build the mapping in O(ni + nt) time instead.

Memory Optimizations

The space used by the implementation described above can be optimized in two complementary ways.

First, if the interface type involved is empty—it has no methods—then the itable serves no purpose except to hold the pointer to the original type. In this case, the itable can be dropped and the value can point at the type directly:

Whether an interface type has methods is a static property—either the type in the source code says interface{} or it says interace{ methods... }—so the compiler knows which representation is in use at each point in the program.

Second, if the value associated with the interface value can fit in a single machine word, there's no need to introduce the indirection or the heap allocation. If we define Binary32 to be like Binary but implemented as a uint32, it could be stored in an interface value by keeping the actual value in the second word:

Whether the actual value is being pointed at or inlined depends on the size of the type. The compiler arranges for the functions listed in the type's method table (which get copied into the itables) to do the right thing with the word that gets passed in. If the receiver type fits in a word, it is used directly; if not, it is dereferenced. The diagrams show this: in the Binary version far above, the method in the itable is (*Binary).String, while in the Binary32 example, the method in the itable is Binary32.String not (*Binary32).String.

Of course, empty interfaces holding word-sized (or smaller) values can take advantage of both optimizations:

Method Lookup Performance

Smalltalk and the many dynamic systems that have followed it perform a method lookup every time a method gets called. For speed, many implementations use a simple one-entry cache at each call site, often in the instruction stream itself. In a multithreaded program, these caches must be managed carefully, since multiple threads could be at the same call site simultaneously. Even once the races have been avoided, the caches would end up being a source of memory contention.

Because Go has the hint of static typing to go along with the dynamic method lookups, it can move the lookups back from the call sites to the point when the value is stored in the interface. For example, consider this code snippet:

1   var any interface{}  // initialized elsewhere
2   s := any.(Stringer)  // dynamic conversion
3   for i := 0; i < 100; i++ {
4       fmt.Println(s.String())
5   }

In Go, the itable gets computed (or found in a cache) during the assignment on line 2; the dispatch for the s.String() call executed on line 4 is a couple of memory fetches and a single indirect call instruction.

In contrast, the implementation of this program in a dynamic language like Smalltalk (or JavaScript, or Python, or ...) would do the method lookup at line 4, which in a loop repeats needless work. The cache mentioned earlier makes this less expensive than it might be, but it's still more expensive than a single indirect call instruction.

Of course, this being a blog post, I don't have any numbers to back up this discussion, but it certainly seems like the lack of memory contention would be a big win in a heavily parallel program, as is being able to move the method lookup out of tight loops. Also, I'm talking about the general architecture, not the specifics o the implementation: the latter probably has a few constant factor optimizations still available.

More Information

The interface runtime support is in $GOROOT/src/pkg/runtime/iface.c. There's much more to say about interfaces (we haven't even seen an example of a pointer receiver yet) and the type descriptors (they power reflection in addition to the interface runtime) but those will have to wait for future posts.

Code

Supporting code (x.go):

package main

import (
 "fmt"
 "strconv"
)

type Stringer interface {
 String() string
}

type Binary uint64

func (i Binary) String() string {
 return strconv.Uitob64(i.Get(), 2)
}

func (i Binary) Get() uint64 {
 return uint64(i)
}

func main() {
 b := Binary(200)
 s := Stringer(b)
 fmt.Println(s.String())
}

Selected output of 8g -S x.go:

0045 (x.go:25) LEAL    s+-24(SP),BX
0046 (x.go:25) MOVL    4(BX),BP
0047 (x.go:25) MOVL    BP,(SP)
0048 (x.go:25) MOVL    (BX),BX
0049 (x.go:25) MOVL    20(BX),BX
0050 (x.go:25) CALL    ,BX

The LEAL loads the address of s into the register BX. (The notation n(SP) describes the word in memory at SP+n. 0(SP) can be shortened to (SP).) The next two MOVL instructions fetch the value from the second word in the interface and store it as the first function call argument, 0(SP). The final two MOVL instructions fetch the itable and then the function pointer from the itable, in preparation for calling that function.

<object allowscriptaccess="always" classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=10,0,0,0" height="410" id="playerArte" width="640"><param name="allowFullScreen" value="true"><param name="allowScriptAccess" value="always"><param name="quality" value="high"><param name="movie" value="http://videos.arte.tv/videoplayer.swf?videorefFileUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Ffr%2Fdo%5Fdelegate%2Fvideos%2Fnotre%5Fpoison%5Fquotidien%2D3761854%2Cview%2CasPlayerXml%2Exml&amp;admin=false&amp;autoPlay=true&amp;mode=prod&amp;localizedPathUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Fcae%2Fstatic%2Fflash%2Fplayer%2F&amp;configFileUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Fcae%2Fstatic%2Fflash%2Fplayer%2Fconfig%2Exml&amp;videoId=3761854&amp;lang=fr&amp;embed=true&amp;autoPlay=false"><embed allowfullscreen="true" allowscriptaccess="always" height="410" name="playerArte" pluginspage="http://www.macromedia.com/go/getflashplayer" quality="high" src="http://videos.arte.tv/videoplayer.swf?videorefFileUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Ffr%2Fdo%5Fdelegate%2Fvideos%2Fnotre%5Fpoison%5Fquotidien%2D3761854%2Cview%2CasPlayerXml%2Exml&amp;admin=false&amp;autoPlay=true&amp;mode=prod&amp;localizedPathUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Fcae%2Fstatic%2Fflash%2Fplayer%2F&amp;configFileUrl=http%3A%2F%2Fvideos%2Earte%2Etv%2Fcae%2Fstatic%2Fflash%2Fplayer%2Fconfig%2Exml&amp;videoId=3761854&amp;lang=fr&amp;embed=true&amp;autoPlay=false" type="application/x-shockwave-flash" width="640"></embed></object>

stanleylieber posted a photo:

1. EncryptedGoogle
2. encrypted.google.com
3. https://encrypted.google.com/search?{google:RLZ}{google:acceptedSuggestion}{google:originalQueryForSuggestion}sourceid=chrome&ie={inputEncoding}&q=%s

My copy arrived today. If you're looking to buy one, ordering directly from the publisher with coupon code KNUTH2010 [sic] gets you the book for $48.74 with free shipping. In contrast, Amazon and Barnes & Noble both charge more and won't ship for another week or two.

The MOS 6502 was ubiquitous in its day. The 6502 and its slight variants were at the heart of the Apple II, the Atari 2600, the BBC Micro, the Commodore 64, and the Nintendo Entertainment System, among others. It's amazing to think that all five—each a very influential system in its own right—were all built around the same chip.

The 6502 was the brainchild of Chuck Peddle, at the time an engineer with Motorola. Peddle was one of the engineers who worked on the Motorola 6800, and one of his jobs was to, well, peddle the 6800 to customers. The customers loved everything about it except its $300 price tag. Peddle tried to convince management at Motorola to create a lower-cost microprocessor, but Motorola didn't want to have such a chip cut into their not insubstantial profits from the 6800, and they told him in no uncertain terms that they wouldn't build such a chip. In response, Peddle and a handful of other 6800 engineers left Motorola and built one themselves. It was the MOS Technology 6502 and sold for $25. Even though both the 6800 and 6502 had a clock rate of 1 MHz, the 6502 had a minimal instruction pipeline that overlapped the fetch of the next instruction with the execution of the current one when possible, giving it a significant performance boost. And of course it sold for ten times less. So it ended up everywhere.

The story of the 6502 makes up the first chapter of Brian Bagnall's On the Edge: the Spectacular Rise and Fall of Commodore. My favorite part of the description of the development of the 6502 is the actual chip layout. These days, you can't design and lay out a computer chip without a computer. An Intel Core 2 chip has hundreds of millions of transistors. The 6502 had 3,510, and an engineer—a person, not a computer—had to draw each one by hand to lay out the chip. Mainly it was a single engineer, Bill Mensch.

But it gets better. Once the layout was completed and double-checked—a process that meant months using a ruler!—it still had to be converted into a Rubylith photomask that would etch the right patterns onto the silicon. The photomask for the 6502 was the size of a large table—large enough that the engineers crawled around on top of it to perform the job of cutting the layout out of the mask, all the while being careful to wear clean socks with no holes, so that stray toenails didn't insert traces in the mask where they didn't belong.

The most amazing part about the whole process is that they got the 6502 right in one try. Quoting On the Edge:

Bil Herd summarizes the situation. “No chip worked the first time,” he states emphatically. “No chip. It took seven or nine revs [revisions], or if someone was real good they would get it in five or six.”

Normally, a large number of flaws originate from the layout design. After all, there are six layers (and six masks) that have to align with each other perfectly. Imagine designing a town with every conceivable layer of infrastructure placed one on top of another. Plumbing is the lowest layer, followed by the subway system, underground walkways, buildings, overhead walkways, and finally telephone wires. These different layers have to connect with each other perfectly; otherwise, the town will not function. The massive complexity of such a system makes it likely that human errors will creep into the design.

After fabricating a run of chips and probing them, the layout engineers usually have to make changes to their original design and the process repeats from the Rubylith down. “Each run is a couple of hundred thousand [dollars],” says Herd.

Implausibly, the engineers detected no errors in [Bill] Mensch's layout. “He built seven different chips without ever having an error,” says Peddle with disbelief in his voice. “Almost all done by hand. When I tell people that, they don't believe me, but it's true. This guy is a unique person. He is the best layout guy in the world.”

The first chapter of On the Edge is posted on Bagnall's web site in HTML or PDF. The chapter says that Peddle “created a concept called pipelining,” which could be interpreted as saying that the 6502 was the first pipelined processor and that Peddle invented it. Does anyone know?

Fast forward thirty years. Computers are now old enough that there can be significant interest in maintaining the history of these old, venerable designs. The actual paper designs of the 6502 are long gone.

A team of three people—Greg James, Barry Silverman, and Brian Silverman—accumulated a bunch of 6502 chips, applied sulfuric acid to them to strip the casing and expose the actual chips, used a high-resolution photomicroscope to scan the chips, applied computer graphics techniques to build a vector representation of the chip, and finally derived from the vector form what amounts to the circuit diagram of the chip: a list of all 3,510 transistors with inputs, outputs, and what they're connected to. Combining that with a fairly generic (and, as these things go, trivial) “transistor circuit” simulator written in JavaScript and some HTML5 goodness, they created an animated 6502 web page that lets you watch the voltages race around the chip as it executes. For more, see their web site visual6502.org.

Oh, and it actually works. They applied the same technique to build the transistor map for an Atari 10444D TIA chip, which connected the 6502 to the television in the original Atari 2600, and then they simulated both chips together and were able to run actual Atari 2600 games. So the transistor map is probably (very close to) correct. More impressively, they got to that point without debugging. Their SIGGRAPH 2010 abstract explains that there were only 8 errors in the map of 20,000 components, and all the errors were spotted during the vectorization process. History repeats itself.

Michael Steil took the circuit information and started looking closely at how the chip did what it did. At last week's Chaos Communication Congress 27C3 conference, he gave a 50-minute talk that introduces the 6502 architecture and then uses the circuit diagram to explain various details and undocumented features of the chip. The original announcement is at Steil's blog. There is a version of the talk on YouTube, and in the blog comments you'll find links to higher-resolution copies. It's well worth watching, in any form, and it's fun to see how much Peddle, Mensch, and the rest of the 6502 team packed into that tiny number of transistors.

P. S. If you liked this, you might also like Computing Machines. Also, Barry Silverman and Brian Silverman (mentioned above) were two of the people behind the PDP-1 simulator written in Java that runs Spacewar!

This video depicts an HTTP GET by showing packets as balls flying between client and server, slowed 40x compared to real time. It's pretty nice for getting a visceral sense of the underlying TCP session: you can see individual rounds at the start and then as the session stabilizes the rounds begin to overlap enough that they disappear.

When I saw the video, it reminded me of the ever-present videos of sorting algorithms, like the ones on the Wikipedia heapsort and quicksort pages:

That in turn reminded me of a 2007 blog post by Aldo Cortesi about visualizing sorting algorithms using graphs instead of videos. He points out that the animations make time-based questions difficult to answer:

[It] is my measured opinion that this animation has all the explanatory power of a glob of porridge flung against a wall. To see why I say this, try to find rough answers to the following set of simple questions with reference to it:

• After what percentage of time is half of the array sorted?
• Can you find an element that moved about half the length of the array to reach its final destination?
• What percentage of the array was sorted after 80% of the sorting process? How about 20%?
• Does the number of sorted elements grow linearly or non-linearly with time (i.e. logarithmically or exponentially)?

If you thought that was harder than it needed to be, blame animation. First, while humans are great at estimating distances in space, they are pretty bad at estimating distances in time. This is why you had to watch the animation two or three times to answer the first question. When we translate time to a geometric length, as is done in any scientific diagram with a time dimension, this estimation process becomes easy. Second, many questions about sorting algorithms require us to actively compare the sorting state at two or more different time points. Since we don't have perfect memories, this is very, very hard in all but the simplest cases. This leaves us with a strangely one-dimensional view into an animation - we can see what's on screen at any given moment, but we have to strain to answer simple questions about, say, rates of change. Which is why the final question is hard to answer accurately.

Instead, he suggests plotting static graphs showing the paths of individual array elements over time. Here are his original visualizations of heapsort and quicksort:

The blog post is worth reading in full. It has much more detail and links to many other interesting blog posts and a new site dedicated to those visualizations, sortvis.org.

Remembering this made me wonder if the lesson of the sorting animations applied to the TCP animations too, so I collected my own tcpdumps of both sides of an HTTP GET, pulled out the trusty (but neglected) Unix tool join(1) to produce a dump with two timestamps on each packet, and then used Perl to turn it into a graph (raw PostScript):

Time marches to the right, with each row picking up where the previous one left off. Blue lines indicate packets from the client and black lines indicate packets from the server.

I think this kind of graph has the same important benefits that Cortesi realized with his sorting graphs. It's static, so you have time to study it, focus on anomalies, or notice patterns that aren't immediately apparent. The geometry of the lines, with flatter slopes corresponding to slower packets, makes it easy to compare speeds.

Here are just a few things I noticed.

The connection starts with the usual 3-way TCP handshake. The client sends the third packet in the handshake and the first data packet back to back, one of its few back-to-back transmissions. After the handshake and the initial GET, which probably fits entirely in that first packet, the client only receives data: the black lines are large payloads while the blue lines are ACK messages that trigger more payloads. Scanning across the client's view of the connection (the top edge of each row) we can see that the client is using the standard delayed ACKs, sending an ACK every two packets. Scanning across the server's view of the connection (the bottom edge of each row) we can see that the server usually responds to the acknowledgement of two packets by sending two more packets, leaving the TCP window size (the number of packets in flight) unchanged. Occasionally, though, the server grows the window size by responding with three packets instead of two. Three of these events are circled in rows 1 and 2. Occasionally the server only responds to an ACK with a single packet, but most of those appear to be times when the client was only acknowledging a single packet.

We can count the number of packets in flight at any given time by counting the number of black lines that cross a particular blue line, plus the number of packets sent when the blue line reaches the server. For example, three black lines cross the last complete blue line on row 1, and the server sends two more packets in response, so the window size then is five packets. By the end of row 2, the window size is seven packets.

The window size fluctuates a little once it stabilizes: at the end of row 10 it has grown to eight packets but at the end of row 20 it is back to seven. It's not clear what causes the server to shrink or grow the window size. I couldn't find any evidence of packet loss in the traces.

I set the time axis such that those initial packets travel on lines with a 2:1 slope. A glance down the page shows that while the packets sent by the client continue to travel at approximately that speed, the packets sent by the server gradually slow until row 3, where they appear to stabilize around a 1:2 slope, four times longer to send than the initial packets. Looking at the raw data, those later packets around 100 ms for a one-way trip compared to 20 ms during the original handshake, so our visual estimate is not far off. This is evidence of queueing along the path from server to client; the likely suspect is the server's upstream DSL connection.

The circled fragment on row 11 is more evidence of queuing. Something delays the ACK from client to server (note the more gradual slope) but the packets that the server sends in response are not noticeably delayed: they still had time to catch up with the bottlenecked packets.

The circled fragment on row 24 shows the opposite case. Most of the time the packet arrivals at the client are evenly spaced, but if a few packets from the server to the client get delayed, that delays the corresponding ACKs, which throws the conversation into a bursty behavior that takes a few rounds to convert to a steady state.

People more familiar with TCP might notice other interesting details in the plot. If you find something, please leave a comment.

Of course, the idea of plotting network packets against time in this way is not new: any class in network protocols uses diagrams like these. However, I have never seen a diagram like this one made from real timings on both sides, so that you can see the actual speeds of individual packets and compare the relative speeds of different packets, and I've never seen a diagram that was this zoomed out, so that you can see macro effects like the occasional congestion burp of rows 11 and 24. It would be interesting to have a tool that generated these automatically, but I rarely have a need to examine protocols at this level so I'm not likely to spend more time on it. If you know of (or make) such a tool, please leave a comment.

The internet tubes have been filled with chatter recently about a paper posted on arXiv by Matthew Might and David Darais titled “Yacc is dead.” Unfortunately, much of the discussion seems to have centered on whether people think yacc is or should be dead and not on the technical merits of the paper.

Reports of yacc's death, at least in this case, are greatly exaggerated. The paper starts by arguing against the “cargo cult parsing” of putting together parsers by copying and pasting regular expressions from other sources until they work. Unfortunately, the paper ends up being an example of a much worse kind of cargo cult: claiming a theoretical grounding without having any real theoretical basis. That's a pretty strong criticism, but I think it's an important one, because the paper is repeating the same mistakes that led to widespread exponential time regular expression matching. I'm going to spend the rest of this post explaining what I mean. But to do so, we must first review some history.

Grep and yacc are the two canonical examples from Unix of good theory—regular expressions and LR parsing—producing useful software tools. The good theory part is important, and it's the reason that yacc isn't dead.

Regular Expressions

The first seminal paper about processing regular expressions was Janus Brzozowski's 1964 CACM article “Derivatives of regular expressions.” That formulation was the foundation behind Ken Thompson's clever on-the-fly regular expression compiler, which he described in the 1968 CACM article “Regular expression search algorithm.” Thompson learned regular expressions from Brzozowski himself while both were at Berkeley, and he credits the method in the 1968 paper. The now-standard framing of Thompson's paper as an NFA construction and the addition of caching states to produce a DFA were both introduced later, by Aho and Ullman in their various textbooks. Like many primary sources, the original is different from the textbook presentations of it. (I myself am also guilty of this particular misrepresentation.)

The 1964 theory had more to it than the 1968 paper used, though. In particular, because each state computed by Thompson's code was ephemeral—it only lasted during the processing of a single byte—there was no need to apply the more aggressive transformations that Brzozowski's paper included, like rewriting x|x into x.

A much more recent paper by Owens, Reppy, and Turon, titled “Regular-expression derivatives reexamined,” returned to the original Brzozowski paper and considered the effect of using Brzozowski's simplification rules in a regular expression engine that cached states (what textbooks call a DFA). There, the simplification has the important benefit that it reduces the number of distinct states, so that a lexer generator like lex or a regular expression matcher like grep can reduce the necessary memory footprint for a given pattern. Because the implementation manipulates regular expressions symbolically instead of the usual sets of graph nodes, it has a very natural expression in most functional programming languages. So it's more efficient and easier to implement: win-win.

Yacc is dead?

That seems a bit of a digression, but it is relevant to the “Yacc is dead” paper. That paper, claiming inspiration from the “Regular-expression derivatives reexamined” paper, shows that since you can define derivatives of context free grammars, you can frame context free parsing as taking successive derivatives. That's definitely true, but not news. Just as each input transition of an NFA can be described as taking the derivative (with respect to the input character) of the regular expression corresponding to the originating NFA state, each shift transition in an LR(0) parsing table can be described as taking the derivative (with respect to the shift symbol) of the grammar corresponding to the originating LR(0) state. A key difference, though, is that NFA states typically carry no state with them and can have duplicates removed, while a parser associates with each LR(0) parse states a parse stack, making duplicate removal more involved.

Linear vs Exponential Runtime

The linear time guarantee of regular expression matching is due to the fact that, because you can eliminate duplicate states while processing, there is a finite bound on the number of NFA states that must be considered at any point in the input. If you can't eliminate duplicate LR(0) states there is no such bound and no such linear time guarantee.

Yacc and other parser generators guarantee linear time by requiring that the parsing state automata not have even a hint of ambiguity: there must never be a (state, input symbol) combination where multiple possible next states must be explored. In yacc, these possible ambiguities are called shift/reduce or reduce/reduce conflicts. The art of writing yacc grammars without these conflicts is undeniably arcane, and yacc in particular does a bad job of explaining what went wrong, but that is not inherent to the approach. When you do manage to write down a grammar that is free of these conflicts, yacc rewards you with two important guarantees. First, the language you have defined is unambiguous. There are no inputs that can be interpreted in multiple ways. Second, the generated parser will parse your input files in time linear in the length of the input, even if they are not syntactically valid. If you are, say, defining a programming language, these are both very important properties.

The approach outlined in the “Yacc is dead” paper gives up both of these properties. The grammar you give the parser can be ambiguous. If so, it can have exponentially many possible parses to consider: they might all succeed, they might all fail, or maybe all but the very last one will fail. This implies a worst-case running time exponential in the length of the input. The paper makes some hand-wavy claims about returning parses lazily, so that if a program only cares about the first one or two, it does not pay the cost of computing all the others. That's fine, but if there are no successful parses, the laziness doesn't help.

It's easy construct plausible examples that take exponential time to reject an input. Consider this grammar for unary sums:

S → T
T → T + T | N
N → 1

This grammar is ambiguous: it doesn't say whether 1+1+1 should be parsed as (1+1)+1 or 1+(1+1). Worse, as the input gets longer there are exponentially many possible parses, approximately O(3ⁿ) of them. If the particular choice doesn't matter, then for a well-formed input you could take the first parse, whatever it is, and stop, not having wasted any time on the others. But suppose the input has a syntax error, like 1+1+1+...+1+1+1++1. The backtracking parser will try all the possible parses for the long initial prefix just in case one of them can be followed by the erroneous ++1. So when the user makes a typo, your program grinds to a halt.

For an example that doesn't involve invalid input, we can use the fact that any regular expression can be translated directly into a context free grammar. If you translated a test case that makes Perl's backtracking take exponential time before finding a match into a grammar, the translated case would make the backtracking parsers in this paper take exponential time to find a match too.

Exponential run time is a great name for a computer science lab's softball team but in other contexts is best avoided.

Approaching Ambiguity

The “Yacc is dead” paper observes correctly that ambiguity is a fact of life if you want to handle arbitrary context free grammars. I mentioned above the benefit that if yacc accepts your grammar, then (because yacc rejects all the ambiguous context free grammars, and then some), you know your grammar is unambiguous. I find this invaluable as a way to vet possible language syntaxes, but it's not necessary for all contexts. Sometimes you don't care, or you know the language is ambiguous and want all the possibilities. Either way, you can do better than exponential time parsing. Context free parsing algorithms like the CYK algorithm or the Generalized LR parsing can build a tree representing all possible parses in only O(n³) time. That's not linear, but it's a far cry from exponential.

Another interesting approach to handling ambiguity is to give up on context free grammars entirely. Parsing expression grammars, which can be parsed efficiently using packrat parsing, replace the alternation of context free grammars with an ordered (preference) choice, removing any ambiguity from the language and achieving linear time parsing. This is in some ways the same approach yacc takes, but some people find it easier to write parsing expression grammars than yacc grammars.

These are basically the only two approaches to ambiguity in context free grammars: either handle it (possible in polynomial time) or restrict the possible input grammars to ensure linear time parsing and as a consequence eliminate ambiguity. The obvious third approach—accept all context free grammars but identify and reject just the ambiguous ones—is an undecidable problem, equivalent to solving the halting problem.

Cargo cults

The “Yacc is dead” paper begins with a scathing critique of the practice of parsing context free languages with (not-really-)regular expressions in languages like Perl, which Larry Wall apparently once referred to as “cargo cult parsing” due to the heavy incidence of cut and paste imitation and copying “magic” expressions. The paper says that people abuse regular expressions instead of turning to tools like yacc because “regular expressions are `WYSIWYG'—the language described is the language that gets matched—whereas parser-generators are WYSIWYGIYULR(k)—`what you see is what you get if you understand LR(k).' ”

The paper goes on:

To end cargo-cult parsing, we need a new approach to parsing that:

• handles arbitrary context-free grammars;
• parses efficiently on average; and
• can be implemented as a library with little effort.

Then the paper starts talking about the “Regular-expression derivatives reexamined” paper, which really got me excited. I hoped that just like returning to derivatives led to an easy-to-implement and oh-by-the-way more efficient approach to regular expression matching, I had high hopes that the same would happen for context free parsing. Instead, the paper takes one of the classic blunders in regular expression matching—search via exponential backtracking because the code is easier to write—and applies it to context free parsing.

Concretely, the paper fails at goal #2: “parses efficiently on average.” Most arbitrary context-free grammars are ambiguous, and most inputs are invalid, so most parses will take exponential time exploring all the ambiguities before giving up and declaring the input unparseable. (Worse, the parser couldn't even parse an unambiguous S-expression grammar efficiently without adding a special case.)

Instead of ending the supposed problem of cargo cult parsing (a problem that I suspect is endemic mainly to Perl), the paper ends up being a prime example of what Richard Feynman called “cargo cult science” (Larry Wall was riffing on Feynman's term), in which a successful line of research is imitated but without some key aspect that made the original succeed (in this case, the theoretical foundation that gave the efficiency results), leading to a failed result.

That criticism aside, I must note that the Haskell Scala code in the paper really does deliver on goals #1 and #3. It handles arbitrary context-free grammars, it takes little effort, and on top of that it's very elegant code. Like that Haskell Scala code, the C regular expression matcher in this article (also Chapter 9 of The Practice of Programming and Chapter 1 of Beautiful Code) is clean and elegant. Unfortunately, the use of backtracking in both and the associated exponential run time makes the code much nicer to study than to use.

Is yacc dead?

Yacc is an old tool, and it's showing its age, but as the Plan 9 manual says of lex(1), “The asteroid to kill this dinosaur is still in orbit.” Even if you think yacc itself is unused (which is far from the truth), the newer tools that provide compelling alternatives still embody its spirit. GNU Bison can optionally generate a GLR parser instead of an LALR(1) parsers, though Bison still retains yacc's infuriating lack of detail in error messages. (I use an awk script to parse the bison.output file and tell me what really went wrong.) ANTLR is a more full featured though less widespread take on the approach. These tools and many others all have the guarantee that if they tell you the grammar is unambiguous, they'll give you a linear-time parser, and if not, they'll give you at worst a cubic-time parser. Computer science theory doesn't know a better way. But any of these is better than an exponential time parser.

So no, yacc is not dead, even if it sometimes smells that way, and even if many people wish it were.

Go is defined to be a safe language. Indices into array or string references must be in bounds; there is no way to reinterpret the bits of one type as another, no way to conjure a pointer out of thin air; and there is no way to release memory, so no chance of “dangling pointer” errors and the associated memory corruption and instability.

In the current Go implementations, though, there are two ways to break through these safety mechanisms. The first and more direct way is to use package unsafe, specifically unsafe.Pointer. The second, less direct way is to use a data race in a multithreaded program.

If you were going to build an environment that ran untrusted Go code, you'd probably want to change the available packages to restrict or delete certain routines, like os.RemoveAll, and you'd want to disallow access to package unsafe. Those kinds of restrictions are straightforward.

The data races that can be used to break through the usual memory safety of Go are less straightforward. This post describes the races and how to rearrange the data structures involved to avoid them. Until the Go implementations have been tuned more, we won't be able to measure whether there is a significant performance difference between the current representation and the race-free implementation.

Package Unsafe

Here's a simple packaging of a type that lets you edit arbitrary memory locations, built using the standard package unsafe:

import "unsafe"

type Mem struct {
 addr *uintptr // actually == &m.data!
 data *uintptr
}

// Peek reads and returns the word at address addr.
func (m *Mem) Peek(addr uintptr) uintptr {
 *m.addr = addr
 return *m.data
}

// Poke sets the word at address addr to val.
func (m *Mem) Poke(addr, val uintptr) {
 *m.addr = addr
 *m.data = val
}

func NewMem() *Mem {
 m := new(Mem)
 m.addr = (*uintptr)(unsafe.Pointer(&m.data))
 return m
}

(The Go type uintptr is an unsigned integer the size of a pointer, like uint32 or uint64 depending on the underlying machine architecture.)

The key line is near the bottom, the use of the special type unsafe.Pointer to convert a **uintptr into a *uintptr. Dereferencing that value gives us m.data (actually a *uintptr) interpreted as a uintptr. We can assign an arbitrary integer to *m.addr, that changes m.data, and then we can dereference the integer as *m.data. In other words, the Mem struct gives us a way to convert between integers and pointers, just like in C. There are no races here: this is just something you can do by importing unsafe. The Mem wrapper is a bit convoluted—normally you'd just use unsafe directly—but we're going to drop in a different implementation of NewMem that doesn't rely on unsafe.

A Race

The current Go representation of slices and interface values admits a data race: because they are multiword values, if one goroutine reads the value while another goroutine writes it, the reader might see half of the old value and half of the new value.

Let's provoke the race using interface values. In Go, an interface value is represented as two words, a type and a value of that type. After these declarations:

var x *uintptr

var i interface{} = (*uintptr)(nil)
var j interface{} = &x

The data structures for i and j look like:

Suppose we kick off a goroutine that alternately assigns i and j to a new interface value k:

var k interface{}

func hammer() {
 for {
  k = i
  k = j
 }
}

After each statement executes, k will look like either i or j, but during the assignment, there will be a moment when k is half i and half j, one of these:

The top case gives us a **uintptr nil, which we could obtain more easily via legitimate means, but the bottom case gives us the value &x (actually a **uintptr) interpreted as a *uintptr. If we can catch the interface when it looks like the case on the right, we'll have rederived the conversion we used above via unsafe. Based on that insight, we can rewrite NewMem without unsafe:

func NewMem() *Mem {
 fmt.Println("here we go!")

 m := new(Mem)

 var i, j, k interface{}
 i = (*uintptr)(nil)
 j = &m.data

 // Try over and over again until we win the race.
 done := false
 go func(){
  for !done {
   k = i
   k = j
  }
 }()
 for {
  // Is k a non-nil *uintptr?  If so, we got it.
  if p, ok := k.(*uintptr); ok && p != nil {
   m.addr = p
   done = true
   break
  }
 }
 return m
}

The same kind of race happens in all of Go's mutable multiword structures: slices, interfaces, and strings. In the case of slices, the trick is to get a pointer from one slice and a cap from a different one. In the case of strings, the trick is to get a pointer from one string and the len from a different one. (The string race isn't as interesting, because strings cannot be written to, so it would only let you read memory, not write it.)

The Fix

The race is fundamentally caused by being able to observe partial updates to Go's multiword values (slices, interfaces, and strings): the updates are not atomic.

The fix is to make the updates atomic. In Go, the easiest way to do that is to make the representation a single pointer that points at an immutable structure. When the value needs to be updated, you allocate a new structure, fill it in completely, and only then change the pointer to point at it. This makes the assignment atomic: another goroutine reading the pointer at the same time sees either the new data or the old data, but not a mix, assuming the compiler is careful to read the pointer just once and then access both fields using the same pointer value.

(The red border indicates immutable data.)

For slices and strings, it makes sense to keep the multiword representation but put an immutable ”pointer and cap” stub structure between the slice and the underlying array. This keeps the same basic efficiency properties of slices at the cost of a few extra instructions on each indexing operation.

The idea here is to keep a structure with a mutable offset and length to support efficient slicing but replace the pointer with an immutable base+length pair. Any access to the underlying data must check the final offset against the immutable cap. Copying slice values is still not an atomic operation, but an invalid len will not keep an out-of-bounds index from being caught.

This representation requires a couple more assembly instructions, because each index must be checked against two bounds, first the relative len and then the absolute cap:

LEAL x, SI
MOVL i, CX
CMPL CX, 4(SI)
JGE panic




MOVL 0(SI), DI
MOVL (4*CX)(DI), AX

LEAL x, BX
MOVL i, CX
CMPL CX, 4(BX)
JGE panic
ADDL 8(BX), CX
MOVL 0(BX), SI
CMPL CX, 4(SI)
JGE panic
MOVL 0(SI), DI
MOVL (4*CX)(DI), AX

 
 
// i >= len?
 
 
// i+off >= cap?
 
// &x[0] -> SI
// x[i] (or x[i+off]) -> DI
 

With suitable analysis, an optimizing compiler could cache 0(BX), 4(BX), 8(BX), and 4(SI), so in a loop, it is possible that the new representation would run at the same speed as the original.

An ambitious implementation might continue to use the current data structures for slices, interfaces, and strings stored on the stack, because data on the stack can only be accessed by the goroutine running on that stack. (Local variables whose addresses might escape to other goroutines are already allocated on the heap automatically, to avoid dangling pointer bugs after a function returns.)

Garbage Collection

This fix is feasible only because Go is a garbage-collected language: we can treat the red stub structures as immutable and trust that the garbage collector will recycle the memory only when nothing points to them anymore. It's much harder to build a safe language without a garbage collector to fall back on.

Security Implications

It is important to note that these races do not make the current implementations any less secure than they already are. The races allow clever programmers to subvert Go's memory safety, but a less clever programmer can still use the aptly-named package unsafe.

These races only matter if you are trying to build a Go service that can safely run arbitrary code supplied by untrusted programmers (and to the best of my knowledge, there are no such services yet). In that situation, you'd already need to change the implementations to disable access to the unsafe package and remove or restrict functions like os.Remove or net.Dial. Changing the data representations to be race free is just one more change you'd have to make. Now you know, not just that a change is needed but also what the change is.

The races exist because the data representations were chosen for performance: the race-free versions introduce an extra pointer, which carries with it the cost of extra indirection and extra allocation. Once the Go implementations are more mature, we'll be able to evaluate the precise performance impact of using the race-free data structures and whether to use them always or only in situations running untrusted code.

This script sets up forwarding for a few basic services, it should be pretty easy to extend with anything needed.

Services are ssh, ftp (with ports specified for passive mode) and http

#! /bin/sh

### BEGIN INIT INFO
# Provides:          forwarding
# Required-Start:    $network
# Required-Stop:     $network
# Default-Start:     2 3 4 5
# Default-Stop:      0 1 6
# Short-Description: Script that sets up forwarding for ssh, ftp and web external acces
# Description:       Script that sets up forwarding for ssh, ftp and web external acces
### END INIT INFO

NAME=forwarding
DESCRIPTION="Script that sets up forwarding for ssh, ftp and web external acces"
CMD=/root/bin/upnpc-static

# Exit if the package is not installed
test -x $CMD || exit 0

# Load the VERBOSE setting and other rcS variables
[ -f /etc/default/rcS ] && . /etc/default/rcS

# Define LSB log_* functions.
# Depend on lsb-base (>= 3.0-6) to ensure that this file is present.
. /lib/lsb/init-functions

do_start () {
    log_daemon_msg "Starting $DESCRIPTION" "$NAME"
    CMD="$CMD -r 22 TCP 21 TCP 80 TCP"
    for port in $(seq 49152 49170); do
        CMD="$CMD $port TCP"
    done
    $CMD 1>&2 > /dev/null
    log_end_msg $?
    return $?
}

do_stop () {
    log_daemon_msg "Stopping $DESCRIPTION" "$NAME"
    CMD="$CMD -d 22 TCP 21 TCP 80 TCP"
    for port in $(seq 49152 49170); do
        CMD="$CMD $port TCP"
    done
    $CMD 1>&2 > /dev/null
    log_end_msg $?
    return $?
}

case "$1" in
    start)
    do_start
    ;;
    stop)
    do_stop
    ;;
    restart|force-reload)
    do_stop 
    do_start
    ;;

    *)
    log_success_msg "Usage: $0 {start|stop|restart|force-reload}"
    exit 1
esac

exit 0

bash function wi_findclient

  wi_findclient () {
    for i in $(wmiir ls /client); do
        if wmiir cat "/client/$i/props" |grep -q $1; then
            echo $i;
        fi;
    done
  }

I just added this to my ~/.bashrc

kvirc setup

in the event editor three events need to be added, i just named all of them wmii

OnHighlight event

run bash -i -c "echo urgent on | wmiir write /client/wi_findclient kvirc4/ctl";

OnQueryMessage event

run bash -i -c "echo urgent on | wmiir write /client/wi_findclient kvirc4/ctl";

OnWindowActivated event

run bash -c "echo urgent off | wmiir write /client/sel/ctl";

That should do it

In any market, as in any poker game, there is a fool.  The astute investor Warren Buffet is fond of saying that any player unaware of the fool in the market probably is the fool in the market. [..] Salomon bond traders knew about fools because that was their job. Knowing about markets is knowing about other people's weaknesses.

Best of all, he [guy teachings the new employees] gave us a rule of thumb about information in the markets that I later found useful: "Those who say don't know, and those who know don't say"

In the stock market the more elaborate and abstruse the mathematics the more uncertain and speculative the conclusion we draw therefrom... Whenever calculus is brought in, or higher algebra, you could take it as a warning signal that the operator was trying to substitute theory for experience" (quoting Benjamin Graham)

[Donnie Green] is remembered as the man who stopped a callow young salesman on his way out the door to catch a flight from New York to Chicago. Green tossed the salesman a ten-dollar bill. "Hey, take out some crash insurance for yourself in my name," he said. "Why?" asked the salesman. "I feel lucky," said Green.

I'm convinced that the worst thing a man can do with a telephone without breaking the law is to call someone he doesn't know and try to sell that person something he doesn't want. 

"Customers have very short memories." (quoting Tom Strauss, President of Salomon Brothers, on the topic of screwing customers.)

The nature of the game is zero sum. A sollar out of my customer's pocket was a dollar in ours, and vice versa.

 Investment banking in America is a long-standing oligopoly [...] American investors (the lenders of money) have been trained to think that they can only do business with a handful of large investment banks.

Note to members of all governments: Be wary of Wall Streeters threatening crashes. They are tempted to do this whenever you encroach on their turf. But they can't cause a crash any more than they can prevent one.

Monday, 10 Sept 2010 - not DEFUNCT, DE-FUNKED, or de.FUNC(t)

The non-arrival of a long-ago promised update to the qemu images and gridtools, as well as the lack of any other posts or announcements, might lead a casual observer to conclude that 9gridchan.org is adrift and falling into the swamp of bitrotting and abandoned open-source projects. We (the royal we) categorically deny this, and will now justify our seeming Sloth and explain our current projects.

Why no update to the qemu images? That has a pretty simple answer: complexity creep. The prototype updated qemu images I was working on included my "rootlessboot" modifications to the startup process and then an additional parameterized set of scripts for users to create new system images with various roles and attributes. I had the sudden realization I was probably the only user for these features and most downloaders and users would simply perceive an incomprehensible divergence from standard Plan 9. My own use of these and other modifications is driven by the desire to really explore the possibilities of distributed network architecture, and I have the time and interest to set up networks of multiple machines and VMs and spend a lot of time configuring them. Adding a lot of new knobs was useful for that, but was not going to be a benefit for the majority of potential users.

So, I did what any flaky hobbyist developer does when they realize their project is drifting into the realm of "only its author has any clue how or even why to use it" - I slacked off and waited for a Better Idea to come along to refocus what I was doing.

The #plan9chan irc channel on freenode is where 9gridchan stays active (for sufficiently relaxed definitions of "active") even when we seem to be completely moribund judging by the website. A lot of the discussion is only vaguely related to plan 9 and grids, but that is a feature, not a bug (and also why we have a project-specific channel, since a lot of it would be noise, not signal, in the main #plan9). At some point in a discussion of information-based economies, a channel veteran mentioned Satoshi Nakamoto's Bitcoin software as an example of a decentralized system that might be of interest.

Sudden change of topic: I'm a long-time player of games like Chess, turn-based strategy video games, and Magic: the Gathering. I've often talked about making some kind of bizarre Plan 9 high-concept strategy game based on namespace operations. The closest I ever got to actually making anything was a few skeleton filesystems with large trees of folders with the names of different nouns and verbs, where you could bind them into semantically meaningful strings.

Sudden change of topic: In general I've taken the position that Plan 9 and 9p represent an alternative to our modern http-centric approach to network services and applications. I also felt that trying to use plan 9 as the backend for browser based services wouldn't promote and encourage the direct use of Plan 9, which is a major goal of this project.

Obligatory sudden integration of topics: So here's the idea - use a network of plan 9 nodes as backend game servers that are "factories" for unique digital objects that are game pieces for an in-browser strategy game. Plan 9 adoption is encouraged because running a plan 9 game node/server means that you are able to create your own customized game pieces. The consistency and fairness of the game is guaranteed using cryptographic principles inspired by Bitcoin. The game itself is similar to a collectibe card or miniatures game. Plan 9 systems create and distribute unique game pieces to web-browser client players who use a subset of the game pieces they control to engage in strategic combat. Game flavor will be customizable, but a fantasy-themed example may make the concept clear. A browser based player is like a knight entering combat; a Plan 9 node operator is like the king hosting the fight and the armorsmith providing the weapons.

Still mostly but not completely vaporware. There's nothing worth presenting to the public yet, but I've been working on this idea for several weeks now and have built working prototype code for the basic systems needed. contrib/mycroftiv/unreleased/rsagame has an already-outdated set of utilities and experiments, and a few hapless victims have poked at the "square character battling engine" in the browser which I could link a screenshot of but won't because it looks really dumb at the current point in time. What needs to be done is to integrate these two pieces, (converting some rc scripts to C in the process) and then replace the placeholder battle code with the worked-out-on-pen-and-paper game system, and update the browser client code to interact with it.

Can we get the Hollywood quick-sell version of the idea? Sure thing - its Plan 9 meets Bitcoin meets Magic:the Gathering meets Farmville!

How long before a beta? Will 9gridchan.org be hosting a server for the game? I'm extremely unreliable as to schedules, but I'd like to have something for people to poke at sometime during October. I'll definitely be hosting game server(s) but I might use a different domain name

Will it all still be free as in freedom and free as in beer? I have a strong commitment to open source code so all server and client side code will absolutely be available. I will, however, be using Affero GPL 3 for large portions of it. I'm aware this is a license with many restrictions, but the goal is to preserve user access to source code. I also have no current expectation that this game project will attract any users or popularity whatsoever so it is 99.99% likely to be monetarily free forever also. On the 0.001% chance that the game attracts an enthusiastic and growing user community that wants me to provide multiple game servers or add professional quality art assets to the game I might investigate ways of letting people pay me to provide a way of growing the project. Availability of source means free play would always exist and the intention of this project is just to create something cool and fun to promote Plan 9. I will admit though that figuring out a way to use an os-agnostic browser based hook to try to get people to start using plan 9 in order to achieve higher power/status in a videogame definitely appeals to me, bwahahaha!

Needless to say, we are still supporting all our current services and software.

"Believe it or not -- I've been able to convince people to add more money -- which is what I'm doing as well.  No one has redeemed as far as I've seen."

Cioffi was growing increasingly nervous about his hedge fnds and initiated the process of removing $2 million of the $6 million that he personally had investe din the Enhanced Leverage Fund.

After Goldman sent out the marks in the $0.50 to $0.55 range, Fanlo called Cohn and told him, "You're way off market. Everyone else is at 80, 85." Cohn then offere to sell Fanlo $10 billion of the paper at his $0.55 price and encouraged him to sell that in the market to all the other broker-dealers at the higher price they claimed to be marking the paper at. [...] "you can sell them to every one of those dealers," Cohn told him. "Sell 80, sell 77, sell 76, sell 75. Sell them all the way down to 60. And I'll sell them to you at my mark, at 55, because I was trying to get out. So if you can do that, you can make yourself $5 billion right now." Cohn had been trying to sell the securities at 55 for a period of time and people would just hang up on him. A few days later, Fanlo called Cohn back. "He cam back and said, 'I think your mark might be right,'" Cohn said.

"Can't say if Warren knew or if the trading desk knew, but personally I thought the notion of packaging the most opaque and complicated securities into a complicated structure and then selling it via an IPO to the widows and orphans of the world was on eof the most bizarre ideas I'd ever heard"

"The wacko Everquest deal was saved from being the dumbest idea ever in the history of the world by not being done," Paul Friedman said. "I mean, 'Let's take CDO equity and residuals and all this stuff, and let's package it up an do a deal and sell it to Mom and Pop.' Nobody's ever come up with a stupider idea in history. Had the funds not blown up, Ithink there's a chance they would have actually tried to bring it to market. That's another indication that there were no grown-ups minding the shop."

Back in 2005, before JavaScript was required for everything on the web, I created a toy language called webscript, to let you script automatic web interactions. I wanted to use webscript to replace some clunky wget-based shell scripts we were using to do things like track packages and reboot computers. Two real webscript programs illustrate the language.

This used to work for tracking UPS packages:

#!./webscript

load "http://www.ups.com/WebTracking/track?loc=en_US"
find textbox "InquiryNumber1"
input "1z30557w0340175623"
find next checkbox
input "yes"
find prev form
submit
if(find "Delivery Information"){
 find outer table
 print
}else if(find "One or more"){
 print
}else{
 print "Unexpected results."
 find page
 print
}

And this used to work to connect to a APC power strip and reboot the computer named yoshimi:

#!./webscript

load "http://apc-reset/outlets.htm"
print
print "\n=============\n"
find "yoshimi"
find outer row
find next select
input "Immediate Reboot"
submit
print

I say that the scripts used to work because I haven't run them in a few years. One of the goals of webscript was to let the programmer describe the interactions with the web page instead of working with the raw form parameters, so that scripts would even as the hidden plumbing behind the web page changed. Even so the UPS script mentions InquiryNumber1.

Every few years I go looking for a replacement for webscript, but I never find anything. As more web sites require JavaScript to do anything useful, the job of implementing something like webscript gets harder. I think you'd essentially have to link against a browser to make it work.

Do you know of a tool like webscript that works with today's web pages? Do you know an easy way to make one? (I know about AppleScript and Chickenfoot, but I'd prefer something that can run and produce output as a command line program, without even displaying a web browser on my screen, so that it can be used in shell scripts and cron jobs.)

According to EW math, the more buzz or intelligence you have, the less likely you are to be on the It List. That may be true, but I bet you didn't mean that. Your equation is art-directed nonsense. EW seems to think the joke is that the equations look cute: If Einstein is funny, his square root is hilarious...

While George Soros was spending lavishly to promote democracy abroad, Mr. Scaife was spending lavishly to undermine it at home.

So i was at a conference three weeks ago called RMLL, they didn't have wi-fi at the "villages" we stayed in, just a captive portal with a 24 hour free trial (of course activated by sms so they have your cell number afterwards and can harass you with pr bullshit).

The thing is that their captive portal did a http permanent redirect to their portal, so now all of my feeds in liferea point to their fucking website. way to go motherfuckers, now i can manually go through my 100 feeds and rewrite the url? or what?

anyone who has a good beefy connection can ping -f wifirst.net