31st May 2013

Post

About code conventions and pretty code

This time I’ll post some kind of answer to Joel on software’s blog post, to be exact, the part “The Real Solution”. You should read the blog post to that position. After you’ve then read mine, I advise you to read the whole article, because it’s good. Also, joelonsoftware.com’s articles are almost all awesome!

Anyways, more apologies: I know he’s not trying to write how to do it right (even when it might sound like that: “The Real Solution” ;D), he was just trying to show how naming conventions can help spotting smelly code, which could even be buggy.

His solution is to put a us for every variable name, which stores an “unsafe String” and a s in front of every “safe” String.

Now I asked myself: Can’t the compiler look whether you’ve put a us or s before variable names and function names and check them to match? Well… The “Real” solution wouldn’t be to check yourself whether those stuff matches, but to let the compiler check that.

No, the compiler won’t check variable names. The solution is to check types. Abstraction is always the most important thing, when programming!

So let’s dive directly into our solution code. First we need to define a way to encode our string and write the request method. The request method will be faked ;)

def request(message: String) = 
  "matheus23"
def encode(string: String) = 
  string
    .replaceAll("<", "&lt;")
    .replaceAll(">", "&gt;")
def write(string: String) =
  println(string)

Okey, so now that’s done, lets write our class structure. Everything is based on the String class, so we’ll need to store the very raw String as data inside all objects, so it’s still accessible. We have a root type HtmlString and two subclasses representing whether they were encoded or not: SafeString and UnsafeString:

sealed trait HtmlString {
  val data: String
}
case class SafeString(data: String) extends HtmlString
case class UnsafeString(data: String) extends HtmlString

That’s it. I don’t know if this is completely right, but I think that’s called Pantom Types. And as you can see it’s a very simple design pattern, but for now it’s very, very verbose to use:

val name: UnsafeString = UnsafeString(request("name"))
// [...]
write(encode(name.data))

As for now, as you can see it’s very verbose, and it’s completely useless and senseless, since the compiler doesn’t check anything. For that we need to change the methods we defined above to use the new classes, so that request returns an UnsafeString and write only accepts a SafeString:

def request(message: String): UnsafeString = 
  UnsafeString("matheus23")
def encode(string: UnsafeString) = 
  SafeString(string.data
    .replaceAll("<", "&lt;")
    .replaceAll(">", "&gt;"))
def write(string: SafeString) =
  println(string.data)

And wohoow! It works perfectly now, and is compile-time checked and everything is awesome:

val name = request("name")
// [...]
write(encode(name))

And if we’d try to use it in a wrong, harming way:

val name = request("name")
// [...]
write(name) // no encoding this time! :/

We’d get an error, at compile-time:

<console>:23: error: type mismatch;
 found   : UnsafeString
 required: SafeString
              write(name) // no encoding this time! :/
                    ^

Awesome! :)

One last thing: This is possible in almost all object-oriented languages, but not in languages like C. So that might be a reason for joel not being able to abstract that away :)

Now, I’m going to finish reading that article…

22nd May 2013

Post with 2 notes

Scala and extending Numeric[T]

Starting simple

I bet you always wondered how to write a purely generic Vec2 class (a class holding a numeric x, and a numeric y, which allows mathematical operations with that so-called vector). If not, you probably wonder now! :)

In scala you usually do it like that:

class Vec2[T](val x: T, val y: T)

So far, so good. What you can do now, is allocate a Vec2 with any type, and reference it’s members which have the type you want:

val vec = new Vec2[Float](1f, 2f)
println(vec.x) // prints "1.0"

val vec2 = new Vec2[Double](1.5, 1.2)
println(vec2.x) // prints "1.5"

Still, so far, so good.

Let’s continue, We’ll add simple operations to our vector class, like +/-/* and /:

import scala.math.Fractional

class Vec2[T](val x: T, val y: T)(implicit num: Fractional[T]) {
  import num.mkNumericOps

  def +(that: Vec2[T]) = new Vec2(this.x + that.x, this.y + that.y)
  def -(that: Vec2[T]) = new Vec2(this.x - that.y, this.y - that.y)
  def *(that: Vec2[T]) = new Vec2(this.x * that.y, this.y * that.y)
  def /(that: Vec2[T]) = new Vec2(this.x / that.y, this.y / that.y)

  override def toString = s"Vec2($x, $y)"
}

To do something arithmetically with a Generic parameter we need scala’s Numeric. It allows us to add, subtract, multiplicate, divide numbers and much more. We also have to import num.mkNumericOps, since that allows us to use the infix operators on the Generic type T. Else we would always need to write something like num.plus(this.x, that.x)".

Now, we can test that code and it works:

val vec1 = new Vec2(10f, 4f)
val vec2 = new Vec2(5f, 3f)
val result = vec1 + vec2
println(result) // prints "Vec2(15.0, 7.0)"

So now we want to add a method for getting the length of a vector:

def squaredLength = x * x + y * y
def length = math.sqrt(squaredLength)

So here is the problem, the compiler won’t let us do that:

<console>:23: error: type mismatch;
 found   : T
 required: Double
        def length = math.sqrt(squaredLength)
                               ^

The problem is, that math.sqrt takes a Double as argument, it’s impossible to call it with the Generic type parameter T.

What can we do about this? Numeric doesn’t have something like num.sqrt(). But Numeric was implemented in scala, too. It’s not a compiler feature! It’s possible to write your own Numeric - or even cooler - extend your Numeric to include methods you like!

How Numeric works: Write your own

Let’s do this. What do we need for this? First, let’s understand how Numeric works. Let’s write our own simple Numeric. It should only be able to add two numbers…

trait MyNumeric[T] {
  def plus(x: T, y: T): T
}

The Idea of the Numeric interface is to make scala choose the right numeric for the right type. So We create a numeric for Float, Double and Int, and it’ll choose the right Object, and if T is none of those, it’ll cry like a baby.

That can be done with implicit objects in scala. They can be used for a so called type class pattern. If you know Haskell, you should know type classes very well.

trait MyNumeric[T] {
  def plus(x: T, y: T): T
}
object MyNumeric {
  implicit object IntIsMyNumeric extends MyNumeric[Int] {
    def plus(x: Int, y: Int) = x + y
  }
  implicit object FloatIsMyNumeric extends MyNumeric[Float] {
    def plus(x: Float, y: Float) = x + y
  }
  implicit object StringIsMyNumeric extends MyNumeric[String] {
    def plus(x: String, y: String) = s"($x + $y)"
  }
}

So now we’ve defined Classes which help to do adding with Int’s, Float’s and String’s. I added Strings just for fun :)

So let’s define a sum method, which is generic (over Int, Float, and Strings). Also, the Strings don’t add like you may be used to with "abc" + "def" = "abcdef", but it represents a mathematical operation, so "1" + "2" is supposed to be "(1 + 2)" and ("1" + "2") + "3" = "((1 + 2) + 3)" and so on.

def sum[T](elements: T*)(implicit num: MyNumeric[T]) = {
    var acc = elements(0)
    for (i <- 1 until elements.size) acc = num.plus(acc, elements(i))
    acc
}

That code is written in a very, very, imperative style, but that makes it easy to understand. And since we’re missing some necessary methods to make it purely functional, we have no choice.

We can test that code and it works magically for our types that we have type classes for:

println(sum(1f, 2f, 3f, 4.1f)) // prints "10.1"
println(sum(1, 2, 3, 4, 5)) // prints "15"
println(sum("1", "2", "3", "4", "abc")) // prints "((((1 + 2) + 3) + 4) + abc)"

But what should the compiler do when he searches for the type class of type Char, for example? We haven’t defined that one, so it can’t work, right?

println(sum('c', 'd'))

<console>:16: error: could not find implicit value for parameter num: MyNumeric[Char]
              println(sum('c', 'd'))
                         ^

Yep, right :)

Extending Numeric

So now we go back to our first issue: We couldn’t call sqrt generically. But technically it’s possible! You’ve probably done it often. In java it’s called casting, in scala it’s not exactly casting, but kind of:

println(math.sqrt(5.toDouble).toInt) // prints "2"
println(math.sqrt(5f.toDouble).toFloat) // prints "2.236068"
println(math.sqrt(5.0)) // prints "2.23606797749979"

So yeah, it’s definitely possible. We can do the same in our type-classes like that:

trait MyNumeric[T] {
  def plus(x: T, y: T): T
  def sqrt(x: T): T
}
object MyNumeric {
  implicit object IntIsMyNumeric extends MyNumeric[Int] {
    def plus(x: Int, y: Int) = x + y
    def sqrt(x: Int) = math.sqrt(x).toInt
  }
  implicit object FloatIsMyNumeric extends MyNumeric[Float] {
    def plus(x: Float, y: Float) = x + y
    def sqrt(x: Float) = math.sqrt(x).toFloat
  }
  implicit object StringIsMyNumeric extends MyNumeric[String] {
    def plus(x: String, y: String) = s"($x + $y)"
    def sqrt(x: String) = s"sqrt($x)"
  }
}

And sqrt now works:

def sqrtMagic[T](x: T)(implicit num: MyNumeric[T]) = num.sqrt(x)
sqrtMagic(10f) // prints "3.1622777"
sqrtMagic("a") // prints "sqrt(a)"

Works perfectly! But we haven’t got +, -, * and stuff… That’s still a problem… :/ We also don’t want to implement them ourself, but simply extend the standard scala’s numerics now. This can be done simply with extending the classes. The idea is to have a subclass of Numeric[T], which requests having the sqrt() method. And the typeclasses of our own Numeric then extend the original Numeric’s typeclasses and extend them by the sqrt() method. Also, we move everything from Numeric to Fractional, since we only want to allow calling .sqrt() on Fractional numerics, that is: Float, Double, BigDecimal and similar. We’ll only define the implicit classes for Float and Double now.

Let’s do this:

import scala.math.Fractional
import scala.math.Numeric._

trait SqrtFractional[T] extends Fractional[T] {
  def sqrt(x: T): T
}
object SqrtFractional {
  trait FloatIsSqrtFractional extends SqrtFractional[Float] {
    def sqrt(x: Float) = math.sqrt(x).toFloat
  }
  implicit object FloatIsSqrtFractional 
    extends FloatIsSqrtFractional 
    with FloatIsFractional 
    with Ordering.FloatOrdering

  trait DoubleIsSqrtFractional extends SqrtFractional[Double] {
    def sqrt(x: Double) = math.sqrt(x)
  }
  implicit object DoubleIsSqrtFractional 
    extends DoubleIsSqrtFractional 
    with DoubleIsFractional 
    with Ordering.DoubleOrdering
}

Yep. That’s it.

We can now use that code to complete our Vec2 class:

class Vec2[T](val x: T, val y: T)(implicit num: SqrtFractional[T]) {
  import num.mkNumericOps

  def +(that: Vec2[T]) = new Vec2(this.x + that.x, this.y + that.y)
  def -(that: Vec2[T]) = new Vec2(this.x - that.y, this.y - that.y)
  def *(that: Vec2[T]) = new Vec2(this.x * that.y, this.y * that.y)
  def /(that: Vec2[T]) = new Vec2(this.x / that.y, this.y / that.y)
  
  def squaredLength = x * x + y * y
  def length = num.sqrt(squaredLength)

  override def toString = s"Vec2($x, $y)"
}

println(new Vec2(10f, 10f).length) // prints "14.142136"

I hope you liked this tutorial :)

Some Extra stuff

If you ever wondered how to implement the infix operators, you’ll keep wondering, since I won’t explain it :)

But if you want to implement your own infix or suffix stuff, you can do it by extending Numeric#Ops. I’ll post an example here on how the SqrtNumeric class would look like to be able to do something like 36f.sqrt:

import scala.math.Fractional
import scala.math.Numeric._

trait SqrtFractional[T] extends Fractional[T] {
  def sqrt(x: T): T

  class SqrtNumericOps(left: T) extends Ops(left) {
    def sqrt = SqrtFractional.this.sqrt(left)
  }
  implicit def mkSqrtNumericOps(left: T) = new SqrtNumericOps(left)
}
object SqrtFractional {
  trait FloatIsSqrtFractional extends SqrtFractional[Float] {
    def sqrt(x: Float) = math.sqrt(x).toFloat
  }
  implicit object FloatIsSqrtFractional 
    extends FloatIsSqrtFractional 
    with FloatIsFractional 
    with Ordering.FloatOrdering

  trait DoubleIsSqrtFractional extends SqrtFractional[Double] {
    def sqrt(x: Double) = math.sqrt(x)
  }
  implicit object DoubleIsSqrtFractional 
    extends DoubleIsSqrtFractional 
    with DoubleIsFractional 
    with Ordering.DoubleOrdering
}

def lolwut[T](n: T)(implicit num: SqrtFractional[T]) {
  import num.mkSqrtNumericOps
  println(n.sqrt)
}
lolwut(36f) // prints "6.0"

Self-advertisement

Just so you don’t have to create it all yourself, I’ve implemented a MathFractional which allows dividing and supports all mathematical operations from scala.math

Also, I’ve already implemented the Vec2, (and Vec3 and Vec4)…

Tagged: scalaprogramming

20th May 2013

Post with 1 note

The Power of the Power of Two

Ever wanted to know, why POT (power of two) numbers appear so often in games like Minecraft? The world is (now) 256 blocks high (2^8), the chunks are 16x16x256 blocks (16 = 2^4) and similar stuff? (The item’s stack size has nothing to do with this, though…)

It’s because of the nature of our CPUs. As you probably already know, our CPU always counts using bits. That means for representing a number from 0 to 255 it uses 8 bits where there are 256 combinations of on/off bits. It’s also important to note, that POT numbers are only a single ‘on’ bit in the binary representation of the number. I won’t cover bits and how the CPU is calculating stuff this time.

I expect you to know every detail about bit operations in the following ‘cheat-sheet’. There I’ll cover how to optimize your code for power-of-two numbers.

Given a number x, which is guaranteed to be a POT number, and given logX being the logarithm with base 2 of it, you can apply following optimizations:

n * x = n << logX This is only a bitshift. It’s faster.

n / x = n >> logX Again. It’s only a bitshift.

n % x = n & (logX-1) Another only-bitwise operation here.

Another interesting thing you can do with optimizing is, when you have guaranteed to have two numbers, which don’t conflict each other (bitwise), that means, their bits don’t intersect, then you can also apply this optimization: n1 + n2 = n1 | n2

The above optimizations helped me create a datastructure, which maps 2D positions to a 1D array. It’s also cache optimized. But that’s another topic, which I’ll probably cover in another blogpost.

EDIT: Yes. Thanks, HeroesGraveDev for noticing the mistake :)

Tagged: programming

3rd March 2013

Question with 1 note

egyptianlion asked: hey im really impressed by your new RPG style game. did you use any API's for the collision detection? it looks really up to par

It’s LibGDX’s port of Box2D :)

Box2D itself is pretty awesome. It allows almost any kind of physical simulation in 2D. LibGDX didn’t port it directly into java (like JBox2D did), but actually built a JNI bridge between the native C++ port and the Java Wrapper. So that is probably the reason why it works so fast.

Tagged: RuinsOfRevenge