Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.

Does this mean we'll be allowed to forward reference nested functions?  If so, yay!

On Tue, Sep 13, 2011 at 6:04 PM, Walter Bright <walter at digitalmars.com>wrote:

> Don, just so you know, I've been thinking for a while about transitioning
> from doing the semantic pass in order to doing it completely "on demand". In
> other words, try to semantic a declaration. In the process, any declarations
> it depends on are semantic'd if not already, recursively.
> ______________________________**_________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/**mailman/listinfo/dmd-internals<http://lists.puremagic.com/mailman/listinfo/dmd-internals>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-internals/attachments/20110913/caa07a96/attachment.html>

No, sorry.

On 9/13/2011 3:18 PM, David Simcha wrote:
> Does this mean we'll be allowed to forward reference nested functions?  If so, yay!
>
> On Tue, Sep 13, 2011 at 6:04 PM, Walter Bright <walter at digitalmars.com <mailto:walter at digitalmars.com>> wrote:
>
>     Don, just so you know, I've been thinking for a while about transitioning
>     from doing the semantic pass in order to doing it completely "on demand".
>     In other words, try to semantic a declaration. In the process, any
>     declarations it depends on are semantic'd if not already, recursively.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-internals/attachments/20110913/d7bd58d2/attachment.html>

On Tue, 13 Sep 2011, Walter Bright wrote:

> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.

Does the compiler have a graph of dependencies at all?  Easy to walk without requiring pausing to do work at each node?  One of the things we talked about _ages_ ago that I've had kicking around in the back of my head ever sense was breaking the problem into two pieces.

Piece 1: A process that finds nodes in the graph that have no unfulfilled dependencies and adds those to a queue to be analyzed.

Piece 2: a thread pool of workers that pull those work items and analyzes them.

As elements finish #2, #1 produces more work due to satisfied dependencies.  Repeat until no more work can be done.

if the graph is fully analyzed, success, if not fail due to true circularness.

For the time being, the worker probably needs to not really be using threads due to the over abundant use of global state.  But it could still be trivially iterated if those two pieces are actually reasonable to build.

If the global state issues can be resolved (and I'm only aware of a few myself, but I'm sure there's more out there), parallel semantic analysis would be a nice speed boost.

On 9/13/2011 4:58 PM, Brad Roberts wrote:
> On Tue, 13 Sep 2011, Walter Bright wrote:
>
>> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.
> Does the compiler have a graph of dependencies at all?

No. Dependencies are discovered by doing semantic analysis. Trying to split that into two separate phases would likely be complex and doesn't seem worthwhile.

>    Easy to walk
> without requiring pausing to do work at each node?  One of the things
> we talked about _ages_ ago that I've had kicking around in the back of my
> head ever sense was breaking the problem into two pieces.
>
> Piece 1: A process that finds nodes in the graph that have no unfulfilled dependencies and adds those to a queue to be analyzed.
>
> Piece 2: a thread pool of workers that pull those work items and analyzes them.
>
> As elements finish #2, #1 produces more work due to satisfied dependencies.  Repeat until no more work can be done.
>
> if the graph is fully analyzed, success, if not fail due to true circularness.
>
> For the time being, the worker probably needs to not really be using threads due to the over abundant use of global state.  But it could still be trivially iterated if those two pieces are actually reasonable to build.
>
> If the global state issues can be resolved (and I'm only aware of a few myself, but I'm sure there's more out there), parallel semantic analysis would be a nice speed boost.
>
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals
>
>

On 14.09.2011 00:04, Walter Bright wrote:
> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.

I've been trying something similar for Visual D in its yet to integrate semantic analysis for intellisense. Still, static if and mixins get in the way of complete "on demand" handling. When a symbol is searched in a scope (e.g. a module, class, struct), some preparational work has to be done before the member list can be searched:

1. all "simple" non-scoping members are expanded (version/debug conditions, attributed declaration blocks). the branch inserted to the scopes' member list is also searched for "simple" non-scoping members (this step could also be done non-lazily, but doing it lazily slightly changes the interaction of version statements and conditionals with "static if" conditionals - good or bad, I don't know)

2. "complex" non-scoping members are expanded in lexical order (static if, mixins). When inserting the expanded branch into the scopes member list, the expansion restarts at 1.

This works out better than the current dmd implementation, e.g. when forward referencing symbols in a mixin. There are still situations that depend on interpretation order, but that is to be expected when "static if" is used.

It might be good to define the lookup mechanism, so it would be possible to determine whether a failing forward reference is beyond expected behaviour rather than a compiler-implementation detail.

On 9/14/2011 12:06 AM, Rainer Schuetze wrote:
>
> On 14.09.2011 00:04, Walter Bright wrote:
>> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.
>
> I've been trying something similar for Visual D in its yet to integrate semantic analysis for intellisense. Still, static if and mixins get in the way of complete "on demand" handling. When a symbol is searched in a scope (e.g. a module, class, struct), some preparational work has to be done before the member list can be searched:
>
> 1. all "simple" non-scoping members are expanded (version/debug conditions, attributed declaration blocks). the branch inserted to the scopes' member list is also searched for "simple" non-scoping members (this step could also be done non-lazily, but doing it lazily slightly changes the interaction of version statements and conditionals with "static if" conditionals - good or bad, I don't know)
>
> 2. "complex" non-scoping members are expanded in lexical order (static if, mixins). When inserting the expanded branch into the scopes member list, the expansion restarts at 1.
>
> This works out better than the current dmd implementation, e.g. when forward referencing symbols in a mixin. There are still situations that depend on interpretation order, but that is to be expected when "static if" is used.
>
> It might be good to define the lookup mechanism, so it would be possible to determine whether a failing forward reference is beyond expected behaviour rather than a compiler-implementation detail.
>

This is good stuff.

On 9/14/11 9:47 AM, Walter Bright wrote:
> On 9/14/2011 12:06 AM, Rainer Schuetze wrote:
>> This works out better than the current dmd implementation, e.g. when forward referencing symbols in a mixin. There are still situations that depend on interpretation order, but that is to be expected when "static if" is used.
>>
>> It might be good to define the lookup mechanism, so it would be possible to determine whether a failing forward reference is beyond expected behaviour rather than a compiler-implementation detail.
>>
>
> This is good stuff.

I'd love to see a clear definition of the behavior of ?static if? and friends, since trying to find out what happens e.g. when forward referencing something from a mixin or referencing the mixed-in scope from a mixin (e.g. via typeof(this), when the template is mixed into a class/struct) is more or less pure guesswork right now.

Also, even if this certainly isn't the best way to advertise for D, it would be great if the definition order-related peculiarities could be clearly mentioned in the docs (e.g. for static if), since these issues caused me a big headache when I first stumbled across them (and they still occasionally do).

David

On 09/14/2011 12:06 AM, Rainer Schuetze wrote:
>
> On 14.09.2011 00:04, Walter Bright wrote:
>> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.
>
> I've been trying something similar for Visual D in its yet to integrate semantic analysis for intellisense. Still, static if and mixins get in the way of complete "on demand" handling. When a symbol is searched in a scope (e.g. a module, class, struct), some preparational work has to be done before the member list can be searched:
>
> 1. all "simple" non-scoping members are expanded (version/debug conditions, attributed declaration blocks). the branch inserted to the scopes' member list is also searched for "simple" non-scoping members (this step could also be done non-lazily, but doing it lazily slightly changes the interaction of version statements and conditionals with "static if" conditionals - good or bad, I don't know)
>
> 2. "complex" non-scoping members are expanded in lexical order (static if, mixins). When inserting the expanded branch into the scopes member list, the expansion restarts at 1.
>
> This works out better than the current dmd implementation, e.g. when forward referencing symbols in a mixin. There are still situations that depend on interpretation order, but that is to be expected when "static if" is used.
>

Every time I've puzzled over the problem, the solution I've gravitated to is to have the symbol table logic result be tri-state: symbol-found, no-symbol, unknown/incomplete (for when a lookup includes an unprocessed scope). From there, you greedily evaluate all symbol that you can and proceed with whatever processing can be done, bailing when an "incomplete" results is found and keeping a list of where to come back and try again later. The only question then is how to handle the case where you dead lock. I suspect that if you make that illegal, a lot of legacy code will break. I'm going to guess we will want to have a small set of well thought out deadlock escape rules.

> It might be good to define the lookup mechanism, so it would be possible to determine whether a failing forward reference is beyond expected behaviour rather than a compiler-implementation detail.
>
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

On 15.09.2011 05:58, Benjamin Shropshire wrote:
> On 09/14/2011 12:06 AM, Rainer Schuetze wrote:
>>
>> On 14.09.2011 00:04, Walter Bright wrote:
>>> Don, just so you know, I've been thinking for a while about transitioning from doing the semantic pass in order to doing it completely "on demand". In other words, try to semantic a declaration. In the process, any declarations it depends on are semantic'd if not already, recursively.
>>
>> I've been trying something similar for Visual D in its yet to integrate semantic analysis for intellisense. Still, static if and mixins get in the way of complete "on demand" handling. When a symbol is searched in a scope (e.g. a module, class, struct), some preparational work has to be done before the member list can be searched:
>>
>> 1. all "simple" non-scoping members are expanded (version/debug conditions, attributed declaration blocks). the branch inserted to the scopes' member list is also searched for "simple" non-scoping members (this step could also be done non-lazily, but doing it lazily slightly changes the interaction of version statements and conditionals with "static if" conditionals - good or bad, I don't know)
>>
>> 2. "complex" non-scoping members are expanded in lexical order (static if, mixins). When inserting the expanded branch into the scopes member list, the expansion restarts at 1.
>>
>> This works out better than the current dmd implementation, e.g. when forward referencing symbols in a mixin. There are still situations that depend on interpretation order, but that is to be expected when "static if" is used.
>>
>
> Every time I've puzzled over the problem, the solution I've gravitated to is to have the symbol table logic result be tri-state: symbol-found, no-symbol, unknown/incomplete (for when a lookup includes an unprocessed scope). From there, you greedily evaluate all symbol that you can and proceed with whatever processing can be done, bailing when an "incomplete" results is found and keeping a list of where to come back and try again later. The only question then is how to handle the case where you dead lock. I suspect that if you make that illegal, a lot of legacy code will break. I'm going to guess we will want to have a small set of well thought out deadlock escape rules.

I guess, Walter also wants to get rid of the "try again later" part. Especially is-expressions and trait(compiles) are getting rather indeterministic and might depend on other symbols being looked up before. If the evaluation is lazy, there is some hope that dependencies will be cyclic only in cases that are actual errors. I'm not sure about a good cycle-detection, though. (Is that what you meant by "deadlock escape"?)

What happens, if the evaluation of "static if" turns out to require symbols from the same scope? (Something I did not mention above: unconditionally existing or expanded members of a scope should be added to the symbol lookup as soon as possible.) My current suggestion is: do not recurse into the expansion of "complex" members, just use the currently available symbols.