Professor Fish

Ein Weihnachtsgedicht

2011-12-08T16:03:00.004+01:00

(C) Professor Fish, aka Ralf Lämmel

Stille Nacht! Unheilvolle Nacht!

Alles schläft; einsam wacht

nur der Bachelor-Student,

der nie pennt,

der nur rennt.

So viele Prüfungen, o weh!

Stille Nacht! Unheilvolle Nacht!

Die wird wieder durchgemacht.

Bester Student, o wie lacht

bös' aus Deinem Gesicht

die Aversion gegen Bologna's Gericht.

So viele Regularien, o weh!

Stille Nacht! Unheilvolle Nacht!

Was hat man nur aus dem Uni-Studium gemacht?

Es ist nicht Bologna allein.

Andere Trends reihen sich hier ein.

Das Denken an Deutschland in der Nacht,

hat auch den Professor um den Schlaf gebracht.

Lautes Land! Unheilvolles Land!

O Marx, gib mir Eltern,

die Kinder fordern anstatt Lehrer zu quälen.

O Lenin, gib mir Erstsemester,

die wissen wollen anstatt videozugamen.

Früher war alles besser, o weh!

Stille Nacht! Unheilvolle Nacht!

Soll es Weihnachten nun sein,

dann Tod den Enten und glühe der Wein.

Der Wunschzettel ist auch schon da.

Merkel & Co. machen es klar.

A riddle regarding type safety

2011-12-07T12:22:00.003+01:00

Of course, I have explained to the students in my language theory class what type safety means (remember: progress + preservation) and we have studied this notion time and again for some of the TAPL languages. However, I don't feel like the notion really sinked in universally. Some students consider all this semantics and calculus stuff as obscure and there is a certain critical mass of notation, when passed, concepts are not understood anymore (by some if not many of the Bachelor-level students in my class).

Last night, I came up with a nice "semantics riddle" for type safety:

What would be a super-trivial language with a type system and an SOS semantics such that type safety is violated?

I gave the students 2 minutes to think about the question.

I emphasized several times that the language should be super-trivial.

I also asked them for a general strategy for mis-designing a language to be type-unsafe.

One idea that popped up was to support some notion of cast.

We agreed that this would not be trivial, certainly not super-trivial.

Here is my reference solution:

Syntax of expressions

e ::= v | z

(Hence, there are expressions (forms) x, y and z.)

Values (normal forms)

v := x | y

Types

t ::= a | b

(a and b are the possible types.)

Small-step relation

z -> x

(Yes, we only have one axiom.)

Typing rules

x : a

y : b

z : b

(Yes, we have only axioms here.)

Demonstration of lack of type safety

The term z is the culprit.

z : b but z -> x and x : a

Regards,

Ralf

A more serious online partial evaluator

2011-05-30T06:49:00.007+02:00

Admittedly, the illustrative partial evaluator of the previous blog post was quite limited. Consider, for example, the following attempts of partially evaluating different applications of the exponentiation function; the last attempt diverges:


> peval (lib, (Apply "exp" [Const 2, Const 3]))
Const 8

> peval (lib, (Apply "exp" [Var "x", Const 3]))
Binary Times (Var "x") (Binary Times (Var "x") (Binary Times (Var "x")(Const 1)))

> peval (lib, (Apply "exp" [Const 2, Var "n"]))
IfZero (Var "n") (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Var "n") (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero (Binary Plus (Binary Plus (Binary Plus (Binary Plus (Var "n") (Const (-1))) (Const (-1))) (Const (-1))) (Const (-1))) (Const 1) (Binary Times (Const 2) (IfZero ...

In the first attempt, we partially evaluate a ground term, which is as if we were using the regular interpreter. In the second attempt, we leave the base parametric, but we fix the exponent. In the third attempt, it is the other way around: we fix the base, but we leave the exponent parametric. The divergence for the third attempt is clearly undesirable. Ideally, partial evaluation of a non-ground term t should terminate whenever there is an ground instance t' of t such that regular evaluation terminates for t'. Otherwise, we could never be sure whether we can safely decompose a computation into partial evaluation followed by evaluation of the residual program.

So let us develop a more advanced partial evaluator:


peval :: Prog -> (Expr, FEnv)

The result type has changed. In addition to a transformed main expression, we also expect to obtain specialized function definitions as they are encountered by partial evaluation. That is, function definitions are specialized by statically known argument values. A demo helps:


> peval (lib, (Apply "exp" [Var "x", Const 3]))
( Apply "exp_[(n,3)]" [Var "x"],
  [("exp_[(n,3)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,2)]" [Var "x"]])),
   ("exp_[(n,2)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,1)]" [Var "x"]])),
   ("exp_[(n,1)]", (["x"], Apply "times" [Var "x",Apply "exp_[(n,0)]" [Var "x"]])),
   ("exp_[(n,0)]", (["x"], Const 1))])

Thus, specialized function definitions were inferred for all the inductively encountered values for the exponent. Subject to a simple inlining optimization (which is not shown here for brevity but included into the open-source repository), we obtain the familiar expression for "x" to the power 3:


Apply "times" [Var "x",Apply "times" [Var "x",Apply "times" [Var "x",Const 1]]]

The partial evaluator commences as follows:


peval :: Prog -> (Expr, FEnv)
peval (fe,m) = runState (peval' m []) []
 where
  peval' :: Expr -> VEnv -> State FEnv Expr

That is, the expression-level partial evaluation function starts from the empty variable environment and it uses the state monad to aggregate specialized function definitions, starting also from the empty list. The type of variable environments is the same as in the original interpreter:


type VEnv = [(String,Int)]

The cases for all constructs but function application can be adopted from the simpler partial evaluator--except that we need to convert to monadic style:


  peval' :: Expr -> VEnv -> State FEnv Expr 
  peval' (Const i) ve = return (Const i)
  peval' (Var x) ve
   = return (case lookup x ve of
              Just v -> Const v
              Nothing -> Var x)
  peval' (Binary op e1 e2) ve
   = do
        e1' <- peval' e1 ve
        e2' <- peval' e2 ve
        return (case (e1', e2') of 
                 (Const v1, Const v2) -> Const (op2f op v1 v2)
                 _ -> Binary op e1' e2')
  peval' (IfZero e1 e2 e3) ve
   = do
        e1' <- peval' e1 ve
        case e1' of 
          (Const v1) -> if (v1==0) then r2 else r3
          _ -> r2 >>= \e2' -> r3 >>= \e3' -> return (IfZero e1' e2' e3')
   where
    r2 = peval' e2 ve
    r3 = peval' e3 ve

The deviating and complicated and interesting case is the one for function application. We prepare this development by an informal specification. (Thanks again to William Cook for teaching me on this part.) The following specification relies on two important terms used in partial evaluation. That is, when partial evaluation encounters a function application with a value (say, a constant---as opposed to an expression) for a given argument position, then this position (or the associated variable) is called static; otherwise, it is called dynamic. The specification follows.

1. The applied function is looked up. 2. The arguments of the function application are partially evaluated. 3. The arguments are partitioned into static and dynamic ones. 4. The specialized function name consists of the original function name qualified by the static arguments. 5. The body of the specialized funtion is obtained by partially evaluating the original body in the variable envrironment of the static variables. 6. An application of the specialized function is constructed from the dynamic arguments. This is the result of partial evaluation.

The following function definition clarifies the step of partitioning the partially evaluated arguments (see 3. above). One list of
expressions is partioned into two lists of static versus dynamic arguments qualified by the formal argument names. Static arguments are Const expressions. Dynamic arguments are all other expressions. Thus:


    partition [] [] = ([],[])
    partition (n:ns) (Const i:es)
     = ((n,i):ss,ds) where (ss,ds) = partition ns es
    partition (n:ns) (e:es)
     = (ss,(n,e):ds) where (ss,ds) = partition ns es

The following equation for function applications implements the afore-mentioned steps 1.-6., but additional details
arise. In order to deal with recursion, it is important that the specialized function is already added to the state before its body is
obtained. To this end, an undefined body is preliminarily associated with the new name, which is replaced later; see get, put, get, put. Furher, we need to distunguish function applications that are fully static from those that involve dynamic arguments because fully static function applications should not be specialized; instead, they should be evaluated.

Here are the glory details:


  peval' (Apply n es) ve
   = do
     -- Look up function
     let (ns,e) = fromJust (lookup n fe)

     -- Partially evaluate arguments
     es' <- mapM (flip peval' ve) es

     -- Partition arguments into static and dynamic ones
     let (ss,ds) = partition ns es'

     case (null ss, null ds) of

       -- A constant application
       (True, True) -> peval' e []

       -- A fully static application
       (False, True) -> peval' e ss

       -- A fully dynamic application
       (True, False) -> return (Apply n es')

       -- A mixed static application
       (False, False) -> (do

         -- The name that encodes the static values
         let n' = n ++ "_" ++ myshowl ss

         -- Construct application of specialized function
         let e' = Apply n' (map snd ds)
        
         -- See whether the specialization exists already           
         fe <- get
         case lookup n' fe of
           Just _ -> return e'
           Nothing -> (do 

             -- Memo before possible recursion
             put (fe++[(n',undefined)])

             -- Partial evaluation of function body
             e'' <- peval' e ss

             -- Record definition of specialized function
             fe' <- get
             put (update (const (map fst ds,e'')) n' fe')

             -- Return application of specialized function
             return e'))

So much for partial evaluation.

Regards,
PF

PS: The source code of this blog post is available through the repository of the Software Language Processing Suite; see here.

An illustrative online partial evaluator

2011-05-27T12:00:00.024+02:00

Let's understand the basic mechanics of a (too?) simple online partial evaluator. (I am grateful to William Cook for encouraging the following Haskell exercise, and for sharing with me some stimulating slides and notes on the subject.) I recommend John Hatcliff's excellent and detailed course material on "Foundations of Partial Evaluation and Program Specialization"---available online. For those in a hurry, try Wikipedia. Anyway, partial evaluation, macro systems, and multi-stage programming is a lot of fun. Here is also a paper (draft) by William Cook that I can warmly recommend.

Consider the following syntax of a simple, pure, first-order, functional programming language:


type Prog = (FEnv,Expr)
type FEnv = [FDef]
type FDef = (String,([String],Expr))

data Expr
 = Const Int
 | Var String
 | Binary Op Expr Expr
 | IfZero Expr Expr Expr
 | Apply String [Expr]
 deriving (Show)

data Op = Plus | Times
 deriving (Show)

Thus, a program consists of a main expression and bindings for functions (i.e., a "function environment" FEnv is a list of "function definitions" FDef each of them being of term form (s,(ss,e)) with s as the function name, ss the formal parameters and e the body). Evaluation of an expression is supposed to return an integer (or to diverge or to fail in reply to a dynamic type error). The functions are supposed to be of first-order: functions are neither passed as arguments, nor returned as results.

Here are some function definitions---including those for factorial and exponentiation:


lib :: FEnv
lib
 = [ ("neg", (["x"], Binary Times (Var "x") (Const (-1)))),
     ("add", (["x", "y"], Binary Plus (Var "x") (Var "y"))),
     ("minus", (["x", "y"], Binary Plus (Var "x") (Apply "neg" [Var "y"]))),
     ("times", (["x", "y"], Binary Times (Var "x") (Var "y"))),
     ("inc", (["x"], Binary Plus (Var "x") (Const 1))),
     ("dec", (["x"], Binary Plus (Var "x") (Const (-1)))),

     ("fac",
       ( ["x"]
       , IfZero (Var "x")
           (Const 1)
           (Apply "times" [Var "x", Apply "fac" [Apply "dec" [Var "x"]]]))),

     ("exp",
       ( ["x","n"]
       , IfZero (Var "n")
           (Const 1)
           (Apply "times" [Var "x", Apply "exp" [Var "x", Apply "dec" [Var "n"]]])))]

Let's first develop a straightforward interpreter.

We expect interpretation to behave as follows:


> eval (lib, Apply "fac" [Const 5])
120
> eval (lib, Apply "exp" [Const 2, Const 3])
8

Here is the complete interpreter:


type VEnv = [(String,Int)]

eval :: Prog -> Int
eval (fe,m) = eval' m []
 where
  eval' :: Expr -> VEnv -> Int
  eval' (Const i) ve = i
  eval' (Var x) ve = fromJust (lookup x ve)
  eval' (Binary op e1 e2) ve = f v1 v2
   where
    f  = op2f op
    v1 = eval' e1 ve
    v2 = eval' e2 ve
  eval' (IfZero e1 e2 e3) ve = if (v1==0) then v2 else v3
   where
    v1 = eval' e1 ve
    v2 = eval' e2 ve
    v3 = eval' e3 ve
  eval' (Apply n es) ve = eval' e ve'
   where
    (ns,e) = fromJust (lookup n fe)
    vs = map (\e -> eval' e ve) es
    ve' = zip ns vs

op2f :: Op -> (Int -> Int -> Int)
op2f Plus = (+) 
op2f Times = (*)

It must be emphasized that this interpreter is in no way special, unusual, or targeted at partial evaluation. One gets this interpreter naturally when using denotational semantics (i.e., compositional functional semantics) as the guiding principle. Now the key "challenge" of our effort here is to modify the interpreter so that it effectively serves as a partial evaluator. That is, the partial evaluator should produce the same result as the interpreter when faced with a ground main expression, but it should compute a residual expression otherwise. Let's think of the residual expression as the "rest of the program" that needs to be evaluated once the free variables are bound to values. For instance:


> peval (lib, Apply "exp" [Var "x", Const 3])
Binary Times (Var "x") (Binary Times (Var "x") (Binary Times (Var "x") (Const 1)))

Thus, the function "exp" is applied to a specific exponent 3, but the base remains a variable "x", and the result of partial evaluation essentially represents the code to compute "x" to the power 3: "x*x*x*1".

Our design of a partial evaluator starts from the insight that the type of the top-level function must be changed so that expressions are returned instead of integers. (A more general design would also return any number of bindings for specialized functions that were encountered along partial evaluation.) Please note that integers are trivially embedded into expressions through the constant form of expressions. Thus:


-- Interpreter
eval :: Prog -> Int
eval (fe,m) = eval' m []
 where
  ...

-- Partial evaluator
peval :: Prog -> Expr
peval (fe,m) = peval' m []
 where
  ...

In the chosen style of partial evaluator design, we also propagate the type change into the definition of variable environments. (This leads to a simple development, but implies some issues as we will discuss towards the end of the blog post.) Thus, variables may be bound to (free) variables:


-- Interpreter
type VEnv = [(String,Int)]

-- Partial evaluator
type VEnv = [(String,Expr)]

The cases for constant expressions differ trivially only as follows:


-- Interpreter
  eval' :: Expr -> VEnv -> Int
  eval' (Const i) ve = i

-- Partial evaluator
  peval' :: Expr -> VEnv -> Expr
  peval' (Const i) ve = Const i

Variables are to be treated in a special manner. The interpreter can only deal with ground main expressions, and---subject to other reasonable assumptions about well-typedness of programs---variables would always be bound throughout interpretation. In contrast, the partial evaluator faithfully deals with free variables: a free variable is partially evaluated to itself.


-- Interpreter
  eval' (Var x) ve = fromJust (lookup x ve)

-- Partial evaluator
  peval' (Var x) ve
   = case lookup x ve of
      Just e -> e
      Nothing -> Var x

Compound expression forms are also affected non-trivially but systematically. The general idea is that an expression form may be evaluated if some or all operands can be, in turn, partially evaluated to values, or the expression form may need to be re-generated in the result otherwise. Consider the following cases for binary expressions:


-- Interpreter
  eval' (Binary op e1 e2) ve = f v1 v2
   where
    f  = op2f op
    v1 = eval' e1 ve
    v2 = eval' e2 ve

-- Partial evaluator
  peval' (Binary op e1 e2) ve
   = case (e1', e2') of 
      (Const v1, Const v2) -> Const (f v1 v2)
      _ -> Binary op e1' e2'
   where
    f  = op2f op
    e1' = peval' e1 ve
    e2' = peval' e2 ve

Thus, in the interpreter, subexpressions are recursively evaluated, and the corresponding operator is applied to the intermediate results. Subexpressions are also recursively evaluated in the partial evaluator, but the intermediate results are to be checked this time such that the operator is applied for the case of value results (constants). Otherwise, a binary expression is generated which incorporates partially evaluated operands as opposed to the original operand expressions.

The same idea is applied to the IsZero construct:


-- Interpreter
  eval' (IfZero e1 e2 e3) ve = if (v1==0) then v2 else v3
   where
    v1 = eval' e1 ve
    v2 = eval' e2 ve
    v3 = eval' e3 ve

-- Partial evaluator
  peval' (IfZero e1 e2 e3) ve
   = case e1' of
      (Const v1) -> if (v1==0) then e2' else e3'
      _ -> IfZero e1' e2' e3'
   where
    e1' = peval' e1 ve
    e2' = peval' e2 ve
    e3' = peval' e3 ve

The pleasant status of IfZero is that it is enough to partially evaluate the condition to a value in order to be able to eliminate the conditional form.

Perhaps surprisingly, the cases for function application can be identical (modulo renaming):


-- Interpreter
  eval' (Apply n es) ve = eval' e ve'
   where
    (ns,e) = fromJust (lookup n fe)
    vs = map (\e -> eval' e ve) es
    ve' = zip ns vs

-- Partial evaluator
  peval' (Apply n es) ve = peval' e ve'
   where
    (ns,e) = fromJust (lookup n fe)
    es' = map (\e -> peval' e ve) es
    ve' = zip ns es'

In both cases, we look up the function from the function environment, we bind (partially) evaluated actual parameters to the formal parameter variables, and we proceed with the (partial) evaluation of the function's body relative to the local environment.

Exercise: Is there any issue of variable capture with the partial evaluator at hand? Can you demonstrate a problem? How would you generally rule out variable capture? Further, can you think of situations where the partial evaluator clones too much code or where it even loops, even though a non-cloning and non-looping partial evaluator would be desirable and feasible, perhaps subject to some form of memoization?

The source code of this blog post is available in the repository for the Software Language Processing Suite; see here. You would also find a not so simple partial evaluator discussed in the next blog post.

Regards,
PF

Empirical studies of software languages

2011-05-14T00:03:00.007+02:00

Dear language researchers and engineers,

if you were interested in empirical studies of software languages, what journals and conferences come to your mind as potential publication venues for such studies? In different terms, what do you think what quality journals and conferences would be popping up if you were googling (binging) intelligently for empirical studies of programming languages, modeling languages, domain-specific languages, and other software languages you can think of?

Please send your ideas by email to rlaemmel@acm.org by 19 May.

The results of this inquiry will be published while preserving anonymity of all participants.

Thanks!

Professor Fish

PS1: The reason for asking is that we are into a meta-empirical effort, continuing our SLE 2010 paper "Empirical language analysis in software linguistics" (Jean-Marie Favre and Dragan Gasevic and Ralf Lämmel and Ekaterina Pek). We are going to use content analysis, where we aim for automation for data mining to the extent possible, but substantial manual efforts remain. Therefore, scalability is limited, and we would like to narrow down the search space for relevant publications by using a short list of journals and conferences, but, at the same time, remaining transparent about what we use. So please, in the interest of science, send your journal and conference acronyms.

PS2: Please understand that I do not include any journals and conferences that are already on our mind. I do not want to bias you in any way. This is also the reason for disabling comments on this post.

Language processing for dummies

2011-05-08T04:29:00.002+02:00

I enjoyed reading recently "Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages" by Terence Parr (the ANTLR guy) as available from The Pragmatic Bookshelf. The book uses a design pattern style to present techniques for language processing. Eventually the book gets to leverage ANTLR for many problems, but it also explains language processing in terms of patterns that require regular programming effort without the help of a program generator. This is a clever way of teaching some basics of grammars, parsing, tree walking and other concepts that can be explained all too easily (elsewhere) in a too complicated manner, or in a manner requiring substantial background.

In my (very) advanced Bachelor's course Programming techniques and technologies, I face students who don't know much yet about formal languages and certainly nothing about compiler construction; they are aware though of context-free grammars (EBNFs) for the purpose of syntax definition. The course covers many programming techniques and technologies, and I am willing to dedicate two lectures to language processing. Hence, I designed patterns that are really simple and that allow me to discuss a number of language processors for 101companies in a systematic manner.

"Manual" patterns

The Chopper Pattern: Chop input into pieces for classification and iterator-based processing.
The Lexer Pattern: Transform character stream into token stream for iterator-based processing.
The Copy/Replace Pattern: Implement text transformation by copying tokens from input to output while replacing tokens of interest.
The Acceptor Pattern: Implement a context-free grammar with procedures for parsing input and signaling acceptance or rejection.
The Parser Pattern: Advance the Acceptor Pattern such that semantic actions are to be executed along with parsing input.

"Generative" patterns

The Lexer Generation Pattern: Use a lexer/parser generator to derive a character-to-token stream conversion from a grammar generatively.
The Acceptor Generation Pattern: Use a parser generator to derive an acceptor from a grammar generatively.
The Parser Generation Pattern: Use a parser generator to derive an parser from a grammar with associated semantic actions generatively.
The Text-to-object Pattern: Instantiate the Parser (Generation) Pattern such that the semantic actions construct objects that resemble the syntactical structure of the input.
The Object-to-text Pattern: Implement an operation on an object model that writes out the object graph in the underlying textual notation.

Associated 101companies implementations

Slide decks (.pdf): [1]. [2]

Lecture videos (.mov): [1]. [2]

Regards,

A tiny attribute grammar exercise

2011-05-05T09:39:00.009+02:00

(C) 2011, Ralf Laemmel

Let's map Knuth' attribute grammar example to Haskell. This has been done many times. In fact, there is a long track of excellent research on the relation between attribute grammars and functional programming. For instance, see the work by Doaitse Swierstra and team over many years. Our development here is meant to just illustrate the basic mapping in an as simple and self-contained manner as possible.

One should notice that the chosen example (due to Knuth) requires laziness for the straightforward encoding that is leveraged
below. Hence, C programmers are encouraged to try to transcribe this Haskell program to their favorite language.

The following context-free grammar is assumed:


digit : '0'
digit : '1'
digits : digit
digits : digits digit
number : digits
number : digits '.' digits

That is, we deal with binary numbers---both integer and fractional numbers.

We use the following algebraic datatypes to model the grammar:


data Digit = Zero | One
data Digits = Single Digit | Several Digits Digit 
data Number = Int Digits | Frac Digits Digits

Let us now associate attributes with the nonterminals:


* digit:
  - inh. p -- position of digit
  - syn. v -- value of digit
* digits:
  - inh. p -- position of digits
  - syn. v -- value of digits
  - syn. l -- length of digits
* number:
  - syn. v -- value of number

In Haskell, we can introduce designated type aliases to capture the names of the attributes, and the association of nonterminals with attributes is modeled with the signatures for functions that are expected to model the semantic equations. (We could also use record types, but Haskell's record system is not quite convenient in this context.) Here, the assumption is that those functions carry one argument for the syntactial part, another argument for (the tuple of) the inherited attributes, and the result corresponds to (the tuple of) the synthesized attributes. Thus:


-- Type synonyms for attributes
type Val = Float
type Pos = Int
type Len = Int

-- Functions for semantic equations
digit :: Digit -> Pos -> Val
digits :: Digits -> Pos -> (Val,Len)
number :: Number -> Val

Here are the semantic equations for the example:


digit : '0'
  v.digit = 0

digit : '1'
  v.digit = 2^^p.digit

digits : digit
  v.digits = v.digit
  l.digits = 1
  p.digit = p.digits

digits : digits' digit
  v.digits = v.digits' + v.digit
  p.digit = p.digits
  p.digits' = p.digits + 1
  l.digits = l.digits' + 1

number : digits
  v.number = v.digits
  p.digits = 0

number : digits '.' digits'
  v.number = v.digits + v.digits'
  p.digits = 0
  p.digits' = -l.digits'

We implement these semantic equations as equations defining the functions from syntax times inherited attributes to synthesized attributes.


digit Zero _ = 0
digit One p = 2^^p

digits (Single d) p = (digit d p,1)
digits (Several ds d) p = (v,l)
 where
  v = v' + v''
  l = l' + 1
  (v',l') = digits ds (p+1)
  v'' = digit d p

number (Int ds) = fst (digits ds 0)
number (Frac ds1 ds2) = v1+v2
 where
  (v1,l1) = digits ds1 0
  (v2,l2) = digits ds2 (-l2)

Let us evaluate 10.01.


main = do print (number n)
 where
  n = Frac ds ds'
  ds = Several (Single One) Zero
  ds' = Several (Single Zero) One

> main
2.25

Regards,
Prof. Fisch

Test-driven grammar-class understanding with ANTLR

2011-04-28T17:14:00.006+02:00

Suppose you would like to understand some grammar classes such as LL(1) and LL(*). Then you might appreciate a test suite like the following, or you would actually try to discover such a test suite yourself. I used the following suite in a lab of my "Software Language Processing" class. It is very convenient means of illustrating things. Students can copy and paste these codes now and further investigate. It helps understanding formal notions and actual, operational parser behaviors.

The first ANTLR input specifies a trivial grammar with a fixed lookahead of 1.

grammar LL1;
options { k = 1; }
s : 'a' 'x' | 'b' 'x' ;

Let's apply ANTLR:

java -classpath ".:antlr-3.2.jar" org.antlr.Tool LL1.g

ANTLR likes that grammar just fine. (There are no complains.) We are allowed to infer hence that the grammar is indeed LL(1).

The next ANTLR input combines two alternatives that are clearly not LL(1). However, we still use a lookahead of 1.

grammar NotLL1;
options { k = 1; }
s : 'a' 'x' | 'a' 'y';

Let's apply ANTLR again:

java -classpath ".:antlr-3.2.jar" org.antlr.Tool NotLL1.g
warning(200): NotLL1.g:3:3: Decision can match input such as "'a'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): NotLL1.g:3:3: The following alternatives can never be matched: 2

That is, ANTLR complains that both alternatives are to be selected with the same lookahead, and hence, ANTLR announces effectively that it will (pragmatically) favor the first alternative. As a result, the second alternative can never be matched operationally.

The next ANTLR input is basically the same as before except that we use a lookahead of 2 now.

grammar LL2;
options { k = 2; }
s : 'a' 'x' | 'a' 'y';

The grammar is indeed LL(2). ANTLR likes the grammar just fine.

The next ANTLR input goes back to lookahead 1 but it enables backtracking.

grammar Backtracking;
options { backtrack = true; k = 1; }
s : 'a' 'x' | 'a' 'y';

With backtracking turned on, ANTLR just gracefully accepts the grammar even with the insufficient look ahead. It is easy to guess that the operational behavior will combine use of lookahead for the optimization of decisions with the use of backtracking for completeness. That is, whenever input cannot be matched on the grounds of lookahead-based decisions, then additional choices are to be explored through backtracking.

The next ANTLR input explores the ANTLR semantics of backtracking. That is, we retain the same grammar as before---except that we inject a semantic action for output into the first alternative---just to see whether semantic actions will be prematurely executed---even if an alternative will not be completed, and a different alternative is chosen by backtracking eventually.

grammar Delay;
options { backtrack = true; k = 1; }
s : 'a' { System.out.println(42); } 'b' 'x' | 'a' 'b' 'y';

When we apply the generated parser for the grammar to the input "aby", then no output will be printed. That is, the parser explores the alternative with the semantic action first, but it delays execution of semantic actions. Such delayed actions are a safe choice when backtracking is involved.

The next ANTLR input starts two alternatives with a kind of prefix that rules out finite lookahead for deterministic decisions.

grammar Not42;
options { k = 42; }
s : 'a'* 'x' | 'a'* 'y';

In particular, the grammar is not LL(42). This is how ANTLR reports the problem:

java -classpath ".:antlr-3.2.jar" org.antlr.Tool Not42.g
warning(200): Not42.g:3:3: Decision can match input such as "'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a' 'a'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

Hence, a parser based on lookahead of 42 would not be able to make the right decision for longer inputs.

The next ANTLR input simply removes the LL(k) option. Thereby, ANTLR's infinite lookahead applies.

grammar LLstar;
s : 'a'* 'x' | 'a'* 'y';

Indeed, ANTLR likes the grammar just fine. The grammar is hence LL(*).

The next ANTLR input starts two alternatives with a kind of prefix that rules out even infinite (DFA-based) lookahead for deterministic decisions. A recursive nonterminal is used which clearly rules out DFAs for lookahead.

grammar NotLLstar;
s : p 'x' | p 'y';
p : 'a' p 'b' | ;

Indeed, ANTLR complains.

java -classpath ".:antlr-3.2.jar" org.antlr.Tool NotLLstar.g
error(211): NotLLstar.g:2:3: [fatal] rule s has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
make: [NotLLstar.gen] Error 1 (ignored)

ANTLR basically suggests a few options which are all worth investigating: factoring, syntactic predicates, and backtracking.

Let's try factoring first. It does not take a rocket grammar engineer to even guess that we get back to LL(1):

grammar Factoring;
options { k = 1; }
s : p ('x' | 'y');
p : 'a' p 'b' | ;

Indeed, ANTLR likes the grammar just fine. We quickly transitioned from non-LL(*) to LL(1).

Now let's try syntactic predicates. That is, we attach essentially grammar expressions as guards to the alternatives:

grammar SynPreds;
s : (p 'x') => p 'x'
 | (p 'y') => p 'y';
p : 'a' p 'b' | ;

ANTLR also is Ok with that grammar. However, we should not expect too much. Essentially, we are using an operational semantics now such that the first alternative is tried first subject to the syntactic predicate to be satisfied; otherwise we continue with the second alternative which is guarded as well. No formal property for the predicates is to be checked. All reasoning is based on order. From a practical point of view, the predicates at hand are somewhat terrible because they actually run the complete alternative in the guard. (We simulate backtracking in a sense.) We should try to find a shorter prefix for the test, but this is impossible in the example at hand. However, even guards that test a lot of the actual alternative may be efficient if we could additionally leverage memoization, but we do not attempt this here.

It is reasonable to turn on backtracking again. In this case, the grammar itself does not need to be transformed:

grammar Desperate;
options { backtrack = true; }
s : p 'x' | p 'y';
p : 'a' p 'b' | ;

We can parse just fine with that grammar. Demo omitted. Of course, efficiency issues are to be expected whenever backtracking is involved, but, again, we could try to leverage memoization in some cases, or we should indeed try to factor---as it is clearly trivial and appropriate in the specific case at hand.

Happy grammar engineering!

Regards,
Ralf

A tiny bit of denotational semantics

2011-01-20T11:44:00.008+01:00

This is actually an assignment for my paradigms/semantics class.

Consider the following super-trivial interpreter written in Haskell and in the direct style of denotational semantics:


data Exp = Const Int
    | Add Exp Exp

eval :: Exp -> Int
eval (Const i) = i
eval (Add x y) = eval x + eval y

It's time to test:


> eval (Add (Const 20) (Const 22))
42

This incredible language handles integer constants and addition. Now assume that we are adding an "exit" form of expression. The intended semantics of a term "Exit e" is to define the final result of expression evaluation as the value of e. Hence, if an exit expression occurs inside an addition, then the addition is effectively cancelled. Thus:


data Exp = Const Int
    | Add Exp Exp
    | Exit Exp

For instance:

Add (Const 20) (Const 22) should evaluate to 42.

Add (Exit (Const 88)) (Const 42) should evaluate to 88.

A particularly clumsy way of writing an interpreter for the extended language is to stubbornly stick to direct style of denotational semantics. That is, we may use, for example, the result type to encode whether we are returning from a normal evaluation or whether we are supposed to exit. In such a case, we have to systematically check intermediate results to propagate exit. In our simple language, we need to propagate in the equation for addition. Thus:


-- Result type for clumsy direct style:
-- The sum serves for tagging.
-- Left tags normal result values.
-- Right tags exit values.
type R = Either Int Int

-- Standard combinator for sum processing
(\/) :: (a -> c) -> (b -> c) -> Either a b -> c
(f \/ g) (Left x)  = f x
(f \/ g) (Right y) = g y

-- Tag removal
toInt :: Either Int Int -> Int
toInt = id \/ id

-- Clumsy semantic function
eval :: Exp -> R
eval (Const i) = con i
eval (Add x y) = add (eval x) (eval y)
eval (Exit x) = exit (eval x)

-- Algebra for denotations
con :: Int -> R
con = Left

add :: R -> R -> R
add x y = ((\x' -> ((Left . (x'+)) \/ Right) y) \/ Right) x

exit :: R -> R
exit = Right . toInt

The clumsy interpreter can indeed be tested as follows:


> toInt (eval (Add (Const 20) (Const 22)))
42
> toInt (eval (Add (Exit (Const 88)) (Const 42)))
88

Here are two trivial assignments that make you understand a) the basics of continuations and b) the relationship between analysis and denotational semantics. 1st assignment: Design an alternative semantics for the extended language so that you exploit continuation style instead of direct style. 2nd assignment: Revise the direct style semantics to derive a program analysis determining the purity of an expression; an expression is pure if it does not contain any reference to the Exit form of expression. Thus, we would like to be able to run tests as follows:


> eval (Add (Const 20) (Const 22)) id
42
> eval (Add (Exit (Const 88)) (Const 42)) id
88
> pure (Add (Const 20) (Const 22))
True
> pure (Add (Exit (Const 88)) (Const 42))
False

(We pass the identity continuation to the applications of eval.)

Regards,

The underappreciated banana and its buddy monoid

2010-12-31T18:22:00.003+01:00

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 such omnipresence of fold, reasoning about our programs may be drastically simplified.

Many bananas team up with monoids. Again, this is great because this tells me that combination of intermediate results along recursive computations is typically quite regular, too. For instance, MapReduce computations for parallel data processing essentially use monoids to aggregate results and to build up indexes. (The monoidal properties enable parallel composition in so far that we can take any segment of input and process it on a separate machine, and such per-machine results can be combined, in fact, reduced later. We also see easily when we need more than just a monoid. For instance, we may need commutativity in order to be even more flexible with parallel processing schedules.) Also, in program analysis, many data processing steps recurse into substructures, and combine intermediate results in a monoidal fashion. It seems that some people mainly think of monoids as numbers and perhaps lists with the usual culprits for binary operation and identity. If you have never used a monoid for pairs or maps, then you should try it as soon as you can.

One may end up obfuscating programs by under-appreciating the fundamental concepts of bananas and monoids for recursion schemes and algebraic computations. For instance, suppose you design a domain-specific language for parallel data processing, and you suggest certain language concepts for data analysis. Wouldn't it be helpful to point out that the key underlying concept is essentially the one of a list homomorphism, which has been heavily studied from a point of view of data parallelism? This is not a conceived example. Sawzall describes a DSL just like that, and it took me a few hours to see that Sawzall's aggregators boil down to a programming scheme for list homomorphisms with interesting monoids. Likewise, the visitor pattern in OO programming is a bit of a chaos, and so it may help to see something as simple and powerful as a large bananas to consider switching paradigms or develop a simpler view on visitors.

I have compiled a lecture with accompanying code base, to appear on Channel9, which discusses a number of use cases for bananas and monoids. I begin with simple uses of foldr meant to show the generality and expressiveness of this great operator; this also includes a quick discussion of those type classes that can be used for folds on container types other than Haskell's concrete list type. (See code module Foldr.hs for this part.) Then I switch to parallel data processing à la MapReduce, and have a lot of fun with map, foldr, monoids, and friends. (See code module MapReduce.hs for this part.) Then, I switch from lists to heterogenous types, as they are used to model problem domains in programming, e.g., dataypes for ASTs used in interpretation, software transformation and analysis. On such AST types, I discuss large bananas, i.e., bananas that possibly handle many constructors, and the "Scrap Your Boilerplate" style of generic functional programming which involves yet other bananas. (See code modules Large.hs and SYB.hs for these two parts.) I had to be selective in the interest of staying close to a 1h lecture. For instance, folds in the sense of Church encodings, functorial style generic programming, or graph traversals remain unmentioned. I also fail to spend significant time on reasoning about the programs at hand, but I give some further reader pointers as usual. Enjoy, and please provide feedback.

Regards
Ralf

A brutalized Haskell programmer

2010-12-21T12:29:00.002+01:00

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

2010-12-13T04:35:00.003+01:00

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 bananas and good accessibility of the subject that is sometimes unjustly considered difficult, if not esoteric. Fold is one of the few swiss army knifes of functional programming. Even if you have to code in Java, knowledge of fold will help you to better understand what you are doing with collections, functors, visitors, or otherwise.

The presentation is structured as follows. First, the basics of higher-order list processing are recalled. Second, folds and friends are examined from the more abstract point of view of iteration over general (abstract) containers as opposed to concrete lists. Third, folds are put to work to serve parallel data processing based on list homomorphisms, and Google's MapReduce and Sawzall approaches are revisited in this context. Fourth, folds are generalized beyond lists, in fact, beyond containers---so that data of arbitrary algebraic datatypes can be processed in catamorphic fashion, thereby entering the area of generic programming. Finally, the "Scrap Your Boilerplate" style of generic programming is presented as a logical continuation of previous work on folds and friends.

Bio: [.html]

Grammar-based Testing Revisited

2010-11-15T04:15:00.004+01:00

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 compliance with the specification. Yet other motivations arise, for example, in the context of DSL design, and, more generally, software language engineering.

Despite all such longstanding and recently renewed interests in grammar-based testing, there is no best practice; there are no standard tools. In this talk, I analyze the current, fragmented, insufficiently automated, predominantly ad-hoc approach. To this end, I survey testing approaches and use cases. Finally, I start infering requirements of a more general approach to grammar-based testing.

This is a good time for revisiting grammar-based testing because some categories of industrial users (e.g., compiler writers, who finally start to use parser generators in products) and several major research communities (such as those working on model-driven engineering and software language engineering) face the need for this sort of testing urgently. Also, there are less obviously related communities who touch upon grammar-based testing needs: think of the grammar-like structures in theorem proving, hardware design, and software-product lines.

Bio: Ralf Lämmel is Professor of Computer Science at University of Koblenz-Landau. In his career, he also served at Microsoft Corp., Free University of Amsterdam, Dutch Center for Mathematics and Computer Science (CWI), and University of Rostock. Ralf Lämmel's speciality is "software language engineering" but he is generally interested in themes that combine software engineering and programming languages. Ralf Lämmel is one of the founding fathers of the international summer school series GTTSE-Generative and Transformational Techniques on Software Engineering and the SLE conference (Software Language

Engineering).

Statistische Analyse der Parkplatz-Situation auf einem Universitätscampus

2010-11-03T10:03:00.002+01:00

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 Fahrzeuge berührten signifikant bzw. übertraten die Trennlinien. Dies sind alarmierende Hinweise.

Beschreibung: Die Arbeit soll geeignete Daten erheben und auswerten---zum Teil auch unter der Verwendung von digitaler Bildtechnik und Analyse (etwa zur Kennzeichenerkennung). Folgende Forschungsfragen werden vorgeschlagen. a) Was ist der Grad der Belegung der Parkflächen? b) Welche Kapazität wird durch Fehlverhalten verschwendet? c) Gibt es Parkplatz-Benutzer, welche statistisch signifikant durch Fehlverhalten auffallen? Der Kandidat soll gern weitere Fragestellungen beitragen.

Gruss,

Towards a megamodel for programming and language technologies

2010-10-11T11:26:00.007+02:00

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 programming courses elsewhere.

In spring 2010, Jean-Marie Favre, Dragan Gasevic and me had an informal workshop in Malaga, where we developed the idea of teaching software languages (or the broader theme of programming and language technologies) in a manner that heavily relies on a) examples; b) comparison; c) megamodeling.

The tutorial and the keynote reveal this idea in more detail.

Your 101companies contributions are welcome.

Regards,

Dealing comfortably with the confusion of tongues

2010-09-14T14:37:00.004+02:00

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 skills more effectively? How would we want to prepare an undergraduate in CS for such toughness? These are the questions that we address in this talk. We put to work a combo of technology modeling, metamodeling, and megamodeling—plus a suite of well-designed examples in any lingo that we could think of. (Contrary to this abstract, the talk is going to be very technical; target audience: software engineers.)

Acknowledgment: This is joint work with Dragan Gasevic and Jean-Marie Favre. Further, I acknowledge contributions by some of my students—most notably Thomas Schmorleiz.

(Mega)modeling Software Language Artifacts

2010-09-13T23:50:00.002+02:00

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 in such models. Some of these patterns, for instance those involving “bridges” between technologies, would be really difficult to grasp without a proper conceptualization. As a result software engineers and researchers usually find it hard to understand the intricacies of technologies that are out of their area of expertise and it is more than likely that they do not realize the analogies that exist between heterogeneous technologies. This tutorial aims to unveil these recurring patterns and to show participants coming from different horizons how to model the technologies they design or work with in an uniform way and how to situate them into the overall software language landscape.

In the first part of the tutorial, the notions of software languages and technical spaces are briefly presented with a special emphasis on their unifying character. Then fundamental relations such RepresentationOf and ElementOf are introduced forming the basis of a (mega)modeling framework. Recurrent patterns based on these relations are then presented, allowing to describe for instance the “conformance” relation between let’s say a program and a grammar, an xml file and an xsd schema, or an uml model and its metamodel, etc. More complex patterns such as bridges between technologies (e.g. XML <==> Relational, OO <==> XML, etc.) are defined following the same approach. Though this notion of bridges seems easy to grasp informally at the first sight, it often leads to a rather large and complex set of technologies that are hard to understand and compare without an appropriate framework.

In the second part of the tutorial, the use of (mega)modeling framework is illustrated through its application in three different technical spaces: Grammarware, Modelware and Ontologyware. Concrete examples of various degree of complexity are provided in each case, with again an emphasis on similarities between technical spaces. The hope of this approach is that it should be possible for someone with some knowledge in technical spaces (let’s say grammarware) to improve significantly his or her comprehension about another space (let’s say ontologyware), and this by virtue of analogy. It is our believe that the (mega)modeling approach, by raising the level of abstraction and focusing on essential software language concepts, enables both to better understand complex structures involving many heterogeneous software artifacts, but also to better apprehend new technologies coming from other spaces.

One of the objectives of the tutorial is to show that bridges can be successfully established between heterogeneous technical spaces such as Modelware, Ontologyware and Grammarware, and in particular to go beyond traditional divisions of fields of expertise. This tutorial being directly inscribed into a “community engineering” perspective, we believe that having three presenters coming from different horizons would be the best way to insist on the integrative aspect of the mega-modeling approach.

Presenters

Jean-Marie Favre is a software anthropologist and a software language archeologist. He is principal scientist at One Tree Technologies. He has published numerous papers and coedited a book (in French) Beyond MDA: Model Driven Engineering. He has given tutorials and keynotes in more than dozen of international events and summer schools and has organized various national and international events. His research interests include software language engineering, software linguistics, software evolution and reverse engineering, model driven engineering and research 2.0.
Dragan Gaševic is a Canada Research Chair in Semantic Technologies and an Associate Professor in the School of Computing and Information Systems at Athabasca University. His research interests include semantic technologies, software language engineering, technology-enhanced learning, and service- oriented architectures. He has (co-)authored numerous research papers and is a led author of the book "Model Driven Engineering and Ontology Development." He has given tutorials at many well-known conferences such as WWW, ISWC, and CAiSE.
Ralf Lämmel is Professor of Computer Science at University of Koblenz-Landau. In his career, he also served at Microsoft Corp., Free University of Amsterdam, Dutch Center for Mathematics and Computer Science (CWI), and University of Rostock. Ralf Lämmel is generally interested in the combination of software engineering and programming languages. Together with the other tutorial speakers and further researchers, he is one of the founding fathers of the SLE conference. He is one of the founding fathers of the summer school series GTTSE--Generative and Transformational Techniques on Software Engineering.

Content

The tutorial will be divided in various parts introducing first the key issues relative to modeling heterogeneous software language artifacts, then presenting the conceptual framework for mega-modeling, and finally examples of application in different technical spaces.

Provisional outline

Introduction and objectives (5’)
Technical Spaces and Software Languages (5’)
Megamodeling fundamentals (10’)
Application to Grammarware (10’)
Application to Ontologyware (10’)
Application to Modelware (10’)
Synthesis and conclusion (10’)

Relevance to GPCE/SLE attendees

Because of its emphasis of software language artifacts, this tutorial should be of interest to SLE attendees. Compilers, transformations and generators being extensively used in generative programming the tutorial should also attract GPCE attendees. We believe that providing a conceptual and unified approach for mega- modeling and showing its application across various technical spaces could improve cross fertilization between communities.

The essence of "The essence of functional programming"

2010-09-12T16:43:00.016+02:00

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 this paper as "the paper".

Recovery and modularization effort due to Ralf Lämmel.

Disclaimer

The code distribution has not been approved, in any form, by the original author (P. Wadler). The author of the code distribution (R. Lämmel) takes all responsibility for any imprecision or misconception of this recovery and elaboration effort. Comments are welcome, as usual. Also, the particular way of distributing (modularizing) the code by means of heavy cpp usage is not meant to suggest any useful style of functional programming. It is merely used as a convenience for organizing the code such that code reuse is explicitly captured.

The paper's code vs. this code distribution

The branch "origin" is meant to stay close to the code in the paper. In particular, Haskell's monad (transformer) library is used only in branch "overhaul". We identify the following deviations (in branch "origin"):

Most importantly, the original paper did not organize the code in any way that would explicitly represent code reuse. In contrast, the code distribution leverages cpp to this end. This approach may be viewed as an ad-hoc cpp-based product-line-like approach.

We use the type class Show for "showing" values and for "getting out of the monads".

We added a few samples; they are labeled with code comments.

Minor forms of name mangling and refactoring are not listed here.

We renamed a few operators to better match the current Haskell library:

unit... -> return

bind... -> (>>=)

error... -> fail

zero... -> mzero

plus... -> mplus

out... -> tell

How to understand and run the code?

One should probably have modest knowledge of monads. For instance, one may read the paper. The easiest approach towards understanding the code distribution is to study the final interpreters in subdirectory "cache". (These interpreters were assembled from pieces, but this may be less important initially.) With two exceptions, these are all complete Haskell 98 programs (modulo TypeSynonymInstances and FlexibleInstances for the sake of Show) with a main function with test cases corresponding to the samples in the paper. The interpreters correspond to scenarios in the paper, and there is a corresponding comment at the beginning of each file to identify relevant sections in the paper. A complete list of all interpreters follows below.

If you want to better understand the structure of the interpreters and their relationships, you may want to have a look at the primary sources that are preprocessed via cpp. Each interpreter is assembled through cpp #includes; see the files in subdirectory "templates". A more profound description of our ad-hoc cpp-based product-line-like approach follows below.

List of interpreters in the order of occurrence in the paper

Baseline.hs: This is a non-monadic, CBV interpreter. This is the (non-monadic) baseline for all experiments. That is, we will turn this interpreter into monadic style, instantiate the monad parameter, perform data extensions and selective code replacements. We will also vary CBV vs. CBN, and we will use CPS eventually.

CBV.hs: This is the scheme of a monadic-style CBV intepreter. This file is incomplete as it lacks a concrete monad. (Don't run this file.) Some of the following interpreters complete this scheme. Such completion typically involves data extension and selective code replacement.

Identity.hs: This is CBV.hs completed by the identity monad.

Errors.hs: This is an interpreter with error messages. To this end, we instantiate the monad parameter of our monadic-style CBV interpreter with the error monad, and we apply selective code replacement so that error messages are actually thrown by the interpreter.

Positions.hs: This is an elaboration of Errors.hs so that position information is maintained and accordingly used in the error messages.

State.hs: This is an interpreter with a reduction count for function applications including additions. To this end, we instantiate the monad parameter with the state monad, where the state models the reduction count. We also need to apply selective code replacement so that function applications are actually counted. We also perform a data extension to provide a language construct for reading the reduction count within the interpreted language.

Output.hs: This is an interpreter with output. To this end, we instantiate the monad parameter with the writer monad, so that output is aggregated as a string. We also perform a data extension to provide a language construct for producing output within the interpreted language.

Nondeterminism.hs: This is an interpreter with non-deterministic choice. To this end, we instantiate the monad parameter with the list monad, so that nondeterminism is modeled with a multiplicity of result values. We also perform a data extension to provide language constructs for the failing computation (that produces the empty list of results) and for nondeterministic choice, indeed.

Backwards.hs: This is a variation on State.hs with backwards propagation of state.

CBN.hs: This is the scheme of a monadic-style CBN interpreter. This file is incomplete as it lacks a concrete monad. (Don't run this file.) Some of the following interpreters complete this scheme.

StateCBN.hs: This is a variation on State.hs with CBN.

NondeterminismCBN.hs: This is a variation on Nondeterminism.hs with CBN.

CPS.hs: This is a non-monadic, CBV and CPS interpreter.

Callcc.hs: This is a monadic-style interpreter (CBV) that uses the continuation monad to provide "call with current continuation" (callcc). We perform a data extension to provide callcc as a language construct within the interpreted language.

ErrorsCPS.hs: This is a variation on Errors.hs which leverages the continuation monad and uses the Answer type to plug errors into the interpreter.

StateCPS.hs: This is a variation on State.hs which leverages the continuation monad and uses the Answer type to plug state into the interpreter.

Code organization of the distribution

Directories:

cache: ready-to-run interpreters
templates: cpp templates for interpreters
monads: monads used in the interpreters
types: syntactic and semantic domains
functions: functions making up the interpreters
terms: sample terms for the interpreters
baselines: interpreter outputs for regression testing

Some types and functions require variation for the different monads and also in terms of the choice CBV vs. CBN. The subdirectory cba (read as call-by-"any") hosts definitions that are shared by CBV, CBN, and CPS. (Here, we should note that the CPS experiments use CBV (not CBN).) Within directories types and functions, the subdirectories cbv and cbn host definitions specific to CBV or CBN respectively. Monad-specific variations are hosted in yet deeper subdirectories with the (one-letter) name of the corresponding monad; see, for example, functions/cbv/E.

Comments and questions and contributions welcome.

Ralf

Bulk mailing for your conferences not appreciated

2010-09-10T16:42:00.010+02:00

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

2010-08-24T18:42:00.007+02:00

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 base.)

The interpreters are programmed in a naive denotational style. We do not use monads for modularization until somewhat late in the exercise. Also, we do not make any effort to add language constructs in a type-safe, modular way (c.f., the Expression Problem). Instead, we use CPP to incrementally extend the interpreter; we also subdivide the interpreters into chunks of code so that we can reuse and replace chunks (files) selectively along evolution. Arguably, we use low level techniques for setting up a kind of product line for simple interpreters.

Code organization

Each interpreter is subdivided into code units as follows:

Imports: any imports needed to use Haskell's library.
Syntax: the algebraic datatype for the abstract syntax.
Value: the designated domain for the types of results.
Domains: other types used by the interpreter.
Interpreter: the semantic function (the interpreter).
Algebra: composition functions for semantic meanings.
Library: reusable, auxiliary functions for the interpreter.
Locals: not so reusable auxiliary functions.
Test: any code needed for testing the interpreter.
Main: the main function for testing the interpreter.

Running the stuff

The code is available from SourceForge.

Contributions are welcome.

All interpreters are readily cached in subdirectory Haskell/src/cache.

You can rebuild and test all this stuff very easily if you have:

- ghc(i) (tested with version 6.10.4)

- gcc cpp (tested with version 4.2.1)

- make (tested with GNU Make 3.81)

Go to subdirectory "Haskell/src" and type in "make".

CPP is used to glue together the interpreters from the code units.

Description of the versions of the interpreter

0-ConstAdd: This is an evaluator for Const/Add expressions. (If you have seen the C9 lecture on the Expression Problem, this option only serves as a reminder that we have already dealt with interpreters back then.)

1-ZeroSucc: Let's pick a trivial starting point for interpretation. This language has a constant operation, Zero, and the successor operation, Succ. This is the basis for Peano-like natural numbers. Semantically, we represent natural numbers through Haskell's Ints. Hence, this tiny interpreter allows us to build Haskell Ints from Peano's Zero and Succ. That's nothing short of impressive. :-)

2-ZeroSuccPred: So far, our interpreter was a total function (assuming non-bottom arguments). We add a predecessor construct to the abstract syntax. Since our (intended) semantic domain is natural numbers, our interpreter function gets partial in this manner. That is, we need to rule out that we compute the predecessor of zero. We need to rewrite existing equations and use "partial function application" all over the place.

3-NB: We add a few more primitives to the interpreter: operations for Booleans. In fact, we arrive at the NB language of Pierce's TAPL (except that we leave out False and True (because they can be expressed already (as you may want to show))). This step of evolution adds something new insofar that we start to consider different result types. Hence, we need to perform partial projections on results, if some operation of the interpreter requires a certain type. (For instance, the successor operation is only applicable to natural numbers.) In principle, NB also brings up typing, but we do not get into issues of static semantics/typing here.

4-Lambda: We add the lambda calculus to NB. Adopting common terminology, our composed beast is best called an applicative lambda calculus. We are ready for functional programming now. (We are Turing complete, too, for what it matters.) For instance, we can define recursive, arithmetic operations. To this end, we leverage the CBV fixed-point operator which is representable as a lambda expression.

5-Letrec: We add a recursive let construct to the applicative lambda calculus. This is a minor extension in terms of interpreter design. That is, it is a straightforward data extension---we do not leave the ground of our current semantic model. Conceptually, this is an interesting extension though because we can now define proper nested, recursive bindings. Our Turing-complete language gets closer to a proper functional programming language. In fact, this is as much expressiveness as we get. The two remaining versions of the interpreter only vary style of its definition.

6-Monads: The signature of the interpreter function involves partiality (c.f., Maybe Value) and environment passing (Env -> ...). The actual interpreter involves considerable plumbing to deal with partiality and environment passing. This makes it hard to focus on the core meaning of the interpreter's equations. We migrate to monadic style to raise the level of abstraction, and to make parts of the interpreter more oblivious to partiality and environment passing, where possible. We compose the required monad through monad transformation---using a Maybe and a Reader transformer on top of the identity monad. (Arguably, one may object to the use of the reader monad for environment passing. The resulting semantics of lambda abstraction shows the difficulty of using the monad.)

7-Bananas: Finally, we separate recursion of the interpreter from the actual algebra of meanings of constructs. In this manner, we clarify the intention of compositionality for such a denotational-style interpreter. Also, this step presents the generalization of folding that is established for lists, which however can also be used for domain-specific algebraic datatypes such as types of abstract syntaxes.

Comments and questions and contributions welcome.

Ralf

PS: This is not rocket science, but it may be pretty useful in teaching interpretation and executable semantics and functional programming, no?

Lecture series on advanced (functional) programming concepts

2010-08-06T18:35:00.009+02:00

[

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 this matter. Thanks a lot to my students who coped with this deadly mix of process algebra, semantics, Haskell, constraints, type systems, and what have you. Some of the topics from the lecture may be of interest though to advanced programming nerds (and similar species), and this is where this post fits in.

Based on an ECOOP 2010 tutorial proposal, which was never implemented, Charles Torre (@C9, this is how he looks like) and Erik Meijer suggested in January 2010 that I could do a few C9 Lectures on advanced (functional) programming concepts. So the idea would be to dive deeper into subjects that were introduced in Graham's chapters, and to generally include some advanced subjects, also possibly related to the tension between mainstream programming and Haskell programming. Well, this sounded cool!

It took me some time to come up with a concept that is hopefully useful for both---the community, say developers or CS students who want to dive deeper into programming, and me who wants to aggregate and improve material that helps with my general occupation in academic and industrial research and education.

Perhaps I have figured out an option.

What this bunch of lectures will not be like:

A detailed Haskell programming tutorial.
An otherwise technology-centric discussion.
A totally Haskell-centric lecture series.
A never-ending lesson in Greek (Math).
An otherwise academic discussion.
A pure functional programming story.
An OO bashing series.

Here is what I will try to cover:

Advanced topics in functional/OO programming.
Properties of programs such as modularity or purity.
Composition of programs from function combinators.
Multi-paradigm programming (functions, objects, predicates).
Software Language Engineering (incl. language processing).

The first few lectures

Let's begin the series with the Expression Problem because it connects OOP and FP ingeniously; it helps understanding pattern matching, dispatch, function application, encapsulation in a combined fashion that complements established means of introducing those subjects in isolation. In this lecture, I don't present solutions to the problem---because they are too hard and too idiosyncratic. I rather present non-solutions because they are insightful and make you ask for more (I hope). See the slide deck here.

Let's continue with a lecture on Haskell's type classes. Thereby, we cover one of Haskell's supernatural powers. Again, I am not describing type classes in the manner of a language manual; I rather demonstrate a few of the mechanisms that are supported by type classes; I will also discuss a bit the underlying principles. For instance, type classes allow us to solve the expression problem like a charm, and to also address several sophistications thereof. It will take a while until C# and Java are on par with type classes. See the slide deck here.

I will discuss language interpretation because it is such a fundamental subject in computer science and programming that also allows us to deeply understand some properties and styles of functional programming. Unfortunately, language interpretation is often obfuscated by academic style of presentation---as if it was something purely mathematical. So this will be the challenge for me to find many advanced Java and .NET programmer who say in the end that language interpretation is a "must-know".

More keywords:

Effects (monads)
Continuations
Algebraic structures (e.g., monoids)
Parallelism (e.g., MapReduce)
Genericity (e.g., "Scrap your boilerplate")

For the rest of the lectures, please see C9 or follow-up posts on my blog. I have started to upload decks and code for lectures to the open-source project https://sourceforge.net/projects/developers/. You can browse the SVN repository and download files here. If everything goes as planned, then the first video will go live at C9 somewhere next week.

I am really excited to work on a lecture series like this because I feel that it allows me to focus on non-trivial, conceptual stuff. This is a welcome break from the typical Bachelor-level lecture where I am supposed to go slowly so that "no student is left behind". In the present lecture series, I enjoy the privilege of diving deep into concepts, and I assume that folks will figure out many details for themselves. I inject riddles into the lectures here and there; some of them are incredibly hard, but you will figure out I hope, and you will gain understanding no matter what---even if the riddles are too hard (perhaps infeasible) in the end. Enjoy, and please let me know how I can improve the concept of the lecture series within the implicit and explicit bounds that I described above.

Thanks,

Ralf

Software adaptation in Koblenz in Sep --- Summer School

2010-06-11T13:11:00.003+02:00

Please spread the message.

Looking forward the 1st ADAPT Summer School.

Regards,

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

2010-03-31T22:21:00.018+02:00

[ 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 does not qualify for the death penalty. It takes a lot of public outcry to solve this Halting problem. This is what I call a solution: a) beheading does not take place + b) the public outcry, also with the contribution of the informed and outspoken online society, made a difference.

Update: I have meanwhile (11pm CEST, 1 April 2010) contacted the Saudi Embassy in Germany, and brought the petition to their attention. I also asked them to pass on the information to the Saudi Ministry of Justice whose email address / fax address is not available on the web. I will sent an update once the petition reaches 1000 signatures and then again for 10.000 signatures.

Update: Join this Facebook group which fights for the same cause. This group is growing rapidly and it is great information centre on Sibat's case, when compared to my humble blog post. The group endorses the petition.

Disclaimer

Please note that the petition and this post do not attempt to make any general statement about Saudi Arabia or Lebanon, their juridical systems or governments (Saudi Arabia's, in particular), about Sharia, Islam, or you name it. Instead the petition and this post is concerned with the specific case of Ali Hussain Sibat and with the charge and death penalty in this case in particular.

A personal note: I condemn with my whole authority the charge and the punishment in question on the grounds of information provided by Amnesty International and CNN reporters modulo personal judgement.

Privacy issues

You are only required to share your email address with PetitionsOnline. Their privacy rules are such that they do not share these email addresses with anyone for whatever reason. PetitionsOnline only uses the email addresses for some forms of validation. If you decide to share your email address with me (the petition's initiator), I will not share your email addresses with anyone for whatever reason. The primary purpose of the petition is to be online and allow us to refer the target of the petition to it.

http://www.PetitionOnline.com/lksadcdc/petition.html

Thanks to everyone who has signed already.

Thank you

Ralf Lämmel

Proprietary hardware jokes

2010-03-28T21:07:00.003+02:00

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, unless brand A decides to cripple the bluetooth driver specifically, in which case you can always buy the new iPad-like device of brand A, for which a keyboard is available (unless you are living in Europe, where you can't purchase that device yet).

Our corpus is your corpus.

2010-02-25T02:12:00.018+01:00

[ 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 you write a paper, you include a URL. (There is one exception: if your work leverages Haskell, you can usually include the complete source code right into your paper so that one gets convenient access through copy and paste. Sorry for the silly joke.) Metadating-wise, common practice is nowhere perfect, but it's perfect compared to what follows.

When you do empirical analysis in CS, which results in some statements or data about software/IT artifacts, then the culture of validation is essentially the one of science. In particular, reproducibility is the crucial requirement. You describe the methodology of your analysis in a detailed manner. So you define your hypotheses, your input, your techniques for measurement, your results (which you also interpret), your threats to validity, what have you. Downloads aren't integral with science. What would you want to download anyway?

Message of this post?!

I suggest that various artifacts of an empirical analysis in CS, in general; in empirical language analysis, in particular, qualify for a valuable download. In this post, I want to call out the corpora (as in corpora of source projects, buildable projects, built projects, runnable projects, ran projects, demos, etc.).

Beyond reproducibility in CS

What's indeed not yet commonplace (if done ever) is that the corpora underlying empirical analyses are given convenient access to. Consider for example Baxter et. al's paper on structural properties of Java software, or Cranor et al.'s paper on P3P deployment. These are two seminal papers in their fields. I would loose a night of sleep over each of the two corpora.

Wouldn't it be helpful for researchers if such corpora were made available for one-click download incl. useful metadata, potentially even tooling? Let's suppose such convenient access became a best practice. First, reproducibility would be improved. Second, derived research would be simplified. Third, incentives for collaboration would be added.

I contend that convenient access adds little pain for the original author, but adds huge value for the scientific community. Why should we need to execute the description of some corpus from some paper, if it requires substantial work for us, but the corpus would be easily shared by the primary author. Why should we work hard to "reproduce the corpus" if some little help by the original authors would make reproducibility (of the corpus and most of the research work, perhaps) a charm.

Naysayers -- get lost

I can think of many reasons why 'convenient access' is not getting off the ground. Here are few obvious options:

"It's extra work, even if it is little extra work." This problem can be solved if incentives are created. For instance, publications on empirical analysis with 'convenient access' to the corpus could be rated higher than those w/o. Also, just like tool papers in many venues, there could be corpus papers.

"There is sufficient, inconvenient access available already." At least, for one of the two examples above, I fully understand how I could go about gathering the corpus myself, but I have not executed this plan, even though I could really use this corpus in some ongoing research activity. It's just too much work for me. I am effectively hampered in benefitting from the authors' research beyond their immediate results.

"Provision of convenient access is too difficult." Think of a corpus of Java programs. Suddenly, an access provider gets into the business of configuration management. After all, convenience would imply that the corpus builds and runs out of the box. I think the short-term answer is that access to the corpus w/o extra "out-of-the box" magic is still more convenient than no access. The long-term-answer is that we may need a notion of remote access to corpora, where I can give you access to my corpus in my environment, through appropriate, web-based or service-oriented interfaces.

"Convenient access gives a head start to the competition." I refuse to believe that this is really too relevant in academic practice. For instance, I am sure that the research groups behind the above-mentioned papers have no "corpus monopoly" in mind. I have not done much work on empirical analysis, but I have experience with papers that "give away details", and I must say that those papers which give away the most typically coincide with those which have the highest impact in all possible ways.

"There is copyright & Co. in the way." Yes, it is. This is a serious problem, and we better focus on solving the problem shortly, if we want to get anywhere with science and (IT) society in this age. This post will just explode if I tried to comment on that issue over here. There are many good ideas around on this issue, and we all understand that some amount of sharing works even now in this very imperfect world as we have it. If you are pro-Research 2.0, don't get bogged down by this red herring.

Well, I can think of quite a number of other reasons, but I reckon that all the usual suspects have been named, and everything else can be delegated perhaps to some discussion on this blog or elsewhere.

Regards,

Ralf Lämmel

PS: CS is of an age that empirical research is becoming viral and vital. I am grateful for talking to Jean-Marie occasionally with his lucid vision of Research 2.0 and linguistics for software languages---two topics that are strongly connected. Empirical analysis of software languages has got to be an integral part of software language linguistics. Specialized software-engineering conferences like SLE, ICPC and MSR or even big ones like ICSE or OOPSLA include empirical research for a while now.

An ambitious course on programming paradigms, semantics, and types

2010-02-24T23:26:00.005+01:00

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 students at my department about semantics, type systems, bits of interesting functional programming, declarative language processors, and sophisticated declarative methods such as process algebra or constraint-logic programming. Luckily there was a similar module in our curriculum, but I admit that I had to hijack this module a bit. (That is, the module is designed for the last semester of Bachelors, whereas the actual course is probably meant for Masters.) The students have complained in a friendly manner that the course is very heavy, but in return, I have designed the exam to be feasible for Bachelors. So everyone is happy: me because I could do loads of material and topics; the students because they receive unusual help in preparation for the exam. As to the content, students are relatively happy with the techniques that we studied---in particular because we are running the course in such a pragmatic mode, where we basically leverage Prolog and Haskell throughout---for every bit of type systems and semantics and programming concepts. In this manner, the CS students can improve the programming skills in paradigms and domains to which they used before. I also admit guilty by saying that there was no way of selling the formal details of many topics. (For instance, an attempt to do soundness proofs almost triggered a riot.) As to the use of twitter, it seems that not enough students were keen to use Twitter; so we had to continue using a newsgroup in parallel.

But again, I am confident that the design of such a course with broad coverage, low formal depth, but operational depth based on declarative programming and a transparent exam is an effective way of exposing Bachelor students (possibly some of them future Master students) to critically important foundations of computer science and modern programming techniques.

The future

I will mature the course next year. I will be happy if others use the design of the course to some extent, or any specific material. Please note that more than half of the material is directly based on other people's work. I probably used 3 resources heavily, and about another 7 for some bits. Each non-original slide has credits on it in the header area. If you want to reuse anything, please let me know.

Acknowledgement

Vadim Zaytsev did an excellent job in running the lab and helping me to prepare the exam at the level of quality that we had in mind. It is good to have such a committed (emerging) declarative programmer next to you for a course like this! As to the reused material, detailed credits are online and on the slides, but I want to emphasize a few sources because of the degree of reuse and my admiration of their work: Hanne Riis Nielson and Flemming Nielson (for their book "Semantics with Applications" with slides); Graham Hutton (for his wonderful introduction to Haskell); Jaakko Järvi (for the slides of his mainly TAPL-based programming course).

Regards,

Empirical Language Analysis

2010-02-21T20:33:00.004+01:00

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 to constraints, coverage of the P3P language, and a number of additional properties of language usage. This effort helps understanding the de-facto usage of the non-executable, domain-specific language P3P. Some elements of our methodology may be similarly useful for other software languages.

Regards,

Constructive art on software languages

2010-01-19T22:08:00.010+01:00

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 each line. Say, while I was generally trying to decrease font size as I was going from bottom to top, I had to actually increase it every now and then--if I wanted that smooth slide from top to bottom.

Background for non-Haskell nerds: In contemporary Haskell, programmers tend to express their dependence on non-standardized features by using detailed pragmas in their modules. For instance, if someone places the pragma for "FunctionalDependencies" in a module, then this means that class declarations are allowed to restrict multi-parameter type classes to model functions on types as opposed to general relations.

At some point, it just occurred to me how organized we Haskell programmers are and how much expressivity we have at avail. From a more historical point of view, we may just run into the kind of problem that is symbolized by the Tower of Babel, but honestly I don't feel like I am suffering from too much expressivity and too sexy types.

As a data point, the project from which I extracted the above language pragmas is a tutorial on type-level programming (joint work with Oleg Kiselyov). The first two lectures of this tutorial have been recorded and posted. I have presented that material for folks with pretty much no Haskell background. Several of the lectures (not those currently available online) require advanced background in typing and programming languages (also measured by the number of language pragmas shown), but the plan is ultimately to get this tutorial to the point that everyone with modest interest in language design and type systems can fully appreciate all that expressivity and sexy typing.

PF

Palindrom dates

2010-01-03T05:39:00.007+01:00

@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!


?- 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) :- ranges(2,1,30,X,S).
day(7,X,S) :- ranges(2,1,31,X,S).
day(8,X,S) :- ranges(2,1,31,X,S).
day(9,X,S) :- ranges(2,1,30,X,S).
day(10,X,S) :- ranges(2,1,31,X,S).
day(11,X,S) :- ranges(2,1,30,X,S).
day(12,X,S) :- ranges(2,1,31,X,S).

% Generate all strings of values in that range with that length
ranges(L,Min,Max,X,S2) :-
  ( Min =< Max, X = Min, name(Min,S1), pad(L,S1,S2)
  ; Min < Max, Min1 is Min + 1, ranges(L,Min1,Max,X,S2)
  ).

% Extend a string to the length given
pad(L,S1,S2) :-
  length(S1,L1),
  ( L1 > L, abort
  ; L1 = L, S2 = S1
  ; L1 < L, pad(L,[0'0|S1],S2)
  ).

% Print all solutions
print(S) :- atom_codes(A,S), write(A), nl.
main :- findall(S,special(S),Ss), maplist(print,Ss).

Major breakthrough in image processing

2009-12-23T18:33:00.005+01:00

In fact, this breakthrough is based on Haskell.

Find all the resources here:

http://userpages.uni-koblenz.de/~laemmel/bildverarbeitung/

Or just go right away to this YouTube video to get a quick idea:

http://www.youtube.com/watch?v=eKVxlHG6Jrw

This lecture was prepared upon invitation by the local research team on active vision. They asked me to hold a lecture on "Bildverarbeitung in Haskell" (engl.: "Image processing in Haskell"). Here I should mention in passing that their invitation was about an Xmas party kind of workshop. Accordingly, my lecture is short and somewhat contrived, but see for yourself. More importantly, all the shown Haskell code is short, well-typed, and available for download, but totally useless.

Technically, the shown, 4th encoding of "image processing" encodes "Bildverarbeitung" and potentially other words, letter by letter, in the type system. The overloaded functions for the letters of the alphabet can only be composed (by means of ".") to form words that are known to the type system. Hence, type checking is spell checking. Quite obviously, this particular approach is horrendously verbose, inefficient and limited. The encoding is good however in so far that it allowed me to illustrate the notion of Haskell's Triangle (as opposed to Pascal's).

Merry Xmas and a Happy New Year!

Yours,

OOPM-Vorlesung auf der Treppe

2009-11-29T18:38:00.009+01:00

Im folgenden fasse ich die Abläufe zusammen, welche ultimativ zu der "Treppenvorlesung" in der OOPM-Veranstaltung am 26.11.2009 geführt haben. Alle die dabei waren, hatten trotz des schlechten Sounds und der Besetzung doch auch ein bisschen Spass neben all der harten Materie?

_______________________________________________________

25.11.2009, 13:03, Post von ASta-Vorsitz in Newsgroup infko.general

"Die VV [Vollversammlung, Anmerkung PF] aller Studierenden hat soeben beschlossen, dass der Audimax (D 028) besetzt wird."

_______________________________________________________

25.11.2009, 13:39, Reply von PF in eben dieser Newsgroup

"Was ist die Semantik dieser Aktion insbesondere in Hinblick auf die Frage, ob damit grosse Vorlesungen im D 028 bis auf weiteres abzusetzen sind?"

_______________________________________________________

25.11.2009, 17:45, PF veröffentlicht eine Blogpost zum Thema

http://professor-fish.blogspot.com/2009/11/vorlesung-kampft-um-ihre-austragung.html

Ein bisschen Wertung extra:

Mein Verständnis war, dass die OOPM-Vorlesung nicht ausfallen sollte, da es sich bei der Besetzung des AUDIMAX nicht um einen allgemeinen Streik handelt. Vielmehr schien es im Sinne der Organisatoren und aller Studenten zu sein, dass Lehrveranstaltungen weiter stattfinden. Allerdings kann eine Grossveranstaltung wie OOPM natürlich nur schwer einen anderen Raum finden. Somit ist die Besetzung des AUDIMAX nahezu effektiv ein Ausschlusskriterium für die Durchführung der Veranstaltung.

... abgesehen von Alternativen, die in der Blogpost erwähnt wurden.

_______________________________________________________

25.11.2009, 22:39, Reply von ASta-Vorsitz in eben dieser Newsgroup

Meine Zusammenfassung: Der AUDIMAX wird insbesondere während der OOPM-Veranstaltung für einen anderen Programmpunkt benötigt.

_______________________________________________________

26.11.2009, ab 9:00, diverse Anrufe durch PF

- Raumplanung Campus; Nachfrage nach Ersatzraum; Bescheid negativ.

- Leitung der Mensa; Nachfrage nach Erlaubnis zur Austragung: Bescheid negativ.

- Hausmeister; Nachfrage nach Lautsprechersystem; Keine rechtzeitige Verfügbarkeit.

- ...

_______________________________________________________

26.11.2009, 9:43, Post von PF in Newsgroup infko.oopm

Bekanntgabe der Treppe neben AUDIMAX als Austragungsort

_______________________________________________________

26.11.2009, 10:21, Beginn der Vorlesung mit 6 Minuten Verspätung.

Die Verzögerung war wie folgt zu erklären:

- Besorgung und nicht-trivialle Aufstellung des Projektors

- Besorgung und Tuning eines eher ungeeigneten Lautsprechersystems

- Interaktion mit den Teilnehmern

_______________________________________________________

Weitere Links

- Kurzfilm (YouTube)

- Langfilm (Webseite der Lehrveranstaltung)

Gruss,

Vorlesung kämpft um ihre Austragung

2009-11-25T17:25:00.008+01:00

Durch eine Vollversammlung der Studenten wurde heute auf dem Campus beschlossen, dass unser, über alles geliebte AUDIMAX (grosser Hörsaal D 028) besetzt wird. Dies zu tun, ist das demokratische Recht der Studenten und deren Argumentation ist anderswo verfügbar. Ich werde mich hier dazu nicht weiter äussern.

Allerdings überlege ich gerade, ob und wie diese Aktion meine donnerstägliche OOPM-Vorlesung in eben diesem Raum (follow @oopm, siehe Link hier http://userpages.uni-koblenz.de/~laemmel/oopm0910/ ) beeinträchtigt.

Da weder AStA noch die Uni-Leitung, noch irgend jemand anders mit Autorität, so weit ich weiss, bisher klare Empfehlungen gibt, was anstehende Veranstaltungen im D 028 angeht, versuche ich mal etwas OOPM-spezifisches -- in der Hoffnung dass ich nicht unwissentlich meine Beamten- und demokratischen Pflichten verletze:

Gelingen und Kooperation durch die Besatzungsmacht vorausgesetzt, findet die morgige OOPM-Veranstaltung im D 028 in unkonventionellerer Form statt.

Ich höre gerade, dass es Bemühungen für einen Ersatzraum gibt, aber das bleibt abzuwarten. Ich ziehe natürlich auch gern mit Ihnen auf eine andere Ecke von Koblenz um und kann wieder 3-4 Leute in meinem Auto mitnehmen.

Wenn die Besetzer des D 028 mir freundlicherweise etwas Platz auf der Bühne lassen und ebenfalls die Benutzung der Technik nicht behindern, dann soll es am Ende der Veranstaltung einen attraktiven Preis für den qualifiziertesten (aus OOPM-Sicht) Besetzer oder Herumsitzer geben. Ich werde den Gewinner demokratisch selbst auswählen.

Ich sehe das wirklich als eine Chance für die Besetzer, etwas Fundiertes über die Programmierung von imperativen Datenstrukturen zu erfahren. Lassen Sie sich das nicht entgehen! Wenn Sie interessante, thematische Bezüge zu dem Besetzungsthema herstellen können, werden wir uns alle freuen.

Gelingen und Kooperation durch die Besatzungsmacht vorausgesetzt, werde ich die Vorlesung wie immer aufzeichnen und verlinken. Dies kommt doch vielleicht auch dem PR-Ziel der Besatzungsmacht zugute? Ich könnte die Kamera so ausrichten, dass die Situation im Raum erfassbar ist. Durch Auflösungsmanipulation würde ich Ihre Persönlichkeitsrechte wahren -- ausgenommen Sie treten nah an meine Kamera.

Falls es nicht zumutbar für die Besetzer ist oder sie den Ablauf unserer OOPM-Veranstaltung zu sehr stören, schlage ich vor, dass wir in das Treppenhaus neben D 028 umziehen. Dort könnte man eine Projektion von vielen Seiten einsehen.

Falls die Besatzungsmacht auch anreichende Gebiete einnimmt, dann lassen Sie uns in mein Büro verlegen. Dort gibt es eine grosse rote Couch und 4 weitere Sitzgelegenheiten (die altmodischen Riesenlautsprecher nicht eingeschlossen). Wir können dann nebenbei an einem Wetten Dass - Beitrag arbeiten. Ich hoffe, dass es keine baustatischen Gründe gibt, die gegen diese Ausweichvariante sprechen.

Gruss,

PF/RL

Countdown with Prolog

2009-11-22T00:15:00.005+01:00

I was just going through G. Hutton's Haskell code for the (simplified) countdown problem which I plan to mention in a class on functional programming. The aforementioned code is discussed in the wonderful book "Programming in Haskell". The development of the brute-force model looks verbose and detouring however. (This is probably because the problem serves some pedagogical purposes.) Here is a simple Prolog-based solution. It is much faster than the brute-force Haskell-based solution, also because some optimizations are naturally achieved by a straightforward solution. I am sure others have tried this because it is so strikingly obvious.

Suppose you want to compute a given number X, by applying the arithmetic operations addition, subtraction, multiplication, and division to numbers picked from a given sequence of positive natural numbers, while using any candidate at most once, and all intermediate results must be positive natural numbers again.

For instance: 765 = (25-10)*(50+1)


% Solutions Ts for countdown problem with numbers Ns, result X

solve(Ns,X,Ts) :-
 findall(T,(
   sublist(L,Ns),
   permutation(L,P),
   compute(P,T),
   X is T
 ),Ts).


% Generate all sublists of a given list

sublist([],[]).
sublist(Z,[H|T]) :-
 sublist(Y,T),
 ( Z = Y
 ; Z = [H|Y]
 ).


% Generate all permutations of a given list

permutation([],[]).
permutation([H|T1],L) :-
 permutation(T1,T2),
 append(T2a,T2b,T2),
 append(T2a,[H|T2b],L).


% Complete sequences of numbers into arithmetic expressions

compute([R],R).
compute(As,T) :-
 As = [_,_|_],
 append(As1,As2,As),
 As1 = [_|_],
 As2 = [_|_],
 compute(As1,T1),
 compute(As2,T2),
 ( T = T1 + T2
 ; T = T1 - T2
 ; T = T1 * T2
 ; T = T1 / T2
 ),
 R is T,
 R > 0,
 integer(R).

Regards,

PPDP 2009 over and Prological SYB code goes live

2009-09-11T00:18:00.005+02:00

Just tried to send an email to what I thought would be the cafe mailing list of the Association of Logic Programming (ALP). My message bounced. Sigh! Anyway, here is the message and below you also see the content of the README file for the tiny code distribution for scrap[p]ing boilerplate prologically.

From: Ralf Laemmel rlaemmel@gmail.com

To: Alp-cafe-request@babel.ls.fi.upm.es

Date: Thu, 10 Sep 2009 22:57:11 +0100

Subject: post-PPDP 2009 greeting

Not sure whether this mailing list is actually working (because I haven't seen any traffic since June when it all started) but I thought it couldn't hurt to send a short post-PPDP 2009 greeting. António Porto, Francisco J. López-Fraguas, Pedro Quaresma, Ana Paula Tomás, and their collaborators have put together a great conference event. The program was really packed; perhaps even a bit stressful :-) I would have loved to interact a bit more during additional breaks and panels.

For what it's worth, I have uploaded the SYB sources for my invited talk to a google code repository.

http://code.google.com/p/strafunski/source/browse/#svn/trunk/ppdp09

Regards,
Ralf

README follows


These are sources that I release with my PPDP 2009 invited talk.
Please understand that this is *illustrative* code.
I have merely sketched certain aspects.
It is really just illustration for a talk!
It may be useful though.

Here is quick inventory of this file system:

shared: basic lib functionality used by several "experiments"
* holp: higher-order logic programming convenience
* syb: very little to be shared of SYB among experiments
* lists: (mainly higher-order) list processing
* meta: metaprogramming convenience
* vars: operations on lists/sets of logical/nonground variables
* msft: test data

experiments: experiments or illustrations used in the talk
* basic: the most basic SYB experiment
* backtracking: illustration of backtracking traversal
* nonground: illustration of traversal of nonground terms
* bidirectional: crazy inquiry into multi-mode traversal
* optimized: a generative and optimized model of SYB

All the experiments consist of two parts:
* lib: all library (generic) functionality
* app: specific illustrations (using msft typically)

Decreasing salaries with addition

2009-09-10T11:12:00.005+02:00

There are some parts of my PPDP 2009 invited talk that didn't make it into the short paper for that talk. In particular, I played a bit with the feature interaction of traversal (SYB) and using predicates in different modes. The use of multi-mode predicates is one of the exciting aspects of logic programming. (It is somewhat disputed how crucial or useful it is, but it is impressive/expressive anyhow.) For instance, beginners are always surprised to see that one can use append/3 to both .... well ... append but also take apart lists.

So I considered the question how to use such multi-modeness, if at all, perhaps even usefully, in the context of traversal programming. Here, we would expect traversal predicates to serve the normal forward direction (traverse first argument, compute second argument) and the unusual backward direction.

Let's consider the following, recession-inspired scenario for the sake of the argument:

We certainly know how to increase salaries (say by 1 $) everywhere.
However, there is pressure that we need to decrease salaries lately.
We wish to run an increasing traversal backwards to decrease salaries.

Let's start with the increase-only traversal.

incSalary(X,Y) :- everywhere(mkT(incSalary_),X,Y).
incSalary_(salary(S1),salary(S2)) :- add(S1,1,S2).
add(X,Y,Z) :- Z is X + Y.

everywhere/3, mkT/3 are defined in a straightforward manner:

(See the PPDP 2009 paper for details.)

% Transform everywhere (bottom-up)

everywhere(T,X,Z) :-
 gmapT(everywhere(T),X,Y),
 apply(T,[Y,Z]).

% One-layer traversal

gmapT(T,X,Y) :-
 X =.. [C|Kids1],
 map(T,Kids1,Kids2),
 Y =.. [C|Kids2].

% "Make transformation"

mkT(T,X,Y) :- choice(T,id,X,Y).

% Left-biased choice

choice(F,G,X,Y) :-
 apply(F,[X,Y]) ->
     true
   ; apply(G,[X,Y]).

% Identity

id(X,X).

The above development will not be able to decrease salaries (by traversing "backwards"). Quite obviously, we need an add/3 predicate that can go backwards. That's easy enough. The following revision of add/3 can cope with any combination of 2 argument positions being instantiated with numbers.

add(X,Y,Z) :-
( \+ var(X), \+ var(Y), Z is X + Y
; \+ var(X), \+ var(Z), Y is Z - X
; \+ var(Y), \+ var(Z), X is Z - Y
).

We need to do a few more things before backward traversal works. In particular, one-layer traversal is not prepared to deal with an uninstantiated first argument. There are actually two reasons for an uninstantiated, first argument to make sense. Reason 1 is that we might be traversing terms with logical variables. Reason 2 is related to our current endeavor: backward traversal with the 2nd argument being instantiated and the first one being variable. So here is our blow that resolves both issues:

gmapT(T,X,Y) :-
 var(X), var(Y),
 Y = X
;
 \+ var(X),
 X =.. [C|Kids1],
 map(T,Kids1,Kids2),
 Y =.. [C|Kids2]
;
 var(X), \+ var(Y),
 Y =.. [C|Kids2],
 map(T,Kids1,Kids2),
 X =.. [C|Kids1].

However, this is still not enough. We also need to make fit the traversal scheme everywhere/3. We need to adjust the sequential order of the body of everywhere/3 depending on instantiation. Please note that the resulting traversal is still to be considered a bottom-up traversal (which is good news!).

everywhere(T,X,Z) :-
 Apply = apply(T,[Y,Z]),
 Recurse = gmapT(everywhere(T),X,Y),
 ( var(X), \+ var(Z) ->
     Apply, Recurse
   ; Recurse, Apply ).

That's it, we can do backward traversal and hence decrease salaries with incSalary/2.

Locked into a juicy apple

2009-08-27T04:05:00.008+02:00

A bit more than 2 years ago I got bored by my usual XP+cygwin box (and I had given up on Linux anyway), and thought I would try a mac. Meanwhile I have tried macs a lot, spent a fortune on software. Sigh, I am having quite some hardware issues, but fortunately everything so far was covered by warranty or apple care. Anyway, my house is the perfect Mac Family place: several MacBook[pro]s, a time capsule, an iPhone, several editions of all the basic software (iWork, iLive, Mac OS -- Snow Leopard pre-ordered), and a good deal of pay and freeware (e.g., several kinds of screen/video capture/recording).

Here is the problem: I have gotten addicted to apples.

So let me self-diagnose whether I can get rid of that addiction:

I write texts with web apps or with LaTeX. Other Oss can do this too.
I use .key for slides. Some bits would get lost in translation to .ppt[x].
iTunes seems to be platform-independent, no?
iPhoto. Who needs that? I am using Picasa above it anyway.
iWeb. Why did I ever start using it? It is sooo constraining anyway!
I have some minor utilities that I would need to find counterparts for ...
Sure my kids will miss PhotoBooth.
I will miss iMovie; it helped me to understand that I need 4 GB.

Based on such preliminary reflection, I claim that there is an Ok transition path to W7. It's good to have a choice.

PF

SWI-Prolog's Java Interface JPL

2009-08-26T17:41:00.001+02:00

I would like to mix Java and Prolog code on a number of occasions. Together with a student of mine (Joachim Pehl), we just convinced ourselves that the JPL library of SWI-Prolog is really cool. Basically JPL allows you to call Prolog from Java and Java from Prolog.

But the question is, of course, how easy is it and can you easily go back and forth. For instance, can we call Prolog from Java and call back Java from Prolog and share Java state throughout? Sure it works!

PROLOG PORTION FOLLOWS


% This library is all we need to call Java from Prolog
:- ensure_loaded(library(jpl)).

main
:-
  % Create an object
  jpl_new(class([],['Test']), [], X),

  % Printing objects is like printing object ids
  write(X),nl,

  % Access a field of the object; happens to be static
  jpl_get(X, state, Y),

  % Prints whatever the state's value is
  write(Y),nl.

JAVA PORTION FOLLOWS


// This jar is all we need to call Prolog from Java
import jpl.*;

public class Test {

public static int state = 0;

public static void main(String[] args) {

 // Consult a Prolog file
 Query q1 = new Query("consult", new Term[] { new Atom("Test.pro") });

 // Prints boolean success/failure value
 System.out.println(q1.query());

 // Affect static field.
 // This way we can see whether Prolog sees the same JVM instance.
 Test.state = 42;

 // Invoke a predicate
 Query q2 = new Query("main");

 // Prints boolean success/failure value
 System.out.println(q2.query());
}
}

BUILDING and RUNNING BOTH

javac -cp $CLASSPATH:/opt/local/lib/swipl-5.6.62/lib/jpl.jar:. Test.java
java -cp $CLASSPATH:/opt/local/lib/swipl-5.6.62/lib/jpl.jar:. -Djava.library.path="/opt/local/lib/swipl-5.6.62/lib/i386-darwin9.5.0" Test
true
@(J#00000000000016809476)
42
true

SO WHAT?

Hence, we can start a Java app, have it start a Prolog engine and consult the Prolog portion of our app, then delegate from Java to Prolog, where we in turn call back on Java in the same JVM and can access some state that we left off in Java before we were calling Prolog.

PF

The same guy as "Grammarware, Haskellware, XMLware"

2009-08-25T14:39:00.000+02:00

What's wrong with the old blog?

I have been using http://blogs.msdn.com/ralflammel/ for some blogging until now. I created that blog when I was still a MS employee and it may be inappropriate to keep using this blog forever. Not that I have any plans to say anything controversial about MS in the future, but some of my personal opinions may be inappropriate on a blogger's domain that is mostly used by MS employees with often more MS-related content. Actually I really like some MS technologies, and I think I can speak about them much more easily when not being hosted on msdn.

Why "Professor Fish"?

I was looking for a content-free title and so I recalled that one of the more offensive students in one of my courses called me a "fish" in a newsgroup. I actually like that name because I like the sea and I like to swim and I like sea food. Anyway, the name is still better than "grammarware, haskellware, xmlware" (the name of my msdn blog) because I also want to (potentially) blog about non-CS stuff.

See me on Twitter.
http://twitter.com/notquiteabba

Regards,
PF