Re: Factor

The man or boy test was proposed by Donald Knuth:

“There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the man-compilers from the boy-compilers.”

— Donald Knuth

The Rosetta Code project has a list of implementations to compare with, and today we are going to contribute one in Factor. While the original was framed in ALGOL 60, let’s look at one contributed in Python, which is probably more readable for most of the audience:

#!/usr/bin/env python
import sys
sys.setrecursionlimit(1025)

def a(k, x1, x2, x3, x4, x5):
    def b():
        b.k -= 1
        return a(b.k, b, x1, x2, x3, x4)
    b.k = k
    return x4() + x5() if b.k <= 0 else b()

x = lambda i: lambda: i
print(a(10, x(1), x(-1), x(-1), x(1), x(0)))

In particular, this is challenging because it involves creating a “tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called.” And, as a result, many languages have difficulting calculating for large values of k due to recursion or depth limits.

In Factor, we have the ability to create inner computations by making quotations, which is essentially an anonymous version of the inner B function. These quotations are allowed to access the variables defined in their outer scope. Thus, we can implement the word reasonably simply by making a B quotation, binding it to a variable for reference, and then calling it:

:: a ( k! x1 x2 x3 x4 x5 -- n )
    k 0 <= [
        x4 call( -- n ) x5 call( -- n ) +
    ] [
        f :> b!
        [ k 1 - dup k! b x1 x2 x3 x4 a ] b!
        b call( -- n )
    ] if ;

The k argument is an integer, the others are quotations with stack effect of ( -- n ), meaning they take no arguments, and produce a number when called. We can call it and demonstrate that it works and produces the first few values of the output of Knuth’s “man or boy” test for varying k:

IN: scratchpad 13 [0..b] [
                   [ 1 ] [ -1 ] [ -1 ] [ 1 ] [ 0 ] a .
               ] each
1
0
-2
0
1
0
1
-1
-10
-30
-67
-138
-291
-642

Presently, larger values of k produce a “retain stack overflow” with the default Factor settings. I looked briefly into using our bend vocabulary, but it currently doesn’t support accessing the outer variable scope, and requires passing arguments on the stack. That would be a nice feature, and theoretically would then look like this simple example:

:: a ( k! x1 x2 x3 x4 x5 -- n )
    k 0 <= [
        x4 call( -- n ) x5 call( -- n ) +
    ] [
        BEND[ k 1 - dup k! [ fork ] x1 x2 x3 x4 a ]
    ] if ;

However, that doesn’t work at the moment. Maybe sometime in the future!