Lambda the Ultimate

What's he got to do with it? The anecdote isn't about him, or is there more than one?

The original quote is about it being Turtles all the way down. For some reason that reminds me of the difficulty of seperating functions within software development - no matter where you draw the lines, it's still software on both sides of the division.

Eddington's the guy, IIRC. Maybe Russell (but I think that's the one with the punch line "Oh alright, I thought you said 100 million years"). Definitely not Hawking.

The opening of "A Brief History of Time" starts with the turtle story.

But to make things even more frustrating Hawking just writes "a wellknown scientist (some say it was Bertrand Russell)". No wonder I wasn't sure who it was.

I want to remember it was feynman, perhaps recounted in his "pleasure of finding things out".

However, tha intarweb is siding with the russel hypothesis.

This reminds me of a coworker who likes to pull my chain saying that "it's all syntax." If you formally define semantics, you are simply using syntax again etc. I am sure everyone here understands what we mean when we say semantics aren't the same as syntax, but try arguing with someone who is smart and tries to resist the distinction. It's quite frustrating :-)

This reminds me of a coworker who likes to pull my chain saying that "it's all syntax."... try arguing with someone who is smart and tries to resist the distinction. It's quite frustrating :-)

If he can argue that, he could probably equally convincingly argue that "it's all semantics." A little cleverness is a dangerous thing! :)

I think most researchers understand that the barrier between syntax and semantics is porous. Like rationals, an object typically admits many ways of factoring itself into syntactic and semantic parts, including ways in which one or the other is trivial. But (and this is very vague but) I think you can only find factorizations where the semantic part is trivial if the object in question is `computable'. A way to attack the "it's all syntax" argument is to point out the chicken-egg problem between, for example, set theory and logic; the same argument works for "it's all semantics." (We don't know that set theory is consistent, for instance.)

In programming languages, there is a very strong tendency to factor a language so the syntactic portion is context-free, both for historical reasons and because we have decent tools for parsing context-free grammars. I think this fact confuses a lot of programmers into thinking the syntax-semantics barrier is immovable.

In the calculus I'm working on now, my terms have a grammar which is not context-free, and I think it's quite nice that way, but I am considering refactoring it so that the context-sensitive conditions turn out as typing rules, just because people find context-sensitive grammars `weird'.

To communicate meaning though, you have to represent it. So to specify the semantics, you have to write something which would have a syntax.

I'm guessing a simple example of this is prefix/postfix/mixfix syntax. Underneath the parameter ordering is a function with some semantics. For example, integer addition is integer addition whether you're on a RPN HP calculator, in Scheme, or doing the usual infix representation on paper (excluding space/representation limitations).

Last week or so I castigated myself for not clearly distinguishing between semantics in the usual PLT sense and what I called "intentional PL semantics", that is, the meaning of the program from the point of view of the programmer/user,
Now I don't feel so bad, as I've since noticed that this is quite common. ;-)

For example, integer addition is integer addition whether you're on a RPN HP calculator, in Scheme, or doing the usual infix representation on paper

I think this is a nice example of the distinction I want to draw. The intentional semantics of all of these are the same, though the PLT semantics may not be.

The reason is that the latter type of semantics must have well-defined formal properties to be considered adequate, and formal details matter.
Some of the different cases you mention might in fact have different formal properties.

For example, the various computer or calculator implementation are actually going to do addition modulo some value (depending on the width integer storage).
This value will vary from case to case and therefore they are not equivalent formal systems.
On paper we normally don't assume any roll-over, which makes it formally different again.

Part of the reason that it is hard to distinguish between formal syntax and formal semantics is that they both must be computational in nature, so they are the "same type of thing" in a sense.

Intentional semantics (and general semantics) has no such limitation (that we know of yet), and finding ways to map it onto more formal semantics is 99% of the challenge of software development.

Last week or so I castigated myself for not clearly distinguishing between
semantics in the usual PLT sense and what I called "intentional PL semantics" ...

Good lord, man!! Intellectual honesty is important and all, but I think you're being way to hard on yourself!

Oh, wait ...

You said castigated?

Uhhh ..... never mind ...

: )

[With apologies to Gilda Radner, as Emily Litella, may she rest in peace.]

If thou didst put this soure cold habit on
To castigate thy pride, 'twere well.

I'm guessing a simple example of this is prefix/postfix/mixfix syntax. Underneath the parameter ordering is a function with some semantics. For example, integer addition is integer addition whether you're on a RPN HP calculator, in Scheme, or doing the usual infix representation on paper (excluding space/representation limitations).

Nice try. :-) This is a good example of exactly what's being discussed above. Lambda calculus provides a simple example of a case where integer addition (along with anything else that's computable) can be implemented as nothing but a series of (arguably) purely syntactic transformations.

If you're not familiar with this, just imagine how the first cavemen might have done addition: using a "syntax" involving a number of stones. To add one to a number, represented by a pile of stones, you perform the syntactic transformation of adding a syntactic token (a stone) to the pile. You can perform any addition this way, if you have enough time, and enough stones. For such cavemen, the actual act of addition would have been entirely syntactic. Assigning a meaning to the resulting pile of stones introduces semantics, but that's only after the answer has been arrived at, and only because it involves translating between systems.

Have you ever written a program with perfect syntax and bad semantics? Lots of people do. That's why they crash.

If you're pulling the article in, then it sounds very much like that people are making a syntax and have no way to map to another syntax while keeping the semantics of programs. It seems that most programmers are so tied up in syntax and representation (rocks vs. numerals) that they aren't thinking about the meaning of what they are writing.

I can't tell if you're demonstrating me wrong. You've just done two implementations of the natural numbers. How is it that you know they are the same? They share the same semantics!

As Marc Hamann pointed out, the word "semantics" is being used in two different senses here. What Marc called the "usual PLT sense" refers to an aspect of a language's definition that is (usually) necessary in order to determine the result that any given program will produce. However, as Frank pointed out, there are typically many ways of factoring something into syntactic and semantic parts. The point of the examples I gave was to show cases where evaluation operations are entirely syntactic, which illustrates an aspect of the point that Ehud was referring to. Incidentally, it also demonstrates that the PL semantics of integer addition may be different between different systems.

The sort of semantics you seem to be referring to, which Marc called "intentional PL semantics", are another matter. That's what I referred to as "translating between systems". Re-reading your original post, you mentioned "communicating meaning", and seem to be focusing on that communication aspect, as opposed to the way in which a result is arrived at. However, communicating meaning can't be done without first dealing with the "internal" PL theory semantics of the languages in question.

To relate this to your prefix/postfix/mixfix example, the "function with some semantics" that lies beneath the syntax first has a semantics in the PL theory sense. This semantics may be different for each of the different systems that implement integer addition, if the systems work in different ways. If the semantics were the same for each of them, they wouldn't really be different systems. To demonstrate that two different systems implement the "same" operation, you'd have to prove the necessary correspondence between their respective semantics.

In your example, you may have intended to focus on a case where the PL semantics were in fact identical in each case, and only the syntax differed. But the fact that any given semantics can support multiple syntaxes doesn't tell us much about the syntactic/semantic divide that Ehud referred to.

If you're pulling the article in, then it sounds very much like that people are making a syntax and have no way to map to another syntax while keeping the semantics of programs. It seems that most programmers are so tied up in syntax and representation (rocks vs. numerals) that they aren't thinking about the meaning of what they are writing.

Again, you're not talking about PL semantics here, which makes things sound a lot easier than they really are. You'd be absolutely right if all languages were simply syntactic layers over some universal language with a single common semantics. Alas, that's not the case. The problem is that languages have (PL) semantics which are non-trivial to map to other languages with different semantics.