‘yield from’ works now

The async features continue to be my major focus of development. I’ve just pushed a couple of commits that make the yield from statement work. Where the plain yield statement produces a single value in the generator’s sequence of outputs, the yield from statement splices an entire sequence into the output stream.

An identical feature showed up in Python a couple of weeks ago, though that language has offered the simple yield statement for a decade now. I chose to head straight for the enhanced form of yield because I intend to use it as a foundation for the rest of the generator feature: any control-flow block nested in a generator will itself become a generator, and its container will implicitly yield from this nested block.

Release 0.1.0

I’ve just tagged v0.1.0 in the git repository and uploaded a new Mac OS X binary build. Changes since last month’s release 0.0.0:

• A string is a sequence of characters, not a sequence of bytes. When iterating over the characters in a string literal, the contents are no longer returned as individual UTF-8 bytes, but as Unicode code points.
• Symbol lookup time is now O(log n) in the worst case, not O(n), since the index is now an AA-tree rather than an unbalanced binary tree.
• A race condition in the symbol allocator has been corrected; it is no longer possible to get duplicate symbols when the first lookup happens simultaneously on different processors.
• io.print function emits UTF-8 byte streams instead of mangling non-ASCII characters.
• The identifiers task, generator, and yield have been reserved for use as syntax keywords.
• String literals implement a compare_to method, which allows them to be compared and used as keys in a map container. This method uses a simple ordinal comparison, not one of the specific Unicode-defined lexical comparisons.
• Import statement allows an optional aliasing clause, where the local symbol has a different name than the symbol defined in the target module. The complete syntax is:
  'import' identifier ['=' identifier] ['from' expression]
  As with all declarations, the first identifier token is the declared name; the optional second identifier specifies the target to import.
• Expressions can now be split and continued on the next line after any binop token, including the comma and period tokens. Comments between a binop token and the end of line will be ignored.
• Tuples implement the sequence interface.
• Map constructor no longer tries to double up as a set constructor. Entries must have both a key and a value.
• Unary operators (negate, not, poison, and yield) no longer parse an entire expression instead of a single term. This caused baffling precedence errors.
• Numerics package supports rational as well as integer arithmetic. Division of two integers will now yield a rational number instead of truncating the remainder and returning an integer. Rational numbers are represented as a pair of integers, numerator and denominator. Rational numbers are normalized such that the numerator and denominator have no common factors and the denominator is always positive and greater than 1.
  Number type has two new predicates: rational?, which is currently true for all numbers, and integer?, which is true only for integral values. The shifting and bitwise arithmetic operations are only defined for integers, not for all rationals.
• Functions in the number module allow rounding of rational numbers in three modes: ceiling rounds toward positive infinity, floor rounds toward negative infinity, and truncate rounds toward zero.
• Sign function in the number module returns -1 for negative numbers, 1 for positive numbers, and 0 for all numbers which are equal to zero.
• New generator block type lets you define a function which returns a
  sequence. The generator supplies each value in the sequence by executing a yield statement. This is not very useful, as you cannot put yield statements inside nested loops or conditionals, but it is a sign of things to come.

State of the project

In 2009, I launched this language project and built its compiler. In 2010, I fleshed out the structure and built the automatic parallelization system. In 2011, I finished the core semantic model, implemented the standard container structures, added an IO interface and a memory management system. Now it’s 2012: what comes next?

I’ve accomplished the primary goal for this project, which was to demonstrate that this approach to parallel programming actually works. You can have a language that looks and feels like Python, Ruby, or JavaScript whose semantic properties allow automated parallelism in a manner similar to Haskell or Erlang. You don’t need to invert your thinking and write your code in functional style; given a few carefully chosen semantic restrictions, a compiler can make that transformation for you.

The next step is to build this tool up into a software ecosystem, so that it can actually do some real people some real good. Who are its users going to be? What tools are they currently using? What does Radian need to offer in order to make life easier than whatever they are doing right now? The job facing me in 2012 is to answer these questions and build the components those answers suggest.

I need to find people doing experimental work with huge amounts of data: people who are writing smallish programs that crunch through gigabytes of stuff. Radian should be good for CPU-bound processes involving varied data: it will do well with embarrassingly parallel problems, but the whole point is that it should also do a good job with problems where the parallelism takes a bit more work to find.

Maybe people are analyzing web server logs, or extracting fingerprints from MP3s, or sorting EXIF tags from hundreds of thousands of pictures. Are there scientific applications for this sort of work? There must be – people use Python for scientific work, after all; scipy is a big deal.

Marshaling objects

The first batch of marshaling objects are in the library now. They all live in the ffi module for now, but they will be useful in any situation where one might want to render values as bytes or retrieve values from bytes, so I may end up breaking them out into their own module. The current list is uint64, int64, uint32, int32, uint16, int16, uint8, int8, ascii, and utf8. A marshaling object is one that implements the to_bytes and from_bytes methods; these methods accept a value and return a sized sequence of bytes, and accept a byte buffer and return a value, respectively.

List object progress

Implementing the log-time finger tree algorithms has proven to be a substantial challenge. Examples are few, and most are written in Haskell, which I find largely unintelligible. After several false starts, however, I am making some progress. I’ve re-implemented the indexed element lookup, in a way that will survive splits and concatenations, and have roughed out the concatenate method. With that and a split function, I can easily build insert, remove, and assign.

The list object has been more of a slog than I expected; the finger tree is substantially more complex than the Andersson-tree used in the map object. It is still clearly the right approach, however, and I am pleased to have such a powerful tool built into the foundation of the language.

Progress on the list object

I’ve implemented the lookup and element-assignment operations on the list now. Lookup uses the subscript protocol: instead of calling a method, you use brackets to look up the element by index. That is, the list’s default operation is the lookup, like this:

var names = ["Joe", "Erin", "Bill", "Colin", "Tessa"]
io->print( names[2] )

In order to replace one of these values, one calls the assign method:
names->assign(1, "Jessie")

I am thinking about sugaring this so that one can assign to a bracket subscript instead, but it’s not a high priority. It would look like this:
names[1] = "Jessie"

The remaining methods the list object needs are insert, remove, concatenate, and of course iterate.

Partial implementation of the list

Incorporating Charles Y.’s suggestion, I’ve renamed the “array” object to “list”. It plays a similar role to an array, but there’s no array anywhere in its implementation, and it’s really more interested in the fact that items occur in some order than in the fact that you can look those items up using a numeric index.

I’ve also taken Guyren H.’s suggestion for method nomenclature: append inserts a new item at the tail of the list and chop removes it. Thus one can use the list as a stack through the push/pop/head functions, as a queue through the push/chop/tail functions, or as a deque by using all six of push/pop/head/append/chop/tail. All of these functions operate in constant time or amortized constant time.

These six functions are all I’ve built so far. You will eventually be able to insert, remove, or [lookup] a specific index, not to mention iterate over all the items or get the size of the list, but those operations require an extra level of bookkeeping I haven’t had time to implement yet.

Comparison operator overloading

I’ve just redesigned Radian’s suite of comparison operators so they can be implemented by any object. A “comparable” object is one which implements a compare_to method; this method must express the relative ordering of the self object and the method’s parameter. This is essentially the same as the Operator_Compare scheme I developed for REALbasic. I’ve added compare_to methods to the number and symbol atoms, and will do the same for the string atom too.

This came up because the map container needs to sort its keys in some specific order. Obviously the map can’t know about all possible key datatypes ahead of time, so the language needs a standard interface for comparability, and with that in place there’s no reason to implement the comparison operators any other way.

Map policy

I’ve been making some progress on the map datatype, one of a handful of built-in data structures. I decided to take the cheater’s way out and write it in C, inside the runtime library, instead of following my original plan and building it up from primitives (tuples) in Radian itself. I can always come back and rewrite it later; for now I am more interested in getting the language bootstrapped.

I’m considering a policy decision: what happens when you try to insert a value to a key which is already present? Does the map raise an exception, since you’re trying to do something whose meaning is somewhat ambiguous, or does it simply replace the existing value with the new one? The same question applies to the other map operations: what should happen if you try to remove a key which is not present? Does the map remain unchanged or raise an exception? Is the operation “make a map which lacks this key”, or “remove this key from the map”?

I am leaning toward raising exceptions in all of these ambiguous cases, because it seems more correct than making a policy decision which might be wrong sometimes. I am concerned that this will be annoying, though, and that the first thing I will end up doing is building a wrapper around the stock map that has the “just do it” behaviors.

LLVM integration success

The LLVM integration project has been coming along, and Radian no longer depends on GCC as a backend. It goes straight from Radian IR to LLVM IR and from there to machine code, which it runs in-process. This is not to imply that Radian is going to live in permanent JIT-land a la Python, but it’s easer to get things running that way. The runtime support is implemented as a separate library, which the compiler happens to link in, so the architecture still supports standalone executables.

Now that we’re using the actual target backend instead of emitting C source code and running through GCC, it’s time to implement the foreign-function interface. This will let us build Radian wrappers for any random shared library/DLL, and that’s the key to making this a useful system.

Other tasks on the near-term schedule are implementation of the intrinsic ‘map’ and ‘array’ types. I had originally intended to build the underlying AA-tree and finger-tree in Radian code, but bootstrapping is hard work, and I’ve decided to throw those data structures into the C runtime module instead. I can always port them back out sometime later.