# Is lambda calculus suitable for expressing semantics of non-functional languages?

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?

## migrated from cstheory.stackexchange.comJul 5 '13 at 12:22

This question came from our site for theoretical computer scientists and researchers in related fields.

• Note that there is the whole field of programming language semantics that uses the lambda calculus extensively to express the semantics of programming languages. – Dave Clarke Jul 5 '13 at 13:37
• What do you mean by "context-sensitive" in this context? – Raphael Jul 5 '13 at 14:43
• 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.) – Wandering Logic Jul 5 '13 at 18:39
• @WanderingLogic: Your comment could be an answer. – Dave Clarke Jul 5 '13 at 19:58
• 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. – Dave Clarke Jul 5 '13 at 20:00

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 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.