Category Archives: Technology

General Tech

Preliminary Sketch for F Natural

February 16, 2014 Bill Leave a comment

I’ve gone back to F♮, but decided to abandon the Perl implementation in favour of Java. I might be able to target the Java VM, but I’m not sure yet. In any case it’s a good chance to brush up my Java and learn IntelliJ IDEA (CE). I’m using SableCC to parse, and I’ve just got Log4j working. I’m long overdue writing some unit tests but for the moment, after a week or so, I have a working interpreter and the following sample script that runs as advertised:

// "env foo { ... }" is shorthand for
// "def foo = env { ... };".
// "env { ... }" extends the current environment,
// evaluates the block in
// the extended environment, then returns
// the extended environment
env math {
    // "fn bar (...) {...}" is shorthand for
    // "def bar = fn(...) {...};"
    fn square(x) { x * x }
    fn adder(x) {
        fn (y) { x + y } // demonstrates closure
                         // and anonymous functions
    }
    env highermath {
        fn cube(x) { x * square(x) } // finds square in
    }                                // the enclosing environment
}

env badmath {
    fn square(x) {
        x + 1;
    }
    env highermath {
        fn square(x) { x * badmath.square(x) } // finds badmath in
    }                                          // the root environment
}

def a = 10;

// "." is the lookup operator:
// lhs is an expression evaluating to an environment,
// rhs is asymbol to look up.
// "." binds more tightly than "(…)":
print( math.square(a) ); // 100

// "if/else" is an expression returning a value,
// not a statement
// so there is no need for the
// ternary "?:" operator.
// here "if" returns a function to call:
print(
    if (a == 5) { math.square }
    else { math.highermath.cube }(a)
); // 1000

// here "if" returns an environment in which
// we look up a function:
print(
    if (a == 5) { math }
    else { badmath.highermath }.square(a)
); // 110

// call a function to get a function
// then call that:
print(math.adder(5)(22)); // 27

// a string is a linked list of chars
// chars are written 'x'
// strings are written "abc"
// "@" is cons (right associative)
// "@@" is append (right associative)
// linked lists can also be written between '[' and ']'
print( 'a' @ 'b' @ "cd" @@ "ef" @@ ['g', 'h'] ); // "abcdefgh"

// "env foo { ... }" is shorthand for

// "def foo = env { ... };".

// "env { ... }" extends the current environment,

// evaluates the block in

// the extended environment, then returns

// the extended environment

env math {

// "fn bar (...) {...}" is shorthand for

// "def bar = fn(...) {...};"

fn square(x) { x * x }

fn adder(x) {

fn (y) { x + y } // demonstrates closure

// and anonymous functions

}

env highermath {

fn cube(x) { x * square(x) } // finds square in

} // the enclosing environment

}

env badmath {

fn square(x) {

x + 1;

}

env highermath {

fn square(x) { x * badmath.square(x) } // finds badmath in

} // the root environment

}

def a = 10;

// "." is the lookup operator:

// lhs is an expression evaluating to an environment,

// rhs is asymbol to look up.

// "." binds more tightly than "(…)":

print( math.square(a) ); // 100

// "if/else" is an expression returning a value,

// not a statement

// so there is no need for the

// ternary "?:" operator.

// here "if" returns a function to call:

print(

if (a == 5) { math.square }

else { math.highermath.cube }(a)

); // 1000

// here "if" returns an environment in which

// we look up a function:

print(

if (a == 5) { math }

else { badmath.highermath }.square(a)

); // 110

// call a function to get a function

// then call that:

print(math.adder(5)(22)); // 27

// a string is a linked list of chars

// chars are written 'x'

// strings are written "abc"

// "@" is cons (right associative)

// "@@" is append (right associative)

// linked lists can also be written between '[' and ']'

print( 'a' @ 'b' @ "cd" @@ "ef" @@ ['g', 'h'] ); // "abcdefgh"

Apart from the env directive, and the fact that strings are lists of chars, this is still very much a scheme interpreter with a more syntax laden parser in front of it, but it’s early days. Next steps:

Get unit tests in place. I’ve delayed too long.
Implement an implicit strong type-checking visitor (I’m falling out of love with the Visitor pattern, but SableCC gives me no choice.)
Replace the variable implementation with the same logic variables used by the type checker.
Add algebraic data types a la ML. This should look like:

typedef List(t) { Pair(t, List(t)) | Null }

1

typedef List(t) { Pair(t, List(t)) | Null }

(except that List is already predefined.) t is a type variable, so this says A List of some type t is either a Pair of a t and a List of t, or it is Null. Pair and Null become type constructors for type List(t), so Pair('c', Null) creates a list of length 1 with type List(char). Like I said, we already have lists, and h @ t is (cons h t), e.g. Pair(h, t).
Extend the function definition to allow pattern matching (actually unification). This would look like:

fn map { (f, []) { [] } (f, h @ t) { f(h) @ map(f, t) } }

1
2
3
4

fn map {
(f, []) { [] }
(f, h @ t) { f(h) @ map(f, t) }
}

so the formal arguments to the function can optionally be moved inside the function body, and repeated with alternative formats, like a case statement. The format that unifies with the actual arguments has its body evaluated with the relevant variables bound.
Rewrite to CPS, add failure continuations, implement amb as a binary operator then:

def name = "Fred" then "Charlie";

1

def name = "Fred" then "Charlie";
Implement fail as a keyword of no arguments:

fn require(x) { if (x) { true } else { fail } }

1

fn require(x) { if (x) { true } else { fail } }

(That last one might give the type checker a headache.)

Languages, Technology

Garbage Collection

February 16, 2014 Bill Leave a comment

One of the defining features of a high-level language like Scheme, Perl, PHP or almost any other recent language is that they have built-in garbage collection (GC), which makes the programmers life much easier because they don’t have to worry about memory management too much. However there are different GC strategies, and costs and benefits depending on the choices you make. I’d like to talk a little about the common GC strategies here, so you can see what the trade-offs are.

Reference Counting Garbage Collection

Unfortunately for both Perl and PHP they made a bad choice of garbage collector; they both opted for the simplest possible mechanism, that is reference counting. Why it is a bad choice I hope to demonstrate.

Reference counting is simple. Each object being memory-managed has a reference-count field which is incremented whenever a new variable refers to the object, and decremented when a variable stops referring to that object. If the reference count reaches zero, nothing can be referring to that object and it can be immediately returned to the free store, decrementing the reference counts of any objects it may contain in turn.

Now this is initially quite attractive: one of the very attractive features, beyond its simplicity, is that garbage collection happens in tiny little steps, and does not usually interfere with the flow of the program, in contrast to Mark-and-Sweep GC discussed below. The real problem with it is that it doesn’t work, at least not in all cases.

The cases where it doesn’t work are where there are circular references between structures. If we imagine a situation where A refers to B, B to C and C back to A, and we have an additional reference X also referring to A, and nothing else, then A will have a reference count of 2 (one from X, one from C), and B and C a reference count of 1. Now when X stops referring to A, A’s reference count will be decremented to 1, but now that entire cyclic structure of A, B and C is cut adrift: since nothing external refers to it, no reference counts can ever be decremented again, and A B and C all still have reference counts of 1.

There are some fancy tricks in Perl to try to work around the problem, specifically weak references which are references that do not disturb the reference counts, but they are probably more difficult to reason about than simple memory management in low-level languages and so are not a valid solution. Another solution is to have a “guard” object acting as a wrapper around the cyclic structure. If the guard object’s reverence count goes to zero its DESTROY method will be invoked, and it then explicitly tells the cyclic structure to remove the circular references so that the components can be recovered. Again this is making memory management the programmers concern.

Mark and Sweep Garbage Collection

This is a strategy that at least works in all cases, but has significant drawbacks. With mark and sweep, a “Free List” of objects is maintained that can be used for their space. A normal request for memory will retrieve an object from the free list and put it on to an “in Use” list. If there are no objects available on the free list, then Mark and Sweep Garbage collection is invoked. Mark and Sweep, as its name suggests, proceeds in two stages. The first is to follow all pointers from the current execution context, recursively, and to “mark” all objects found as “in use”. The next phase, the “Sweep” phase, traverses the “In Use” list and moves any objects not marked as in use to the free list (also resetting the “mark” on all objects).

The problem is that in a typical application the majority of the objects on the “In Use” list will not be actually in use, and the sweep phase will use a lot of resources moving unused objects back to the free list. This can produce a pronounced “stutter” in interactive programms, where they appear to hang for seconds at a time. This behaviour was a common failing of early Lisp implementations, and one solution there was to provide a (gc) command that the programmer could sprinkle around the code in order that the number of unused objects on the used list never got too big. Again this is passing memory management back to the programmer, albeit at a higher level.

Copying Garbage Collection

The realisation that most supposedly in-use objects actually are not in use is a clue to a more time efficient (but not space-efficient) garbage collection strategy.

To get it to work we have to drop the high-level notion of lists, and instead get down to the machine level and consider free pools and in-use pools, where a pool is just a contiguous region of memory on the heap.

Basically, instead of moving everything that isn’t in use from the in-use pool to the free pool, we move what is in use, as we find it during the mark phase, to the “free pool” then we swap the ponters to the two pools: so the free pool becomes the in-use pool and vice versa. We know that the free pool was initially empty otherwise garbage collection would not have been invoked. Of course that means we can no longer have an explicit (gc) command, but that’s not a bad thing. It also means we can dispose of the Sweep phase altogether.

The remaining details are fairly simple: when moving an object from the in-use pool to the free pool, we must leave a note behind to say that it has been moved, and where it has been moved to. We replace the old copy of the object with a “forwarding pointer” with a flag to say that it has been forwarded. That way any further encounters of the object during garbage collection merely update their pointers to refer to the new copy and then stop, because the object and its contents have already been moved.

Generational Garbage Collection

Another observation about the memory usage of typical applications provides a more time efficient variation on Copying Garbage Collection. That observation is “the longer an object has persisted, the longer it is likely to persist”.

To leverage that observation, we divide our heaps into “generations”. The most recent generation being the objects that have not yet been through a garbage collection. Generational Garbage collection inspects the most recent generation of in-use objects first, and if it can reclaim enough space there its job is done. It moves objects still in use to the next generation, and so on (the choice of the number of generations is presumably configurable, and the oldest generation falls back to standard Copying Garbage collection behaviour.)

More details needed, later…

Languages, Technology

A Bit on the Lambda Calculus

February 16, 2014 Bill Leave a comment

In my book I briefly mention (in a footnote I think) the lambda calculus. It’s probably time to expand on that. As I said, the lambda calculus is a mathematical discipline that predates computers, but is amazingly relevant to computer language design. Basically it assumes that there are nothing but functions, each taking only one argument, and it derives all possible computations from them.

I won’t bother describing the specific syntax right now, rather let’s take a look at a translation of some of it into Perl.

First off, functions can only take one argument. So how do we imitate functions, such as addition, that require more than one argument? The answer is a technique called “Currying” (after the mathematician Haskell Curry who gave the better part of his name to a programming language.) To summarise, a “Curried” function of two arguments is a function that takes one argument and returns a function that takes a second argument and returns the result. So for example Currying a perl function add:

my $add = sub {
    my ($a, $b) = @_;
    $a + $b;
}

my $add = sub {

my ($a, $b) = @_;

$a + $b;

}

(using anonymous subs throughout for consistency) produces:

my $add = sub {
    my ($a) = @_;
    sub {
        my ($b) = @_;
        $a + $b;
    }
}

my $add = sub {

my ($a) = @_;

sub {

my ($b) = @_;

$a + $b;

}

which you can call like:

$add->(3)->(4);

1	$add->(3)->(4);

to get 7.

More interestingly, we can represent truth and falsehood as functions. Assuming implicit Currying from now on, true can be represented as a function that takes two arguments and returns its first one:

my $true = sub {
    my ($a, $b) = @_;
    $a;
}

my $true = sub {

my ($a, $b) = @_;

$a;

}

and false similarily as a function that returns its second argument:

my $false = sub {
    my ($a, $b) = @_;
    $b;
}

my $false = sub {

my ($a, $b) = @_;

$b;

}

Now we can represent the conditional if as a function of three arguments:

my $if = sub {
    my ($test, $consequent, $alternative) = @_;
    $test->($consequent, $alternative);
}

my $if = sub {

my ($test, $consequent, $alternative) = @_;

$test->($consequent, $alternative);

}

It just applies the truth value to the consequent and alternative arguments, so if is just syntactic sugar.

What about data structures? The simplest composite data structure is a pair, and we can do that with functions too:

my $cons = sub {
    my ($car, $cdr) = @_;
    sub {
        my (selector) = @_;
        $if->($selector, $car, $cdr);
    }
}

my $car = sub {
    my ($pair) = @_;
    $pair->($true);
}

my $cdr = sub {
    my ($pair) = @_;
    $pair->($false);
}

my $cons = sub {

my ($car, $cdr) = @_;

sub {

my (selector) = @_;

$if->($selector, $car, $cdr);

}

my $car = sub {

my ($pair) = @_;

$pair->($true);

}

my $cdr = sub {

my ($pair) = @_;

$pair->($false);

}

so a pair is a function that takes a truth value and returns the car if it is true and the cdr if it is false, and car and cdr are functions that pass the appropriate truth value to the pair.

(I need to talk here about Church Numerals, when I can figure them out.)

Currying all of the above is left as an exercise for the reader.

So what does the lambda calculus actually look like? Well, it’s very terse. Functions are created by λ.x body where x is the argument, and are called like fa where f is the function and a the argument. Of course you can use brackets to disambiguate, but that’s it, nothing more to it. Here’s my attempt at a definition for if:

λ.t (λ.c (λ.a (tc)a))

1	λ.t (λ.c (λ.a (tc)a))

I hope I got that right: a function taking argument t (test) returning a function taking argument c (consequent) returning a function taking argument a (alternative) which applies t to c, and applies the result to a (remember t is Curried). Phew!

Currying is quite a useful thing to be able to do given support from a language, but it can be difficult to read. For F♮ I hit upon the idea of using a trailing comma to indicate a partial function call:

fn add(a,b) { a + b; }

def add2 = add(2,);

add2(3); // 5

fn add(a,b) { a + b; }

def add2 = add(2,);

add2(3); // 5

Which provides a visual clue to the reader that add() in this example is not being called with all of its arguments and therefore returns a function that expects the rest. Perhaps more practically, something like this is more visually appealing, once you get what the trailing comma means:

map(eval(env,) lst);

1	map(eval(env,) lst);

where we map eval with a supplied first argument env over the items of lst. This avoids having to create a closure:

map( fn (l) { eval(env, l) }, lst);

1	map( fn (l) { eval(env, l) }, lst);

Languages, Technology

Purely Functional Environments

February 16, 2014 Bill Leave a comment

Here’s a different take on environments. In a pure functional language all data is immutable, end of story, and that would apply to any environments implemented in such a paradigm too. Operators like define would not be allowed to modify an environment, instead such operators would have to return a copy of the environment with the modified value. This has some interesting implications for any language using such an environment. For example:

define PI = 3.14159265;
fn printPI { print(PI); }
define PI = 4;
fn printNewPI { print(PI); }
printPI(); // prints 3.14159265
printNewPI(); // prints 4

define PI = 3.14159265;

fn printPI { print(PI); }

define PI = 4;

fn printNewPI { print(PI); }

printPI(); // prints 3.14159265

printNewPI(); // prints 4

So each fn captures the current environment, and since nothing is allowed to change, the environment captured is precisely as it was when it was captured.

So how can we make a functional environment that is even remotely efficient? A standard technique is to implement it as a binary tree. Let’s assume symbols have unique numeric identifiers, so that symbol lookup can be reduced to numeric lookup. Then our environment can be a tree who’s left nodes all have indexes less than the current node, and who’s right nodes all have indexes greater than the current node. Here’s a pair of classes that implement such a tree:

abstract class Env {}

class Node extends Env {
    Env left;
    Env Right;
    int index;
    Datum value;

    Datum lookup(int ix) {
        if (ix < index) {
            return left.lookup(ix);
        } else if (ix > index) {
            return right.lookup(ix);
        } else {
            return value;
        }
    }
}

class EmptyNode extends Env {
    Datum lookup(int id) {
        error(...);
    }
}

abstract class Env {}

class Node extends Env {

Env left;

Env Right;

int index;

Datum value;

Datum lookup(int ix) {

if (ix < index) {

return left.lookup(ix);

} else if (ix > index) {

return right.lookup(ix);

} else {

return value;

}

class EmptyNode extends Env {

Datum lookup(int id) {

error(...);

}

So far so good, but what about extension?

class Node extends Env {
    // ...
    Env extend(int ix, Datum val) {
        if (ix < index) {
            return new Env(
                left.extend(ix, val),
                right,
                index,
                value
            );
        } else if (ix > index) {
            return new Env(
                left,
                right.extend(ix, val),
                index,
                value
            );
        } else {
            return new Env(
                left,
                right,
                ix,
                val
            );
        }
    }
}

class EmptyNode extends Env {
    // ...
    Env extend(int ix, Datum val) {
        return new Env(
            self,
            self,
            ix,
            val
        );
    }
}

class Node extends Env {

// ...

Env extend(int ix, Datum val) {

if (ix < index) {

return new Env(

left.extend(ix, val),

right,

index,

value

);

} else if (ix > index) {

return new Env(

left,

right.extend(ix, val),

index,

value

);

} else {

return new Env(

left,

right,

ix,

val

);

}

class EmptyNode extends Env {

// ...

Env extend(int ix, Datum val) {

return new Env(

self,

ix,

val

);

}

extend() only makes a copy of the path through the tree that was traversed in order to find the node to add or replace. this means that for a balanced tree, extend() is O(log n) of the number of items in the environment, which is not too bad.

Note also how the EmptyNode behaves as a singleton without explicitly requiring a static instance variable. This makes the implementation quite space efficient too.

The implementation does not support deletion of values, but that is ok since only a non-functional language with backtracking would require it, in order to undo side-effects.

Lastly, note that because these environments are immutable, we do not need any notion of an environment frame to encapsulate local changes, the old environment is still present and will be reverted to outside of a closure just as if we were using environment frames.

Of course this completely ignores the issues of maintaining balanced binary trees, for the sake of simplicity.

Languages, Technology

A Bit More on Compiler Environments

February 16, 2014 Bill Leave a comment

Rather than a single “Environment” type, a compiler distinguishes between compile-time and run-time environments.

In an interpreter, the value of a symbol is the result of looking it up in the current environment. That lookup process involves traversing the environment, frame by frame, until the symbol is found and the associated value is retrieved. The interpreter’s environment is constructed at run-time by closures extending a previous environment with bindings of formal to actual arguments.

A compiler can’t know the values of variables at compile time. It can however, determine the location those variables will have in the environment at run-time. A compiler will perform lexical analysis of code analagous to evaluation. It passes and (when entering a closure) extends a compile-time environment that contains only the symbols, not their values. When it comes across a variable access it looks up the symbol in the compile time environment and replaces the variable with its address in the environment (i.e.three frames back, two variables in).

At run time that data can rapidly be retrieved from the run-time environment (which contains only the data) without any laborious traversal and comparison.

That gives us three classes and a dumb data object for the location (all of this is pseudocode)

A compile-time environment

class CTE {
    private CTE parentEnv;
    private Symbol[] symbols;

    Location lookup(Symbol s, int framecount=0) {
        if (symbols.contains(s)) {
            return new Location(framecount, symbols.positionOf(s));
        } else {
            return parentEnv.lookup(s, framecount + 1);
        }
    }
}

class CTE {

private CTE parentEnv;

private Symbol[] symbols;

Location lookup(Symbol s, int framecount=0) {

if (symbols.contains(s)) {

return new Location(framecount, symbols.positionOf(s));

} else {

return parentEnv.lookup(s, framecount + 1);

}

A run-time environment:

class RTE {
    private RTE parentEnv;
    private Datum[] data;

    Datum lookup(Location l) {
        this._lookup(l.framecount, l.pos);
    }

    Datum _lookup(int framecount, int pos) {
        if (framecount) {
            return parentEnv._lookup(framecount - 1, pos);
        } else {
            return data.valueAt[pos];
        }
    }
}

class RTE {

private RTE parentEnv;

private Datum[] data;

Datum lookup(Location l) {

this._lookup(l.framecount, l.pos);

}

Datum _lookup(int framecount, int pos) {

if (framecount) {

return parentEnv._lookup(framecount - 1, pos);

} else {

return data.valueAt[pos];

}

And of course a terminating Null object for the CTE

class EmptyCTE extends CTE { Location lookup(Symbol s, int framecount=0) { error("symbol %s not found", symbol.name); } }

1
2
3
4
5

class EmptyCTE extends CTE {
    Location lookup(Symbol s, int framecount=0) {
        error("symbol %s not found", symbol.name);
    }
}

Extenders for the CTE and RTE take arrays of symbols and values respectively, otherwise they are just the same as interpreter extend() methods.

Technology, Unit Testing

Your Worst Nightmare

February 16, 2014 Bill Leave a comment

…happened to me:

Our team was handed a project which was in an awful state. The codebase was almost 500,000 lines of code and not a single test. The code was badly written, confusing, and extensive. We were tasked with not only maintaining this code, but also keeping on top of a demanding and growing list of new feature requests from the client.

After considering our options, up to and including resignation, we decided to treat the situation as a challenge. Luckily our engineering manager at the time was a great proponent of code quality and testing, and we agreed a mandate that no new code was to be written, and no existing code was to be changed, without tests.

All well and good, but the realities soon hit home: this code didn’t want to be tested. How did this happen?

Code without tests is not easy to change. That means that developers are afraid of the code, and make the minimum changes necessary to get the new feature or fix in place. This in turn means that methods grow in place, code is duplicated by copy and paste, calls to external resources (file and database access) are written in-line, and what started out as simple methods become deeply nested monstrosities, sometimes four and five levels deep and hundreds of lines long.

I say methods grow in size, why is that? Simply because the proliferation of temporary variables makes it difficult to extract a block of code into a separate method and guarantee to find all of the relevant temporaries.

So our first task was to get a test framework set up. We opted to do it properly and use the Perl Test::Class package. We then identified three major impediments to making any given piece of code testable:

Some of the code was procedural – no classes, just libraries.
The code was opening and using external resources (file handles, file system tests, time, databases, large production-only subsystems) in-line.
Where the code was object-oriented, it was calling new() directly, making objects impossible to mock out.

The first of these problems (no o-o) was fairly easily, if only partially, solved by writing o-o wrappers around these procedural libraries.

The other two problems were addressed by creating what is generally called a global Factory that would allocate objects of the requested type, and provided a level of indirection between the code under test and the creation of new objects, open file handles etc.

In order to make these global factories convenient to use we decided that they should export a single function (not method) whose exact name could be decided by the importing package. That function would act as a shorthand to the factory’s new() class method, so a typical use of the factory might be:

Before

package MyUntestablePackage;
use SomeOtherPackage;

    ...
    if (-e $datafile) {
        open DATAFILE, $datafile;
        my $blah = new SomeOtherPackage($datafile, time());
        ...

package MyUntestablePackage;

use SomeOtherPackage;

...

if (-e $datafile) {

open DATAFILE, $datafile;

my $blah = new SomeOtherPackage($datafile, time());

...

After

package MyUntestablePackage;
use Factory qw(fetch);

    ...
    if (fetch->file->exists($datafile)) {
        my $DATAFILE = fetch->fileHandle($datafile);
        my $blah = fetch->someOtherPackage($datafile, fetch->time());
        ...

package MyUntestablePackage;

use Factory qw(fetch);

...

if (fetch->file->exists($datafile)) {

my $DATAFILE = fetch->fileHandle($datafile);

my $blah = fetch->someOtherPackage($datafile, fetch->time());

...

The idea of exporting fetch() was If you want people to do the right thing, make it the easy thing. Typing fetch is only one more character than typing new and therefore met little resistance within the team.

So now we have the Factory, what can we do with it?

Well, the factory is a special kind of Singleton, with a special mockMode() method:

package Factory; # we didn't really call it this
use strict;
use warnings;

# special code to export fetch() ...
# ...

{
    my $self = 0; # lexical scope

    sub _new {
        my ($class) = @_;
        $self ||= bless {}, $class;
    }

    sub mockMode {
        require Mock::Factory;
        $self = Mock::Factory->new();
    }
}

sub fetch {
    __PACKAGE__->_new();
}

sub fileHandle {
    my ($self, @args) = @_;
    return FileHandle->new(@args);
}

# etc. for other factory methods

package Factory; # we didn't really call it this

use strict;

use warnings;

# special code to export fetch() ...

# ...

{

my $self = 0; # lexical scope

sub _new {

my ($class) = @_;

$self ||= bless {}, $class;

}

sub mockMode {

require Mock::Factory;

$self = Mock::Factory->new();

}

sub fetch {

__PACKAGE__->_new();

}

sub fileHandle {

my ($self, @args) = @_;

return FileHandle->new(@args);

}

# etc. for other factory methods

So mockMode() unconditionally assigns a mock version of the factory to the lexical $self. This can be used in the test fixtures:

sub setup : Test(setup) {
    my ($test) = @_;
    fetch->mockMode();
    my $fh = Test::MockObject->new();
    # add functionality to $fh
    # ...
    # remember the file names:
    $test->{openfiles} = [];
    fetch->mock(
        fileHandle => sub {
            my ($fetch, $filename) = @_;
            push @{$test->{openfiles}}, $filename;
            return $fh;
        }
    );
    # etc.
}

sub setup : Test(setup) {

my ($test) = @_;

fetch->mockMode();

my $fh = Test::MockObject->new();

# add functionality to $fh

# ...

# remember the file names:

$test->{openfiles} = [];

fetch->mock(

fileHandle => sub {

my ($fetch, $filename) = @_;

push @{$test->{openfiles}}, $filename;

return $fh;

}

);

# etc.

}

Of course the mock factory has features similar to Test::MockObject that allow factory methods to be mocked.

Code Generation, Technology

A Slightly Non-Standard Application

February 16, 2014 Bill Leave a comment

Here’s an application of code generation that doesn’t fit the standard Enterprise Application mold: here I’m using code generation to build a class heirarchy for abstract syntax trees.

The idea is pretty simple. An abstract syntax tree is a tree containing the results of parsing a programming language. Nodes of the tree could be function calls, operator application or control flow constructs, and the leaves of the tree would be comstants and variables. Of course these trees cannot be constructed arbitrarily, it doesn’t often make sense to add an integer to a record for example, so the constructors for the nodes need to declare (or, in an untyped language, type-check) their arguments. Each node will furthermore need accessors and probably an accept() method for the Visitor pattern, so that is a substantial amount of boiler-plate code for something that is easily describeable at a very high level.

Here’s a snapshot of the AST definition from F♮:

abstract      Expr()
Expr          Char(scalar value) # [id]
Expr          Number(scalar value)

Expr          WildCard()

abstract Expr Symbol() # [id]
Symbol        DollarName(scalar name)
Symbol        Name(scalar name)
Symbol        TypeName(scalar name)

abstract Expr List()
List          Cons(Expr car, List cdr)
List          Nil()

abstract Expr Sequence()
Sequence      Statement(Expr car, Sequence cdr)
Sequence      EmptySequence()

abstract Expr Constructors()
Constructors  Constructor(Expr car, Constructors cdr)
Constructors  EmptyConstructor()

Expr          Typedef(Expr type, Constructors constructors)
Expr          Type(Expr type)

Expr          Apply(Expr op, List args)
Expr          End(Expr expr)
Expr          Define(Symbol name, Expr value)
Expr          Declare(Name name)
Expr          Lambda(List args, Sequence body)
Expr          LambdaSwitch(List lambdas)
Expr          Try(Apply attempt, LambdaSwitch catches)
Expr          Throw(List exprs)
Expr          String(scalar value)

Expr          LambdaLet(List formals, List actuals, Sequence Body)
Expr          LambdaSwitchLet(List actuals, List lambdas)

# these next are rewritten by the RewritingVisitor
Expr          And(Expr a, Expr b)
Expr          Or(Expr a, Expr b)
Expr          Not(Expr)
Expr          If(Expr test, Sequence consequent, Sequence alternative)
Expr          Then(Expr first, Expr second)
Expr          Pairs(List list)
Expr          Switch(List exprs, LambdaSwitch lambdas)

abstract Expr()

Expr Char(scalar value) # [id]

Expr Number(scalar value)

Expr WildCard()

abstract Expr Symbol() # [id]

Symbol DollarName(scalar name)

Symbol Name(scalar name)

Symbol TypeName(scalar name)

abstract Expr List()

List Cons(Expr car, List cdr)

List Nil()

abstract Expr Sequence()

Sequence Statement(Expr car, Sequence cdr)

Sequence EmptySequence()

abstract Expr Constructors()

Constructors Constructor(Expr car, Constructors cdr)

Constructors EmptyConstructor()

Expr Typedef(Expr type, Constructors constructors)

Expr Type(Expr type)

Expr Apply(Expr op, List args)

Expr End(Expr expr)

Expr Define(Symbol name, Expr value)

Expr Declare(Name name)

Expr Lambda(List args, Sequence body)

Expr LambdaSwitch(List lambdas)

Expr Try(Apply attempt, LambdaSwitch catches)

Expr Throw(List exprs)

Expr String(scalar value)

Expr LambdaLet(List formals, List actuals, Sequence Body)

Expr LambdaSwitchLet(List actuals, List lambdas)

# these next are rewritten by the RewritingVisitor

Expr And(Expr a, Expr b)

Expr Or(Expr a, Expr b)

Expr Not(Expr)

Expr If(Expr test, Sequence consequent, Sequence alternative)

Expr Then(Expr first, Expr second)

Expr Pairs(List list)

Expr Switch(List exprs, LambdaSwitch lambdas)

This is a high level but complete description of the required classes, all of the details of implementation are merely repetitive, which makes it a perfect candidate for code generation.

So, given this description, and a couple of command-line options to cover class prefixes etc., my treebuilder (tbd) will generate all of the classes required. For example, here’s the generated class definition for Expr If(Expr test, Sequence consequent, Sequence alternative):

# WARNING: Automatically generated from ast.tb on Sat May 29 18:51:18 2010 GMT. DO NOT EDIT! YOUR EDITS WILL BE LOST!

package Lang::FN::AST::If;
use strict;
use warnings;
use base qw(Lang::FN::AST::Expr);

=head1 NAME

Lang::FN::AST::If - a tree node, a type of Lang::FN::AST::Expr.

=head1 SYNOPSIS

  use Lang::FN::AST::API;
  my $if = If($test, $consequent, $alternative);

  my $test = $if->getTest();
  my $consequent = $if->getConsequent();
  my $alternative = $if->getAlternative();
  $if->accept(new Lang::FN::AST::Visitor());

=head1 METHODS

Individual Lang::FN::AST::If methods are described below.

=head2 new

  my $If = new Lang::FN::AST::If($test, $consequent, $alternative);

or better:

  use Lang::FN::AST::API;
  my $If = If($test, $consequent, $alternative);

The C<If()> subroutine is provided by
C<Lang::FN::AST::API> to make
it easier to create instances of C<Lang::FN::AST::If>.
In either case
C<$test>
must be a
C<Lang::FN::AST::Expr>, C<$consequent>
must be a
C<Lang::FN::AST::Sequence> and C<$alternative>
must be a
C<Lang::FN::AST::Sequence>.

=cut

sub new {
    die "wrong number of arguments to Lang::FN::AST::If::new(\$test, \$consequent, \$alternative)\n"
        unless @_ == 4;

    my ($class, $test, $consequent, $alternative) = @_;

    die "argument test to If is not a Lang::FN::AST::Expr, it is a ",
        (ref($test) || 'scalar'), "\n"
        unless defined($test)
               && $test->isa('Lang::FN::AST::Expr');
    die "argument consequent to If is not a Lang::FN::AST::Sequence, it is a ",
        (ref($consequent) || 'scalar'), "\n"
        unless defined($consequent)
               && $consequent->isa('Lang::FN::AST::Sequence');
    die "argument alternative to If is not a Lang::FN::AST::Sequence, it is a ",
        (ref($alternative) || 'scalar'), "\n"
        unless defined($alternative)
               && $alternative->isa('Lang::FN::AST::Sequence');

    return bless {
        _test => $test,
        _consequent => $consequent,
        _alternative => $alternative,
    }, $class;
}

=head2 getTest

  my $test = $If->getTest();

gets the value of the C<test> field,
which is a C<Lang::FN::AST::Expr>.

=cut

sub getTest {
    my ($self) = @_;
    return $self->{_test};
}

=head2 getConsequent

  my $consequent = $If->getConsequent();

gets the value of the C<consequent> field,
which is a C<Lang::FN::AST::Sequence>.

=cut

sub getConsequent {
    my ($self) = @_;
    return $self->{_consequent};
}

=head2 getAlternative

  my $alternative = $If->getAlternative();

gets the value of the C<alternative> field,
which is a C<Lang::FN::AST::Sequence>.

=cut

sub getAlternative {
    my ($self) = @_;
    return $self->{_alternative};
}

=head2 accept

  $If->accept(new Lang::FN::AST::Visitor());

Accepts a C<Lang::FN::AST::Visitor> and calls its C<visitIf>
method, passing it C<$self> (i.e. a C<Lang::FN::AST::If>) as argument.

=cut

sub accept {
    my ($self, $visitor) = @_;
    return $visitor->visitIf($self);
}

=head2 eq

   if ($If->eq($other)) {
       ...
   }

Returns true if the argument C<$other> is recursively equal to C<$self>.

=cut

sub eq {
    my ($self, $other) = @_;
    if (ref($other) eq 'Lang::FN::AST::If') {
        return 1
            && $self->getTest->eq($other->getTest)
            && $self->getConsequent->eq($other->getConsequent)
            && $self->getAlternative->eq($other->getAlternative)
    } else {
        return 0;
    }
}

=head2 isIf

Returns true.

=cut

sub isIf { 1 }

=head1 AUTHOR

Automatically generated from ast.tb on Sat May 29 18:51:18 2010 GMT.

=head1 SEE ALSO

The other generated node classes:
L<Lang::FN::AST::And>,
L<Lang::FN::AST::Apply>,
L<Lang::FN::AST::Char>,
L<Lang::FN::AST::Cons>,
L<Lang::FN::AST::Constructor>,
L<Lang::FN::AST::Constructors>,
L<Lang::FN::AST::Declare>,
L<Lang::FN::AST::Define>,
L<Lang::FN::AST::DollarName>,
L<Lang::FN::AST::EmptyConstructor>,
L<Lang::FN::AST::EmptySequence>,
L<Lang::FN::AST::End>,
L<Lang::FN::AST::Expr>,
L<Lang::FN::AST::Lambda>,
L<Lang::FN::AST::LambdaLet>,
L<Lang::FN::AST::LambdaSwitch>,
L<Lang::FN::AST::LambdaSwitchLet>,
L<Lang::FN::AST::List>,
L<Lang::FN::AST::Name>,
L<Lang::FN::AST::Nil>,
L<Lang::FN::AST::Not>,
L<Lang::FN::AST::Number>,
L<Lang::FN::AST::Or>,
L<Lang::FN::AST::Pairs>,
L<Lang::FN::AST::Sequence>,
L<Lang::FN::AST::Statement>,
L<Lang::FN::AST::String>,
L<Lang::FN::AST::Switch>,
L<Lang::FN::AST::Symbol>,
L<Lang::FN::AST::Then>,
L<Lang::FN::AST::Throw>,
L<Lang::FN::AST::Try>,
L<Lang::FN::AST::Type>,
L<Lang::FN::AST::TypeName>,
L<Lang::FN::AST::Typedef>,
L<Lang::FN::AST::WildCard>,
an abstract visitor that can be subclassed to walk them:
L<Lang::FN::AST::Visitor>,
and the API that makes them available: L<Lang::FN::AST::API>.

=cut

1;

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

# WARNING: Automatically generated from ast.tb on Sat May 29 18:51:18 2010 GMT. DO NOT EDIT! YOUR EDITS WILL BE LOST!

package Lang::FN::AST::If;

use strict;

use warnings;

use base qw(Lang::FN::AST::Expr);

=head1 NAME

Lang::FN::AST::If - a tree node, a type of Lang::FN::AST::Expr.

=head1 SYNOPSIS

use Lang::FN::AST::API;

my $if = If($test, $consequent, $alternative);

my $test = $if->getTest();

my $consequent = $if->getConsequent();

my $alternative = $if->getAlternative();

$if->accept(new Lang::FN::AST::Visitor());

=head1 METHODS

Individual Lang::FN::AST::If methods are described below.

=head2 new

my $If = new Lang::FN::AST::If($test, $consequent, $alternative);

or better:

use Lang::FN::AST::API;

my $If = If($test, $consequent, $alternative);

The C<If()> subroutine is provided by

C<Lang::FN::AST::API> to make

it easier to create instances of C<Lang::FN::AST::If>.

In either case

C<$test>

must be a

C<Lang::FN::AST::Expr>, C<$consequent>

must be a

C<Lang::FN::AST::Sequence> and C<$alternative>

must be a

C<Lang::FN::AST::Sequence>.

=cut

sub new {

die "wrong number of arguments to Lang::FN::AST::If::new(\$test, \$consequent, \$alternative)\n"

unless @_ == 4;

my ($class, $test, $consequent, $alternative) = @_;

die "argument test to If is not a Lang::FN::AST::Expr, it is a ",

(ref($test) || 'scalar'), "\n"

unless defined($test)

&& $test->isa('Lang::FN::AST::Expr');

die "argument consequent to If is not a Lang::FN::AST::Sequence, it is a ",

(ref($consequent) || 'scalar'), "\n"

unless defined($consequent)

&& $consequent->isa('Lang::FN::AST::Sequence');

die "argument alternative to If is not a Lang::FN::AST::Sequence, it is a ",

(ref($alternative) || 'scalar'), "\n"

unless defined($alternative)

&& $alternative->isa('Lang::FN::AST::Sequence');

return bless {

_test => $test,

_consequent => $consequent,

_alternative => $alternative,

}, $class;

}

=head2 getTest

my $test = $If->getTest();

gets the value of the C<test> field,

which is a C<Lang::FN::AST::Expr>.

=cut

sub getTest {

my ($self) = @_;

return $self->{_test};

}

=head2 getConsequent

my $consequent = $If->getConsequent();

gets the value of the C<consequent> field,

which is a C<Lang::FN::AST::Sequence>.

=cut

sub getConsequent {

my ($self) = @_;

return $self->{_consequent};

}

=head2 getAlternative

my $alternative = $If->getAlternative();

gets the value of the C<alternative> field,

which is a C<Lang::FN::AST::Sequence>.

=cut

sub getAlternative {

my ($self) = @_;

return $self->{_alternative};

}

=head2 accept

$If->accept(new Lang::FN::AST::Visitor());

Accepts a C<Lang::FN::AST::Visitor> and calls its C<visitIf>

method, passing it C<$self> (i.e. a C<Lang::FN::AST::If>) as argument.

=cut

sub accept {

my ($self, $visitor) = @_;

return $visitor->visitIf($self);

}

=head2 eq

if ($If->eq($other)) {

...

}

Returns true if the argument C<$other> is recursively equal to C<$self>.

=cut

sub eq {

my ($self, $other) = @_;

if (ref($other) eq 'Lang::FN::AST::If') {

return 1

&& $self->getTest->eq($other->getTest)

&& $self->getConsequent->eq($other->getConsequent)

&& $self->getAlternative->eq($other->getAlternative)

} else {

return 0;

}

=head2 isIf

Returns true.

=cut

sub isIf { 1 }

=head1 AUTHOR

Automatically generated from ast.tb on Sat May 29 18:51:18 2010 GMT.

=head1 SEE ALSO

The other generated node classes:

L<Lang::FN::AST::And>,

L<Lang::FN::AST::Apply>,

L<Lang::FN::AST::Char>,

L<Lang::FN::AST::Cons>,

L<Lang::FN::AST::Constructor>,

L<Lang::FN::AST::Constructors>,

L<Lang::FN::AST::Declare>,

L<Lang::FN::AST::Define>,

L<Lang::FN::AST::DollarName>,

L<Lang::FN::AST::EmptyConstructor>,

L<Lang::FN::AST::EmptySequence>,

L<Lang::FN::AST::End>,

L<Lang::FN::AST::Expr>,

L<Lang::FN::AST::Lambda>,

L<Lang::FN::AST::LambdaLet>,

L<Lang::FN::AST::LambdaSwitch>,

L<Lang::FN::AST::LambdaSwitchLet>,

L<Lang::FN::AST::List>,

L<Lang::FN::AST::Name>,

L<Lang::FN::AST::Nil>,

L<Lang::FN::AST::Not>,

L<Lang::FN::AST::Number>,

L<Lang::FN::AST::Or>,

L<Lang::FN::AST::Pairs>,

L<Lang::FN::AST::Sequence>,

L<Lang::FN::AST::Statement>,

L<Lang::FN::AST::String>,

L<Lang::FN::AST::Switch>,

L<Lang::FN::AST::Symbol>,

L<Lang::FN::AST::Then>,

L<Lang::FN::AST::Throw>,

L<Lang::FN::AST::Try>,

L<Lang::FN::AST::Type>,

L<Lang::FN::AST::TypeName>,

L<Lang::FN::AST::Typedef>,

L<Lang::FN::AST::WildCard>,

an abstract visitor that can be subclassed to walk them:

L<Lang::FN::AST::Visitor>,

and the API that makes them available: L<Lang::FN::AST::API>.

=cut

The point of all this is to be able to use these constructors directly in a yapp or similar grammar file. Here’s a snippet of these generated classes in action:

...
expr      :   int
          |   char
          |   string
...
          |   END expr %prec L_5 { End($_[2]) }
          |   expr '=' expr      { Apply(Name('='), Cons($_[1], Cons($_[3], Nil))) }
          |   expr THEN expr     { Then($_[1], $_[3]) }
          |   expr '&&' expr     { And($_[1], $_[3]) }
          |   expr '||' expr     { Or($_[1], $_[3]) }
          |   '!' expr           { Not($_[2]) }
          |   '(' expr ')'       { $_[2] }
...
          ;

ifexpr    :   IF '(' expr ')' block ELSE alternative
                            { If($_[3], $_[5], $_[7]) }
          ;

alternative : block
            | ifexpr
            ;

...

expr : int

| char

| string

...

| END expr %prec L_5 { End($_[2]) }

| expr '=' expr { Apply(Name('='), Cons($_[1], Cons($_[3], Nil))) }

| expr THEN expr { Then($_[1], $_[3]) }

| expr '&&' expr { And($_[1], $_[3]) }

| expr '||' expr { Or($_[1], $_[3]) }

| '!' expr { Not($_[2]) }

| '(' expr ')' { $_[2] }

...

;

ifexpr : IF '(' expr ')' block ELSE alternative

{ If($_[3], $_[5], $_[7]) }

;

alternative : block

| ifexpr

;

One of the visitors over the resulting tree is a rewriting visitor that converts some abstract syntax to simpler forms so that there are fewer constructs that need to be dealt with later on. Here’s the visitor routine that converts If abstract syntax to a function call:

sub visitIf {
    my ($self, $if) = @_;
    my $test = $if->getTest->accept($self);
    my $consequent = $if->getConsequent->accept($self);
    my $alternative = $if->getAlternative->accept($self);
    Apply(
        LambdaSwitch(
            Cons(
                Lambda(
                    Cons(TypeName('True'), Nil),
                    Statement(
                        End($consequent->getCar),
                        $consequent->getCdr
                    )
                ),
                Cons(
                    Lambda(
                        Cons(TypeName('False'), Nil),
                        $alternative
                    ),
                    Nil
                )
            )
        ),
        Cons($if->getTest->accept($self), Nil)
    )
}

sub visitIf {

my ($self, $if) = @_;

my $test = $if->getTest->accept($self);

my $consequent = $if->getConsequent->accept($self);

my $alternative = $if->getAlternative->accept($self);

Apply(

LambdaSwitch(

Cons(

Lambda(

Cons(TypeName('True'), Nil),

Statement(

End($consequent->getCar),

$consequent->getCdr

)

Cons(

Lambda(

Cons(TypeName('False'), Nil),

$alternative

Nil

)

Cons($if->getTest->accept($self), Nil)

)

}

Languages, Technology

An Abstract Machine

February 21, 2011 Bill Leave a comment

Another recent idea I’ve had is to build a compiler for a pscheme-like language (different syntax, extended functionality) that would target an abstract machine much as Java does (I know Java calls it a “Virtual Machine” but that’s an accident of history since Java originally targeted a real CPU and the replacement machine was a “virtualisation” of that.) I started looking at Parrot, but Parrot has built-in support for a single continuation only, and would make a second “failure” continuation doubly difficult to implement.

So I started thinking about building my own. The real joy of this is that I can prototype it in a high-level language like Perl, then re-write it into something fast like C or C++ later. I actually have a (mostly) working version in Perl for PScheme that runs about seven times faster than the interpreter, but it has issues.

Anyway I think the basic ideas are sound. In an interpreter a closure is a function plus an environment. In a compiled language that’s even simpler, a “function” is just a machine address, so a closure is a pair of addresses: address of environment on the heap and address of machine instruction in the core. A Success Continuation on the other hand has a lot more context. It contains the return address and the old environment, but also must restore any temporary variables, along with the previous continuation that will be returned to later. Finally a Failure continuation is a complete reset. It does not preserve any data when it is invoked, but completely restores the Abstract machine to a previous state.

So without further ado, here’s my abstract machine:

PC: is just an integer index into the machine code table.
ENV: is the address of the current run-time environment (the compiler has pre-determined the locations of the data in the environment, the run time environment contains only the data.)
ARGS: would point to an array or linked list of actual arguments to a closure, before they are bound into an environment. They constitute the nearest lexical scope once inside the closure.
CONT: points at the most recent Continuation.
TEMPS: is just an arbitrarily sized array of temporary registers, their utility is questionable as there is no efficiency saving as there would be for a real CPU, but it makes the model closer to a standard compilation target.
FAIL: points at the most recent Failure continuation.
RESULT: is where a return value is passed to a Continuation.

Usefully, the different subcomponents (Closure, Continuation and Failure) are all contiguous, so invoking any of them is just a singlememcpy() from the stored object (on the heap) to the “cpu”. I don’t know if this is just blind luck or something deeper.

For each subcomponent there would be two abstract machine instructions: one to set up a new structure and one to invoke it. Specifically:

Closure

create_closure(PC, ENV): create a new closure object (and put it in TEMPS somewhere)
call_closure(): memcpy(&AM, AM.TEMPS[n], sizeof(struct closure))

Continuation

create_continuation(PC): allocate a new continuation struct, copy the relevant components of the AM into it, assign the PC to it directly, pointAM.CONT at the new continuation.
continue(): memcpy(&AM, AM.CONT, sizeof(struct continuation))

Failure

completely analagous to Continuation above.

So the plan is:

Write the Abstract Machine in C or C++.
Write an interpreter for the new language in Perl.
Write a compiler for the new language in itself.
Run the interpreted compiler on its own source code to produce bytecode for the compiler.
Compile the compiler again using the bytecode compiler and diff the bytecodes: any difference is a problem.
World domination.

So far, I have a parser and a partial interpreter for a new language called “F-Natural”: If you think of ML but with real Unification, backtracking and a javasript-like syntax you will get the basic idea. I’m still a long way from world domination but we live in hope. I may post some code here later.

Languages, Technology

A Programming Language in a Picture

February 15, 2011 Bill Leave a comment

Recently I’ve been thinking about how best to describe a really simple language so that the reader can just “get it” in one go. As you probably know I’m quite fond of UML and this is what I’ve come up with:

I’d hope that this diagram stands alone, but for the impatient I’ll describe it.

You can see that the implementation breaks down into three primary groups of classes: Syntax structures, Environment and Operations. The environment is the simplest and the best thing to look at first. You can see an abstract base class Env with concrete Frame and Empty subclasses. The Env class provides one concrete method: extend() which takes a dictionary (hash, or whatever) as argument and creates and returns a new Frame containing that dictionary and a parent pointer to the original environment. The Frame and Empty subclasses supply a lookup() method which, for the empty env just errors. For a non empty env it either looks up the symbol in the dictionary or calls lookup() on its parent, passing it the symbol.

The Syntax group of classes all inherit from a common abstract Exp base class that declares one abstract method: eval(env), that they all must implement. A Constantevaluates to itself. A Symbol looks itself up in the argument environment. A Conditional evaluates the test then either evaluates the consequent or the alternative.Function declarations evaluate by creating a new Closure object passing it the body and formal arguments to the function, along with the current environment.Application of an operation involves evaluating the operation expression in the current environment, evaluating the argument expressions in the current environment, then calling the resulting operations apply() method on the resulting evaluated arguments. Note that in operands.map(eval(env)) that eval is sort of Curried: the argument env is explicit, but the map supplies the objects whose eval methods are to be called.

Lastly, Operations themselves share an abstract Op base class with an abstract apply() method. An Op is either a Primitive or a Closure. The implementation of the primitive apply() is just an implementation detail, however the implementation of the Closure‘s apply() ties the whole thing up:

Extend the captured environment (the one passed to new()) binding the formal arguments (passed to new()) to the actual arguments (passed to apply()).
Evaluate the body of the closure in that new environment.

That’s about as simple as I can make it.

Bill Hails

Category Archives: Technology

Preliminary Sketch for F Natural

Garbage Collection

Reference Counting Garbage Collection

Mark and Sweep Garbage Collection

Copying Garbage Collection

Generational Garbage Collection

A Bit on the Lambda Calculus

Purely Functional Environments

A Bit More on Compiler Environments

Your Worst Nightmare

A Slightly Non-Standard Application

An Abstract Machine

A Programming Language in a Picture

Random Blogs