Comment by ajross
14 years ago
S-expressions don't declare types, though. A sexp grammar for the same thing would be basically isomorphic to a fully-parenthesized C type expression.
C has some glitches: the fact that the pointer type decoration goes on the left while the array decoration goes on the right is one. The precedence rule that requires parentheses for function pointers is unfortunate. And the putting the decoration on the variable and not the type is just simply a bug IMHO.
But the complexity here is inherent. Complicated types require complicated expressions no matter what grammar you use.
I think the gist of your argument is this: both C languages and s-expression based languages are touring complete and thus isomorphic.
For any given C compiler I can write a lisp program that gives the same answers for input. Likewise for any Lisp program I can make input for a c compiler that yields the same behavior. I know this because both c and lisp are touring complete. Yay formal languages !!!
But touring completeness and isomorphism are not exactly the same thing. When you run into undefined behavior in your c/c++ program, there does not exist exactly one s-expression to cover the possible interpretations of every compiler. You may need to write several compiler specific s-expressions to cover all the behaviors from the same c expression.
These compiler specific difference break the mappings required for isomorphism.
Lisps also have two different ways of evaluating input. Lazy and strict. So one s-expression may require several c expressions to deal with edge cases. Nothing is perfect.
Sadly, either way you look at it, c expressions are not quite isomorphic to s-expressions.
I agree with you about left to right vs right to left precedence. That's actually why I prefer s-expressions to order of operations and infix notation.
Also some complexity is inherent, some is self imposed. Sometimes static typing is nice and catches errors. Sometimes dynamic typing can save a lot of keystrokes.