4 ms·

1. Then you haven't seen very much sugar. Take a look at the transformations used in Racket, for instance. Entire parts of the language that would be built into

1. Then you haven't seen very much sugar. Take a look at the transformations used in Racket, for instance. Entire parts of the language that would be built into other languages are seamlessly expressed through extremely sophisticated sugar. You can "argue" all you want, but it's a perfectly sensible language definition approach, and it works superbly, without any clear indication of anything having "gone wrong". 2. I don't know what it means for "sugar" to be or not be "decidable": that sentence isn't even type-correct. But even guessing at what you might mean, making something language-specific isn't going to help you, assuming a typical Turing-complete language, if the underlying problem is not decidable. (I don't even know what a language-independent "magical sugaring oracle" might be, because any "sugaring" procedure would have to be defined relative to some language that it works on. Except, maybe, in the "magical" case, about which I don't know very much, I'm afraid.) Of course you can approximate it – you can always approximate anything you want – but you're then solving a different problem. It's fine perfectly to define that as the problem you want solved. But it helps to be clear about what one wants, and the OP was not.

Dylan16807 12y ago
By 'decidable' I meant that you can write an always-correct, always-halting algorithm for taking a desugared program in the language and transforming it into an 'idiomatic' sugared form. Then you have a nice bidirectional idempotent transform. (The 'gone wrong' was more in the definition of 'sugar' but I don't want to argue that, just ignore that line.) Most languages have a fixed set of simple sugar. There is no approximation needed; you can make a 100% perfect sugar/desugar mechanism. I'm glad you agree that it should be language-specific. That way we can discuss the typical language where the language itself is Turing-complete but the sugar-related transformations are not even close to Turing-complete. The original statement discussed having an ability to transform code into an idiomatic form as a 'language feature'. This means it's intertwined with the design of the sugar itself, and it's up to the language designers to make it feasible. When you discuss all the ways a program could arrive at the same result, you are going far beyond the realm of the finite sugars that apply to a specific language. The Halting Problem is not relevant.
- shriramkmurthi 12y ago
  Just because you can algorithmically desugar doesn't mean you can invert that transformation. The property you're looking for is invertibility, not idempotence (which neither follows nor is relevant), and it doesn't follow. As for the power of the desugaring system, you apparently decided to just ignore my first paragraph as an inconvenient truth. I could repeat it. But I can give you even simpler examples that are well-known as canonical examples of the genre: C++ templates, Scheme macros. Scheme's macros are about as simple a desugaring system as you could want. And yet even its _simplest_ version — too weak to express many of the language's constructs, way weaker than Racket's — is Turing-complete. I don't even know what you're talking about with "finite" sugars (all programs are finite by definition, but that doesn't imply anything about their dynamic properties). I'm guessing haven't really thought about this problem much and are just speculating casually. You might want to read work like http://cs.brown.edu/~sk/Publications/Papers/Published/pk-resuarging/ http://cs.brown.edu/~sk/Publications/Papers/Published/pk-res... which shows some of the complexity involved. (Just to make you happy, the desugaring in this paper uses about as "simple" a desugaring mechanism as you could want. And it is about an extended version of precisely the problem of undoing desugaring, hence the name "resugaring".) Once you've understood this material we'd be in a position to actually have a meaningful conversation.
  - Dylan16807 12y ago
    I'm not looking for the ability to strictly invert, I'm looking for the ability to make a canonical sugaring. desugar+resugar may or may not give me the same as the original, but it will be idempotent. Scheme macros? Oh wow we really are talking about completely different things. I'm talking about fixed transformations that are part of the language (just like the original comment seems to be, as far as I can tell), not arbitrary user-supplied transformations. And I admit that I'm coming at this rather casually, but I'm considering languages I've used that have very little sugar and writing this sort of mechanism would be easy. I looked at that paper a bit, they're tackling a very hard problem by taking languages with complex sugar and making a program that automatically processes sugar into an algorithm for resugaring. That's much harder than codesigning language and sugar to be amenable to resugaring.

Dylan16807 12y ago

By 'decidable' I meant that you can write an always-correct, always-halting algorithm for taking a desugared program in the language and transforming it into an 'idiomatic' sugared form. Then you have a nice bidirectional idempotent transform. (The 'gone wrong' was more in the definition of 'sugar' but I don't want to argue that, just ignore that line.) Most languages have a fixed set of simple sugar. There is no approximation needed; you can make a 100% perfect sugar/desugar mechanism. I'm glad you agree that it should be language-specific. That way we can discuss the typical language where the language itself is Turing-complete but the sugar-related transformations are not even close to Turing-complete. The original statement discussed having an ability to transform code into an idiomatic form as a 'language feature'. This means it's intertwined with the design of the sugar itself, and it's up to the language designers to make it feasible. When you discuss all the ways a program could arrive at the same result, you are going far beyond the realm of the finite sugars that apply to a specific language. The Halting Problem is not relevant.

shriramkmurthi 12y ago
Just because you can algorithmically desugar doesn't mean you can invert that transformation. The property you're looking for is invertibility, not idempotence (which neither follows nor is relevant), and it doesn't follow. As for the power of the desugaring system, you apparently decided to just ignore my first paragraph as an inconvenient truth. I could repeat it. But I can give you even simpler examples that are well-known as canonical examples of the genre: C++ templates, Scheme macros. Scheme's macros are about as simple a desugaring system as you could want. And yet even its _simplest_ version — too weak to express many of the language's constructs, way weaker than Racket's — is Turing-complete. I don't even know what you're talking about with "finite" sugars (all programs are finite by definition, but that doesn't imply anything about their dynamic properties). I'm guessing haven't really thought about this problem much and are just speculating casually. You might want to read work like http://cs.brown.edu/~sk/Publications/Papers/Published/pk-resuarging/ http://cs.brown.edu/~sk/Publications/Papers/Published/pk-res... which shows some of the complexity involved. (Just to make you happy, the desugaring in this paper uses about as "simple" a desugaring mechanism as you could want. And it is about an extended version of precisely the problem of undoing desugaring, hence the name "resugaring".) Once you've understood this material we'd be in a position to actually have a meaningful conversation.
- Dylan16807 12y ago
  I'm not looking for the ability to strictly invert, I'm looking for the ability to make a canonical sugaring. desugar+resugar may or may not give me the same as the original, but it will be idempotent. Scheme macros? Oh wow we really are talking about completely different things. I'm talking about fixed transformations that are part of the language (just like the original comment seems to be, as far as I can tell), not arbitrary user-supplied transformations. And I admit that I'm coming at this rather casually, but I'm considering languages I've used that have very little sugar and writing this sort of mechanism would be easy. I looked at that paper a bit, they're tackling a very hard problem by taking languages with complex sugar and making a program that automatically processes sugar into an algorithm for resugaring. That's much harder than codesigning language and sugar to be amenable to resugaring.