Hi Ladislav,
thanks for your response.
In the message you were responding to, I was commenting on your recursive
function example. Why then did your response include a *non*-recursive
function - your second example - that contains an embedded fun2 in a parent
fun1? Both functions have an argument called x. Were you trying to
demonstrate that each of the two x's retain their respective binding, which
is local to their respective functions? I was not disputing that.
Certainly the two x's are bound in different contexts. The first 'x in
fun1's context and the second 'x in fun2's context. Given that each 'x is
bound in a different context, and the context of both x's is extended by
appending them to the block blk, reduce [x x] returns the block [2 1],
demonstrating that each of the two x's retained their binding, and
therefore each 'x evaluates to the value it is associated with by virtue of
being bound bound in the context of the function it is associated with.
Perhaps you felt it necessary to demonstrate non-recursive function calls,
because you misunderstood me? To set the record straight:
1. Identical tokens that are bound in different contexts ('x bound in fun1,
'x bound in fun2) retain their respective values.
2. I am not claiming that in recursive function calls those words that are
local to the function being called recursively are duplicated during the
recursive call.
You appear to comment on something I said:
>As you pointed out, there is a conflict of two things:
>"Static Context Binding" vs. "Dynamic Value Binding". As a
>consequence, Use may misbehave during recursive calls.
Interestingly you agree here with something I never said, nor intended to
say. Apparently you did misunderstand me. Maybe I did not explain what I
meant well enough.
Since I am not sure where the misunderstanding begins, let me start with
the basics. I'll present my "mental model" of contexts and discuss context
behavior of recursive function calls within the context of my mental model,
as I understand it.
My understanding is that the two things that are bound in a context are a
word and a value. The relationship between them is loosely referred to as a
"binding". A "context" is simply the total of all currently valid or
effective bindings. The "Currently Active Context" is the complete list of
all word-value pairs that answer the two questions:
1. When I evaluate the following statement, which words are currently bound
to values?
2. When I evaluate the following statement, what values are the currently
bound words currently associated with?
You can think of a context as a table consisting of two columns, a word
column and a value column.
Given the assignments:
>> a: 1
>> b: 2
>> c: func [x y] [+ x y]
The Currently Active Context Table would include the following new bindings:
word | value
. | .
. | .
. | .
a | 1
b | 2
c | func [x y] [+ x y]
There exists a Context Table that is always effective, which is therefore
called the "Global Context Table". At times, there may be additional
context tables effective, "Private Context Tables". The bindings defined in
"Private Context Tables" override the bindings defined in the "Global
Context Table".
>From the point of a statement that is being evaluated, there exists a
hierarchy of "Effective Context Tables". The lowest Context Table in this
hierarchy will first be used to search for the value of a word, and if the
word is not found in this context table, the search will continue in
context tables at higher levels in the context table hierarchy. The lowest
table in the context table hierarchy is the context table that was last
created, "last" in terms of previous statements that were evaluated.
When REBOL identifies a word in its input stream, it replaces that word by
the value that word is bound to (and in some instances evaluates that
value, i.e. functions, actions, primitives). In terms of our "Context
Table", when REBOL evaluates a word, it looks up the value of the word in
the "Currently Active Context Table", and replaces the word it is
evaluating by the value it finds in the table. In some instances REBOL then
continues to evaluate the value itself, for instance when that value is a
function.
When REBOL encounters the following input,
>> c a b
then, given the above context table for c a and b, for instance, it would
look up the word c in the word column of the the table and discover the
function func [x y] [+ x y]. Because it is a function, REBOL retrieves AND
evaluates the function. At the beginning of this evaluation REBOL
determines that two arguments are needed for the function. Therefore REBOL
considers the next two tokens in the input stream as the function's arguments.
Now REBOL looks up the word 'a in the word column of the table and finds
the value 1. In the following piece of pseudo code I express the fact that
the first two words, a and b, have been dereferenced (i.e. replaced by
their values), and that the second value will be used as the function's
first argument, by using the notation x: 1 in the argument block of the
function:
>> func [x: 1 y] [+ x y] b
^^^
Now REBOL still needs a second argument for the function, a value that will
be bound to y. REBOL looks up the word b in the "Context Table" and passes
its value to the function:
>> func [x: 1 y: 2] [+ x y]
^^^^^^^^^
Multiple "Context Tables"
At the time REBOL enters the function a new "Context Table" becomes
effective. This context table, at this point in time, would like this:
word | value
x | 1
y | 2
The Global Context is effective when REBOL normally evaluates scripts. In
addition there are private contexts. When we enter the function, two
context tables are effective, the function's private context table, in
which the words x and y are bound to their respective values, and the
global context table. (There may be more context tables effective, if the
function is defined in a use evaluation block, for instance, or in a
function, or in an object.)
REBOL first looks up words in the functions private context table, and if
it cannot find a word there, then REBOL looks up the same word in context
tables on a higher level (such as a parent function, or an object) until it
reaches the global context table.
Now REBOL evaluates the function with the two arguments, x and y set to 1
and 2 respectively.
When REBOL encounters the word '+ in the function's body, [+ x y], REBOL
first looks '+ up in the function's private context table. It does not find
'+ there. Therefore REBOL looks up '+ in the global context table. It does
find '+ there and now looks for two more tokens in the input stream, to
satisfy +'s required two arguments, the values to be added. REBOL ecounters
'x, looks it up in the function's private context table, finds it there,
retrieves its values, 1, and passes that value to '+. It does the same
thing with 'y.
Now REBOL evaluates the + function (actually is datatype is op!), and
returns the result of this evaluation, hopefully something quite close to 3
;-).
Recursion And Context Tables: The Context Table Stack
=====================================================
Based on the mental model of context tables, how does recursion work? To
answer this question, first let us determine, when a private context table
is created for a function. Is it at the time the function is defined, or is
the table created when the previously defined function is evaluated?
To determine that we will first define a global word x:
>> x: "global word x."
== "global word x."
Now we define a function that uses a local word x as its argument:
>> f: func [x] [x]
We can look up the value of the argument 'x, by accessing the second block
of the function:
>> first second :f
== x
Now let us retrieve the value of this x. We have not yet evaluated the
function, we have only created it.
If REBOL created a private context table for the function at the time the
function was defined, then it will not be able to retrieve a value for x,
because the function was not evaluated yet, and no value was assigned to x
as yet.
Or there does not exist a private context table for the function yet, and
REBOL will look up x in the global context table, find it there (remember,
we just defined a global x), and return the value 1:
>> get first second :f
** Script Error: x has no value.
** Where: get first second :f
Aha, globally x is defined at this point in time. Nevertheless, REBOL
complains that there is no value associated with 'x. Therefore REBOL must
have looked up 'x in the private context table, and, because the function
was not evaluated yet, though it did find 'x, it did not find a value
associated with 'x, and accordingly returned an error. The private context
table for 'f at this time looks as follows:
word | value
x | unassigned
Now we evaluate the function with the value 222:
>> f 222
== 222
>> get first second :f
== 222
Aha, this get first second :f succeeded and returne the value we expected,
namely 222. The private context table for f now looks like this:
word | value
x | 222
The following function determines all words that are defined local to a
function and creates a private context table for that function:
show-context-table: func ['func-name /local value] [
print "Context Table"
print "============="
print "Word | Value"
foreach private-word third get func-name [
prin mold private-word
for i 1 (8 - length? form :private-word) 1 [
prin " "
]
either error? try [
value: get (bind :private-word first second get func-name)
] [
print "| unassigned"
][
print ["|" :value]
]
]
]
Note: this version show-context-table is specific to our example. It
assumes that there are no words contained in blocks (if, either, loop,
foreach ...
We implement f again (to create a virgin copy in which x is not yet
defined), and run show-context-table agains this version of f:
>> f: func [x] [x]
>> show-context-table f
Context Table
=============
Word | Value
x | unassigned
Now we evaluate f, this time with the value 613
>> show-context-table f
Context Table
=============
Word | Value
x | 613
Now we get the expected resulting private context table for 'f.
The question we are driving at is, how do context tables behave in
recursive situations. We will use a global word, recursion-level, to keep
track of recursions.
The highest recursion-level (i.e. when the function is not calling itself
recursively) will be 0. The recursion level will be incremented, when the
function calls itself recursively. We add this information to
show-context-table's output (the final version of show-context-table is
documented at the end of this message):
>> f: func [x] [x]
>> show-context-table f
Context Table of f at recursion level 0
=====================================================
Word | Value
x | unassigned
>> f 613
== 613
>> show-context-table f
Context Table of f at recursion level 0
=====================================================
Word | Value
x | 613
Now let us add instructions to f that will
a) call show-context-table during each call to f
b) increment the recursion-level
c) if x > 0 , call f with x - 1
f: func [x] [
x
show-context-table f
recursion-level: recursion-level + 1
if x > 0 [ f (x - 1)]
]
Note that we include 'x as the first statement in the function, so that we
have a local word in that position to bind to.
We now call f with a value of 2 and monitor the context table during
recursions:
>> f 2
Context Table of f at recursion level 0
=====================================================
Word | Value
x | 2
Context Table of f at recursion level 1
=====================================================
Word | Value
x | 1
Context Table of f at recursion level 2
=====================================================
Word | Value
x | 0
Everything works as we expected it to. The context table the function f
reflects the value of x as we decrement x. The final value for x is 0.
Now that the recursive function calls are completed, let us see what f's
private context table looks like. Recall that the last argument f was
called with recursively was 0 (as documented above).
>> show-context-table f
Context Table of f at recursion level 3
=====================================================
Word | Value
x | 2
Ooh! Aah! f's private context-table displays the local word 'x as being
bound to the value 2, not 0, which was the last value x was set to by the
final recursive call.
How? Why? By virtue of what magic was x set back to 2?
We modify f, such that upon returning from a recursive call f
- displays the private context table, and
- decrements the recursion-level
- notifies us that is now returning from a recursion, if recursion-level > 0
- tells us that f is returning, if the top level of f was reached:
f: func [x] [
x
show-context-table f
recursion-level: recursion-level + 1
if x > 0 [ f (x - 1)]
show-context-table f
recursion-level: recursion-level - 1
either recursion-level > 0 [
print "returning from recursion"
][
print "returning from f"
]
]
Here is the resulting printout:
>> f 2
Context Table of f at recursion level 0
=====================================================
Word | Value
x | 2
Context Table of f at recursion level 1
=====================================================
Word | Value
x | 1
Context Table of f at recursion level 2
=====================================================
Word | Value
x | 0
Context Table of f at recursion level 3
=====================================================
Word | Value
x | 0
returning from recursion
Context Table of f at recursion level 2
=====================================================
Word | Value
x | 1
returning from recursion
Context Table of f at recursion level 1
=====================================================
Word | Value
x | 2
returning from f
We see that upon returning from each recursive call f's context table is
re-populated with the value that x was bound to at the recursion level we
have returned to.
What we should note here is that apparently REBOL remembered all three
context tables for the function f, even while it was in the third
(recursive) function call to f. In other words the f function was
temporarily associated with three context tables. At the deepest
recursion-level the two context tables it acquired during the previous
calls to f were remembered.
It is as though REBOL uses a stack to keep track of intermittent context
tables for a function.
Are these indeed different context tables, or are they one context table,
whose values are being changed?
We can explore this question by modifying the function f. First we modify
show-context-table by skipping occurences of the word /local (see the
extended show-context-table function at the end of this message), then we
add a local word 'a to the f's declaration. We first display the
context-table and then we assign a value to 'a.
Upon returning we once again display the private context table:
f: func [x /local a] [
x
show-context-table f
a: recursion-level
recursion-level: recursion-level + 1
if x > 0 [ f (x - 1)]
show-context-table f
recursion-level: recursion-level - 1
either recursion-level > 0 [
print "returning from recursion"
][
print "returning from f"
]
]
Our expectations:
1. If REBOL is re-using the old private context table for this function,
then after 'a has been set to a value during the higher recursive
evaluation of f (i.e. f before it called itself recursively), then it
should find the old value of 'a in its private context table, before it has
modified that value.
2. If, however, REBOL is using a completely new private context table at
each recursion, then 'a should be assigned the value none (which is what
local words are initially set to at the time a function is evaluated,
before a value assignment statement is evaluated within the function):
Here is the result of running this new version of f:
>> f 2
Context Table of f at recursion level 1
=====================================================
Word | Value
x | 2
a | none
Context Table of f at recursion level 2
=====================================================
Word | Value
x | 1
a | none
Context Table of f at recursion level 3
=====================================================
Word | Value
x | 0
a | none
returning from recursion
Context Table of f at recursion level 3
=====================================================
Word | Value
x | 0
a | 3
returning from recursion
Context Table of f at recursion level 2
=====================================================
Word | Value
x | 1
a | 2
returning from recursion
Context Table of f at recursion level 1
=====================================================
Word | Value
x | 2
a | 1
== 0
At the level 1, before f called itself recursively, we displayed the
context table before we set the local word 'a to a value. Accordingly, the
private context table during that evaluation, displays 'a as being
associated with none, the default value for local words.
Then we 'a associated with the current-recursion level, and subsequently
called f recursively. If f continued to use its previous context table,
then, while x was set to a lower level by virtue of the function call f (x
- 1), a was not modified yet, so 'a should continue to be associated with
1, the value of recursion-level, during the privous call.
Accordingly upon entering recursion level 3, 'a should have been set to 2,
the result of the assignment of 'a during the higher previous recursion.
That is not the case. Each time we enter a deeper recursion, 'a is assigned
none, and when we step out of recursions, 'a shows up in the recursion
table associated with the value it was assigned during its current
recursion, before evaluating f a a deeper recursion level.
Conclusion:
===========
1. Each function is associated with a stack of private context tables.
During recursive function calls, the private context table of a function is
pushed on the stack, and a new context table for that function is created.
When a function returns from a deeper recursion level, its private context
table is released, and then replaced by the top-most private context table
for this function, which is popped off the stack.
2. Once the stack is emptied, the function remains associated with the last
private context table that was associated with that function.
I think, Ladislav, that this model explains what happened, when your
function recfunc repeatedly appended x to a block blk, and used probeblk to
display the reduced block blk.
1. When recfunc was originally called with 3 as its argument, x was
associated with 3 in the function's context, and the reduced block blk [x]
evaluated to [3], the value that x was bound to at the time.
Recfunc's private contex table at recursion level 0:
word | value
x | 3
recfunc's private context table stack:
none
2. When recfunc recursively called itself, it's current private contex
table was pushed on the context table stack for this function
contex table stack:
===================
[x 3]
none
the same x was appended to blk, now blk consists of two instance of x [x
x], both instances being the x bound to a value in the private context
table of recfunc.
Because this instance of recfunc was called with 2 as its argument, x in
the context of recfunc is now bound to the value 2:
Recfunc's private context table at recursion level 1:
word | value
x | 2
Reducing blk consisted of looking up x twice in the recfunc's context, and
that context consisted of the binding recorded for 'x in recfunc's current
private context table, which was the context table generated based on the
assigned of x to the value 2 (see context table above).
Therefore the reduced block blk returned [2 2], twice the value that x is
bound to in the currently active private context table of recfunc.
And so on for deeper recursion levels.
Upon returning from the recurdsions, recfunc's private context tables are
popped from the stack, until the top-level private context table becomes
the currently effective context table:
Before returning to the top-level private context table:
recfunc's context table stack:
===================
[x 3]
none
recfunc's currently effective private context table:
=========================================================
word | value
x | 2
Now the final context table is popped of the stack:
recfunc's context table stack:
===================
none
recfunc's currently effective private context table:
=========================================================
word | value
x | 3
When then probeblk'd recfunc after the recursions had ended, you were
probing the block [x x x] in which all instances of x are bound in the
context table of recfunc, which now, once again, associates x with the
value that was originally passed to recfunc, namely 3. Reducing this block
therefore, now, returns [3 3 3].
Terminology
===========
I used the term "Static Context" to refer to the context table that is
effective at the time the context stack is empty.
I used the term "Dynamic Context" to refer to the hierarchy of context
tables that are effective during the time at which the function is being
evaluated, and the stack is being used to store context tables that
resulted from higher level recursive calls to a function.
The Complete show-context-table and f functions that I used here:
=================================================================
REBOL []
recursion-level: 0
show-context-table: func ['func-name /local value] [
print ["Context Table of" :func-name "at recursion level" recursion-level]
print "====================================================="
print "Word | Value"
foreach private-word third get func-name [
if not private-word = 'local [
prin mold private-word
for i 1 (8 - length? form :private-word) 1 [
prin " "
]
either error? try [
value: get (bind :private-word first second get func-name)
] [
print "| unassigned"
][
print ["|" :value]
]
]
]
]
f: func [x /local a] [
x
show-context-table f
a: recursion-level
recursion-level: recursion-level + 1
if x > 0 [ f (x - 1)]
show-context-table f
recursion-level: recursion-level - 1
either recursion-level > 0 [
print "returning from recursion"
][
print "returning from f"
]
]
At 03:47 AM 7/20/00 +0200, you wrote:
>Hi Elan,
>
>You wrote:
>"During recursive calls, REBOL is using a dynamic binding for 'x,
>which means that each instance of recfunc, called from within
>recfunc recursively, has its own context in which 'x is bound to
>the value that was passed to the recfunc instance."
>
>I would like to divide the paragraph into two parts:
>
>"During recursive calls, REBOL is using a dynamic binding for 'x."
>
>That looks allright, but the next part makes a problem:
>
>"...each instance of recfunc, called from within recfunc
>recursively, has its own context in which 'x is bound to the value
>that was passed to the recfunc instance"
>
>This is true for non-Rebol notion of "contexts". Once we
>compare this to Rebol Contexts, we see:
>
>blk: copy []
>probeblk: func [] [
> prin mold blk
> prin ": "
> print mold reduce blk
>]
>recfun: func [x] [
> append blk 'x
> either x <= 1 [
> probeblk
> probe same? first blk second blk
> ] [
> recfun x - 1
> ]
>]
>recfun 2
>
>The results:
>
>>> recfun 2
>[x x]: [1 1]
>true
>== true
>
>While:
>
>blk: copy []
>probeblk: func [] [
> prin mold blk
> prin ": "
> print mold reduce blk
>]
>fun1: func [x] [
> append blk 'x
> either x <= 1 [
> probeblk
> probe same? first blk second blk
> ] [
> fun2: func [x] [
> append blk 'x
> probeblk
> probe same? first blk second blk
> ]
> fun2 x - 1
> ]
>]
>fun1 2
>
>And the results:
>
>>> fun1 2
>[x x]: [2 1]
>false
>== false
>
>>From that is clear, that in the case of Recfun, there is only one
>'x. Words 'x inserted to Blk as the first and the second element
>are in fact just one word 'x that was bound to just one Rebol
>Context - the (dynamic) Rebol Context of Recfun, while two Rebol
>Contexts in the
>case of Fun1 and Fun2 mean two words 'x in Blk, each bound to a
>different Rebol Context (Fun1's context's 'x and Fun2's context's
>'x).
>
>Similarly the next statement's first part:
>"Once the recursion expires the context of 'x is again bound to
>the value it last had before recfunc called itself recursively..."
>
>Is true, if we consider a different kind of binding - "Value
>Binding", because "Context Binding" remains the same, the only
>thing changing between Recfun calls is the value of 'x.
>
>While the second part:
>"Once the recursion expires (...), it ('x) is bound in the static
>context of the top-level instance of the recfunc function."
>
>Can not be interpreted as Rebol Context change, because Rebol
>Context remains the same - namely that of Recfun and no Rebol
>Context change is necessary.
>
>As you pointed out, there is a conflict of two things:
>"Static Context Binding" vs. "Dynamic Value Binding". As a
>consequence, Use may misbehave during recursive calls.
>
>Regards
> Ladislav
>
>> Hi Ladislav, Brett,
>>
>> Ladislav wrote:
>>
>> >> blk: copy []
>> >> probeblk: func [] [
>> >> prin mold blk
>> >> prin ": "
>> >> print mold reduce blk
>> >> ]
>> >> recfun: func [x] [
>> >> append blk 'x
>> >> either x <= 1 [
>> >> probeblk
>> >> ] [
>> >> recfun x - 1
>> >> ]
>> >> ]
>> >> recfun 3
>> >> probeblk
>>
>> To which Brett replied
>>
>> >I would have expected [3 2 1]
>> >not [1 1 1] nor [3 3 3].
>>
>> What you are demonstrating, Ladislav, is IMHO a conflict that
>results from
>> the fact that REBOL is using two different binding mechanisms.
>>
>> During recursive calls, REBOL is using a dynamic binding for 'x,
>which
>> means that each instance of recfunc, called from within recfunc
>> recursively, has its own context in which 'x is bound to the
>value that was
>> passed to the recfunc instance.
>>
>> Once the recursion expires the context of 'x is again bound to
>the value it
>> last had before recfunc called itself recursively, it is bound
>in the
>> static context of the top-level instance of the recfunc
>function.
>>
>> So 'x exists in multiple contexts: the static context of the
>function
>> recfunc, and the temporary dynamic contexts, that are created
>for each
>> recfunc instance, when recfunc calls itself recursively.
>>
>> When you reduce blk from within a recursively called instance of
>recfunc,
>> 'x is bound in the temporary dynamic context of the recursively
>called
>> function's instance. Once recfunc's loop expires and there are
>no more
>> recursively called instances of recfunc effective, then 'x is
>once again
>> bound in the context of the top-level recfunc function, its
>static context,
>> and the reduced block evaluates to the value that 'x is bound to
>in that
>> context.
>>
>>
>> At 11:44 PM 7/19/00 +1000, you wrote:
>> >I would have expected [3 2 1]
>> >not [1 1 1] nor [3 3 3].
>> >
>> >But I find it difficult to answer what I want, because the
>function argument
>> >x seems like it's in a bit of a no-mans land (I'm thinking of
>:x )
>> >
>> >My brain hurts now. :)
>> >Brett.
>> >
>> >----- Original Message -----
>> >From: <[EMAIL PROTECTED]>
>> >To: <[EMAIL PROTECTED]>
>> >Sent: Wednesday, July 19, 2000 5:03 PM
>> >Subject: [REBOL] Bug in 'use? Re:(3)
>> >
>> >
>> >> Hi,
>> >>
>> >> > Hi Ladislav, 15-Jul-2000 you wrote:
>> >> >
>> >> > >you are right, the problem is caused by a context
>> >> manipulation -
>> >> > >Use unsets your Middle every time it gets executed. My
>> >> suggestion
>> >> > >is to not use Use in recursive functions, while this
>problem
>> >> > >doesn't get corrected.
>> >> >
>> >> > Judging from the nature of recursiveness, that's a little
>hard,
>> >> isn't it? ;-)
>> >> >
>> >> > Do you know if this problem has already been reported to
>> >> feedback?
>> >> >
>> >> > Kind regards,
>> >> > --
>> >> > Ole Friis <[EMAIL PROTECTED]>
>> >> >
>> >> > Amiga is a trademark of Amiga Inc.
>> >> >
>> >>
>> >> You should probably report it to feedback. BTW, did you
>succeed to
>> >> sort the permutations correctly?
>> >>
>> >> One more question for everybody. What do you want to see
>after
>> >> executing:
>> >>
>> >> blk: copy []
>> >> probeblk: func [] [
>> >> prin mold blk
>> >> prin ": "
>> >> print mold reduce blk
>> >> ]
>> >> recfun: func [x] [
>> >> append blk 'x
>> >> either x <= 1 [
>> >> probeblk
>> >> ] [
>> >> recfun x - 1
>> >> ]
>> >> ]
>> >> recfun 3
>> >> probeblk
>> >>
>> >> Regards
>> >> Ladislav
>> >>
>> >
>> >
>> >
>>
>> ;- Elan [ : - ) ]
>
>
>
>
>
>
>
>
>
>
;- Elan [ : - ) ]
