4 ms·

I implemented an R5RS macro expander, and, at least from the perspective of Scheme and macros, the only truly base is application, and all other forms can be re

by sreque 8y ago

I implemented an R5RS macro expander, and, at least from the perspective of Scheme and macros, the only truly base is application, and all other forms can be reduced to it. For my expander I actually implemented all let forms, for instance, as macros that reduced to lambda applications. Now other lisps might have more forms that don't reduce quite nicely, I'm not sure, I still strongly believe in my original point that lisp practically has no syntax, and that's one of the reasons its easy to create macro systems for it.

lispm 8y ago
That one can expand macros does not make them non-existing. The programmer writes the macro forms, not their expansions. If you actually look into the R5RS document, you can see that chapters 7.1.3-7.1.6 define the syntax for that particular toy version of Scheme. Lisp usually has three syntax types: function applications, built-in operators and macro operators. That you can implement some constructs by expanding them to LAMBDA expressions says nothing about the syntax of Scheme or Lisp. Lisp users don't develop in pure lambda calculus. Each built-in operator and each macro operator are adding syntax. One can reduce arithmetic to lambda expressions - this does not mean that Scheme has no arithmetic operators. R5RS documents arithmetic and not their lambda variant. Same as R5RS defines the syntax for DEFINE, COND, IF, CASE, SYNTAX-RULES, ... That's what the progammer sees, not LAMBDA. Take any real world Scheme, like Chicken Scheme -> lots of macros have added syntax. That's what the programmer uses, not lambda calculus.
kazinator 8y ago
What is your rewrite rule for reducing (set! var value) to application? For iteration and selection, did you just turn everything into lambdas? E.g. (if x y z) -> (__if_fun (lambda () x) (lambda () y) (lambda () z)) If you minimize the special forms, you have fewer cases in the expanding code walker; but then the compiler has little information for producing good code. Note that a compiler doesn't necessarily just let every instance of function application be function application. If the above expansion for if is forced upon you as a compiler writer, you can recognize the __if_fun function as a built-in and open-code it, effectively undoing the reduction to function application. Check that all arguments are lambdas (and diagnose if they aren't zero-argument lambdas) destructure them and turn into an open-coded branching construct. The cost for fewer code walking cases in the macro expander ends up being more cruft in the compiler. About let to lambda: in non-toy implementations, you almost always want to go the other way: recognize lambdas which can be turned into lets.
kbp 8y ago
> For my expander I actually implemented all let forms, for instance, as macros that reduced to lambda applications. > Now other lisps might have more forms that don't reduce quite nicely, I'm not sure, I still strongly believe in my original point that lisp practically has no syntax This isn't an argument against Lisp having syntax: it does have those operators, and each one defines its own syntax. The fact that they can be written entirely in the language itself doesn't mean Lisp doesn't have syntax, it means that Lisp has extensible syntax: you can add more syntax whenever you like, and in some dialects, you can remove or replace the pre-defined syntax forms. Syntactic sugar is still syntax, too: in C, arr[i] is just sugar for *(arr + i), but I don't know anyone who would claim that array indexing isn't part of C's syntax.

by sreque 8y ago

lispm 8y ago

That one can expand macros does not make them non-existing. The programmer writes the macro forms, not their expansions. If you actually look into the R5RS document, you can see that chapters 7.1.3-7.1.6 define the syntax for that particular toy version of Scheme. Lisp usually has three syntax types: function applications, built-in operators and macro operators. That you can implement some constructs by expanding them to LAMBDA expressions says nothing about the syntax of Scheme or Lisp. Lisp users don't develop in pure lambda calculus. Each built-in operator and each macro operator are adding syntax. One can reduce arithmetic to lambda expressions - this does not mean that Scheme has no arithmetic operators. R5RS documents arithmetic and not their lambda variant. Same as R5RS defines the syntax for DEFINE, COND, IF, CASE, SYNTAX-RULES, ... That's what the progammer sees, not LAMBDA. Take any real world Scheme, like Chicken Scheme -> lots of macros have added syntax. That's what the programmer uses, not lambda calculus.

kazinator 8y ago

What is your rewrite rule for reducing (set! var value) to application? For iteration and selection, did you just turn everything into lambdas? E.g. (if x y z) -> (__if_fun (lambda () x) (lambda () y) (lambda () z)) If you minimize the special forms, you have fewer cases in the expanding code walker; but then the compiler has little information for producing good code. Note that a compiler doesn't necessarily just let every instance of function application be function application. If the above expansion for if is forced upon you as a compiler writer, you can recognize the __if_fun function as a built-in and open-code it, effectively undoing the reduction to function application. Check that all arguments are lambdas (and diagnose if they aren't zero-argument lambdas) destructure them and turn into an open-coded branching construct. The cost for fewer code walking cases in the macro expander ends up being more cruft in the compiler. About let to lambda: in non-toy implementations, you almost always want to go the other way: recognize lambdas which can be turned into lets.

kbp 8y ago

> For my expander I actually implemented all let forms, for instance, as macros that reduced to lambda applications. > Now other lisps might have more forms that don't reduce quite nicely, I'm not sure, I still strongly believe in my original point that lisp practically has no syntax This isn't an argument against Lisp having syntax: it does have those operators, and each one defines its own syntax. The fact that they can be written entirely in the language itself doesn't mean Lisp doesn't have syntax, it means that Lisp has extensible syntax: you can add more syntax whenever you like, and in some dialects, you can remove or replace the pre-defined syntax forms. Syntactic sugar is still syntax, too: in C, arr[i] is just sugar for *(arr + i), but I don't know anyone who would claim that array indexing isn't part of C's syntax.