Posts

Showing posts from 2010

The underappreciated banana and its buddy monoid

Note : This is the blog post that goes with the Channel9 lecture "Going Bananas". You find all material (slides, code) linked up on the web site for my Channel9 series ; see the section on "Going Bananas". I will add a link to the C9 website with the video as soon as it gets available. I am really Ok. Well, but I do see bananas (folds) everywhere. This tells me that data processing is quite regular. For instance, MapReduce computations for parallel data processing are essentially folds that extract some intermediate data from the records of a voluminous input---subject to subsequent, possibly distributed and staged reduction. Also, in program transformation and analysis, many data processing steps are compositional, and thereby suggest themselves as being implemented through "large" bananas. Further, in XML processing, many operations are busy with folding over XML trees. There are bananas for everyone ---not just for lists. If we were just acknowledging s

A brutalized Haskell programmer

In working on a special Xmas lecture for my 1st semester course, I was going through Fritz Ruehr's " The Evolution of a Haskell Programmer " only to notice that there is no imperatively faked version that uses references. This omission could be resolved with the following code: module Control.Pascal where import Data.IORef while :: IORef a -> (a -> Bool) -> IO () -> IO () while ref pred body = while' where while' = do v <- readIORef ref if (pred v) then body >> while' else return () {- ******************************* -} import Data.IORef import Control.Pascal factorial n = do r <- newIORef 1 i <- newIORef n while i (>0) ( readIORef i >>= modifyIORef r . (*) >> modifyIORef i ((+) (-1)) ) readIORef r For instance: Prelude> factorial 5 120

Going bananas

This week I will be visiting Klaus Ostermann and his team. I am going to be a guest lecturer in Klaus' programming languages lecture. I am going to misuse this opportunity for a rehearsal of my upcoming Channel9 lecture on bananas. I eat 2 bananas over the last 42 hours in order to get into the right mood. The talk announcement follows. Speaker : Ralf Lämmel , Software Languages Team, Universität Koblenz-Landau Title : Going bananas Slides: [ .pdf ] Abstract : Banana is functional programming slang for "fold", say an application of the catamorphic recursion scheme---most widely known in higher-order list processing in the tradition of the Bird-Meertens Formalism and the Squiggol community. In this talk, I will present various kinds of folds, and thereby show the omnipresence, versatility, and expressive power of folds in different areas of programming. This presentation will integrate work by others and my own in a balanced manner, while aiming at broad coverage of banan

Grammar-based Testing Revisited

I am about to leave for Southampton ( this is from where the Titanic started ) for a few days to visit Dr. Bernd Fischer , who also calls himself Fish. (Another fish that is!) The idea is to give a talk and have interaction on the topic of grammar-based testing. In fact, I don't tell you any secret, if I say that Bernd is the expert on code generation, and so I am keen to intensify collaboration on that topic as well. The talk announcement follows. Speaker : Ralf Lämmel , Software Languages Team, Universität Koblenz-Landau Title : Grammar-based Testing Revisited Slides : [.pdf] Abstract : Testing grammar-based artifacts has been researched for decades. A classical and enduring motivation for such testing is that grammar-based functionality (such as an interpreter or a compiler) may be formally specified (e.g., by means of an attribute grammar) so that the specification lends itself to test-data generation. The test data, in turn, can be used to test a proper implementation for com

Statistische Analyse der Parkplatz-Situation auf einem Universitätscampus

Wenn sich ein Kandidat und ein Mitbetreuer etwa aus dem Inst. CV des FB4 (Informatik) findet, dann soll ich dieses ansonsten für illustrative oder Frustrations-lösende Zwecke erfundene Bachelor-Thema am Ende wirklich gern betreuen. Bachelorarbeitsthema Thema : Statistische Analyse der Parkplatz-Situation auf einem Universitätscampus Motivation : Auf dem einen oder anderen solchen Parkplatz bzw. Campus gibt es empirische Hinweise, dass es einerseits zu wenig Parkplätze oder anderseits zu wenig verantwortliches Verhalten der Parkplatznutzer gibt. In Vorbereitung dieser Themenstellung hat der Themenstellende beispielsweise am 3.11.2010 um 8.45 eine Zählung auf dem Mitarbeiterteil des Parkplatzes am Campus Koblenz der Universität Koblenz-Landau vorgenommen. Um diese Zeit waren alle bis auf 3 Parkplätze belegt und diese verbleibenden Plätze waren nicht mit handelsüblichen Fahrzeugen einnehmbar wegen der durch das Falschparken Anderer verursachten Verringerung des Platzes. Knapp 1/3 aller Fa

Towards a megamodel for programming and language technologies

Summary We have started a major effort on megamodeling programmig and language technologies. At GPCE 2010 and SLE 2010, we have revealed this effort. Contributions are more than welcome. Our next milestone is an actual megamodel that covers the software corpus "101companies". Links The GPCE/SLE megamodeling tutorial: description [ .pdf ]; slides [ .pdf ]. The GPCE 2010 keynote: website: [ .html ]; slides: [ .pdf ]. The 101company website at SourceForge developers: [ .html ]. Acknowledgements All of this is joint work with Jean-Marie Favre and Dragan Gasevic. Thomas Schmorleiz is the incredible developer who helps on 101companies. Wolfgang Lohmann has done a great job on the empirical parts of the keynote. Background I have been developing an advanced programming class over the last 3 years. A defining characteristic of the class is that it is supposed to cover a broad range of programming and language technologies---perhaps a much broader range than in many other programmin

Dealing comfortably with the confusion of tongues

That's the title of my invited talk at CHOOSE Forum 2010 . See the abstract below. I just realized that I am going to meet some esteemed colleagues there: Jean Bezivin, Jean-Marie Favre, Uwe Zdun. Talk announcement : http://choose.s-i.ch/events/forum2010/laemmel Abstract : Yahweh brought the confusion of tongues upon the people in the plain of Shinar because he did not like their efforts of building the Tower of Babel with its top in the heavens. In IT, we brought the confusion of tongues upon ourselves with the continuous aggregation of ideas for programming (languages), modeling (languages), domain concepts and domain-specific languages, design patterns, APIs, and so on. All this diversity makes a nontrivial software system look like the Tower of Babel—in terms of the involved complexity. That is, a nontrivial software system involves multiple technical spaces, technologies, bridges between them, and harmful amounts of software asbestos. How can IT personnel acquire the relevant

(Mega)modeling Software Language Artifacts

GPCE/SLE 2010 tutorial Jean-Marie Favre (OneTree Technologies, Luxembourg) Dragan Gašševic (Athabasca University, Canada) Ralf Lämmel (University of Koblenz, Germany) Description Modern software is typically made of heterogeneous sets of software artifacts including for instance databases, programs, transformations, grammars, models and metamodels, compilers, interpreters, formats, ontologies, frameworks, APIs, schemas, configuration files, makefiles, etc. In practice particular languages, tools, implementations, and standards are used such as SQL DDL, Saxon, XLST, Java, Hibernate, XSD, OWL, DOM, Antlr, UML, XMI, Ecore, Awk, and so on. In the absence of a conceptual framework it is difficult to understand the relationships between these software artifacts, if any. The goal of this tutorial is to provide such a framework, showing that the similarity and relationships between techniques can be modeled at a high level of abstraction, and even more importantly that recurring patterns occur

The essence of "The essence of functional programming"

Code for all my Channel9 videos is now hosted  here . If "code is the essence", then this blog post is concerned with the essence of "The essence of functional programming" --- because the post matches a code distribution that is derived from P. Wadler's paper of just that title. The code distribution has two branches: " origin " --- where it indeed stays close to the original code of the paper, and " overhaul " --- where it uses the Haskell's monad/monad transformer library to show some of the examples in modern style. This code has been initially prepared for a Channel9 lecture about monads. The code is available through the SourceForge project developers ; browse the code here ; see the slide deck for the Channel9 lecture here . Here is a more complete reference to Wadler's paper: P. Wadler: The essence of functional programming http://doi.acm.org/10.1145/143165.143169 POPL 1992 Henceforth, we refer to thi

Bulk mailing for your conferences not appreciated

Dear Dr. Nagib Callaos, For some years now, my mailbox is flooded by CFPs for your many conferences such as WMSCI 2011 (for which you are General Chair etc.). My email address is rlaemmel@gmail.com. Please remove me from your bulk mailing system. (I have tried your instructions for unsubscribing in the past, obviously, w/o success.) Keep up the good work . Thanks, Ralf Lämmel PS: It is not easy to set up a mail filter that addresses this problem reliably over the years. Or does anyone have an idea as to how to stretch gmail's filter mechanism? I can think of a rule that checks whether a) we face a CFP or some other form of conference ad, and b) certain keywords (names) occur on the website of the conference. Now, gmail, please provide us with that expressiveness :-)

A bunch of interpreters using CPP and Haskell

Introduction This text is about the code distribution that you find here (@ SourceForge project developers ). Released: 24 Aug 2010 Last updated: 31 Aug 2010 We walk through the evolution of a simple interpreter. This exercise is meant to explore functional programming in the context of language interpreters. We start from a trivial language which can generate natural numbers. Step by step, we add some language constructs that make us deal with partiality of interpretation, type tests, a binding mechanism, and different forms of recursion. None of these evolution steps are particularly advanced. The contribution of this code distribution lies more in the pedagogical style of making simple, well-understood extensions, and reflecting on the functional programming issues that pop up as well as the code-level organization and reusability that is achievable. (For the actual reflection, I recommend the upcoming Channel9 lecture on language interpretation that will use some part of the code

Lecture series on advanced (functional) programming concepts

[ Added 10 Aug 2010: Here is the link to the first lecture's video: " The Expression Problem ". ] If you are a programming nerd or something of a similar species, you may know of C9 Lectures at http://channel9.msdn.com/tags/C9+Lectures . Several of the lectures are given by Erik Meijer who has turned many chapters of Graham Hutton 's book " Programming in Haskell " into videos. In my recent, recorded lecture on " Programming Paradigms and Formal Semantics ", I also incorporated Graham's text, but you should really watch Erik's lectures, if you haven't---they are more fun. I am inspired by his ability to present relatively simple content in such a crisp, insightful, and enjoyable manner. In the aforementioned lecture, I covered all kinds of "crazy stuff" though, and in the end, I had to deliver body bags to my Bachelor students---in the form of a radically simple examination. Thanks a lot btw to @grammarware for helping with t

Software adaptation in Koblenz in Sep --- Summer School

Please spread the message. Looking forward the 1st ADAPT Summer School. Regards, PF CALL FOR PARTICIPATION : ADAPT 2010 1st ADAPT Summer School September 26 - October 2, 2010, Koblenz, Germany http://adapt.uni-koblenz.de/summerschool2010 Software adaptation is a topic that crosscuts much of software engineering, programming languages, information systems, formal methods, and other major areas of computer science. The CS department at the University of Koblenz-Landau engages in a research focus on software adaptation, and thereby connects scientists and teams in classical areas of computer science as much as application areas such as web-based systems, SOA, mobile systems, and robotics. ADAPT 2010 is the first edition in a series of summer schools on software adaptation. The program of ADAPT 2010 appeals to PhD students and possibly specialized Master's students in computer science.

A solution to the Halting problem

[ This is not about this Halting problem . ] The Halting problem The problem is how to halt execution of Ali Hussain Sibat. I cite CNN as of 31 March 2010 : "A Lebanese man charged with sorcery and sentenced to death in Saudi Arabia is scheduled to be beheaded on Friday [PF: 2 April] the man's lawyer said Wednesday [PF: 31 March]." Amnesty International has reported about this case on 8 Dec 2009 [ Article from the Amnesty International Website ]. I became aware of the case by CNN's article on 19 Mar 2010 . Update : CNN reported on Thursday, 1 April 2010 that Sibat "won't face beheading Friday [PF: 2 April], his lawyer said Thursday [PF: 1 April]". The solution to the Halting problem I am pretty sure that Sibat's lawyer, his family, Amnesty International, Lebanese government and many other individuals and organizations are working frantically to stop the beheading. Here is an online petition that I ask you to sign if you agree with me that sorcery d

Proprietary hardware jokes

Suppose you own a 2007 model of the then-cutting-edge, high-end laptop of a given brand A with say 4 GB of Ram, an 2.4 GHz Intel Core 2 Duo. Further suppose you want to purchase the current display offering of the same brand (available since Oct 2008), wouldn't you expect to be able connecting both expensive pieces of hardware without yet further investment, say without purchasing a converter that's not even available from brand A? Of course, I should get a 2010 model of an A-branded laptop, and everything works fine until I guess 2011, when they replace the Mini DisplayPort by say a new "Nano DVI port". Suppose you are very happy with the display, the computing power, the browser speed of your lovely smartphone, again from the same brand A. Occasionally, you would like to write some longer emails or edit online documents, or ride on a wave, for which it would make terribly sense to have an external keyboard. Technically, it is trivial to enable this through bluetooth

Our corpus is your corpus.

[ Here is our P3P corpus , be it your corpus as well. ] Giving away your corpus (in empirical language analysis or elsewhere) is perhaps nothing extremely established, but it's nothing original or strange either. It does make sense a lot! Stop limiting the impact of your research efforts! Stop wasting the time of your community members! Sharing corpora is one of these many good ideas of Research 2.0: see SSE'10 (and friend events ), eScience @ Microsoft, R2oSE , ... Computer Science vs. Science When you do academic CS research in programming- or software development-related contexts , then the culture of validation is these days such that you are often expected to provide online access to your program, application, library, tool, what have you as an implementation or illustration. There are various open-source repositories that are used to this end--as a backend (a storage facility), but any sort of author-hosted download locations are also used widely. In basic terms, if

An ambitious course on programming paradigms, semantics, and types

We have completed this course . I hope others find the design or some of the material helpful. See more about reuse below. Coverage - Parsing and interpretation in Prolog - Basics of small-step and big-step semantics - Basics of untyped and typed lambda calculi - Introduction to Haskell - Basics of denotational semantics - Denotational semantics in Haskell - Basics of static program analysis - Static program analysis in Haskell - OO programming in Haskell - The Expression Problem - Basics of Constraint-Logic Programming - Basics of Process Algebra (CCS) - ... a few more specialized lectures Characteristics - English as the course language - Slides, videos , exercises available online publicly - 42 hours (45mins each) of lectures over 4 months - 12 programming-oriented, interactive labs - Transparent scheme for midterm and final exam - Heavy reuse of material from other courses - Use of Twitter for notification and aggregation Experiences This course is my only chance to tell many st

Empirical Language Analysis

We have been trying to understand the language P3P . Ok, its pretty simple to say what it is. It's a small (domain-specific, non-executable) language for privacy policies and it's used by web sites and checked by user agents (potentially part of browsers). Arguably, understanding is limited if you look at online samples and syntax definition alone. So we figured we had to understand usage of the language in order to understand the language . Here is the link to the paper: http://userpages.uni-koblenz.de/~laemmel/p3p/ Joint work with Ekaterina Pek Keywords: Software Language Engineering Domain-Specific Languages Empirical Analysis Policy Languages P3P Abstract : P3P is the policy language with which web sites declare the intended use of data that is collected about users of the site. We have systematically collected P3P-based privacy policies from web sites listed in the Google directory, and analysed the resulting corpus with regard to metrics and cloning of policies, adherence

Constructive art on software languages

Image
If you (feel like you) need to explain a piece of art, then something sucks. But I am not saying that Haskell's Tower of Babel is true art. Perhaps it could be called constructive art (or nerdy art). Anyway, I am going to explain you how I constructed this picture. See here for the original twitpic with the tower, but it's included right below for your convenience. This is how you can reproduce the tower: Use something like Mac OS's Keynote to actually assemble the picture. Go through a nifty Haskell project and gather all Haskell 98 extensions. Use one line per pragma and format everything with a proportional font as shown. Sort the extensions (the lines) by the visual length. Results depend on the font chosen. Starting at the bottom, adjust font size per line to get a smooth slide from top to bottom. In my instance, there was some fuzzy effect due to the used proportional font and the tension between the upper case LANGUAGE and the camel-cased name of the extension in e

Palindrom dates

@lizettegagne re-tweeted as follows earlier today (or yesterday +/-): "RT @mashable: Happy Palindrome Day everyone - 01022010! Last one was 10022001, prior to that 08311380!! Wow! They don't come around often." I hacked up the following Prolog code to get some certainty. Simple modification reveals that European ordering or YYYYMMDD ordering would lead to entirely different results. Try it out! PF ?- main. 08311380 10022001 01022010 true. % This is what a palindrom is ... palindrom(S) :- reverse(S,S). % Generate all palindrom dates; ignoring leap years. special(MDYS) :- year(_,YS), month(M,MS), day(M,_,DS), append(MS,DS,MDS), append(MDS,YS,MDYS), palindrom(MDYS). % Here is an over-approximation of dates. year(X,S) :- ranges(4,1380,2010,X,S). month(X,S) :- ranges(2,1,12,X,S). day(1,X,S) :- ranges(2,1,31,X,S). day(2,X,S) :- ranges(2,1,29,X,S). day(3,X,S) :- ranges(2,1,31,X,S). day(4,X,S) :- ranges(2,1,30,X,S). day(5,X,S) :- ranges(2,1,31,X,S). day(6,X,S) :- rang