Clash of the Lambdas, updated

We would like to provide a revised version for our Clash of the Lambdas paper that was accepted in ICOOOLPS'14. We would also like to thank the reviewers, the conversations on our Github repo and other readers that have sent comments via email and strengthened this paper.

In the revised version:

1. we used a fixed heap with 3GB. The GC throughput was improved and results are more balanced
2. we discussed briefly why we chose not to use targeted JVM flags
3. we discussed @specialized and miniboxing
4. we added a new benchmark that tests a streaming operation that avoids automatic boxing of our input data
5. a subtitle was added

Attended SIGPLAN PLMW and POPL 2014

This year's "Programming Languages Mentoring Workshop" and POPL that took place in San Diego, had been a blast. This was my second time attending PLMW/POPL and I can say that anyone who will be able to attend this conference (and the mentoring workshop day) while being a PhD -or even undergrad- student will get a unique opportunity to explore the field of programming languages. So, go for it, the next time you hear about the PLMW scholarships!

This year's attendance had a little bit of structure in note taking for me, since I had a "battery-autonomy > 2 hours"d laptop this time. The format was in Latex and in the end I had a ten-page pdf-document of raw data with links, listings, citations, summaries of talks, to-do items that will help me or a colleague! Surprisingly, the interest some times doesn't come from the solution to a problem that a paper presents per se, but from the methodology that was followed. Some things/realizations/resolutions/advices to share listified are the following:

• Invariants are calculated, are approximated, are broken, can be temporarily broken and then restored, dependent types are super-related to them, are definitely a key concept of parametricity, to abstraction safety and many more! 
• Look for Peter O’Hearn's and Isil Dillig's talks for abstract interpretation 101 (this will help you a lot for past, current and future POPL papers).
• Study about academic writing, presenting!
• Separation Logic can provide solutions to reasoning of infinitely many problems (like type invariant that holds almost everywhere, like reasoning for C sequence points)
• Study Software Foundations and Certified Programming with Dependent Types, Coq is must nowadays. Mechanically checked proof writing with Coq is already a top-class skill for POPL publishing.

Important papers as prerequisites of several talks I attended. This list features papers that I have either found to be a seminal paper, or a paper of a system that was used for evaluation purposes, or a previous paper of the same author, etc. [1] was mentioned from at least 3 distinct speakers; a Coq implementation of a verified Red Black Tree, [2] to understand a this direction in POR, [3] seminal paper on abstract interpretation, [4] interesting use as a case study from a paper but interesting in general for industrial-strength parser library, [5] for lambda calculus with effects, [6] for Symbolic Finite Automata cases and basics, [7] a super-tutorial for DT PL, [8] for parametricity and "on the point and purpose of types", [9-10] parametricity, [11] a guide/insight of Reynolds-papers.

1. Appel, Andrew W. Efficient verified red-black trees, 2011.
2. Flanagan, Cormac, and Patrice Godefroid. Dynamic partial-order reduction for model checking software, ACM Sigplan Notices. Vol. 40. No. 1. ACM, 2005.
3. Patrick Cousot and Radhia Cousot. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, 1977.
4. Leijen, Daan, and Erik Meijer. Parsec: Direct style monadic parser combinators for the real world, 2001.
5. Felleisen, Matthias, and Daniel P. Friedman. Control Operators, the SECD-Machine, and the Lambda-Calculus, 1986
6. Veanes, Margus. Applications of symbolic finite automata. Implementation and Application of Automata. Springer Berlin Heidelberg, 2013.
7. Löh, Andres, Conor McBride, and Wouter Swierstra. A tutorial implementation of a  dependently typed lambda calculus. Fundamenta informaticae 102.2, 2010.
8. Reynolds, John C. Types, abstraction and parametric polymorphism. (1983):513-523.
9. Mitchell, John C. Representation independence and data abstraction. Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 1986.
10. Wadler, Philip. Theorems for free!. Proceedings of the fourth international conference on Functional programming languages and computer architecture. ACM, 1989.
11. [metapaper] Brookes, Stephen, Peter W. O’Hearn, and Uday Reddy. The essence of Reynolds. Proceedings of the 41st annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM, 2014.

Oculus Rift: First Impression

First Impression

I was very lucky today to experiment with an Oculus Rift Development Kit. By now, I am probably several months late to do an elaborate review of the packaging-installation-performance evaluation; you already know many of that stuff from many other posts from the Oculus community (e.g. r/oculus). However, the experience of playing with a Rift as a user was unprecedented and I believe that some thoughts are worthsharing.

Firstly, the Rift came in a beautiful case that absolutely protects the device and everything was included: from UK, US plugs to HDMI cable, mini-usb and a usb-to-DVI adapter. The professionalism that the Oculus team shows by this "product" presentation with the SDK is amazing. 

Unfortunately I wasn't able to try this out at my Ubuntu laptop, as a displayport-to-HDMI converter was necessary; so our first exploration was made from a Sony Vaio equipped with a mainstream NVidia GeForce 330 that did run the demos, but with the FPS (in Rift) varying from 30 to 40. The installation was seamless. No quirks, no missing dlls (except when I first built a demo with some needed DirectX components that come with the redistributable), no surprises. We used the second pair of lenses that came with the Rift. The package included three pairs, A, B and C and the user is free to use which ever he likes in order to achieve the most focus possible for nearsighted people. The 1280x800 (an HD prototype is already presented) (2 displays with resolution 640x800), 32-bit colour, LCD head-display was ready to have it's gyroscope sensor calibrated.

And then the fun started with the free demos from share.oculusvr.com and www.riftenabled.com. Many hours of "playing" and experimenting with the setup followed. Among the demos, the few that I highly recommend-as a must-are the vr.training (inspired by Metal Gear Solid training levels~nostalgia alert~and highly recommended for low-end graphic systems), VR Cinema (that can load an avi, wmv or mkv and play it as if you watch it in a theater), Titans of Space (educational), Blocked In (just a presentation of a single room for an adventure game), Dreadhalls (an absolute atmospheric/horror game), Fallen Angel's Lair (demonstrating UDK, the Unreal Engine), Oculus Tuscany Demo (101 demo from Oculus), Ocean Rift (watch out for the shark) and the coasters from archivision. What will come next to our evaluation is the heavy artillery of gaming (e.g. Half Life 2 - opting in for beta from its Steam menu and by providing the "-vr" command line argument).

The simulator sickness

Before trying Rift, I was sceptical (as everyone) for the simulator sickness that occurs to the user, that results from slight disorientation as a game progresses. The user builds up discomfort from in-game locomotion, rapid rotations, fast changes in elevation etc., which are all some form of acceleration that the brain perceives but the body doesn't actually feel. Some things regarding this matter can be improved dramatically: 1) technologically (like latency and tracking precision) and 2) some other things must be taken under consideration in the game design - HCI level. The developer.oculusvr.com site has a very informative wiki page with guidelines (e.g., placement of camera, displaying text, speed of elements, flashing, providing static references like a cockpit etc. that limit the sickness effect).

Screen-door effect

 

The most annoying thing in the whole process of evaluation is that due to the low resolution of the displays that are extremely close to your eyes you can really see the black lines between pixels. From what I read at the community-press this effect can be eliminated with both higher resolution and better higher pixel-fill rate (to my understanding).

Packaging

Lenses

USB box (transfers sensor data to pc)

Again a rear view

Side view (controlling the distance of the headset from eyes)

I would really recommend the Step into the Game with Oculus Rift and Unity 4.2 video from Unite 2013 by Peter Giokaris who explains elements of the device and gives a primer on the Unity 3D for Rift.

Conclusion 

(as an end user and not API-wise yet)

Oculus Rift is definitely THE future of Virtual Reality (as a computer science field in general). It can have many applications apart from home entertainment to boost productivity and efficiency, enhance (augment) reality, help people with vision problems (as in this recent project about diplopia) and many more. The final product is expected to benefit from the market growth of smart-phones and the need for better, more complex with live colors, high refresh-rate (and of reduced price) displays. 

Qt, MPRIS2 and Clementine

I have been using Clementine in a daily basis for some months now and I finally feel that I have a solid music player for my Ubuntu box. Clementine is a Qt-based media player that is inspired by Amarok 1.4 and the maintainers have done a great job supporting and extending this project while building a solid and dedicated community about it (follow on Facebook, on Twitter, on Last.fm).

Lately I noticed a little quirk (~where quirk is a low importance abnormality for usual people - but not for my state of mind :P) in Clementine's interaction with the Sound Menu widget in Ubuntu's taskbar (Issue 3962). The quirk was that the open playlists in Clementine weren't reflected at the same time in this widget. This initially led to Arnaud fixing a crash when adding a new playlist, re-opening Clementine, removing the playlist from Clementine and selecting it from Ubuntu's sound menu. But my initial obsession still hadn't been satisfied, so I kept looking for a way to trigger the rebinding of the Sound Menu with the playlist collection, upon each playlist change. I learned several things over the last weekend that I'd like to share but I was also reminded that a lot of IPC is text-based at the user-level and progress is a matter of text-based specifications that won't fully express the semantics of underlying processes.

 

Playing with D-Bus

The Sound Menu communicates with Clementine via the MPRIS2 D-Bus interface specification (mpris2 is the latest specification for communication with media players). Regarding the message-bus for the graphical system of Ubuntu, I knew nothing so I experimented a little bit. However, I could not find a way to refresh the Sound Menu. How was it populated at the initialization phase and why we couldn't find a way to re-populate it on demand? The specification isn't clear about this if you study it in detail. A certain bug reported back in 2011, however shed light to our case:

Sound Menu should re-read playlists from MPRIS apps when PropertiesChanged is posted

the description of which was:

At the moment, the sound menu only ever calls GetPlaylists for an MPRIS app once, immediately after it appears on the bus. If an app's playlists change, there's no way for the app to notify the sound menu that the playlists should be re-read.

As you see from the fix, from there on you could get an update by posting an arbitrary PropertiesChanged to the Sound Menu in order for it to trigger calling the GetPlaylists again. Below, you can see the output of dbus-monitor that captured the traffic of the GetPlaylists method invocation (from the sound panel to Clementine).

method call sender=:1.45 -> dest=org.mpris.MediaPlayer2.clementine serial=425 path=/org/mpris/MediaPlayer2; interface=org.mpris.MediaPlayer2.Playlists; member=GetPlaylists
   uint32 0
   uint32 100
   string "Alphabetical"
   boolean false

method return sender=:1.121 -> dest=:1.45 reply_serial=425
   array [
      struct {
         object path "/org/mpris/MediaPlayer2/Playlists/29"
         string "Playlist 29"
         string ""
      }
      struct {
         object path "/org/mpris/MediaPlayer2/Playlists/30"
         string "Playlist 30"
         string ""
      }
   ]

In the example above the sender that sent/invoked the GetPlaylists messages/command is the com.canonical.indicator.sound service. This command sent four arguments each for every parameter and the response was an array that contained two playlists. Unfortunately, yet another quirk came to light (to us) which I believe is related with the "sound menu caches playlists which causes issues" bug that was fixed (or reported fixed) recently. Here are tools that guided me through the process of experimenting with d-bus.


Additionally, several interesting utilities exist like qdbus (for Qt based applications), mdbus2 (for general introspection) and dbus-send for complete control on sending commands over d-bus. Of course there are visual tools also (like Qt's D-Bus Viewer-qdbusviewer), that will definitely assist you.

Qt

 

I didn't have any previous experience with Qt but a lot from Windows Forms, ASP.net and Silverlight instead to have enough intuition about the general abstraction. I also have some experience from MFC C++ that was enough to catch up easily with the low-level-ness of Qt.

The thing I found interesting about Qt at first glance was the mechanism that it employs to implement signalling between objects. Qt employs a loosely coupled design separating the concerns of the binding process between slots and signals diverging by the callback-based design. In essence signals are emitted when something happens and slots are potential handlers. The gluing code (which signal is going to be handled-or delivered-by what slot) is realized by a connect function. The documentation mentions:

You can connect as many signals as you want to a single slot, and a signal can be connected to as many slots as you need. It is even possible to connect a signal directly to another signal. 

What is of great interest (for the C++ realm) is that the connect functions are promoted with a programming model that is considered type-safe (or just more safe that a callback based design).

Slot and signals can be wired like below:

connect(playlist_manager,       
        SIGNAL(SelectionChanged(QItemSelection&),
        SLOT(SelectionChanged(QItemSelection&));

Note that SIGNAL and SLOT are macro functions that support the static check of whether types match (and certain rules, e.g. about the number of parameters between signal and slots). How are these macros defined?

#define Q_SLOTS 
#define Q_SIGNALS protected 
#define SLOT(a) "1"#a 
#define SIGNAL(a) "2"#a

From the definitions above you understand that something else happens from what you have initially thought. Qt uses the mechanism of a Meta-Object Compiler (moc). Why does Qt use moc for signals and slots? This article provides a reasonable argument that by this way they keep syntax easy to read, generated code is compiled by a standard C++ compiler and performance isn't that of a big compromise for Qt to have used a template metaprogramming solution, instead of moc. You can find more info about the usage of moc at the Using the Meta-Object Compiler (moc) article.

"Classes. He would like to replace classes with delegation."

I had the intuition from my software engineering days, but for the last few months (due to our Forsaking Inheritance paper) I have been seeing stuff about dropping inheritance or advocating that inheritance is bad... everywhere.... from very old sources to very recent ones, spanning a period of nearly three decades...

1. James Gosling 's interview that I first saw some months ago at Simon Peyton Jones' talk at the OPLSS'13 (There were two main questions: What would you take out? What would you put in? To the first, James evoked laughter with the single word: Classes. He would like to replace classes with delegation since doing delegation right would make inheritance go away. But it's like Whack-A-Mole (more laughter) since when you hit one mole, er, problem, another pops up.)
2. Why extends is evil.
3. Recent example from the C++ themed online conference GoingNative 2013, Inheritance Is The Base Class of Evil (general example of a talk, demonstrating that inheritance is still discussed as a "it would be best to avoid" feature.)
4. Patterns for subclassing to avoid embarrassing situations with library clients, The Art of Subclassing.
5. The are even refactoring options for it (e.g., IntelliJ's "Replace Inheritance with Delegation".)
6. There are solutions with Java annotations like lombok's @Delegate
7. delegate(*methods) in Ruby on Rails
8. Go (the programming language) diverges from the usual notion of subclassing, by embedding types together (without late binding as mentioned explicitly) simplifying composition [SO]. The Gang of 4's crucial principle is "prefer composition to inheritance"; Go makes you follow it. (I liked how the so poster put it).
9. The End Of Object Inheritance & The Beginning Of Anti-Rumsfeldian Modularity by Augie Fackler and Nathaniel Manista
10. .... and last but not least a whole category of academic work on Subtyping, Subclassing, and the Trouble with OOP in general (article and refs by Oleg Kiselyov.)

Scala Specialization: a primer on the translation scheme

Scala's specialization facility is present since 2.8 and is enabled selectively with the @specialized annotation that can annotate generic parameters. This means that the type parameter can be specialized on the specified primitive types to avoid the performance burden of boxing and unboxing. In an effort to understand the basic idea of the translation scheme I created this post for a quick reference of mine.

In a nutshell

The core concept of the translation scheme is that normal method invocations to instances must always work when the instance is not specialized and on the other hand if enough type information exists the compiler will rewrite method calls to the specialized variants.

In the example below, the original code defines a Specialized class, that indicates two specializations, one to Int and the other to Double. This annotated definition creates three generated classes: a generic one that is called Specialized (with regular type erasure, where generic type arguments are erased and substituted by bounds) and two specializations Specialized$mcI$sp and Specialized$mcD$sp. These latter extend Specialized, overriding methods with specialized ones. The interesting part is that each specialized variant overrides the apply method that returns Object and a code generated one. The apply method in each class delegates the call to the generated method that performs an operation on the primitive type itself. Additionally, the generic versions of the methods of the specialized classes (like apply in line 40) are preserved and also specialized versions of methods on the generic class are also preserved like in lines 4,5. This duality in the wiring process ensures both correctness (e.g., calling the generic method apply in the specialized instance) and ensures proper late binding.

A question that was answered to me in this comment by Aleksandar Prokopec was: Why in line 22, the ret.apply() call is rewritten to ret.apply$mcI$sp();? The compiler acts pro-actively here by rewriting every apply call to the specialized one. The static type of the receiver directs the compiler to rewrite the call, but then the proper version of the method body is found via late binding on the actual instance that was passed (and potentially calling a specialized method to avoid boxing).

References

A more elaborate description of the initial design, implementation and semantics of Scala Specialization is included in Iulian Dragoș PhD thesis which is about Compiling Scala for Performance. Also, in Aleksandar Prokopec's blog there is an elaborate post about Quirks of Scala Specialization outlining several guidelines. Finally, I don't know what the current state of specialization is but back in the 2012, the rethinking specialization spawned the SIP: Changes to the Specialization Phase.

Reified Type Parameters Using Java Annotations

My GPCE talk about @reify is over. One of the questions asked during Q&A was how is it possible to override the object's getClass() method to return correct information. If an instance is available and obj.getClass() is invoked (where obj is declared as T where T is generic type), then by employing only our proposed generation scheme getClass() won't provide the full type information. getClass() cannot be overriden and the answer to this is that method invocations of getClass() may also need to be rewritten in the AST level. Additionally, generic type information must be stored in the object instance level to make full reflection support possible to be provided. The class literal (.class syntax) on the other hand is valid only on types right now. With @reify if we get to write T.class where T is abstract, due to the .class expression that evaluates to the T class statically we can generate the proper code as we showed in the paper.

Thank you all for attending and also thank you for your comments.


And the poster that I presented in the SPLASH Poster Session (in pdf format):