Timeline for Difference Between Small and Big-step Operational Semantics
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2017 at 21:24 | comment | added | Gilles 'SO- stop being evil' |
@TimothySwan As long as there are no side effects, no non-determinism and no functions, the denotational semantics of an expression is the value that it evaluates to. Non-determinism is a good way to illustrate the difference between big-step and denotational: the denotation of an expression would be the set of values that it can have: $[\![\mathtt{rand}(1..n)]\!] = \{1,2,\ldots,n\}$, whereas a big-step semantics would have multiple admissible judgements: $\mathtt{rand}(1..n) \Downarrow 1$ and $\mathtt{rand}(1..n) \Downarrow 2$ and ... The 3 was a typo.
|
|
| Sep 21, 2017 at 19:22 | comment | added | Timothy Swan |
So when you said, 'Denotational semantics assigns a “meaning” to each expression.' you didn't mean uniquely identifying expressions themselves, but some sort of evaluation-independent meaning? Can you provide a simple example that shows clearly the difference between big-step and denotational semantics? Also, please explain the 3 in ((2+1)+1)⇓3 I'm guessing 'denotational' is some end-all value, but in what instance would 'big-step' not necessarily map directly to that? Does the difference have something to do with context, like (a + 1) depending on the environment which contains a ?
|
|
| Sep 21, 2017 at 18:58 | comment | added | Gilles 'SO- stop being evil' | @TimothySwan Assuming that you want to define the usual arithmetic evaluation, a denotational semantics would not distinguish C and D. A small-step semantics would define a reduction chain like $((2 + 1) + 1) \to 3 + 1 \to 4$. A big-step semantics would be very similar to a denotational semantics: $((2 + 1) + 1) \Downarrow 3$ vs $[\![((2 + 1) + 1)]\!] = 4$. The $4$ in the big-step semantics is the one in the language syntax whereas the $4$ in the denotational semantics is the one from the metatheory, but the distinction is not visible or important in this simple example. | |
| Sep 21, 2017 at 18:50 | comment | added | Timothy Swan | I'm also learning this, but I have an issue with something you said in your answer that I would like you to clarify. You said "Big-step semantics are kind of in the middle." However, wouldn't small-step actually be the 'middle' model? Consider expressions: A: ((5 + 7) + 3) B: ((5 + 5) + 5) C: ((1 + 2) + 1) D: ((2 + 1) + 1) Denotational would classify even C and D with different values (possibly "C" and "D"), and big-step would classify them both as "4" and both A and B as "15" However, small-step would give you "(12 + 3)" and "(10 + 5)" for A and B, and "(3 + 1)" for C and D. | |
| Dec 19, 2015 at 20:49 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
typo (thanks Anton Trunov)
|
| Jun 20, 2015 at 15:02 | vote | accept | Simon Morgan | ||
| Jun 7, 2015 at 2:13 | history | answered | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |