% ------------------------------------------------------------------------------
\section{Rejecting demand dependent programs}
\label{Strict-and-head-lazy-mapping}

Consider the definition of the strict $\imap$ function.

\begin{tabbing}
MM \= MM \= MMMMMM \= MMMMM \= MMMM \kill
	\> $\imap \ \ilist$ \\
	\> \ $= \kcase \ \ilist \ \kof$ \\
	\> \> $\iNil$			\> $\to \iNil$ \\
	\> \> $\iCons \ x \ \ixs$	\> $\to \iCons \ (f \ x) \ (\imap  f \ \ixs)$ 
\end{tabbing}

As the evaluation order of $\imap$ depends only on its definition, and not the surrounding program, we can safely apply it to an impure parameter function. For example, the following expression will print ``\texttt{123}'' in any evaluation context.
\begin{tabbing}
MM \= MMMMMMM \= MM \= MMMMMM \= MMMMM \= MMMM \kill
	\> $\iprintSquare \ x$ 	\> $= \kdo \ \{ \ \iprint \ x; \ x * x \ \}$ \\
	\> $\isquares$		\> $= \imap \ \iprintSquare \ [1, 2, 3]$
\end{tabbing}

Our do-expressions contain a sequence of statements or non-recursive bindings, end with a statement, and are executed left to right. The value of the whole expression is the value of the last statement. In our concrete implementation, when $\isquares$ is applied it allocates five objects into the heap. Three for the $\iCons$-cells, one for the $\iNil$ element, and three for the squared integers.
\begin{center}
\includegraphics[scale=0.5]{fig/map123}
\end{center}
To define a lazy version of map, we have three options of where to introduce the laziness. We could suspend the function application that creates the head elements, the recursive call that creates the tail of the list, or both. We create suspensions with $(\isuspend \ f \ x)$ where $\isuspend$ takes a parameter function, its argument, and creates a thunk. The thunk is forced automatically when its value is demanded by the right of a function application, or the discriminant of a case-expression. Forcing a thunk causes the embedded function application to be evaluated, and the thunk overwritten with the resulting value. Here is the version of $\imap$ that suspends application that creates the elements of the list, and a binding that uses it.

\begin{tabbing}
MM \= MM \= MMMMMM \= MMMMM \= MMMM \kill
	\> $\imapLH \ f \ \ilist$ \\
	\> \ $= \kcase \ \ilist \ \kof$ \\
	\> \> $\iNil$			\> $\to \iNil$ \\
	\> \> $\iCons \ x \ \ixs$	\> $\to \iCons \ (\isuspend \ f \ x) \ (\imap_{LH}  f \ \ixs)$ 
\end{tabbing}

\begin{tabbing}
MM \= MMMMMM\= MMMMMM \= MMMMM \= MMMM \kill
 	\> $\ibadSquares$	\> $= \imapLH \ \iprintSquare \ [1, 2, 3]$
\end{tabbing}

The trouble with this definition is that if $\imapLH$ is applied to impure parameter functions, the result of the application can depend on the evaluation order of the resulting list elements. Here is the object that represents the value of $\ibadSquares$.

\begin{center}
\includegraphics[scale=0.5]{fig/mapLH123}
\end{center}

In this diagram the @ nodes are application thunks, and the arrow labled with $\ipS$ represents a pointer to the code for $\iprintSquare$. Now, the first time we inspect each of the list elements, the corresponding integer will be printed to the console. This will not cause the program to ``go wrong'' in the usual sense, that is, it will not crash, but it does limit the sort of optimisations we can perform. If we change the order that the list elements are demanded, then we will change the meaning of the program. Because of this we wish to detect and reject such programs.
