CTM: Exercise 3-9

[ Posted by Urban Hafner Thu, 15 Sep 2005 18:55:46 GMT ]

The problem

Iterative computations and dataflow variables. The previous exercise shows that using dataflow variables sometimes makes it simpler to write iterative list operations. This leads to the following question. For any iterative operation defined with dataflow variables, is it possible to give another iterative definition of the same operation that does not use dataflow variables?

My solution

I’m really unsure about this one. If anyone can explain it in a nice and convincing way I’d happily replace my hand waving with it.

If we assume that iterative computation means the function Iterate from section 3.2.4 then it seems possible to replace any use of dataflow variables. Just translate your function into one similar to Iterate and you have removed any dataflow variables.

Tags , , , , , ,

CTM: Exercise 3-8

[ Posted by Urban Hafner Thu, 15 Sep 2005 18:55:23 GMT ]

The problem

An iterative append. This exercise explores the expressive power of dataflow variables. In the declarative model, the following definition if append is iterative:

fun {Append Xs Ys}
   case Xs
   of nil then Ys
   [] X|Xr then X|{Append Xr Ys}
   end
end

We can see this by looking at the expansion:

proc {Append Xs Ys ?Zs}
   case Xs
   of nil then Zs=Ys
   [] X|Xr then Zr in
      Zs=X|Zr
      {Append Xr Ys Zr}
   end
end

This can do a last call optimization because the unbound variable Zr ca be put in the list Zs and bound later. Now let us restrict the computation model to calculate with values only. How can we write an iterative append? One approach is to define two functions: (1) an iterative list reversal and (2) an iterative function that appends the reverse of a list to another list. Write an iterative append using this approach.

My solution

The iterative list reversal is already defined in the book in section 3.4.2.4. Taking this Append can be defined as follows:

local
   fun {IterAppend RevXs Ys}
      case RevXs
      of nil then Ys
      [] X|Xr then {IterAppend Xr X|Ys}
      end
   end
in
   fun {Append Xs Ys}
      {IterAppend {Reverse Xs} Ys}
   end
end

Tags , , , , ,

CTM: Exercise 3-5

[ Posted by Urban Hafner Wed, 14 Sep 2005 19:24:24 GMT ]

The problem

An iterative SumList. Rewrite the function SumList of section 3.4.2 to be iterative using the techniques developed for Length.

My solution

local
   fun {IterSumList S Es}
      case Es
      of nil then S
      [] E|Er then {IterSumList S+E Er}
      end
   end
in
   fun {SumList L}
      {IterSumList 0 L}
   end
end

Tags , , , , , ,