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.

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(b.plus(c)).minus(d)'. Personally, I like that.

.NET core spec more openly licensed than Java?

For the legally minded folks, how does this news from Microsoft compare to the licensing trouble between Sun/Oracle and Apache?

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("$Time.now: $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.

Firefox 3.5 and Ogg

Just wanted to say thanks to the Mozilla folks for having the guts to put Ogg in the browser. I know it won't have a deep impact overnight, but I think it might have deep long-term impacts.

Project idea for the willing and able: Make the video tag work cross browser. Swap via JS to Flash (or Silverlight or Quicktime or Java or ...) if video's not supported, automatically picking a different source. And make the paired sources easier to prepare on the server.

I guess the down side is that no one distributes video themselves, due to the large size, but maybe such a project would encourage the Vimeos, Hulus, and YouTubes of the world to consider support for open video. The goal in this case would be to make it easy for them to swap to Ogg (or whatever) video when Flash is unavailable.

Bonus points to Firefox if they ever get Canvas 3D in there. Even better to have an additional integrated mode for content inside and out of a 3D scene graph. (I suppose shouldn't get my hopes too high for Bullet physics ...)

Fan vs. Scala: Type System

It's been a while, but here's my next installment of detailed discussion of my personal reasons for preferring Fan to Scala. Here is my next claimed advantage:

2. In Fan, you don't have to figure out existential types or other complex typing. Fan will even do your casting for you in many cases.

There's a huge debate about dynamic vs. static typing. I like static typing (because of easier toolability, performance, and hints for the programmer but yes I know there are pros and cons). I don't like typing to get in my way. That means I only want to say as much as I want to say. That is, infer where possible, and sometimes I just don't care what's co or contravariant. (Oh, the blasphemy!) I also don't want the type system to tie me in knots. Sometimes static enforcement blocks me from doing something correct the way I want to do it, even if other times it catches my mistakes.

Both Fan and Scala (and C# and others) do limited type inference. Usually, you have to specify types for public methods and such. Sure, they could be inferred in some cases. Some languages do that, but I like it to be explicit. The exact limits of type inference differ among these languages, but most of the focus is on local vars. For example (in Fan):

greeting := "hello"
size := greeting.size

In Fan, ':=' is used for var initialization as opposed to the 'var' keyword in Scala or C#. You even use it when specifying an explicit type for the var, just for consistency. I like either style better than the "guess where the var is defined" behavior you get in Python or Ruby. (Actually, Python has fairly simple rules, but they can get annoying sometimes. I've heard Ruby is cleaning up their ambiguity in this arena, too.)

But, anyway, my discussion had more to do with this list of features from Scala.

1. Abstract Types
2. Existential Types (officially not recommended except for interoperability with Java, is my understanding)
3. Generics
4. Type Bounds
5. Variances
6. Views

And probably things I'm forgetting. Yes, the type system is serious in Scala. They want to you get it right. Personally, I see the need for awesome static typing in a language like OCaml that has no dynamic type safety (no casting exceptions) but still wants to be type safe and avoid security risks.

But in a language with dynamic type safety (like Java or ducky languages like Python, JavaScript, or Ruby), how often do you really see casting exceptions? If I make a mistake, it will be found (rather than opening security holes), and I don't usually make mistakes.

So, to make life easy, Fan will do your casting (up or down a hierarchy) automatically. For example (in Fan):

Obj[] items := ["something", "and", "more"]
Str message := items[0]

In Java, you'd have to make that second cast explicit, being a down cast. Welcome to "I don't need generics to have my casting done for me" land.

And while I know that Scala folks will be all over me about this feature of Fan, think first about Scala's automatic type conversion. Fan only casts for you (yay! in my book). Scala, for all its type safety will magically convert integers into strings, if you set up the right magic. I'm personally really scared of automatic variable swapping going on behind my back. It's also something I dislike about C#.

One thing that I don't like about Fan is its lack of generics (except for Lists, Maps, and Funcs). Yep, I like generics (despite my list above on Scala). I just want autocasting and arbitrary support for co and contravariance. I'm a hippie that way. I think Scala's generics go too far. So really, I'd prefer some land in between Scala and Fan on the generics front. But between the two, I'll take Fan.

Side note, Fan also supports dynamic duck typing. If you say, "myVar->something", that does a dynamic lookup rather than the static form "myVar.something". Note that this is different from duck typing support in languages such as C#, Boo, and haXe, where method calls look the same, but the variable type is declared to be dynamic. The two styles have different effects on your code. Scala shuns dynamic typing in favor of static structural typing. I'm not sure either take is fully necessary, but between the two (duck typing vs. structural), I'd prefer structural. I just don't want the rest of Scala typing with it. Sorry for being too quick to find good links, but Google can probably help out.

I'll give at least one link, though, to the official description of Fan's system.