3. Some Miscellaneous Functions

Our first module, entitled lifemisc and stored in the file lifemisc.icl, defines some basic list operations in CLEAN, for use in the other modules. Each CLEAN implementation module has a corresponding definition module which lists exported type and macro definitions and function type declarations. These definitions can be imported with the IMPORT declaration. Here we import CLEAN's standard library modules deltaC, deltaI, deltaB, deltaM and deltaS :

IMPORT deltaC, deltaI, deltaB, deltaM, deltaS;

The constant Huge is macro-defined to be (2^31)-1 using the bit operations SHIFTL% and NOT% defined in the deltaI library. This constant can be used as a virtual infinity:

Huge -> NOT% (SHIFTL% 1 31);

The RULE keyword introduces a group of function type declarations and definitions. The Min function takes two integer arguments and produces an integer result. The ! annotations indicate that Min is strict on both its arguments, i.e. the arguments are evaluated eagerly. Functions with strict INT, BOOL, CHAR, REAL, STRING, or FILE arguments are implemented more efficiently than lazy functions in CLEAN.

:: Min !INT !INT -> INT;
   Min x y -> x, IF < x y
           -> y;

The definition of Min uses a guarded right-hand side: Min x y rewrites to x if x is less than y, and to y otherwise (i.e. Min x y rewrites to the minimum of its two arguments). Notice that all binary operators in CLEAN are written in prefix notation, i.e. < x y rather than x<y. The Max function is defined in a similar way to Min:

:: Max !INT !INT -> INT;
   Max x y -> x, IF > x y
           -> y;

The well-known Map function is defined by pattern-matching on cases. CLEAN's list notation is similar to that of PROLOG. Notice that the arrow operator on types, like all binary operators, is written in prefix notation. Although a function must be declared with a fixed arity (in this case, 2) matching the arity in the definition, functions can be used as curried objects. For example, Map can be used with the type => (=> x y) (=> ![x] [y]), which would be more readable written in infix notation as (x => y) => ![x] => [y].

:: Map (=> x y) ![x] -> [y];
   Map f [] -> [];
   Map f [h|t] -> [f h | Map f t];

The list-length function Len can be efficiently implemented using the tail-recursive auxiliary function LenAux which has a strict accumulating parameter. This technique allows Len to execute in constant space.

:: Len ![x] -> INT;
   Len l -> LenAux 0 l;

The function LenAux is strict on its second (list) argument, since pattern-matching forces evaluation to weak head normal form. This strictness is inferred by CLEAN's strictness analyser. The strictness of Len could be inferred from this, but Len must be declared strict for export purposes. The ++ operation increments its argument (and similarly -- decrements it).

:: LenAux !INT [x] -> INT;
   LenAux i [] -> i;
   LenAux i [h|t] -> LenAux (++ i) t;

A similar technique can be used to concatenate a list of strings, generalising the binary string concatenation operation +S:

:: Concat ![STRING] -> STRING;
   Concat l -> ConcatAux "" l;

:: ConcatAux !STRING [STRING] -> STRING;
   ConcatAux s [] -> s;
   ConcatAux s [h|t] -> ConcatAux (+S s h) t;

The Drop function removes a specified number of elements from a list. Since rules are examined in sequence, Drop 0 [h|t] rewrites to [h|t] and not to Drop (-- i) t:

:: Drop !INT ![x] -> [x];
   Drop 0 l -> l;
   Drop i [] -> [];
   Drop i [h|t] -> Drop (-- i) t;

The Take operation is defined similarly. It is not strict on its list argument:

:: Take !INT [x] -> [x];
   Take 0 l -> [];
   Take i [] -> [];
   Take i [h|t] -> [h | Take (-- i) t];

The lifemisc definition module lists the exported macro and functions. It is stored in the file lifemisc.dcl.

UpTop Level

BackWhy Program in CLEAN?


ForwardRepresenting Patterns for the Game of Life