begin quoting David Brown as of Fri, Feb 01, 2008 at 09:06:25AM -0800:
> On Thu, Jan 31, 2008 at 09:58:30PM -0800, [EMAIL PROTECTED] wrote:
[snip]
> >"properly tail recursive" (Is there such thing as improperly tail
> >recursive?)
>
> I'm not sure what improperly tail recursive would mean. It is a bit
> redundant to say properly tail recursive, but it emphasizes to the reader
> that there is something special about tail recursion in Scheme vs non-tail
> calls.
The problem arises from "tail recursion" being two things. One, it
describes the *source* -- the LAST thing in a function defintion is
a (recursive) call.
function foo( x ) {
code here
return foo( y );
}
The recursive call is at the tail end of the function.
Now, we *know* that nothing is going to happen between the return of the
recursive call and the return of the function... so we know we don't
need the stack-frame, and thus we can resuse it, saving space and time.
But that's an implementation detail, and depends on the compiler
(or interpreter).
So "tail recursion" is both a description of the structure of a
recursive call AND an assumption about the runtime behavior given
the described structure.
I would take "properly tail recursive" to be the latter meaning,
as that's the more constrained and useful sense.
> >"statically scoped" (Scope to me just means the parens in which a bound
> >symbol
> > is valid. What's with the 'static' part?)
>
> Statically scoped means that the variable binding can be determined at
> compile time. Dynamic scoping means the scoping is determine by the call
> flow at runtime. Few languages support dynamic scoping, although it is
> easy in common lisp, and possible in Scheme.
>
> Some schemes implement the (now withdrawn) srfi-15
> <http://srfi.schemers.org/srfi-15/srfi-15.html> for fluid-let.
>
> Probably best to explain by example.
>
> (define x 5)
>
> (define (show-x)
> (print x))
>
> Ordinary static binding:
>
> (let ((x 10))
> (show-x))
>
> will print 5. The static scoping rules, mean that the 'x' that is created
> by the let is different than the one that show-x is using.
>
> But:
>
> (fluid-let ((x 10)
> (show-x)
>
> will print 10. The easiest way to think of it is that the dynamic binding
> in the fluid-let saves off the old value of 'x' and puts 10 in while it's
> body is running.
Another description:
Lexically scoped means you can find the variable definition by tracing
the scope outward from use, while dynamic scope means that you find the
variable definition by tracing the call-stack back.
I don't find the scheme example very clear, personally, because I don't
see that it demonstrates as to what's happening if you're unclear on the
concept to begin with.
(So let me seek to further muddy the waters...)
In pascal-ish psuedocode:
def foo
var x
def bar
var x
begin
x := 5
qux()
print x
end
end
def baz
begin
qux()
print x
end
end
def qux
begin
x := x + 10
end
end
begin
x := 1
print x
bar
print x
baz
print x
end
end
For a lexically-scoped defintion, the output is
1
5
11
21
21
For a dynamically-scoped defintiion, the output is
1
15
1
11
11
(Pedants, please double-check my work...)
Basically, for lexical scoping, you put your finger on the line of code
that's being run, and when you see a variable, you look for the variable
definition in the current block, and if you don't find the variable, you
move your finger to the enclosing block (but never into an enclosed
block!) and repeat.
For dynamic scoping, you again start by looking in the enclosing block,
but if you don't find the variable definition, you look at the block
of that encloses the call to your function; you keep looking at the
block for each caller until you find the variable definition.
--
Dynamic or lexical, for both
will lead always to confusion.
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
