Alex Saint Croix

Scala allows you to use the lazy keyword to defer the initialization of member values until they are called.  With this technique, you can implement some excellent data structures called streams.

As discussed in Chapter 3.5.1 of Structure and Interpretation of Computer Programs by Abelson, Sussman, and Sussman (a.k.a. The Wizard Book), streams are delayed lists. They let us use sequence manipulations without forcing us to incur the cost of implementing these sequences as lists.  Most importantly, we don’t have to initialize every value of a list in order to look at some of the values in the list.

Over the last two days, I’ve applied this technique to a stream-based QuadTree design, allowing me to have a data structure capable of providing access to massive (Terabyte-sized) terrain heightmaps without forcing me to load all of the terrain data into memory at once.  Moreover, I can use my streaming QuadTree class to generate the terrain, building as much or as little of it as I need for the sake of demonstrations, and preserving the concept of shared vertices between neighboring (or enclosing) branch and leaf nodes.

This design is modular.  Not as much as I’d like, and it needs more refactoring, but it’s modular enough that I could cache the terrain data to disk (or to a network service) after generation, and prune unused nodes from my local copy as I move through the terrain, in order to minimize runtime memory.

While technically possible to do this in Java, it would have been extremely ugly and complex.  Once again, I’m really happy to be writing this project in Scala.

Scala 2.9.0 final was released last night: http://www.scala-lang.org/node/9483

The Scala 2.9.0 codebase includes several additions, notably the new Parallel Collections, but it also introduces improvements on many existing features, and contains many bug fixes.

Eschewing method overloading as a matter of principle seems to conform to the general spirit of functional programming, though for the sake of fluent API designs it might still be useful.  I’ll have to chew on it some more.  Thanks for the detailed post, Chris!

iamchrislewis:

What does a compiled curried method in Scala look like in java? Compile this:

object Concat { def concat(s: String)(ss: String) = s + ss def concat(s: String)(i: Int) = i + s
}

Now inspect the resulting class with javap:

Compiled from "Concat.scala"
public final class Concat extends...

Upgraded to PicoContainer v2.10.  Close inspection convinced me that the new lifecycle annotation methods were absolutely crucial, library size be damned.

Here’s an example of how to construct a DefaultPicoContainer instance in Scala, using the  version 2.10 API:

    val pico : DefaultPicoContainer = new PicoBuilder().
      withJavaEE5Lifecycle().
      withConstructorInjection().
      build().
      asInstanceOf[DefaultPicoContainer]

That gives you the actual container.  You can now use it to register and instantiate components, like so:

    pico.addConfig("width", 800)
    pico.addConfig("height", 600)
    pico.as(Characteristics.USE_NAMES).addComponent(classOf[Box])

    val box = pico.getComponent(classOf[Box])
    println(box)

Which yields:

Box(800,600)

The motivation behind using PicoContainer will start to make more sense Real Soon Now™, as I start to add my giant web of dependent game engine subsystems.

Hope this saves you some time getting started with PicoContainer 2.10+ in Scala

Eye candy for Isometric, Terrain Engine, Scala, LWJGL,

Isometric terrain engine written in Scala and LWJGL.  First screenshot of 2nd generation engine still lacks many of the terrain processing features of my first cut, and the tiles in this screenshot are positioned manually just so I could get a screenshot.  Surface colors are determined by surface slope.

With a little effort and some “clever” workarounds (I don’t like these), I finally got my new vertex buffer object (VBO) code written in Scala!  The first tile was a simple cube, but I ran it through some tests to see a few of the other tileforms as well.  Instead of drawing the tile edges into the texture itself, I also implemented a wireframe overlay. In addition, I built a mechanism by which I can color the polygons based upon their surface slope, mapping slope to different color schemes.

Next on the list of things to do is redesign the “main loop” to limit it to about 60FPS and release resources when the window is not focused.  After that, I need to pull in all of the tileforms and start rebuilding the Terrain Processor system that takes heightmaps and “solves” how to represent them with the various tileforms.

I know that Scala has no static methods and it uses singleton objects instead.  I also know that Scala is supposed to be able to call Java methods, including Java static members.

Further, I know that org.lwjgl.opengl.ARBVertexBufferObject extends org.lwjgl.opengl.ARBBufferObject in the LWJGL library, and that the latter is generated code.

What I did not appreciate, but do now, is that Scala cannot make calls to static members in a superclass of a given class.  In order to call ARBVertexBufferObject.glGenBuffersARB(…) I need to either call ARBBufferObject.glGenBuffersARB(…) directly, or use some sort of calling class antipattern.

Needless to say, this is a headache.  Java / Scala interop is not quite where I’d like it to be, but I’m grateful for what does exist.

Software Engineering for breakfast at Espresso Royale on Ann Arbor Saline Road.

Yeah, I’m using PicoContainer version 1.3 still, because size does really matter a lot in game programming, and I’m not sure how much of what’s in 2.0 is sugar.  I’ll use it out of the box for now, but might chop it later if I don’t need some of what’s in there.

Which reminds me of something else.  Before I got sucked into grad school and surrendered my entire attention span for three and a half years I was contemplating writing a program specifically designed to chop down jars, discarding all of the classes that you don’t use, and removing references to them from their .class files.  Almost like what maven does for build dependencies, but more pernicious and thorough, and on a class-by-class basis instead of whole libraries at once.

Wouldn’t that be a cool tool?

Anyway, as promised:

import junit.framework.TestCase
import org.scalatest.junit.AssertionsForJUnit
import scala.collection.mutable.ListBuffer
import junit.framework.Assert._
import org.picocontainer.defaults.DefaultPicoContainer

class ExampleSuite extends TestCase with AssertionsForJUnit {
  def testPico() {
    val pico: DefaultPicoContainer = new DefaultPicoContainer();
    pico.registerComponentInstance("key", "bean")
    println(pico.getComponentInstance("key"))
    pico.unregisterComponent("key")
    println(pico.getComponentInstance("key"))
  }
}

Running this test inside of my JUnit test suite yields the following:

bean
null

I know it looks like a HashMap, but there’s so much more going on under the hood, this example is analogous to HelloPicoContainer. I’m actually feeling a little giddy. I’m going to bootstrap my entire OpenGL rendering pipeline in PicoContainer, and design components for managing lights, camera, physics, textures, and everything else. Instead of one ugly monolithic singleton state machine nightmare, I’m going to have containers running subsystem containers running components that can all be tested and easily maintained.

This is why Scala is so ridiculously powerful for graphics programming.  Assume I have these two lists representing x,y and z coordinates, and corresponding normal vectors for a couple of triangles that I want to draw:

val surfaceCoordinates = List(
  List(
    List(0.5, 0.5, 0.5), 
    List(0.5, 0.5, -0.5), 
    List(-0.5, -0.16666669, -0.5)), 
  List(
    List(-0.5, -0.16666669, -0.5), 
    List(-0.5, 0.16666666, 0.5), 
    List(0.5, 0.5, 0.5)))

val surfaceNormals = List(
  List(
    List(-0.5547002, 0.8320503, 0.0), 
    List(-0.5547002, 0.8320503, 0.0), 
    List(-0.5547002, 0.8320503, 0.0)), 
  List(
    List(-0.30151135, 0.90453404, -0.30151135), 
    List(-0.30151135, 0.90453404, -0.30151135), 
    List(-0.30151135, 0.90453404, -0.30151135)))

val s = surfaceCoordinates
val n = surfaceNormals

/**
 * Merges 2 nested lists into 1.  For example, vertex coords and vector normals. Can be chained.
 */
def merge(s: List[List[List[Float]]], t: List[List[List[Float]]]): List[List[List[Float]]] = {
  val buf: ListBuffer[List[List[Float]]] = new ListBuffer()
  for ((x,y) <- s zip t) buf += x zip y map {case (u,v) => List(u,v).flatten(w => w)}
  buf.toList
}

Now I can call:

val geom = merge(surfaceCoordinates, surfaceNormals)
println(geom)

List(
  List(
    List(0.5, 0.5, 0.5, -0.5547002, 0.8320503, 0.0), 
    List(0.5, 0.5, -0.5, -0.5547002, 0.8320503, 0.0), 
    List(-0.5, -0.16666669, -0.5, -0.5547002, 0.8320503, 0.0)), 
  List( 
    List(-0.5, -0.16666669, -0.5, -0.30151135, 0.90453404, -0.30151135), 
    List(-0.5, 0.16666666, 0.5, -0.30151135, 0.90453404, -0.30151135), 
    List(0.5, 0.5, 0.5, -0.30151135, 0.90453404, -0.30151135)))

Beautiful.

I’m using this method to construct my library of tileforms for conversion to Vertex Buffer Objects.  Needless to say, the coordinates and normals and so on are all programmatically generated as well.  When I’m done adding the color data and the textures, I can call:

println(geom.flatten(funk => funk).flatten(soul => soul))

List(0.5, 0.5, 0.5, -0.5547002, 0.8320503, 0.0, 
     0.5, 0.5, -0.5, -0.5547002, 0.8320503, 0.0, 
    -0.5, -0.16666669, -0.5, -0.5547002, 0.8320503, 0.0, 
    -0.5, -0.16666669, -0.5, -0.30151135, 0.90453404, -0.30151135, 
    -0.5, 0.16666666, 0.5, -0.30151135, 0.90453404, -0.30151135, 
     0.5, 0.5, 0.5, -0.30151135, 0.90453404, -0.30151135)

Boom! Instant VBO, baby.  Want to pick your colors based on height or terrain information, or something else?  No sweat.  Just mix them into the geometry and flatten, then feed your float buffers into VRAM.  Want to choose just textures, or just colors?  Remix and go.  

Not bad for 3 lines of code.

So.  

My plan was to save myself a lot of headache involving the silly amount of list and coordinate manipulation I was starting to do, and switch to Scala.  Great idea, things are now moving pretty quickly.  However, the decision came with some serious side effects.  First, Scala takes a long time to compile.  Type inferencing comes at a cost, and the compiler has to make two separate sweeps to make sure it conforms with Java type erasures as well.  Scala’s platform contains a lot of classes, all of which must be loaded into the class loader at runtime.  The potential savings gained from having fewer lines of code somewhat offsets this, but I found that compiles were taking an unacceptably long time to run a continuous build.

Searching for good ways to perform unit testing in Scala led me to ScalaTest, and upon installing it I realized I needed to upgrade from Scala 2.8.x to 2.9.x, so I did that.  Or tried to. Strange “file not found” compiler errors led me to the discovery that Scala 2.9 doesn’t run on IntelliJ IDEA prior to version 10.5, so I ended up gutting and reinstalling IDEA from scratch as well.

Once I got through that minefield and got my simple tests running, I started digging into setting up the Fast Scala Compiler (fsc) server to run in the background.  I’ve had very limited success with this.  In order to actually get it running I had to configure it in IntelliJ, then run it, copy the line from the run dialogue window into Terminal, un-b0rk some of the whitespace in the command, and run the server from the command line.

For a long time I struggled against this, without success.  Eventually I took a break, took a walk, went to the local cupcake shop and contemplated the matter while scarfing down a pineapple upside down cupcake.  When I came back, I dug some more and found a more straightforward thread about setting up fsc in IntelliJ IDEA. Nick’s description of the process gave me an idea.

I took out the port number from the fsc configuration screen and it. Just. Worked.

So, now I’m happily using the fast scala compiler, running my build every 30 seconds or so, cranking out unit tests to define my core logic behavior, and rapidly catching up to my last Java milestone.

When you code in Scala in IntelliJ IDEA, and especially if you use a test driven method like I do, you will find yourself constantly, constantly wanting to run the app.  In order to speed up this test driven development process toward continuous integration, and save yourself a lot of repetitive typing, you can use scala scripts in IntelliJ to do that bit for you.  This will help you to minimize the time you spend loading up the scala console, importing your classes, and running your test code.

Setting up a Scala script in IntelliJ IDEA is simple.  Here’s how:

1. Create a new file in your project.  Call it <InsertNameHere>.scala
2. Add whatever you would normally type into the scala console.  For example, to run the simple game display example I posted earlier today, you’d enter the following:
   

   import com.some.package.GameDisplay;
   
   val d = new GameDisplay();
   d.start();
   

3. That’s it!  Now you can skip the typing and run the app directly.  Just right click on the new .scala file in your project browser and select “Run”.  It will probably tell you that you need java.library.path added to your VM classpath, but once you’ve tried to run it you can configure the VM preferences for that.  For more information about how, read this handy guide on Setting up LWJGL in IntellJ IDEA.

Here’s how you bootstrap an LWJGL Display in Scala:

import org.lwjgl.LWJGLException;
import org.lwjgl.opengl.Display;
import org.lwjgl.opengl.DisplayMode;

class GameDisplay {

  def main(args: Array[String]) {
    val gameDisplay : GameDisplay = new GameDisplay();
	  gameDisplay.start();
  }

   def start() {
    try {
      Display.setDisplayMode(new DisplayMode(800,600));
      Display.create();
    } catch {
        case e: LWJGLException => {
          e.printStackTrace();
          System.exit(0);
        }
    }

	// init OpenGL here
	while (!Display.isCloseRequested()) {
	    // render OpenGL here
	    Display.update();
	}
		
	Display.destroy();
  }
}

Don’t forget to add the native libraries for LWJGL to your VM classpath.

That’s it!  Once you have this, the rest is standard rendering and update loop business.  Have fun!

Curious to revisit an earlier post about computations over lists versus arrays in Scala, and examine how the environment handles more difficult floating point operations with OpenCL acceleration under the hood, I rigged together this very very simple benchmark on scalacl/0.2.Beta10:

import scalacl._
import scala.math._

implicit val context = new ScalaCLContext

def testLists(num: Int): Float = {
val a = List.fromArray(Array.range(0,num))
val start = System.nanoTime
val result = a.map(s => cos(s / 100.0f).toFloat)
val end = System.nanoTime
((end - start).toFloat) / num
}

def testArrays(num: Int): Float = {
val a = Array.range(0,num)
val start = System.nanoTime
val result = a.map(s => cos(s / 100.0f).toFloat)
val end = System.nanoTime
((end - start).toFloat) / num
}

def testParallelLists(num: Int): Float = {
  val r = (0 to num).cl
  val a = r.toCLArray
  
  val start = System.nanoTime
  val result = a.map(s => cos(s / 100.0f).toFloat)
  val end = System.nanoTime
  ((end - start).toFloat) / num
}

def testSuite() = {
  val n = 10000000
  println(testLists(n))
  println(testArrays(n))
  println(testParallelLists(n))
}

testSuite()

:wq!
ListFlopParallel.scala (END) 

$ JAVA_OPTS="-Xmx1g" scala ListFlopParallel.scala

1050.4584
49.255398
22.513

I’m using an NVIDIA GeForce 330M GPU with a 48-core CUDA processor, and I suspect that there’s a significant overhead cost associated with shuttling the data between main memory and the GPU (and back). But, despite this overhead, as you can see, there’s still a ~2x speedup from pushing these floating point computations onto the GPU. Exciting stuff!

Unfortunately, in scalacl/0.2.Beta11, there’s no ability to convert functions that capture external symbols yet, so the code above doesn’t run.  Still, I’m looking forward to seeing where this project goes.  In the meantime, I plan to use good functional design principles and leave myself room to hook into OpenCL hardware acceleration later on.

• Pure object oriented language: everything is an object.
• Pure functional language: functions are first class objects, similar to ML or Haskell
• Uniform object model, similar to Smalltalk and Ruby.
• Universal nesting: Any type of object can be nested in any other type of object.
• Uniform access principle for method invocation similar to Eiffel.
• Actor-based concurrency inspired by Erlang.
• Treats infix operators like functions, similar to Iswim and Smalltalk.
• Permits function literals or blocks as parameters, allowing libraries to define control structures.

And now you can hook right into the GPU to perform parallel operations with hardware acceleration:

$ vi ScalaCLTest.scala

import scalacl._
import scala.math._

implicit val context = Context.best
// prefer CPUs ? Context.best(CPU)

val a = (0 until 100000).cl // this gives a CLRange

val result = a.map(x => cos(x / 100.0f).toFloat).zipWithIndex map { 
  case (c, i) => c * 10 + i 
} filter { 
  v => (v.toInt % 2) == 1 
}

result.foreach(println)

:wq! 
  
$ scala ScalaCLTest.scala 
11.998
13.992001
15.982005
17.968018
19.950043
21.928085
23.90216
25.872272
27.838436
29.800667
31.758974
33.71338
35.6639
37.610554
39.553364
...

I love this, it’s the first step toward really cracking into the world of GPU-accelerated parallelism and the awesome potential of Scala and OpenCL for computational intelligence purposes.  Thanks to Olivier Chafik for his continued efforts in building the ScalaCL library.