Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

We seem to be saying the same thing; I just don’t see any inherent meaning in it. A literal interpretation of meta- would have us define it like this:

    Instance ::= 0
    Meta(X)  ::= Succ(X)
But it’s much more convenient to define meta- recursively:

    Instance ::= 0
    Meta(X)  ::= Succ(X)
               | Meta(Succ(X))
In both cases, we have an arbitrary designation:

    Class    ::= Succ(Instance)
That kind of redundancy is a linguistic artifact, not a deeply meaningful one.

It’s not the case that reaching the second level of abstraction necessarily results in enough flexibility to make the inductive step. As a counterexample, consider C macros, which only add one meta- because they are only expanded once. Lisp macros, on the other hand, are expanded until a fixed point is found. That’s why Lisp macros are Turing-complete while the C preprocessor is only a pushdown automaton.



A bit of disagreement with your last paragraph: The (Common) Lisp macro processor is Turing-complete trivially because it invokes a Turing-complete language along the way, not because of power inherent in its expansion strategy.

Common Lisp macro bodies are written in Common Lisp, i.e. written in a Turing-complete language — they would still be Turing-complete even if we wrote them in the subset Lisp-without-macros. The C preprocessor, on the other hand, does not invoke a Turing-complete language to compute a macro's expansion.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: