Dynamic scoping

Benutzeravatar
Chase
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 5. Apr 2008 11:14

Dynamic scoping

Beitrag von Chase »

Hello. I have a question about static/dynamic scoping.

Code: Alles auswählen

{with y 1
	{with x {+ y y} 
		{with y 4
			x}}}
With static scoping the result is obviously 2.
With dynamic scoping, the result could be 8. (x is bound to {+ y y}). But isn't this dependant on whether we use lazy or eager evalutation?

I am also not sure about the terms: Is 'lazy evalutation' and 'lazy substitution' the same?

Thanks.

vaidas
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 4. Feb 2010 17:12

Re: Dynamic scoping

Beitrag von vaidas »

With static scoping the result is obviously 2.
With dynamic scoping, the result could be 8. (x is bound to {+ y y}).
Yes
But isn't this dependant on whether we use lazy or eager evalutation?
I have not heard about lazy evaluation in combination with dynamic scoping. In principle in case of lazy evaluation we also have expression closures, which means that we could have something like dynamic scoping for lazy evaluation, which would evaluate the expression with the current (dynamic) environment instead of the environment stored in the expression closure. But I have never heard about something like that. So if I say dynamic scoping, I assume eager evaluation.
I am also not sure about the terms: Is 'lazy evalutation' and 'lazy substitution' the same?
Semantically it is the same. It is just that we introducted lazy substitution in the context of interpreters based on immediate subtitution, while lazy evaluation was presented with deferred substitution, but lazy substitution can also be seen as a form of lazy evaluation.

Basically you should be able distinguish between immediate substitution and deferred substitution as different implementation strategies of substitution.

Then you should distinguish between lazy and eager evaluation regimes, which can be applied both in combination with immediate and deferred substitution. In a language with functions lazy evaluation corresponds to call-by-name semantics, and eager evaluation corresponds to call-by-value semantics.

In case of lazy evaluation based on deferred substitution we also distinguish between implementations with or without caching. Call-by-need refers to lazy evaluation with caching.

Vaidas

citta
Mausschubser
Mausschubser
Beiträge: 96
Registriert: 7. Nov 2006 21:52

Re: Dynamic scoping

Beitrag von citta »

There are two concepts involved here that got mixed together:
Explicit substitution vs deferred substitution
and
Eager evaluation vs lazy evaluation.

The first one is about when substitutions are made. In explicit substitutions, we have an (explicit) subst function whereas in deferred substitution we have a substitution repository and substitution takes only place if needed. Explicit substitution is slow, as the rest of the program (abstract syntax nodes) must be traversed by the substitution algorithm. The problem with dynamic scoping occurs only when using deferred substitution.

The latter is about when function arguments or with's named-exprs are evaluated (interpreted).

To get back to your example: Yes, with dynamic scoping and eager evaluation the result is 2. This might seem surprising at first, but if you think about the named-expr {+ y y} as a function argument, it is not. After all, with eager evaluation, the function argument is evaluated before the function (resp. with's) body and is thus unaffected by all the magic that happens in the body. Dynamic scoping with eager evaluation does not change interpration of function arguments, only identifiers that occur in the function body are possible affected. There is no difference between static scoping and dynamic scoping if your program does not contain any function applications. (Everything deducted from my understanding of interpreters, no guarantee if everything I said is correct.)

I don't know if there is a language with dynamic scoping and lazy evaluation but the mere thought of it gives me the shivers.

Edit:
@Vaidas: Sure that with dynamic scoping this is 8? The named-expr's environment is unaffected by anything that happens in bound-boy:

Code: Alles auswählen

From PLAI 5.1:

[with (bound-id named-expr bound-body)
(interp bound-body
fun-defs
(aSub bound-id
(interp named-expr
fun-defs
ds)
ds))]

Benutzeravatar
Chase
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 5. Apr 2008 11:14

Re: Dynamic scoping

Beitrag von Chase »

Thank you.
To clarify: If the expression would be evaluated with dynamic scoping and lazy evaluation, the result is in fact 8.
But commonly, eager evaluation is used when implementing dynamic scoping and the result is 2.

Antworten

Zurück zu „Archiv“