Design patterns are bullshit!

It all started Monday morning at college. Professor of Information Systems was talking about evolution of programming techniques and at the end of the chain was OOP. The pinnacle of program design. Well, no. Even professor admitted that OOP failed to deliver. (No word on FP though, I was kinda disappointing). This made me thinking about problems of Java and the like.
Some hours later I'm sitting in cafe Metropol above Kiberpipa having tea with some friends - freshmen from FRI. And one of them asks me if there is a class on design patterns. I give a puzzled look and say no and he goes on to explain he's currently reading Design Patterns in C#. Apparently an awesome book that teaches you some general approaches to problems.
But I have quite strong opinions on some topics. And one of them are design patterns. I believe they are bullshit and I said that. I didn't read the GoF book and I don't have any intention to do so in near future. But I'm familiar with some patterns. Mostly workarounds for shortcomings of OOP languages and contrived solutions to non-existent problems. And I explained this.
Response was to paraphrase: "Well, MVC is a great design pattern". But I argued that it isn't a design pattern at all. Since everybody had a laptop, a quick wiki search cleared this up. It's an architectural pattern. Not a design pattern.

What are design patterns

So I asked him out of curiosity for some patterns from the book(also trying to prove my point).

Singleton

Well I used this one, so I cannot say it's bad. But I can still say it's overused and when it lets you access mutable object graph. Because this leaks mutable shared data all across your code base. But it gets real messy with double locking and stuff like that. Luckily Java solves this with enum. Now design pattern becomes just a keyword. That doesn't qualify as a pattern in my book. C# has static classes that are basically same thing, singleton instance held by the class loader. For some reason C# folks call this Monostate, but it's the same concept. Concepts are important, because they're language agnostic. Even though patterns try, they inherently aren't. And just for the last nail in the coffin. Scala has object keyword that creates a singleton. 

Factory, static factory...

This one is also abused. You even have metafactories that produce factories. Srsly...wtf? That's exactly like currying but wrapped up in objects and contrived to the point you no longer see it's currying. The only useful use-case for them is abstraction over constructors. That is, a single method that, depending on the arguments calls some constructor for the type it constructs. But again, this is hardly a pattern. 

Decorator

Decorator in statically typed languages means just implementing an interface or mixing in a trait(scala). I don't see the point here. That's why interfaces(traits) exist. 

Proxy

My friend insisted that this is something like Strategy pattern(didn't use the word) but from the other way. Proxy is the user of strategy object. Anyway strategy is just a wrapper for function value, nothing to see here. But not I googled it and I'm even more puzzled. It seems this means object reuse. Like literally sharing data. You know, like you do with any immutable values. Did I misread?

And about here we digressed to static vs dynamic typing. Sadly I was the only one for static. Apparently nobody wants compiler to help them. Now I'm sad. Compilers are one of the best programs out there. And with type inference they do all the work for you. You must be a fool not to use one and rather do a shitload of unit tests instead.

So... and anyone point to a useful design pattern or am I right and they truly are bullshit?

Related articles 

• Does Functional Programming Replace GoF Design Patterns?
• Do These Design Patterns Stand the Test of Time?: Abstract Factory

Cool Monday: HList and Shapeless

Java (programming language) (Photo credit: Wikipedia)

HList as in heterogenous lists. This means every element is of different type. Yeah sure, just list List<Object> in Java, but that is in no way typesafe. I want compiler to know the type of every element and stop me if I try to do something silly.

Linked lists to the rescue

So what's a linked list anyway? A sequence of nodes with pointers to next. And a nice implementation(still talking Java here) would be generic to allow type-safety for homogeneous lists. It turns out generic are solution for HLists too. Just introduce additional type parameter. Apocalisp has a great post on implementing them in Java. Here's just a factory method to see the gist

public static <E, L extends HList<L>> HCons<E, L> HCons(final E e, final L l) {
   return new HCons<E,L>(e, l);
}

Problem comes with instantiation.

final HConsInteger[], HNil>>> b =
      cons(4.0, cons("Bar", cons(new Integer[]{1, 2}, nil())));

Java requires A LOT of type annotation. It works but it's just painful and it doesn't pay off.

Type inference to the rescue

Type inference gets rid of this problem entirely. Let's implement whole working HList in scala.

abstract class HList[H,T<:HList[_,_]] {
  def head: H
  def tail: T
  def ::[A](a: A) = Hcons(a, this)
}

object HNil extends HList[Nothing, Nothing]{
  def head = throw new IllegalAccessException("head of empty hlist")
  def tail = throw new IllegalAccessException("tail of empty hlist")
}

case class Hcons[H,T<:HList[_,_]](private val hd: H, private val tl: T) extends HList[H, T]{
  def head = hd
  def tail = tl
}

So this list can be instantiated like this

scala> val myHList = 1 :: "hi" :: 2.0 :: HNil
myHList: Hcons[Int,HList[java.lang.String,HList[Double,HList[Nothing,Nothing]]]] = Hcons(1,Hcons(hi,Hcons(2.0,HNil$@dbb62c)))

And it just works. Scala compiler does all the heavy lifting with type annotations. This implementation bare bones and doesn't provide any useful methods(even random access!). Check out Miles Sabin's shapeless project for a useful implementation and much more. I provides indexing, map, fold, concatenation, type-safe casts, conversions to tuples(and abstracting over arities!) and back. And even conversions with case classes. Just click the link above and read the readme. It's awesome.

Related articles

• A better Java: Scala or Xtend?
• Is Java Dead or Invincible?
• Quicksort - the Easy Way

Setting up for scala development on Android

Image via CrunchBase

Scala (programming language) (Photo credit: Wikipedia)

I've been developing for android more than a year now and a few months in scala. So naturally I wanted to combine the two. But it's not dead simple. This is kinda a tutorial an a reference if I ever forget how to do this. It took me a few days to figure it all out. I tried maven, ant with special config and sbt(I need to learn more about this one) but in the end I just wanted fast solution integrated into my IDE.

So I use IntelliJ IDEA community edition for my IDE.  You should check it out, it's totally awesome. It's primary a Java IDE but scala plugin rocks. It offers some more advanced text editing capabilities, not like vim or emacs but enough for me. It also brings up coloring and editing features that are language aware. So you have a shortcut(Ctrl-W) to select semantically valid block. And press it again to expand to next bigger valid piece of code. And stuff like that. Real-time structure view is nice and there are some cool refactorings. But scala REPL is where fun begins. You get your module classpath pre-set and you get full editor capabilities in REPL. Enough with advertisement(they didn't pay me to do this) and let's get to work. 

Prerequisites

• JDK...duh!  I use OpenJDK 7, IDEA gives some warnings but it works like a charm
• Android SDK and at least one platform
• IntelliJ IDEA
• scala distribution. I recommend you use latest stable release from here 

Setting up

First install scala plugin. It's quite straightforward. Plugin Manager->Browse repos->search for scala->select->ok.

Now actual setting up. I use global libraries for all my projects, you can also put these into just Libraries and to that on per-project basis.

Open project structure(no project open) and go to Global Libraries. You need to create two libraries containing jars from <path to scala>/lib/.

First scala-compiler with scala-compiler.jar and scala-library.jar and then scala-library with scala-library.jar and anything else you might need. Reason for scala library in compiler is that compiler also relies on scala lib. I needed quite some time to figure this out.

This whole process can be automated if you add scala to your project when creating it but it's not possible with android so you need to know how to do it by hand. 

Creating a project

• Project from scratch
• add android module and configure it
• now go to project structure. add scala facet to this module and go to its settings and set the compiler jar.
• back to module and add dependency to global scala-library
• set dependency to provided. This is important. Else it will try to dex whole library and you'll end up with "too  many methods error".

Now your project should compile. But not run.

Running

Obviously not including scala library in the build means you need to provide it in another way. For developing on emulator I customized it to provide predexed scala library. Excellent tutorial.

In a nutshell

$ git clone git://github.com/jberkel/android-sdk-scala.git
$ cd android-sdk-scala
$ ./bin/createdexlibs

$ bin/createramdisks

$ emulator -avd ... -ramdisk /path/to/custom.img
$ adb shell mkdir -p /data/framework
$ for i in configs/framework/*.jar; do adb push $i /data/framework/; done

And reboot.

There is also (not so trivial) part about pathcing a device. However you can try Scala Installer from Play to do this. I had some success and some failures.

Now the app should run on your device.

Deploying

Well it doesn't work on other devices right now. For export you need to change scala-library dependency back to compile to include it into the build. Trick now is to enable ProGuard to remove unnecessary methods and classed to fit the jar through dexer. You do this in Tools->Android->Export. Select ProGuard and your config. I got mine from jberkel's repo. That's it. Sadly this export takes quite some time. Scala's standard library is not a piece of cake afterall(actually it is a cake). Minute and a half on my machine for small apps. So I only to this for testing on other phones and deployment.

Faster compilation

Compiling with scala-libray set to provided is much faster but not fast enough for me. I want to be doing stuff not waiting for it to compile. 

Turns out compiler is the big time sucker(and I'm being Capt. Obvious). Afterall scalac is not known for it's speed.

Enter FSC or Fast Scala Compiler. This is a scala compiler running in the background having everything preloaded and just does incremental compilation. It even comes with standard scala distribution and is supported by IntelliJ IDEA. Great. 

To set it up just head over to Project Structure->Scala facet and select Use FSC. And then immediately click Setting to access Project Settings and set compiler jar for the compiler.

Success. Scala builds are now on par(or even faster!) than java ones. 

No more fencing for me.

Related articles

• Alternative JVM languages
• Functional Programming Principles in Scala: Setting up IntelliJ
• Easily Cross-compile and Release Scala Projects With sbt
• Pretty function composition in scala and asynchronous function composition on android

Javascript faster than light! (well C actually)

157/365. Acorn - Oak Nut - The Scrat Problem. (Photo credit: Anant N S (www.thelensor.tumblr.com))

Disclaimer: I never was a fan of js, but I've come to think it's quite AWESOME!

Anyway I invented my own toy language scrat recently. And I now I want it to go fast and do cool stuff. So I went on to compile it. Well more appropriate term would be "translate"(as zidarsk8 pointed out) since my target is JavaScript. And then I use node.js to run it - browser test sometime in the future. Enough about that, I'll be doing a post when I get everything to run under js.

My original purpuse for translation was speed as node uses V8 and that's quite speedy. So I did a quick test. I wrote a simple recursive Fibonacci sequence generator. The cool thing about this is that it takes fib(n) steps to calculate fib(n) but call-stack depth is just n - I don't have loops and I haven't implemented tail call optimization yet.  And then I wrote same thing in js an noticed it's quite a bit faster. Great. Now halfway through implementation(more like 80%) I decided to do a real benchmark.

Scrat

Here's the source

func fib(n) if n<2 then 1 else fib(n-1) + fib(n-2)
println(fib(30))

Neat huh?

And then I timed this repeatedly and all results were about the same:

andraz@andraz-desktop:/tmp/temp$ time scrat fib.scrat 
1346269.0

real 0m3.254s
user 0m3.652s
sys 0m0.096s

Of course there is some startup overhead that must be taken into account so I ran an empty file

andraz@andraz-desktop:/tmp/temp$ time scrat empty 

real 0m0.420s
user 0m0.448s
sys 0m0.032s

To obtain total running time of 3254 - 420 = 2830ms

Javascript

Then I translated my source into js. Below is the untouched(apart from whitespace) result

function fib(n){
    return (function(){
        if(n<2.0){
           return 1.0;
        } else {
           return (fib((n)-(1.0)))+(fib((n)-(2.0)));
        }
    }());
}

In scrat ifs are expressions too, so the if is wrapped in an anonymous function. In spite of additional invocations, running time decreased dramaticaly: 128ms.

Real reason for this test was my wory of if overhead so I did a by-hand implementation

function fib(n){
    if(n<2){
        return 1;
    } else {
        return fib(n-1)+fib(n-2);
    }
}

Running time: 35ms.
Auch! Wrapping the if statement into an if expression multiplies running time by almost 4!! But it's still 22 times faster than my interpreter. (My code sucks I guess)

C

At this point you should be wondering what does this has to do with C. Not much. I tried to do an implementation in C just for kicks. To see how much overhead my by-head function still has. I was assuming C program will go in something like 10ms.

My best attempt(in the same style: recursion, if expression)

#include <stdio.h> 

int fib(int n){
 return (n<2)?1:fib(n-1)+fib(n-2);
}

int main(){
 printf("%d", fib(39));
 return 0;
}

Startup time is neglectible here, since it doesn't load an interpreter or a framework, and I wouldn't even know hoe to measure it. So here's the full running time..ready?
634 fricking miliseconds!
That's only 4 times faster than my interpreted code. And 18 times slower than javascript. I'm not sure how is this even possible. It's probably just my bad implementation. But rules were: keep the style.
So I hereby declare: js is faster than C. (in this microbenchmark)

UPDATE:

I did something terribly wrong. Look at the C code closely. Its fib(39) where in scrat and js I called fib(30). I just compared apples and oranges. 

Fixing the C code I got average 20ms. A bit faster than node. So it turns out javascript isn't faster than light(c) but it's pretty damn close. 

I guess this whole post is now wrong, but it was fun to do nonetheless. 

Related articles

• No tail call optimization in PHP (yet)
• Using Javascript? You *MUST* know about invocation patterns
• Faster than C? Parsing binary data in JavaScript.
• Making a programming language: Part 6 - functions

Virtual machine in C(++)

This is not a tutorial. This post is a flashback I had today. It might be a bit fiction as my memory about events tends to be fuzzy at times. But I promise it at least resembles the real story.
I was in elementary school and just found out about programming and was learning about c++. After reading "C++ na kolenih" by Goran Bervar I was empowered by knowledge and tried to do all sorts of projects. Mostly in console. Stuff like subtitle format converter - NIH syndrome. I was a bit frustrated because I couldn't find any books about windows programming in the library. Yes, library was may primary source of information, because my English was not nearly good enough for technical stuff.
I might add here I worked on Windows 98(and later XP) with DevC++. I found out about Visual Studio in a few years and did some Windows development.
I digressed a bit. Then came the most optimistic idea. A virtual machine. Something quite high level(instruction to print) an eventually an assembler. I now realize I was always into language stuff. So a designed a machine language with just enough instructions to do Hello World, that is PRINT and END.

Implementation

At first I thought about doing a monolithic structure - switch case(in fact what I've done with scrat recently). But I had some considerations. What if number of of instruction rises a lot? I'll be left maintaining spaghetti code. Or at least I thought that's what spaghetti code looks like, but in retrospective I believe I had a good taste anyway. 

But I tried that anyway. Just for kicks. Did whole machine as one class that had an array for memory and a single point of entry - boot. It run a loop a while loop with PC<-PC+1, fetched instruction from memory, switched on them, called appropriate method to implement that instruction and looped. Even had registers. I think my current professor of Computer Architecture(this course brought back the memory) might actually be proud if he heard what I did back then. 

Pointers

I was always quite comfortable with pointers. I don't now, they're mathematicky concept. I like such stuff. Or perhaps it was because I was young when I was introduced into the matter and wasn't spoiled with automatic memory management(which I quite like nowadays). 

So I tried with function pointers. C is cool enough to let you have pointers to functions! And that means higher order functions. But I didn't know about math enough to appreciate the concept as I do now. But still - I thought it's extremely cool. So I did a function that halted execution and printed out "no such instruction". Why you ask? Well I did a 256-cell table(8-bit instruction) of pointers to functions. Now I didn't have to switch - just a look-up and invocation. Great. Apart from the fact it doesn't work. 

Compiler said something along the lines of "You cannot make a table of pointers to functions!". I was puzzled. Skip 10 years into the future. Today I was rethinking this and thought about casting the pointer. All the functions would be void->void so I can cast back no problem. A table of void pointers and casting. Yay!

Now 10 years back. I didn't think about casting the pointer. Type info was sacred to me!

So I "invented" function objects.

Objects

I swear to god I have not heard about function objects back then. It wasn't until this year reading Bloch's Efficient Java where he talks about strategy objects. I immediately recognized my idea. So now I had many classes, every one implementing execute method. And I had an array of these objects. Now I did a look-up and invocation on an object. Sweet. And it even worked. But sadly I dropped the project and went on to graphics. Learnt SDL and did Tic-Tac-Toe. And dreamed about doing a vector 3D engine(curves baby!). Which until this day I didn't try to implement. Maybe I'll try in near future. 

Related articles

• Sol - a sunny little virtual machine
• What is spaghetti code?
• The hidden cost of C++
• Void pointers in C
• Making a programming language: Part 1 - how to start

Making a programming language: Part 7b - using objects

Table of contents, Whole project on github

Something like EPIC FAIL occured to me and I published a post containing only half the content I intended to write. So I'm doing a part b.

My intended usage of objects is something along the lines of

objectName.someProperty
objectName.someFunction()
someFunction().someProperty
someObject.someProperty.someFunction().someProperty.someFunction

Explanation

1. getting a value from an object
2. invoking a function contained in an object
3. getting a value from returned object of the invoked function
4. a bit contrived example. Invoking a function contained inside a property(object) of an object and then getting a function value from a property of the returned value from the first function. That's a mouthful, just read the damn code instead

Dot access

So everything bases on those little dots. First my thoughts were something like "you just do expr <- expr | expr.expr". This is just wrong. At least I should have reversed the order as this leads to infineite left recursion. Then I might have got away. Then I realized I only need dots after function calls and simple identifiers. Design choice(if you think it's a bad one leave a comment). Notice the "simple identifier". That's what I did: Renamed identifier to simple identifier and put something that handles dots under name identifier. And then fixed everything. 

case class DotAccess(lst: List[Expression]) extends Expression

private def identifier: Parser[DotAccess] = 
  rep1sep((functionCall | simpleIdentifier), ".") ^^ DotAccess.apply

That's about it. At least for parsing. Now the fun begins.

Nesting scopes

Scopes were designed with nesting in mind. This is a double edged sword. See, the "privates" can be  done if you rely on not being able to access the parent scope. If dot access exposes full addressing functionality a powerful feature ceases to exist. So some protection should me in place. Something like strict get

class SScope ...
 def getStrict(key: String): Option[Any] = map.get(key)
...

And I also added an unlinked view to it just to ease usage. This is just a method that returns new SScope with no parent overriding getters and put to use map available in closure.
So now I can walk down the list in DotAccess recursively and explicitly override the implicit scope parameter. And everything automagically works. Well, not quite. If you have a function call, the arguments need to be evaluated in top scope. Not in the nested one like the function identifier. At first I didn't even think about this and only failing attempts at more complex recursion brought up this quite obvious bug.
So how to solve this? I could pre-evaluate all arguments, but I use recursion to do this and it's two levels(at least) deeper from where dots happen. So no go. I need to carry on the outer scope. I overloaded the apply method from Evaluator so other code can still function(tests ftw!) and all in all it looks like this:

def apply(e: List[Expression])(implicit scope: SScope): 
    Any = {
    (e map apply).lastOption match {
      case Some(a) => a
      case None => ()
    }
  }

  def apply(e: Expression)(implicit scope: SScope): Any = apply(e, None)(scope)

  def apply(e: Expression, auxScope: Option[SScope])(implicit scope: SScope):     Any = e match {
    ...
    case DotAccess(list) => {
      val outerScope = scope
      def step(list: List[Expression])(implicit scope: SScope): Any =
        list match {
        case Nil =>        
          throw new ScratInvalidTokenError("got empty list in DotAccess")
        case elem :: Nil => apply(elem, Some(scope))(outerScope)
        case head :: tail => apply(head) match {
          case s: SScope => step(tail)(s.unlinked)
          case other => 
            throw new ScratInvalidTypeError("expected scope, got " + other)
        }
      }
      step(list)
  }
}

So an optional aux scope is the answer. It doesn't seem pretty to me, but it does the job. 

next: trying to go faster

Related articles

• Making a programming language: Part 7 - objects
• A Quick Intro to TypeScript
• What is an object?