Why use a DFA instead of DIP1000?

[Richard (Rikki) Andrew Cattermole]

On 16/09/2025 11:20 PM, Dennis wrote:
>     And that would be a rewrite and I don't mean just DIP1000.
> 
>     Doing this stuff as part of the type system isn't the normal way to
>     handle it, and for good reason. Attaching a DFA engine today
>     directly into the type system to resolve this is quite frankly too
>     late. From what I've seen that would be a bad direction to go in and
>     have no desire to watch that being tried.
> 
> I don't understand this paragraph at all, you're referring to 5 
> different things (rewrite, DIP1000, too late, type system, things you've 
> seen) and I don't know the context/relevance of any of those.

Hmm, I think I see a missing piece of the puzzle.

A type system is the types and declarations and how they get processed 
in a language.

When a DFA is attached to a type system properly, you are not calling 
functions like runSemantic on AST nodes. This is handled by the worklist 
algorithm. This is an important distinction between what we have and 
what the more advanced type systems with a DFA attached to them have.

Take a look at all of the issues we have with resolving templates. These 
stem from not having the DFA directed type system. Its very easy to 
exceed what the compiler can instantiate with cycles and other ordering 
issues. We've all run into them and they are rarely fixable.

And no, this isn't a new thing. This is from the 70's just a different 
branch of DFA and related analysis engines. I doubt Walter would have 
learned this branch, and may not have been exposed to it, its mostly 
academic (for a reason up until the 90's). The papers he has sent me are 
all backend related, not these other branches.

I do want to say, that I have been knowingly confusing DFA and other 
analysis engines, this is fully intended. Their interplay can be pretty 
heavy and would feed from one to the other here. Lines get blurred in 
the implementation and their solutions can be based upon the same theory 
& algorithms.

Now compare us to the ML family with signatures (type classes), modules 
and their variation of meta-programming. They can resolve stuff we 
wouldn't have a dream of doing. We have to employ CTFE just to come 
close to what they can do, and even then there is stuff we simply will 
never be able to do due to ordering issues.

This would be a good time to define what lint level means to a type 
system. In essence it puts anything that the type system knows about 
into a read only mode. You can't change it in a given lint level engine.

This makes DIP1000 in the type system, not lint level. Due to it messing 
with storage classes.

What analysis dmd does do like VRP and CFG, is impressive. Not because 
they are the most advanced thing in the world (not even close). But 
because our type system wasn't meant to support it. This isn't a 
strength of its design.

A good thing to note here is how SDC uses a worklist algorithm to 
process its type system. 
https://github.com/snazzy-d/sdc/blob/master/src/d/semantic/scheduler.d

SDC will have the ability to solve problems that dmd cannot do. Not 
because the language prevents it, but because the type system 
implementation does not allow for it by having a much lower ceiling in 
its capability.

To give dmd the kind of capability where you have a DFA engine dictating 
analysis of the type system, or feeding a significant amount of 
information throughout a function is a rewrite. Simply because the 
existing architecture wasn't written with that in mind. It was never 
meant to have templates like we have today, nor analysis like VRP.

The literature is massive on these topics, and gets quite broad. It can 
be argued differently than what I am.

Some people who read this, may conclude that dmd needs a rewrite, and to 
that end I know SDC folks with love some help. However my take away from 
a pragmatic perspective is to recognize what we can't do, to help 
determine what we can do. D is a production language, not an academic or 
toy one. If we have to give up strong guarantees by default for DFA 
features then so be it, I'd rather have some than none.