cdiggins.com

In a functional stack-based langauge, it is quite natural to handle local assignment with destroying referential transparency. The following is from a recent post I made to Lambda-the-Ultimate.org in order to ascertain the wider thinking on the problem.

Okay, this might seem like an odd question, but is there contention on whether or not a while loop that performs assignment on local function variables is pure functional? For example the following Java code:

int process(int[] xs)  {

   int zeros = 0;

   int sum = 0;

   int i=0;

   while (i < xs.Size) {

     if (xs[i] == 0)

       zeros++;

     sum += xs[i];

     ++i;

   }

   return sum - zeros;

 }

Now I have heard frequently that the above code is considered to have side-effects because of the local assignments to variables. However, the mapping to pure-functional stack-based code (here shown in Cat) is very straightforward:

define process {

   // top argument = xs

   0 // zeros

   0 // sum

   0 // i

   [

     dig3 // bring xs to top of local stack

     dupd swap get_at eqz // xs[i] == 0

       [[inc] dip3] // inc zeros

       []

     if

     dupd swap get_at // tmp = xs[i]

     [bury3] dip // put xs to bottom of local stack

     swap [add_int] dip // sum += tmp

     inc // ++i

   ]

   [

     dig3 count [bury3] dip // tmp = xs.Size

     dupd lt_int // i < tmp

   ]

   while

   pop // remove i

   swap sub_int // sum-zeros

 }

So, my problem is that I am not sure whether this is old news or new news. Any feedback would be appreciated.

For those interested, the type of “while” in Cat is (’A (’A -> ‘A) (’A -> ‘A bool) -> ‘A). In other words, while takes a stack with two functions on the top, the first one is a predicate and the next one is the loop body. If the predicate returns true, the loop body is executed, and the process is repeated. The loop body takes the rest of the stack as an argument, and returns it in the same state. The predicate is the same, but in addition pushes a boolean value.

If you really feel like geeking out then we can define while from core primitives using the “m” recursive combinator (m == dup apply) as follows:

define m_while : ('A ('A -> 'A) ('A -> 'A bool) -> 'A)  

{{  

  desc:  

    A while function written using the m (a.k.a. U) combinator  

  test:  

    in: 1 5 [[2 mul_int] dip dec] [is_neqz] m_while pop  

    out: 32  

}}  

{
  // [$A] [$B]  

  [dip swap] papply      // [$A] [[$B] dip swap]  

  swap               // [[$B] dip swap] [$A]  

  [dip m] papply     // [[$B] dip swap] [[$A] swap m]  

  quote compose      // [[$B] dip swap [[$A] dip m]]  

  [[pop] if] compose // [[$B] dip swap [[$A] dip m] [pop] if]  

  m
}

To be completely forthright there is a small bug in the “m_while” code. The actual inferred type is “(’A (’B -> ‘C) (’A -> ‘B bool) -> ‘B)”. This is because my type-inference engine can not currently handle recursive types properly (it used to, honest!). This is just a question of finding the time to sit down and fix it, at least theoretically there are no hurdles preventing one from performing inference of equi-recursive types.

This entry was posted on Thursday, April 10th, 2008 at 5:46 pm and is filed under Everything. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.