A Perspective on D from game industry

H. S. Teoh via Digitalmars-d digitalmars-d at puremagic.com
Tue Jun 17 10:17:49 PDT 2014


On Tue, Jun 17, 2014 at 04:50:07PM +0000, via Digitalmars-d wrote:
> On Tuesday, 17 June 2014 at 16:08:18 UTC, H. S. Teoh via
> Digitalmars-d wrote:
> >I think you are underestimating the complexity of programming.
> 
> No need to go ad hominem. I don't underestimate anything. What
> makes you think so?

I did not intend that as an ad hominem attack, I apologize if it came
across that way. My point was just that automation, while desirable,
isn't always possible, and that shouldn't be the only reason for
rejecting certain language features.


> >Automated tools can only go so far -- ultimately, human intervention
> >is needed for certain code transformations, and perhaps even that can
> >only go so far, because programming is inherently complex!
> 
> No more complex then computer assisted proof systems.

Yes, and such proof systems, AFAIK, are limited to highly-constrained
subsets of what programming languages today offer in general, because
automated proving becomes intractible once you reach a certain point.


> >Turing-complete languages exhibit unsolvable problems like the
> >halting problem (that even humans can't solve),
> 
> How does the halting problem relate to anything practical? It's a fun
> example of a proof where you reason about one infinite dimension being
> larger than another infinite dimension, but that is about all it
> provides.

The halting problem is equivalent to Kolgomorov complexity, which in
turn relates to optimal compression, which has applications in global
optimization problems in compiler technology. Sure, the way some
textbooks present it, it's just an obscure academic exercise, but it
does have far-reaching implications.

But the point is, Turing-complete language are capable of expressing
problems in the spectrum that spans from trivial problems to something
of the complexity of the unsolvable halting problem, and while that
endpoint (i.e., the halting problem) itself may not be interesting in
practical applications, the stuff that lies in between does, and they
can take on any level of complexity up to the halting problem, so many
of them are intractible to automate.


> >besides also exhibiting intermediate intractible complexities like
> >non-primitive-recursive functionality and the expression of
> >NP-complete problems that are inherently irreducible to simpler
> >constructs.
> 
> Most NP-complete problems are NP-complete because they are expressed
> as a decision problem (boolean function). The moment you take the
> quantifiable sub problem and formulate it as something reasonable it
> often seize to be NPC.
> 
> You almost never want an optimal result, you want a good result that
> require less resources. NPC is a funny construct, but reasoning about
> NP-hard problems has very little practical value and that's the only
> thing NPC is good for.

That depends on your specific application. There are applications for
which the whole point *is* to find the optimal solution. I don't think
you can simply write off the whole thing as "unnecessary".


> NPC has little to do with automated code translation. E.g. if you for
> some reason want to remove all "while(){}" loops you can easily
> replace them with "if(){do{}while()}".

Some forms of code translation may very well be NP-complete, or worse.
Like running global optimization on a set of mutually-recursive
functions. And some instances of optimal register allocation, IIRC.


> >around, etc.. So this part is easily automatable. But I think you're
> >deceiving yourself if you think that automation is possible beyond
> >the trivialities of programming.
> 
> Gofix worked out ok in a macro-free environment.
> 
> It cannot work in a macro-heavy environment.
> 
> Of course, code transformations is easier in a pure functional
> language, but that does not change the fact that having a
> transformation-friendly imperative language is desirable.

True, but as I said, string mixins really should only be used as a last
resort, so 99% of the time you don't need to deal with them anyway. So
that shouldn't stop you from implementing automated code transformation
on the subset of D that doesn't include string mixins -- and it will
work just fine on code that doesn't use string mixins (or whatever else
there is in the language, that makes automation hard/impossible).
There's no need to get rid of string mixins just because of that 1% of
code that actually needs to use them. Nobody says that the
transformation must work on 100% of all D programs, otherwise we can't
have it at all. It's the same thing as computing a "good enough"
solution to an NP complete problem that isn't necessarily globally
optimal. I think it's "good enough" for automated code transformation to
work on a subset of D that doesn't include string mixins -- there are
use cases where string mixins is the cleanest solution, but nobody is
saying that code transformation MUST work on those cases too.


T

-- 
Жил-был король когда-то, при нём блоха жила.


More information about the Digitalmars-d mailing list