If you're wondering what things like "operational" and "denotational" mean and what they look like in code, I created this article for my compilers students:
* A denotational semantics is a function M : Program -> (Value -> Value) that maps a program to a mathematical function.
* An operational semantics is a relation (=>) between consecutive machine states. That is, if state => state' holds, then the machine transitions from state to state'.
* The relation in a "big-step" operational semantics need not be decidable. Big-step relations are usually recursive.
* The relation in a "small-step" operational semantics must be decidable.
* When you implement a transition relation, =>, it's usually implemented as a function. That is, if you have a relation R \subseteq State x State, you can encode this as a "transfer function" f : State -> 2^State.
Where is a good place to get started with studying formal semantics? I've tried to follow chapters about formal semantics in LiSP, TAPL, CTM, and _The Definition of Standard ML_ with varying degrees of success (the material in TDoSML was beyond me), but I'm not sure where to start. I know part of the issue is getting familiar with the dense notation. I'm gradually getting an intuition for the stuff, but reading the right book would go a long way.
I've wondered if this is one of the things I missed by being self-taught, but I don't think most programmers working in (say) Java or Python could really follow it either.
I agree that documentation is useful and important, but too much programming languages documentation really doesn't answer some fundamental questions about the semantics of a language.
All too often, this is because the programming language designers/implementors don't know what the semantics are.
The answers for the examples given near the end of the article are often present in language documentation. You can dig around and find the answer or you can spend two minutes and write a test or you can crash/debug later. In any case, you'll eventually find the answer.
The real issue is that programmers new to a language are unlikely to even realize there's a semantic boondoggle in a given situation. Had they read all of the documentation, perhaps they would - but that's obviously not what most people do. Adding more pages to the documentation just to collect all semantics in one place wouldn't seem to make it more likely that a new programmer is going to read and properly understand their implications.
I don't think you can solve the problem of inexperience with additional education, but it's a common idea in academic circles.
Arguably one of the reasons for the success of C was that it was introduced along with a comprehensive codebase- Unix- which made its semantics crystal clear.
It would be worthwhile to examine Github data to see how strong the correlation is between new languages and their adoption as a function of how large an initial codebase they come with.
[+] [-] fadmmatt|16 years ago|reply
http://matt.might.net/articles/writing-an-interpreter-substi...
Short version:
* A denotational semantics is a function M : Program -> (Value -> Value) that maps a program to a mathematical function.
* An operational semantics is a relation (=>) between consecutive machine states. That is, if state => state' holds, then the machine transitions from state to state'.
* The relation in a "big-step" operational semantics need not be decidable. Big-step relations are usually recursive.
* The relation in a "small-step" operational semantics must be decidable.
* When you implement a transition relation, =>, it's usually implemented as a function. That is, if you have a relation R \subseteq State x State, you can encode this as a "transfer function" f : State -> 2^State.
[+] [-] anonymousDan|16 years ago|reply
* Can you convert a denotational semantics to an operational semantics (and vice versa)? Is there any value in doing this?
[+] [-] silentbicycle|16 years ago|reply
I've wondered if this is one of the things I missed by being self-taught, but I don't think most programmers working in (say) Java or Python could really follow it either.
[+] [-] plinkplonk|16 years ago|reply
I found "Design Concepts in Programming Languages" by Gifford and Turbak (http://www.amazon.com/Design-Concepts-Programming-Languages-...) well written and comprehensive. ( I am self taught too! :-))
[+] [-] proemeth|16 years ago|reply
Topic treated as well in the famous law of leaky abstractions : http://www.joelonsoftware.com/articles/LeakyAbstractions.htm...
[+] [-] gdp|16 years ago|reply
All too often, this is because the programming language designers/implementors don't know what the semantics are.
[+] [-] silentbicycle|16 years ago|reply
Off the top of my head, the only languages I can think of with small, precisely defined formal semantics are Scheme, SML, Joy, and Prolog.
[+] [-] BigZaphod|16 years ago|reply
The real issue is that programmers new to a language are unlikely to even realize there's a semantic boondoggle in a given situation. Had they read all of the documentation, perhaps they would - but that's obviously not what most people do. Adding more pages to the documentation just to collect all semantics in one place wouldn't seem to make it more likely that a new programmer is going to read and properly understand their implications.
I don't think you can solve the problem of inexperience with additional education, but it's a common idea in academic circles.
[+] [-] pook|16 years ago|reply
It would be worthwhile to examine Github data to see how strong the correlation is between new languages and their adoption as a function of how large an initial codebase they come with.
[+] [-] rogermugs|16 years ago|reply
[+] [-] gdp|16 years ago|reply