Friday, July 24, 2009

Spore Galactic Adventures for Machinima?

My kids earned money to buy Spore after enjoying the free Creature Creator trial. I had though, "Wow, this could be great for machinima (making movies)!", but it wasn't really all there enough. And then my kids earned enough to buy Spore Galactic Adventures. After trying that out, I was really excited about the possibilities. But it's still not all there.

Here's an example of something I could do:

Talk about low res.

And they don't have recording of dialog. And it stops recording automatically every couple of minutes or so and some features of interaction are lacking and ...

You can't play the games themselves unless you own Spore Galactic Adventures either. So all I can really export is just the movies, which are lacking.

Could someone please make a serious, general-purpose, high-quality video machinima engine, please? I'm interested in it myself, and I might take my research directions into that someday (as well as robotics and AI which I focus on more at this point). Cause I can say that Spore GA is way higher level and easier to work with than Blender (even the Blender Game Engine). I personally don't mind lower quality for easier work. I'm not a full studio.

Spore GA might still be good for storyboarding, though, even if it's still lacking for movie production.

Monday, July 20, 2009

Fan vs. Scala: Nullability (including quizzes!)

Scala's great, but I personally prefer another new statically-typed language for the JVM, called Fan. I think some others might, too. This blog post is my next in a series of some reasons why I personally prefer Fan to Scala. Here was my next claimed advantage from my original post:

5. Fan types are not-nullable by default, with the concept built into the core of the language, instead of being "Option"al.

This particular subject is interesting. I've rarely seen ClassCastExceptions in practice, but I've seens plenty of NullPointerExceptions. Without good documentation (remember path of least resistance here), it's really hard to know whether a method expects to support null pointers or not. And in a method that has been around for months or years, it's hard to analyze whether all the callers (however far up the call chain) are passing in nulls or not. It's common to get null pointer exceptions in random places in your code all the time with enough developers and a large enough code base. And the solution to random breakage is ad hoc null checks and best-guess alternative behavior. That clutters up code and leaves expectations still unclear.

So, my answer is that nulls are usually evil. Apparently, I'm not alone in this opinion. Tony Hoare, for example, called null references his "billion dollar mistake" in ALGOL W.

My opinion of the right answer for Java is "don't use null if you can avoid it" and "document your methods as whether they support null" and "throw exceptions early if you get a null when you shouldn't". That takes a lot of manual effort in Java. And then there's the primitives not-nullable vs. objects nullable distinction, which is there mostly for convenience/performance. But it leaves the language more complicated than necessary.

So, both Fan and Scala seem to feel nulls are bad, too. They both discourage them. Fan avoids them by making every type not-nullable by default:
Str a := "hello"
Str? b := "world"
b = null // okay
a = b // NullErr run-time error
Str c := null // compile-time error

Lovely, lovely, in my opinion. The same type rules apply for method parameters. Yes, you should still document what your parameters mean, but your path of least resistance leaves you safe from nulls by default. And often, I think that's what coders mean, anyway. Usually, you get NullPointerExceptions because you just presume everything's not null, without even thinking about it. At least, that's how it often seems to me.

Also in Fan, the types 'Bool', 'Float' (64-bit), and 'Int' (64-bit) can be nullable or not. When not nullable, they are called "value types" because they are stored expanded (using 'boolean', 'double', and 'int' primitives in the JVM, for example). Fan also supports autoboxing along these lines. Happily, the '==' operator will compare values for these types (and is one of the overloadable operators for your own types, though I don't recommend overloading except for 'const' types in most cases). Anyway, this strategy also allows for faster math in many cases vs. purely reference-based languages. There are still some improvements needed relative to making the value types blend more transparently into the rest of the type system, but they are in the queue. The final goal is to make it blend almost seamlessly into the rest of the null-vs.-not-null type system.

Scala also recommends against null but in a very different way. They have very distinct reference vs. value types. All value types are predefined (I think) and mostly (but not entirely) correspond to the primitive types in Java. The reference types correspond to objects in Java. All reference types are nullable, but good style says don't use null. At least, when you don't need to interoperate with Java or whatnot. So, just keep in your head not to use null. Instead, you use 'Option' (usually, as there are other alternatives, too). My Fan examples above now look like this in Scala (if I'm not making any mistakes at the moment -- already fixed a few since my original post):
var a: String = "hello"
var b: Option[String] = Some("world")
b = None
a = b.get // NoSuchElementException run-time error
var c: String = None // compile-time error

I'm ignoring 'getOrElse' at the moment (just as I ignored the elvis '?:' operator in Fan above), by the way. I'm just focusing on the basic rules. My opinions on handling nulls when you have them are beyond my current scope.

So again, Fan has a (mostly) unified type system defaulting to not-null. Scala has a branched type system supporting value types on one side and and nullable references on the other, but don't use null. I think Fan's system is simpler, and I like that it pushes not-null into the strong position.

Well, I could be done here, but I'm not.

There's another word in Java that gives the same idea as the English word "null". That word is "void". If you know Java, you know what both keywords mean, but I think the relationship is interesting, and it brings up additional exploration for Fan vs. Scala, too. The value "null" is actually out there. It's a real thing that represents "no object". On the other hand, "void" really means "nothing". It doesn't exist. You can't assign it to anything. As a type, it is an empty set. I should also mention 'Void' in Java as the reflection-friendly type corresponding to the keyword 'void'.

Scala quiz time! Instead of describing what they mean, I'll give a list of similar concepts in Scala and see if you can match them with the correct meaning. If you read above, you'll get some of these. And maybe you can guess the others. First the Scala list of terms (all related to null and void in Java):

1. Null
2. null
3. Nothing
4. Nil
5. None
6. Unit
7. ()

And here are the definitions to match them against (in a mixed order):

A. The empty list.
B. The empty set type, corresponding to the meaning of 'void' in Java. The subtype of all value and reference types in Scala. The type parameter used for the empty list.
C. The single instance of type 'Unit'. I think it's purposely not supposed to mean anything.
D. The single instance of type 'Null'. Corresponds to 'null' in Java, but don't use it that way.
E. A subtype of all reference types in Scala whose only value is 'null'.
F. The instance of type 'Option' that means the option was not chose to be 'Some' value. Use with 'Option' types instead of 'null' for direct reference use. Also a kind of empty list.
G. A value type with only one (meaningless) member. Used in place of 'void', although it has a different meaning in my opinion.

Fan quiz time! I'm leaving out empty lists here, although you can have those in Fan just like in Java. They just don't have names or meanings so intertwined with 'null' and 'void', so just like Java, I think they are less relevant in Fan. Anyway, here are the terms I think should be considered:

1. null
2. Void
3. Void?

And here are the definitions to consider:

A. A type that corresponds quite closely to 'void' in Java. An empty set with no members, and only used for return types from functions.
B. A type with just the 'null' reference as a member. Somewhat related to the 'Unit' type in Scala, but I'm not sure it has any practical use. I think I'm glad it's there (just for consistency), and maybe it has some use I haven't figured out yet.
C. Corresponds to 'null' in Java. Assignable to vars of any nullable type.

Anyway, I hope this post was sufficiently readable. I think it's an important subject, and I personally like the solution that I think is simpler, more orthogonal, and less null-friendly. (And that particular personal preference is presumably easy to guess at this point.)

Wednesday, July 8, 2009

Prioritized Reduction Engine

I've been using MATLAB a lot in the past year. Many pros and cons with it, but it has definitely had me thinking from a batch update perspective. Saying 'a + b' can be really fast if 'a' and 'b' are both huge matrices. Despite some JIT support, MATLAB is generally quite slow if you want to write your own loops. While I still haven't done any explicit GPGPU programming, I have to imagine that the MATLAB batch/parallel operation mentality would map nicely to GPGPU thinking. I'm fairly excited about the whole OpenCL thing coming up. I like small computers rather than supercomputers, but I don't mind making more efficient use of them.

Anyway, while I've sort of gotten into the groove, I'm actually interested in a much fancier form of parallel computing. See my second bullet point here (on bubbling up). This has some relationships to the whole MapReduce concept, too, but I tend to imagine it fancier than that. The scheduler (or metathinker) becomes much more sophisticated, so it can handle the most important things first.

For example, I might want to add the elements in matrix 'a' and 'b', but maybe I care more about some of the results than others. And maybe I want to use those results in a later operation, say '(a + b) * c'. And I might have different tasks going on at the same time with dynamically adjustable priorities. And there might be different ways of getting to the same answer. A map might tell me where to go when I'm driving, but if I'm close enough, maybe I can look out and see where I need to go. Whatever data is available should also drive the later steps.

So we need a way to assess the value of single components of the operation and a way to execute the most important parts at all levels in parallel, such that the most important operations are getting done first. I haven't worked out all the details, but I know what I want it to look like. For example, I should be able to say '(a + b) * c' or much fancier programs and have it all just work prioritized and parallel in batch form. The priorities would have to be registered somehow, too, but perhaps separately from the algorithm chaining.

The ability to label intermediate computations for reuse at various steps could also be nice.

I think this concept isn't far off from the parallel and concurrency frameworks being built today. It's also not far off from current autoparallelization features today in systems like MATLAB and Fortress, but none of these have the same level of sophistication in dynamical scheduling that I want to see.

My current name for such a system is a "prioritized reduction engine". This is somewhere in between algorithms (iterative/online algorithms specifically) and parallel computing. Maybe I can find things in the literature about it. Sometimes it's hard to know the right words to use when searching.

Side thought I had while writing this: I wonder if there's ever any chance of getting GPGPU-powered math engines into web browsers. I guess I can dream.

Tuesday, July 7, 2009

Fan vs. Scala: Operators

Scala is a great, statically-typed language for the JVM with many advantages over Java. Some expect it to be "the next Java". It definitely has some momentum. However, I personally prefer another new statically-typed language for the JVM, called Fan. I think some others might, too. This blog post is my next in a series of some reasons why I personally prefer Fan to Scala.

Here was my next claimed advantage from my original post:

4. In Fan, you can't invent your own <**==!!! operator. (I haven't double-checked this particular one in Scala, but I've seen some doozies.)

Personally, I like operator overloading, because I'd rather say 'a * (b + c) - d' than 'a.multiply(b.add(c)).subtract(d)'. The former is more readable to me, and apparently someone felt that way in Java since they gave operators for basic numeric types in the first place. Well, it also helps to provide the separate worlds of primitives and objects that pervades Java.

However, in C++, people used operator overloading for the purposes of evil. That is, people sometimes have used say '+' to mean things very different from addition. That might have been encouraged by the C++ standard library immediately hoisting the bit shift operators (such as '>>') to provide IO services. Still, I don't see the evidence of widespread abuse even in C++, let alone other languages with operator overloading support. But I get the concern.

Scala is different from C++ in that you can invent your own operators. (I think Haskell might be the same and maybe other languages, too.) Then there's no need to abuse '+' when you can invent '+:+' instead (or whatever). For that matter, you can use normal methods as if they were operators. For example, instead of saying 'a.add(b)', you can say 'a add b'. My concern with Scala is the easy invention of creative operators. I have less concern about the use of named methods as operators.

My concern with invented operators is that I can't pronounce them, and I don't know what they mean. If I can read method names, I can guess what they mean. If I see a new operator, I have no idea. I also have trouble remembering lots of things, if I can't pronounce them. (Side note, IDEs may become vital in this matter for Scala.) I'll dodge the English-vs.-other-languages question at the moment, but feel free to weigh in on that, if you want.

Also, just like C++ immediately encouraged changing the semantics of operators (i.e., with ">>"), Scala has encouraged the use of fancy operators. Here's a list of operators extracted from the Scala standard library (based on this list):

^ ^^ ^^^ ^? ~ ~> ~! < <~ < <= == > >= >> >>> | || ||| - -= -> -- --= :: ::: :/: :\ ! != !! !? ? / /: /% * ** \ \\ & &~ && &&& &+ % + += +: ++ ++= ++: unary_~ unary_- unary_! unary_+

Off the top of my head, I can't guess at all what ':/:' should mean. Nor '^^^'. Nor some others. Combining this with implicit type conversion can make it so tracking down the source of an operator could also be tricky. So, I hope context usually makes things clear. And then there's that IDEs to the rescue again. IDEs are a fact of life these days, though, and once Scala IDEs get good enough, that might mitigate this concern to a large degree. Hard to say for every use case. By the way, an operator ending in ':' in Scala is right-associative. Meaning that 'a :: b' means 'b.::(a)' rather than 'a.::(b)'. I know some of why they did that, but it's definitely another issue to be aware of.

Here are some other discussions that show attempts at making up interesting operators in Scala. Might be some good and some bad in there, but overall it seems like excessive complexity to me. And in my opinion, hats off to Bill (in one of the links above) for choosing a clear name for his method.

Anyway, Fan lets you use operators (since like Scala and many other languages, it tries to avoid excessive primitive vs. object distinctions), but they are effectively shorthand for method names. This technique is also used in Groovy, MATLAB, Python, and presumably other languages. I like it because it reminds you what that operator should do. Here are the operators and rules for operator overloading in Fan. So, really, saying 'a * (b + c) - d' in Fan is exactly the same thing as saying 'a.mult('. Personally, I like that.

Friday, July 3, 2009

Formalized Path of Least Resistance

Just a quick note to myself (or others). I've more than once talked about how programming languages should be convenient but that the path of least resistance should encourage good programming. For example, Java's checked exceptions cause the path of least resistance to end up hiding error conditions and details. I don't like Java's checked exceptions.

It just occurred to me (though it's likely been done before by others) that you could formalize the path of least resistance when programming by approximating the gradient descent across some kind of vastly multidimensional space. By observing conditions when programming (maybe only visible in the programs produced, perhaps across time for openly accessible version control), you might be able to define a statistical distribution of cost functions used by programmers when making decisions. Hard to factor in things like deadlines, interpersonal concerns, life circumstances, and so on, but maybe some vague approximate model could be made.

Summary, hopefully in English, is that some folks like formalisms. Otherwise, they don't believe you at all. It might be possible to make a formalism to study the usability of programming languages for writing good software. Not 100% sure, though. Too many assumptions might be needed.

Fan vs. Scala: Globals and Variables

This is the next installment in my series hoping to elucidate my own preferences for Fan after having been a fan of Scala. I realize that the same thing isn't for everyone. If Scala works for you, great, and feel free to comment and/or correct any of my mistakes. For today, I'm now moving on to global variables. Here was my claim from my original post:

3. Fan doesn't encourage or even support global variables. It has an almost Erlang level of attention to concurrency. (Hopefully, people don't abuse 'object' in Scala for global vars, but I fear it's an easy trap, at least for newbies.)

This was perhaps one of my most unfair comparisons, but I still think there are interesting points to be made here.

One of the first questions is, what globals? When I speak of globals, I speak of globally accessible objects. Being in a namespace doesn't make something less global, for my present concerns. Such globals include types, packages/pods, and static functions/methods and variables/constants. Anything not "injected" (passed in from outside) is a global, really.

Here's where Scala takes an interest variation from most common languages. There are no "statics" in Scala. That's actually a nice simplification in ways. Instead of static members, you define singleton objects, like so (Scala here):

object OneAndOnly {
val favoriteNumber = 3
def favoriteDoubled() = 2 * favoriteNumber

Then you have an object accessible as 'OneAndOnly' (in whatever package), and you access its members sort of like you'd access statics in Java (or C++ or C# or Fan or such languages). See perhaps a more authoritative discussion in section 11 of this article. Singletons are also how you make applications in Scala:

object HelloWorld {
def main(args: Array[String]) {
println("Hello, world!")

Here's my main complaint: I'm a big dependency injection fan, with or without a framework to do it for me. I think singletons are teh evil. I don't want them to be easier to do. I'd sort of like to see a language without static access to type names and such like, though at some point it gets in the way of convenience, and sneaky tricks behind the scenes (classloader tricks and bytecode manipulation in Java, perhaps) can still inject behavior. Lots of pros and cons floating around here. But in any case, I'll at least stick to not encouraging singletons. I'm sure you could make (constant) singleton objects in Fan the old-fashioned way, but I don't recommend it.

Here's hello world in Fan, by the way:

class HelloWorld {
Void main() {
echo("Hello, world!")

I could have made 'main' static or allowed for args or whatnot, but Fan also allows simple modes like this where it instantiates a (non-singleton) HelloWorld object for you.

Anyway, where I was unfair in my original point for Fan vs. Scala was saying that Scala encourages global variables. It's not true. Scala encourages singletons, and you can have variables in those singletons, but every tutorial in Scala encourages the use of 'val' (think 'final' in Java) and 'def' (making methods) over 'var' (non-final vars or in other words, actual variables). While it's just as easy to say 'var', everyone will encourage you not to do so. Furthermore, they have lots of immutable types in the Scala standard library. That said, it might be easy to fall into the trap of using mutable vals or even just vars in your singletons. Especially if you aren't versed in the art of functional programming.

Fan, on the other hand, doesn't let you make global variables. And I'm talking your static members have to be 'const' not just 'final'. Further, closures are tracked dynamically for whether they reference non-const items, and you can't start a thread with access to mutable state from outside (Fan here, skipping into the middle of a method for convenience):

pool := ActorPool()
nums := [1, 2, 3]
a := Actor(pool) |Obj msg| {
echo("$ $msg")
nums[0]++ // <-- Error to reference non-const locals outside this block.

This nicely skirts the issues with 'final' or not for Java closures. (See more on Fan threading here, where I modified the above sample from.) And if I remember right in Fan (not double-checked right now), this is figured out at runtime. That is, some 'const classes' are known to be have const instances at compile time. But some types (such as List and Map) might have const instances or not. So a runtime check can tell whether a closure is const or not, too.

It might be possible these days to pass around non-const messages between actors in Fan. I'm not sure, but the idea would be that only one actor should own a mutable object at a time. I don't recall the details. Someone who's more expert on this should feel free to chime in.

In any case, while Scala pushed immutable, it doesn't hold you to it the same way that Fan does. And sometimes code development just flows in the path of least resistance. That least resistance should keep your code clean, in my opinion, and I think Fan is stronger here.

That said, Fan best practices do not emphasize final locals the same way that Scala does. Least resistance in Fan has all kinds of non-final mutability in your local scope (Fan here):

evenCount := 0 // Hey, look! I'm not final!
[1, 2, 3].each {
if (it % 2 == 0) {
evenCount++ // Okay since Fan knows you are using this in the same thread.

Personally, I like the mixture of mutable local state but const globals and cross-thread data. Apparently some other folks like the same style. See, for example, this discussion of the Reia programming language that allows non-final vars while compiling to Erlang's BEAM virtual machine. Good stuff, in my opinion, though I can't claim to be the super expert here. Just speaking from my own experience and understanding.