Tail pad optimization, cache friendlyness and C++ interrop

[H. S. Teoh via Digitalmars-d]

On Thu, Jun 19, 2014 at 07:12:52PM +0000, via Digitalmars-d wrote:
> On Thursday, 19 June 2014 at 18:50:27 UTC, H. S. Teoh via Digitalmars-d
> wrote:
> >Exactly.  Just because something is *finite*, doesn't necessarily
> >mean it's practical.  Anything that requires enumeration of all
> >possible states is impractical, because it has an exponential worst
> >case bound, which is unacceptable for compilation time (or for
> >anything, really, except in the most trivial cases).
> 
> You are being silly. You either discuss computability or you discuss
> complexity. Please don't mix the two topics.
> 
> You either discuss a useful verification of safe features or you
> don't.
> 
> It's not at all impossible to verify memory safety for real time
> applications. Real time applications have an upper bound on how long
> they should run. This even holds for TMs.
> 
> The problem "does the TM terminate within N steps" is decidable.

Decidable doesn't mean feasible. You have to run a simulator of the
program for N steps in order to determine whether it terminates. If N is
large, this means compilation will be impractically slow.

The halting problem is not just about needing infinite time, it's also
about the non-existence of algorithms that can analyze every possible
program. Even if a given TM never terminates, as long as it fits into an
analysable pattern, we can prove its non-termination in finite time. The
analysing algorithm is able to "compress" the proof into finite length.
But the non-solvability of the halting problem means that there is no
algorithm that can compress every possible program. This means there is
no such algorithm that can determine termination within N steps for
arbitrary N, except the one that enumerates all possible states up to N
steps. If I have code like this:

	while (!finished) {
		if (arbitarilyComplexFalseCondition)
			unsafeOperation();
		else
			safeOperation();

		finished = arbitrarilyComplexStoppingCondition;
	}

you cannot, in general, prove safety without enumerating all possible
states (since you can't predict which branch the if statement will
take). Since enumerating all possible states is impractical, this means
your N-step termination problem is practically unsolvable, even if it's
decidable in theory.


T

-- 
The early bird gets the worm. Moral: ewww...