Realizing evaluation strategies by
hierarchical graph rewriting
Petra Hofstedt
Brandenburg University of Technology Cottbus

arXiv:1009.3770v1 [cs.LO] 20 Sep 2010

hofstedt@informatik.tu-cottbus.de

Abstract. We discuss the realization of evaluation strategies for the
concurrent constraint-based functional language ccfl within the translation schemata when compiling ccfl programs into the hierarchical
graph rewriting language lmntal. The support of lmntal to express local computations and to describe the migration of processes and rules
between local computation spaces allows a clear and simple encoding of
typical evaluation strategies.

1

Introduction

The C oncurrent C onstraint F unctional Language ccfl is a new multiparadigm
constraint programming language combining the functional and the constraintbased paradigms. ccfl allows a pure functional programming style, but also the
usage of constraints for the description and solution of problems with incomplete
knowledge on the one hand and for the communication and synchronization of
concurrent processes on the other hand.
ccfl compiles into another multiparadigm language, i.e. the language lmntal
(pronounced ”elemental”) [UK05,UKHM06]. lmntal realizes a concurrent language model based on rewriting hierarchical graphs. One of its major aims is to
unify various paradigms of computation and, thus, we chose lmntal as a base
model and target language for the CCFL compilation.1
In this paper we discuss the implementation of evaluation strategies for ccfl
within the compilation schemata. The support of lmntal to express local computations and to describe the migration of processes and rules between local
computation spaces allows the realization of typical evaluation strategies in a
clear and simple way.
Sect. 2 introduces into programming with ccfl and presents the main language features by example. Sect. 3 is dedicated to the compiler target language
lmntal and its evaluation principles. We discuss the encoding of evaluation
strategies in Sect. 4.
1

In [HL09] we took another approach with an abstract machine on a parallel multicore architecture as compilation target and enabled even programming with typical
parallelization patterns in ccfl.

Program 2.1 A simple (functional) ccfl program
def add x y = x + y
def addOne = add 1
def f a c x = case x of 1 −> x ;
n −> n ∗ f a c ( n−1)

Program 2.2 ccfl: list length
data L i s t a = N i l | Cons a ( L i s t a )
def l e n g t h l =
case l of N i l
−> 0 ;
Cons x x s −> 1 + l e n g t h x s

2

Constraint-functional programming with CCFL

The C oncurrent C onstraint-based F unctional Language ccfl combines concepts from the functional and the constraint-based paradigms. We briefly sketch
on the main conceptual ideas. For a detailed presentation of ccfl’s full syntax
and semantics and application examples we refer to [HL09,Hof08].
Functional programming. ccfl’s functional sub-language syntactically borrows
from haskell. The language allows the typical constructs such as case- and letexpressions, function application, some predefined infix operations, constants,
variables, and constructor terms, user-defined data types, higher-order functions
and partial application and it has a polymorphic type system.
Example 1. Prog. 2.1 shows a simple functional ccfl program. We stress on
this example later again. The following derivation sequence uses a call-by-value
strategy. As usual, we denote the n-fold application of the reduction relation
by n and its reflexive, transitive closure by ? . We underline innermost
redexes. Note, that the given sequence is one of several (equivalent) derivations.
add (addOne (6+1)) (addOne 8)
add (addOne 7) (add 1 8)

2

add (addOne 7) (addOne 8)
3
add (addOne 7) 9
add 8 9

2

17

Free variables. In ccfl, expressions may contain free variables. Function applications with free variables are evaluated using the residuation principle [Smo93],
that is, function calls are suspended until the variables are bound to expressions
such that a deterministic reduction is possible. For example, a function call 4 + x
with free variable x will suspend. In contrast, consider Prog. 2.2 defining the data
type List a and a length-function on lists. To proceed with the computation of
the expression length (Cons x (Cons 1 (Cons y Nil))) a concrete binding of the
variables x and y is not necessary. The computation yields 3.
In the following, we will use the haskell-typical notions for lists, i.e. [] and
e.g. [1,6] for an empty and non-empty list, resp. , and ”:” as the list constructor.
2

Program 2.3 ccfl: a game of dice
1
2
3
4
5
6
7

fun game : : Int −> Int −> Int −> C
def game x y n =
case n of 0 −> x =:= 0 & y =:= 0 ;
m −> with x1 , y1 , x2 , y2 : : Int
in d i c e x1 & d i c e y1 &
x =:= x1 + x2 & y =:= y1 + y2 &
game x2 y2 (m−1)

8
9
10

fun d i c e : : Int −> C
def d i c e x =
member [ 1 , 2 , 3 , 4 , 5 , 6 ] x

11
12
13
14
15

fun member : : L i s t a −> a −> C
def member l x =
l =:= y : y s −> x =:= y |
l =:= y : y s −> case y s of [ ]
−> x =:= y ;
z : z s −> member y s x

Constraint-based programming. ccfl features equality constraints on functional
expressions, user-defined constraints, and conjunctions of these which enables the
description of cooperating processes and non-deterministic behavior.2
As an example consider Prog. 2.3. In lines 2–7 we define a constraint abstraction (or user-defined constraint, resp.) game. A constraint abstraction has
a similar form like a functional definition. However, it is allowed to introduce
free variables using the keyword with, the right-hand side of a constraint abstraction may consist of several body alternatives the choice of which is decided
by guards, and each of these alternatives is a conjunction of constraint atoms.
A constraint always has result type C.
The constraint abstraction game initiates a game between two players throwing the dice n times and reaching the overall values x and y, resp.
In lines 5–7 we see a conjunction of constraints which are either applications
of user-defined constraints, like (dice x1) and (game x2 y2 (m−1)), or equalities
e1 =:=e2 on functional expressions.
Constraints represent processes to be evaluated concurrently and they communicate and synchronize by shared variables. This is realized by suspending
function calls (see above) and constraint applications in case of insufficiently
instantiated variables.
Guards in user-defined constraints enable to express non-determinism. For
example the member-constraint in lines 12–15 non-deterministically chooses a
value from a list. Since the match-constraints of the guards of both alternatives
are the same (lines 13 and 14), i.e. l =:= y : ys, the alternatives are chosen
non-deterministically which is used to simulate the dice.
2

The integration of external constraint domains (and solvers) such as finite domain
constraints or linear arithmetic constraints is discussed in [Hof08].

3

Note that alternatives by case-expressions as in lines 3 and 4 and alternatives
by guarded expressions as in lines 13 and 14 are fundamentally different concepts.
They do not only differ syntactically by using the keyword case−of and the
separation mark ”;” on the one hand and constraints as guards and the mark ”|”
on the other hand. Of course, the main difference is in the evaluation: While casealternatives are tested sequentially, guards are checked non-deterministically for
entailment.
The constraint evaluation in ccfl is based on the evaluation of the therein
comprised functional expressions. Thus, we can restrict our presentation of evaluation strategies to the reduction of functional expressions in this paper.
Equality constraints are interpreted as strict. That is, the constraint
e1 =:= e2 is satisfied, if both expressions can be reduced to the same ground
data term [HAB+ 06]. While a satisfiable equality constraint x =:= fexpr produces a binding of the variable x to the functional expression fexpr and terminates with result value Success, an unsatisfiable equality is reduced to the value
Fail representing an unsuccessful computation.
ccfl is a concurrent language. Thus, constraints within conjunctions are
evaluated concurrently. Concerning the functional sub-language of ccfl, we allow the concurrent reduction of independent sub-expressions.

3

LMNtal

The hierarchical graph rewriting language lmntal is the target language of
the compilation of ccfl programs. One of its major aims is to ”unify various paradigms of computation” [UK05] and, thus, it lent itself as base model
and target language for the compilation of ccfl programs. We briefly introduce
the principles of lmntal by example, in particular the concepts necessary to explain our approach in the following. For a detailed discussion of lmntal’s syntax,
semantics, and usage see e.g. [UK05,UKHM06,LMN10].
An lmntal program describes a process consisting of atoms, cells, logical
links, and rules.
An atom p(X1 , ..., Xn ) has a name p and logical links X1 , ..., Xn which may
connect to other atoms and build graphs in this way. For example, the atoms
f (A,B,E), A = 7, g(D,B) are interconnected by the links A and B. Note that
the links of an atom are ordered such that the above atoms can also be denoted
by E = f(A,B), A = 7, B = g (D). As a shortened notation we may also write
E = f(7,g(D)). A and B are inner links in this example; they cannot appear
elsewhere because links are bilateral connections and can, thus, occur at most
twice.
A cell {a? , r? , c? , l? } encloses a process, i.e. atoms a, rules r (see below),
and cells c within a membrane ”{}” and it may encapsulate computations and
express hierarchical graphs in this way. Links l may also appear in cells where
they are used to interconnect with other cells and atoms.
4

Program 3.1 lmntal: non-deterministic bubble sort
1

L=[X,Y| L2 ] :− X > Y | L=[Y,X| L2 ] .

2

aList = [2 ,1 ,5 ,0 ,4 ,6 ,3].

Program 3.2 lmntal: membranes to encapsulate computations
1
2

{@r , { $p } , $s } :− {{@r , $p } , $s } .
{{@r , $p } / , $s } :− {@r , $p , $s } .

3
4

{addOne (A, B) :− B = 1 + A.
{addOne ( 2 ,D) } , {addOne ( 4 ,E) } }

Example 2. Consider the following two cells.
{addOne(A,B) :− B=1+A. E=5, {addOne(2,D)}}, {+E}
The first cell encloses a rule addOne(A,B) :− B=1+A., an atom E=5, and
an inner cell {addOne(2,D)} enclosing an atom itself. The second (outer) cell
just contains a link +E connecting into the first cell onto the value 5.
Rules have the form lhs :− rhs and they are used to describe the rewriting
of graphs. Both, the left-hand side lhs and the right-hand side rhs of a rule are
process templates which may contain atoms, cells and rules and further special
constructs (see e.g. [UK05]) among them process contexts and rule contexts.
Contexts may appear within a cell and they refer to the rest of the entities
of this cell. Rule contexts @r are used to represent multisets of rules, process
contexts $p represent multisets of cells and atoms.
Consider the bubble sort rule and a list to sort in Prog. 3.1 as a first and
simple example. In the bubble sort rule, link L connects to the graph [X,Y |L2]
representing a list. Thus, [X,Y |L2] does not describe the beginning of a list but
an arbitrary cutout such that the rule is in general applicable onto every list
position where X > Y holds. Since lmntal does not fix an evaluation strategy,
the sorting process is non-deterministic.
As a second example consider the lmntal Prog. 3.2. Lines 3–4 show a cell, i.e.
a process encapsulated by a membrane ”{}”. It consists of an addOne-rewrite
rule in a prolog-like syntax and two cells each enclosing an addOne-atom by
membranes in line 4. A, B, D, E are links. The addOne-rewrite rule cannot be
applied on the addOne-atoms in line 4 because they are enclosed by extra membranes which prevent them from premature evaluation. The rules in lines 1 and
2, however, operate on a higher level and they allow to describe the shifting of
the addOne-rule into the inner cells and backwards. At this, @r is a rule-context
denoting a (multi)set of rules, and $p and $s are process-contexts which stand
for (multi)sets of cells and atoms. The template {@r, $p}/ in line 2 has a stable flag ”/” which denotes that it can only match with a stable cell, i.e. a cell
containing no applicable rules.
In the current situation, the rule in line 1 is applicable to the cell of the
lines 3–4, where @r matches the addOne-rule, $p matches one of the inner
5

addOne-atoms and $s stands for the rest of the cell contents. A possible reduction of the this cell (in the context of the rules of lines 1–2) is, thus, the
following; we underline the elements reduced in the respective steps:
{addOne(A, B) : −B = 1 + A. {addOne(2, D)}, {addOne(4, E)} } (1)
{ {addOne(A, B) : −B = 1 + A. addOne(4, E) }, {addOne(2, D)} } addOne
{ {addOne(A, B) : −B = 1 + A. E = 1 + 4 }, {addOne(2, D)} } +
{ {addOne(A, B) : −B = 1 + A. E = 5}, {addOne(2, D)} }
The first inner cell is now stable such that no rule is applicable inside. Thus,
we can apply the rule from line 2.
{ {addOne(A, B) : −B = 1 + A. E = 5}, {addOne(2, D)} }
{addOne(A, B) : −B = 1 + A. E = 5, {addOne(2, D)} }

(2)

In this state, again the first outer rule (line 1) is applicable which yields the
following rewriting sequence and final state:
{addOne(A, B) : −B = 1 + A. E = 5, {addOne(2, D)} }
{ {addOne(A, B) : −B = 1 + A. addOne(2, D) }, E = 5}
...
{addOne(A, B) : −B = 1 + A. E = 5, D = 3}

(1)
addOne

As one can see by the above example, lmntal supports a prolog-like syntax.
However, there are fundamental differences. Our example already demonstrated
the use of process-contexts, rule-contexts, membrane enclosed cells, and the stable flag. Different from other languages, the head of a rule may contain several
atoms, even cells, rules, and contexts. A further important difference to other
declarative languages are the logical links of lmntal. What one may hold for variables in our program, i.e. A, B, D, E, are actually links. Their intended meaning
strongly differs from that of variables. Declarative variables stand for particular
expressions or values and, once bound, they stay bound throughout the computation and are indistinguishable from their value. Links in lmntal also connect to
a structure or value. However, link connections may change. While this is similar
to imperative variables, links are used to interconnect exactly two atoms, two
cells, or an atom and a cell to build graphs and they have, thus, at most two
occurrences. The links D and E in the above example occur only once and, thus,
link to the outside environment. In rules, logical links must occur exactly twice.
Semantically, lmntal is a concurrent language realizing graph rewriting. It
inherits properties from concurrent logic languages. lmntal does not support
evaluation strategies. The rule choice is non-deterministic, but can be controlled
by guards (used e.g. in Prog. 4.1 for the fac-rules, see below).
As shown in the example, the encapsulation of processes by membranes allows to express local computations, and it is possible to describe the migration
of processes and rules between local computation spaces. We will use these techniques to implement evaluation strategies for ccfl.
6

Program 4.1 Intermediate lmntal compilation result
1

add (X, Y, V0) :− V0 = X+Y.

2

addOne (X, V0) :− app ( add , 1 , V1 ) , app (V1 , X, V0 ) .

3
4

f a c (X, V0) :− X =:= 1 | V0 = 1 .
f a c (X, V0) :− X =\= 1 | V0 = X∗V1 , V2 = X−1, app ( f a c , V2 , V1 ) .

5
6
7
8
9
10

app ( f a c , V1) :− f a c (V1 ) .
app ( f a c , V1 , V2) :− f a c (V1 , V2 ) .
...
app ( add , V1 , V2 , V3) :− add (V1 , V2 , V3 ) .
app (V2 , V3 , V4 ) , add (V1 , V2) :− add (V1 , V3 , V4 ) .
...

4

Encoding evaluation strategies

Now, we discuss the compilation of CCFL programs into lmntal code. We start
with a presentation of the general translation schemata and show the realization
of a call-by-value strategy and an outermost evaluation strategy subsequently.
Our compilation schemata are partially based on translation techniques
[Nai91,Nai96,War82] for functional into logic languages.
A ccfl function definition is translated into a set of lmntal rules. ccfl data
elements and variables are represented and processed by means of certain heap
data structures during run-time. However, to clarify the presentation in this
section, we represent ccfl variables directly by lmntal links3 instead and data
structures by lmntal atoms. For a detailed discussion of the heap data structures
see [Hof08]. ccfl infix operations are mapped onto their lmntal counterparts.
Function applications are realized by an atom app (...) and an according app-rule
which is also used for higher-order function application and partial application
as discussed in [Hof08]. Case-expressions generate extra lmntal rules for pattern
matching, let-constructs are straightforwardly realized by equalities.
Example 3. Consider the ccfl Prog. 2.1. It compiles into the (simplified) lmntal
code given in Prog. 4.1 (not yet taking an evaluation strategy into consideration).
The additional link arguments V0 of the add-, addOne-, and fac-rewrite rules
are used to access the result of the rule application which is necessary because
lmntal explicitly deals with graphs while a computation with a (constraint-)
functional language like ccfl yields an expression as a result. The two fac rules
result from the case distinction in the according ccfl function.
Note that the right-hand side of the addOne rule in line 2 represents the
lmntal expression (app (app add 1) X) resulting from the ccfl addOne definition in Prog. 2.1 by η-enrichment.
3

Moreover, we tolerate n-fold occurrences of links in rules, where n 6= 2. This is also
not conform with lmntal, where links must occur exactly twice in a rule, but the
problem disappears with the introduction of heap data structures as well.

7

The rules of lines 5-10 are a cutout of the rule set generated to handle function
application including higher-order functions and partial application (according
to a schema adapted from [Nai96,War82]). Thus, in these rules the root symbols
appear with different arities.
lmntal evaluates non-deterministically, and it does a priori not support certain evaluation strategies. Thus, the control of the order of the sub-expression
evaluation for ccfl is integrated into the generated lmntal code. We realized
code generation schemata for different evaluation strategies for ccfl by encapsulating computations by membranes using similar ideas as demonstrated in
Prog. 3.2. We discuss the realization of a call-by-value and an outermost reduction strategies in the following.
A call-by-value strategy To realize evaluation strategies expressions are destructured into sub-expressions which are encapsulated by membranes and interconnected by links. These links allow to express dependencies between subexpressions on the one hand, but to hold the computations apart from each
other, on the other hand. Consider the ccfl application
add (addOne (6+1)) (addOne 8)

(1)

from Example 1. It is destructured and yields the following lmntal atoms:
Z = add (X,Y), X = addOne (W), W = 6+1, Y = addOne (8)
or in an equivalent notation, resp.:
add (X,Y,Z), addOne (W,X), W = 6+1, addOne (8,Y)

(2)

The idea to realize a call-by-value evaluation strategy is now provide the
expressions to be reduced first (i.e. the inner calls W = 6+1 and addOne (8,Y))
with the ruleset and to delay the outer calls by holding them apart from the
rules until the computation of the inner redexes they depend on is finished.
To enable a concurrent computation of independent inner sub-expressions as
discussed in Example 1 we must assign each independent inner expression or
atom, resp., a separate membrane (including a copy of the rules). This yields
the following structure (where every atom is held within separate membranes
for organizational reasons).
{{add(X,Y,Z)}} {{addOne(W,X)}} {@rules, {W=6+1}} {@rules, {addOne(8,Y)}} (3)

Fig. 1 visualizes an evaluation of (3) using a call-by-value strategy with concurrent evaluation of independent sub-expressions. Reduction step numbers are
given in brackets at the right margin. Membranes are represented as enclosing
ellipses. Interdependencies of atoms by links control the order of the evaluation
and they are represented by arrows.
In the initial state, the atoms W=6+1 and addOne(8,Y) are inner redexes
to be reduced first. We mark these by a gray color. They are provided with the
lmntal rules @rules generated from the ccfl program. The atoms add(X,Y,Z)
8

@rules

W=6+1

addOne(W,X)

add(X,Y,Z)

addOne(8,Y) @rules
(1)

addOne(W,X)

@rules W=7

add(X,Y,Z)

addOne(8,Y) @rules
(2)

(A)
@rules

addOne(7,X)

add(X,Y,Z)

addOne(8,Y) @rules
(3,4,5)

3
@rules

addOne(7,X)

add(X,Y,Z)

Y=9

@rules
(6)

(B)
@rules

addOne(7,X)

add(X,9,Z)

···
Fig. 1. A call-by-value computation sequence

and addOne(W,X) represent outer calls to be delayed until the computation of
their inner sub-expressions have been finished. Thus, we put them into extra
protecting membranes.
To control the order of sub-expression evaluation we need three things:
i. the destructured expression as given in (3),
ii. lmntal rules (denoted by @rules in Fig. 1) generated from the ccfl program: These rules take the destructuring of expressions into consideration
and realize local call-by-value evaluations.
iii. a general lmntal ruleset reorganizing the computation spaces in case that
local computations are finished.
(i) and (ii) The destructuring of expressions in lmntal rules (ii) generated
from the ccfl program is handled similarly to (i) as discussed above. Prog. 4.2
shows the lmntal code generated from Prog. 2.1 taking the intended call-by-value
evaluation into consideration.
The lmntal rules’ right-hand sides consist of cells containing the destructured
expressions. Outermost expressions are encapsulated by extra membranes to protect them against premature evaluation as necessary for an innermost strategy.
This effect is observable for the addOne-rule in line 2 and the second fac-rule in
line 5, while for the other rules the flat term structure of the right-hand sides
of the ccfl functions is just carried over to the generated lmntal rules. To simplify the presentation in Fig. 1, however, we inlined the app-calls for function
9

Program 4.2 Generated lmntal code for a call-by-value strategy
1
2

{ add (X, Y, V0 ) , $p } :− {V0 = X+Y, $p } .
{addOne (X, V0 ) , $p } :− { app ( add , 1 , V1 ) } , {{ app (V1 , X, V0 ) , $p } } .

3
4
5

{ f a c (X, V0 ) , $p } :− X =:= 1 | {V0 = 1 , $p } .
{ f a c (X, V0 ) , $p } :− X =\= 1 |
{{V0 = X∗V1 , $p } } , {V2 = X−1} , {{ app ( f a c , V2 , V1 ) } } .

6
7
8

{ app ( f a c , V1 ) , $p } :− { f a c (V1 ) , $p } .
{ app ( f a c , V1 , V2 ) , $p } :− { f a c (V1 , V2 ) , $p } .
...

Program 4.3 lmntal code for a call-by-value strategy, simplified version
1

{ add (X, Y, V0 ) , $p } :− {V0 = X+Y, $p } .

2

{addOne (X, V0 ) , $p } :− { add ( 1 ,X, V0 ) , $p } .

3
4
5

{ f a c (X, V0 ) , $p } :− X =:= 1 | {V0 = 1 , $p } .
{ f a c (X, V0 ) , $p } :− X =\= 1 |
{{V0 = X∗V1 , $p } } , {V2 = X−1} , {{ f a c (V2 , V1 ) } } .

applications (e.g. we applied the app-rule of line 7 on the call app (fac ,V2,V1)
of line 5) and used instead of Prog. 4.2 the accordingly simplified Prog. 4.3.
(iii) The reorganization of computation spaces for the call-by-value strategy
is mainly realized by two lmntal rules given in Prog. 4.4. They are visualized
in Fig. 2 for better understanding. These rules organize the evaluation of outer
calls when the inner redexes they depend on have been completely reduced. In
the following, we discuss the rules semantics by means of Fig. 2.

(A)

@rules p(...,L)

q(...,L,...)

(B)

@rules p(...,L)

q(...,L,...)

@rules

...

p(...,L) q(...,L,...)

p(...,L) q(...,L,...)

...

Fig. 2. lmntal: rules emulating a call-by-value strategy

Both rules, (A) and (B), are only applicable when the cell
{@rules, {p (..., L)}} is stable, i.e. the rules cannot be applied on the
atom p (..., L) (or L=p(...), resp.) further. For rule (A), the atom q (..., L ,...)
does not contain any further link connected to a process representing a
sub-expression evaluation. Thus, both atoms are ready for their combined
evaluation, and they are put into one computation cell or space, resp., together
with the rules. An example for the application of this rule is the computation
10

Program 4.4 lmntal rules to control the reorganization of computation spaces
for a call-by-value reduction of the ccfl compilation result
1
2
3
4

ruleA@@
{ @rules , { $ p r o c s p , +L , i n L i n k s ( 0 ) } } / ,
{ { $ p r o c s q , −L , i n L i n k s (N) } } :−
N =:= 1 | { @rules , { $ p r o c s p , $ p r o c s q , i n L i n k s ( 0 ) } } .

5
6
7
8

ruleB@@
{ @rules , { $ p r o c s p , +L , i n L i n k s ( 0 ) } } / ,
{ { $ p r o c s q , −L , i n L i n k s (N) } } :−
N > 1 | { { $ p r o c s p , $ p r o c s q , i n L i n k s (M) , M = N−1} } .

Program 4.5 lmntal compilation result for an outermost strategy
1
2
3

{ f a c (X, V0 ) , $p } :− X =:= 1 | {V0 = 1 , $p } .
{ f a c (X, V0 ) , $p } :− X =\= 1 |
{V0 = X∗V1 , $p } , {{V2 = X−1}} , {{ f a c (V2 , V1 ) } } .

step (2) in Fig. 1, where the atoms W=7 and addOne(W,X) are brought
together into one membrane and join into the atom addOne(7,X).
Rule (B) describes the case that the atom q (..., L ,...) does contain at least
one further link connected to a process itself under evaluation. These represent
sub-expressions of q (..., L ,...) or inner redexes, resp., and are denoted by ingoing links resp. arrows in Fig. 2.4 Thus, while p (..., L) and q (..., L ,...) can
be combined in one membrane, they are not ready for evaluation yet such that
we omit the rules @rules on the right-hand side here. An example is step (6) in
Fig. 1: the atoms add(X,Y,Z) and Y=9 are combined in one membrane but not
provided with the rules.
An outermost strategy For call-by-name and lazy evaluations the computation
proceeds on the outermost level. As we will see in the following, thus, copying
of the rule-set, like for the innermost strategy, (which may become expensive) is
not necessary. Besides, the mechanisms are are quite similar.
Consider the ccfl faculty function from Prog. 2.1. The (simplified) lmntal
compilation result taking an outermost strategy into consideration is given in
Prog. 4.5. In contrast to Prog. 4.3, now innermost expressions on the right-hand
sides are encapsulated by extra membranes to protect them against premature
evaluation. (The flat term structure of the right-hand sides of the ccfl functions
add and addOne is again just carried over to the generated lmntal rules and
yields the same results as in Prog. 4.3).
Fig. 3 shows an outermost evaluation sequence of an lmntal process corresponding to the ccfl expression add (addOne (6+1)) (addOne 8). We did denote the ruleset @rules only in the first computation state; there is in general
only one copy and it resides on the top level where the computation executes. An
4

An outgoing link from q (..., L ,...) would accordingly represent its parent expression. Such links are allowed, of course, but omitted in Fig. 2 for easier understanding.

11

@rules
addOne(W,X)

W=6+1

add(X,Y,Z)

addOne(8,Y)
(1)

addOne(W,X)

W=6+1

Z=X+Y

addOne(8,Y)
(2,3)

(C) 2
addOne(W,X)

W=6+1

Z=X+Y

addOne(8,Y)
(4)

(D)
W=6+1

addOne(W,X)

Z=X+Y addOne(8,Y)
(5,...)

?
W=6+1

X=1+W Z=X+9

···
Fig. 3. An outermost computation sequence

evaluation sequence for an lmntal process corresponding to the ccfl expression
fac (addOne (addOne 3)) is shown in Fig. 5.
We show two examples of evaluation sequences to allow a direct comparison
between the two evaluation sequences in Fig. 1 and Fig. 3 for the expression
add (addOne (6+1)) (addOne 8) on the one hand, but to illustrate a particular
aspect of outermost strategies (i.e. the unprotect-protect mechanism as described
in particular for the sequence in Fig. 5 below), too.
The two main rules realizing the outermost evaluation are given in Fig. 4.
We mark cells on the outermost level, i.e. cells to be reduced first, by the dark
gray color as before. Again, the rules are only applicable if the cells with dark
gray color are stable, i.e. they cannot be reduced further.
Rule (C) lifts the (”first”) inner expression p (..., L) on the evaluation level
in case that the outermost term q (..., L ,...) is not (yet) reducible. However, for
such (light-gray marked) sub-expressions (and except for arithmetic expressions)
only one reduction step is allowed before protecting its result again by an extra
membrane. This is realized by a variant of each rule of Prog. 4.5 (not shown
there). Rule (C) is applied e.g. in the first computation step of Fig. 5. Afterwards
the described unprotect-protect-mechanism applies. In steps (3) and (4) of Fig. 5
rule (C) is applied even twice which allows to make a reduction step onto the
inner redex addOne(3,Y) in step (6). For the applications of rule (C) in e.g. step
(4) of Fig. 5 and (2,3) in Fig. 3 the unprotect-protect mechanism does not apply
because the outermost expressions are arithmetic ones, here, such that we use
rule (D) afterwards.
12

...

(C)

(D)

...

q(...,L,...)

p1(...,L1)

p(...,L)

R=L1 op L2

...

...

p2(...,L2)

...

q(...,L,...)

p(...,L)

...

...

op L2 p2(...,L2)
p1(...,L1) R=L1 ...

Fig. 4. lmntal: rules emulating an outermost strategy
Program 4.6 lmntal compilation result: list length
l e n g t h (L , V0 ) , n i l (L) :− . . .
l e n g t h (L , V0 ) , cons (X, XS , L) :− . . .

Rule (D) can only be applied on expressions with arithmetic built-in operators as root. Because, in this case, the outermost term can only be evaluated if
the inner expressions are completely evaluated, we lift them onto the outermost
level, in general. The rule is applied in the step 4 of Fig. 3 and step 5 of Fig. 5.
We realized a call-by-name strategy using the presented approach. The encoding of a call-by-need strategy is possible by additionally introducing heap
data structures as anyway needed to deal with free variables and constraints in
ccfl (see above and [Hof08]). These allow sharing as needed for lazy evaluation.
Residuation Function applications in ccfl may contain free variables. In such a
case, we apply the residuation principle [Smo93] (see above). This is realized in
the resulting lmntal program by according atoms in the rules left-hand sides as
in the following example (or guards resp. as e.g. in Prog. 4.1 for the fac-rules)
checking for concerning variable bindings.
Example 4. Consider again the ccfl Prog. 2.2 defining a length-function.
Prog. 4.6 shows a cut-out of the generated lmntal program. From a not sufficiently instantiated ccfl expression (length y) the compiler generates an according lmntal atom length (Y,V). The lmntal evaluation of this process together with Prog. 4.6 suspends as long as there is no connection of the link Y to
an appropriate atom or graph, i.e. we need an atom nil (Y) or cons (H,T,Y).

5

Conclusion

We discussed the realization of typical evaluation strategies for functional programs based on hierarchical graph rewriting. The control of sub-expression evaluation was built into the translation schemata when compiling ccfl programs
into the graph rewriting language lmntal. lmntal is a concurrent language not
13

@rules
addOne(3,Y)

addOne(Y,X)

fac(X,W)
(1)

(C)
addOne(3,Y)

addOne(Y,X)

fac(X,W)
(2)

addOne(3,Y)

X=1+Y

fac(X,W)
(3)

(C)
addOne(3,Y)

X=1+Y

fac(X,W)
(4)

(C)
addOne(3,Y)

X=1+Y

fac(X,W)
(5)

(D)
addOne(3,Y) X=1+Y

fac(X,W)
(6)
fac(X,W)

Y=3+1 X=1+Y

(7)

(C)
fac(X,W)

Y=3+1 X=1+Y

···
Fig. 5. An outermost computation sequence, II

supporting strategies a priori. However, the abilities of lmntal to express hierarchical computation spaces and to migrate processes and rules between them
enables a clear and simple strategy control.
Ueda [Ued08b,Ued08a] presents encodings of the pure lambda calculus and
the ambient calculus, resp., using lmntal. Like in our approach, the membrane
construct of lmntal plays an essential role for the encoding and allows a significantly simpler than previous encodings, like e.g. that of the lambda calculus by
Sinot [Sin05] based on token passing in interaction nets. In [BFR05] Banâtre,
Fradet, and Randenac identify a basic calculus γ0 containing the very essence
of the chemical calculus and which – similar to lmntal – is based on multiset
rewriting. They show an encoding of the strict λ-calculus which is straightforward because of the strict nature of γ0 and state that an encoding of a call-byname λ-calculus is possible too, but more involved. In contrast, lmntal a priori
does not support certain evaluation strategies. Instead, lmntal offers extended
14

features like the rewriting of rules and graph hierarchies which allows to encapsulate and migrate computations which was highly used in our modelling of
evaluation strategies as presented in the paper.
Acknowledgment This work has been supported by a postdoctoral fellowship No.
PE 07542 from the Japan Society for the Promotion of Science (JSPS).

References
BFR05.

J.-P. Banâtre, P. Fradet, and Y. Radenac. Principles of Chemical Programming. Electr. Notes in Theor. Computer Science, 124(1):133–147, 2005.
HAB+ 06. M. Hanus, S. Antoy, B. Braßel, H. Kuchen, F.J. Lopez-Fraguas, W. Lux,
J.J. Moreno Navarro, and F. Steiner. Curry: An Integrated Functional
Logic Language. Technical report, 2006. Version 0.8.2 of March 28, 2006.
HL09.
P. Hofstedt and F. Lorenzen. Constraint Functional Multicore Programming. In Informatik 2009. Proceedings, volume 154 of LNI – Lecture Notes
in Informatics, pages 367, 2901–2915, 2009.
Hof08.
P. Hofstedt.
CCFL – A Concurrent Constraint Functional Language. Technical Report 2008-08, Technische Universität Berlin, 2008.
http://www-docs.tu-cottbus.de/programmiersprachen-compilerbau/
public/publikationen/2008/2008-08.pdf.
LMN10. LMNtal PukiWiki. http://www.ueda.info.waseda.ac.jp/lmntal/, 2010.
last visited 12 May 2010.
Nai91.
L. Naish. Adding equations to NU-Prolog. In Programming Language
Implementation and Logic Programming – PLILP, volume 528 of LNCS,
pages 15–26. Springer, 1991.
Nai96.
L. Naish. Higher-order logic programming in Prolog. Technical Report
96/2, Department of Computer Science, University of Melbourne, 1996.
Sin05.
F.-R. Sinot. Call-by-Name and Call-by-Value as Token-Passing Interaction
Nets. In P. Urzyczyn, editor, Typed Lambda Calculi and Applications –
TLCA, volume 3461 of LNCS, pages 386–400. Springer, 2005.
Smo93.
G. Smolka. Residuation and Guarded Rules for Constraint Logic Programming. In F. Benhamou and A. Colmerauer, editors, Constraint Logic Programming. Selected Research, pages 405–419. The MIT Press, 1993.
Ued08a.
K. Ueda. Encoding Distributed Process Calculi into LMNtal. ENTCS,
209:187–200, 2008.
Ued08b. K. Ueda. Encoding the Pure Lambda Calculus into Hierarchical Graph
Rewriting. In A. Voronkov, editor, Rewriting Techniques and Applications
– RTA, volume 5117 of LNCS, pages 392–408. Springer, 2008.
UK05.
K. Ueda and N. Kato. LMNtal: a Language Model with Links and Membranes. In Fifth International Workshop on Membrane Computing (WMC
2004), volume 3365 of LNCS, pages 110–125. Springer, 2005.
UKHM06. K. Ueda, N. Kato, K. Hara, and K. Mizuno. LMNtal as a Unifying Declarative Language. In T. Schrijvers and T. Frühwirth, editors, Third Workshop on Constraint Handling Rules, Technical Report CW 452, pages 1–15.
Katholieke Universiteit Leuven, 2006.
War82.
D.H.D. Warren. Higher-order extensions to PROLOG: Are they needed?
Machine Intelligence, 10:441–454, 1982.

15

