• When a program executes, computation generally proceed via different evaluation orders, according to which one of many different evaluation strategies is being pursued.
• The evaluation strategies, are differentiated according to the method of passing arguments to functions.
• Mainly, parameter passing methods are call by value, call by reference, call by name and call by need a variance of call by name.
• Call by value is a computation rule of programming language where the arguments are fully evaluated before outer function applications are evaluated.

• Therefore, corresponding to the arguments of functions, only values are passed. That is why this strategy is called call-by-value.
• It is used in imperative languages such as Java, C, Pascal and functional programming languages such as SML, Scheme etc.

• In call by reference the address (reference / pointer) of actual arguments are passed to functions instead of the values.

• This computation rule is available in all imperative programming languages.
• Arrays are passed by reference in all imperative languages.

• In call by name the arguments are passed unevaluated and are evaluated every time when needed in the body of the function. If the argument is not needed, then it will not be evaluated at all.
• Call by need is an optimization of call-by-name such that an expression corresponding to an argument is evaluated at most once, if at all required.
• That means once it is evaluated, then the result is remembered and the next access to the corresponding formal parameter uses this value.

• Let us illustration different evaluation strategies using the following SML functions

- fun constant (x) = 1;

- fun cube (x : int) = x * x * x;

> val cube = fn : int -> int

Call by value: (value of argument of a function is evaluated)

Case1: Call to constant function

- val p = constant (cube (cube (cube (2))));

> val p = 1

Evaluation of the function is done as follows:

p = constant (cube (cube (cube (2))))

= constant (cube (cube (2*2*2))) = constant (cube (cube (8)))

= constant (cube (8*8*8))

= constant (cube (512)) = constant (512*512*512)

= constant (134217728) = 1

Case2: Call to cube function.

- val q = cube (cube (cube (2)));

Evaluation:

q = cube (cube (cube (2)))

= cube (cube (2*2*2)) = cube (cube (8))

= cube (8*8*8) = cube (512)

= 512*512*512 = 134217728

• We notice that the amount of time required in both the cases is same, whereas in case1, we have done calculation in vain as the result is independent of what we have calculated.
• Let us see other mechanisms for evaluation which are not available in SML

Call by name: (outermost reduction order).

Case1: Call to constant function

- val p = constant (cube (cube (cube (2))));

> val p = 1 at one step

Case2: Call to cube function

- val q = cube (cube (cube (2)));

> val q = 134217728 : int

Evaluation:

q = cube (cube (cube (2))) outermost cube is evaluated

= cube (cube (2)) * cube (cube (2)) * cube (cube (2))

= cube (2) * cube (2) * cube (2) * cube (cube (2)) * cube (cube (2))

= (2*2*2) * cube (2) * cube (2) * cube (cube (2)) * cube (cube (2))

= 8 * (2*2*2) * cube (2) * cube (cube (2)) * cube (cube (2))

= 64 * (2*2*2) * cube (cube (2)) * cube (cube (2))

• Here, the result of function in case1 is instant, whereas in case2, lots of computations are repeated and time required in this case is much higher than as compared to call by value (eager evaluation) method.
• Best of both the methods are combined in call by need (lazy evaluation). Let us see the way call by need handles such computations.

Call by need: (similar to call by name except that the repetitions are avoided )

Case1:

- val p = constant (cube (cube (cube (2))));

> val p = 1 at one step

Case2:

- val q = cube (cube (cube (2)));

> val q = 134217728 : int

Evaluation:

q = cube (cube (cube (2)))

x = cube (cube (2))

Let y = cube (2) = 8

Then, x = cube (y) = 512

q = cube (x)

q = x * x * x

q = 512 * 512 * 512 = 134217728

• There are broadly two categories of evaluation strategies in functional languages viz., eager evaluation and lazy evaluation.

• Any evaluation strategy where evaluation of all function arguments is done before their values are required.
• Call-by-value is a typical example of such evaluation where the values of all arguments are evaluated and are passed.
• In Functional languages, this type of evaluation strategy is called eager evaluation. Eager evaluation does not specify exactly when argument evaluation takes place.
• The reduction of the innermost redex forces evaluation of arguments before applications are performed. It is also called applicative reduction order.
• The term eager evaluation was invented by Carl Hewitt and Henry Baker. Eager evaluation is used to implement strict functions. SML, Scheme have eager evaluation method.
• A function is said to be strict if the result is undefined when it is applied to undefined argument(s) and said to be non-strict otherwise.

• Lazy evaluation is one where evaluation of an argument only starts when it is required first time.
• This evaluation strategy combines normal order evaluation with updating. Call by need uses lazy evaluation strategy.
• Normal order evaluation means that an expression is evaluated only when its value is needed in order for the program to return (the next part of) its result. Call by name uses normal order evaluation method.
• Updating means that if an expression's value is needed more than once (i.e. it is shared), the result of the first evaluation is remembered and subsequent requests for it will return the remembered value immediately without further evaluation.
• Lazy evaluation is one evaluation strategy used to implement non-strict functions. Choosing a particular evaluation strategy is not trivial.
• The implications are wide-ranging and, in some cases, quite subtle. It affects execution efficiency, programming style, interaction, etc.
• Lazy evaluation is a very desirable property of a functional language. This means for instance that an expression being a function argument is not evaluated at the point of call (as is usually the case with traditional languages and non-lazy functional ones).
• Instead the expression is evaluated when its value is needed, if at all.
• Lazy evaluation makes it possible to have infinite lists, infinite trees, etc, where the evaluation is done incrementally on demand.
• Lazy evaluation is must for interactive input/output in a pure functional language (explained later).
• Functional languages can be eager, lazy or a mix of the two. Functional language SML uses eager evaluation whereas languages like Haskell and Miranda use lazy evaluation scheme.
• Functional programming languages which employs lazy evaluation strategies are called lazy languages otherwise non lazy languages.
• In lazy languages, function arguments may be infinite data structures (especially lists), the components of which are evaluated as needed.
• Lazy evaluation can lead to a less constrained programming style. It helps in delay of unnecessary computation (explained later).
• Full Laziness is obtained by further optimizing a lazy evaluation by transforming a program by evaluating all those sub expressions in a function body which do not depend on the function's arguments.
• Generally, in non lazy languages, it is essential that conditional expressions have special form whose evaluation does not require full evaluation.
• Exceptions to the rule of strict (eager) evaluation for the conditional expression if E then E₁ else E₂ are given below. Let us assume that the symbol v denotes undefined expression.

Conditional expression Evaluated value

If E = true then E₁ else v E₁

If E = false then v else E₂ E₂

If E = v then E₁ else E₂ v

• If non lazy languages do not provide lazy evaluation of conditional expression, then it could be simulated (explained later).
• In lazy functional languages, conditional expressions can be treated as ordinary functions such as

- fun conditional (true, x, y) = x

| conditional (false, x, y) = y

• The evaluation of a function call conditional (E , E₁, E₂) has the same behaviour as if E then E₁ else E₂ under lazy evaluation strategy.
• It is evident that common style of programming is not possible for both lazy and eager evaluations because of subtle differences.
• Some commonality can be achieved by transformational approach to program construction.

• The evaluation rule in SML is eager (strict) evaluation, while most of pure functional languages adopt lazy evaluation.
• SML provides lazy evaluation of conditional expressions and infix boolean operators.

• As a special case, SML evaluates conditional expression using lazy strategy. Consider the following conditional expression

if E then E₁ else E₂

• If E is true then E₁ is evaluated and E₂ is not.
• If E is false then E₂ is evaluated and E₁ is not.

- if true then 4 else 23 div 0 ;

> val it = 4 : int

- if false then (4 div 0) else 5;

> val it = 5 : int

• In SML, boolean infix operators andalso, orelse are not functions but are conditional expressions, so are evaluated using lazy strategy. All other SML infixes are really functions.
• In SML, evaluation of E₁ andalso E₂ amounts to basically evaluating if E₁ then E₂ else false, where E₁ and E₂ are expressions.
• So an expression E₂ is evaluated if required or needed. Similarly E₁ orelse E₂ is equivalent to if E₁ then true else E₂. In SML infix operator andalso is defined as follows:

- infix andalso

- fun true andalso b = b

| false andalso b = false

- false andalso 4 > (6 div 0) ;

> val it = false : bool

- true orelse 4 > (6 div 0) ;

> val it = true : bool

• We know that function bodies are not evaluated until the functions are applied.
• This means that the evaluation of any expression can also be delayed by embedding the expression within the body of a function whose argument is dummy (unused value). Normally, empty tuple ( ) : unit is used for this purpose.

- fun delay ( ) = Exp

Here 'a is the type of an expression Exp. An application of delay to an empty tuple will require an evaluation of Exp.

• It is possible to simulate lazy evaluation within an eager languages by making use of higher-order functions which means that the functions are passed in place of simple arguments.
• But the resulting programs are more difficult to write, read and maintain. Delay mechanism helps simulating normal order evaluation (call by name) in non lazy languages.
• The function compute defined below have arguments of the type 'a list. Here the lists are evaluated at the time of applying compute function as eager evaluation is used in SML.

- fun compute (x, y) = if null (x) then [] else hd(x) :: y ;

- val p = compute([3,4,5],[6,7,8,9]);

- val q = compute ([], [1,2,3,4,5]);

• If we want to delay the evaluation of lists at the time of applying function, we can modify above function as follows:

- fun delayf (fun1, fun2) = if null ( fun1( ) ) then [] else hd(fun1( )):: fun2( );

• The functions compute and delayf are similar except that the arguments of function compute are of the type 'a list and that of delayf are functions of the type unit -> 'a list.

Calls to both the functions are: compute(a, b) and delayf (( fn( ) Þ a), (fn( ) Þ b)).

• They produce the same result but the evaluation of a and b are delayed until the arguments to delayf are applied. In particular if the value of a is null then b is not evaluated.
• Few calls to both the functions are given below:

- val x =[3,4,5];

- val y = [6,7,8,9];

- fun fun1( ) = x;

- fun fun2( ) = y;

- val p = delayf ( (fn( ) =>x), (fn( ) =>y) );

- val q = delayf ((fn( ) =>y), (fn( ) =>p) );

- val r = delayf ((fn ( ) => [ ] ), (fn ( ) => q));

OR

- val p = compute ( x, y );

- val q = compute (y, p);

- val r = compute([ ], q);

• Therefore, the functions as arguments to other functions delay evaluation until the function argument is applied.
• If function argument is applied more than once then in this kind of simulation, function argument is evaluated as many times as it is applied.
• This is basically a simulation of call by name and not call by need (lazy evaluation).
• If we want to avoid repetition of evaluation of function arguments, then this can be achieved by using local definition (let in SML) to compute the value at the time of first application and then use that local variable when ever it is required.
• Consider the following function.

- fun comp (x, y) = if null(x) then [] else y @ y @y;

- fun delay1 (fun1,fun2) = if null(fun1( )) then [] else fun2( ) @ fun2( ) @ fun2( );

• Here if fun1( ) is not null then fun2( ) is evaluated thrice. To avoid this repetition, let us rewrite another version of the same function.

- fun delay_lazy (fun1,fun2) = if null(fun1( )) then [] else let val temp = fun2 ( )

• The function, delay_lazy simulates the lazy evaluation strategy.
• Eagerly evaluated conditional expression in non lazy languages could also be easily simulated by using delay mechanism as follows:

- fun cond (x, y, z) = if x then y( ) else z( );

- val n = cond (true, (fn( ) => 4), (fn( ) => 34 div 0)) ;

• It is evident that the second argument (undefined) of application of function cond has not been evaluated. The effect is same as that of lazy evaluation and the function is behaving as non strict function.
• The evaluation has been delayed by using function as an argument. Similarly, the first argument is not evaluated in the following application of cond in the following case.

- val n = cond (false, (fn() => 4 div 0 ), (fn() => 34 ) );

> val n = 34 : int

For illustration, the functions are written in SML.

• Lazy languages avoid unnecessary computations. If long computations are not needed, they will not be done in lazy evaluation environment.
• Let us consider a case of lists equality. If we compute an equality of two long lists with different first items, then their tails are not evaluated in lazy languages.
• Comparing two lists

- infix equal;

- fun ([] equal []) = true

| ((a::x) equal (b::y)) = (a = b) andalso (x equal y)

| ((a::x) equal []) = false

| ([] equal (b::y)) = false;

• In non lazy languages such as SML, tails are also evaluated even if a ¹ b because equal is strict function and requires both the arguments to be evaluated before executing its body.
• Comparing two binary trees for preorder sequence equality. Here we make use of equality function defined for list.

- datatype 'a BT = Null | Node of ‘a BT * ‘a * 'a BT;

- fun preorder Null = []

| preorder (Node (left, data, right))= [data] @ preorder left @ preorder right;

- fun tequality(t1, t2) = preorder (t1) equal preorder (t2); {list equality}

- val t = Node(Node (Node (Null, 3, Null), 2, Null), 1, Node(Node(Null,5, Null),

- val t1 = Node(Node (Null, 2, Null),1, Node(Node(Null,4, Null),3, Node(Node(Null,6,Null), 5, Null)));

- val x = tequality (t, t1);

- tequality (Node(Null, 6, Null), Node (Node(Null, 4, Null), 2, Null))

Evaluation: tequality (Node(Null, 6, Null), Node (Node(Null, 4, Null), 2, Null))

= preorder (Node(Null, 6, Null)) equal preorder (Node (Node(Null, 4, Null), 2, Null))

= [6] @ preorder(Null) @ preorder(Null) equal [2] @ preorder(Node (Node(Null, 4, Null)) @ preorder(Null)

= (6:: [] @ preorder(Null) @ preorder(Null) equal (2 :: [] @ preorder(Node (Node(Null, 4, Null)) @ preorder(Null)

= (6 = 2) andalso ([] @ preorder(Null) @ preorder(Null) ) equal ([] @ preorder(Node (Node(Null, 4, Null)) @ preorder(Null)

= false andalso ...... equal .......

= false

• During lazy evaluation, calls to functions moves back and forth to give rise coroutine like behaviour whereby each function is driven by request for some output from another function requiring some input.
• Therefore, the functions call each other and returns values as and when required. For example, in tree equality, if first value of both the trees in preorder sequence are equal then second element of first tree is computed followed by second element of second tree and so on otherwise false is returned.
• So at no point in time both the lists are computed completely thus avoiding redundant computation.

• If a function terminates via any reduction order, then the result will be the same using lazy evaluation.
• The functions which are non terminating in non lazy languages can terminate in lazy languages. For example, define a function for computing factorial as follows:

- fun conditional (x, y, z) = if x then y else z;

- fun fact n = conditional (n=0, 1, n * fact(n-1));

• The function fact is non terminating in non lazy (eager) languages. If we call fact(0), it goes into non termination as the arguments of function conditional gets evaluated before its body is executed.

- val x = fact (0);

- val y = fact (2);

fact (0) = conditional (true, 1, 0 * fact(-1) )

It is non terminating.

y = fact(2)

= conditional(false, 1, 2 * fact(1))

= conditional (false, 1, 2 * conditional (false, 1, 1 * fact(0)))

Because of fact (0) in the argument of conditional it goes into non termination as explained above,

- val x = fact (0);

- val x = fact (4);

• It gives result as 1 for fact(0) because 0 * fact(-1) will not be evaluated at all.
• As already mentioned earlier, lazy evaluation can be simulated to some extend in eager languages.
• The same function fact is rewritten using delay mechanism for eager languages. Of course the function becomes difficult to be understood.
• We make use of function cond that simulated lazy evaluation.

- fun fact n = cond ( n = 0, (fn() => 1), (fn() => n* fact (n-1)));

- fact 0;

- fact 4;

• Generate an infinite list of integers in increasing order starting from some initial value.

- fun gen(n) = n::gen(n+1);

• Define another function get to obtain first n elements of an infinite list generated as above.

- fun get (1, x::xs) = [x]

| get (n, []) = [0]

| get (n, x::xs) = x:: get(n-1, xs);

- val x = get (3, gen(1) );

> non termination

x = get (3, gen(1) ) = get(3, 1 :: gen(2))

= get(3, 1 :: 2 :: gen(3)) = get(3, 1 :: 2 :: 3 :: gen(4))

• It is non terminating because of infinite list as an argument of function get. It is to be evaluated before executing the body of get.

- val x = get (3, gen(1) );

> val x = [1,2,3]

• It gives a list of first 3 elements from infinite list generated by function gen because the elements in a list are only evaluated when required by another function.

Evaluation:

x = get(3, gen(1)) = get(3, 1 :: gen(2))

= 1 :: get(2, gen(2)) = 1 :: get(2, 2::gen(3))

= 1 :: 2 :: get(1, gen(3)) = 1 :: 2 :: get(1, 3::gen(4))

= 1 :: 2 :: [3] = [1,2,3]

• Consider another problem of generating infinite sequence of numbers in increasing order using the following the following formula.

Number = 2ⁿ * 3^m , " n, m ³ 0

The list of numbers can be defined informally as:

1. 1 is valid number,
2. if x is a valid number, then 2x and 3x are also valid numbers.

• Thus, an infinite sequence of numbers generated by above definition is 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36 .....
• In most of the languages, this is quite complex but using lazy evaluation technique it can be easily expressed.
• We define a function seq that generates an infinite list of numbers in increasing order stated as above using another function get_next.
• The function merge is used in get_next that takes two ascending lists and merges them maintaining the ordering and removing duplicates.

- fun seq ( ) = get_next [1];

- fun get_next (x :: xs) = x :: get_next (merge ( [2*x, 3*x], xs ));

- val t = get (5, seq( ));

- val t = get (5, seq( ));

t = get (5, seq ( ))

= get (5, 1 :: get_next (merge([2,3], [])))

= 1 :: get (4, get_next ([2,3]))

= 1 :: get (4, 2 :: get_next(merge([4,6], [3]) ))

= 1 :: 2 :: get(3, get_next([3,4,6]))

= 1 :: 2 :: get(3, 3 :: get_next(merge([6,9], [4,6])))

= 1 :: 2 :: 3 :: get (2, get_next ([4,6,9] ) )

= 1 :: 2 :: 3 :: get (2, 4 :: get_next (merge([8,12], [6,9])))

= 1 :: 2 :: 3 :: 4 :: get (1, get_next([6, 8, 9, 12]))

= 1 :: 2 :: 3 :: 4 :: get (1, 6 :: get_next(merge ([12, 18],[8, 9, 12])))

= 1 :: 2 :: 3 :: 4 :: 6

= [1,2,3,4,6]

• Generate a list of prime numbers using Eratosthenes sieve method which does the following:

1. Initially, assume that 2 is a prime number.
2. Find prime numbers by removing the non prime numbers from a list of integers generated from 2 onwards.
3. Non prime number is one which is a multiple of some previously generated prime number.

Alternatively, we can state the method as follows:

• Get a number from a infinite list generated from 2 onwards and check if it is non prime. If not, then attach this number to the list of primes generated otherwise generate new number. Repeat this method as many time as you want.

- fun not_multiple x y = (y mod x <> 0);

- fun filter f [] = []

| filter f (x::xs) = if f (x) then x :: filter f xs else filter f xs;

- fun remove x [] = []

| remove x xs = filter (not_multiple x) xs;

- fun main (x ::xs) = x :: main(remove x xs);

- fun primes ( ) = main (gen 2);

- get(4, primes( ));

- get(4, primes( ));

• Lazy languages also include lazy constructors, hence provide one of the most important benefits of lazy evaluation i.e., the ability to handle infinite data structures.
• So far we have seen function and data types being defined recursively.
• It is very useful if we define infinite data structure like list, trees, infinite series and any infinite mathematical structure and assign them directly to the variables and use them directly in the program.
• Further, lazy evaluation helps in creating cyclic data structures, which would terminate. The following are recursive definition of some infinite data structures.
• Define a variable inf_list which is an infinite list of 1.

- val rec inf_list = 1:: inf_list;

- val x = get(10, inf_list);

- val rec pair_list = (1,2) :: pair_list;

- val y = inf_list equal pair_list;

- val z = get(3, pair_list);

• Infinite list can be constructed and easily used in lazy languages as arguments of other functions. Functions get and equal are defined earlier.

• Define a variable inf_tree for infinite binary tree with all nodes having value 6.

- val rec inf_tree = Node (inf_tree, 6, inf_tree);

- val x = get (5, preorder (inf_tree));

- val rec t = Node (Node (Null, 4, Null), 5, t);

• Recursive definition for an infinite sequence of numbers in increasing order using the following formula.

Number = 2ⁿ * 3^m , " n, m ³ 0

This problem has also been discussed earlier and was solved by using recursive function. Alternatively the problem is stated as:

1. 1 is valid number,
2. if x is a valid number, then 2x and 3x are also valid numbers.

- val rec seq_num = 1:: merge ((map(times 2) seq_num), (map(times 3) seq_num))

The function map multiplies 2 or 3 whichever the case might be to the head of recursive list seq_num whenever there is a need. It is defined as follows:

- fun map f [] = []

| map f (x :: xs) = f x :: map f xs ;

• List is constructed as follows:

seq_num = 1:: merge ((map(times 2) seq_num), (map(times 3) seq_num))

= 1 :: merge (2 :: (map(times 2) seq_num), 3 :: (map(times 3) seq_num))

= 1 :: 2 :: merge ((map(times 2) seq_num), 3 :: (map(times 3) seq_num))

= 1::2::3 :: merge (4 :: (map(times 2) seq_num), (map(times 3) seq_num))

• Writing algorithms for numerical techniques finding solution(s) by successive refinement till the difference between previous solution and the current solution is negligible is more elegant and concise.
• Newton Raphson is numerical technique for solving equation of the form f(x) = 0. It starts with good initial approximate solution and converges rapidly to the solution.
• Computing square root of a real number is an application of Newton Raphson method. The equation f(x) = x² - a = 0 is solved for finding square root of a real number say, a.

x² - a = 0 Þ x² = a Þ x = Ö a

• Consider initial solution to be x₀ = 1.0 and next solution is obtained by the following formula.

x_i = (x_(i-1) + a / x_(i-1) ) / 2.0

Termination condition: (x_i - x_(i-1) ) < .000001

- fun gen (a, n) = n :: gen(a, (n + a / n) / 2.0);

- fun findroot (a) = gen (a, 1.0);

- fun terminate(x::y::xs) = if (x-y ) < 0.00001 then x else terminate (y :: xs);

- fun sqrt (a) = terminate (findroot (a));

• A function sqrt calls a function terminate which is a higher order function. Argument of terminate is another function findroot that generate a list of possible solutions by using function gen.
• In eager evaluation, sqrt is a non terminating function but it terminates for lazy evaluation.

• The lazy functions can be written without containing operational control as evaluation is demand-driven.
• Therefore, Laziness can help in separating data from control. It gives a pipeline approach to a program construction. For example, given the following components:

- fun cube [] = []

| cube (n:: ns) = n*n*n :: cube ns;

- fun double [] = []

| double (n::ns) = n + n :: double ns;

- fun positive x = if x > 0 then true else false;

- fun main ( ) = double (cube(filter positive (get_list)));

• We can compose them simply to create a pipeline that filters out positive numbers from a list, cube them and then double them. The function filters is defined earlier.
• The important point is that function main has been written without knowing the size of the list.
• Lazy evaluation has therefore freed the programmer from operational control issues like exiting from a loop in imperative languages.
• Here get_list operates on demand and supplies an element of a list (of unknown size).
• This pipeline style generally leads to clearer, more maintainable solutions and prompts the observation that laziness may provide important links in the convergence of functional programming, visual programming and analysis and design methods.

 Interactive program

• Lazy evaluation forms the basis for effective, elegant interaction. Consider an interaction at the highest level as a function taking responses and returning requests on the demand.

rsponses -> function -> requests

• Demand driven evaluation with suspensions can be regarded as a special case of several components of a program working independently and communicating via demand.
• It gives rise coroutine kind of behaviour whereby each process is driven by demand for some output from another process requiring some input.
• Processes are suspended as soon as the demand is satisfied but may resume when further demands are placed on them.
• A interactive program reads in different values of X (requests) and outputs the values (responses) at different stages can easily be expressed as a function which takes a list of values for X and produces a list of responses.
• In order to generate requests before receiving responses, the program must be lazy with its argument otherwise it would hang forever waiting for responses that haven't yet been requested.
• Even though there is a large semantic gap between a purely functional program and the outside world.
• The goal is to provide elegant, purely functional mechanisms for input/output and sequencing.
• Recent research advances, however, such as the Haskell I/O system [HPW92], have tamed many of these problems and a variety of effective bridges now exist

 Simulation and Implementation of infinite data structures in SML

• As already mentioned earlier, evaluation can be delayed in eager languages by using higher order functions.
• In eager evaluation, only functions can be defined recursively and recursive data structures can not be defined directly because of non termination problem.
• But infinite data structure can be simulated with eager evaluation by use of higher order functions which expand the structure bit by bit i.e., a data structure containing functions can represent an infinite object such as infinite lists, trees etc.

• In order to avoid unnecessary computation in comparing two lists, one can simulate lazy comparison in SML (in any eager language).
• We define below the datatype for lazy list whose element is constructed by applying function of the type (unit ->'a * 'a lazy_list). E_list represents an empty list.

- datatype 'a lazy_list = ML_list of (unit ->'a * 'a lazy_list) | E_list;

• Various functions for lists constructed using above datatype.

- fun cons x xs = let fun f( ) = (x, xs) in ML_list f end;

- fun head E_list = ~1

| head (ML_list f) = let val (x, xs) = f( ) in x end;

- fun tail E_list = E_list

| tail (ML_list f ) = let val (x, xs) = f( ) in xs end;

- fun null E_list = true

• Function for comparing two lists for equality

- infix eq

- fun (E_list eq E_list ) = true

in (x = y) andalso (xs eq ys ) end

| ((ML_list f) eq E_list) = false

| (E_list eq (ML_list f)) = false;

• Construction of a list and its operations

- cons 4 E_list;

- cons 4 it;

- cons 7 it;

- val p = cons 8 it;

- head p;

- tail p;

- p eq it;

- val q = p;

- p eq q;

Construction of infinite lists: (list of ones, list of natural numbers etc.)

• The same datatype definition is used for constructing infinite lists.

- val inf_ones = let fun f( ) = (1, ML_list f) in ML_list f end;

- fun gen n = let fun f ( ) = (n, gen (n+1)) in ML_list f end;

- val nat = gen 1;

- val from10 = gen 10;

• Function for getting finite number of elements from infinite list

- fun front n s = get_first(lazy_get n s);

where get_first and lazy_get are defined below:

- fun lazy_get 0 s = ([], s)

| lazy_get n E_list = ([],E_list)

| lazy_get n (ML_list f) = let val (x, xs) = f();

val (y,ys) = lazy_get (n-1) xs in (x::y, xs) end;

- fun get_first (x, y) = x ;

• Extracting finite values using front function

- front 5 inf_ones;

- front 10 inf_ones;

- front 6 nat;

- front 10 from10;

• With eager evaluation, earlier function for comparing two trees in preorder gives wasteful computation by getting preorders of both the lists and then comparing these lists using list comparison function.
• If we combine the actions of flattening binary trees and comparing lists, then in case when elements of both the binary trees in the preorder sequence are not equal, remaining portions of the trees could be avoided for computation.

- datatype 'a BT = Null | Node of 'a BT * 'a * 'a BT;

• The function tree_eq makes use of another function stack_compare which compares values in two stacks each consisting of binary trees.
• Initially stack contains binary trees. Get top element of both the stacks and compare the value at the root. If they are equal then both the trees are split into sub trees (left and right) and stored in their respective stacks.
• The process is repeated till the stacks are empty or values do not match. The processing of sub trees when the values do not match is delayed.

- fun stack_compare [] [] = true

| stack_compare [] (a::x) = if a = Null then stack_compare [] x else false

| stack_compare (a::x) [] = if a = Null then stack_compare x [] else false

| stack_compare (Null::x) y = stack_compare x y

| stack_compare x (Null::y)= stack_compare x y

| stack_compare (Node(l1,d1,r1)::x) (Node(l2,d2,r2)::y) = if (d1 = d2) then stack_compare (l1 ::r1::x) (l2::r2::y) else false;

- fun tree_eq t1 t2 = stack_compare [t1] [t2];

• Creating binary trees as follows

- val t = Node(Node(Node (Null,3,Null),2,Null),1, Node(Node(Null,5, Null), 4, Node(Null, 6, Null)));

- val t1= Node (Node (Null,1,Null),2,Node(Node(Null,4, Null, 3, Node

(Node(Null,6,Null), 5, Null)));

- val x = Node(Node(Node (Null,2,Null),1,Node(Node(Null,5, Null), 4, Null));

- val y = Node (Node (Null,1,Null),2,Node(Null, 3, Null));

• Comparing two binary trees

- val p = tree_eq t t1;

- val q = tree_eq x y;

• Define datatype for binary tree using function as an argument. The binary tree is either Null or (Node f ), where f is a function of type unit -> 'a BT * 'a * 'a BT.
• Using function one can delay evaluation of a node. Node is evaluated only when function is applied.

- datatype 'a BT = Null | Node of (unit -> 'a BT * 'a * 'a BT);

• One can construct a binary search tree using following delayed_insert function defined below:

- fun delayed_insert(key, Null) = let fun f() = (Null, key, Null) in Node f end

fun g ( )= (delayed_insert (key,left), k,right) in Node g end else let fun h( ) = (left, k, delayed_insert (key, right)) in Node h end end;

• Functions for traversing binary trees

- fun preorder Null = []

| preorder (Node f)= let val (left, data, right) = f( ) in [data] @ preorder left @ preorder right end;

- fun inorder Null = []

| inorder( Node f) = let val (left, data, right) = f( ) in inorder left @ [data] @ inorder right end;

- fun postorder Null = []

| postorder(Node f) = let val (left, data, right) = f( ) in postorder left @ postorder right @ [data] end;

- val tree6 = let fun f () = (Node f, 6, Node f) in Node f end;

- val tree23 = let fun g ( ) = (Node f, 2, Null) and f ( ) = (Node g, 3, Null) in Node g end;

- val t = let fun f ( ) = (Null, 1, Node f) in Node f end;

• Function for getting fixed number of values from infinite binary tree in preorder sequence.

- fun l_get 0 s = ([], s)

| l_get n Null = ([], Null)

| l_get n (Node f) = let val (l,d,r) = f( ); val (d1, xs) = if null l then l_get (n-1) r else l_get (n-1) l in (d::d1, l) end ;

- fun fst (x, y) = x ;

- fun front n s = fst(l_get n s);

- front 6 t;

- front 5 tree6;

- front 8 tree23;

• Comparing two infinite binary tree

- fun delayed_stack_eq [] [] = true

| delayed_stack_eq [] ((Node f)::x) = false

| delayed_stack_eq ((Node f)::x) [] = false

| delayed_stack_eq (Null::x) y = delayed_stack_eq x y

| delayed_stack_eq x (Null::y) = delayed_stack_eq x y

| delayed_stack_eq ((Node f)::x) ((Node g)::y) = let val (l1,d1,r1) = f(); val (l2,d2,r2) = g() in if (d1 = d2) then delayed_stack_eq (l1::r1::x) (l2::r2::y) else false end;

- fun tree_equality t1 t2 = delayed_stack_eq [t1] [t2];

- tree_equality t tree6;

• The function tree_equality gives rise false value as soon as it does not match two corresponding values in binary trees but goes into non termination if trees are equal.

• Although functional languages allow user to ignore the underlying mechanism that manages data, the system must still manage that memory.
• When laziness is introduced, the situation becomes more complex, and there is conflicting evidence as to whether it helps or hinders memory management.
• Laziness undoubtedly adds a memory management overhead, although some case studies identify situations when memory management allows lazy functional languages to beat not only eager ones, but imperative languages as well (see [KoOt93]).
• Traditionally, lazy functional languages executes slower than eager ones. This is due to overheads required to handle closures or equivalent constructs.
• But in some cases, it largely depends on the nature of algorithm. A well-designed lazy programs execute faster than eager ones.
• Laziness can be exploited to make a simple dynamic-programming algorithm run quickly as explained in [All92].
• Execution efficiency can also be viewed as trade off between fast eager code against better engineered lazy code from software engineering point of view.
• Garbage collection is a problem in functional programs which may effect run-time performance of functional programs in terms of both time and space.
• Lazy evaluation computational model is harder to interpret and analyze.