Pipes Output http://pipes.yahoo.com/pipes/pipe.info?_id=skjzGlDl3RGCCO8fPxJ3AQ Sat, 28 Jan 2012 12:27:39 +0000 http://pipes.yahoo.com/pipes/ http://dcsobral.blogspot.com/2012/01/string-interpolation-on-scala-210.html One of the Scala Improvement Proposals for Scala 2.10 is String Interpolation. It has recently been added to trunk, behind the -Xexperimental flag, and I have started playing with it. At first, I stumbled upon bugs and limitations of its current implementation relative to the proposal, but I finally got something working.To be clear: the interpolation works fine, in both of the provided forms (with and without formatting). As usual with Scala, it's the possibility of replicating the functionality for my own purposes that gets me excited. I usually explain the whys and the hows of my code, but in this case a simple paste says it all, imho.dcs@ayanami:~/github/scala (master)$ scala -XexperimentalWelcome to Scala version 2.10.0.rdev-4232-2012-01-23-g9a20086 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_26).Type in expressions to have them evaluated.Type :help for more information.scala> case class StringContext(parts: String*) { | object matching { | def unapplySeq(s: String): Option[Seq[String]] = { | val re = (parts map ("\\Q" + _ + "\\E") mkString ("^", "(.*?)", "$")).r | re findFirstMatchIn s map (_.subgroups) | } | } | def s(args: Any*) = scala.StringContext(parts: _*).s(args: _*) | }defined class StringContextscala> "23/01/2012" match { case matching"$day/$month/$year" => s"$month-$day-$year" }res0: String = 01-23-2012 Daniel Sobral tag:blogger.com,1999:blog-6373963829340632529.post-370427441742826755 Mon, 23 Jan 2012 20:18:00 +0000 http://dcsobral.blogspot.com/2011/12/using-scala-api-documentation.html One link that was missing from my post about Scala on the Web was the link to the Scala API documentation, often called "scaladoc" for short, after the tool that generates it. I tried to put it in, but it kind of broke the narrative and, to be honest, I have a lot to talk about the subject. So I decided to do a whole blog just about it.First of all, there are two main links that you can use to access it:The link to the API of the latest Scala release, andThe link to the nightly Scala build of the next Scala versionMost of the time, I prefer the second link: it contains improvements to the Scaladoc tool, and the documentation often contains improvements. On the other hand, being a nightly release, it is subject to regresssions in the Scaladoc tool, and the documentation contains information that is not correct for the latest release. For that reason, I keep both links in my bookmarks.So, what else is there to say? Well, if you are new to Scala, a lot. Those familiar with the Java equivalent probably find it both familiar and strange: the screen is divided into left and right sections, the right section having description of classes and packages, while the left contains a list of them. Whereas Java splits package and class lists, however, Scala does not. And, of course, the look is completely different. These, however, are skin-deep differences, and I want to get to the bones of the matter.One Doc, Two FramesThe first thing I want you to notice are the two search boxes: one on the left, at the very top of the page, and one on the right, a bit lower. Scaladoc is search-oriented! That means you usually don't browse it, looking for stuff, but just type what you want. You can still browse, of course, which is useful when you don't know what you are looking for.On the left side you have the package hierarchy and classes, traits and objects belonging to the packages. Note that classes, traits and objects can be members of other classes traits and objects, in which case they won't appear on the left.The right side contains information about a selected package, trait, class or object. The URL will change to match what is being displayed on the right side of the screen, so that you can easily bookmark or share links to specific class or object. At the present, there's no way to further refer to a member of a class, such as a specific method. This improvement will be added at some point in the future.Typically, you'll search or browse for a class on the left side of the screen, and then browse its contents on the left, or further search for a particular member of that class.The Left FrameLet's drill down the left side, then, to get a better understanding of what's there and how to use it. At the top of the left frame, you'll see this:Topmost is the search box, with a little "x" icon on the right hand to clear the search. Searching for something will hide any traits, objects and classes that don't match, as well as any packages that don't have any matching members.Right below that is an index of all existing methods. Click on a letter and you'll get all methods starting with that letter, and the places they are defined at. Click on the hash symbol (#), and you'll get a page with all methods starting with a symbol instead of a letter. For example:Finally, you have a small caption saying "display packages only". Surprisingly, that's a clickable option. In fact, ScalaDoc is full of clickable parts, so if you are getting familiar with it, my advice is to try to click stuff, just to see what happens. Back to that caption, though, it switches the package hierarchy from displaying all entities to displaying packages only. Clicking it will give you something like this:If you click on "show" on one of these packages, it will open up that particular package. If you click on "display all entities", it will revert to the initial mode of display.Speaking of "show", let's now look at the various parts of the entities list:The darker background indicates package or package objects, and the entities on the lighter background right below it are the classes, objects and traits belonging to that package, as indicated by the icons on their left. Note that, though package objects have other members such as methods, they do not appear on the left frame of Scaladoc.The icons for "o", "c" and "t", in dark blue, green and light blue respectively, indicate objects, classes and traits. A name can be shared between an object and a trait or class, as seen for Regex above. Traits and classes cannot share the same name, however, so each name will have at most two icons beside it.If you are not familiar with Scala, an object is a singleton, containing what, in Java, would be represented as static.One thing to realize here is that everything in that image is clickable, except whitespace. You can click on "scala.util.matching" and "scala.util.parsing.combinator", on "hide" and "focus", on "Regex" and "RegexParsers", and on the icons.Clicking on a package name will show its traits, classes and objects on the right frame, unless the package is a package object, in which case the right frame will show the other members it might have. This is important because many package objects contain implicit definitions used as helpers with that package. Check, for instance, scala.sys.process.Clicking on "hide" will hide the entities belonging to that particular package, but not any subpackage that might exist. The text will then change to "show", which will revert this action upon being clicked.Clicking on "focus" will hide all other packages from view, like this:Clicking on the "x" icon that appears will revert this action.Clicking on an icon for object, class or trait will show information for it on the right frame, as will clicking on the text itself. If an object shares a name with a trait or class, however, clicking on the text will show not the object, but the class or trait, following the assumption that this is what people want most of the time.On recent ScalaDoc versions, clicking on an entity will also move the focus to the search box on the right frame, so that you can instantly typeThe Right FrameTo begin the discussion of the right, I picked GenSeq, which is rich enough in ScalaDoc UI components, but (relatively) poor enough in actual content to fit in here.You may have wondered why the search box is not at the top on the right frame, like it is on the left. The reason for it is our starting point in explaining the right frame.The right frame is divided in three parts, the topmost two being shown above. The first part contains general information about the selected entity, and it comprises everything from the top until right before the search box. The second part starts with the search box, and is comprised of everything in that gray background. This part contains display options that affect the third part of the right frame. The third part contains all members of the selected entity, with individual information for each one.From the top, then, we have a green or blue background (the former for traits and classes, the latter for objects, packages and package objects) on which the name of the entity is prominently displayed. A big icon beside it indicates what kind of entity it is: t for traits, c for classes, o for objects and p for packages and package objects alike.If the icon is slightly folded on the bottom, like the one in the example, clicking on it (or the entity name) will switch the right frame to the companion of that entity. If you are not familiar with Scala, objects, traits and classes that share a name are said to be companions to each other. Clicking on the GenSeq trait above, then, will display the GenSeq object.In a smaller font above the entity name is the full path to that entity. Clicking on a path component will display that component.After that, in a gray background, comes a description of all classes, traits and type parameters used in the definition of that entity. It does not list classes or traits that are inherited -- that is available further below. Not to sound too repetitive, but clicking on any of the classes and traits will display it... Also, moving the mouse over one of these names will show the full path for that name.What follows is the full description and attributes associated with that entity. I deliberately choose one extremely poor in those, so that I could concentrate on what ScalaDoc provides. One of those things is the link to the source code in which that entity is defined. Not all Scala projects provide that attribute, but Scala API itself does. The link currently points to the web interface to the old Subversion repository -- I presume this will be switched to the new repository on Github in the near future. At any rate, all niceties of source version control systems are available on that link. For the Scala API, anyway."Linear Supertypes" and "Known Subclasses" at the bottom of this part can be expanded upon click, to display the exact linearization of an entity's supertypes -- the inheritance precedence -- and all known subclasses. For example, for List it will show this:Also shown above is the tool tip indicating the full path of one of the supertypes being pointed at, just like mentioned above for entity declaration.Let's now look at the second part of the right frame:The search box works pretty much like the one on the left frame, hiding anything that isn't a match, but it includes descriptions on the search as well. Search for a verb, therefore, will often yield good results, unless the verb is too general.One particularly nice feature, available on recent versions, is that typing multiple words will search for matches of any one of the words, which makes it easy to display two methods close together on the screen.All other options below the search box also change the way things are shown in the third part. The default Ordering mode, Alphabetic, will display all non-private members of an entity, separated in categories which we'll shown below, in alphabetical order. This is different than Java, which only shows full information for members defined or overridden on that class/interface.Clicking "By inheritance" will change the display mode to separate the members according to where it was last defined/overridden. Full information will still be displayed, and the members will still be shown in alphabetical order in their own section.The Inherited options let you easily filter out inherited methods. Clicking on "Hide All" will toggle off all supertypes, leaving only the entity itself selected. This will hide methods that are not abstract, defined or overridden on the entity. For GenSeq, for example only two methods will be displayed: seq and companion.Note that clicking on "Show all" will not select AnyVal, AnyRef or Any. Because the methods defined on these are available on pretty much everything, one rarely needs to see these methods.Because many times you might be interested in a particular aspect of an entity, you can also toggle each supertype individually. You can do so to display the methods on Any, for example, or you could look into what Function1 has to offer to List.The last option, Visibility, will toggle between displaying only public members and everything except private members.The last part of the right frame, as mentioned, contains all members of that entity. These are divided into type members and value members. A type member is a trait, a class or a type, and value members are everything else. For example, the object Regex contains this:Note that anything that shows up as a type member of anything but a package will not be displayed on the left frame, even though you can display it on the right frame by clicking on a link to it.Value members are actually divided in three separate sections: abstract value members, concrete value members and deprecated value members. These are shown in that precise order, so that one can easily see all members that must be implemented to make a concrete class, and don't get the screen polluted by methods they shouldn't be using -- deprecated methods -- when browsing.Let's look at some important points of value member definitions. The snapshot below was taken from a List with members filtered by "map":By default, only a member's definition and the first sentence of its description are shown, like method groupBy above. Clicking on either the small arrow on the left or on the definition itself will show the full information for that member, as seen in the two definitions for map.Since Scala supports method overload, methods can have multiple definitions. In this particular case, however, the first definition is not a real one -- this is indicated by the [use case] tag. It is important to understand what use cases are, for two reasons: first, they represent the most common way to use the method, and, second, they are lies. Well-meaning lies, but lies.Compare the definition of the two map methods shown. Clearly, the second definition has a lot going on, whereas the first definition is pretty clear: on a List[A] (see definition for List), the map method takes a function that converts an A into a B, and returns a List[B].Though that definition works very fine for List, the map method is not defined on List, but much  higher on the hierarchy. And what works for List won't work for a BitSet, for example: since a BitSet is a Set[Int], if you map those Int into String, you won't be able to return a BitSet! After all, a BitSet  cannot be a Set[String]. The same thing happens in other cases: a WrappedString is a Seq[Char], a Map[A, B] is a Iterable[Tuple2[A, B]] (aka Iterable[(A, B)]), etc. In any of these cases, a map definition like in the use case won't work.So the actual definition of map is the second one, which can handle all of these cases. If you need precise information about map -- for example, if you are extended Scala collections -- you can look it up. On the other hand, if you just want to know how a method is used, the use case should be much easier to understand.Most of the remaining information is pretty obvious: a description follows, and then various attributes describing how parameters are supposed to be used, what the return type is, etc.The final interesting thing here is the Definition Classes shown below each method. This only appears when a method has been inherited from elsewhere, and it indicates both where it was originally declared (which might have been as abstract), and all places where it was overridden, ie, the implementation has been changed.And this concludes the tutorial on using the Scala API documentation, as well as the docs for any other library written in Scala. Looking back, it is much longer (and took much more time to write) than I first thought. Yet, rest assured that using ScalaDoc becomes second nature very fast! Daniel Sobral tag:blogger.com,1999:blog-6373963829340632529.post-2311978234863327748 Tue, 27 Dec 2011 18:27:00 +0000 http://scala-enterprise.blogspot.com/2012/01/scala-with-cdi-dependency-injection.html “Sometimes”, Scala creates public final methods, although the .scala source defines no public final method at all. There are two things that CDI doesn’t like (which Scala “sometimes” generates): 1. public final methods2. public fields To investigate and reproduce these problems I created a scala-cdi project at GitHub. public final method: The Bug Referencing a parent field from a closure / inner class triggers this behavior: @RequestScoped @Named class IndexBean { private lazy val log = LoggerFactory.getLogger(classOf[IndexBean]) def testExecutor() = { val executor = Executors.newFixedThreadPool(4); executor.submit(new Runnable() { override def run(): Unit = log.debug("Executor is running") }) } } Compiles to: $ javap -p IndexBean Compiled from "IndexBean.scala" public class com.soluvas.scalacdi.IndexBean extends java.lang.Object implements scala.ScalaObject{ private org.slf4j.Logger com$soluvas$scalacdi$IndexBean$$log; ... public final org.slf4j.Logger com$soluvas$scalacdi$IndexBean$$log(); Deploying this app in Weld will throw: org.jboss.weld.exceptions.UnproxyableResolutionException: WELD-001437 Normal scoped bean class com.soluvas.scalacdi.IndexBean is not proxyable because the type is final or it contains a final method public final org.slf4j.Logger com.soluvas.scalacdi.IndexBean.com$soluvas$scalacdi$IndexBean$$log() - Managed Bean [class com.soluvas.scalacdi.IndexBean] with qualifiers [@Any @Default @Named]. at org.jboss.weld.util.Proxies.getUnproxyableClassException(Proxies.java:225) at org.jboss.weld.util.Proxies.getUnproxyableTypeException(Proxies.java:178) at org.jboss.weld.util.Proxies.getUnproxyableTypesExceptionInt(Proxies.java:193) at org.jboss.weld.util.Proxies.getUnproxyableTypesException(Proxies.java:167) at org.jboss.weld.bootstrap.Validator.validateBean(Validator.java:110) public final method: Workaround Create a final local variable to hold the parent instance’s value: def testExecutor() = { val executor = Executors.newFixedThreadPool(4); // this avoids 'log' becoming 'final' like: // private org.slf4j.Logger com$soluvas$scalacdi$IndexBean$$log; // public final org.slf4j.Logger com$soluvas$scalacdi$IndexBean$$log(); val log = this.log; executor.submit(new Runnable() { override def run(): Unit = log.debug("Executor is running") }) } Which now compiles to: $ javap -p IndexBean Compiled from "IndexBean.scala" public class com.soluvas.scalacdi.IndexBean extends java.lang.Object implements scala.ScalaObject{ private org.slf4j.Logger log; private org.slf4j.Logger log(); public field I’m not able to reproduce this yet... Tip: To learn more about Scala programming, I recommend Programming in Scala: A Comprehensive Step-by-Step Guide, 2nd Edition. Hendy Irawan tag:blogger.com,1999:blog-733023572967116656.post-6045521817017971610 Sun, 22 Jan 2012 15:17:00 +0000 http://feedproxy.google.com/~r/blogspot/vnby/~3/bqOoOtnSpfo/javascript-and-scala-good-parts-and-bad.html I've just finished reading "JavaScript: The Good Parts" by Douglas Crockford. It's a fantastic book, mostly because it's incredibly concise, elaborating only the details that experienced programmers should need to understand the true form of JavaScript. If you do ANY JavaScript programming and you haven't read it, I suggest you go out and get it straight away, and don't write a single line more of buggy JS code until you do. What is 'this'? Early on in the book, Crockford highlights one of JavaScript's oddest and most dangerous quirks: the late binding of 'this'. Basically, whenever you call a function, the value of 'this' within the function is determined by HOW you called the function! To demonstrate: If object 'a' has a function called 'run()' and you invoke it like this: a.run(); then the value of 'this' within 'run()' will be 'a'. JavaScript is a functional language, so functions can be passed around as values. If you instead invoked the function above using only a reference to the function value, like this: var f = a.run; f(); then the value of 'this' within 'run()' will be... the global variable pool! As you can imagine, that can lead to some pretty nasty and hard to track bugs. Functional Limitations  If you're a fan of functional programming, you might have tweaked straight away that this could place limits on the usefulness of functions as first class objects, and specifically higher-order functions (i.e. functions that take other functions in their parameters). Here's an example of an object that doesn't work with higher-order functions: var object1 = { total: 0, add: function(numbers) { var i; for (i = 0; i < numbers.length; i++) { this.total += numbers[i] } return this.total; } }; var valueOf = function (f, p1) { return f(p1); } var numbers = [1, 2, 3, 4]; document.writeln(object1.add(numbers) + " / " + valueOf(object1.add, numbers)); // outputs: 10 / NaN Obviously the reason this quirk causes confusion is because JavaScript has borrowed a keyword from other languages but uses it to mean something subtly different. Most OO languages use 'this' to represent a pointer to an object in which the function seemingly resides. Importantly, in OO/functional languages, when a function is used as a value, it takes with it a closure around 'this' that is used when invoking it. In JavaScript, however, the 'this' pointer just refers to the object on which the function was called, or if there was no object, just to the global variable pool. This Naughtiness Explained There is a reason for this weirdness. Because JavaScript is classless, the function doesn't actually belong to the object in which it resides. In fact, it's not hard to imagine situations where JavaScript's behaviour is what you'd expect. If I took a function from one object and placed it in another object (which I can do, because the function is also a value), I actually would expect 'this' to refer to the new object when I invoked it, and JavaScript provides just that capability: var b = {}; b.run = a.run; b.run(); // 'this' will refer to 'b' Once you understand where JavaScript is coming from a bit better, it's not too hard to see the solution to this problem. 'this' doesn't provide a closure around the context where your function was defined, so if you want a closure around the context where your function was defined, then give your function a closure around that context, rather than assuming that 'this' will be the same context whenever the function is invoked. To demonstrate this by correcting the example above: var object2 = (function () { var that = {}; that.total = 0; that.add = function(numbers) { var i; for (i = 0; i < numbers.length; i++) { that.total += numbers[i] } return that.total; }; return that; })(); document.writeln(object2.add(numbers) + " / " + valueOf(object2.add, numbers)); // outputs: 10 / 20 Scala: The Bad Parts?  Does any of this have anything to do with Scala? Well, in the details, no, but in the general sense there is a very important approach in Crockford's book. His suggested solution to the problem above is simple: don't use 'this' in JavaScript and don't use its accompanying feature, 'new'. In fact, he suggests not using LOTS of features of JavaScript. He dedicates 14 pages of appendix to listing them. Crockford also spends a very un-indulgent two pages discussing the modern phenomenon of "feature-driven design", both in products and programming languages, explaining how "Features that offer value to a minority of users impose a cost on all users" and concluding the book with this pearler: "It would be nice if products and programming languages were designed to have only good parts." It was those two lines that caused me to reflect on Scala. I started asking myself questions like: Are there too many features in Scala? Are there parts that aren't "good parts"? Are there features that very few people make use of but that cost everyone because of the complexity they add? From my own experience, the answer to all three of these is "yes". Crockford explains that we all crave simplicity and that, when we aren't given it, we make it for ourselves by creating our own feature subset, and I realised that I've done this to some extent in the way I use Scala. So finally I began wondering how long it will be until someone publishes "Scala: The Good Parts", complete with appendices listing all the features that you should steer clear of for everyone's sake. What confusing or dangerous feature of Scala do you reckon will be at the top of the list? Want to learn more? From Amazon... From Book Depository... Graham Lea tag:blogger.com,1999:blog-7317245822288637185.post-2010862824295619276 Sat, 21 Jan 2012 03:26:00 +0000 http://villane.wordpress.com/2012/01/17/mixfix-operators-parser-combinators-part-2/ In the previous post I introduced the notion of mixfix operators. In this post we will look at them more closely, in the context of an actual grammar. In the next part we will implement the parser for this grammar, look at performance issues and try to fix them with packrat parsers. We will implement a simple language that consists of boolean algebra and integer arithmetic expressions. The grammar for the language looks like the following (we’re only considering tokens here and assume that a lexical parser has already identified literals, identifiers and delimiters in the text) statement   ::= expression | declaration declaration ::= variable ":=" expression expression  ::= ??? | value value       ::= literal | variable literal     ::= booleanLiteral | integerLiteral variable    ::= identifier What should the expression productions look like, though? In examples of parsers and grammars we can commonly find an arithmetic expression language described with concepts of ‘factor’ and ‘term’ to create a precedence relation between addition and multiplication: expression ::= (term "+")* term term       ::= (factor "*")* factor factor     ::= constant | variable                | "(" expression ")" This seems simple, but when we add more precedence rules, it can get quite complex, especially if we are writing a parser for a general purpose programming language instead of a simple expression language, and we also do semantic actions (create AST nodes) in the parser. This also makes the set of operators rather fixed: you might have to change several grammar productions to add a new operator with a new precedence level. I didn’t even try building Slang’s precedence rules into the grammar in this fashion. Mixfix parsers still make the precedence part of the grammar, but there is a layer of abstraction there: we describe operators and their precedence rules as a directed graph, where (groups of) operators are the nodes and precedences are the edges. Then we instantiate the grammar with that particular precedence graph. Before getting to the precedence rules in the language we are about to create, lets look at the operators it will have. In the list below, _ means a hole in the expression that can contain any other expression that “binds tighter” than the operator in question. In the case where the hole is closed on both left and right, it can contain any expression at all. Only a pair of parentheses forms a closed operator in this language. ( _ ) – parentheses _ + _ – addition _ - _ – subtraction   - _ – negation _ * _ – multiplication _ / _ – division _ ^ _ – exponent _ mod _ – modulo/remainder _ = _ – equality test _ ≠ _ – inequality test _ < _ – less than _ > _ – greater than _ & _ – conjunction _ | _ – disjunction   ! _ – logical not This doesn’t include many common operators in real programming languages, but it is enough to demonstrate some interesting aspects of mixfix operators and using a DAG to describe their precedence relations. I used mod instead of % to show that operators don’t have to be symbols. Before defining the precedence rules, lets look at some sample expressions and how we want them to be interpreted, mostly sticking with existing well known precedence rules, such as those in C, Java or Scala, but occasionally deviating from them: a + b * c      = a + (b * c) a < b & b < c  = (a < b) & (b < c) -5 ^ 6         = (-5) ^ 6 a & !b | c     = (a & (!b)) | c 5 < 2 ≠ 6 > 3  = (5 < 2) ≠ (6 > 3) 1 < x & !x > 5 = (1 < x) & !(x > 5) I think that’s enough examples for now. Lets try to describe the rules behind these somewhat intuitive expectations as a precedence graph. First, we’ll put the operators into groups where all operators in one group bind just as tightly as the others in the same group. For example 1 + 2 - 3 will be (1 + 2) - 3 and 1 - 2 + 3 will be (1 - 2) + 3 parentheses   : () negation      : - (prefix) exponent      : ^ multiplication: *, /, mod addition      : +, - comparison    : <, > equality      : =, ≠ not           : ! (prefix) and           : & or            : | Negation (prefix -) is in it’s own group so that we can do: -2 + 1. If it was in the same group with infix - and +, then it couldn’t appear next to them without parentheses because prefix operators are treated as right-associative, but most infix operators, such as - and + are left-associative. And we can’t mix left-associative and right-associative operators of the same precedence level! Why? Take the expression 1 + 2 - 3 If + and - are left-associatve, it means (1 + 2) - 3. If - is right-associative instead, then both (1 + 2) - 3 and 1 + (2 - 3) would be right! We could read the list of operator groups above as an order of precedence, where the first group (parentheses) binds tightest and the last group (or) binds least tight. This would be mostly compatible with many programming languages and we would have a good enough set of precedence rules right there. However, as mentioned earlier, Danielsson’s mixfix grammar scheme describes precedence relations as a directed graph. Each of the groups above is a node in the graph, and a directed edge from one node to another a -> b means: b binds tighter than a. So lets describe these relations as a graph instead — it will be in reverse order compared to the above list where we started from the most tightly binding: or -> and, not, equality, comparison, parentheses and -> not, equality, comparison, parentheses not -> equality, comparison, parentheses equality -> comparison, addition, multiplication, exponent, negation, parentheses comparison -> addition, multiplication, exponent, negation, parentheses addition -> multiplication, exponent, negation, parentheses multiplication -> exponent, negation, parentheses exponent -> negation, parentheses negation -> parentheses Notice that from each group we draw the edge not into a single group, but into all of the groups that bind tighter. This is because of the non-transitivity of precedence in this scheme: each pair of operator groups that is to have a precedence relation must have an edge between them in the graph. The advantage of this is that we don’t need to describe the precedence between operators that aren’t related at all. This is one of the motivations for using a directed graph to represent operator precedence. I hope that from the names of the operators it was clear that some of them will apply only to booleans and some only to integers. For example, the & operator isn’t defined as bitwise &, only as logical conjunction. Thus, assuming that our language is strongly typed, some of the operators can’t appear in the holes of some other operators in a correct program. A parser doesn’t do type checking of course, but with this mixfix grammar scheme, it does implicitly do precedence correctness checking. For example 4 + 5 & 6 + 4 is not precedence correct, as we didn’t define a precedence relation between addition and and. And due to the parser’s precedence checking, this expression will not even parse. If we had used a total precedence order instead, we would have + binding tighter than &. The expression would be interpreted as (4 + 5) & (6 + 4) but would probably yield a type error as & works on booleans, but + works on integers. We could write (4 + 5) & (6 + 4) ourselves and that would also parse, because we made the precedence explicit. Well, actually parentheses follow the same rules: remember that in our graph, () bind tighter than everything. The fact that the parser only produces precedence correct expressions can be both a blessing and a curse. On one hand, this allows us to view some unrelated groups of operators almost as sublanguages. In our case, boolean algebra and integer arithmetic. This might be good for implementing internal DSLs in the presence of extremely flexible user-defined mixfix operators. We could allow users to extend our precedence graph or even replace it completely with their own. If a DSL has boolean logic in it, but no arithmetic, it might have precedence relations to logical operators, but not to arithmetic operators. This would preclude arithmetic operators from appearing in the DSL without being surrounded by parentheses. Or the DSL could even disallow parentheses. Implementing this much flexibility in a host language is complicated, though. For example, the parser would have to know about any custom mixfix grammars defined in imported modules. On the other hand, this puts some correctness checks at the wrong level. Arguably, a parser should only validate the syntax of a program and nothing else. If a simple mistake such as using a wrong operator (equal to calling a non-existing method in some languages) would prevent the whole program from being parsed, it would also prevent the compiler from doing other interesting and useful things, or reporting better error messages. So maybe this grammar scheme isn’t ideal for a general purpose programming language. I am sticking with it in Slang for now, because the scheme is relatively simple and works for me at least as long as I’m the only user of Slang :) And perhaps there are workarounds that would allow a precedence-incorrect expression to be accepted by the parser still. But I don’t have immediate plans to allow a wide variety of user-defined mixfix operators or operator precedence. Anyway, for our simple language, I think this scheme works well enough as long as we don’t care whether it is the parser or the type checker that reports the errors in incorrect programs. There aren’t any useful direct precedence relations between boolean algebra operators and arithmetic operators here. Only by having equality, comparison or parentheses between them, can we put them in the same expression. Lets look at one of the consequences of our rules more closely. Many languages, including Java and C, would put most prefix (unary) operators such as ! and - at the same level of precedence, binding tighter than all infix (binary) operators. In Java, !6 == 5 is a type error because the operator ! is bound to 6, not to 6 == 5, and ! isn’t defined on integers. In our language, it isn’t necessary to have ! at the same level as -, though. Since there is no (precedence) relation between logical and arithmetic operators, !6 + 5 will not parse. But ! does have a relation to comparison and equality tests (they bind tighter), so you can write !6 = 5 and it will mean !(6 = 5). The precedence rules that have = binding tighter than boolean operators is based on the assumption that booleans are rarely compared to each other, but multiple comparisons of other types of values are often used in disjunctions, conjunctions and complements. To get back to the question in the beginning of the post, what would the expression production in the grammar look like instead of expression ::= ??? | value? The short answer is that we replace ??? with the mixfix grammar scheme instantiated with our particular precedence graph. The long answer would probably take an entire blog post by itself. You can read more about this scheme in the Agda paper, or look at the source code of my mixfix library. The scheme looks somewhat like the parser combinators in the following pseudo-code (~ means sequential composition): value = variable | literal expression = mixfixGrammar(precedenceGraph) | value mixfixGrammar(graph) = { // graph - the precedence graph // g - an operator group, node in the graph // op - an operator in a group ⋁(parsers) = // returns the result of the first parser in the list to succeed opsLeft(g) = // all left-associative infix operators in g opsRight(g) = // all right-associative infix operators in g opsNon(g) = // all non-associative infix operators in g opsClosed(g) = // all closed operators in g opsPre(g) = // all prefix operators in g opsPost(g) = // all postfix operators in g operator(op) = if (op.internalArity == 0) op.namePart1 if (op.internalArity == 1) op.namePart1 ~ expression ~ op.namePart2 // expression is an recursive reference back to the "outer" production // these are the internal "holes" that can take any expression group(g) = closed(g) | non(g) | left(g) | right(g) // any ops in this group closed(g) = ⋁{ opsClosed(g) map operator } // closed ops non(g) = ↑(g) ~ ⋁{ opsNon(g) map operator } ~ ↑(g) // non-associative ops left(g) = (left(g) | ↑(g)) // left-associative ops ~ ( ⋁{ opsPost(g) map operator } | ⋁{ opsLeft(g) map operator } ~ ↑(g) ) right(g) = ( ⋁{ opsPre(g) map operator } // right-associative ops | ↑(g) ~ ⋁{ opsRight(g) map operator } ) ~ (right(g) | ↑(g)) ↑(g) = ⋁{ graph.groupsTighterThan(g) map group } // every group that binds tighter than g | value // or the tightest "group" of values return ⋁{ graph.nodes map group } } If you don’t understand this right now, no big deal — it’s late enough that I couldn’t come up with a better representation of the actual code that would fit in this post. And if you are not familiar with parser combinators I would recommend reading Daniel Spiewak’s post on the subject, at least before continuing to the next part of this series. If you notice, the value and expression productions are referenced inside the mixfixGrammar. This is no good if the mixfix library is to be a separate module, so I actually implemented that by introducing a pseudo operator group that has a custom parser. This pseudo-group is then added to the precedence graph along with edges from every other group into that “really tight” group. This concludes part 2. In the next part we will forget this pseudo-code and use Scala’s parser combinators and my mixfix library to implement an actual parser for the language, and maybe an AST and an interpreter as well. Thanks to Miles Sabin and Daniel Spiewak for reviewing drafts for this series of posts. Erkki Lindpere http://villane.wordpress.com/?p=216 http://villane.wordpress.com/2012/01/16/mixfix-operators-parser-combinators-part-1/ Until recently, Slang’s parser really sucked. It was a quick hack implemented with Scala’s parser combinator library. Nothing really wrong about that in particular, but there was a gaping hole in the grammar: no operator precedence. So to get an expression like a + b * c to mean a + (b * c) I had to add the parentheses myself. In fact, there were even more problems — some things that should have been left-associative were right-associative. This resulted in very hairy test code, with lots of parentheses everywhere. Although I think parsers are cool, I am actually not very good at writing one for a complex grammar. I feel that I just know too little about the theory behind them or how to put it to practical use. I’ve used parser combinators before and think they are probably the easiest way for newbies like me to implement parsers, so that’s what I used. The use of symbolic names in the library might be scary the first time, but actually I think parsing is one of the few contexts where use of lots of symbols and extremeley concise code is desirable. It allows one to put a lot of code on a few lines, and when you are looking at or writing a parser, you want to see many productions of the grammar at the same time to understand what is going on. At least I do. For Slang, I implemented something minimal that could parse the language. I had no idea how to solve operator precedence well with parser combinators, and I didn’t want to spend a lot of time studying parsers, because the next compiler phases seemed more interesting at first. But getting the parser right is important for actually using the language because it’s the first thing that processes the code and reports errors. A parser that only kind of works can be very annoying. Thankfully Miles Sabin suggested that I should look into mixfix operator parsers, and I did. I don’t know exactly where the word mixfix comes from, so I’m assuming it means mixed fixity — operators can be prefix, infix, postfix or closed. Here are some samples: prefix : -a infix : a + b postfix: n! closed : (a) Of course, most languages have operators with all of these fixities. The term mixfix actually refers to something more flexible than that — a mixfix operator can be seen as a sequence of alternating name parts and “holes in the expression”. A hole is where the operator’s arguments go. _ + _ has two holes and one name part + (and is infix) if _ then _ else _ has three name parts if, then, else and three holes (and is prefix) In the mixfix viewpoint, many syntactic constructs might be seen as operators that can have precedence in relation to others, and this concept of many name parts can make it easier to let users define their own operators in a more flexible way than just a single prefix or infix word (as is allowed by Scala). I think this would be a really nice way of creating internal DSL-s. In Slang, like in Scala, most operators are really methods. Slang doesn’t allow user-defined fixity or precedence for methods yet (or even multiple argument lists), but I may add this feature one day. There are existing languages that support mixfix operators, such as Agda, Maude and BitC. To my knowledge, all these languages assign numeric precedence values to operators, and no language currently uses the exact scheme we will look at, although it was proposed for Agda. Mixfix operators can be implemented in many ways, but one of the first things I found was the paper Parsing Mixfix Operators by Anders Danielsson and Ulf Norell that was a great help to me. I was able to implement the grammar scheme described in that paper on top of Scala’s parser combinators and patch that into Slang’s existing parser with minimal changes to existing productions. The characteristics of the grammar scheme described in Danielsson’s paper seemed like a good enough fit for what I wanted for Slang: operator name parts and holes alternate — there can’t be two subsequent name parts or two subsequent holes if _ then _ else _ is ok, if _ _ else _ is not operator precedence is described as a directed acyclic graph (DAG), not as a total or partial ordering. You only have to describe the precedence relations where they make sense (more about this in the next post) a directed edge '+' -> '*' means “* binds tighter than -” operator precedence is not transitive '=' -> '+' and '&' -> '=' does not mean “+ binds tighter than &” prefix operators are treated as right-associative !!a = !(!(a)) postfix operators are treated as left-associative n!! = ((n)!)! left-associative and right-associative operators of the same precedence can’t appear next to each other assuming +: is a right-associative +, a + b +: c would not be allowed parses are precedence correct implementation using left-recursion is possible, for example when using Scala’s Packrat parsers There weren’t any restrictions I couldn’t live with (in fact, we could relax some of the above requirements and the scheme would still work for some grammars), so I decided to implement this grammar scheme for Slang, pretty much as described in the paper. Although I didn’t really grok all of the Agda code samples, the principles were easily understandable. I implemented it as a separate library (available on GitHub) that builds on top of the existing Scala parser combinator library. It might even be somewhat usable in it’s current state, but needs improvement. In the next post we’ll look at how to define a grammar for an arithmetic and boolean algebra language using mixfix operators. In the third part, we will actually implement the parser for the grammar, look at performance issues and whether we can solve them with packrat parsers. Thanks to Miles Sabin and Daniel Spiewak for reviewing drafts for this series of posts. Erkki Lindpere http://villane.wordpress.com/?p=213 http://debasishg.blogspot.com/2012/01/event-sourcing-akka-fsms-and-functional.html I blogged on Event Sourcing and functional domain models earlier. In this post I would like to share more of my thoughts on the same subject and how with a higher level of abstraction you can make your domain aggregate boundary more resilient and decoupled from external references.When we talk about a domain model, the Aggregate takes the centerstage. An aggregate is a core abstraction that represents the time invariant part of the domain. It's an embodiment of all states that the aggregate can be in throughout its lifecycle in the system. So, it's extremely important that we take every pain to distil the domain model and protect the aggregate from all unwanted external references. Maybe an example will make it clearer.Keeping the Aggregate pureConsider a Trade model as the aggregate. By Trade, I mean a security trade that takes place in the stock exchange where counterparties exchange securities and currencies for settlement. If you're a regular reader of my blog, you must be aware of this, since this is almost exclusively the domain that I talk of in my blog posts.A trade can be in various states like newly entered, value date added, enriched with tax and fee information, net trade value computed etc. In a trading application, as a trade passes through the processing pipeline, it moves from one state to another. The final state represents the complete Trade object which is ready to be settled between the counterparties. In the traditional model of processing we have the final snapshot of the aggregate - what we don't have is the audit log of the actual state transitions that happened in response to the events. With event sourcing we record the state transitions as a pipeline of events which can be replayed any time to rollback or roll-forward to any state of our choice. Event sourcing is coming up as one of the potent ways to model a system and there are lots of blog posts being written to discuss about the various architectural strategies to implement an event sourced application. That's ok. But whose responsibility is it to manage these state transitions and record the timeline of changes ? It's definitely not the responsibility of the aggregate. The aggregate is supposed to be a pure abstraction. We must design it as an immutable object that can respond to events and transform itself into the new state. In fact the aggregate implementation should not be aware of whether it's serving an event sourced architecture or not.There are various ways you can model the states of an aggregate. One option that's frequently used involves algebraic data types. Model the various states as a sum type of products. In Scala we do this as case classes ..sealed abstract class Trade { def account: Account def instrument: Instrument //..}case class NewTrade(..) extends Trade { //..}case class EnrichedTrade(..) extends Trade { //..}Another option may be to have one data type to model the Trade and model states as immutable enumerations with changes being effected on the aggregate as functional updates. No in place mutation, but use functional data structures like zippers or type lenses to create the transformed object in the new state. Here's an example where we create an enriched trade out of a newly created one ..// closure that enriches a tradeval enrichTrade: Trade => Trade = {trade => val taxes = for { taxFeeIds <- forTrade // get the tax/fee ids for a trade taxFeeValues <- taxFeeCalculate // calculate tax fee values } yield(taxFeeIds ° taxFeeValues) val t = taxFeeLens.set(trade, taxes(trade)) netAmountLens.set(t, t.taxFees.map(_.foldl(principal(t))((a, b) => a + b._2)))}But then we come back to the same question - if the aggregate is distilled to model the core domain, who handles the events ? Someone needs to model the event changes, effect the state transitions and take the aggregate from one state to the next.Enter Finite State MachinesIn one of my projects I used the domain service layer to do this. The domain logic for effecting the changes lies with the aggregate, but they are invoked from the domain service in response to events when the aggregate reaches specific states. In other words I model the domain service as a finite state machine that manages the lifecycle of the aggregate.In our example a Trading Service can be modeled as an FSM that controls the lifecycle of a Trade. As the following ..import TradeModel._class TradeLifecycle(trade: Trade, timeout: Duration, log: Option[EventLog]) extends Actor with FSM[TradeState, Trade] { import FSM._ startWith(Created, trade) when(Created) { case Event(e@AddValueDate, data) => log.map(_.appendAsync(data.refNo, Created, Some(data), e)) val trd = addValueDate(data) notifyListeners(trd) goto(ValueDateAdded) using trd forMax(timeout) } when(ValueDateAdded) { case Event(StateTimeout, _) => stay case Event(e@EnrichTrade, data) => log.map(_.appendAsync(data.refNo, ValueDateAdded, None, e)) val trd = enrichTrade(data) notifyListeners(trd) goto(Enriched) using trd forMax(timeout) } when(Enriched) { case Event(StateTimeout, _) => stay case Event(e@SendOutContractNote, data) => log.map(_.appendAsync(data.refNo, Enriched, None, e)) sender ! data stop } initialize}The snippet above contains a lot of other details which I did not have time to prune. It's actually part of the implementation of an event sourced trading application that uses asynchronous messaging (actors) as the backbone for event logging and reaching out to multiple consumers based on the CQRS paradigm.Note that the FSM model above makes it very explicit about the states that the Trade model can reach and the events that it handles while in each of these states. Also we can use this FSM technique to log events (for event sourcing), notify listeners about the events (CQRS) in a very much declarative manner as implemented above.Let me know in the comments what are your views on this FSM approach towards handling state transitions in domain models. I think it helps keep aggregates pure and helps design domain services that focus on serving specific aggregate roots.I will be talking about similar stuff, Akka actor based event sourcing implementations and functional domain models in PhillyETE 2012. Please drop by if this interests you. Debasish Ghosh tag:blogger.com,1999:blog-22587889.post-7711822270811502612 Sun, 15 Jan 2012 14:54:00 +0000 http://debasishg.blogspot.com/2011/09/non-blocking-composition-using-redis.html scala-redis now supports pooling of Redis clients. Using RedisClientPool you can do some cool stuff in non blocking mode and get an improved throughput for your application. Suppose you have a bunch of operations that you can theoretically execute in parallel, maybe a few disjoint list operations and a few operations on key/values .. like the following snippets ..val clients = new RedisClientPool("localhost", 6379)// left push to a listdef lp(msgs: List[String]) = { clients.withClient {client => { msgs.foreach(client.lpush("list-l", _)) client.llen("list-l") }}}// right push to another listdef rp(msgs: List[String]) = { clients.withClient {client => { msgs.foreach(client.rpush("list-r", _)) client.llen("list-r") }}}// key/set operationsdef set(msgs: List[String]) = { clients.withClient {client => { var i = 0 msgs.foreach { v => client.set("key-%d".format(i), v) i += 1 } Some(1000) // some dummy }}}Redis, being single threaded, you can use client pooling to allocate multiple clients and fork these operations concurrently .. Here's a snippet that does these operations asynchronously using Scala futures ..// generate some arbitrary valuesval l = (0 until 5000).map(_.toString).toList// prepare the list of functions to invokeval fns = List[List[String] => Option[Int]](lp, rp, set)// schedule the futuresval tasks = fns map (fn => scala.actors.Futures.future { fn(l) })// wait for resultsval results = tasks map (future => future.apply())And while we are on this topic of using futures for non blocking redis operations, Twitter has a cool library finagle that offers lots of cool composition stuff on Futures and other non blocking RPC mechanisms. Over the weekend I used some of them to implement scatter/gather algorithms over Redis. I am not going into the details of what I did, but here's a sample dummy example of stuffs you can do with RedisConnectionPool and Future implementation of Finagle ..The essential idea is to be able to compose futures and write non blocking code all the way down. This is made possible through monadic non-blocking map and flatMap operations and a host of other utility functions that use them. Here's an example ..def collect[A](fs: Seq[Future[A]]): Future[Seq[A]] = { //..It uses flatMap and map to collect the results from the given list of futures into a new future of Seq[A].Let's have a look at a specific example where we push a number of elements into 100 lists concurrently using a pool of futures, backed by ExecutorService. This is the scatter phase of the algorithm. The function listPush actually does the push using a RedisConnectionPool and each of these operations is done within a Future. FuturePool gives you a Future where you can specify timeouts and exception handlers using Scala closures. Note how we use the combinator collect for concurrent composition of the futures. The resulting future that collect returns will be complete when all the underlying futures have completed.After the scatter phase we prepare for the gather phase by pipelining the future computation using flatMap. Unlike collect, flatMap is a combinator for sequential composition. In the following snippet, once allPushes completes, the result pipelines into the following closure that generates another Future. The whole operation completes only when we have both the futures completed. Or we have an exception in either of them.For more details on how to use these combinators on Future abstractions, have a look at the tutorial that the Twitter guys published recently.implicit val timer = new JavaTimer// set up Executorsval futures = FuturePool(Executors.newFixedThreadPool(8))// abstracting the flow with futureprivate[this] def flow[A](noOfRecipients: Int, opsPerClient: Int, fn: (Int, String) => A) = { val fs = (1 to noOfRecipients) map {i => futures { fn(opsPerClient, "list_" + i) }.within(40.seconds) handle { case _: TimeoutException => null.asInstanceOf[A] } } Future.collect(fs)}// scatter across clients and gather them to do a sumdef scatterGatherWithList(opsPerClient: Int)(implicit clients: RedisClientPool) = { // scatter val allPushes: Future[Seq[String]] = flow(100, opsPerClient, listPush) val allSum = allPushes flatMap {result => // gather val allPops: Future[Seq[Long]] = flow(100, opsPerClient, listPop) allPops map {members => members.sum} } allSum.apply}For the complete example implementations of these patterns like scatter/gather using Redis, have a look at the github repo for scala-redis. Debasish Ghosh tag:blogger.com,1999:blog-22587889.post-1267847223414228921 Tue, 27 Sep 2011 05:13:00 +0000 http://dcsobral.blogspot.com/2012/01/adding-methods-to-scala.html I don't like getting much involved in these Scala flame wars, but this recent article left me a bit irked. At some point, the following statement is made:"it is impossible to insert a new method that behaves like a normal collection method. "So, for the record, that is just not true. Here's an implementation for the filterMap method:import scala.collection._import generic.CanBuildFromimport mutable.Builder class FilterMap[A, C <: Seq[A]](xs: C with SeqLike[A, C]) { def filterMap[B, That](f: A => Option[B]) (implicit cbf: CanBuildFrom[C, B, That]): That = { val builder: Builder[B, That] = cbf() xs foreach { x => val y = f(x); if (y.nonEmpty) builder += y.get } builder.result() } } implicit def toFilterMap[A, C <: Seq[A]](xs: C with SeqLike[A, C]): FilterMap[A, C] = new FilterMap[A, C](xs)Is this what the author wanted? No. He wanted too add a method that behaved like a normal collection method to something that isn't a collection. This is so crazy that, not surprisingly, people are misunderstanding him.Now, one may come up and say that Scala does do that (add methods to stuff that are not collection), with String and Array. Yes, it does, and it does so by creating a completely new class with all these methods for each of them. Rest assured that if I create a completely new class for each one, I can add filterMap to String and Array too. Daniel Sobral tag:blogger.com,1999:blog-6373963829340632529.post-2495407794211942342 Mon, 09 Jan 2012 23:50:00 +0000 http://feedproxy.google.com/~r/blogspot/vnby/~3/lLbLkt0mTQc/updates-to-scalaspringhibernatemaven.html One of the projects I maintain is a public domain code base on GitHub called Scala-Spring-Hibernate-Maven-Webapp. The repository contains source code for kickstarting your own webapp project using the latest versions of Scala, Spring Web, Hibernate and Maven. Project Updates I've been committing some major changes over the last couple of weeks, including: Upgrading to Scala 2.9.1, Spring 3.1.0 and Hibernate 4.0.0  Adding to the existing REST-ful Create and Retrive examples some Update and Delete operations  Adding server-side form validation using JSR-303 annotations with Spring Web MVC  Creating examples of automated web testing using Selenium WebDriver and the PageObjects pattern  If you're about to start your own project with these technologies, or are just keen to see how they all work together, you can get your own copy of the source code from here: https://github.com/GrahamLea/scala-spring-hibernate-maven-webapp Resolved Issues I encountered a couple of time-consuming issues during the upgrades to the latest versions and I think it would be worth sharing how they were resolved in order to save some time for others googling for solutions to the same problems. Spring Schema SAXParseException After upgrading the versions of all the Spring Schemas in my Spring XML files, I started getting the following error while trying to start up the webapp: org.xml.sax.SAXParseException: cos-all-limited.1.2: An ''all'' model group must appear in a particle with '{'min occurs'}'='{'max occurs'}'=1, and that particle must be part of a pair which constitutes the '{'content type'}' of a complex type definition. At first this appears to be a bug in the Spring schema, but a bit more investigation revealed that it is, in fact, a bug in an old version of the Xerces XML parser library. In my case, an old version of the library was being pulled in through commons-dbcp. The solution I took was to explicitly add a dependency on the latest version of Xerces: xerces xercesImpl 2.9.1 runtime Hibernate Function Not Supported After upgrading Hibernate to 4.0.0, I started getting this error message whenever I tried to execute a query: org.hibernate.exception.GenericJDBCException: This function is not supported Caused by: java.sql.SQLException: This function is not supported I don't remember whether HSQLDB appeared in the stack trace or not, but the solution to this was to upgrade the version of HSQLDB I was using from 1.8.0.10 to 2.2.6. If you get the same error and you're not using HSQLDB, I would suggest considering an upgrade of your JDBC driver or maybe even your database server. "No Session found for current thread"  Also after upgrading to Spring 3.1.0 and Hibernate 4.0.0, and after changing all my Hibernate 3 Spring beans to the corresponding Hibernate 4 versions, I started getting the old classic "No Session found for current thread" error when trying to view any page with a transaction. I thought this was very odd, because the traditional solution to this has always been to make sure you have an OpenSessionInViewInterceptor, but I already had one, defined like this: By pure chance, I'd seen a Spring documentation page earlier the same day where I'd noticed an alternative way of declaring interceptors using the 'mvc' namespace: Replacing my old DefaultAnnotationHandlerMapping definition with the one above got my OpenSessionInViewInterceptor working again and solved the "No Session found for current thread". No Appenders for Log4J Finally, this one is a bit silly, but I spent a good half hour on it without finding any good help on the web so I thought it was worth documenting. At some point I started getting this error out of Log4J every time I started my webapp: log4j:WARN No appenders could be found for logger After all kinds of googling, experiments with winding back dependency upgrades and investigations into ClassLoaders, I eventually noticed that I just had a typo in the Log4J configuration file: og4j.rootCategory=INFO,Console Notice the 'l' missing at the start of that line? Ouch. So if you're getting this error message about no appenders and you think your log4j config is all set up properly, check whether the config for your root category is correct before investing too much time in breakpoints inside Log4J classes. Want to learn more? Here's some books you might find useful if you plan to go further with Spring, Hibernate, Scala or Maven: From Amazon From The Book Depository Spring in Action - Craig Walls & Ryan Breidenbach (Manning) Hibernate in Action - Gavin King & Christian Bauer (Manning) Spring Recipes - Gary Mak (Apress) Programming in Scala - Martin Odersky, Lex Spoon & Bill Venners (Artima) Maven - A Developer's Notebook - Vincent Massol & Timothy M. O'Brien (O'Reilly) Graham Lea tag:blogger.com,1999:blog-7317245822288637185.post-6966341080002235096 Mon, 09 Jan 2012 06:44:00 +0000 http://debasishg.blogspot.com/2012/01/learning-type-level-fixpoint-combinator.html I blogged on Mu, type level fixpoint combinator some time back. I discussed how Mu can be implemented in Scala and how you can use it to derive a generic model for catamorphism and some cool type level data structures. Recently I have been reading TAPL by Benjamin Pierce that gives a very thorough treatment of the theories and implementation semantics of types in a programming language. And Mu we meet again. Pierce does a very nice job of explaining how Mu does for types what Y does for values. In this post, I will discuss my understanding of Mu from a type theory point of view much of what TAPL explains. As we know, the collection of types in a programming language forms a category and any equation recursive in types can be converted to obtain an endofunctor on the same category. In an upcoming post I will discuss how the fixed point that we get from Mu translates to an isomoprhism in the diagram of categories.Let's have a look at the Mu constructor - the fixed point for type constructor. What does it mean ? Here's the ordinary fixed point combinator for functions (from values to values) ..Y f = f (Y f)and here's MuMu f = f (Mu f)Quite similar in structure to Y, the difference being that Mu operates on type constructors. Here f is a type constructor (one that takes a type as input and generates another type). List is the most commonly used type constructor. You give it a type Int and you get a concrete type ListInt.So, Mu takes a type constructor f and gives you a type T. This T is the fixed point of f, i.e. f T = T.Consider the following recursive definition of a List ..// nil takes no arguments and returns a List data typenil : 1 -> ListInt// cons takes 2 arguments and returns a List data typecons : (Int x ListInt) -> ListIntTaken together we would like to solve the following equation :a = Unit + Int x a     // ..... (1)Now this is recursive and can be unfolded infinitely as a = Unit + Int x (Unit + Int x a)  = Unit + Int x (Unit + Int x (Unit + Int x a))  = ...TAPL shows that this equation can be represented in the form of an infinite labeled tree and calls this infinite type regular. So, generally speaking, we have an equation of the form a = τ where1. if a does not occur in τ, then we have a finite solution which, in fact is τ2. if a occurs in τ, then we have an infinite solution represented by an infinite regular treeSo the above equation is of the form a = ... a ... or we can say a = F(a) where F is the type constructor. This highlights the recursion of types (not of values). Hence any solution to this equation will give us an object which will be the fixed point of the equation. We call this solution Mu a . F. Since Mu a . F is a solution to a = F(a), we have the following:Mu a . F = F {Mu a . F / a}, where the rhs indicates substitution of all free a's in F by Mu a . F.Here Mu is the fixed point combinator which takes the type constructor F and gives us a type, which is the fixed point of F. Using this idea, the above equation (1) has the solution ListInt, which is the fixed point type ..ListInt = Mu a . Unit + Int x aIn summary, we express recursive types using the fix point type constructor Mu and show that Mu generates the fixed point for the type constructor just like Y generates the same for functions on values. Debasish Ghosh tag:blogger.com,1999:blog-22587889.post-591560437586381904 Sat, 07 Jan 2012 20:13:00 +0000 http://blog.yuvimasory.com/2011/08/functional-programming-trivia-from.html By popular request, here are the questions and answers from the quizzo at Scalathon. I've formatted them so you can try the questions for yourself! The questions were written by Ben Karel, Randall Schulz, and yours truly. I put the final wording on all the questions, so any mess-ups are my fault alone.Round 1What language is most closely associated with the actors model of concurrency?Who wrote "Purely Functional Data Structures"?Place the following languages in chronological order, from oldest to newest: Lisp, Fortran, Cobol.Two of the three primary techniques of giving formal semantics to a programming language are operational and denotational semantics. What is the third of the trio?What term am I defining? "A tractable syntactic method for proving the absence of certain program behaviors by classifying phrases according to the kinds of values they compute."Round 2Can you have functional programming without static typing?Who invented LISP?What is the name of the type inference algorithm used by Haskell and ML?What is the more common name for Schönfinkelization?What language is CompCert, the formally verified C-compiler written in?Round 3Analogy: Types are to values, as kinds are to what?Some type systems have the feature that a type can depend upon a value. What is that feature called?Name the co-author of most of the original Lambda papers (his name is the longer one).According to Tony Hoare, this was "a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors." Name the language, which was (almost) based on the fully-typed call-by-value lambda calculus.Peter J. Landin described the SECD machine in 1963; what language was he defining?Round 4What is the difference between a total function and a partial function?Name the titles of two of the three original "lambda papers"?Which of these languages is Turing-complete: SQL, The Coq Specification Language, XSLT, XML, JSON, Prolog, Ant.What common higher-order function implements a catamorphism?Who quipped that "Syntactic sugar causes cancer of the semicolon."?Tie-break RoundThe quirky bird, thrush, and mockingbird are all names of closed lambda terms, also known as what?A paper called "Macaroni is better than spaghetti" was published in 1977 on efficient implementation of call stacks. Name the author, who also gave an OOPSLA speech starting only with words of one syllable, and is known for his work on Scheme and Common Lisp, among many other languages.Peter Landin defined an operator to capture continuations; it shares a name with an array-based functional programming language derived from APL. What was the name of Landin's operator?Compositional type inference is assured by the property of what?Round 1 AnswersA1: Erlang, A2: A: Chris Okasaki, A3: Fortran (1956), Lisp (1958), Cobol (1959), A4: axiomatic semantics, A5: "type system"Round 2 AnswersA1: Yes; A2: John McCarthy; A3: Hindley-Milner [Hindley-Dumas was also accepted. Daniel Spiewak registered his strong protest that the question as worded does not make sense. It confuses type systems and type inference algorithms.]; A4: Currying; A5: CoqRound 3 AnswersA1: Types; A2: Dependent typing; A3: Gerald Jay Sussman; A4: Algol 60; A5: ISWIMRound 4 AnswersA1: Partial functions are undefined for some argument values. [Many other answers were accepted since the term "function" is used in many contexts.]; A2: [This question should have been worded differently. We only wanted papers with the words "Lambda the Ultimate" in the title, so any three of these four counted: "Lambda The Ultimate Imperative", "Lambda The Ultimate Declarative", "... Lambda The Ultimate GOTO", "... LAMBDA the Ultimate Opcode"] A3: XSLT, Prolog, Ant; A4: Fold/reduce; A5: Alan PerlisTie-break Round AnswersA1: combinators; A2: Guy Steele; A3: J; A4: principal typings Yuvi Masory tag:blogger.com,1999:blog-5448311202414367852.post-1677040584597722192 Wed, 10 Aug 2011 16:14:00 +0000 http://pchiusano.blogspot.com/2011/12/future-of-programming.html What will programming look like 10 or even 20 years from now? With another new year almost here, now is the time to wax philosophical about the future of our industry. We are on the cusp of a number of major transformations in programming that will make 2011 programming technology, techniques, and ideas seem primitive by comparison. The transformations will occur in several key areas: tooling and infrastructure, languages and type systems, and runtime systems.Before I get started, let me preface this all with the disclaimer that this should be taken with a grain of salt, in the spirit of being provocative, and these are not really predictions per se. There are lots of reasons why inferior technologies might continue to dominate the industry longer than expected. I won't talk much about that here, although it's certainly interesting. No, instead I want to give my vision of the future of programming. If there were no accumulated network effects attached to all the mediocre technologies currently in use for programming, if the programming world were given a clean slate and the directive to invent the future, what would I want to result?An overarching theme to all these transformations is the move away from incidental structure and its close cousin incidental complexity. Manifested in various forms, these factors are major barriers to the building programs of greater complexity, and many of the major transformations will be to enable lifting of these barriers. The resulting programming world will look much different--orders of magnitude more code reuse, ease of deployment, efficiency, and much more.Where we beginThe first major change is the move away from storing programs as text, split across "files". You can be forgiven for thinking of this as a minor thing. Who cares how programs are stored or represented, right? In fact, this major source of incidental complexity has spillover effects all the way down the programming toolchain, starting with the pollution of programmers mental thought processes, continuing to development environments (which I'll discuss next), and then to build systems and deployment. Like many of the things I discuss here, the full extent of lost productivity due to this incidental complexity is below most programmers radars. Programmers have unconsciously accepted this lost productivity, to the point that many now rationalize their dependence on files and text for programming.But what about intentional programming, you ask? Or Smalltalk development environments? The idea of moving away from programs as text spread across files is not exactly new, but the devil is in the details. Previous efforts to rid ourselves of this incidental structure have failed in part because they merely substituted one arbitrary structure for another. For instance, intentional programming advocated the good idea of separating code presentation from its storage, substituting instead another format like XML with only slightly less incidental structure. Any advantage conferred by the new format and structure was not exploited to significant benefit, and there was a huge, very real cost in terms of lost network effects from all the text-based tools that could no longer be leveraged. Likewise for Smalltalk development environments. Also, somewhat ironically for Smalltalk, being an OO language, its fundamental premise includes one of the most arbitrary choices of all, in some sense the ultimate generator of incidental complexity, namely, the decision of which class should implement a particular method.There is a real barrier to entry here for any new technology. It doesn't need to just be better than the antiquated status quo; it needs to be significantly so to overcome the network effects and switching cost advantage that status quo technologies inherently posses. In my opinion, none of the proposed text-in-file alternatives so far have come close to overcoming these handicaps.But this is nothing fundamental. We should not conclude from these failed experiments that the idea is unsound. It's merely been poorly executed. The first major shift in getting this right is not storing programs as text at all, not even some normalized textual form like XML, and not some normalized binary form which nonetheless contains a huge amount of incidental structure. Likewise, get rid of files. Instead, a codebase is stored relationally, as a database, with some version of datalog being used for querying and update. Careful thought will be given to this query-update language so that many of the large-scale refactorings that are currently difficult or impossible can be fully automated, or guided automated, with just a few lines of this codebase transformation code. As a simple example, we eliminate the notion of where a function or datatype "is located". Instead, each function gets a unique id (perhaps content addressed, to enable a simple, automated form of code deduplication), and a separate names table maps these ids to names for purposes of rendering the code in some fashion to a human (and in principle, there is really no reason why there can't be multiple names tables, with different programmers choosing different names for the same operation). This representation trivially enables the "renaming" refactoring in just a single table cell update.Let me sketch out a few additional thoughts on how this could work. First, I am not advocating for datalog syntax. I don't care about that. The key functionality enabled by datalog over and above the relational algebra is the ability to express transitive closure and mutual recursion guaranteed to terminate. Together these features enable many of the common queries we'd like to express in transforming and querying our codebases. For instance, here is a hypothetical query to find all references to a given function id, fid. Don't worry if the syntax looks alien or doesn't make sense. The key is more that this query is just a few lines of code to express, and it can be reused and built upon.-- propagate reference to containing applyrefs(Id) :- apps(Id, fid, _). refs(Id) :- apps(Id, _, fid).refs(Id) :- refs(X), apps(Id,X,_).refs(Id) :- refs(X), apps(Id,_,X).-- any lambda whose body is or contains fid-- is considered to reference fidreturn(Id) :- lambdas(Id,_,Id1), refs(Id1).return(Id) :- lambdas(Id,_,fid).Current IDEs, with their enormous development staff and reams of special purpose code, support a very limited subset of code transformation/querying operations, poorly, slowly, and with huge overhead. As a result, there is an entire subculture of programmers (myself included) who have largely rejected IDEs in favor of minimal, less feature-rich but more dependable text editors. Future development environments will take the refactorings now supported by the most advanced IDEs as the most insignificant starting point, and build from there.Large scale refactorings are the inevitable consequence of achieving the reuse needed to build programs of significant complexity that don't die of heat death. Refactoring times in this new model will go from weeks or months to hours, and writing code to transform a codebase will become a separate but critical skill, distinct from the usual act of programming. That is, programmers do not simply conceive of a refactoring (which is often quite simple to express to another programmer), then begin a tedious, manual and error-prone process of text munging to implement it. Instead, the programmer conceives of a refactoring, then conceives of a code transforming program to implement the refactoring, then applies this transformation to the code database, all in the span of a few hours.The code as database concept has spillover simplification effects in other areas of tooling, in particular version control. The problem of handling merges of ordered sequences of characters spread across files and directories with yet more arbitrary structure is extremely difficult, resulting in a huge amount of complexity in the area of version control software. The difficulties have led many to settle for what are arguably inferior VCS models (Git, Mercurial), where changesets form a total order and cherrypicking just doesn't work. In the future, with code databases, we'll see a resurrection of Darcs' patch theory, only this time, it will work exactly as expected, and will be trivial to implement.Related to this notion of code databases, we get much more fine-grained dependency management. Dependency management is another serious problem for software development, a huge hindrance to code reuse, and once again, something that is simply below many programmer radars. A library will often introduce some new interface or abstraction and give several instances of that abstraction for particular concrete types. The library now depends on these concrete types being available for compilation. Including this library now means pulling in all these dependencies, even if you just require the one instance. The overhead of doing this in conjunction with the existing complexity of builds (again partially caused by the programs-as-text-in-files paradigm) means code is reused much less than would be possible or easy otherwise.In the future, we'll be able to conditionally specify code, and not using an ad hoc, 1970s technology like the C preprocessor. The datalog query and update language will factor in here, and allow us to express things like: if a concrete type X is available in the codebase, define some set of functions and new datatypes. Likewise, dependencies will in general not be on "a library" or "a module". A function will depend only on the set of functions and types it references, and a codebase will be a much more fluid thing. We can extract any connected component of functions and datatypes from a codebase, and this is trivial, automated transformation supported by the query language. There are some unknowns here, all solvable, around versioning, and they are related to how we reconceptualize version control as a partial order of changesets, with no extraneous dependencies due to the representation of programs as ordered sequences of characters.Code editing, IDEs, and type systemsCode editing will be done in structural editors, which will look nothing like the existing batch of IDEs that are little more than glorified text editors (and they are actually rather poor text editors). In a structural editor, the programmer will construct expressions which may have holes in them not yet filled with terms. Importantly, these structural editors will be type-directed, so for any given hole the programmer can be presented with set of values matching the expected type, ordered in some sensible way. The editor will perform local program search to enable autocompleting of multiple expressions. If you've ever seen someone live-code Agda, you'll know how powerful and productive this idea could be. Yeah, the actual interface for programming Agda is still kind of 1970s (a custom Emacs mode), but the idea of type-directed editors is powerful. It makes it clear that types are effective not just at preventing many software errors, but also in guiding development. They are a powerful tool to augment our puny programming brains.Along these lines, the rise of type-directed development in languages with real, state of the art type systems will mark the beginning of the end for dynamically typed (aka, single-typed) languages. Dynamic typing will come to be perceived as a quaint, bizarre evolutionary dead-end in the history of programming. This is already widely accepted in some programming circles, where the general consensus is that most dynamic typing advocates are not familiar with type-directed development in a language with a real type system and are basically unaware of the state of the art in type systems and programming language theory. With some additional developments in type systems we'll see any last of any advantages to dynamic typing completely evaporate.A related transition is that types will become even more critical and type systems will grow features to better handle data normalization, the lack of which is a major source of incidental structure and complexity. A big problem in large codebases is data normalization. Lack of data representation normalization is responsible for the significant amounts of plumbing code involved in aligning two pieces of code so they can talk to each other. Most of the mainstream programming world isn't really aware of this issue because code reuse in most imperative codebases is extremely limited (because side-effects don't compose well).In the functional programming world, there is insane amounts of code reuse happening, but along with this comes a fair bit of plumbing. As a small example, consider a function, f, of type X -> Y -> Int, and a value, xs of type [(Y, X)] and suppose you want to apply f to the list. An experienced functional programmer will bust out map (uncurry f . swap) xs in about 3 seconds and not think twice about it. But this code is total boilerplate, there to convince the compiler this is what you really want to do, and is noise when reading the code. Yes, you are acheiving reuse (an imperative programmer would still be writing out a for loop for the millionth time instead of reusing higher-order functions) but it should be cleaner. If this code needs to exist (and I'm not sure it even does, see below), I'd rather get to this point in the editing process and then tell my editor to map f over xs. The editor will search for a program to make the types align, show me the program for confirmation if I request it, and then not show this subexpression in the main editor view, perhaps just showing map f* xs, where the * can be clicked and expanded to see the full program.Even better, perhaps we can get away with much less plumbing in the first place. Plumbing can be eliminated from code in two general ways--the first, which I've just discussed, is to have plumbing code written for you automatically, then hidden unless requested. The second is to have more normalized types and type systems so that there is no incidental structure for code to broker between in the first place. To support this we'll see things like row types, unordered tuples, type sets, and so on, and any related type system machinery needed to make all this feasible and convenient. An idea I'm interested is explicit separation between the model underlying a type (which could be something very normalized, with no incidental structure), and views of that type, which may contain some additional structure. Functions will generally be written to operate over the model, from which any number of views can be reconstructed post-transformation. The compiler or runtime is generally smart about choosing runtime representations to avoid unnecessary round trip conversions between different representations.Language runtimesNon-strict languages will come to dominate the programming world, due to the increase in code reuse and modularity that comes with pervasive non-strictness. As I've argued before, optional laziness doesn't cut it. As with other issues I've mentioned, the problems with strict as default aren't apparent to most programmers, even those who view themselves as well-versed in functional programming. The problems with strictness only become fully apparent as you get much further along in the development of the FP style, in particular, after the discovery of combinator libraries and the further abstractions that develop to remove duplication across these libraries. This has been a source of tension in the Scalaz library, which supports functional programming in Scala, a strict-by-default language, and also in our Scala codebase at work.The only real problem with laziness has to do with reasoning about space usage performance, and evaluation stack usage. These problems get a lot of play among people who enjoy rationalizing their ignorance of Haskell and FP in general, but the truth is some additional research and smarter evaluation strategies can address the problems. There's nothing fundamental here suggesting we should throw up our hands and resort to strict evaluation.The usual normal order evaluation is guaranteed to terminate if any is, but reasoning about is space usage in this evaluation order is problematic. We can do much better. Besides static strictness analysis, which only covers a fraction of the cases we'd like, we can conceive of additional evaluation orders which terminate for the same set of programs as normal-order evaluation, and which can propagate additional strictness information. The one I am particularly interested in I refer to as specializing, strictness-propagating evaluation. I'll elaborate on this in another post, but in this evaluation model, calling a function is something like two communicating coroutines. When calling a function, the callee begins evaluating its body, yielding control back to the caller when it needs its first argument, and also indicating whether that argument should be strict or lazily passed, using whatever information is available at runtime. Subsequent arguments work similarly. As a result, functions are automatically specialized as arguments are passed, and we do not construct thunks if they are going to be consumed strictly by a subsequent callee. This can be implemented efficiently using just two call stacks, and there are various optimizations to the scheme. It is intended to augment, not replace, the existing static strictness analysis and argument passing.In general, the goal of new evaluation strategies should not be efficiency (though that is a nice goal as well), but simple reasoning about space and evaluation stack usage, so that these things do not depend as they currently do on incidental details of how a function is factored or what the compiler chooses to inline (being forced to reason about these things in Haskell breaks the black box abstraction of functions that FP and higher-order programming depend on).Language runtimes and VMs will grow to support these new evaluation strategies, and the current crop of "general-purpose" VMs that are actually quite specialized for strict, imperative languages (the JVM, the CLR) will likely die off.Code distribution and the future of the webWhat of the web, javascript, html 5 and beyond? Are we going to keep hobbling along with these technologies indefinitely? I don't think it's too controversial to say that writing applications of any significant complexity as a web application involves far more work than would be required with access to a truly powerful client-side language. Again, I don't think many web programmers realize just how bad the situation is. In comparison to mainstream languages like Java, C#, or Python, Javascript isn't so bad; in some ways it's even a better language. But compared to a programming language with a good type system and real support for FP like Haskell, Scala, and whatever the next generation of languages can bring, Javascript is quite sad.Of course, proponents of existing web technologies are always finding ways to rationalize the status quo, pointing out how much better things are today than they used to be. That's maybe true, but why settle?I envision a future where Javascript dies off, as do browser-specific plugins like Flash, and instead we'll see client code written in arbitrary, compiled languages, using something like NaCl. This will be combined with a signed code caching and dependency tracking mechanism, so that for instance, you can distribute an application that downloads the entire Java virtual machine and other dependencies, but only if they aren't already cached on your local machine (and the signatures match, of course). This changes how we think about software. Software won't be something you "download onto our computer and then run". Instead, software exists "out there", and you run it. As an implementation detail of running it, it may choose to download some additional code it needs to do its work.This will end the monopoly that html+javascript has on client-side web applications and largely eliminate the switching costs of moving to new client-side technologies. A few lower-level protocols and standards will be enough to tie everything together and maintain the good parts of the web today (I'll say more about this next), but nothing so high-level as specifying the client side language for interaction (Javascript, or Dart, or whatever) or the client-side language for layout and display (html + CSS). In the future, client-side code is written in whatever language, compiled to native code if desired.In place or in addition to native client support, another option would be some sort of in-browser low-level VM designed by people who know what they're doing, who are fluent in the state of the art in programming languages and runtimes. In other words, not the people who designed Dart, Go, Ceylon, or any of the other recent languages that are 30 years or more behind state of the art. We need something that actually supports languages of the future, not something that rearranges the deck chairs on the titanic sinking ship that form the current batch of mainstream languages.What of the suggestion that we simply use Javascript as the "assembly language" of the web, use it as a compilation target, and avoid programming in it directly? This obviously is not ideal. Compiling a real programming language like Haskell or whatever is next through Javascript or Dart is obviously not how anyone would not how design things today given a clean slate. Even if this were possible to do well without bloating client code size beyond what's acceptable, there is the inevitable efficiency hit of compiling to a language whose performance is as bad as Javascript. When you think about it, it makes no real sense to be reverting to 1/10th or 1/100th the speed of what native code or a well-JIT'd VM could provide, purely for ease of deployment. We don't need to be making this tradeoff, and with the rise of something like NaCl and/or a real browser VM, we won't have to.There's one wrinkle. There are tremendous network effects on the web. This is part of its power, and its usefulness, and we don't want to lose it. We do still need the moral equivalent of urls and hyperlinking but one thing we don't necessarily need is the DOM. What will take its place? Don't we need the DOM to enable mashups and services like search engines? Actually, no. DOM munging and traversal is not the only way programs could obtain information from applications on the web, and when you think about it, it's actually rather primitive. Why screen scrape when you can call a real API? This transformation is already sort of happening; most modern web applications expose APIs in the form of REST+JSON. It just needs to be taken a little further.What would this look like? Well, we would need a standard type system for the web. By this I mean a standard way for the applications that live at a url to expose a module of types and functions they support. The underlying type system would be expressive enough to encode richer data than what JSON currently provides (which besides being dynamically typed, cannot even represent sum types effectively) and will support for algebraic data types and some of the type system features alluded to earlier. With this in place, standards will arise for certain function signatures, with standard meanings attached to them. So, for instance, rather than the googlebot crawling the DOM looking for links, it invokes the getAllLinks function of the application at the given url, which returns an actual list of url values. getAllLinks is some separate standard, and new ones can arise on an ad hoc basis, as we grow new modes of interaction with web sites. There will be certain near-universal standards (like getAllLinks) and more specialized ones, specific to the web application in question (for instance, Facebook exports certain functions and datatypes that are specific to Facebook, which are unlikely to be implemented by other sites, though this is certainly not a requirement).Already, we can see this happening somewhat: there are various ad hoc APIs and mechanisms for basically controlling how web crawlers should interpret the DOM.With a standard way of interacting with web sites programmatically, there's no longer any need for the DOM and we can see a proliferation of innovation of different display and layout technologies.Closing thoughts: the rise of functional programmingI've hinted at this throughout: functional programming will absolutely win. Not everyone shares my views, but many of the improvements I've talked about start with the assumption that we are working in a functional, post-imperative world. FP provides a dramatic increase in productivity due to massive increases in code reuse and the ease of reasoning about functional code (not to mention ease of parallelization). The industry is slowly starting to understand this, but it doesn't really matter if many programmers are still for whatever reason resistant to learning FP (which is unfortunately true). Eventually, the selection pressures of a competitive market will weed out less productive and effective techniques, and this largely means the death of imperative programming as we know it, except in certain niche areas. Regardless of initial biases or attitudes, programmers and companies who wish to stay competitive will be forced to employ FP.As for why FP hasn't gained more prominence already, well, perhaps I'll write more about that in another post. What I will say is FP is currently reaching a tipping point enabling its wider adoption and relevance. There are several factors in play: functional language compiler technology is advanced enough, computers are fast enough, and most importantly, the FP community is rapidly discovering all the necessary techniques to organize large programs that preserve referential transparency. The Haskell community has mostly led this charge, Haskell being the only widely-used language that, due to its non-strict evaluation, had no choice but to fully commit to preserving referential transparency throughout. Ten years ago, admittedly, there was a good chance that expressing some programs purely functionally involved what was basically new research. Today, many of the required techniques are known, and expressing even the most imperative-seeming program functionally is possible, and for an experienced functional programmer, pretty effortless. There are still interesting open questions of how to express certain programs, but these are diminishing rapidly.That said, I understand why many people claim FP is too hard, or it's unnatural or awkward, etc. Like many worthwhile subjects, attaining fluency in FP is difficult and requires dedication. Once this level of fluency is reached, though, expressing functional programs is quite natural and effortless (of course, software design is still hard, but finding functional designs becomes easy with practice). For people looking in, the techniques of FP seem opaque and unnecessarily difficult. For people on the inside, there's nothing difficult or complex about it and the benefits are enormous. For those who would criticise FP, I think a little humility is in order. To draw an analogy, no one without mathematical background would feel equipped to dismiss or criticise an entire branch of mathematics ("real analysis is a stupid idea"), and yet programmers with barely a cursory understanding of FP regularly (and loudly) criticise it.I see why some people are frustrated with some of the existing resources for learning the subject. But it's wrong to dismiss the subject on that basis, or on the basis of personalities of people (myself included!) who feel that FP is more productive; objectively, either FP is worth knowing because of the productivity and other benefits it provides, or it isn't. For my part, I am co-authoring a book on FP that I hope is helpful to some who are interested in learning the subject. With the solidification of FP techniques I expect to see more and more resources like this, to the point that fluency and the huge resulting benefits are something that any motivated programmer can work toward, without encountering some of the discouraging hurdles to learning FP that are present today.Will the future of programming look anything like what I've laid out here? Maybe, maybe not. But I certainly hope it will. Paul Chiusano tag:blogger.com,1999:blog-2267747408703654731.post-5656318608400538034 Thu, 29 Dec 2011 03:39:00 +0000 http://scala-enterprise.blogspot.com/2012/01/implementing-richfaces.html JSF 2.1 and JBoss RichFaces 4.1.0 make it easy to do server-side paging and sorting, which improves performance of Java EE web applications significantly compared to returning list of all rows from the database and filtering it later in the application. By implementing ExtendedDataModel, the data model can be used directly by rich:dataTable and rich:dataScroller JSF components.ExtendedDataModel for Spring Data Neo4j Finder/Query Methods To implement this on Neo4j graph database, by using Spring Data Neo4j finder methods we can implement ExtendedDataModel like below: (in Scala programming language) package com.satukancinta.webimport collection.JavaConversions._ import org.ajax4jsf.model.ExtendedDataModelimport javax.faces.context.FacesContext import org.springframework.data.domain.Pageimport org.ajax4jsf.model.DataVisitor import org.springframework.data.neo4j.repository.GraphRepositoryimport org.springframework.data.domain.PageRequest import org.springframework.data.neo4j.aspects.core.NodeBackedimport org.ajax4jsf.model.Range import org.ajax4jsf.model.SequenceRangeimport org.slf4j.LoggerFactory import org.springframework.data.domain.Sortimport org.springframework.data.domain.Sort.Direction import org.springframework.data.domain.Pageableabstract class FinderModel[E]() extends ExtendedDataModel[E] {   private lazy val log = LoggerFactory.getLogger(classOf[FinderModel[E]])    private lazy val rowCount: Int = {    val result= getRowCountLazy     log.debug("Total rows: {}", result)    result   }    private var rowIndex: Int = _   private var page: Page[E] = _  private var pageData: List[E] = _   private var lastRange: (Int, Int) = _  log.trace("Created {}", this.getClass)     def getRowCountLazy: Int   def find(pageable: Pageable): Page[E]  def setRowKey(key: Object): Unit = setRowIndex(key.asInstanceOf[Int])   def getRowKey: Object = getRowIndex: java.lang.Integer    private def loadData(range: Range): Unit = {    val seqRange = range.asInstanceOf[SequenceRange]     val curRange = (seqRange.getFirstRow, seqRange.getRows)    if (lastRange == curRange) {       log.debug("loadData returning cached")      return     }    lastRange = curRange         val pageNum = seqRange.getFirstRow / seqRange.getRows     // ORDER BY name is painfully slow: https://groups.google.com/group/neo4j/t/f2219df41f5500a9     val pageReq = new PageRequest(pageNum, seqRange.getRows/*, Direction.ASC, "y.name"*/)     log.debug("loadData({}, {}) -> PageRequest({}, {})",        Array[Object](seqRange.getFirstRow: java.lang.Long, seqRange.getRows: java.lang.Long,             pageNum: java.lang.Long, seqRange.getRows: java.lang.Long))    val startTime = System.currentTimeMillis     page = find(pageReq)    val findTime = System.currentTimeMillis - startTime     log.debug("Page has {} rows of {} total in {} pages, took {}ms",        Array[Object](page.getSize: java.lang.Long, page.getTotalElements: java.lang.Long,             page.getTotalPages: java.lang.Long, findTime: java.lang.Long))    pageData = page.toList //    val pageIds = pageData.map( _.asInstanceOf[NodeBacked].getNodeId )//    log.debug("Node IDs: {}", pageIds);   }  def walk(context: FacesContext, visitor: DataVisitor, range: Range, argument: Object): Unit = {     loadData(range)    for (val index <- 0 to pageData.size - 1) {       visitor.process(context, index, argument)    }   }  def isRowAvailable: Boolean = rowIndex < pageData.length   def getRowCount: Int = rowCount   def getRowData: E = {    val result = pageData(rowIndex) // repository.findOne(rowKey.asInstanceOf[Long])     val node = result.asInstanceOf[NodeBacked]    log.trace("getRowData({}) = #{}: {}",         Array[Object](rowIndex: java.lang.Long, node.getNodeId: java.lang.Long, node))    result   }  def getRowIndex: Int = rowIndex   def setRowIndex(index: Int): Unit = rowIndex = index  def getWrappedData: Object = { null }   def setWrappedData(wrappedData: Object): Unit = { /* dummy */ }} To use the FinderModel, it's much easier if we create a repository first and add some finder/query methods returning count and Page:public interface InterestRepository extends GraphRepository {     @Query("START u=node({userId}) MATCH u-[:LIKE]->y RETURN COUNT(y)")     public Long findUserLikeCount(@Param("userId") long userId);     // ORDER BY name is still slow: https://groups.google.com/group/neo4j/t/f2219df41f5500a9 //    @Query("START u=node({userId}) MATCH u-[:LIKE]->y RETURN y ORDER BY y.name")     @Query("START u=node({userId}) MATCH u-[:LIKE]->y RETURN y")    public Page findUserLikes(@Param("userId") long userId, Pageable pageable); }How to create a FinderModel instance from Java :    @Inject InterestRepository interestRepo;     private FinderModel userLikesModel;    @PostConstruct public void init() {         userLikesModel = new FinderModel () {            @Override             public int getRowCountLazy() {                return interestRepo.findUserLikeCount(user.getNodeId()).intValue();             }            @Override             public Page find(Pageable pageable) {                return interestRepo.findUserLikes(user.getNodeId(), pageable);             }        };     }And how to use this data model from a JSF Template .xhtml file:             Name                 Quite practical, isn't it?ExtendedDataModel for Spring Data Neo4j RepositoryFinderModel can then be further subclassed to handle any Spring Data Neo4j repository: class GraphRepositoryModel[E]() extends FinderModel[E] {  private var repository: GraphRepository[E] = _     def getRowCountLazy: Int = repository.count.toInt   def find(pageable: Pageable): Page[E] = repository.findAll(pageable)  override def getWrappedData: Object = repository   override def setWrappedData(wrappedData: Object): Unit =    repository = wrappedData.asInstanceOf[GraphRepository[E]] }And use it like this:@Inject InterestRepository interestRepo; private GraphRepositoryModel interestModel;    @PostConstruct public void init() {    interestModel = new GraphRepositoryModel ();     interestModel.setWrappedData(interestRepo);} Hope this helps. To learn more about Scala programming, I recommend Programming in Scala: A Comprehensive Step-by-Step Guide, 2nd Edition. Hendy Irawan tag:blogger.com,1999:blog-733023572967116656.post-1782185778579988778 Sun, 01 Jan 2012 18:32:00 +0000 http://debasishg.blogspot.com/2012/01/2011-year-that-was.html The very first thing that strikes me as I start writing a personal account of 2011 as it was is how it has successfully infused some of the transformations in my regular chores of programming world. It has been different and I am starting to enjoy some of the renewed vigor in areas like Type Systems, Machine Learning, Algebra etc. Throughout the year I used mostly one single language - Scala for programming with some occasional stints in Haskell and Octave for the Stanford Machine Learning course. But I have no regrets in not being more polyglotic, because I could find more time to dig deep into some of the more fundamental areas like algebra, category theory and type systems.Favorite books read / started readingTypes and Programming Languages by Benjamin Pierce : definitely a Knuth statured book in the theory of type systems in programming languages. It's written with a very pragmatic outlook and contains all necessary implementation details to complement the accompanying theory. I have not yet finished reading the book. I am into Chapter 20 and 21 doing recursive types, that look to be one of the most exhaustive treatments of the subject I have ever seen. If and when I manage to finish reading this book, my next plan for theory of programming languages is Design Concepts in Programming Languages.Conceptual Mathematics by F. William Lawvere and Stephen H. Schanuel - I started reading this book from recommendation by Paul Snively as a precursor to Benjamin Pierce's Category Theory for Computer Scientists. This is an excellent introduction to Category Theory and contains a detailed treatment of the unifying ideas of mathemetics, set theory and category theory.Learn You a Haskell for Great Good by Miran Lipovaca - possibly the most recommended and updated Haskell reading in print form. The chapters on Applicative Functors, Monads and Zippers are real treats.Language Proof and Logic by Jon Barwise and John Etchemendy - Starts with a great review of logic and goes on to discuss proofs of soundness andA Tribute to a Mathemagician by Cipra, Demaine, Demaine and Rodgers - Another book in a series written by those illustrious mathematicians and puzzlers who were inspired by Martin Gardner. It's a fascinating collection of essays on mathematical puzzles - get it if you have that bent of mind. Exploring new ideasCategory Theory - Often debated on its usefulness in the practical world, category theory gives you the basic understanding of programming language design, semantics and domain theory. I did lots of readings on Category Theory this year and this has led to a more concrete understanding of type systems as well. Hope to continue more in 2012.Algebra - What's the algebra behind the term Algebraic Data Types ? I took some notes as I started understanding the algebra of recursive data types. Have a look at my notes on github.Machine Learning - I took the Stanford online course on machine learning. It's been a revelation for me to find the pervasiveness of the subject in today's application context. Also the course encouraged me to look more into mathematics that govern all the theories that ML implements. Some great papers readTheorems for Free! by Philip WadlerMonad Transformers and Modular Interpreters by Sheng Liang, Paul Hudak and Mark JonesLazy Functional State Threads by John Launchbury and Simon Peyton JonesA Domain-Specific Language for manipulation of binary data in Dylan by Hannes Mehnert and Andreas BogkRRB-Trees: Efficient Immutable Vectors by Phil Bagwell and Tiark RompfCategorical Programming with Inductive and Coinductive Types by Varmo VeneFunctional Programming with Overloading and Higher-Order Polymorphism by Mark P Jones Programming and Open SourceOnce again a year passed by where I did 95% of programming in Scala. Scala has somehow hit the sweet spot of my liking - OO, FP, JVM, succinctness, I get them all in Scala. However, having said that I have every honest intention to renew all my friendships with Haskell and Clojure in 2012. I did quite a bit of Haskell in 2010 and still reaping the ebnefits of being a better Scala programmer piggybacking on my Haskell thoughts. I know Haskell is purer, a piece of Haskell code can be poetry. But the pragmatics of being on the JVM makes Scala more appealing to my professional life.Two of my open source projects sjson and scala-redis are still quite active. I get pull requests on a regular basis and of course quite a few feature requests and bugs reported on Github. I plan to make some major upgrades to sjson particularly when reflection becomes more accessible in Scala 2.10. Also in line are some enhancements planned towards functor based JSON composition in sjson, which I plan to take up pretty soon. I tried to upgrade scala-redis to keep it in sync with the various releases of redis. Thanks to all of you for trying out sjson and scala-redis. Open source programming is fun and I consider myself blessed to have the opportunities to give something back to the community, which has given me so much over the years.Any mention of my programming activities in 2011 would be incomplete without mentioning scalaz. I now use it in almost every project. It's really a great creation by Tony, Runar, Jason, Paul and the other members of the team. Using scalaz, I have learnt a lot about functional programming and functional thinking.Another library that I have been using regularly since its inception is Akka. Asynchronous messaging is the gateway towards writing scalable applications and Akka provides the right set of batteries towards that. You get messaging, data flows, agents, STMs and all through a nice set of APIs both in Java and Scala. I think Akka is nicely poised to be the killer application to push Scala into the mainstream.Some PublicationsIn 2011 I got the following two papers published, one of them as part of the esteemed team of Justin, Kresten and Steve. Thanks guys ..Debasish Ghosh, Justin Sheehy, Kresten Krab Thorup and Steve Vinoski, "Programming Language Impact on the Development of Distributed Systems," FOME'11: Future of Middleware at Middleware'2011.Debasish Ghosh, "DSL for the Uninitiated," Communications of the ACM, vol. 54, no. 7, pp. 44-50, July 2011 Some nice experiencesI attended 2 international conferences in 2011 - QCon London and PhillyETE. I also talked at PhillyETE on Domain Specific Languages. Both the conferences were amazing and I got to know in person many of the faces that I see and talk to regularly on Twitter and Google+. Incidentally I will also be talking at PhillyETE 2012 slated to be held in April.My book DSLs In Action came out in late Dec 2010. 2011 was the year where I got the first royalty check from Manning. The writing of the book has been an amazing experience and to get to hear good words from people using the book gives another level of satisfaction. Thank you Manning for giving me the opportunity.Looking forward to 2012I am not one for resolutions, but here's a wish list towards more geekery in 2012 ..Program more in Haskell and ClojureBlog more (It was pathetic in 2011)Do more mathAttend more online classes (currently registered for Natural Language Processing, Algorithms and Probabilistic Graphical Modeling at Stanford)Try to do more conferences (currently registered for PhillyETE and Scala Days)Learn more algebra, type theory and category theoryGet started with TAOCP Vol 4ALearn Factor Wish you a very happy new year. See you all in 2012! Debasish Ghosh tag:blogger.com,1999:blog-22587889.post-1217482404269919964 Sat, 31 Dec 2011 20:40:00 +0000 http://scala-enterprise.blogspot.com/2011/12/scala-closures-vs-guava-collection.html Let me show you the same method using list transformations (aka "map" in functional programming speak), one in Java programming language:    @GET @Path("user/{userId}/likes") @Produces(MediaType.APPLICATION_JSON)     public Payload >> getUserLikes(@PathParam("userId") long userId) {         User user = neo4j.findOne(userId, User.class);        Iterable likeInterests = user.getLikeInterests();         Iterable > likes = Iterables.transform(likeInterests, new Function >() {             @Override            public Map apply(Interest interest) {                 HashMap row = new HashMap ();                row.put("id", interest.getNodeId());                 row.put("name", interest.getName());                return  row;             }        });         return new Payload >>(likes);    } And one in Scala programming language :    @GET @Path("user/{userId}/likes") @Produces(Array(MediaType.APPLICATION_JSON))     def getUserLikes(@PathParam("userId") userId: Long): Payload[Iterable[Map[String, Object]]] = {        val user = neo4j.findOne(userId, classOf[User])         val likeInterests = user.getLikeInterests        val likes = likeInterests.map(interest =>           Map("id"->interest.getNodeId, "name"->interest.getName) )        new Payload(likes)     }Is Scala hard to read? I'll leave it to you to decide. :-) To learn more about Scala programming, I recommend Programming in Scala: A Comprehensive Step-by-Step Guide, 2nd Edition. Hendy Irawan tag:blogger.com,1999:blog-733023572967116656.post-7138602570659211771 Sat, 31 Dec 2011 18:33:00 +0000 http://scala-enterprise.blogspot.com/2011/12/coding-json-rest-jax-rs-service.html Spring Data Neo4j makes it easy to accessing graph data in Neo4j graph database.After separating the AspectJ-enhanced Spring Data Neo4j node entities, relationship entities, and repositories, it's very fun to access the entities from a Scala web application. In this case, I'll show you a JAX-RS application written in Scala programming language, consuming and producing JSON in REST-style. The application exposes Spring Data Neo4j through HTTP, which can be accessed via curl or any other web client. Java programming language version:@Path("node") @Statelesspublic class NodeResource {     private transient Logger logger = LoggerFactory.getLogger(NodeResource.class);     @Inject Neo4jTemplate neo4j;    @Inject InterestRepository interestRepo;         @GET @Path("interest") @Produces(MediaType.APPLICATION_JSON)     public Iterable interest() {        ClosableIterable records = neo4j.findAll(Interest.class);         return records;    }     @GET @Path("user") @Produces(MediaType.APPLICATION_JSON)    public Payload getUser() {         return new Payload (neo4j.findOne(5L, User.class));    }     @POST @Path("interest")    @Consumes(MediaType.APPLICATION_JSON)     @Produces(MediaType.APPLICATION_JSON)    public Response createInterest(Payload payload) {         logger.debug("createInterest {}", payload.data);        Interest interest = payload.data;         interest.persist();        return Response.created(URI.create(String.format("interest/%d", interest.getNodeId())))                 .entity(new Payload (interest)).build();    }     @DELETE @Path("interest/{id}")    public Response deleteInterest(@PathParam("id") long id) {         try {            Interest node = neo4j.findOne(id,  Interest.class);             node.remove();            return Response.ok("deleted").build();         } catch (DataRetrievalFailureException e) {            return Response.status(Status.NOT_FOUND).entity(e.getMessage()).build();         }    }     @GET @Path("interest/by/facebookId/{facebookId}")    @Produces(MediaType.APPLICATION_JSON)     public Payload findInterestByFacebookId(@PathParam("facebookId") long facebookId) {        logger.debug("findInterestByFacebookId {}", facebookId);         Interest interest = interestRepo.findByFacebookId(facebookId);        if (interest == null)             throw new WebApplicationException(Response.status(Status.NOT_FOUND).entity("Interest with facebookId="+ facebookId +" not found").build());         return new Payload (interest);    } }Scala programming language version:@Path("node") @Stateless class NodeResource {    private lazy val logger = LoggerFactory.getLogger(classOf[NodeResource])     @Inject var neo4j: Neo4jTemplate = _     @Inject var interestRepo: InterestRepository = _         @GET @Path("interest") @Produces(Array(MediaType.APPLICATION_JSON))     def interest: Iterable[Interest] = neo4j.findAll(classOf[Interest])    @GET @Path("user") @Produces(Array(MediaType.APPLICATION_JSON))     def getUser: Payload[User] = new Payload[User](neo4j.findOne(5L, classOf[User]))     @POST @Path("interest")    @Consumes(Array(MediaType.APPLICATION_JSON))     @Produces(Array(MediaType.APPLICATION_JSON))    def createInterest(payload: Payload[Interest]): Response = {         logger.debug("createInterest {}", payload.data)        val interest = payload.data         interest.persist        Response.created(URI.create(String.format("interest/%d", interest.getNodeId)))                 .entity(new Payload[Interest](interest)).build    }     @DELETE @Path("interest/{id}")    def deleteInterest(@PathParam("id") id: Long): Response = {         try {            val node = neo4j.findOne(id, classOf[Interest])             node.remove            Response.ok("deleted").build         } catch {          case e: DataRetrievalFailureException =>             Response.status(Status.NOT_FOUND).entity(e.getMessage).build        }     }    @GET @Path("interest/by/facebookId/{facebookId}")     @Produces(Array(MediaType.APPLICATION_JSON))    def findInterestByFacebookId(@PathParam("facebookId") facebookId: Long): Payload[Interest] = {         logger.debug("findInterestByFacebookId {}", facebookId)        val interest = interestRepo.findByFacebookId(facebookId)         if (interest == null)            throw new WebApplicationException(Response.status(Status.NOT_FOUND).entity("Interest with facebookId="+ facebookId +" not found").build         new Payload[Interest](interest)    } }Apart from less code and cruft, Scala code is not much different in structure. If there are list processing functions or closures, then Scala code will read much easier, while the Java code will use Guava library and clunky syntax (at least until Java 8 arrives). To learn more about Scala programming, I recommend Programming in Scala: A Comprehensive Step-by-Step Guide, 2nd Edition. Hendy Irawan tag:blogger.com,1999:blog-733023572967116656.post-7509776215606216125 Sat, 31 Dec 2011 17:21:00 +0000 http://scala-enterprise.blogspot.com/2011/12/graph-analysis-with-scala-and-spring.html Neo4j graph database is the an awesome technology for graph data persistence. With Spring Data Neo4j accessing graph data becomes even easier. The easiest way to use Spring Data Neo4j is by enabling its AspectJ weaving. Because I wanted to use both Scala and Spring Data Neo4j in my web application, using both languages (AspectJ and Scala) in the same project isn't possible for now. A tip for you, separate the AspectJ-enhanced classes (@NodeEntity, @RelationshipEntity, and repositories) into a separate AspectJ project, then depend on the AspectJ from the Scala application. The result is I'm able to fully utilize the versatile Scala and the excellent Spring Data libraries with Neo4j.Now for mandatory code comparison between Java and Scala :-)Java programming language version: package com.satukancinta.web;import java.util.List; import java.util.Map;import javax.enterprise.context.ApplicationScoped; import javax.inject.Inject;import javax.inject.Named; import org.slf4j.Logger;import org.slf4j.LoggerFactory; import org.springframework.data.neo4j.conversion.Result;import org.springframework.data.neo4j.support.Neo4jTemplate; import com.google.common.base.Function;import com.google.common.collect.Iterables; import com.google.common.collect.Lists;import com.satukancinta.domain.User; /** * @author ceefour  * Various analysis of the social graph. */ @Named @ApplicationScopedpublic class GraphAnalysis {         private transient Logger logger = LoggerFactory.getLogger(GraphAnalysis.class);     @Inject Neo4jTemplate neo4j;        public List getMutualLikesLookup(User user) {        logger.debug("getMutualLikesLookup {}/{}", user.getNodeId(), user);         Result > rows = neo4j.query("START x=node("+ user.getNodeId() +") MATCH x-[:LIKE]->i<-[:LIKE]-y RETURN id(y) AS id, y.name AS name, COUNT(*) AS mutualLikeCount", null);         Iterable result = Iterables.transform(rows, new Function , MutualLikeRow>() {             @Override            public MutualLikeRow apply(Map arg) {                 return new MutualLikeRow((Long)arg.get("id"), (Integer)arg.get("mutualLikeCount"),                        (String)arg.get("name"));             }        });         return Lists.newArrayList(result);    } }Scala programming language version:package com.satukancinta.web import collection.JavaConversions._import org.slf4j._ import javax.inject.Injectimport org.springframework.data.neo4j.support.Neo4jTemplate import com.satukancinta.domain.Userimport javax.enterprise.context.ApplicationScoped import javax.inject.Named/**  * @author ceefour * Analysis functions of friend network graph.  */@Named @ApplicationScoped class GraphAnalysis {  private lazy val logger = LoggerFactory.getLogger(classOf[GraphAnalysis])   @Inject private var neo4j: Neo4jTemplate = _    def getMutualLikesLookup(user: User): java.util.List[MutualLikeRow] = {    logger.debug("getMutualLikesLookup {}/{}", user.getNodeId, user)     val rows = neo4j.query(        "START x=node("+ user.getNodeId() +") MATCH x-[:LIKE]->i<-[:LIKE]-y RETURN id(y) AS id, y.name AS name, COUNT(*) AS mutualLikeCount", null)     val result = rows.map( r =>          new MutualLikeRow(r("id").asInstanceOf[Long],             r("mutualLikeCount").asInstanceOf[Integer].longValue,            r("name").asInstanceOf[String]) )         .toList    result.sortBy(-_.mutualLikeCount)   }  } As you can see, the Scala version is not only much more concise, easier to understand, but actually has added functionality (sorted using .sortBy) with less code. Thanks to collection functions and closure support. To learn more about Scala programming, I recommend Programming in Scala: A Comprehensive Step-by-Step Guide, 2nd Edition. Hendy Irawan tag:blogger.com,1999:blog-733023572967116656.post-4545426233073459063 Sat, 31 Dec 2011 16:36:00 +0000