static vs. dynamic scoping

static vs. dynamic scoping

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2425 bytes --]

On the Austin Group mailing list, David Korn (of ksh93 fame)
complained[1] that bash's 'local' uses dynamic scoping, but that ksh's
'typeset' uses static scoping, and argued that static scoping is saner
since it matches the behavior of declarative languages like C and Java
(dynamic scoping mainly matters in functional languages like lisp):

[1]
https://www.opengroup.org/sophocles/show_mail.tpl?CALLER=show_archive.tpl&source=L&listname=austin-group-l&id=14951

I'm trying to standardize the notion of local variables for the next
revision of POSIX, but before I can do so, I need some feedback on two
general aspects:

1. Implementation aspect:
  How hard would it be to add static scoping to dash?
  Is it something that should be added in addition to dynamic scoping,
via the use of an option to select the non-default mode (for example,
'local -d' to force dynamic, 'local -s' to force static, and 'local' to
go with default scoping)?
  Or should dash switch entirely to static scoping (my gut feel is that
static scoping may be more efficient to implement, which fits in line
with dash's desire to be as lean as possible)?

2. User aspect:
  Is anyone aware of a script that intentionally uses the full power of
dynamic scoping available through 'local' which would break if scoping
switched to static?

Here's a sample shell script that illustrates the difference between the
two scoping methods (note that ksh only provides nested scoping via its
typeset builtin, and only when using the function reserved word).

$ ksh -c 'function f1 { typeset a=local; f2; echo $a; };
  function f2 { echo $a; a=changed; };
  a=global; f1; echo $a'
global
local
changed

$ dash -c 'f1 () { typeset a=local; f2; echo $a; };
  f2 () { echo $a; a=changed; };
  a=global; f1; echo $a'
local
changed
global

In static scoping, function f2 does not shadow a declaration of a, so
references to $a within f2 refer to the global variable.  The local
variable a of f1 can only be accessed within f1; the behavior of f2 is
the same no matter how it was reached.

In dynamic scoping, function f2 looks up its call stack for the closest
enclosing scope of a variable named a, and finds the local one declared
in f1.  Therefore, the behavior of f2 depends on how f2 is called.

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: static vs. dynamic scoping

[ольга крыжановская]

Eric Blake wrote:
> Or should dash switch entirely to static scoping (my gut feel is that
> static scoping may be more efficient to implement, which fits in line
> with dash's desire to be as lean as possible)?

static scoping is much more efficient. Think about accessing a global
variable in a deep function call stack, e.g. 20 functions deep. With
dynamic scoping you have to look up the list of local variables for
each function *first* before looking at the global variables. In my
example this means 20 look ups. Each further function adds another
look up.
For static scoping you just look at the local variables of the
*current* function and then look up the global ones. This is faster
and much more efficient.

Olga
-- 
      ,   _                                    _   ,
     { \/`o;====-    Olga Kryzhanovska   -====;o`\/ }
.----'-/`-/     olga.kryzhanovska@gmail.com   \-`\-'----.
 `'-..-| /       http://twitter.com/fleyta     \ |-..-'`
      /\/\     Solaris/BSD//C/C++ programmer   /\/\
      `--`                                      `--`

Re: static vs. dynamic scoping

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2321 bytes --]

[redirecting back to the list, so others can benefit]

On 11/10/2010 02:16 AM, Marc Herbert wrote:
> Le 09/11/2010 21:52, Eric Blake a écrit :
>> I'm trying to standardize the notion of local variables for the next
>> revision of POSIX, but before I can do so, I need some feedback on two
>> general aspects:
>> [...]
>> Here's a sample shell script that illustrates the difference between the
>> two scoping methods.
> 
> Hi Eric,
> 
>   I found your sample script quite confusing. To make your point, does
> this script really need to:
> - use unquoted language keywords as string values?

No; I could have used other strings.

> - use deprecated "typeset" instead of declare?

Yes - the current Austin Group thoughts are to standardize 'typeset' and
NOT 'local', since 'typeset' can be used with arguments outside of
functions, and more existing shells provide 'typeset' than 'local' (dash
being the odd one out) or 'declare'.  Shells can continue to provide
'local' as a synonym for the most basic use of typeset.

> - use the not (or less?) standard "function" keyword?

Yes - ksh93 ONLY supports function-local scoping when using the function
keyword, rather than when using POSIX functions (although David Korn
agreed that if POSIX standardizes function-local scoping, he'd make the
next build of ksh support it in POSIX functions).

So, here's the example again, with those points addressed:

# Demonstrate ksh local scoping is static - requires ksh's 'function'

$ ksh -c 'function f1 { typeset a=temp; f2; echo "in f1: $a"; };
function f2 { echo "in f2: $a"; a=changed; }; a=global; f1; echo "top
level: $a"'
in f2: global
in f1: temp
top level: changed

# Demonstrate that with POSIX functions, ksh has global scoping

$ ksh -c 'f1 () { typeset a=temp; f2; echo "in f1: $a"; }; f2 () { echo
"in f2: $a"; a=changed; }; a=global; f1; echo "top level: $a"'in f2: temp
in f1: changed
top level: changed

# Demonstrate that dash local scoping is currently dynamic

$ dash -c 'f1 () { local a=temp; f2; echo "in f1: $a"; }; f2 () { echo
"in f2: $a"; a=changed; }; a=global; f1; echo "top level: $a"'
in f2: temp
in f1: changed
top level: global

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]

Re: static vs. dynamic scoping

[Jilles Tjoelker]

On Wed, Nov 10, 2010 at 03:15:59PM +0100, ольга крыжановская wrote:
> Eric Blake wrote:
> > Or should dash switch entirely to static scoping (my gut feel is that
> > static scoping may be more efficient to implement, which fits in line
> > with dash's desire to be as lean as possible)?

> static scoping is much more efficient. Think about accessing a global
> variable in a deep function call stack, e.g. 20 functions deep. With
> dynamic scoping you have to look up the list of local variables for
> each function *first* before looking at the global variables. In my
> example this means 20 look ups. Each further function adds another
> look up.
> For static scoping you just look at the local variables of the
> *current* function and then look up the global ones. This is faster
> and much more efficient.

That's not how dash implements it, though. The local builtin saves the
value and attributes of the variable and they are restored upon return.
There is just one table of variables to search (two in older versions
and other ash versions, the additional one storing variable assignments
for regular builtins like IFS= read x; these were converted to the local
mechanism recently).

The real efficiency benefit of static scoping comes when disallowing
access to locals when the name is not known at compile time: at run
time, the names of the locals are not necessary.

-- 
Jilles Tjoelker

Re: static vs. dynamic scoping

[Harald van Dijk]

On 09/11/10 23:02, Eric Blake wrote:
> 2. User aspect:
>    Is anyone aware of a script that intentionally uses the full power of
> dynamic scoping available through 'local' which would break if scoping
> switched to static?

FWIW, some scripts use "local IFS" to reset IFS to a sane value, and 
have the shell take care of restoring it afterwards. This works with 
ksh's typeset, but because of the static scoping only so long as no 
other shell functions get called, or those other shell functions also 
take the effort to handle IFS correctly. In the scripts I have been able 
to find, other shell functions do get called, but they themselves set 
IFS too. Still, it may be worth keeping in mind, if only to serve as one 
of the few examples of when dynamic scoping would have been slightly 
more useful.

Re: static vs. dynamic scoping

[ольга крыжановская]

How is dynamic scoping in this case 'more useful'? Imagine function a
written by author A and function b written by author B, both loaded
into an application and each of them working independently, bound
together by an api spec.
Now function a uses typeset IFS="X" to set the field separator to "X"
via a local variable IFS. If function b now uses "read foo1 foo2 foo3"
to read a line of a database the concept of dynamic scoping *BITES*.
Suddenly function b no longer works as author B intended it. Lots of
surprise, lots of raised eyebrows by an unwanted interaction.
Static scoping is in this case much *SAFER* because IFS is reset in
function b to the (global) default.

The issue isn't new but the issues with dynamic scoping are one major
factor why there are so few shell function libraries: It is just hard
to write such a library without running afoul dynamic scoping.

Olga

On Sun, Nov 14, 2010 at 12:22 AM, Harald van Dijk <harald@gigawatt.nl> wrote:
> On 09/11/10 23:02, Eric Blake wrote:
>>
>> 2. User aspect:
>>   Is anyone aware of a script that intentionally uses the full power of
>> dynamic scoping available through 'local' which would break if scoping
>> switched to static?
>
> FWIW, some scripts use "local IFS" to reset IFS to a sane value, and have
> the shell take care of restoring it afterwards. This works with ksh's
> typeset, but because of the static scoping only so long as no other shell
> functions get called, or those other shell functions also take the effort to
> handle IFS correctly. In the scripts I have been able to find, other shell
> functions do get called, but they themselves set IFS too. Still, it may be
> worth keeping in mind, if only to serve as one of the few examples of when
> dynamic scoping would have been slightly more useful.
> --
> To unsubscribe from this list: send the line "unsubscribe dash" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>



-- 
      ,   _                                    _   ,
     { \/`o;====-    Olga Kryzhanovska   -====;o`\/ }
.----'-/`-/     olga.kryzhanovska@gmail.com   \-`\-'----.
 `'-..-| /       http://twitter.com/fleyta     \ |-..-'`
      /\/\     Solaris/BSD//C/C++ programmer   /\/\
      `--`                                      `--`

Re: static vs. dynamic scoping

[Harald van Dijk]

On 14/11/10 00:54, ольга крыжановская wrote:
> Now function a uses typeset IFS="X" to set the field separator to "X"
> via a local variable IFS. If function b now uses "read foo1 foo2 foo3"
> to read a line of a database the concept of dynamic scoping *BITES*.

The way I had seen "local IFS" used is to sanitise IFS -- to reset IFS 
to the default value, when IFS was set to, for example, : before the 
function was called, and the function wants to split on whitespace. In 
that case, you don't want b to get IFS=:. Both forms are used, and in 
your form, I agree, static scoping is more useful.

Re: static vs. dynamic scoping

[Cedric Blancher]

On 10 November 2010 16:13, Eric Blake <eblake@redhat.com> wrote:
> [redirecting back to the list, so others can benefit]
>
> On 11/10/2010 02:16 AM, Marc Herbert wrote:
>> Le 09/11/2010 21:52, Eric Blake a écrit :
>>> I'm trying to standardize the notion of local variables for the next
>>> revision of POSIX, but before I can do so, I need some feedback on two
>>> general aspects:
>>> [...]
>>> Here's a sample shell script that illustrates the difference between the
>>> two scoping methods.
>>
>> Hi Eric,
>>
>>   I found your sample script quite confusing. To make your point, does
>> this script really need to:
>> - use unquoted language keywords as string values?
>
> No; I could have used other strings.
>
>> - use deprecated "typeset" instead of declare?
>
> Yes - the current Austin Group thoughts are to standardize 'typeset' and
> NOT 'local', since 'typeset' can be used with arguments outside of
> functions, and more existing shells provide 'typeset' than 'local' (dash
> being the odd one out) or 'declare'.  Shells can continue to provide
> 'local' as a synonym for the most basic use of typeset.
>
>> - use the not (or less?) standard "function" keyword?
>
> Yes - ksh93 ONLY supports function-local scoping when using the function
> keyword, rather than when using POSIX functions (although David Korn
> agreed that if POSIX standardizes function-local scoping, he'd make the
> next build of ksh support it in POSIX functions).
>
> So, here's the example again, with those points addressed:
>
> # Demonstrate ksh local scoping is static - requires ksh's 'function'
>
> $ ksh -c 'function f1 { typeset a=temp; f2; echo "in f1: $a"; };
> function f2 { echo "in f2: $a"; a=changed; }; a=global; f1; echo "top
> level: $a"'
> in f2: global
> in f1: temp
> top level: changed
>
> # Demonstrate that with POSIX functions, ksh has global scoping
>
> $ ksh -c 'f1 () { typeset a=temp; f2; echo "in f1: $a"; }; f2 () { echo
> "in f2: $a"; a=changed; }; a=global; f1; echo "top level: $a"'in f2: temp
> in f1: changed
> top level: changed
>
> # Demonstrate that dash local scoping is currently dynamic
>
> $ dash -c 'f1 () { local a=temp; f2; echo "in f1: $a"; }; f2 () { echo
> "in f2: $a"; a=changed; }; a=global; f1; echo "top level: $a"'
> in f2: temp
> in f1: changed
> top level: global

Why is the debate static-vs-dynamic scoping coming up again? People
like Ken Thompson, who wrote the very first UNIX shell, Douglas
McIlroy, inventor of the UNIX pipelines and many others of the fathers
of UNIX have criticized the concept of dynamic scoping in ksh88
loudly, in USENIX meetings and elsewhere. Even David Korn admitted
that it was a grave design error and corrected it for the next major
version of the korn shell, which became ksh93.

With this background I doubt any proposal for dynamic scoping will
make it into the next POSIX standard. It's simply not considered a
sane design for a modern computer language anymore and bash's
emulation of ksh88's dynamic scoping can hardly be used as precedent
in Austin Group proposals after ksh88 itself was abandoned in 1992.

Ced
-- 
Cedric Blancher <cedric.blancher@googlemail.com>
Institute Pasteur

Re: static vs. dynamic scoping

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2140 bytes --]

On 11/15/2010 02:11 PM, Cedric Blancher wrote:
> 
> Why is the debate static-vs-dynamic scoping coming up again?

Because before 'typeset' can be standardized in POSIX, we have to get
consensus from all the shell implementers that they will agree to
implement static scoping.

For ksh, the question is moot - ksh93 already does static only.

For dash, the question is valid - the current dash implementation is
dynamic only, but given that switching to static only could probably be
made more efficient, and dash values efficiency, it's a reasonable goal.

For bash and zsh, which currently are dynamic only, the problem stems
that there are now a number of shell script libraries for these two
shells that have exploited dynamic scoping, and which would break if we
aren't careful to standardize something that can still allow dynamic
scoping as an extension.  In other words, this was a probe of the
various shell implementers to figure out how easily static scoping can
be added on after the fact to a dynamic scoping implementation, so that
the shell could conform to a future POSIX revision that mandates static
and permits dynamic as an extension.

> With this background I doubt any proposal for dynamic scoping will
> make it into the next POSIX standard.

There's no desire for dynamic scoping in POSIX; David Korn has already
made that point clear on the Austin Group mailing list.  Rather, there
is a desire for minimal effort for complying with a new POSIX
requirement of static scoping on shells that currently lack it, as well
as backwards compatibility for shells that wish to continue to provide
dynamic scoping as an extension to the standard.

My take of the Austin Group list discussion is that the next revision of
the standard is most likely to have consensus if it just mandates
'typeset' for static scoping, and leaves 'local' as an implementation
extension for dynamic scoping.  Please, chime in on the Austin Group
conversation if you have something useful to add.

-- 
Eric Blake   eblake@redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 619 bytes --]