Related to: Capturing abstractions in Lisp

I came across Yay today, which allows us to use macros in PHP. Cool right?

Start with

composer require yay/yay:dev-master

Then you can use

vendor/bin/yay

to pre-process your code with macros.

Now we can implement lazy evaluation (kinda) in PHP!

We start with:

<?php
macro {
    __delay( ···expression )
} >> {
    function() { return ···expression; }
}

function force( $x ) {
    return $x();
}

function not_a_delay( $x ) {
    return function() use ( $x ) {
        return is_callable( $x ) ? $x() : "Not a callable function";
    };
}

echo "__delay start\n";
$x = __delay( printf( "The time function returns: %d\n", time() ) );
echo "__delay end\n";

echo "\n----------\n\n";

echo "force start\n";
echo 'Retval: ' . force( $x ) . "\n"; // print here!
echo "force end\n";

echo "\n----------\n\n";

echo "not_a_delay start\n";
$x = not_a_delay( printf( "The time function returns: %d\n", time() ) ); // print here!
echo "not_a_delay end\n";

echo "force start\n";
echo 'Retval: ' . force( $x ) . "\n";
echo "force end\n";

So if we look at the output:

boro@bor0:~/Desktop/test$ vendor/bin/yay test.php | php
__delay start
__delay end

----------

force start
The time function returns: 1494937031
Retval: 38
force end

----------

not_a_delay start
The time function returns: 1494937031
not_a_delay end
force start
Retval: Not a callable function
force end

The two big differences are line 19 and 31 of the code. As we can see from the output, line 19 got “delayed”, while line 31 got evaluated eagerly.

For the sake of discussion, let’s consider a recursive and an iterative function that converts a number to a list.

(define (number->list l)
  (if (= l 0)
      '()
      (cons
       (remainder l 10)
       (number->list (quotient l 10)))))

(define (number->list-iter l acc)
  (if (= l 0)
      acc
      (number->list-iter
       (quotient l 10)
       (cons (remainder l 10) acc))))

Calling the functions produce:

> (number->list 123)
'(3 2 1)
> (number->list-iter 123 '())
'(1 2 3)

Further, let’s consider this same function rewritten in JavaScript, but implemented with stacks and queues instead of recursion:

function numbertolist_stack(n) {
        var stack = [n];

        while (stack.length) {
                var x = stack.pop();
		stack.push(x % 10);

                if (parseInt(x / 10)) {
                        stack.push(parseInt(x / 10));
                } else {
                        break;
                }
        }

        return stack;
}

function numbertolist_queue(n) {
        var queue = [n];

        while (queue.length) {
		var flag = false;
                var x = queue.shift();

                if (parseInt(x / 10)) {
                        queue.push(parseInt(x / 10));
		} else {
			flag = true;
		}

		queue.push(x % 10);

                if (flag) {
                        break;
                }
        }

        return queue;
}

So, now we have:

> numbertolist_stack(123)
[ 3, 2, 1 ]
> numbertolist_queue(123)
[ 1, 2, 3 ]

So, in terms of cons, what we can conclude is that recursion can be viewed as a stack, and tail recursion can be viewed as a queue. For if we haven’t worked in terms of cons, we can rewrite the Scheme iter function to use (append acc (list (remainder l 10))) instead of cons and achieve the same effect as number->list.

However, note that most interpreters that contain an implementation of tail call optimization wouldn’t probably implement a queue, but only a fixed set of variables in order to save space.

Another interesting observation is that we can look at it in terms of associativity (think foldr and foldl). foldr is implemented using a stack, and foldl is implemented using a queue, so that gives an idea in terms of associativity.

Or that we can implement depth-first search with a stack and breadth-first search with a queue.

IMHO, discovering relations like this is fun 🙂

Let’s consider the following code in Scheme:

#lang racket
(define (add-deferred x)
(if (eq? x 0) 0 (+ x (add-deferred (- x 1)))))

(add-deferred 3)
;(add-deferred 3)                   =
;(3 + (add-deferred 2))             =
;(3 + (2 + (add-deferred 1)))       =
;(3 + (2 + (1 + (add-deferred 0)))) =
;(3 + (2 + (1 + 0))) ## evaluate now

(define (add-iter x acc)
(if (eq? x 0) acc (add-iter (- x 1) (+ acc x))))

(add-iter 3 0)
;(add-iter 3 0) = ## evaluate
;(add-iter 2 3) = ## evaluate
;(add-iter 1 5) = ## evaluate
;(add-iter 0 6) = 9

And in C:

#include <stdio.h>

int add(int x) {
if (x == 0) {
return 0;
}

return x + add(x - 1);
}

int add_iter(int x, int acc) {
if (x == 0) {
return acc;
}

return add_iter(x - 1, acc + x);
}

int main() {
printf("%d\n", add(3));
printf("%d\n", add_iter(3, 0));
}

And then this quote from SICP:

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while.
The implementation of Scheme does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

Now since C doesn’t have tail call optimization, both calls actually produce a recursive process, that is the stack frame size grows with each call, while with Scheme the stack grows only in the case of a non-iterative process.