A debate has arisen in the course of using an assembler (which does a bit of preprocessing first, but is mainly a static assembler):

This particular assembler allows recursive macros to be defined, which it then attempts to resolve (statically, at compile time) and embed in the binary output.

The question is, does this language feature still allow the assembler to terminate (for all input) or is there a case where the assembler will never terminate - excluding memory considerations?

From an empirical perspective "even short programs take forever to compile" but whether this is theoretically rigorous is a different story, at which point we defer to cs.stackexchange!

  • 5
    $\begingroup$ We probably can't answer it with 100% certainty without being familiar with the specifics of how macros work for this assembler, but this seems like it would be easy to test with a simple experiment. What happens if you introduce macro that is the equivalent of #define a() a();a();, and then run the assembler on it? Does it appear to run forever? If so, the answer seems pretty clear.... $\endgroup$ – D.W. Jun 21 '15 at 7:12
  • $\begingroup$ Depends on the kind of recursion you allow. cf primitive vs $\mu$-recursion. $\endgroup$ – Raphael Jun 21 '15 at 7:24
  • 3
    $\begingroup$ Even #define a() a() should be enough for a test if you are only after termination. But the thing may have elementary loop detectors, so that there is no way to be sure without a precise specification, as said by @D.W. . $\endgroup$ – babou Jun 21 '15 at 7:24
  • $\begingroup$ Yeah the call stack was depleted after 16 calls. Can we "trick" it in this case? Or do we just lose the ability to do more recursive calls for the benefit of ensured termination? $\endgroup$ – lol Jun 21 '15 at 8:04
  • 1
    $\begingroup$ It seems that recursion is there as a convenience to organize macros, but should not be considered a "looping" feature is the usual programming sense. Does the macro language have loops? It seems, as one would expect, that the macro language will always terminate, probably rather fast. But again: having a spec would be better. $\endgroup$ – babou Jun 21 '15 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.