## Tree @02a5277 (Download .tar.gz)

## recursion.txt @02a5277 — raw · history · blame

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | ```
Recursive closures =====================================================
Haldean Brown First draft: Nov 2016
Last updated: Jan 2018
Status: Complete
------------------------------------------------------------------------
The closure transformation turns closures into partially-applied
functions, by turning values that have been closed over into arguments
to the function itself. The specific algorithm for doing this is
detailed greatly in the header closure.c, but the general gist is that:
It transforms this:
\x -> (\y -> + x y)
To this:
\x -> ((\x0 y -> + x0 y) x)
It transforms this:
\x -> (\y -> (\z -> x))
Into this:
\x -> ((\x0 y -> ((\x1 z -> x1) x0)) x)
It transforms this:
\x -> {
: y = + x 10
! \z -> y
}
Into this:
\x -> {
: y = + x 10
! (\y0 z -> y0) y
}
This closes these functions over the enclosing scope by making all
enclosing scope information an explicit argument to the function, and
then partially applying the function over that information.
This document describes how the closure transformation interacts with
recursion for values that are not bound to a global name. For example,
this snippet:
! {
: t = \x -> ? {
. eq x 0 => "ok\n"
. => t 0
}
! t 1
}
In this example, t needs access to its own value from within its definition.
However, since t is a local binding, it's never actually assigned to a name
that persists past its own scope. To handle this, we transform t to take itself
as a parameter; callers then call t by passing it itself. The resulting
function then looks like:
: t = \$t x -> ? {
. eq x 0 => "ok\n"
. => $t $t 0
}
This poses a problem for the callers of this function, though; now all callers
have to know that t needs to be passed itself as its first argument, so the
immediate value of the block would be transformed to:
! t t 1
But this is clunky; we don't want to have to transform every call site that
references t. Instead, we transform t to a partially-applied function, with
itself already applied (for brevity, B is used to represent the body of the
function t as given in the previous listing):
: t = (\$t x -> B) (\$t x -> B)
Note that this can be very succinctly represented in Ubik bytecode, without
requiring a double-definition of the function, as the function must be its own
value:
000 VALUE &B
001 APPLY 000 000
This seems nice in practice, but there's one more sticky bit: the original
closure transformation. Let's take a slightly more complicated example:
: top = \x -> {
: inner = \y -> inner (+ x y)
! inner
}
Never mind that this is infinitely recursive: it's a nice simple example for
our syntactic transformations. The closure transformation takes inner from that
given in the previous listing to this:
: inner = (\x y -> inner (+ x y)) x
Which works fine. The recursion transformation would then take it to:
: inner =
(\inner x y -> inner inner (+ x y))
(\inner x y -> inner inner (+ x y))
x
This looks okay, but doesn't properly work, because the reference to inner in
the body of the function doesn't pass any of the closed-over parameters. What
we want is something more like:
: top = \x -> {
: inner_ = \x inner y -> inner (+ x y)
: inner_with_x_ = inner_ x
: inner_with_inner_ = inner_with_x_ inner_with_x_
}
But that doesn't work either. Hm. Instead, we introduce a secret atom type,
SELFREF, which is a reference to the innermost enclosing function. So we end up
rewriting inner to be:
: inner = (\x y -> {
: inner = SELFREF x
! inner (+ x y)
}) x
Now the "inner" on the inside doesn't actually reference a named binding on the
outside. When this is compiled down to a graph, SELFREF will be transformed
into a VALUE node that points at the value currently being compiled.
With more-heavily-nested recursion, this ends up transforming:
: outer = \a -> {
: inner = \b -> outer (+ (inner a) b)
! inner a
}
Into:
: outer = \a -> {
: outer = SELFREF
: inner = (\a outer b -> {
: inner = SELFREF a outer
! outer (+ (inner a) b)
}
}
Which actually ends up being pretty pleasantly readable.
``` |