Mulling a small syntax change

Radian has three sorts of definitions: variables which hold a value and can be reassigned, constants which hold a value and cannot be reassigned, and functions which may have parameters and can be invoked to return a value. (Objects, methods, generators, and tasks are all different types of functions.)

Constants bug me because they aren’t really constant in the sense I am used to from C++. The definition can’t be changed, but its value certainly may, when it is defined in terms of variables. What’s more, the difference between a constant and a one-line function without parameters is so slight that I can’t think of any way you could tell the difference in code.

The change I’m pondering would be to ditch const entirely, then split the one-line function form apart from the block form. The new one-line simple definition statement would use the keyword def, borrowed of course from Python and Ruby. The zero-parameter form of this statement would be equivalent to the current const and to the current single-line parameterless function.

This change would regularize the syntax somewhat, in that each leading keyword would then unambiguously introduce either a single-line statement or a multi-line block. I haven’t been using const much because it often feels wrong, especially as an object member, where the “constant” is often defined in terms of variables; I think I might use def somewhat more.

The downside is that programmers familiar with Python or Ruby might find it jarring to find their familiar def keyword set to a similar but rather more restricted use.

IO, coroutines, generators

Radian’s functional semantics make synchronous I/O operations difficult, perhaps impossible; I certainly haven’t figured out how one would implement them. Instead, all I/O operations are performed asynchronously. A program’s job is not to perform I/O actions, but to describe them. You could think of a program as a function which returns a list of changes the external world ought to apply to itself. Each change has a continuation: another program to run once the change has been applied.

This lets you construct chains of I/O actions: read the contents of a directory, open all the files in it, transform the contents of those files, write them back. Each step is a little program which runs as the callback for the previous action, and then returns the next action.

The scheme works well in a mathematical sense but it’s a right nuisance in actual practice. Javascript programmers will be familiar with the issue: you end up with callback nested in callback nested in callback, and you can’t use the language’s built in flow control structures. You have to decompose your loops and conditionals into groups of functions by hand, and the result is hard to read.

The whole point of the Radian project is that the compiler should perform this kind of mechanical, predictable translation for you.You should be able to write straightforward straight-line code that expresses the algorithm you want to execute, and let the compiler figure out how to decompose that into a set of interrelated callback functions.

Let’s start by describing the IO process as an interface. It looks a lot like a sequence: a sequence contains a chain of iterators, where each iterator has a current value and a method letting you move on to the next iterator. An IO task contains a chain of sub-tasks, where each one returns an IO action to perform, and offers a method letting you move on to the next sub-task. The chief difference is that the “next” method needs some value as input, that being whatever came back from the IO action. It might be the contents of a file, the state of a socket, or an error condition flag, but whatever it is, it determines what the next IO subtask is going to do.

I’ll call this thing a “task”, and the subtasks I’ll call “steps”. Task will have a “run” method, which returns the first step; this is analogous to the sequence’s “iterate” method. Each step will have a “current” function, returning some IO action, and a “next” method which accepts the result of that action. Finally, a “valid?” method will return true when the IO task is complete; the terminal step has no “current” or “next”.

It is obviously be possible to use the existing object system to construct such a task, but that doesn’t solve the problem of having to decompose all your flow control by hand. The language needs a new bit of syntax: a task block, which defines a new task, and a yield operation, which marks the divisions between steps. The yield operation is like a function which accepts a parameter – that’s the IO action returned by “current” – and yields a value – which is of course the parameter the caller will pass in to “next”. It’s a doubly apt name: seen as a generator, the yield operator yields the generator’s output; seen as a thread, or coroutine, the yield operator yields control back to some other process.

Once this structure exists, I plan to redefine the IO system in terms of the “task” and “step” interfaces. The program itself will become one big task block, broken down into steps between each “yield” operation. The task syntax block will let you define these asynchronous state-machine tasks in the same way you can currently define ordinary functions and methods, and you’ll be able to create complex sequential IO operations by composing task instances in much the same way that ordinary functions can call each other.

This will completely change Radian IO syntax, of course. Right now one uses the ‘io’ object to create sequences of actions: it notionally represents the state of the world, and you wrap it in a series of actions to transform it. Once you return the resulting, modified state-of-the-world, that commits your changes to reality, and a new state-of-the-world (still called ‘io’) gets passed in to the next continuation function.

In the new system, there’ll be no need to represent the state of the world explicitly. IO actions will be simple objects; you won’t need to have a world-token in order to create them. It will be much more practical to have modules that manage specific types of IO, and return specific types of IO actions. Instead of making calls on the “io” object, you’ll yield things from function calls into various modules. For example, the hello world program will change from this:
io->print("Hello, world!")
to this:
yield console.print("Hello, world!")

This does mean that “yield” and the task system will have to be one of the first things people learn about Radian, but I suppose that’s worth the vast increase in ease of IO programming.

This scheme also opens the door for a lot of useful concurrency features. Tasks are basically coroutines; they’re like lightweight, cooperative threads which don’t need permanently-allocated stacks. You could have thousands of them running at once, Erlang-style.

Operator implementation

The infix operator implementations have always been something of a temporary hack. There was a built in list of arithmetic operations and comparisons for a while, then they became a series of intrinsic functions in the standard library. Over the weekend I reimplemented them in a more generic style. The infix operators are now nothing more than syntactic sugar: each one is associated with a well-known method name, and an object which wants to implement that operator simply provides a method with the appropriate name. This is the same basic idea as the compare_to method I described a couple weeks ago.

The implementations have not changed: the object member invocation syntax is a lookup operation anyway, so I’ve simply made the process of identifying the correct add, subtract, multiply, or divide function explicit instead of hardcoding the linkage into the compiler.

The operator-to-method correspondences are:

+ => add
-  => subtract
* => multiply
÷ => divide
mod => modulus
** => exponentiate
<< => shift_left
>> => shift_right

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.

Array as deque: API thoughts

Now that the map object is finished, the array is the only remaining intrinsic data type on the development plan. The point of an array, of course, is to store a series of values in some specific order, and to allow efficient access to those values by index. Radian’s arrays will use a densely-packed zero-based ascending index, which is to say they will not have gaps, and that an array containing N items will store values at indexes 0..(N-1). Perhaps someday it will make sense to allow a variable lower bound, or to allow gaps in the index, but for now I don’t want to worry about those complications.

An array is a container, so it will have empty? and size functions. It is a sequence, so it will have iterate. It is also an indexed container, so it will also have a [lookup] function and the insert and remove methods.

The best way to implement this data structure is, without a doubt, the finger tree. This is an immutable data structure which offers some highly appealing performance characteristics and has enough versatility to serve as the foundation of a deque, a string, an array, a priority queue, and more.

Ah yes, the deque. I grew up on arrays, but these days I more often find myself reaching for queue, stack, or deque classes when I need to keep a list of values in some order. Most of the time, it turns out, all I really need is a way to construct a list and review it in order, or possibly in reverse order. The Radian library definitely needs to include such tools.

So why not, I wonder, fold the deque right into the array? The finger tree offers amortized constant-time read and write access to the first and last item in the array, so the deque operations would practically come along for free if I decided to expose them. Methods push, pop, and head would let you insert, remove, or lookup the item at one end of the list, and add, shift, and tail would let you work with the item at the other end. Push/pop/head gives you a stack; push/shift/tail gives you a queue going in one direction, and add/pop/head gives you a queue going in the other direction.

I’m not completely satisfied with this nomenclature: in particular, I don’t think shift is quite right for an operation which removes the last entry from the array. It feels like it ought to remove the first entry, thus shifting all the other elements back. That would certainly work, but then “pop” has to move to the end of the list, which means “push” has to come with it, and now the head and the tail are backwards. Could the head really be the last element of the array, and the tail represent element zero? No matter which way I try to arrange this, something ends up sounding a little bit wrong.

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.

Beginning of a type system

Last night’s checkin added a new binary operator: has lets you inquire about a container’s attributes. The has operator has the same precedence as the comparison operators. Its left operand must be a container and its right operand may be any value. The result is a boolean, which is true if looking up the value in the container would result in a non-exceptional value, false if the lookup would fail.

Combining this with the new symbol-literal syntax lets you ask whether a given object implements some method:

if foo has :bar:
    foo->bar(42)
end if

Testing for a set of related methods lets you determine whether an object implements some interface:

function stack?(foo):
    result = foo has :push
    result = result and foo has :pop
    result = result and foo has :head
end stack?

Syntax for a symbol literal

Symbols are a kind of atomic datatype which can be used to identify things within a program. You can think of them as a unique-ID. The Radian compiler generates symbols internally as part of the object structure, using them as keys in the member index; member access on an object then uses the same symbol to look up the method.

Examples of symbol literals in other languages – these are the only examples I know about, as most languages don’t use symbols:

• Ruby: :foo
• Scheme: 'foo
• Clojure: :foo
• Scala: 'foo

I’m not happy with either of these: the apostrophe feels too much like an unbalanced single-quote, and the colon already has two other meanings in the Radian syntax. Using it to begin a symbol would not introduce ambiguity, but I am concerned that reusing the same character in too many different situations would confuse people.

Determining whether an object has some method or property

• Ruby: has = foo.respond_to?('bar')
• Python: has = getattr(foo, "bar", None)
• JavaScript: has = foo.hasOwnProperty('bar')
• PHP: has = method_exists($foo, "bar");
• Perl: has = $foo->can("bar");
• C#: has = foo.GetType().GetMethod("bar") != null;

This is also possible in Java, using the reflection API, which is so verbose that I refuse to waste time typing out an example. I don’t know whether Scala or Clojure has better syntax than Java does, but presumably they can at least use the same API.