2
$\begingroup$

Would it be convenient to express semantics of imperative languages (e.g. C) and object-oriented languages (e.g. Java) with $\lambda$-calculus?

Or in the other words: is $\lambda$-calculus a suitable candidate for expressing semantics of all context-sensitive languages?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Note that there is the whole field of programming language semantics that uses the lambda calculus extensively to express the semantics of programming languages. $\endgroup$
    – Dave Clarke
    Commented Jul 5, 2013 at 13:37
  • 1
    $\begingroup$ What do you mean by "context-sensitive" in this context? $\endgroup$
    – Raphael
    Commented Jul 5, 2013 at 14:43
  • 1
    $\begingroup$ Scheme is an imperative language. (It has set!) The Revised<sup>5</sup> Report and earlier used Scott-Strachey Denotational semantics, which is what I think you want. The semantics of set! is on page 41. (In the 6th rev Scheme switched to an operational semantics.) $\endgroup$
    – Wandering Logic
    Commented Jul 5, 2013 at 18:39
  • 1
    $\begingroup$ @WanderingLogic: Your comment could be an answer. $\endgroup$
    – Dave Clarke
    Commented Jul 5, 2013 at 19:58
  • 1
    $\begingroup$ I think the "context-sensitive" part of the question is misguided. The languages you are interested in are typically Turing complete. Although their grammars are context-sensitive, if you include well-typedness, this fact is simply uninteresting from a semantic perspective. I would simply drop the second part of the question. $\endgroup$
    – Dave Clarke
    Commented Jul 5, 2013 at 20:00

1 Answer 1

Reset to default
5
$\begingroup$

There are two main approaches to giving the semantics of a language that I'm aware of. $\lambda$-calculus is a suitable candidate for expressing semantics in either approach. (Note that my knowledge of programming language semantics is restricted to a single course that I took in the mid-1990s, so I may be missing significant developments from the past 20 years.)

The first approach is operational semantics. According to David Schmidt's Denotational Semantics, Allyn&Bacon, 1986, page 2, operational semantics "uses an interpreter to define a language." In this sense writing a syntax-directed translator or attribute grammar as an extension of your parser gives an operational semantics to the language. Somewhat more abstractly, you might define a small-step operational semantics (like those on the Wikipedia page) where you define the meaning of each syntactic expression with respect to the actions it takes to transform a formally defined state or environment. The imperative programming language Scheme (which is notable for having "first-class" functions and continuations and as being the progenitor of JavaScript) has switched to an operational semantics in their most recent standard.

The other approach is denotational semantics. In denotational semantics you define a domain of program outcomes, and then for every syntactic structure in the program its meaning is a function that maps from an environment (a map from variable names to values) to the outcome domain. Scheme Revision5 and earlier have denotational semantics. The semantics of set! (Scheme's imperative construct) are given towards the end of Page 41.

I would guess that language semantics are largely used to prove the correctness of implementations, and in particular to clarify what optimizations are legal and under what circumstances those optimizations are legal. But my only experience in this domain is with respect to compiler optimizations and the memory semantics of C++11, which does not have a formal semantics.

Improve this answer
$\endgroup$
1

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.