Calculating an Object Graph's Size on the JVM

Here’s a little something I learned today. Recently, I had the task of adding an in memory cache for an exchange rate web service to the project I’m working on. I’ve used Guava’s CacheBuilder and set some random values for its maximum size and expiry periods. And the I got wondering, what would be the amount of memory this cache will need when full?

I had a faint idea, from Twitter, that a tool called jol (Java Object Layout) might be exactly what I needed, but I wasn’t exactly sure. I investigated and, sure enough, it is a very good tool for finding not only the memory size of an object graph, but also how objects are laid out in memory on different JVMs. This later feature is useful when optimizing for CPU caches, but I’ve got no experience with this yet.

Back to the subject of this blog post — finding the total amount of memory for an object graph — things are actually quite simple.

Add Dependency

First, you want to add jol as a dependency in your favourite build system. I’m using sbt here.

libraryDependencies += "org.openjdk.jol" % "jol-core" % "1.0-SNAPSHOT" % "compile"

As you may have noticed, I’ve declared this dependency as compile time only. We need it during interactive development, but not (yet) at runtime.

Start Exploring

Next, fire up sbt console and try these commands:

import org.openjdk.jol.info.GraphLayout

println(GraphLayout.parseInstance("USD").toFootprint)
println(GraphLayout.parseInstance("USD").toPrintable)
println(GraphLayout.parseInstance("USD" -> "EUR").totalSize)

Here’s the output I got when inspecting a simple tuple value.

scala> println(GraphLayout.parseInstance("USD" -> "EUR").toFootprint)
scala.Tuple2 instance footprint:
 COUNT   AVG   SUM DESCRIPTION
     2    24    48 [C
     2    24    48 java.lang.String
     1    24    24 scala.Tuple2
     5         120 (total)

In the first column we have an instance count per class: two instances of type [C or Array[Char], two instance of type String and one instance of type Tuple2.

The third column shows how much memory all the instance of a particular type occupy. The char arrays and the strings occupy 48 bytes each. The tuple takes 24 bytes. They all add up to a total memory size of 120 bytes.

The average column says what amount of memory is consumed, on average, by each instance. Why on average though? I don’t have an answer to this yet, but I presume is becuse of byte alignment rules.

Another question might be why does a single String instance occupy 24 bytes? This is where another utility, called ClassLayout comes in handy:

scala> println(ClassLayout.parseClass(classOf[String]).toPrintable)
java.lang.String object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                    VALUE
      0    12        (object header)                N/A
     12     4 char[] String.value                   N/A
     16     4    int String.hash                    N/A
     20     4    int String.hash32                  N/A
Instance size: 24 bytes (estimated, the sample instance is not available)
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

The output says precisely how the object fields will be lay out in the computer memory and how much space they take up.

The first item, the object header, contains class type information. It starts at offset 0 and takes up 12 bytes.

The second item is the first object field. In this case we have an array of chars, which is used to store the actual characters that make up the string. It starts at offset 12 and occupies 4 bytes. Similar for the subsequent two fields.

If you’d like to know more, the project’s source tree contains a directory of samples demonstrating some of its features. It’s a good place to learn more about jol.

References

• jol — http://openjdk.java.net/projects/code-tools/jol/
• Java Object Layout: A Tale Of Confusion
• http://bboniao.com/openjdk/2014-06/java-object-layoutjol.html

Tweet List all posts, go to homepage or subscribe to the RSS feed

Run a single specs2 example from sbt

Every now and then I need to run an single failing specs2 test from the sbt command line. Because it happens so seldom, though, I keep on forgetting how to do it. Google isn’t very helpful either because I have to remember the specs2 terminology, i.e., specification vs example, when searching.

In this blog post I’ll work with the following test:

package com.example.quux

import org.specs2.mutable._

// This class represents a **specification**.
class ExampleSpec extends Specification {
  "this is a group of example" should {
    "this is example one" in {
      true must be(true)
    }

    "this is example two" in {
      true must be(true)
    }
  }
}

Running a Single Specification

If you’re interested in running all the examples in the ExampleSpec specification, the following sbt command will do.

sbt> testOnly com.example.quux.ExampleSpec

Or, using a wildcard for the package name, which is what I personally prefer.

sbt> testOnly *ExampleSpec

Running a Single Example

If, on the other hand, you’d like to run just the example named this is example two, you have to make use of the -ex specs2 flag. Please note, this argument only works with the specs2 testing framework. ScalaTest supports a different set of arguments.

sbt> testOnly -- -ex "this is example two"

This works, but the test reporter will show even the names of the groups that haven’t been run, which makes it hard to figure out where’s the actual failed test. For this reason, the command I’m actually using is akin to this one:

sbt> testOnly *ExampleSpec -- -ex "this is example two"

NB: you have to wrap the example name in double quotes. Single quotes won’t do it.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Contravariant Functors — An Intuition

Today I came across a blog post listing different types of functors (expressed using Scala), and once again I found a mention of contravariant functors. I heard about them in the past, saw their signature, but… no epiphany.

In this post I’d like to gain an intution for what a contravariant functor is. I’ll leave it for another post to understand the other scary one, the exponential functor (shouldn’t be much harder I presume, seems to be composed of two other functors — one covariant, the other contravariant).

Here’s the signature given for contravariant functor in the above blog post:

trait Contravariant[F[_]] {
  def contramap[A, B](f: B => A): F[A] => F[B]
}

It’s pretty mind bending (for me) to understand how that f function can possibly get a handle over a value of type B when B can’t be found in the argument list, only in the return type (as opposed to A). What’s going on then?

A Concrete Example

After a brief search on the internet I found out that a good example of a contravariant functor can actually be seen in the Scala standard library. Ordering.by is a contramap incarnation, specialized for instances of Ordering.

def by[T, S](f: T => S)(implicit ord: Ordering[S]): Ordering[T]

The signature looks a bit different that the one used by Tony Morris, but they’re the same conceptually (the former is just more general). What it says is that if you know how to compare elements of type S and you have a function relating elements of type T to elements of type S, then you know how to compare elements of type T.

There are two conceptual mappings here. At a higher-level you want to map Ordering[S] to Ordering[T], but in order to achieve that an opposite mapping is required — from T to S — hence “contra”.

Generalizing we get that contramap is a function which says that if you give it some abstraction over a concept A, i.e., F[A], and a function that maps from a different concept B to the concept A, then it is able to give you back an abstraction over B, i.e., F[B]. Pretty abstract maybe, but bear with me.

Intuition

Here’s a simple real world example inspired by this thread.

Everybody knows how to compare numbers, right? 2 is smaller than 3, 3 is greater than 2. Also, everybody knows what money are. It’s a concept we’ve been using for ages now, and it’s pretty trivial to draw a correspondence between money and numbers. We’d map a one dollar bill (100 cents) to the number 100 for example.

Because we know these two things: 1. how to compare numbers; 2. how to map from money to numbers, we can actually compare money. Obvious, right? Well, calling contramap using those two facts as arguments will provide you the knowledge of how to compare money. That’s exactly the knowledge that a contravariant functor encodes, but in a more general way, not only for numbers, money and comparisons.

As I said, the final goal is to actually map F[A] => F[B], but in order to achieve that we need a function that maps B => A, i.e. the opposite (contra) direction. It’s basic abstraction. You build new abstraction out of old ones by specifying relationships between concepts.

Translating to Scala

Let’s put the above example in Scala code. First, let’s represent Money:

case class Money(amount: Int)

Scala already knows how to compare Ints and based on that knowledge we want to specify how Money should be compared, i.e., derive Ordering[Money] from Ordering[Int]. To achieve that, we need a way to specify which sub-component of Money is our desired Int, which is trivial in this example:

val contramapFn: Money => Int = (money) => money.amount

Having defined that, and given that an implicit instance for Ordering[Int] is already in scope, all we need now is to call the contramap function defined on the Ordering object, namely, the by method. The resulted Ordering[Money] is marked as being implicit because we want the compiler to use it when we use the comparison method <.

implicit val moneyOrd: Ordering[Money] = Ordering.by(contramapFn)

Now we can easily compare Money instances (we still need an implicit conversion from Ordering to Ordered in scope, hence the first import):

scala> import scala.math.Ordered._
import scala.math.Ordered._

scala> Money(13) < Money(20)
res0: Boolean = true

scala> Money(23) < Money(20)
res1: Boolean = false

Implementing by

How is Ordering.by implemented though? One possible implementation looks like this (the real one is a bit more complicated due to optimizations):

def by[T, S](f: T => S)(implicit ord: Ordering[S]): Ordering[T] =
  new Ordering[T] {
    def compare(x:T, y:T) = ord.compare(f(x), f(y))
  }

As you can see, it creates an Ordering instance whose compare method simply delegates to the compare method of the known Ordering[S], but not before transforming the x and y parameters by passing them through f.

This simple implementation also gives an idea of how f is able to receive an argument of type T. It creates a new “function” that will receive Ts and inside that “function” will we have access to these Ts to pass to f. When you need a value of a specific type and you don’t have it, what do you do? You return a function that asks for one. In this particular case we don’t have a proper function, but an object (an instance of Ordering), which is nothing more than a collection of functions, so the reasoning holds.

Conclusion

There are a few more concrete implementation of contravariant functors in the pages I’ve linked to in the resources section below, but the principle remains the same — you build new abstractions out of old ones by providing a mapping function from the new concept being abstracted to the old one that has already been abstracted.

Resources

• Functors and things using Scala
• I love profunctors. They’re so easy.
• Contravariant functors package on Hackage

Tweet List all posts, go to homepage or subscribe to the RSS feed

Dependencies and Modules In Scala

I’ve watched two presentations on how traits make for a “really, really, really” awesome module system in Scala, while:

Dependency Injection is like a poor man’s module system that isn’t typechecked.

I’d like to know what was meant by Dependency Injection there, because in my world DI is just as typechecked. I understand Scala is the new shit, and the ability to bake enormous cakes is tantalizing, but seriously… let’s stop the hand waving. Describing something as being “really, really, really intersting”, “profound”, or whatever won’t prove anything.

Why is the cake pattern better than the “classical” constructor-based injection? How isn’t a simple interface/trait better than this contraption using nested traits, abstract type aliases, and long lists of traits being mixed in. Or… ok, let me rephrase it. When is the cake pattern better than “classical” constructor-based injection? I have yet to see a convincing answer. On the other hand, I can tell you when the cake pattern is categorically weaker than normal constructors.

But maybe people are not aware of constructor based injection… I can’t blame them though, given that Spring has tried very hard to hide this behind their bloated XML files. One thing that might help in accepting this type of DI is to think of it as a partial application over a collection of related functions. I’m sure you’ve heard this one before, right?

Here’s what I mean by “classical”, constructor-based, injection. We’ve got a Cache trait and two concrete implementations, one based on Mongo and one based on Redis.

trait Cache[K, V] {
  def get(k: K): Option[V]
  def set(k: K, v: V): Cache[K, V]
}

class MongoCache[K, V]() extends Cache[K, V] {
  override def get(k: K) = ???
  override def set(k: K, v: V) = ???
}

class RedisCache[K, V]() extends Cache[K, V] {
  override def get(k: K) = ???
  override def set(k: K, v: V) = ???
}

We’ve also got two abstract repositories for students and teachers.

trait StudentRepository {
  def all: Seq[Student]
  def get(id: String): Option[Student]
}

trait TeacherRepository {
  def all: Seq[Teacher]
  def get(id: String): Option[Teacher]
}

There are two implementations of them that support caching, which can be inferred by observing the constructor arguments.

/**
 * A PostgreSQL backed implementation that supports caching. Notice how
 * the cache dependency is passed through the constructor.
 */
class PostgresStudentRepository(cache: Cache[String, String]) extends StudentRepository {
  override def all = ???
  override get get(id: String) = ???
}

/**
 * Same thing as with PostgresStudentRepository.
 */
class PostgresTeacherRepository(cache: Cache[String, String]) extends TeacherRepository {
  override def all = ???
  override get get(id: String) = ???
}

Now that we have some components, let’s build the graph of objects/modules and let the whole system run.

class Main {
  def main(args: Array[String]): Unit = {
    val mongoCache = new MongoCache[String, String]
    val redisCache = new RedisCache[String, String]
    val studentRepository = new PostgresStudentRepository(mongoCache)
    val teacherRepository = new PostgresTeacherRepository(redisCache)

    // Both repositories can now be passed to some other components
    // via constructor injection.
    val system = new System(studentRepository, teacherRepository)
    system.start()
  }
}

Try to do the same thing using the cake pattern. You’ll quickly discover that you won’t be able to provide two different implementations for the Cache module. And that’s because in the end, when you wire together all those modules you mix together all trait members into the same “namespace” (I use it with the literal meaning here, a space for names, not with the meaning of “package”).

trait CacheModule {
  type Cache[K, V] <: CacheLike[K, V]

  def Cache[K, V]: Cache[K, V]

  trait CacheLike[K, V] {
    def get(k: K): V
    def set(k: K, v: V): Cache[K, V]
  }
}

trait MongoModule extends CacheModule {
  override def Cache[K, V] = new Cache[K, V]

  class Cache[K, V] extends CacheLike[K, V] {
    override def get(k: K): V = ???
    override def set(k: K, v: V): Cache[K, V] = ???
  }
}

trait RedisModule extends CacheModule {
  override def Cache[K, V] = new Cache[K, V]

  class Cache[K, V] extends CacheLike[K, V] {
    override def get(k: K): V = ???
    override def set(k: K, v: V): Cache[K, V] = ???
  }
}

trait StudentRepositoryModule {
  type StudentRepository <: StudentRepositoryLike

  def StudentRepository: StudentRepository

  trait StudentRepositoryLike {
    def all: Seq[Student]
    def get(id: String): Option[Student]
  }
}

trait TeacherRepositoryModule {
  type TeacherRepository <: TeacherRepositoryLike

  def TeacherRepository: TeacherRepository

  trait TeacherRepositoryLike {
    def all: Seq[Teacher]
    def get(id: String): Option[Teacher]
  }
}

trait PostgresStudentRepositoryModule extends StudentRepositoryModule {
  self: CacheModule =>

  override def StudentRepository = new StudentRepository

  class StudentRepository extends StudentRepositoryLike {
    override def all: Seq[Student] = ???
    override def get(id: String): Option[Student] = ???
  }
}

trait PostgresTeacherRepositoryModule extends TeacherRepositoryModule {
  // This module needs a CacheModule. Just as in the non-cake case, when
  // the TeacherRepository's constructor required a Cache instance, in
  // this case we declare our dependency on caching using a self-type.
  self: CacheModule =>

  override def TeacherRepository = new TeacherRepository

  class TeacherRepository extends TeacherRepositoryLike {
    override def all: Seq[Teacher] = ???
    override def get(id: String): Option[Teacher] = ???
  }
}

This is where it gets interesting. Notice how we can’t provide a RedisCacheModule.

class Main {
  def main(args: Array[String]): Unit = {
    val app = new System with PostgresStudentRepositoryModule
                         with PostgresTeacherRepositoryModule
                         with MongoCacheModule
                      // with RedisCacheModule is impossible...
  }
}

I agree the cake pattern looks cool, but I haven’t seen solid arguments for adopting it. It seems it’s cooler just because it uses quite a few JVM-novel language features, like traits, trait composition at call site, and self-types.

Both of these approaches are just as typesafe. Also, in my opinion, the former approach is easier to comprehend because it’s an old pattern, but that’s not quite a good argument, as time will easily solve this issue. However, as you’ve noticed, the cake pattern is imposing a serious limitation on how many different implementations you can provide for a single trait.

Another point is that both objects created from traits, as well as objects created from classes are objects, i.e. first-class values. You can still use classes and constructor-based DI if you like this idea of first-class modules. A class would be just a factory for modules.

There is however a particular case enabled by the cake pattern, which looks impossible to achieve using normal classes, and that is abstract interface composition.

I’m not sure how clearly I can describe this, but… in the above example, you can imagine that the implementation of PostgresStudentRepository.get will first verify the cache and just when there’s no value in the cache it will actually execute a database query. This piece of caching logic can be abstracted away, but notice that it depends on two traits: Cache and StudentRepository. What can we use in Scala to declare these dependencies? Self-types, of course:

/**
 * This trait provides the caching boilerplate, but leaves undefined
 * the mechanism that provides a fresh, non-cached, Student. Also, we
 * don't specify anything about the implementation of Cache. These are
 * the two interfaces: StudentRepository.slowGet and Cache.get that
 * we're composing within this trait.
 */
trait CachingStudentRepository extends StudentRepository {
  self: Cache =>

  override def get(id: String): Option[Student] = {
    self.get(id).map(makeStudent(_)).orElse(slowGet(id))
  }

  def slowGet(id: String): Option[Student]
}

The only way I can see this implemented without using the cake pattern is by replacing the self-type with an abstract cache member:

trait CachingStudentRepository extends StudentRepository {
  def cache: Cache

  override def get(id: String): Option[Student] = {
    cache.get(id).map(makeStudent(_)).orElse(slowGet(id))
  }

  def slowGet(id: String): Option[Student]
}

This will still cause namespacing issues if a CachingTeacherRepository will declare an abstract cache member as well. It’s actually the same problem that the cake pattern suffers from. You won’t be able to provide different implementations for the same interface.

A simple solution is to prepend, or append, the trait name to the member: cachingStudentRepositoryCache. Not so nice, eh? It would be nice if Scala would allow us to rename members inherited from traits, like say… PHP 5.4 does, a language everybody loves to hate:

<?php

trait A {
  public function smallTalk() {
    echo 'a';
  }
  public function bigTalk() {
    echo 'A';
  }
}

trait B {
  public function smallTalk() {
    echo 'b';
  }
  public function bigTalk() {
    echo 'B';
  }
}

class Talker {
  use A, B {
    B::smallTalk insteadof A;
    A::bigTalk insteadof B;
  }
}

class Aliased_Talker {
  use A, B {
    B::smallTalk insteadof A;
    A::bigTalk insteadof B;
    B::bigTalk as talk;
  }
}

The Cake Pattern. When?

Okay, that was my little rant concerning the cake pattern. I believe people give it too much credit for no added benefit over what we were already able to do in Java. Any counter-argument will be greatly appreciated. I haven’t written this blog post to prove someone is wrong. I actually wrote it so that I know what’s the best tool for the job. And when it comes to DI in Scala, I see no clear arguments that the cake pattern is best for me.

Oh… I’m lying. There’s actually a situation when there’s no other choice. That’s when you have no control over your own constructors, e.g., the Servlet API. Or when you don’t even have constructors, e.g. Play! Framework controller objects (enforcing objects in Play! is again something I don’t see a good reason for, but that’s another blog post I guess).

So, I’m curious to see a clear example of when I’ll really have to use the cake pattern, because constructor-based injection won’t handle the issue.

Unexplored Grounds

There are two things I haven’t yet explored in this post:

1. Whether any of these two DI patterns helps or hinders an immutable style
2. Left-most currying vs. right-most currying DI, where left-most currying is represented by constructor-based injection, and right-most currying is represented by the reader monad. This is also a subject for a future blog post.

Resources

• Videos
  • Cake Pattern: The Bakery from the Black Lagoon
  • Living in a Post-Functional World
  • Dead-Simple Dependency Injection is Scala
• Articles
  • Real-World Scala: Dependency Injection (DI)
  • Cake pattern in depth
  • Dependency Injection vs. Cake pattern
  • Guide: Writing Testable Code
  • Where Have All the Singletons Gone?

Tweet List all posts, go to homepage or subscribe to the RSS feed

Explore JVM Libraries in a Quick sbt Session

Dear younger me, here’s a quick way to try out a new third-party library in the Scala REPL without having to create a new sbt project or edit the sbt build file.

In this particular example I’m just playing around with dispatch, trying to see whether it sends the correct query parameters to httpbin.org.

Create Temp Directory

This is an optional step, but I do it because sbt creates two sub-directories: project and target, and I don’t like to pollute whatever directory I’m in (usually $HOME or Desktop).

λ Desktop master: mkdir -p sbt-project
λ Desktop master: cd sbt-project/
λ sbt-project master: sbt
[info] Set current project to default-a63394 (in build file:/Users/igstan/Desktop/sbt-project/)

Set Scala Version

> set scalaVersion := "2.10.0"
[info] Defining *:scala-version
[info] The new value will be used by no settings or tasks.
[info] Reapplying settings...
[info] Set current project to default-a63394 (in build file:/Users/igstan/Desktop/sbt-project/)

Add Library as Dependency

> set libraryDependencies += "net.databinder.dispatch" %% "dispatch-core" % "0.10.0"
[info] Defining *:library-dependencies
[info] The new value will be used by *:all-dependencies
[info] Reapplying settings...
[info] Set current project to default-a63394 (in build file:/Users/igstan/Desktop/sbt-project/)

Enter the REPL

> console
[info] Updating {file:/Users/igstan/Desktop/sbt-project/}default-a63394...
[info] Resolving org.slf4j#slf4j-api;1.6.2 ...
[info] Done updating.
[info] Starting scala interpreter...
[info]
Welcome to Scala version 2.10.0 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_21).
Type in expressions to have them evaluated.
Type :help for more information.

Import Dependencies

scala> import dispatch._, Defaults._
import dispatch._
import Defaults._

Create a Request Builder

scala> val u = url("http://httpbin.org/get")
SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.
u: com.ning.http.client.RequestBuilder = com.ning.http.client.RequestBuilder@2cce6b12

Add Some Query Params

scala> u <<? Seq("a" -> "foo", "b" -> "bar")
res0: com.ning.http.client.RequestBuilder = com.ning.http.client.RequestBuilder@2cce6b12

Execute Request

scala> val r = Http(u.OK(as.String))
r: dispatch.Future[String] = scala.concurrent.impl.Promise$DefaultPromise@7495a73e

scala> r.onComplete(println(_))

scala> Success({
  "args": {
    "a": "foo",
    "b": "bar"
  },
  "headers": {
    "Connection": "close",
    "Accept": "*/*",
    "Host": "httpbin.org",
    "User-Agent": "Dispatch/0.10.0"
  },
  "url": "http://httpbin.org/get?q=foo"
})

scala>

Improvements

I’ve added a bash alias that saves me from creating a scratch directory every time I’d like to play with some library:

take () {
  mkdir -p $1 &&
  cd $1
}

alias sbt-playground="take '$HOME/.sbt-playground' && sbt"

Also, because the command to add a library dependency is quite long, I’ve created an sbt alias in $HOME/.sbtrc:

alias dep=set libraryDependencies +=

Now, all I have to type in the sbt console is this command:

> dep "net.databinder.dispatch" %% "dispatch-core" % "0.10.0"

Tweet List all posts, go to homepage or subscribe to the RSS feed

Scala's flatMap is not Haskell's >>=

The behaviour of flatMap in Scala:

scala> List(1, 2, 3, 4) flatMap (Some(_))
res0: List[Int] = List(1, 2, 3, 4)

The behaviour of >>= in Haskell:

> [1, 2, 3, 4] >>= Just

<interactive>:4:18:
    Couldn't match expected type `[b0]' with actual type `Maybe a0'
    Expected type: a0 -> [b0]
      Actual type: a0 -> Maybe a0
    In the second argument of `(>>=)', namely `Just'
    In the expression: [1, 2, 3, 4] >>= Just

Tweet List all posts, go to homepage or subscribe to the RSS feed

Commonly Used List Processing Functions in FP

A list of commonly used functions for processing collections in FP languages or when adopting an FP style. Grouped by language in alphabetical order. The listing order for the functions is the same for every language. Some functions, though, are missing in some languages or there are alternative ways to accomplish the same goal.

• Clojure
• Erlang
• Haskell
• JavaScript
• Scala

Clojure

• first
• rest
• map
• filter or its dual remove
• every? or its dual not-every?
• some or its dual not-any?
• zipmap
• zip-with. There’s no such function in Clojure, but the same thing can be achieved by passing at least two collections to map.
• take
• take-while
• drop
• drop-while
• reduce

Please note that some of the functions above will probably be superseded by the new reducers library.

Erlang

• hd/1
• tl/1
• lists:map/2
• lists:filter/2
• lists:all/2
• lists:any/2
• lists:zip2/2 and lists:zip3/3
• lists:takewhile/2
• lists:dropwhile/2
• lists:foldl/3
• lists:foldr/3

Haskell

• head
• tail
• map
• filter
• all or the closely related and
• any or the closely related or
• zip or any of the zip3 up to zip7 in the Data.List module
• zipWith or any of the zipWith3 up to zipWith7 in the Data.List module
• take
• drop
• takeWhile
• dropWhile
• foldl
• foldr

JavaScript (using underscore.js)

• first
• rest
• map
• filter and its dual reject
• all
• any
• zip
• reduce / inject / foldl
• reduceRight / foldr

Scala

• head
• tail
• map
• filter and its dual filterNot
• forall
• exists
• zip
• zipWith. There’s no such method in Scala, instead use the zipped method which is only available for Tuple2 and Tuple3
• take
• drop
• takeWhile
• dropWhile
• foldLeft
• reduceLeft
• foldRight

Tweet List all posts, go to homepage or subscribe to the RSS feed

How Inheritance Violates Encapsulation

I’ve recently finished reading Effective Java, and in this book Joshua Bloch gives a simple demonstration on how inheritance can break encapsulation. That composition should be favoured over inheritance is a thing I hear quite a lot and I’m actually trying to follow the rule myself, but I never had a thorough understanding as to why inheritance would be a bad thing besides the fact that certain languages don’t allow multiple inheritance (a problem I hit in the past).

Joshua Bloch actually makes a good example of a situation where inheritance forces the developer of the subclass to know about the internals of the superclass, which means the encapsulation in the superclass is broken. I’ve put his example in a small JUnit test case:

public class BrokenEncapsulationTest {

  @Test
  public void testAddCount() {
    InstrumentedHashSet<String> set = new InstrumentedHashSet<String>();

    set.addAll(Arrays.asList("Snap", "Crackle", "Pop"));

    assertEquals(3, set.addCount);
  }

  public static class InstrumentedHashSet<E> extends HashSet<E> {

    public int addCount = 0;

    @Override
    public boolean add(E a) {
      addCount += 1;
      return super.add(a);
    };

    @Override
    public boolean addAll(Collection<? extends E> c) {
      addCount += c.size();
      return super.addAll(c);
    }
  }
}

The above test fails with this message:

java.lang.AssertionError: expected:<3> but was:<6>

It is entirely non-obvious why addCount would return 6 instead of 3. After all, we only added three elements, right? The answer is that HashSet.addAll() uses internally the add method. This means, that inside InstrumentedHashSet we add 3 to addCount inside our overridden version of addAll, and then we add 1 three more times to addCount for each call to add that super.addAll executes.

This is such a simple and effective demonstration for a case where you really have to dig up the source of the parent class in order to find out the cause for the unexpected behaviour.

Inheritance Overflow

Here’s another weird case I came across two times in my developer life. Once a couple of years ago while developing a PHP application, and once a few weeks ago in a Java application. If you try to run the example below you’ll get a StackOverflowError.

public class InheritanceOverflow {

  public static class Parent {

    public void foo() {
      bar();
    }

    public void bar() {}
  }

  public static class Child extends Parent {
    @Override
    public void bar() {
      // I have no idea that foo in Parent is actually calling bar, that calls
      // this method, which will call foo againg, and so on. Infinite recursion.
      foo();
    }
  }

  public static void main(String[] args) {
    new Child().bar();
  }
}

Unexpected, isn’t it? As I said, I’m not making up these examples just to find weak spots about inheritance. I actually had to debug stuff like this.

Solutions

So, what’s to be done about this kind of problems? The best approach would be to use composition. This basically translates to using the Decorator pattern. For example, InstrumentedHashSet can be rewritten like this:

public static class InstrumentedHashSet<E> implements Set<E> {

  private final Set<E> wrappedSet;

  public int addCount = 0;

  public InstrumentedHashSet(Set<E> wrappedSet) {
    this.wrappedSet = wrappedSet;
  }

  @Override
  public boolean add(E e) {
    addCount += 1;
    return wrappedSet.add(e);
  }

  @Override
  public boolean addAll(Collection<? extends E> c) {
    addCount += c.size();
    return wrappedSet.addAll(c);
  }

  // The other methods required by the Set interface, which would just
  // delegate to the wrappedSet member. Skipped for brevity.
}

If, for whatever reason, you decide you want your class to be inherited, then make sure overridable methods don’t call other overridable methods. Have them use either private helper methods, or make those helper methods final if you want to allow more relaxed visibility rules.

public class InheritanceOverflowRevisited {

  public static class Parent {

    public void foo() {
      barHelper();
    }

    public void bar() {
      barHelper();
    }
    
    private void barHelper() {
      // do bar stuff
    }
  }

  public static class Child extends Parent {
    @Override
    public void bar() {
      foo(); // no more StackOverflowError
    }
  }

  public static void main(String[] args) {
    new Child().bar();
  }
}

References

• Effective Java (2nd edition), Item 16: Favor composition over inheritance

Tweet List all posts, go to homepage or subscribe to the RSS feed

Composing Java Interfaces Using Generics

A few months ago I noticed an interesting aspect of the Java programming language. Everyone knows that a certain class can implement multiple interfaces in Java, but how would you specify in client code that you expect an instance of an object that implements multiple interfaces, without using the concrete type?

Say for example that you create a QueueSet class which implements both Queue<T> and Set<T>.

public class QueueSet<T> implements Queue<T>, Set<T> {
  // methods required by Queue and Set
}

Now, some client code needs such a QueueSet<T>. What are its options? It could require an instance of QueueSet<T> in the method signature…

public <T> void foo(QueueSet<T> queueSet) {}

It works, but if foo is itself part of a library, it would want to be as generic as possible, and as such depend on an interface rather than a concrete class. The obvious answer for this problem is to make QueueSet an interface, and rename the initial concrete class to something else.

public interface QueueSet<T> extends Queue<T>, Set<T> {}

public class PeculiarQueueSet<T> implements QueueSet<T> {
  // methods required by QueueSet, i.e. Queue and Set
}

The problem here is that any other class that implements Queue<T> and Set<T>, but doesn’t implement QueueSet<T>, won’t satisfy the type signature of foo. It’s a shame that we had to create a wrapper interface just for this. It would have been better to be able to specify inside foo, that the queueSet parameter is expected to be an instance of an object that implements both Queue<T> and Set<T>, without any additional wrapper interface. Something like this:

public <T> void foo(Queue<T> and Set<T> queueSet) {}

The idea came to me from Haskell’s typeclasses, which allow a notation similar to the one above when you want to enforce a particular type variable to be an instance of multiple typeclasses.

foo :: (Ord a, Show a) -> [a] -> [a]
foo list = -- implementation

So, my first thought was that Java does not permit this level of abstraction, but I was wrong. A couple of days ago, while playing with some generics, I rediscovered that Java’s generics allow multiple bounded type parameters. So, the generic version of foo that satisfies our needs would be this:

public <T, QS extends Queue<T> & Set<T>> void foo(QS queueSet) {}

My wishful thinking about Queue<T> and Set<T> transformed into QS extends Queue<T> & Set<T>. You can rename QS to whatever you want. I chose a two letter type variable as a means to convey that it uses multiple type bounds, i.e., both Queue<T> and Set<T>.

Regarding the syntax. Well, yes, I agree it is unnecessarily verbose, but at least it’s possible. Although, on a second thought, the real problem is that the type declarations are interleaved with the method name and the formal parameter names. Haskell code seems more legible, to me at least, just because it separates the function signature from its implementation.

References

• Gilad Bracha’s Generics in the Java Programming Language
• Bounded Type Parameters

Tweet List all posts, go to homepage or subscribe to the RSS feed

On Life and Evolution

So, I know this guy on Twitter (@missingfaktor, you should follow him), who frequently tweets or re-tweets about religion, atheism, or evolution, and just like in Inception a little idea got inside my head.

I don’t really see the world in black and white, and this is true for the evolutionism and creationism stuff too, although I tend to believe more in evolution than in creation (I don’t see human beings popping out of nowhere on Earth). However… who created evolution? Or, did the evolution, more precisely, the rules for evolution were created or evolved or something? And who planted the initial seed? Is it really necessary that there is some entity out there to create the initial seed? Do we need time?

Now, all these questions above got mixed this morning with some other idea. We have computers, and we can actually model and create worlds inside them. So, what would be the minimum rules necessary to create that would allow evolution and would actually create some intelligent life-form inside our program given a considerable amount of time? Would it even be possible? Conway did his research with his Game of Life, and some people (forgot where I read this) wondered how many game generations are needed for a given initial generation in order to reach some sort of life form.

So, these are the initial two questions.

• is it even possible to devise a world with built-in evolution mechanism which given enough time will produce self-conscious intelligence?
• how hard would that be? I mean, how complex could the initial rules be?

I’ll assume the answers are that it is possible and not actually very hard, otherwise I’d stop here. So, let’s imagine we’re in front of our artificial, evolving, world were we try to model evolution and see where it ends up.

The big problem now I believe is to spot intelligence. I assume the program we devised is just let to run and we don’t actually attempt to intervene in it. Will we be able to spot intelligence? It doesn’t have to look like what we see among us. It doesn’t have to generate multiple, self-conscious, life forms. One would suffice.

Let’s assume though that we’re able to recognize it. Let’s say we’ve built some visual interface to this world that would allow some sort of representation of it (although I don’t think it should necessarily represent something true to what it is actually). Here’s the thing now. We would be some lousy gods because we depend on time, and our tools depend on that, and the world we devised probably has some form of time in it. The time is generated by the CPU. I assume this world runs entirely in the memory of the computer (no persistence for the moment), and that the amount of memory is infinite. However, the CPU speed does not necessarily have limits, but it is variable. Imagine those creatures inside that world, they would be so constrained to the world they live in that, no matter the CPU speed, for them time will always have the same speed, or… it would be just time. Because, without time they would not exist, and every thought of them would be a certain amount of CPU instructions. So, it doesn’t matter how many instructions per unit of time the CPU executes. All it matters is that they get executed. Do they have any chance to get a feel for this? Is there any chance for them to plan some experiments that will show them that time actually has speed and that it varies? I don’t see one, unless we design the initial world that way.

It would be quite funny to watch those little guys banging their heads against the wall trying to understand their world. With some of them believing in creationism, some others in evolutionism.

Here’s another question. Now that you know your computer holds a world of intelligent life forms, would you unplug the power cable? How would you feel yourself after deliberately obliterating an entire universe?

To me, that seems to be the problem with evolution. Is it necessary that someone lay out the initial rules of evolution, or not?

We, as intelligent entities, cannot really imagine a universe without time. We can imagine ourselves existing in a world without dimensions (see Shadows), but not a world without time. So, my opinion is that it either has to be some sort of superior entity that lives outside time, or maybe time is just another dimension of the world we live in and it’s just our perception about it that makes us unable to imagine a world without time, but the world can exist just fine all by itself, for ever, since ever (so to say).

How would a world without verbs look like? Because verbs denote time. You wouldn’t “exist” because that’s a verb and it implies time.

What does life actually mean? Would we perceive what we created as life if we know they actually follow some basic rules of evolution? How can order be created out of chaos? Have we actually created life until now and didn’t actually realize it?

Another interesting part is that the universe we created it’s not material. The substrate they would exist on would be material, but that’s our material, our electrons (quarks, strings, whatever), not theirs. Maybe they would perceive their world as material, but that depends entirely on the initial world we create.

The irony is that… oh, well, the chaos that exists in our world would create their world too. So, abstraction will leak, but they probably won’t be able to sense it. Or, if maybe they’ll be able to obtain some buffer overflows, and then some weird things could happen in their world, and as such maybe they will ultimately be able to create some model of their world, i.e. our computer.

How would this experiment makes us able to understand the world we live in? After all, the world we would create would be based on the world we live in. Maybe we can sense some stuff by means of this experiment. Here’s a little analogy for this.

I find it pretty hard to imagine a world with four dimensions, but I can attempt to understand this if I imagine how two 1-dimensional worlds intersect themselves to form a point. Then, two 2-dimensional worlds intersect themselves and form a 1-dimensional world, a line. Finally, two 3-dimensional worlds intersect themselves to form a 2-dimensional world, a plane. However, note that for each intersection you actually need a superior dimension. To intersect two 2-dimensional worlds, that forms a 1-dimensional world, you need a 3-dimensional world, otherwise the intersection of two planes would be the same plane.

Maybe, trying to create this world inside our world will actually help us understand the world we live in. Maybe…

Tweet List all posts, go to homepage or subscribe to the RSS feed

Clojure Impressions

Following some unintentional peer pressure on Twitter, with people acclaiming the recently published book “Joy of Clojure”, and some others showing their solutions to the Clojure problems on 4clojure.com, I finally decided to try this language a bit. I’ve refrained myself from doing so for almost a year and a half. The main reason was that it didn’t seem to be as elegant as Scheme. There’s something about the look of Clojure programs that reminds me of dirt. I can’t really put my finger on it, but that’s what I feel sometimes. A second reason was the JVM. Just as with many other people, for some time I thought JVM and Java are the same thing. Now I don’t, but I still dislike the time it takes JVM to start up.

The way I approached Clojure was by trying to solve the problems on 4clojure.com. I didn’t read any tutorial beforehand though. I’m familiar with Scheme, and lately I’ve been writing some Haskell code too. So, both the basics of the syntax and the paradigm (functional programming with laziness) were there. However, throughout the whole exercise I made good use of the reference on clojuredocs.org.

Below I’d like to capture my current impression about this language, while it’s still fresh in my mind.

Syntax

I like the syntax. Well, not all of it, but the basic syntax because it’s Lisp. And, it may seem strange, but sometimes I kind of wish Clojure made use of more (round) parentheses. I don’t particularly like the square brackets of let or the :else keyword of cond, but I got used to the square brackets of defn. The syntax for calling into Java is also kind of weird.

Strings and Characters

This was my first WTF with Clojure. Mainly because now I expect every respectable programming language to treat strings the way Haskell does, i.e. as a list of characters. I quickly found out that strings in Clojure are… Java strings. Well, to be honest, I don’t fucking care what language they used to implement Clojure. And the fact that they let this thing leak through didn’t look good to me. This is actually a bigger problem with Clojure. It leaks implementation details in multiple places. If you want to manipulate strings or characters, you have to resort to the Java API for strings and characters. If you’ve got an exception in your program, well… you have to wade through the guts of the Clojure’s internals stack trace in order to find the line number you’re interested in. And that’s when that number exists, because sometimes it’s just 0.

I know that strings are actually transformed to sequences in most of the core functions, but you still have to jump some hoops. Here’s what I mean. Let’s upper-case a string, shall we? The obvious answer would be:

user=> (.toUpperCase "foo")
"FOO"

And it could be fine, but… ah, why do I have to call a Java method?

Now, let’s pretend I don’t know there’s a .toUpperCase method on String, but I know there’s one such static method on the Character class.

user=> (map Character/toUpperCase "foo")
java.lang.Exception: Unable to find static field: toUpperCase in class ...

Oh, Java methods aren’t really first class functions. We’re talking about Java so we shouldn’t be surprised. Next try.

user=> (map #(Character/toUpperCase %) "foo")
(\F \O \O)

Huh? Where’s my string? Next try.

user=> (str (map #(Character/toUpperCase %) "foo"))
"clojure.lang.LazySeq@18505"

Lazy? Why? Next try.

user=> (apply str (map #(Character/toUpperCase %) "foo"))
"FOO"

That’s better, but too much for something that could just as well be:

user=> (map upper-case "foo")
"FOO"

So, in short, I don’t like that strings and characters are not citizens of Clojure, but rather visitors from the land of Java.

Documentation

Every function in Clojure’s core is documented. It uses the same convention that Python uses. A multiline string at the beginning of the function represents the documentation. Not unexpectedly, there’s a doc function available inside the REPL that takes a function value (not function name) and returns its docs. Pretty much like Python’s help function. However there’s more in Clojure. You have access to every core function’s source code by calling the source function. This is hugely useful because, as we all know, docs aren’t perfect, so it helps to sometimes take a look at the source of the function and try to understand what that docstring is actually trying to say. There’s also find-doc and javadoc. I really like this part of Clojure.

Standard Library

There’s a plethora of functions in clojure.core. Most of them being there to support the ubiquitous sequences of Clojure. If you’re used to Haskell, it may look like there’s something in Haskell and not in Clojure. It may be true, but you should first ask around because it might be there under a different name. For example I found myself wanting a zipWith function:

Prelude> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]

I couldn’t find it in the beginning. Later on I discovered that Clojure’s map function actually maps over multiple collections. So there it was, my zipWith function in disguise.

user=> (map + [1 2 3] [4 5 6])
(5 7 9)

Actually, it’s more than zipWith, because Clojure is dynamic and takes an infinite number of collections to iterate over, while zipWith takes just two. You’d need zipWith3 for three collections, zipWith4 for four collections, and so on up to seven. Also, the equivalent for Haskell’s zip is zipmap.

Polymorphism of conj

I don’t think I have yet started to love this. conj seems too polymorphic for my taste. It may either prepend an element if the collection is a list, or append it, if the collection is a vector. Not to mention it also works on maps and sets.

I did’t like conj especially when I had to work with functions generating lazy sequences. Whenever I saw conj I had to read carefully to see what kind of collection that conj acts on. Most of the time they’re lists, but sometimes it’s a vector and you end up with a reversed list without knowing why.

conj is useful, but I think it should be used with care.

Laziness

It was a nice pleasure to see Clojure having support for laziness. There are plenty of algorithms on sequences that are easier to implement when you have lazy sequences.

In Clojure, laziness is something you opt in when you’re writing your function by constructing sequences with lazy-seq. However, because there are so many built-in functions that return lazy sequences most of the time you won’t feel a difference compared to Haskell.

Pattern Matching

Another nice surprise. I didn’t use it too much because I’m not used to pattern matching in a Lisp, but it’s powerful and can make the code both more concise and readable.

Tail-Call Recursion

Just as with laziness, you have to explicitly opt-in for tail-call recursion. It’s the same thing as in any other language that supports tail-calls, you have to make sure that the recursive call is the last thing that your function does. However, in Clojure, you have to use the recur special form instead of the function name. That signals the Clojure compiler that you want tail-call recursion.

(defn gcd [a b]
  "Calculates greatest common divisor using Euclid's algorithm."
  (if (zero? b) a
      ;; uses `recur` instead of `gcd`
      (recur b (mod a b))))

Java Interoperability

This one is what made Clojure popular. And it appeals to me too, even if I’m not a Java person. In the past I had to use some Java libraries, like Apache POI for processing Excel files, and back then I scripted them using JavaScript (with Mozilla Rhino). Nowadays, if I were to solve the same problem, I’d probably choose Clojure. Once you hide the Java ugliness behind a sane, Lisp-like, API, things are much better.

But this is something that I also fear. It may happen that some of the monstrosity of Java libraries will percolate through all these layers of abstraction until it hits Clojure. I don’t know, maybe it won’t happen, but I still think it would be a pity.

seq? vs sequential?

This is something I haven’t yet understand despite my attempts. I have googled the topic and even looked inside the Clojure source code. The two are still foggy subjects in my mind. Mainly because of those leaks I was talking above. For example the docs for sequential? read:

Returns true if coll implements Sequential

Ok, and what exactly that means? I took a look at the Sequential interface, and to my surprise it was used as a marker interface, i.e. it specifies no methods. It is used in several places with instanceof checks. Until now, it seems that sequential? will tell you if the order of the elements in a collection matters. For example it returns true for both lists and vector, but not for maps and sets.

The docs for seq? read:

Return true if x implements ISeq

Please, not Java interfaces again… Fortunately this time ISeq is not a marker interface, but I shouldn’t have to read the internals of Clojure to figure out what this function does. Anyway, this function answers whether the passed argument is a data structure that supports three main operations on it:

• first
• rest
• cons

Gotchas

Just one for the moment. contains? works on keys not on values, but beware, sets are like a collection of keys, so:

user=> (contains?  [1 2 3] 3)
false
user=> (contains? #{1 2 3} 3)
true

The End

These are my first impressions with Clojure. I had a great time solving those problems on 4clojure.com and I think you’ll enjoy them too. Thus far I like Clojure.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Understanding Monads With JavaScript

Update

Nice people have translated this article into Portuguese and Russian.

For the past weeks I’ve been working hard studying monads. I’m still learning Haskell, and to be honest I thought I knew what monads are all about, but when I wanted to write a little Haskell library, just to sharpen up my skills, I realized that while I understood the way monadic bind (>>=) and return work, I had no understanding of where that state comes from. So, most likely I had no understanding at all. As a result of this I thought I rediscover monads myself using JavaScript. The plan was basically the same as that used when I derived the Y Combinator: start from the initial problem (dealing with explicit immutable state in this case), and work my way up to the solution by applying simple code transformations.

Also, I chose JavaScript because it forces you to write some code that Haskell readily hides for you thanks to its terse syntax or different semantics (lambda expressions, operators, and built-in function currying). Lastly, I learn best by comparison, which is why I tried it in CoffeeScript and Scheme too. Here are the GitHub gists for the latter two:

• CoffeeScript: https://gist.github.com/936519
• Scheme: https://gist.github.com/936695

Constraints

In this article I’ll limit my problem to the state monad. Understanding the state monad is good enough to have an idea what monads are all about. So here are the solution constraints.

• no mutable state
  Haskell makes use of the state monad because it does not allow mutable state.
• no explicit state
  When you don’t have mutable state, you have to thread residual state around. Typing and reading all those intermediate states is not pleasant. Monads try to hide all this plumbing. You’ll see what I mean in a moment.
• no code duplication
  This goes hand in hand with the previous point, but I still put it here because in my experience removal of code duplication is a powerful tool to explore new grounds.

Too Long; Won’t Read

This article is a pretty dense one, so I thought I should add some additional material to it. That’s why I recorded a little video with all the steps that are described below. It’s sort of a tl;dr version, and it should help visualize the transitions more easily, but most likely the video won’t make too much sense if you won’t read the whole article.

I advise you watch it directly on Vimeo, where it’s available in HD.

Derivation Vehicle

I’ll use a stack as my derivation vehicle because it’s an easy to understand data structure, and its usual implementation is done using mutable state. First, here’s how you’d normally use a stack in JavaScript.

var stack = [];

stack.push(4);
stack.push(5);
stack.pop(); // 5
stack.pop(); // 4

JavaScript array objects have the usual methods one would expect from a stack, push and pop. What I don’t like about it is that it mutates state. Well, I don’t it like for the sake of this article, at least.

Each step I’ll describe is a working step. Just open your browser’s console and reload this page. You should see several console groups with the string 5 : 4 logged inside. However, in the body of the article I’ll only present those parts that differ from the previous steps.

A Stack With Explicit Handling of State

The obvious solution to avoid mutable state is to construct a new state container every time we need mutation. Here’s how it can look like in JavaScript (note that concat and slice are two Array methods that do not mutate the object they’re called on, instead they create new Array objects):

var push = function (element, stack) {
  var newStack = [element].concat(stack);

  return newStack;
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var stack1 = push(4, stack0);
var stack2 = push(5, stack1);
var result0 = pop(stack2);        // {value: 5, stack: [4]}
var result1 = pop(result0.stack); // {value: 4, stack: []}

As you can see, both push and pop return a residual stack, the resulted state. pop additionally returns the popped value. Each subsequent stack operation uses the previous stack, but this may not be easily observable because of differences in representation of return values. However, code duplication can be emphasized by normalizing return values. We’ll have push return a dummy undefined value.

var push = function (element, stack) {
  var value = undefined;
  var newStack = [element].concat(stack);

  return { value: value, stack: newStack };
};

var pop = function (stack) {
  var value = stack[0];
  var newStack = stack.slice(1);

  return { value: value, stack: newStack };
};

var stack0 = [];

var result0 = push(4, stack0);
var result1 = push(5, result0.stack);
var result2 = pop(result1.stack); // {value: 5, stack: [4]}
var result3 = pop(result2.stack); // {value: 4, stack: []}

That’s the kind of duplication I was talking earlier. Duplication that also means explicit handling of state.

Transforming to Continuation-Passing Style

Now, I’ll replace those intermediate result variables with functions and parameters. I want this because I find it easier to abstract over functions and parameters than over simple variables. To do this, I’ll create a small helper function, called bind, which does nothing more than just apply a continuation callback to the stack operation result. In other works, it binds a continuation to a stack operation.

var bind = function (value, continuation) {
  return continuation(value);
};

var stack0 = [];

var finalResult = bind(push(4, stack0), function (result0) {
  return bind(push(5, result0.stack), function (result1) {
    return bind(pop(result1.stack), function (result2) {
      return bind(pop(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

The return value of the whole expression, stored in finalResult, has the same type as the return value of a single push or pop operation. We want to have consistent interfaces.

Currying push and pop

Next, we want to be able to detach the stack arguments from push and pop. We want this because the intention is to have bind thread them behind the scenes.

For this we’ll apply another lambda calculus trick called function currying. An alternative name could be function application procrastination.

Now, instead of calling push(4, stack0), we’ll call push(4)(stack0). In Haskell we wouldn’t even need this step, because its functions are curried by default.

var push = function (element) {
  return function (stack) {
    var value = undefined;
    var newStack = [element].concat(stack);

    return { value: value, stack: newStack };
  };
};

var pop = function () {
  return function (stack) {
    var value = stack[0];
    var newStack = stack.slice(1);

    return { value: value, stack: newStack };
  };
};

var stack0 = [];

var finalResult = bind(push(4)(stack0), function (result0) {
  return bind(push(5)(result0.stack), function (result1) {
    return bind(pop()(result1.stack), function (result2) {
      return bind(pop()(result2.stack), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      });
    });
  });
});

Preparing bind to Handle Intermediate Stacks

As I said in the previous section, I’d like bind to handle the passing of the explicit stack arguments. First, let’s have bind accept a stack as its last parameter, but in a curried way, i.e. bind now returns a function which takes a stack. Also, push and pop are now partially applied, i.e. we longer pass them the stack manually. bind will handle this instead.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    return continuation(stackOperation(stack));
  };
};

var stack0 = [];

var finalResult = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;
        return { value: value, stack: result3.stack };
      })(result2.stack);
    })(result1.stack);
  })(result0.stack);
})(stack0);

Removing Trailing Stacks

We’re now able to hide the intermediary stacks by modifying bind to inspect the return value of a stackOperation, extract the stack and use it as an argument to the return value of the continuation callback, which must be a function that receives a stack. That’s why we also have to wrap the final result (return result2.value + " : " + result3.value) inside an anonymous function that will receive a stack.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    var newStack = result.stack;
    return continuation(result)(newStack);
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {
        var value = result2.value + " : " + result3.value;

        // We need this anonymous function because we changed the protocol
        // of the continuation. Now, each continuation must return a
        // function which accepts a stack.
        return function (stack) {
          return { value: value, stack: stack };
        };
      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Hiding the Final Residual Stack

In the previous step, we hid away several intermediate stacks, but exposed a new one in the function that wraps the final result value. We can hide this trace of a stack by writing another helper function that I’ll call result. Additionally, this will also hide the internal representation of the state we’re keeping, i.e. a struct with two fields, value and stack.

var result = function (value) {
  return function (stack) {
    return { value: value, stack: stack };
  };
};

var computation = bind(push(4), function (result0) {
  return bind(push(5), function (result1) {
    return bind(pop(), function (result2) {
      return bind(pop(), function (result3) {

        return result(result2.value + " : " + result3.value);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

This is exactly what the return functions does in Haskell. It wraps the computation result inside a monad. In our case it wraps the result in a closure which accepts a stack. But that’s basically what the state monad is, a function that accepts its state. Another way to view result/return is like a factory function that creates a new stateful context around the value we provide it with.

Keeping State Internal

We don’t want our continuation callbacks to have to traverse or even know about the struct returned by push or pop, which actually represents the internals of the monad. So, we’ll modify bind to pass just the minimum required data to the callback.

var bind = function (stackOperation, continuation) {
  return function (stack) {
    var result = stackOperation(stack);
    return continuation(result.value)(result.stack);
  };
};

var computation = bind(push(4), function () {
  return bind(push(5), function () {
    return bind(pop(), function (result1) {
      return bind(pop(), function (result2) {

        return result(result1 + " : " + result2);

      });
    });
  });
});

var stack0 = [];
var finalResult = computation(stack0);

Evaluating The Stack Computation

Once we’re able to compose stack operations this way, we’ll also want to run these computations and do something with the result. This is generally called evaluation of the monad. In Haskell, the state monad provides three functions for evaluating the state monad: runState, evalState, and execState.

For the purpose of this article though, I’ll replace the “State” suffix with “Stack”.

// Returns both the result and the final state.
var runStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack);
};

// Returns only the computed result.
var evalStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).value;
};

// Returns only the final state.
var execStack = function (stackOperation, initialStack) {
  return stackOperation(initialStack).stack;
};

var stack0 = [];

console.log(runStack(computation, stack0));
// { value="5 : 4", stack=[]}

console.log(evalStack(computation, stack0));
// 5 : 4

console.log(execStack(computation, stack0));
// []

If all we’re interested in is the final computed value, then evalStack is what we need. It will trigger the whole monadic computation, drop the final resulted state and return the computed value. Using this function we can extract a value out of its monadic context.

If you’ve ever heard that you can’t escape a monad, then let me tell that this is true just in a small number of cases, like the IO monad for example. But that’s another story. The point is that you can get out of the state monad.

Done

If you’re still with me, then let me tell you that this is how the state monad could look like in JavaScript. It probably doesn’t look that readable, compared to a similar Haskell version, but it’s the most I can get out of JavaScript today.

A monad is a pretty abstract concept because it specifies little about what you have to write. Mainly, it says that you need to design a function which will take some arguments (the state in the case of the state monad), and two additional functions: result and bind. The former will act as a factory for the function you just designed. The latter will be responsible for exposing just enough details about your monad to the outside world, and also perform some boring stuff like passing state around. Exposing is done by means of a continuation function that will take the value that the monad computes. Everything that is internal to the monad will be kept internal. Just like in object-oriented programming. And it’s even possible to have monadic getters/setters for the those internals.

Just for the record, here’s how the computation function would look like in Haskell.

computation = do push 4
                 push 5
                 a <- pop
                 b <- pop
                 return $ (show a) ++ " : " ++ (show b)

The main reason the Haskell version looks better is because Haskell has built-in syntactic support for monads in the form of the do notation. do notation is just sugar for the following version, which still looks better than the JavaScript one. Haskell, having support for operator definitions and terse lambda expressions allows for a more readable, in my opinion, implementation of monads.

computation = push 4 >>= \_ ->
              push 5 >>= \_ ->
              pop    >>= \a ->
              pop    >>= \b ->
              return $ (show a) ++ " : " ++ (show b)

What I called bind in JavaScript is >>= in Haskell, and what I called result in JavaScript is return in Haskell. Yes, return in Haskell is a function, not a keyword. Other times, return is named unit. Brian Marick called >>= a decider in his videos about monads in Clojure. The patcher was of course return.

Some JavaScript Sugar

It turns out there’s a better way to do monadic computations in JavaScript using a little utility function called sequence. Thanks to JavaScript’s dynamic nature, sequence can take a variable number of arguments that represent the monadic actions it must perform in sequence, save for the final argument which is a callback that contains the computation over the result of the monadic actions. The callback is called with all the non-undefined results of the monadic actions.

var sequence = function (/* monadicActions..., continuation */) {
  var args           = [].slice.call(arguments);
  var monadicActions = args.slice(0, -1);
  var continuation   = args.slice(-1)[0];

  return function (stack) {
    var initialState = { values: [], stack: stack };

    var state = monadicActions.reduce(function (state, action) {
      var result = action(state.stack);
      var values = state.values.concat(result.value);
      var stack  = result.stack;

      return { values: values, stack: stack };
    }, initialState);

    var values = state.values.filter(function (value) {
      return value !== undefined;
    });

    return continuation.apply(this, values)(state.stack);
  };
};

var computation = sequence(
  push(4), // <- programmable commas :)
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var initialStack = [];
var result = computation(initialStack); // "5 : 4"

The authors of Real World Haskell compared monads to a programmable semicolon. In this case, I can say we have programmable commas, because that’s what I used when calling sequence to separate monadic actions.

Monads As Suspended Computations

You’ll often see monads being called computations. In the beginning I didn’t understand why. You might say because they compute stuff, but… nobody says “monads compute something”, they actually say “monads are computations”. I finally understood (or I think I did) what that means after I finished an early draft of this article. All that chaining of monadic actions and values does not actually compute anything until you tell it to. It’s all a big chain of partially applied functions, which represent a suspended computation that will finally be triggered by calling it with the initial state. Again, here’s this snippet.

var computation = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

Does it compute anything when it is evaluated? No. You have to trigger the computation with runStack, evalStack, or execStack.

var initialStack = [];
evalStack(computation, initialStack);

It looks like the push and pop functions act on some global value, whereas they in fact are always awaiting for that value to come. It’s almost like in OOP where this is the context of the computation. In our case though, this is implemented by means of currying and partial application, it also points to a new context in each expression. And, if in OO context is said to be implicit, then by using monads you make it even more implicit (if there even is such a thing).

The advantage of monads (and functional programming in general) is that you get highly composable building blocks. And it’s all because of function currying. Each time two monadic actions are chained, a new function is created which awaits to be run.

var computation1 = sequence(
  push(4),
  push(5),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var computation2 = sequence(
  push(2),
  push(3),
  pop(),
  pop(),

  function (pop1, pop2) {
    return result(pop1 + " : " + pop2);
  }
);

var composed = sequence(
  computation1,
  computation2,

  function (a, b) {
    return result(a + " : " + b);
  }
);

console.log( evalStack(composed, []) ); // "5 : 4 : 3 : 2"

This may seem useless for performing stack operations, but when designing a library of monadic parser combinators for example, this gets very handy. It allows the author of the library to provide just a handful of “primitive” functions on his Parser monad, and then, the user of the library is able to mix and match those primitives as he sees fit, ultimately ending up with an embedded domain specific language (EDSL).

The End

Well, I hope you found this article useful. Writing it definitely helped me having a better understanding of monads.

References

• Books
  • Programming in Haskell
  • Learn You a Haskell For Great Good!
  • Real World Haskell
• Articles and Papers
  • A Schemer’s Introduction to Monads
  • Monadic Parsing in Haskell
  • Monadic Parser Combinators
  • Monads in Python
  • What the hell are Monads?
• Videos
  • The Quick Essence of Functional Programming
  • Monad Tutorial in Clojure, Part 1
  • Monad Tutorial in Clojure, Part 2
  • Monad Tutorial in Clojure, Part 3
  • Monad Tutorial in Clojure, Part 4

Tweet List all posts, go to homepage or subscribe to the RSS feed

How to Associate TextMate With CoffeeScript Files

First, tell OS X to use TextMate.app when you try to open .coffee files. The command below will do just that.

$ defaults write com.apple.LaunchServices LSHandlers -array-add \
"<dict>
    <key>LSHandlerContentTag</key>
    <string>coffee</string>
    <key>LSHandlerContentTagClass</key>
    <string>public.filename-extension</string>
    <key>LSHandlerRoleAll</key>
    <string>com.macromates.textmate</string>
</dict>"

To associate TextMate’s generic document icon with .coffee files first go to /Applications/TextMate.app/Contents and open Info.plist. At the bottom of the file there’s a section that looks like this:

{   CFBundleTypeName = "Source";        /* generic source code types */
    CFBundleTypeExtensions = (
        coffee, g, vss, d, e, gri, inf, mel, build, re,
        textmate, fxscript, lgt
    );
    CFBundleTypeIconFile = TMDocument;
    CFBundleTypeRole = Editor;
}

Put coffee inside the CFBundleTypeExtensions listing (as you can see above). Now rebuild the LaunchServices database:

$ ln -s /System/Library/Frameworks/CoreServices.framework/Versions/Current/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister /usr/local/bin/lsregister
$ lsregister -kill -r -domain local -domain system -domain user

That should be all.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Deriving the Y Combinator in 7 Easy Steps

The Y Combinator is a method of implementing recursion in a programming language that does not support it natively (actually, it’s used more for exercising programming brains). The requirement, though, is that language to support anonymous functions.

I chose JavaScript for deriving the Y Combinator, starting from the definition of a recursive factorial function, using a step-by-step transformation over the initial function.

Update

There’s now a Chinese translation of this article as well as a Clojure port.

Step 1

The initial implementation, using JavaScript’s built-in recursion mechanism.

var fact = function (n) {
    if (n < 2) return 1;
    return n * fact(n - 1);
};

Step 2

What would be the simplest thing to do to obtain basic recursion? We could just define a function which receives itself as an argument and calls that argument with the same argument. That’s an infinite loop of course, and would cause a stack overflow.

(function (f) {
    f(f);
})(function (f) {
    f(f);
});

Let’s use the above pattern for our factorial function. There is however a small difference. The factorial function receives an argument which we don’t know yet, so what we want is to return a function which takes that argument. That function can then be used to compute factorial numbers. Also, this is what makes our implementation to not result into an infinite loop.

var fact = (function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
})(function (f) {
    return function (n) {
        // termination condition
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});

Step 3

At this point we have some ugly duplication in there. Let’s hide it away into a helper function called recur.

var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    return function (n) {
        if (n < 2) return 1;

        // because f returns a function, we have a double function call.
        return n * f(f)(n - 1);
    };
});

Step 4

The problem with the above version is that double function call. We want to eliminate it so that the implementation of this factorial is similar with the recursive version. How can we do that?

We can use a helper function that takes a numeric argument and performs the double call. The trick is though to keep this helper function in the same environment where f is visible, so that g can actually call f.

var recur = function (f) {
    return f(f);
};

var fact = recur(function (f) {
    var g = function (n) {
        return f(f)(n);
    };

    return function (n) {
        if (n < 2) return 1;

        // no more double call, g is a function which takes a numeric arg
        return n * g(n - 1);
    };
});

Step 5

The above works nice, but the definition contains so much clutter code. We can hide it away inside yet another helper function, keeping almost just the definition of factorial.

var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        var g = function (n) {
            return f(f)(n);
        };

        return h(g);
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Step 6

Let’s inline the definition of g inside wrap because we only call it once.

var recur = function (f) {
    return f(f);
};

var wrap = function (h) {
    return recur(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = wrap(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

Step 7

Now, if we also inline the definition of recur function inside wrap we end up with the famous Y Combinator.

var Y = function (h) {
    return (function (f) {
        return f(f);
    })(function (f) {
        return h(function (n) {
            return f(f)(n);
        });
    });
};

var fact = Y(function (g) {
    return function (n) {
        if (n < 2) return 1;
        return n * g(n - 1);
    };
});

The End

I hope you enjoyed it!

Tweet List all posts, go to homepage or subscribe to the RSS feed

How to install Memcached functions for MySQL

Download libmemcached 0.35 (any version greater than this won’t work) and Memcached functions for MySQL (I’ve used version 1.1).

Extract libmemcached and execute the following inside the extracted directory:

./configure
make
sudo make install

Extract the Memcached functions archive and execute the following inside the extracted directory:

./configure
make
sudo make install

Execute the following query inside a MySQL client and copy the returned value:

SHOW VARIABLES LIKE 'plugin_dir';

Copy the compiled Memcached libraries to the MySQL plugins directory:

sudo cp /usr/local/lib/libmemcached_functions_mysql* <VALUE_FROM_ABOVE_QUERY>

Restart the MySQL server, then go to Memcached functions dir and then the “sql” directory. Log into a mysql client in that dir:

$ mysql -uroot
mysql> source ./install_functions.sql

You’re done. Hopefully.

Tweet List all posts, go to homepage or subscribe to the RSS feed

PLAI - Rudimentary Interpreters

I’ve just finished the second section of PLAI, Rudimentary Interpreters.

It revolves around a basic interpreter for arithmetic expressions. The idea was presented from chapter I actually. The difference is that chapter I introduces the syntax for this languages, which is more or less Scheme with curly brackets instead of braces. For example, {+ 1 2} represents the addition operation between the numbers 1 and 2. The second chapter though, deals with the semantics of the language; introduces concepts such as identifiers, scope and functions. All in a progressive manner, building new concepts on top of existing ones.

A little digression. PLAI uses a dialect of Scheme as its languages, and while I like Scheme, this language that they use, called PLAI Scheme, is actually quite ugly to my eyes. The reason is that it’s some sort of typed Scheme, in that it has algebraic data types and means of destructuring such data into its variants. In fact, it looks a lot like Haskell, so what I did was to write all the supporting code in Haskell. I started with PLAI Scheme in chapter one, but chapter two was all Haskell. The little disadvantage is that in Haskell I don’t have a read function that takes valid Scheme code and returns a corresponding Scheme data structure. So I had to write the parser myself, but it was no big deal for two reasons. First of all, the syntax for this arithmetic language is quite simple, and secondly, Haskell has really powerful libraries for parsing. For convenience I’ve used Parsec, as I already have some experience with it, but there lots of other parsing libraries (I’ve heard some of them are even better than Parsec). To end this digression, all the Haskell code I wrote for this chapter is available in my Github repo. I hope I’ll write another blog post with details about its implementation.

Now, back to the book.

The chapter starts by exploring the concept of identifiers and ways of supporting them in a language by means of substitution. These identifiers resemble normal variables that we all know, except for one thing, they can’t be reassigned a new values. So they’re actually constants, not variables. It then goes on describing what happens when there are overlapping identifiers names, whether it’s a good thing and how to implement it correctly. But it’s not a book that gives you the correct solution from the first shot. It makes you write a program with mistakes, then provides some examples that won’t work with the respective program, at which point the whole theory behind the concepts begins. The reason is very simple, the author wants the readers to judge based on a concrete program instead of some abstract concepts.

I won’t go into details about substitution, as it is a pretty complex subject and would provide no information that it’s not in the book. There’s one thing that I want to mention though. One section of chapter three asks whether names are necessary for identifiers. It appears that someone called Nicolaas de Bruijn said they’re not, and instead, he used numbers. This appears to be employed in compiler construction. Maybe I’ll talk in detail about substitution in a future post.

After substitution, the language is enriched with functions. These are quite simple conceptually, as they take a single argument and return a value that is always numeric, but it’s a good start for observing the issues that arise when combining substitution and functions.

After substitution and functions, the author introduces deferred substitution as a means of improving the performance of the interpreter. Instead of passing through the whole program for each identifier that dictates a substitution, the interpreter is now storing these identifiers and their values in a data structure that is queried on a per need basis, i.e., whenever a new scope is found that uses a free identifier.

The last part of this second section of the book deals with first-class functions, i.e., functions that ca be used as any other value in the language. They can be returned from functions, or passed to functions. Also, in the moment functions as first-class values meet deferred substitution, the concept of closure emerges.

In short, that’s what section two of PLAI touches. If you want more details, then start reading the book. I had a lot of fun implementing this little language in Haskell. Although small, it encompasses a lot of advanced programming concepts unavailable in other languages (PHP for example, which is what I do for a living).

Tweet List all posts, go to homepage or subscribe to the RSS feed

PLAI - Chapter I

Yesterday I’ve begun reading Programming Languages: Application and Interpretation (abbreviated PLAI), written by Shriram Krishnamurthi. The book is available for free in PDF format.

The main reason for starting it is because I’ve noticed, about a year ago, that I have a passion for programming languages. I like to learn new programming languages, programming concepts or ways to make such languages more expressive. The final goal would be to implement myself a programming language. This goal, however, is not set for the near future. First of all, I want to work hard in the trenches with multiple languages, and learn as much as I can about languages that have gone away, or maybe that have influenced other ones. In order to invent, I need an inventory.

For the next month or so, I plan to read the above book. It is used as a text book at Brown University, and seemingly in some other universities. The thing that got me about it is the titles of the chapters. I’ve heard about most of those concepts in my short experience with several languages, and maybe even worked with several of them, but I certainly want to know more about them (like ways of implementing them, advantages and disadvantages). Things like laziness, recursion, (immutable) state, continuations, type inference and metaprogramming are guaranteed to give me thrills at this point in my life. They may sound like buzzwords, and they may actually be in this moment of functional programming resurrection, but… as I have little knowledge about them (that means, I can’t yet explain them that well to you, I only have instinctive understanding) it seems normal to attract me so much.

Yesterday I’ve read the first chapter, the Prelude, which is basically an introduction to programming language modelling and some theory about parsers.

The main thing that should be retained from this chapter would be that each programming language (I’d say programming platform though, because of the libraries part) consists of four categories:

• syntax
• behavior associated with syntax: semantics
• libraries
• idioms

Also, as a note for those interested in reading the book themselves. I’m using DrRacket to work through the examples, but the syntax isn’t standard Scheme, so I had to choose the “Pretty Big” language.

Now, I’m going to start reading the next chapter: Rudimentary Interpreters.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Git's environment filter

This is a thing I keep on forgetting although I’ve done it several times. So, I’m writing a blog post hoping it will help me memorize this.

So… how do you rewrite Git’s history, specifically the environment variables. With git filter-branch of course. I frequently need it in order to change the author and committer email addresses (either from personal to work or the other way around).

git filter-branch --env-filter 'export GIT_AUTHOR_EMAIL="email@address.com"' HEAD
git filter-branch --env-filter 'export GIT_COMMITTER_EMAIL="email@address.com"' HEAD

Don’t forget that there are two email addresses, OK? The author’s and committer’s one. Oh, and no spaces around the equal sign.

For a more complicated situation see this answer on serverfault.com.

Tweet List all posts, go to homepage or subscribe to the RSS feed

CSS for Firefox only

So, how do you write CSS code that will be understood only by Firefox?

Same question was asked by someone on stackoverflow.com. My first attempt was to use XBL and Mozilla’s proprietary -moz-binding CSS extension in order to run some JavaScript that will eventually load the intended CSS rules. This solution was inspired by Dean Edwards’ moz-behaviors library and it looks like this:

firefox.html

<!DOCTYPE html>

<html>
<head>
<style type="text/css">
body {
  -moz-binding: url(firefox.xml#load-mozilla-css);
}
</style>
</head>
<body>

  <h1>This should be red in Firefox</h1>

</body>
</html>

firefox.xml

<?xml version="1.0"?>

<bindings xmlns="http://www.mozilla.org/xbl">
    <binding id="load-mozilla-css">
        <implementation>
            <constructor>
            <![CDATA[
            var link = document.createElement("link");
            link.setAttribute("rel", "stylesheet");
            link.setAttribute("type", "text/css");
            link.setAttribute("href", "ff.css");

            document.getElementsByTagName("head")[0]
                    .appendChild(link);
            ]]>
            </constructor>
        </implementation>
    </binding>
</bindings>

firefox.css

h1 {
  color: red;
}

But I felt that there should be a better solution. So I kept digging on MDC. After a couple of clicks I discovered the easiest solution out there for targeting just the Firefox browser in our CSS. It uses a Mozilla specific at-rule, called @-moz-document, and it’s actually intended for user styling.

Here’s the final solution

<!DOCTYPE html>

<html>
<head>
<style type="text/css">
@-moz-document url-prefix() {
  h1 {
    color: red;
  }
}
</style>
</head>
<body>

  <h1>This should be red in FF</h1>

</body>
</html>

A word of caution

We all know how many hours Internet Explorer conditional comments have saved us, but I believe Firefox is a much, much better browser, so please think twice before using the above trick. I’m pretty sure there must be some other way. We don’t want to maintain three different stylesheets, for IE, FF and the rest of the browsers out there.

Tweet List all posts, go to homepage or subscribe to the RSS feed

JScript deviations from ECMAScript 3

Just found a great resource of “things” that are specific to JScript and are not conforming to the ECMAScript 3 standard. Found it on a MSDN blog post from 2007. Enjoy, 87 pages of standards deviations (aka bugs)! Here’s the PDF.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Lambdas and closures in PHP 5.3

Beginning with PHP 5.3 we’ll be able to write anonymous functions and build closures around them - almost the same way we do it in JavaScript. I’d like to introduce these to those of you unaware of these new possibilities in this little blog post.

Defining a lambda

The most simple way to define a lambda can be find below. It’s exactly the same way JavaScript handles it. One has to assing a function to a variable.

<?php

$lambda = function() {
    return 'Hello World';
}; // <- this semicolon is mandatory, unlike JavaScript

echo $lambda();

Creating closures

However, if we want closures, we have to do something more and this because the way scope is designed in PHP where functions don’t get easy access to variables declared outside them. If we want that with a normal (old style) function, we need to import them using the global keyword. Following the same idea, in order to capture a variable into a closure we need to use it:

<?php

$word = ' World';
$lambda = function() use($word) {
    return 'Hello' . $word;
};

echo $lambda();

Mutable closures

Now, our anonymous functions has access to $word. But there’s a gotcha right here. It has read only access to $word. We may try to modify $word inside our function, but those changes won’t be visible outside it. So, here we are, introducing the third thing we need to know about lambdas and closures in PHP. In order to be able to modify a closed variable, we need to import it using the reference operator:

<?php

$word = ' World';
$lambda = function() use(& $word) {
    $result = 'Hello' . $word;
    $word = 'Bye World';
    return $result;
};

echo $lambda();
echo $word;

This time, $word can and will be modified. The variable inside the closure is mutable.

Some history about the future

Although, as of yet, a stable version of PHP 5.3 is not yet out, I should mention that in the process of bringing lambdas and closures to the language there was a particular property of these in that they were able to automagically import the $this pointer if the function was defined inside a class. Not long after, some people thought about writing PHP in the prototypal style of JavaScript, thus there were some discussion that lead the PHP internals to temporarily remove the magic import feature. The main reason was that they had to push the final version out sooner and any new feature would have meant delays. Nevertheless, this feature has been postponed for PHP 6 in which we may get some niceties that should allow us to more easily write code in a monkey patching/prototypal style.

Tweet List all posts, go to homepage or subscribe to the RSS feed

What's new in PHP 5.3

A few weeks ago, PHP 5.3 RC1 has been released and I expect the final version to be out in no more than a month. I’m watching its development since the beginning of 2008 and am really eager to see it in production. The reason for this impatience is that it brings really cool features to the language and I’d like to enumerate some of them in order of my preferences. Initially I also wanted to briefly describe them, but apparently there was to much to talk about in just one post, therefore each feature in the list below will, eventually, point to a more detailed post about the respective feature. So here’s what I like best:

1. Lambdas and closures
2. Callable classes
3. Namespaces
4. The Phar extension
5. Late static binding

There are some other features beside the above mentioned, but these are easier to present so I’ll shortly describe them here:

__callStatic

This is just like the __call we all know except it is designed to work when calling methods in a static context:

<?php

class Test
{
    public static function __callStatic($method, $args)
    {
        return array($method, $args);
    }
}

var_dump(Test::dummyMethod('with dummy argument'));

Nowdoc strings

We all know heredoc strings and the fact they are parsed by the PHP engine for variable interpolation. They’re also good when we have large strings with both single and double quotes, because it saves us from escaping them. Some PHP internals thought though, that the overhead produced for variable interpolation is to big, so they came up with nowdoc strings. This is just like heredoc save for the variable interpolation. Here’s an example:

<?php

$here_doc = <<<STR
Some random string with $variable interpolation...
STR;

$now_doc = <<<'STR'
Some random string without $variable interpolation...
STR;

Ternary shortcut (?:)

This is just like the old ternary operator except that we can leave out the middle statement. The rule is that, if the left-hand side expression evaluates to true, its result is returned, otherwise it will return the result of the result of right-hand side expression:

<?php

var_dump('' ?: 'there was an empty string');
var_dump('I am not empty' ?: 'there was an empty string');

Limited goto

Honestly, I don’t yet understand why this construct is limited because I have never worked with gotos. All I know is that we cannot use goto statements inside loops, this will cause a fatal error to be thrown. Anyway, here’s a basic example taken straight from the manual:

<?php

goto a;
echo 'Foo';

a:
echo 'Bar';

Tweet List all posts, go to homepage or subscribe to the RSS feed

Komodo Edit dark theme

For some time now, I developed some computer related eye fatigue, which kinda sucks and I believe this is due (in part) to the white background of my text editor(s). That’s why I decided to try a dark theme in Komodo Edit. The one shipped with the editor is a bit ugly, I wanted something more like Twilight for Textmate and any Google search for Komodo themes returned pretty much nothing. So, here’s my creation, inspired by all those dark themes out there, especially Twilight.

If you like it, you can grab the theme file from my GitHub repo.

It only supports PHP and JavaScript syntax for the moment. More to come when I’ll have some time. Update: There’s Python and XML support right now.

After you download it, put the “.ksf” file in your Komodo Edit application data folder, more precisely the schemes directory. On my Windows machine this is: C:\Documents and Settings\{user}\Application Data\ActiveState\KomodoEdit\4.3\schemes.

Enjoy!

Tweet List all posts, go to homepage or subscribe to the RSS feed

XHTML no matter what

metropotam.ro changed their layout. Here’s what XHTML obsession means (look after IE conditional comments).

<base href="http://metropotam.ro/" /><!--[if IE]></base><![endif]-->

I simply cannot see the reason for such a useless hack. Too bad they forgot to do the same thing for script tags. But I see the reason for the one below (again, look after IE conditional comments).

<li class="selected">
  <!--[if lte IE 6]><table><tr><td><![endif]-->
  <ul>
  ...
  </ul>
  <!--[if lte IE 6]></td></tr></table></a><![endif]-->
</li>

But then again. What’s this?

<li><a href="..."><strong>Unde iesim</strong><!--[if gte IE 7]><!--></a><!--<![endif]-->

Regardless of the above nitpicking though, I like the new layout.

Tweet List all posts, go to homepage or subscribe to the RSS feed

PHP's ErrorException class

Did you know PHP has an ErrorException class that solves the problem of throwing exceptions from an error handler function?

What problem?

Well, if you throw a normal Exception from such a handler, the file name and line number of the Exception will be set to match the file and line where the Exception was actually thrown and not the place where the error happened. There was no way to extend an Exception class and provide the correct information as Exception’s $file and $line properties are private and there are no setters for them, only getters.

ErrorException solves this problem by overriding the Exception constructor, allowing us to pass up to five arguments. From these five arguments, four have the same meaning as the four arguments passed to the error handler function: $errno, $errstr, $errfile, $errline. By passing along these arguments to the ErrorException constructor we get a more meaningful exception from our error handler.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Change default sort order in Mozilla Thunderbird

I like email and feed messages ordered by date ascending in my Thunderbird, but its default settings are date descending. So I changed it like this:

• Go to: Tools -> Options
• Click “Config Editor…” button
• Search for “sort”
• Change value of mailnews.default_sort_order from 1 to 2

In case you had no idea whether Thunderbird has an “about:config” capability like Firefox, now you know.

Tweet List all posts, go to homepage or subscribe to the RSS feed

MySQL transliteration function

In my latest project at work I had to obtain, by means of an SQL query, transliterated values of certain data fields in our database. And when I say transliteration I don’t mean to transform characters from all over the world into latin characters. What I wanted was to strip diacritics out of latin based characters, like: ș, ț, ă, î or â.

Initially I thought this should be an easy job as database, table and column charset values were all set to utf8_general_ci and I knew MySQL does well at comparing basic latin characters against derived ones. Well, it wasn’t. Although the following query returns true (or 1), there’s no way of querying MySQL for a transliterated value, i.e. from the right hand side string to obtain the left hand side string.

SELECT 'staia' = 'șțăîâ';

So what I did was to define a function in which to take advantage of the comparison feature in order to obtain transliteration. What I came up with might end up on thedailywtf.com but despite its apparent stupidity it does its job very well. So here’s the function:

UPDATE: I’ve incorporated Gabriel Humeniuc’s fixes for preserving the character case, fixed a bug in the MySQL CONCAT function which ignores whitespace characters, and added a special case for the Polish letter “ł”. However the most up-to-date version of this procedure will always be on GitHub: https://github.com/igstan/sql-utils/blob/master/transliterate.sql.

-- Copyright (c) 2012, Ionut Gabriel Stan. All rights reserved.
--
-- Redistribution and use in source and binary forms, with or without modification,
-- are permitted provided that the following conditions are met:
--
-- * Redistributions of source code must retain the above copyright notice,
-- this list of conditions and the following disclaimer.
--
-- * Redistributions in binary form must reproduce the above copyright notice,
-- this list of conditions and the following disclaimer in the documentation
-- and/or other materials provided with the distribution.
--
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-- ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-- WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
-- ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
-- (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-- LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
-- ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
-- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

DELIMITER $

DROP FUNCTION IF EXISTS `transliterate` $
CREATE FUNCTION `transliterate` (original VARCHAR(512)) RETURNS VARCHAR(512)
BEGIN

  DECLARE translit VARCHAR(512) DEFAULT '';
  DECLARE len      INT(3)       DEFAULT 0;
  DECLARE pos      INT(3)       DEFAULT 1;
  DECLARE letter   CHAR(1);
  DECLARE is_lower BIT;

  SET len = CHAR_LENGTH(original);

  WHILE (pos <= len) DO
    SET letter   = SUBSTRING(original, pos, 1);
    SET is_lower = IF(LCASE(letter) COLLATE utf8_bin = letter COLLATE utf8_bin, 1, 0);

    CASE TRUE
      WHEN letter = 'a' THEN SET letter = IF(is_lower, 'a', 'A');
      WHEN letter = 'b' THEN SET letter = IF(is_lower, 'b', 'B');
      WHEN letter = 'c' THEN SET letter = IF(is_lower, 'c', 'C');
      WHEN letter = 'd' THEN SET letter = IF(is_lower, 'd', 'D');
      WHEN letter = 'e' THEN SET letter = IF(is_lower, 'e', 'E');
      WHEN letter = 'f' THEN SET letter = IF(is_lower, 'f', 'F');
      WHEN letter = 'g' THEN SET letter = IF(is_lower, 'g', 'G');
      WHEN letter = 'h' THEN SET letter = IF(is_lower, 'h', 'H');
      WHEN letter = 'i' THEN SET letter = IF(is_lower, 'i', 'I');
      WHEN letter = 'j' THEN SET letter = IF(is_lower, 'j', 'J');
      WHEN letter = 'k' THEN SET letter = IF(is_lower, 'k', 'K');
      WHEN letter = 'l' THEN SET letter = IF(is_lower, 'l', 'L');
      WHEN letter = 'ł' THEN SET letter = IF(is_lower, 'l', 'L');
      WHEN letter = 'm' THEN SET letter = IF(is_lower, 'm', 'M');
      WHEN letter = 'n' THEN SET letter = IF(is_lower, 'n', 'N');
      WHEN letter = 'o' THEN SET letter = IF(is_lower, 'o', 'O');
      WHEN letter = 'p' THEN SET letter = IF(is_lower, 'p', 'P');
      WHEN letter = 'q' THEN SET letter = IF(is_lower, 'q', 'Q');
      WHEN letter = 'r' THEN SET letter = IF(is_lower, 'r', 'R');
      WHEN letter = 's' THEN SET letter = IF(is_lower, 's', 'S');
      WHEN letter = 't' THEN SET letter = IF(is_lower, 't', 'T');
      WHEN letter = 'u' THEN SET letter = IF(is_lower, 'u', 'U');
      WHEN letter = 'v' THEN SET letter = IF(is_lower, 'v', 'V');
      WHEN letter = 'w' THEN SET letter = IF(is_lower, 'w', 'W');
      WHEN letter = 'x' THEN SET letter = IF(is_lower, 'x', 'X');
      WHEN letter = 'y' THEN SET letter = IF(is_lower, 'y', 'Y');
      WHEN letter = 'z' THEN SET letter = IF(is_lower, 'z', 'Z');
      ELSE
        SET letter = letter;
    END CASE;

    -- CONCAT seems to ignore the whitespace character. As a workaround we use
    -- CONCAT_WS with a whitespace separator when the letter is a whitespace.
    SET translit = CONCAT_WS(IF(letter = ' ', ' ', ''), translit, letter);
    SET pos = pos + 1;
  END WHILE;

  RETURN translit;

END $

DELIMITER ;

Tweet List all posts, go to homepage or subscribe to the RSS feed

Ajax file upload with pure JavaScript

Update

The API I wrote about in this article has been removed from recent versions of Firefox. Instead, you can now use a FileReader object to read files on the client, and a FormData object to serialize such file values and POST them using asynchronous requests. These two objects are also available in Chrome and Safari, possible other browsers too. However, I’ll keep the old article here for posterity. Here goes.

Old Article

I don’t know about you, but there’s one little thing I’ve always hated about Ajax. The impossibility of file uploading. I still remember the ugly day when I discovered the terrible truth. There was no chance on earth you could send a file using an XMLHttpRequest, thus workarounds appeared. Google made use of a hidden iframe to imitate such an asynchronous call for their Gmail service, and later on, Flash based uploaders appeared. Things are though going forward.

Firefox 3 introduced a new API, that few people know about, which allows JavaScript to read local files selected by an user from a form file-upload dialog. A copy of Firefox 3 with default settings offers full access to this new programming interface. So we’ll embrace the challenge and write a little JavaScript uploader on top of this new API.

However, if you’re not into reading this long article, just go ahead and look at the complete source code in my GitHub repo.

Goal

In this tutorial we’ll write a little application that is able to read and upload local files to a remote web server using an asynchronous HTTP request. The whole application consists of three parts:

• the client side comprised of JavaScript, HTML and a little CSS
• the server side script, written in PHP
• the communication channel in between them, old good HTTP

We’ll start with the JavaScript side, as I’m sure you’re eager to find about the new file access API, then we’ll review the XMLHttpRequest object as available in Firefox version 3 (it got enhanced with a new method). After the client-side part follows explanations for the server-side script, written in PHP, continued with a little summary over the HTTP protocol concerning data transmission and HTML forms. Finally, we’ll put all these together to build a powerful asynchronous file uploader.

The Firefox file upload API

When Firefox 3 has been launched in June this year, we heard a lot about the improvements it brought to the web development field by further implementing existing standards and technologies like HTML, CSS and JavaScript. One thing I have never seen mentioned was the interface for reading local files, provided the file is chosen by the user through an HTML file input element. For example, a simple Google search for getAsBinary, one of the new methods in the API, will give you few results, even when counting the false positives (such a false positive is related to ColdFusion which has a similar method name, and results comprising information about it are preponderant). That surprises me a lot as, in my opinion, it is a huge step forward in building more powerful web applications. Actually, there is someone that wrote about it in May 2008. Alas the news hasn’t spread. With this new API, each input element (not only file input elements), is given a property called files. This property is our gateway to reading local files. When the type attribute of the input element isn’t file, the value of the files property is null. On the other hand, for input elements whose type attribute is file, the files property is of type FileList and resembles a NodeList object returned by, let’s say, document.getElementsByTagName(). You may access it as if it were an Array and has the following properties and methods:

• length
• item(index)

Each element in the files property is a File element that exposes the following properties and methods:

• fileName
• fileSize
• getAsBinary()
• getAsText(encoding)
• getAsDataURL()

Those two lists above are all there is to know about the API for reading local files. There is nothing more about it. No security restrictions, no special configurations. As I’m sure the files property itself poses no problem in understanding its interface let’s review the contained file objects with a little script. You may want to download Firebug in order to get a thorough understanding of the following exploration. Here’s the code that we’ll use:

<!DOCTYPE html>

<html>
<head>
<title>JavaScript file upload</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<script type="text/javascript">
var upload = function() {
    var photo = document.getElementById("photo");
    return false;
};
</script>
</head>
<body>

<form action="/" method="post" onsubmit="return upload();">
  <fieldset>
    <legend>Upload photo</legend>
    <input type="file" name="photo" id="photo">
    <input type="submit" value="Upload">
  </fieldset>
</form>

</body>
</html>

The fileName property gives us the name of the picked up file, but not the absolute path on the filesystem, just the basename. Modify the above source code above so that the JavaScript part now becomes:

var upload = function() {
    var photo = document.getElementById("photo");
    // the file is the first element in the files property
    var file = photo.files[0];

    console.log("File name: " + file.fileName);
    console.log("File name: " + file.fileSize);

    return false;
};

The getAsBinary() method will read the contents of the file and return them in binary representation. If you select a binary file, an image for example, you should see some weird characters, question marks or even rectangles in the alert, this is how Firefox represents the bytes contained in the file. For a text file it will simply output its text.

The getAsText(encoding) method will return the contents as a string of bytes encoded depending on the encoding parameter. This is by default UTF-8, but the encoding parameter it’s not really optional. You still have to pass some value. An empty string will do it just fine:

var upload = function() {
    var photo = document.getElementById("photo");
    // the file is the first element in the files property
    var file = photo.files[0];

    console.log("File name: " + file.fileName);
    console.log("File size: " + file.fileSize);
    console.log("Binary content: " + file.getAsBinary());
    console.log("Text content: " + file.getAsText(""));
    // or
    // console.log("Text content: " + file.getAsText("utf8"));

    return false;
};

Finally, the getAsDataURL() method, a very interesting and very useful one, will return the file contents in a format ideally suited for, let’s say, the src attribute of an IMG tag. Of course, this will work as we’re in Firefox right now, so let’s add a IMG tag to the HTML source and the appropriate JavaScript code to make this work:

<!DOCTYPE html>

<html>
<head>
<title>JavaScript file upload</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<script type="text/javascript">
var upload = function() {
    var photo = document.getElementById("photo");
    var file = photo.files[0];

    console.log("File name: " + file.fileName);
    console.log("File size: " + file.fileSize);
    console.log("Binary content: " + file.getAsBinary());
    console.log("Text content: " + file.getAsText(""));

    var preview = document.getElementById("preview");
    preview.src = file.getAsDataURL();

    return false;
};
</script>
</head>
<body>

<form action="/" method="post" onsubmit="return upload();">
  <fieldset>
    <legend>Upload photo</legend>
    <input type="file" name="photo" id="photo">
    <input type="submit" value="Upload">
    <hr>
    <img src="" alt="Image preview" id="preview">
  </fieldset>
</form>

</body>
</html>

More information about the new API can be found on their dedicated pages on Mozilla Developer Center:

• https://developer.mozilla.org/en/nsIDOMFileList
• https://developer.mozilla.org/en/nsIDOMFile

Some extra information

You may wonder why an array of files for just one input element. It turns out that RFC 1867, concerning form-based file uploads, specifies that a file input element allows its size attribute to receive a complex value:

The SIZE attribute might be specified using SIZE=width,height, where width is some default for file name width, while height is the expected size showing the list of selected files. For example, this would be useful for forms designers who expect to get several files and who would like to show a multiline file input field in the browser (with a “browse” button beside it, hopefully). It would be useful to show a one line text field when no height is specified (when the forms designer expects one file, only) and to show a multiline text area with scrollbars when the height is greater than 1 (when the forms designer expects multiple files).

None of the browsers I tested this in seems to obey the RFC, nevertheless this should be the reason for which the files property is an array-like object.

The XMLHttpRequest object

Now that we’re able to read local files, we need a way to get this data, over the network, to the server. As we’re aiming for an asynchronous data transmission, an XMLHttpRequest object should do the job just fine. Unfortunately, its send() method isn’t that reliable in sending binary data. For this reason, along with the local file access interface, Firefox 3 brought a new method to the XMLHttpRequest object: sendAsBinary(data). Just as the send() method, the new one takes a single argument, a string, which is converted to a string of single-byte characters by truncation (removing the high-order byte of each character), according to the documentation. The difference, a very important one, is that, as long as send() knows how to process an URL query string, sendAsBinary() expects a totally different format in order to be useful for the server-side end of the application, but we’ll talk about this a little bit later. Let’s just write a little JavaScript skeleton, that we’ll use when assembling together all the pieces of the application:

send: function () {
    var boundary = this.generateBoundary();
    var xhr = new XMLHttpRequest;

    xhr.open("POST", this.form.action, true);
    xhr.onreadystatechange = function() {
        if (xhr.readyState === 4) {
            alert(xhr.responseText);
        }
    };
    var contentType = "multipart/form-data; boundary=" + boundary;
    xhr.setRequestHeader("Content-Type", contentType);

    for (var header in this.headers) {
        xhr.setRequestHeader(header, headers[header]);
    }

    // here's our data variable that we talked about earlier
    var data = this.buildMessage(this.elements, boundary);

    // finally send the request as binary data
    xhr.sendAsBinary(data);
}

As you see, there’s an undefined variable in the above snippet, data, which remains to be defined after we review the mechanism behind files upload over HTTP. For the moment though, I want to talk about the server-side part, as it will guide us in choosing the appropriate strategy for sending binary information.

The server-side script

PHP, as well as several web frameworks made on top of other languages, offers different access points for reading POST data containing uploaded files and POST data containing just simple values. In PHP there are two predefined arrays giving you access to simple POST data, the $_POST array, and another one for accessing files sent to the server, the $_FILES array. It is thus wise to build a client-side script able to send information that PHP would read as from a classical request issued with an HTML form: our uploaded files would appear as elements inside the $_FILES array and additional values as elements inside the $_POST array. Under these circumstances we can write the PHP script to test that our JavaScript client is performing well:

<?php

print_r($_FILES);
print_r($_POST);

That’s all we need on the server. Although simple this we’ll give us valuable feedback about the sent data. The PHP script should list our uploaded files inside the $_FILES array and any additional form data (like text INPUT or SELECT element) inside the $_POST array.

Form data over HTTP theory

As we saw, PHP treats POST-ed files differently than ordinary form field values, so it’s only natural to ask ourselves what’s the “clue” that helps PHP tell apart one from the other.

First of all, every HTML form element out there has an optional attribute called enctype, with a default value of application/x-www-form-urlencoded. This is actually a MIME type value specifying the encoding to be used by the web browser when sending form data. It also guides the web server script in decoding that data as the encoding is sent by the browser to the server in the form of an HTTP header, called Content-Type. For a default enctype value, form data is sent as ASCII characters, URL encoded when necessary. On the other hand, when uploading files, we need to change the enconding to multipart/form-data. Cloning this basic form functionality inside our JavaScript client is what we should do. Let’s modify the earlier script so that it sends such a multipart/form-data header:

var xhr = new XMLHttpRequest;
xhr.onreadystatechange = function() {
    if (xhr.readyState === 4) {
        alert(xhr.responseText);
    }
};
xhr.setRequestHeader("Content-Type", "multipart/form-data");
xhr.sendAsBinary(data);

RFC 1867, regarding form-based file uploads, dictates that an extra parameter is required for the Content-Type header when its value is multipart/form-data. It is called boundary and its presence it’s very logical. The multipart word inside the header means the sent request is formed of multiple parts (obviously), so there must be something to separate those parts. This thing is the boundary parameter which value must be a string of characters that shouldn’t be found inside any of the form values we send, otherwise the request will get garbled. Once again, let’s modify the script to reflect this requirement.

var xhr = new XMLHttpRequest;
xhr.onreadystatechange = function() {
    if (xhr.readyState === 4) {
        alert(xhr.responseText);
    }
};

/*
 * The value of the boundary doesn't matter as long as no other structure in
 * the request contains such a sequence of characters. We chose, nevertheless,
 * a pseudo-random value based on the current timestamp of the browser.
 */
var boundary = "AJAX--------------" + (new Date).getTime();
var contentType = "multipart/form-data; boundary=" + boundary;
xhr.setRequestHeader("Content-Type", contentType);
xhr.sendAsBinary(data);

Next, let’s talk about the structure of the parts comprised in the request. Each of these is like a little request on its own. Each has its own headers structure and body.

The mandatory header, every part must have, is called Content-Disposition and its value should be form-data followed by an additional parameter called name, which represents the name of the form input that holds the data. In case of parts holding uploaded files, a second parameter must also be present, called filename. This is the name of the file as it was on the user’s computer. Not the absolute path, just the basename (for example, monkey.png). Parameter values are enclosed inside double quotes. A little example:

Content-Disposition: form-data; name="photo"; filename="monkey.png"

In the case of files, a second header must is also needed. It is called Content-Type and specifies the MIME type of the file. This may be deduced by reading the file extension or the source of the file. Anyway, a general value of application/octet-stream is perfectly acceptable:

Content-Disposition: form-data; name="photo"; filename="monkey.png"
Content-Type: image/png

As per the standards, every such header should end with two characters, a carriage return and a new line: CR and LF. The last header doubles this sequence (i.e. it ends with CRLFCRLF).

Following the headers is the body which consists of the form field value. I’ll illustrate with a simple text file upload, although it could be any type of file. The text inside the file is “my random notes about web programming”:

Content-Disposition: form-data; name="notes"; filename="my_notes.txt"
Content-Type: text/plain

my random notes about web programming

Finally I’ll give you a final example with both the HTML markup of the form as well as a fictional request from that form:

<form action="upload.php" method="post" enctype="multipart/form-data">
  <fieldset>
    <legend>Upload photo</legend>
    <label for="image_name">Image name:</label>
    <input type="text" name="image_name" id="image_name">
    <select name="image_type">
      <option>Family</option>
      <option>Work</option>
      <option>Vacation</option>
    </select>
    <input type="file" name="photo" id="photo">
    <input type="submit" value="Upload">
  </fieldset>
</form>

The issued request could be:

Content-Type: multipart/form-data; boundary=RANDOM_STRING_BOUNDARY
--RANDOM_STRING_BOUNDARY
Content-Disposition: form-data; name="image_name"

Monkey
--RANDOM_STRING_BOUNDARY
Content-Disposition: form-data; name="image_type"

Vacation
--RANDOM_STRING_BOUNDARY
Content-Disposition: form-data; name="photo"; filename="monkey.png"
Content-Type: image/png

[ here would be the png file in binary form ]
--RANDOM_STRING_BOUNDARY--

In case you didn’t noticed, the boundary, when used in between the parts is prepended with two hyphens and the last one appended with also two hyphens. Don’t forget about this, it’s an ugly source of bugs.

Encapsulating the JavaScript logic

At this point we know all the parts to successfully build a pure JavaScript file uploader, which we’re going to implement as an object. Here’s the basic structure of the constructor and its prototype:

/**
 * @param DOMNode form
 */
var Uploader = function(form) {
    this.form = form;
};

Uploader.prototype = {
    /**
     * @param Object HTTP headers to send to the server, the key is the
     * header name, the value is the header value
     */
    headers : {},

    /**
     * @return Array of DOMNode elements
     */
    get elements() {},

    /**
     * @return String A random string
     */
    generateBoundary: function() {},

    /**
     * Constructs the message as discussed in the section about form
     * data transmission over HTTP
     *
     * @param Array elements
     * @param String boundary
     * @return String
     */
    buildMessage : function(elements, boundary) {},

    /**
     * @return null
     */
    send : function() {}
};

In case you didn’t understand the elements() construct, this is called a getter and is supported by the latest versions of Firefox, Opera, Safari and Chrome. A setter form is also provided. You can find more about these on Mozilla Developer Center.

We should fill the above methods, so let’s start with the send() method because we already wrote much of it in a previous sections of the tutorial:

/**
 * @return null
 */
send : function() {
    var boundary = this.generateBoundary();
    var xhr = new XMLHttpRequest;

    xhr.open("POST", this.form.action, true);
    xhr.onreadystatechange = function() {
        if (xhr.readyState === 4) {
            alert(xhr.responseText);
        }
    };
    var contentType = "multipart/form-data; boundary=" + boundary;
    xhr.setRequestHeader("Content-Type", contentType);

    for (var header in this.headers) {
        xhr.setRequestHeader(header, headers[header]);
    }

    // here's our data variable that we talked about earlier
    var data = this.buildMessage(this.elements, boundary);

    // finally send the request as binary data
    xhr.sendAsBinary(data);
}

In addition to what we had earlier we have now introduced an iteration that allows us to send additional headers without modifying the prototype itself. We have also defined the variable we talked about earlier, data, which holds the source of the HTTP request. It holds the value returned by a call to a method whose only purpose is to build an HTTP compliant request for file uploads. Here’s its source:

/**
 * @param Array elements
 * @param String boundary
 * @return String
 */
buildMessage : function(elements, boundary) {
    var CRLF = "\r\n";
    var parts = [];

    elements.forEach(function(element, index, all) {
        var part = "";
        var type = "TEXT";

        if (element.nodeName.toUpperCase() === "INPUT") {
            type = element.getAttribute("type").toUpperCase();
        }

        if (type === "FILE" && element.files.length > 0) {
            var fieldName = element.name;
            var fileName = element.files[0].fileName;

            /*
             * Content-Disposition header contains name of the field
             * used to upload the file and also the name of the file as
             * it was on the user's computer.
             */
            part += 'Content-Disposition: form-data; ';
            part += 'name="' + fieldName + '"; ';
            part += 'filename="'+ fileName + '"' + CRLF;

            /*
             * Content-Type header contains the mime-type of the file
             * to send. Although we could build a map of mime-types
             * that match certain file extensions, we'll take the easy
             * approach and send a general binary header:
             * application/octet-stream
             */
            part += "Content-Type: application/octet-stream";
            part += CRLF + CRLF; // marks end of the headers part

            /*
             * File contents read as binary data, obviously
             */
            part += element.files[0].getAsBinary() + CRLF;
       } else {
            /*
             * In case of non-files fields, Content-Disposition
             * contains only the name of the field holding the data.
             */
            part += 'Content-Disposition: form-data; ';
            part += 'name="' + element.name + '"' + CRLF + CRLF;

            /*
             * Field value
             */
            part += element.value + CRLF;
       }

       parts.push(part);
    });

    var request = "--" + boundary + CRLF;
        request+= parts.join("--" + boundary + CRLF);
        request+= "--" + boundary + "--" + CRLF;

    return request;
}

Although it looks complex, it has a fair amount of comments so that you won’t have hard times understanding what it does. It simply iterates over an array of HTML elements and for each such an element constructs a different message depending whether the element is a file upload input or not. It pushes this message into an internal array, which is finally joined using the boundary sent as an argument inside the send() method.

Here follows the source of the elements() getter, used in send():

/**
 * @return Array
 */
get elements() {
    var fields = [];

    // gather INPUT elements
    var inputs = this.form.getElementsByTagName("INPUT");
    for (var l=inputs.length, i=0; i
        fields.push(inputs[i]);
    }

    // gather SELECT elements
    var selects = this.form.getElementsByTagName("SELECT");
    for (var l=selects.length, i=0; i
        fields.push(selects[i]);
    }

    return fields;
}

The snippet above grabs all the INPUT and SELECT elements inside the FORM element associated with the Uploader object. These elements are eventually returned into a unified array. There are, however no checks on these elements, like filtering disabled controls. Furthermore, the RFC specifies that a client should send form data in the same order it was rendered in the user agent. For keeping the examples as short as I could, the method above doesn’t take care of that, but the code inside the accompanying archive does.

The final piece of code left for presentation is the generateBoundary() method which must return a string unique in the body of our request. For our simple example though, the method below should be just fine:

/**
 * @return String
 */
generateBoundary: function() {
    return "AJAX-----------------------" + (new Date).getTime();
}

The code inside is building a string based on the current timestamp to which some other characters are prepended. I’m using the uppercased word “AJAX” and some dashes, but this prefix isn’t mandatory, the only condition that must be met is that the result of generateBoudary() should not appear anywhere else in out request except for the boundary placeholders.

Finally, the headers property of our object remains like it was in the skeleton. It is there so that you can append additional headers to the request, for example:

var upl = new Uploader(form);
upl.headers["X-Requested-With"] = "XMLHttpRequest";

Save the source of the Uploader object in a file called “uploader.js”, we’ll use it in a few moments.

Putting it all together

Let’s now write the final HTML source and save it inside a file called “index.html”. Aside the markup, the code below introduces some event listeners for the “Upload” and “Preview” button:

<!DOCTYPE html>

<html>
<head>
<title></title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta http-equiv="imagetoolbar" content="false">
<meta http-equiv="imagetoolbar" content="no">
<link rel="stylesheet" type="text/css" href="css/default.css">
<script type="text/javascript" src="uploader.js"></script>
<script type="text/javascript">
window.addEventListener("load", function() {
    var input = document.getElementById("photo");
    var img = document.getElementById("img");
    var previewBtn = document.getElementById("preview");
    previewBtn.addEventListener("click", function() {
        img.src = input.files[0].getAsDataURL();
    }, false);

    var form = document.getElementsByTagName("form")[0];
    var uploader = new Uploader(form);
    var uploadBtn = document.getElementById("upload");

    uploadBtn.addEventListener("click", function() {
        uploader.send();
    }, false);

}, false);
</script>
</head>
<body>

<form action="upload.php" method="post"
      enctype="multipart/form-data"
      onsubmit="return false;">
  <fieldset>
    <legend>Upload photo</legend>
    <label for="image_name">Image name:</label>
    <input type="text" name="image_name" id="image_name"> |
    <label for="image_type">Image type:</label>
    <select name="image_type" id="image_type">
      <option>JPEG</option>
      <option>PNG</option>
      <option>GIF</option>
    </select> |
    <input type="file" name="photo" id="photo">
    <input type="submit" value="Upload" id="upload">
    <input type="submit" value="Preview" id="preview">
    <hr>
    <img src="" alt="image preview" id="img">
  </fieldset>
</form>

</body>
</html>

Now create another file, save it as upload.php, and write inside it the code we presented in the server-side section of the tutorial:

<?php

print_r($_FILES);
print_r($_POST);

That’s all. You may now test the application, which will hopefully work from the first run. Don’t forget to install Firebug to inspect what’s happening behind the scenes.

Conclusion

There’s probably a lot to be discussed around this new feature Mozilla introduced along with Firefox 3. Some may wonder if it is worth using it. Well, as ever, it depends on what you want to accomplish. You may employ fall back techniques (like the iframe workaround) in order to have support for other browsers, if that is your concern. If you want a fancy UI though, a Flash based uploader may be better. But don’t forget, the new API is not all about uploading. You may now read local files and process them right there in the browser. You may resize images, parse XML or do whatever your imagination limits are. In my opinion this is a huge step forward for web development and I’d really like other browser vendors to implement this API as the standards seem to be abandoned. Rich Internet applications would be far more powerful and their responsiveness further increased.

Tweet List all posts, go to homepage or subscribe to the RSS feed

My first contribution to an open source project

Two weeks ago, while writing some unit tests for one of my projects I wanted to use an XML configuration file in order to bootstrap the PHPUnit testing framework. As you may know, in PHPUnit you may organize your unit tests in test suites, and also give them names. So, for better organizing my tests, I wanted five directories holding five different test suites which I thought could be easily configured inside the phpunit.xml file. Well, apparently there was support for only one test suite and a ticket opened for such an addition to the framework. As a result I hacked a little bit the source code and came up with a simple patch (really, there is nothing fancy about it) so that now the config file accepts multiple test suites.

Thanks to Sebastian Bergmann the patch got accepted and it will be available with PHPUnit 3.4

For many (web) developers out there this might be something really, really trivial and they’re right, but this is my first contribution to an open source project and I’m happy about it. Some time ago, reading blog post of Andrei Maxim (a fellow web developer) I got inspired and said to myself that I should too contribute some code to an open source project (he wanted a commit though, not a patch). Well, this was my first step. More to come… I hope.

Tweet List all posts, go to homepage or subscribe to the RSS feed

How not to use dates in PHP

How many times did you find yourself using basic arithmetic operations to make a range of UNIX timestamps, given that you know the ends of the interval? I’m talking about something like this:

<?php

date_default_timezone_set('Europe/Bucharest');

$start = strtotime('01 October 2008');
$end   = strtotime('01 November 2008');

$next = $start;
while ($next <= $end) {
    echo date('Y M d', $next) ,'<br>';
    $next += 60*60*24;
}

If you run the above little script you might be surprised to see that October 26th appears twice, one after the other.

If you’re not aware of Daylight Saving Time you may have hard times understanding what’s happening behind the scenes and solving the problem. In the above snippet I started the script by specifying that PHP’s all date/time functions should use Bucharest’s timezone. That means that my date() call in the for loop would know that October 26th, 2008 is officially marked as the end of Daylight Saving Time for Bucharest (as well as whole Europe). In that day 04:00 AM became 03:00 AM, “rewinding” time one hour and passing from EEST to EET.

So how can only one hour duplicate a day? Well, by observing DST, one day in year gets one hour longer, while another day gets one hour shorter. October 26th, 2008 is the day that got one hour longer, counting a total of 25 hours, while our script is adding 24 hours for each iteration. That’s why, when the counter is supposed to return a UNIX timestamp for October 27th, 2008 it actually returns the timestamp for October 26, 2008 23:00:00, because now it’s one hour behind DST. Here’s a modified script to show exactly this transition:

<?php

date_default_timezone_set('Europe/Bucharest');

$start = strtotime('01 October 2008');
$end   = strtotime('01 November 2008');

$next = $start;
while ($next <= $end) {
    echo $next ,' ';
    echo date('Y M d H:i:s', $next) ,'<br>';
    $next += 60*60*24;
}

echo '<hr>';
$hours_in_26 = (strtotime('27 October 2008') - strtotime('26 October 2008'));
$hours_in_26 = $hours_in_26 / 60 / 60;
echo "October 26th, has $hours_in_26 hours when observing DST.";

I’ve also made a little diagram to highlight the problem. On the left hand side is the way date() function works when we’ve set a timezone value. On the right hand side is the way our script works, by treating all days as having only 24 hours. The green rectangle is that one hour difference between our script and date(). The red hours is when DST ends.

Now that we know the problem we should fix it and the most simple solution is to change the timezone. Instead of Europe/Bucharest I could have been used GMT and the above script had been worke well:

<?php

date_default_timezone_set('GMT');

Unfortunately, using GMT is not always an option, as you want to display users valid dates for their territories, that is, you want localization (L10N). The other solution, which is better, is to not rely on arithmetic for such calculations. You’re better off using mktime() which, as any other date/time function, is DST aware.

<?php

date_default_timezone_set('Europe/Bucharest');

$start = strtotime('01 October 2008');
$end   = strtotime('01 November 2008');

$next = $start;
while ($next <= $end) {
    echo date('Y M d H:i:s', $next) ,'<br>';

    list($month, $day, $year) = explode('-', date('n-j-Y', $next));
    $next = mktime(0, 0, 0, $month, $day + 1, $year);
}

By the way, changing the timezone identifier to “Asia/Jerusalem” would double October 5th, 2008 in the first version of the script. You may find more about these on timeanddate.com.

Tweet List all posts, go to homepage or subscribe to the RSS feed

MVC example from real, biological life

Lately I’ve been thinking a lot about software design patterns and software architecture in an attempt of being a better software developer (or just being one). Anyway, too much talk, I want to get to the subject because I think it’s very nice.

You’ve probably heard of the Model-View-Controller pattern which is a big hype nowadays thanks to the Ruby on Rails web framework. It’s all about separating data access (Model) from data presentation (View) and that’s all. You may wonder where’s the third part, the Controller. It’s in between gluing the two parts together. The controller, while an important aspect of the MVC paradigm, is not as important as the idea of separation data and presentation.

You’ve also probably read a lot of examples about MVC, involving web application that suddenly have to switch from a certain database vendor to another or output data in multiple formats, like HTML, JSON, PDF, etc. Well, here’s a little MVC example that actually lies within your own body.

It’s the very human act of expressing ideas, either written or spoken.

When someone is expressing her ideas in speech she uses an MVC system where data is the idea itself (what she thinks) that sits in the Model (our conscience and perception of the surrounding world), the View is the language in which the ideas are presented and the Controller is the sum of biological and associated neuronic structures that let us map these ideas to comprehensible and logical sounds (in a normal human being).

It’s true that I exaggerated a little about the limits between the parts of this system and that these are very blurry line that separate them… nevertheless is the idea that matters. If it weren’t for this MVC system inside us, speaking foreign languages would be impossible.

P.S. Who?! Me? A nerd?!
P.S.S. I’m not implying that my English view is perfect

Tweet List all posts, go to homepage or subscribe to the RSS feed

How to install Python libraries on Windows

Whenever you have to install another Python library on a Windows OS is good to do it like this from the command line:

cd path/to/library/dir
python setup.py bdist --format=wininst

This will pack all the source into an installer that can be found under “path/to/library/dir/dist”.

Using this method you will later be able to go to “Control Panel” -> “Add or Remove Programs” and uninstall such a library from there.

For other platforms and options see Python documentation on creating built distributions.

Tweet List all posts, go to homepage or subscribe to the RSS feed

Assessing Google Chrome

I have already discovered some bugs and managed to crash two tabs in under 3 minutes when I interrupted for writing this post. There are also some features I miss from Firefox. Details…

Bugs

1. It erroneously fills some form fields from a forum I often visit overriding the input’s value attribute (at least that’s what I was able to see with the built in, à la firebug, inspector, which is good news by the way.)
2. The whole browser freezed when opening a link from the above mentioned forum that pointed to my weblog home page. I succeded to take back control when killing one process from the Windows task manager, which aparently made two tabs, not one (I killed one process, not tow), to show the sad face of failure.
3. Opening a 155 page PDF document made iresponsive the whole browser, not just the respective tab as said in the comic book and reduced 4 tab-processes to only one process in the Windows task manager which took the whole browser down when killing it.
4. After reboot the PDF page still isn’t rendered as it should and any interaction with it slows down (to freezing) the whole browser. (At least this blog entry was preserved in the textarea).
5. There appear to be some bugs with the character encoding support. In Romanian we have special characters like “ăîâșț” that aren’t rendered as they should nor when the enconding is ISO-8859-2 (which I know should be OK for Romanian), nor when I change it to UTF-8. Anyways, the website isn’t sending a charset in the HTTP headers (according to LiveHTTPHeaders), on other web sites it is OK.

Missing features

1. Can’t scroll pages while middle-clicking :-( That’s awful for me, a reason not to use a browser.
2. Iframes used for rich text editing don’t have spell checking, whereas textarea elements do.
3. I can’t turn off spell checking on textarea elements.
4. Maybe not a missing features but I couldn’t find it. Where can I choose another engine from my opensearch engines that were imported from Firefox after the installation? (later on) it may be redundant as all the opensearch providers are available for querying inside the address bar.
5. I’d really like to disable the close buttons on every opened tab.
6. When opening many tabs (> 20) there’s no way to know what site is in which tab, except for the favicon (if there is one) that is being displayed. That is because a tab’s width is in inverse ratio with the number of tabs. I tend to like more the scrolling feature of Firefox in such a case (but maybe I’m just spoiled by Firefox). Anyway, they load fine dispite the large number.
7. It comes with built-in support for Adobe Flash and Adobe PDF but not Quick Time.
8. At this moment I have 7 folders of bookmarks imported from Firefox. When clicking one, there’s a submenu that popups and the bookmars contained can be seen, well, now I expect that hovering another folder will open it automatically without click on it again but it doesn’t happen like this, you have to click it again. I think on a Windows OS this is common practice for user interface (not to be forced to click again).
9. I don’t have a history list by the back/forward buttons.
10. An RSS/Atom reader like in Firefox.
11. No “Zoom page” tool, only zoom text with CTRL++, CTRL+- and CTRL+0 just like in Firefox.
12. I can’t middle click the back/forward button to open a previous page in new tab.

Good things/features

1. The HTML inspector (mentioned above) and JS debugger and console.
2. Searching through the installation files I discovered some js scripts that deal with the local data store and seemed to be integrated with the Inspector but I couldn’t lauch it from the browser.
3. The source turn links into real links so that I can quickly go to the CSS and JS files of a website.
4. Mozilla Prism’s idea of web pages that could be saved as desktop apps is now to be found in Google Chrome. You can save a shortcut to Gmail, for example, on the desktop, quick launch bar and start menu. Details
5. It has “View Frame Source” when right clicking on an iframe element.
6. I like the search capabilities in the address bar (I always wished it in Firefox).
7. The “bookmark this page” from the address bar is like Firefox’s, except it misses tagging.
8. Incognito mode.
9. Speed of loading for some of the pages I visited.
10. Incremental search + it shows how many results it has found until that point + highlighting of matching keywords + F3 does work to jump to next result + … the place of the search box :).
11. CTRL+J opens downloads tab (just like in Firefox).
12. Detaching tabs in standalone windows.
13. X/Y resizable textarea element, but the resizer image has a non-transparent upper-left corner.

WTFs

1. The installation place. On my system (Windows XP Professional 32bit) it was in C:\Documents and Settings\username\Local Settings\Application Data\Google\Chrome\Application\chrome.exe, along with Gears and… GoogleUpdate.

Tweet List all posts, go to homepage or subscribe to the RSS feed