14
$\begingroup$

There are many popular languages. But, computer scientists tell us that in order to understand the behaviour of programs in those languages definitely and unambiguously argue upon program behavior (e.g. prove their identity), we need to translate them into another, well understood language. They call such language "a semantics". Authors propose one of many semantics. They explain the meaning of their constructions and how you can translate your language into their. Once you do that, everybody will understand your program certainly, they say.

Looks good, yet, I do not understand something. Do they tell us that they introduce another language to understand the first one? Why do we understand it better than the original one? Why this semantics is better than that? Why not to learn semantics of C right away instead of inventing another language, for describing semantics of C? The same applies to the syntax. Why don't I ask the same question regarding the syntax?

PS In the comments I hear that semantics does not mean another language or translation into it. But Formal Semantics for VHDL says that if you understand something in only one way then you do not understand it and "meaning of meaning" can be specified if we supply a language with a mechanism that translates it into another (known) language. That is, "semantics is a Relation between formal systems". Hennessy, in Semantics of Programming Languages, says that semantics allows for formal processing of the program "meaning", when semantics is supplied as BNF or Syntax Diagram. What is a formal system if not a language?

PS2 Can I say that HW synthesis of given HDL program into interconnection of gates, is a process of semantics extraction? We translate (high-level) description into the (low-level) language that we understand, afterwards.

Improve this question
$\endgroup$
8
  • $\begingroup$ What kind of diagrams do you mean? I work with semantics, but virtually never use diagrams. $\endgroup$
    – Dave Clarke
    Nov 6, 2012 at 17:08
  • 1
    $\begingroup$ I would not call semantics a "language". Semantics define meaning of languages. For example, the syntax of binary numbers it $\{0,1\}^+$. Only with the semantics $\operatorname{value}(w) = \sum_{i=1}^{|w|} w_i 2^{n-i+1}$ do we get actual numbers; note that this is not the only possible semantics, there are also BCD, 2-complement and many more. $\endgroup$
    – Raphael
    Nov 6, 2012 at 20:44
  • $\begingroup$ @Dave Excuse me, I created my question under impression of Assignment Decision Diagrams. I also just Formal Semantics for VHDL, a book where authors propose different semantics, lots of diagrams in each. I was thinking that this is a language we map to. $\endgroup$
    – Val
    Nov 7, 2012 at 10:30
  • $\begingroup$ This sounds a lot less like semantics, and more like an intermediate step on the way to compilation to hardware. $\endgroup$
    – Dave Clarke
    Nov 7, 2012 at 10:34
  • $\begingroup$ Yes, but they extract the "meaning" from the description. $\endgroup$
    – Val
    Nov 7, 2012 at 10:36

1 Answer 1

Reset to default
15
$\begingroup$

Why not to learn semantics of C right away instead of inventing another language, for describing semantics of C?

Because in order to define the semantics of C you need some kind of language, for example English. English can be ambiguous, and especially is the C99 semantics.

The computer science notion of semantics is generally a mathematical description of a program, and this description is not exactly a translation. There are several kind of semantics, that can be about different things:

  1. about which mathematical function the program computes (denotational semantics), $$ ⟦ \verb!lambda x: x + x !⟧ = (x \mapsto 2x)$$
  2. about properties that shall hold before and after the program (axiomatic semantics), $$ \{\verb.a. > 0\} \quad \verb! x = a; y = 0; while(1 < x){ x = x/2; y++; } ! \quad \{\verb.y. = \lfloor\log(\verb.a.)\rfloor\} $$
  3. about how the program will reduce (operational semantics). $$ (σ, \verb! while(x){x--;y++;}!) ⇒ σ' $$ where $σ, σ'$ represents your memory before and after. In this case $σ=(x↦a,y↦b)$ and $σ'=(x↦a+b,y↦0)$ if $x$ and $y$ are the memory cells for $\verb.x.$ and $\verb.y.$, and if $a∈ℕ$.

A little sadly for now, universally understanding a program through its semantics is neither easy nor the intention of it all. It is not the former because, well, those math can be messy. It is not the latter because semantics provide indeed provide a common and unambiguous description, but it is not used to understand a program.

If reading the semantics is not that much meaningful, reading and agreeing on the semantics on the basic elements of the language is very important, for example to explain unambiguously how C's $\verb.continue.$ primitive works.

In conclusion:

Do they tell us that they introduce another language to understand the first one?

Technically no, the language is math. Also it is basically the same for all programming languages, so even introducing a new language, if it is the same for all, would be pretty much OK.

Why do we understand it better than the original one?

Because it is math so it may be harder to understand, but it is way more precise and complete.

The same applies to the syntax.

There are works on verified parsers, but the question of what would mean a semantics of a parser is not trivial.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ "math [...] is way more precise and complete." -- which of course begs the question for formal syntax and semantics of mathematics itself. ;) $\endgroup$
    – Raphael
    Nov 6, 2012 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.