Sunday, January 16, 2011

Closures are now regular objects

Well, that didn't take long.

Previously, closures were implemented as a special data type consisting of a pair (function-pointer, environment). Now closures are regular objects that implement the Function interface:

/** Interface that represents a callable object. */
interface Function[%ReturnType, %ParamTypes...] {
  def (params:*ParamTypes) -> ReturnType;
}

This means that from the caller's point of view, there's no difference between a closure and any other object that is callable.

There are several language features worth highlighting the the above code snippet:
  • Templates with variadic parameters.
  • *ParamTypes to expand a list of types as a function signature. Works with any tuple type, not just template params. (Although it's currently limited to methods that don't have a body, since I have not yet added code to access the parameter values.)
  • def () syntax for defining a callable object (similar to Python's __call__.)
Unfortunately, bound methods are broken by this change, I'll fix them up later.

Thursday, January 13, 2011

More on statements as expressions

I've been playing around with this idea some more, and I'm starting to like some of the results.

Here's the specific changes that would be made to the language syntax:

  • The following statements will be able to be used as expressions:
    • if
    • switch
    • classify, which will be renamed 'match'.
    • with
  • Statement blocks can be used as expressions.
    • The last statement in the block is the result.
    • The semicolon after the last statement is now optional - meaning that semicolon now becomes a statement separator rather than a statement terminator.
    • Braces are still always required around statement blocks.
    • Return values can be type 'void' if there's no actual value to return.
    • One particularly challenging issue will be making the type inference system smart about statement blocks - that is, the type of the last statement in a block will in some cases be inferrable from the type of expression that block is assigned to.
  • The 'return if' syntax is no longer allowed ("return value if condition") since it's ambiguous.
    • We can still keep "break if" and "continue if" if desired, but it may be best to remove those as well. I need to think about it.
  • 'cond' goes away as it is no longer needed.
    • Macros can stay for the moment, as they are needed for assertions (they make it possible to print the string form of the assertion expression.)
Here's some example syntax to show how the code would look:

// All in one line
var x = if n != 0 { result1 } else { result2 }
var x = if n == 0 { result1 } else if n == 1 { result2 } else { result2 }

// Multi-line if
var x = if n == 0 {
  result1
} else if n == 1 {
  result2
} else {
  doSomethingBeforeReturning();
  result2
}

// if-statement as a function argument:
writer.printLn(

  if n == 0 { result1 }
  else if n == 1 { result2 }
  else { doSomethingBeforeReturning(); result2 });

// Match statement
var x = match n {
  as s:String { "String" }
  as t:Type { "Type" }
  as * { "Other" }
}

// Switch statement
var x = switch n {
  case 1 { "one" }
  case 2 { "two" }
  case * { "none" }
}

// With statement
var str = with f:open(file) {
  ",".join(f.lines())
}

// With statement with multiple values
var str = with (f1:open(file2), f2:open(file2)) {
  ",".join(f1.lines()) + ",".join(f2.lines())
}


In my earlier post, I suggested that try/catch also be usable as an expression, however there's a bit of a problem there, which is what to do with 'finally'? When used without a 'finally' statement, the flow of control in a try/catch always reaches the end of one and only one block - so you know exactly which value is returned. With 'finally', however, it's not clear whether the value returned is the one at the end of the finally block, or one of the other blocks.

Tuesday, January 11, 2011

Tart status update

I've started working on Tart again, after a break of about a month. The reason I stopped was that I was feeling a bit burned out, and I felt like I had hit a wall with respect to some unsolved problems. I figured that if I deliberately kept away from working on it for a while, I'd not only recharge my batteries, but perhaps I could get some new inspiration as well.

And in fact I did have some minor brainstorms during this period, which made me want to work on it again. Here's a summary of the direction my thoughts have been going lately:

Reflection

If you remember from earlier, I had been kind of obsessing about the large amount of reflection metadata that was being generated. Well, I've made a decision, which is that reflection will now be an opt-in rather an opt-out for classes. That means the compiler will not generate reflection information for class methods and fields unless there is an annotation telling it to do so.

The @Reflect annotation will cause a class, and all of its subclasses, to be fully reflected. In addition, any class member which has an annotation will be reflected, if that annotation is retained in the final executable (the reflection structure is what holds the list of annotations, so it needs to present in order for the annotations to be found.)

Initially, I assumed that all classes would want to have detailed reflection information. My rationale for assuming this is that reflection is about discovery - it's about taking a data type that your code never seen before, and extracting information from it. I reasoned that for any given class, there's no way to know what possible future users of that class might want to discover, so the policy would have to be conservative and inclusive.

However, after thinking about this some, I realized that in practice, the use of reflection generally begins from some known starting point, such as a particular interface, or classes annotated with a particular annotation. Take for example JUnit - it uses reflection to identify all of the test methods within the class (any method that begins with the word 'test'.) However, it only does this for classes that are derived from TestCase. So that's a known starting point. Similarly, another classic use case for reflection is to be able to serialize or edit a class by getting a list of it's properties. However, the author of the class to be serialized or edited generally knows in advance that this is going to happen, and designs the properties and fields of the class to facilitate such access - so requiring an extra attribute on the class to enable this is not a big hardship.

Another common pattern is to scan the class members looking for ones that bear a particular annotation. An example is Guice's dependency injection logic - it scans a class for any constructors that are annotated with @Inject or @Provides. It's not interested in class members that don't have annotations, so there's no need to reflect those.

One possible pitfall of this scheme is that a reflected class may have members whose types are not reflected. For example, a class might have a member whose type is List[String]. Neither List nor String are reflected by default. That means that if you were trying to do a recursive traversal of some tree of objects using reflection, you wouldn't be able to traverse fields with these types. That doesn't mean that you would have no information at all - non-reflected classes still have information about their name, module path, base classes, type parameters, and so on. They just lack information about their members.

For the case of List[String], your traversal algorithm could just have a special case for fields of type List, and iterate through the list normally instead of using reflection. You still wouldn't be able to handle fields whose types were both non-reflected and unfamiliar to your code. The question is, how important is this use case? At the moment, I can't think of a situation where this would be important, but I could be wrong.

The advantage of the opt-in strategy is three-fold: First, it means that we don't generate a pile of unneeded metadata each time a template gets instantiated. Secondly, because we no longer have to worry about size, I can rip out a whole bunch of complicated compression / decompression logic from the Tart runtime (although I still keep method descriptors and field descriptors compressed, but not types). And finally, since I'm no longer creating types lazily, it means that reflection metadata can go back to being static constants - which means that every type Tart once again has a unique, canonical, immutable pointer for its runtime information.

Functional Style

After watching the Scala presentation at Google last month, I realized that there might be some advantage to making some statements more functional in style than they currently are. This doesn't mean that I've drunk the functional programming kool-aid, and I certainly don't think that functional programming is the panacea that some of its adherents claim. However, I was pretty impressed with the brevity of the code examples and the clarity of the abstractions involved.

Thinking about those code samples makes me realize that there's a very common coding pattern in imperative languages that kind of annoys me, although my level of annoyance was so minor that I wasn't aware of it before. Here's some examples:

Example 1:

Record record;
if (some_condition) {
  record = dataSource.getRecord(FIRST_ID);
} else if (other_condition) {
  record = dataSource.getRecord(SECOND_ID);
} else {
  record = dataSource.getRecord(OTHER_ID);
}

doSomethingWithRecord(record);

Example 2:

Record record;
try {
  record = dataSource.readRecord(RECORD_ID);
} catch (IOException e) (
  logger.log(e);
  return;
}

doSomethingWithRecord(record);

In both cases, we're assigning to a temporary variable because in Java/Python/C++, expressions are subservient to statements - that is, statements may contain expressions, but expressions can never contain statements. If we want to calculate an expression where there is control-flow involved in the calculation, then we have to break up the expression into multiple statements.

(Note that Example 1 can be generalized to switch statements as well as chained if-else statements.)

A language that supported a functional style, in which statements could return values, would allow these statements to be written more concisely:

doSomethingWithRecord(
    if (some_condition) {
      dataSource.getRecord(FIRST_ID);
    } else if (other_condition) {
      dataSource.getRecord(SECOND_ID);
    } else {
      dataSource.getRecord(OTHER_ID);
    });

doSomethingWithRecord(
    try {
      dataSource.readRecord(RECORD_ID);
    } catch (IOException e) (
      logger.log(e);
      return;
    });

Of course, Tart already lets you do the first with the 'cond' macro:

doSomethingWithRecord(
    cond(some_condition, dataSource.getRecord(FIRST_ID),
         other_condition, dataSource.getRecord(SECOND_ID),
         dataSource.getRecord(OTHER_ID)});

There are several problems with 'cond' however:
  • It looks different from a regular if-statement. In other words, the language has two completely different if-statements, one functional, one procedural. Think about this for a moment from the perspective of an IDE with syntax highlighting - the 'cond' macro will be syntax-colored just like a regular function call, but it would be nice if the editor could syntax-color it like a flow-of-control construct.
  • The 'cond' macro only allows a single expression to be returned as the result of each if-test. It would be better if the 'value' argument could contain multiple statements. (You can do this by making a closure, but that's overkill IMHO.)
  • 'cond' relys on Tart's macro system, a feature which so far is not pulling it's weight in terms of benefits delivered. I think language features which are only useful in obscure edge cases should be removed, and so far macros have exactly 3 use cases: 1) cond, 2) lazyEval, and 3) assert.
For the second example, with the try-catch statement, we have another interesting issue, which is the behavior of the return statement. When used as an expression, 'return' acts as a non-local exit out of the function - it effectively cancels the function call as a side-effect of evaluating the calling arguments. Pretty freaky but completely logical given the original example that it was derived from.

Unfortunately, there's no way that Tart's macro system can implement try-catch as an expression. If we want to support cases like this, then it's got to have some sugar from the compiler.

If we decided to go down this road, one of the first things we would need to deal with is how to handle expressions containing multiple statements:

doSomethingWithRecord(
    if (some_condition) {
      doSomePreperatoryWork();
      dataSource.getRecord(FIRST_ID);
    } else if (other_condition) {
      doSomeDifferentPreperatoryWork();
      dataSource.getRecord(SECOND_ID);
    } else {
      dataSource.getRecord(OTHER_ID);
    });

In the above example, the first if-block has two statements. What is the value that results when that branch of the if-statement is taken? We can't use the 'return' statement at the end of the block, because as we've seen that returns from the function as a whole. We could come up with some new keyword to indicate the result produced (I haven't been able to think of one), or perhaps some new operator, or we could do as some languages do and say that the last statement in a block is always the result. I don't particularly like the implicit last-statement rule, EIBTI.

(Pure functional languages don't generally have this problem because they don't have 'statements' per se, only expressions.)

It also quickly becomes obvious that the block statements { } are in fact expressions. Does this mean that one can omit the 'return' statement at the end of a function, and just put an expression? That's annoyingly perl-ish from my point of view.

There's also the question of whether all those braces are necessary. Tart's rule for block statements up to this point has been that the braces are not optional, but the parens around the condition can be omitted. However, I'm pretty open to a certain degree of design churn for an experimental language in development, which is another way of saying that I'm open to changing my mind.

In any case, I haven't come to any conclusions on this matter as yet, so no action will be taken.

Functions as Objects

I'd like to be able to write the following in Tart:

interface Function[%ReturnType, %ParamTypes...] {
  def (params:ParamTypes) -> ReturnType;
}

I currently can't do this because ParamTypes is a variadic template argument. Ideally, the Function class should be able to take a list of 0 or more function parameter types as template arguments, such as Function[String, int, int, int].

Secondly, I'd like closures and bound methods to implement this interface - that is, if you have a closure, you can assign it to a variable of this type, assuming the parameter types match. 
Also, the type declaration 'fn (params) -> ReturnType" should simply be a shortcut for this type. Doing that involves changing the internal representation of closures to be more like objects, so that when a closure is called it goes through the normal vtable dispatch mechanism.

The advantage of doing this is that you can derive new classes from Function, and they can be used in all of the same places that closures and bound methods are used (similar to __call__ in Python.)

There's another cool feature that I'd like to steal from Scala: Let's say you have a function that takes as its argument an interface with a single callable method, such as Factory[String].build(). In Scala, you can pass a closure as that argument instead of creating a class which instantiates that interface. So for example:

interface Factory[T] {
  def build() -> T;
}

def buildLotsOfStuff(factory:Factory[String]) {
  // ...
}

// Convert a closure to a Factory[String].
buildLotsOfStuff(fn { return "Hello"; });

// In Java, we'd have to do this much more verbosely:
buildLotsOfStuff(new Factory<String> {
  public String build() {
    return "Hello";
  }
});

I'm not quite sure how Scala does this - that is, there are two ways I can think of to do it, but each has disadvantages. The first way is to automatically generate an adapter object when the closure is converted to a reference to type Factory.
So for example the compiler would generate something like this:

class AnonymousFunctionAdapter : Factory[String] {
  var closure:fn -> String;

  def construct(closure:fn -> String) {
    self.closure = closure;
  }

  def call -> String {
    return closure();
  }
}

This works in all cases, but is less efficient because of the overhead of calling the adapter and because you have to allocate the adapter instance.

The other approach would be for the compiler to generate the closure itself as an instance of Factory[String]. All that is required in this case is to add the additional dispatch table entries to the closure's class - that is, the actual method pointer would be copied into two dispatch slots, one for Function.(), and one for Factory.build(). This means that you avoid allocating the extra object and the code is able to jump right into the method body directly without having to pass the arguments through the adapter.

However, there's a drawback, which is that this technique only works if the compiler knows what type the closure is going to be cast to at the point where the closure is generated. If we pass the closure around as a function pointer, and then later decide to cast it to some other callable type, we won't be able to modify the closure to conform to that type's calling conventions.

Monday, December 6, 2010

Should parameter names be part of the function type?

Here's an issue which I have been ignoring for a long time, but which is starting to become a pain point.

Tart supports keyword arguments in a manner similar to Python: When calling a function, any parameter can be referred to by name or by position. Parameters can also have default values, so you can have a function with a large number of parameters having default values, and use parameter names to pick out just the ones you want to have non-default values. (Whether this is a good API design choice is an open question.)

However, under the hood Tart does this very differently from the way Python does it. In Python, the matching of argument keywords to parameter positions is done at the time the call is dispatched. Since creating a dictionary is cheap in Python (in a relative sense, at least), the named parameters are bundled into a dictionary and the contents of this dictionary is matched against the parameter names of the called function.

In Tart, because it's a statically typed language, the matching of keyword arguments to parameter positions is done at compile time. (One of Tart's design principles is "if you can't figure out how to make it fast, it doesn't go in - meaning that no language feature is allowed if ordinary use of that feature would create a performance bottleneck.) Tart doesn't create a dictionary of keyword arguments - instead, the compiler internally creates a map of keyword arguments to parameter positions, and uses this information to re-arrange the order of arguments of the call. Any arguments not explicitly mentioned are filled in with their default values. In other words, all of the keyword stuff is just syntactic sugar on top of a C-style calling convention. Note that this also means that the Python feature of unpacking a dictionary via **args isn't supported.

In order for this to work, the names of the function parameters (and any other trait that would change how a function gets called) need to be part of the function's type. That means that f(a:int) and f(b:int) are actually different types.

Where this gets weird is when you start having things like pointers to functions. Imagine the following:

def f(a:int, b:int) { ... }

let f2 = f;
let f3:fn (b:int, a:int) = f;

Here we've assigned the original function 'f' to two function variables, one which has the same type as 'f', and one which defines a different function signature with the order of parameters reversed. Note that even though f3 is a different type than f, the conversion is allowed - the compiler doesn't consider the types to be incompatible just because the parameters have different names. Essentially, the names of the parameter are what I call a "type hint" - meaning that they make the type distinct, but it's a distinction without a difference as far as the type conversion checker is concerned. (The reason for this is simple: If we didn't allow function types with different parameter names to be interconvertible, then every function pointer would have to have the exact same spelling of the parameter names as the function that was assigned to it, which would make life hell for programmers.)

Thus, in the above example, if we call f3(a=1, b=2) it's the same as if we called f(a=2, b=1). Trippy, dude!

Where this starts to get painful is when we try to represent this information in the reflection metadata. As you know, one of my challenges has been to avoid a combinatorial explosion of metadata that gets generated along with a class or function. One way to do this is by sharing definitions whenever possible, so that two functions with the same type can point to the same type definition. Thus, in an ideal world, all functions with the type signature f(:int) could point to the same definition. However, if we include the parameter names along with the type, then the amount of sharing diminishes greatly, since it's unlikely that two functions will have both the same parameter types and parameter names.

Now, all this being said there's an alternative strategy I could have chosen, which is not to make the parameter names part of the type. In this strategy, when a function is called, the parameter assignment logic looks beneath the type to the actual function declaration being called. In the case of function pointers, where there is no underlying function declaration, keyword arguments simply wouldn't be allowed. I suspect that this would cause even more confusion than the case outlined above. However, it would have greatly simplified the logic of function types.

Actually, this is not strictly speaking true: every function type ultimately derives from a declaration somewhere - even a function value which is the result of some complex expression still has a type declaration which ultimately leads back to some variable or function declaration. The reason this is true is because even though functions can be created dynamically, function types can't be. So it might be possible for the compiler to examine an expression of function type, and by diving deep enough in the expression it could find the original function declaration. I'm not sure this strategy is any different than having the information be encoded in the type, nor am I certain I could make the compiler smart enough to figure this out in all cases.

Monday, November 29, 2010

Integer parsing checked in

Tart programs can now convert strings to integer types:

let n = int8.parse("10");
let m = int32.parse("fff", 16);

Features:
  • The implementation is pure Tart - no calling C library functions. It is also efficient :)
  • Radix conversions from 2 to 35 are supported.
  • Overflow is properly handled, even for 64-bit ints - so for example if you attempt to convert 9223372036854775809 to a 64-bit signed int, it will throw an OverflowError.
  • Bad input strings throw an InputFormatError.
  • Currently supports all integer and boolean types.
Character and float types are not implemented yet. I probably won't be able to do a pure-Tart implementation of float parsing, because that's hard to get right. So I'll probably end up having to call strtod(). Unfortunately strtod() has much less restrictive input conditions that I'd like (allows junk characters at the end, for example.)

There's also a "tryParse" function in the "Strings" namespace for each numeric type that returns either a numeric value or a conversion error:

def tryParse[uint8](s:String, radix:int) -> uint8 or ConversionError;

Note that the reason for naming it 'tryParse[uint8]' instead of 'tryParseUint8' is to make it easier to work with templates.

Thursday, November 18, 2010

More Closure Fun

Here are some more closure test cases that work:

// Test the closures can be passed as parameters
def testClosureAsParam {
  var i = 0;
  callTenTimes(fn { i += 2; });
  Debug.assertEq(20, i);

  var s = StringBuilder();
  callTenTimes(fn { s.append("A"); });
  Debug.assertEq("AAAAAAAAAA", s.toString());
}

def callTenTimes(f:fn) {
  for i = 0; i < 10; ++i {
    f();
  }
}

// Test that nested closures work.
def testNestedClosures {
  let makeCounter = fn n:int -> fn -> int {
    return fn -> int {
      return n++;
    };
  };
  
  let c = makeCounter(2);
  Debug.assertEq(2, c());
  Debug.assertEq(3, c());
}

// Test that an inner closure can access a variable two levels out.
def testNestedClosures2 {
  var i = 0;
  let makeCounter = fn -> fn -> int {
    return fn -> int {
      return i++;
    };
  };

  let c = makeCounter();
  let d = makeCounter();

  Debug.assertEq(0, c());
  Debug.assertEq(1, c());
  Debug.assertEq(2, d());
  Debug.assertEq(3, d());
}

One thing that does not work yet is closure variables that are large structs or tuples - basically any local variable that is not an object reference or a primitive type. It shouldn't be hard to fix, however.

Wednesday, November 17, 2010

Closures

I decided to take a break from the low-level work of debugging and garbage collection, and work on some language features, which is a much more pleasant activity. It only took a couple of days to get closures working. Here's one of the unit tests, for example:

def testClosureCounter {
  var a = 0;
  let f = fn -> int {
    return a++;
  };

  Debug.assertEq(0, f());
  Debug.assertEq(1, f());
  Debug.assertEq(2, f());
}

The mechanism behind closures is fairly efficient: The closure environment is a subclass of Object that has a member slot for each captured variable. For 'let' variables (which cannot be changed after the initial assignment), the slot contains just a copy of the variable. For 'var' variables, the slot is a reference to a shared closure cell, whose type is tart.core.MutableRef[T], so that both the inner and outer functions can modify the same variable.

The closure itself is passed around as a pair of pointers - the pointer to the executable code, and the pointer to the environment. Note that closures are type-compatible with bound methods - that is, anywhere you can put a bound method, you can also put a closure, assuming that it takes the same argument types.