Not so happy with Git

Posted: January 21st, 2010 | Author: Mars | Filed under: Uncategorized | 3 Comments »

The ability to host a repository via HTTP is nice, but I’m left swimming any time something unusual happens. I’m sure one of git’s hundreds of sub-commands can tell me why it won’t do what I want, but in absence of a comprehensive knowledge of the system, I’m stuck. Here’s the latest example of its helpfulness:

Morgan:git marssaxman$ git apply 0001-implementation-of-an-intrinsic-function-system-in-th.patch 
error: patch failed: source/flowgraph/pool.cpp:355
error: source/flowgraph/pool.cpp: patch does not apply
Morgan:git marssaxman$ 

There are no changes in the local repository, and the patch comes from a fresh clone of the same master. Why won’t this work? Beats me. I guess it’s time to trash the local repository and clone a new one.


Implementation of member lookup

Posted: January 16th, 2010 | Author: Mars | Filed under: Progress | Comments Off

I’ve checked in the new member-lookup code for objects and modules. The compiler generates a binary search tree, which the object function captures as one of its slots. Request for an object member becomes a call to the BST lookup function. The lookup code is implemented as a compiler intrinsic. I tried to write it as an actual function, which would live in a “core” library, but implementing modules in terms of a module turned out to be something of a challenge.

The next step will be a function to set a value in the tree. This is not the same as the standard associative-container “insert” operation – you can’t establish a new key-value mapping, but only change the value associated with an existing key. This way I can organize the tree at compile time, and the intrinsic member-lookup and member-set functions don’t need any complex balancing logic.


Objects and member variables

Posted: January 11th, 2010 | Author: Mars | Filed under: Uncategorized | Comments Off

An object contains a group of related things: pieces of data and functions which operate on the data. We can think of an object as a kind of associative container, then, mapping names to members. What is the value of bar, one may ask; or how do I perform the baz operation?

In many object-oriented languages, this mapping is established by a class. Radian objects are simpler; instead of combining instantiation, inheritance, and type identification into one structure, each of these functions is implemented separately. The object itself, once you’ve constructed it, is just a function which returns a value in response to some key, which is the name of the function or variable you want to retrieve.

The dot-syntax for members is therefore a specialized form of function call. If you have an object foo, and you want its member bar, you would write this:
baz = foo.bar
This operation performs two calls. First, you call the object foo, passing in the symbol bar. The object responds with a reference to whichever function it is that can return the value of bar. Then you call that function, passing in the object reference, and it returns the value.

The lookup mechanism and the accessor mechanism are thus separated from one another. Accessors do not need to have any privileged relationship with the object, provided they are capable of doing the job requested of them; any function which returns an appropriate value when presented with the object can work. Further, it doesn’t matter where the data actually comes from; it may live in the object, it may live somewhere else, or it may be computed on demand, but the mechanism for retrieving it is the same in each case.

The object constructor syntax is effectively a dictionary, or map, constructor. The object block itself represents a function which returns some object; the object is an associative mapping of keys, which are member names, to values, which are functions that return some interesting information. Each new item declared in the object block adds such a mapping to the resulting object.

Each function or method defined inside this block gets an implicit parameter, self, representing the object it is expected to work on. This need not be declared explicitly, as in Python; it is a byproduct of the object-constructor context. Variables defined inside an object block also receive special handling: they are marked in the symbol table as self-members, so that the compiler can generate code to look the value up through the “self” object, or to assign a new value by assigning to the “self” object.


Data structures implementation

Posted: January 6th, 2010 | Author: Mars | Filed under: Design, Progress | Comments Off

Radian offers syntax for five types of container data structures: tuple, array, set, map, and object. The tuple is a primitive element, implemented in the compiler backend, but the others must be built up from simpler components. I’ve been thinking a lot about the fundamentals of data organization in Radian lately, therefore, and while I’ve spent a lot of time working on the project, I’ve written little code, all of which I have thrown away.

It’s less the implementation that has been puzzling me – though immutability certainly complicates matters – than the fact that I have to design an API for the whole thing, and API design is hard. Objects, like maps, are associative containers; but how much of the map interface should an object share? How much support should I build in for runtime inspection or mutation of object structure? Should arrays serve double-duty as queues and stacks?

I’m making progress, and I think the next round of code I write may actually stick. I’ve settled on a list of standard containers, interfaces, and method names. Key->value containers like maps and objects will be implemented with red-black trees; ordered containers, like arrays, will be finger trees. Both structures offer O(log n) average performance for lookup, insert, and delete, and both are compatible with immutability.

It’s proving difficult to implement any useful API using only the current set of primitives. I’m thinking of upgrading the red-black tree to become one of the primitives, alongside tuples and closures. Tonight’s project is a persistent implementation in Python, as a prototype for the version I intend to embed in the compiler’s semantics engine.