Definition of language constructs

[Tim Frink]

Hi,

is there a formal definition of the high-level language constructs
"expression" and "statement" or are the definitions different depending
on the programming language? For example, in the ANSI-C standard, these
both terms are defined, thus I was wondering if this definition is
valid for any imperative language or just really for ANSI-C.

For example, the definition for an expression is:
An expression is a sequence of operators and operands that specifies
computation of a value, or that designates an object or a function,
or that generates side effects, or that performs a combination thereof.

Regards,
Tim

 

[Eric Sosman]

Hi,

is there a formal definition of the high-level language constructs
"expression" and "statement" or are the definitions different depending
on the programming language? For example, in the ANSI-C standard, these
both terms are defined, thus I was wondering if this definition is
valid for any imperative language or just really for ANSI-C.

For example, the definition for an expression is:
An expression is a sequence of operators and operands that specifies
computation of a value, or that designates an object or a function,
or that generates side effects, or that performs a combination thereof.

The notions of "expression" and "statement" in different
languages may be similar, but they tend to differ in detail.
For example, C's assignment operator is an operator, hence
part of an expression, and the expression yields a value;
that's why you can write `x = y = 42'. In Fortran, though,
assignment is a kind of statement and not an expression, and
the `=' is just part of the syntax of the statement (at least,
that's how it was in the FORTRAN of my youth; the language has
since adopted lower-case as part of its name, and may have
taken on other baggage as well).

Going the other way, pretty much everything in Lisp is an
"expression," even things that in C would be "statements" or
"declarations." Lisp's `(for)' construct is an expression and
yields a value; C's `for' is a statement and does not yield a
value. (I know you said "imperative language," but I've never
found the definition of "functional language" all that clear-
cut, or convincing.)

PL/I -- it's been a *really* long time since I last saw
PL/I, but my recollection is that assignment was a kind of
statement, and not an operator. SNOBOL is the faintest of
fading memories; it was "imperative" but its expressions were
not much like C's. I never wrote COBOL (although I've debugged
it), but it seems to me there's a MOVE "statement" rather than
an "assignment operator" -- that's just an impression, not
Gospel truth. Languages that distinguish between "functions"
and "procedures" (or "subroutines") tend to call the former in
expressions and the latter in statements. And, of course, there
are languages that produce at least some of their side-effects
with built-in statements like `WRITE (6, 42) A,B,C' rather than
with expressions.

Diversity rules!

 

[Nobody]

(I know you said "imperative language," but I've never
found the definition of "functional language" all that clear-
cut, or convincing.)

That may be because people use the term for languages which have some
functional features but aren't really functional languages, e.g. Lisp.

I've never really had much trouble distinguishing the two. ML, Haskell,
Hope, and Miranda (plus various languages which never really made it out
of the lab) are functional languages, almost anything else isn't.

A useful clue as to whether a language is "really" a functional language
is to look at whether typical code (and/or standard library functions)
performs iteration using recursion or using a distinct iteration primitive
(using a pre-defined iteration function which is implemented using
recursion counts as using recursion).

Another way to look at it is whether it's considered "normal" for a
"function" to use and/or modify global state, i.e. whether "functions" are
(mathematical) functions or procedures. Exceptions such as unsafePerformIO
are allowed, so long as they're the exception rather than the rule.

 

[Nick Keighley]

That may be because people use the term for languages which have some
functional features but aren't really functional languages, e.g. Lisp.

I've never really had much trouble distinguishing the two. ML, Haskell,
Hope, and Miranda (plus various languages which never really made it out
of the lab) are functional languages, almost anything else isn't.

A useful clue as to whether a language is "really" a functional language
is to look at whether typical code (and/or standard library functions)
performs iteration using recursion or using a distinct iteration primitive
(using a pre-defined iteration function which is implemented using
recursion counts as using recursion).

so scheme is a functional language?

 

[Richard Tobin]

A useful clue as to whether a language is "really" a functional language
is to look at whether typical code (and/or standard library functions)
performs iteration using recursion or using a distinct iteration primitive
(using a pre-defined iteration function which is implemented using
recursion counts as using recursion).

This isn't very convincing. Any language where the iteration
construct turns into recursion had better be implemented in such a way
that the recursion gets turned back into iteration by the compiler,
and if such a system didn't bother with the intermediate stage, who
would know the difference?

It might be better to demand a language where iteration can be
natural and efficiently written as recsursion.

-- Richard

 

[Chris Dollin]

is there a formal definition of the high-level language constructs
"expression" and "statement"
No.

or are the definitions different depending on the programming language?

Yes.

An /informal/ definition is that statements are there to change things
(but not (necessarily)) to compute values), and expressions are there
to compute values (but (typically) not to change things).

To my mind, given that in a typical imperative language expressions can
and do make state changes, the syntactic distinction between statements
and expressions is pretty much useless, and what use it does have can
be subsumed under type-checking rules rather than grammar. But then, I
would say that, given that I've built languages for which that's true.

--
"Is there a reason this is written in iambic pentameter?" Marten,
/Questionable Content/

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

 

[Richard Tobin]

so scheme is a functional language?

Of course. It's just not *only* a functional language.

-- Richard

 

[Stefan Ram]

Yes.

I agree.

An /informal/ definition is that statements are there to change things
(but not (necessarily)) to compute values), and expressions are there
to compute values (but (typically) not to change things).

The execution of the empty statement »;« does not have an
effect; the execution of the fundamental expression
statement »e;« does have an effect if and only if the
evaluation of its expression »e« does have an effect, so
effects of (the evaluation of an )expression are essential
in imperative languages. Therefore, we can not deny that the
fact that the evaluation of an expression might have an
effect is an essential part of imperative languages.

Effects of the evaluation of expressions were sometimes
called »side effects«, but usually they are important or
are the main purpose, so that this term is inappropriate.

~~

Expressions are not »executed« but »evaluated«, while
statements are not »evaluated« but »executed«, so each of
the two does have a specific verb for its run-time treatment.

The evaluation of an expression might have an effect and
might produce a value for the expression. The execution of a
statement might have an effect, but it never produces a
value.

expression statement
value possible not possible
effect possible possible

Every expression has to be part of either another expression
or a statement, it can not be used directly within the main
block of a function definition.

A statement can be used directly within the main block of
a function definition.

While I have used C terminology, here, this is similar in
other imperative languages.

Between statements in a block, there are sequence points,
while there usually are no sequence points between
subexpressions of an expression. So a statement can be seen
as an operation that is to happen in a chronological
sequence between other operations, while an expression gives
an operation or a value with less emphasis on a certain
chronological sequence.

Complex expressions might give a data flow abstracting the
temporal sequence, for example, in »f(g(),h())«, we do not
have care whether »g()« or »h()« is evaluated first. While
in »x=g();y=h();f(x,y);« this sequence is specified.

 

[Chris Dollin]

I agree.


The execution of the empty statement »;« does not have an
effect;

Typically. Even so, that's a natural degenerate case of statements
being there for -- having the purpose of -- changing things; the
minimal statement is the one that does nothing.

the execution of the fundamental expression
statement »e;« does have an effect if and only if the
evaluation of its expression »e« does have an effect,

Which is only the case if expressions /can/ have effects. It's
not necessary for an imperative language to allow expressions
to have effects.

Effects of the evaluation of expressions were sometimes
called »side effects«, but usually they are important or
are the main purpose, so that this term is inappropriate.

If you take the view -- as I was -- that expressions are there
/to compute values/, then /anything/ else they do is a side-whatever,
/regardless of how important it is to the program/. "Importance"
isn't (typically) part of programming-language semantics.

Expressions are not »executed« but »evaluated«, while
statements are not »evaluated« but »executed«, so each of
the two does have a specific verb for its run-time treatment.

You can make that distinction if you find it useful; it is
a faithful mirror of the informal distinction I drew above.
In general, execution involves evaluation, and evaluation
involves execution; they are intertwined.

The evaluation of an expression might have an effect and
might produce a value for the expression. The execution of a
statement might have an effect, but it never produces a
value.

That's not a necessary restriction; statements might well
produce values. (No-one is making the mistake of thinking
we're restricting ourselves to C in this discussion, right?)
Unless you're just going to call any value-producing statement
an expression?

expression statement
value possible not possible
effect possible possible

Every expression has to be part of either another expression
or a statement, it can not be used directly within the main
block of a function definition.

That depends on the language. Consider

let add( x, y ) = x + y

The expression `x + y` is not part of any expression or statement.
(The BCPL `let` is a /declaration/, not a statement.)

In Algol68, if I remember correctly, the distinction between
"statement" and "expression" reduces to whether the construct
has type void or not.

While I have used C terminology, here, this is similar in
other imperative languages.

In /some/ other imperative languages.

Between statements in a block, there are sequence points,
while there usually are no sequence points between
subexpressions of an expression.

Sequence points are a /particular/ way of expressing execution
orderings, but letting that aside, some languages are much more
specific than C about evaluation order. I'm not sure "usually"
is the right adverb. There /may well be/ -- as there are in Java --
constraints equivalent to putting a sequence point after the
evaluation of each operand of a normal (non-|| etc) binary
operator.

So a statement can be seen
as an operation that is to happen in a chronological
sequence between other operations, while an expression gives
an operation or a value with less emphasis on a certain
chronological sequence.

Chronology only matters because of effects, consistent with
my informal distinction above.

Complex expressions might give a data flow abstracting the
temporal sequence, for example, in »f(g(),h())«, we do not

/might/ not.

have care whether »g()« or »h()« is evaluated first.
While in »x=g();y=h();f(x,y);« this sequence is specified.

--
"He was thinking about an immortal man who flew - James Blish
from star to star faster than light." /They Shall Have Stars/

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

 

[Stefan Ram]

In /some/ other imperative languages.

Thank you, I should have written:

»This is similar in other imperative languages
that I am aware of.«
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
~~

The role model for expression might have been terms and
formulas of mathematics (thus the name of the programming
language »FORTRAN«), while the role model for statements
might have been machine instructions (as in assembler
languages). Higher languages sometimes are an attempt to
integrate (combine) both. But in the process of integration
some properties of mathematical terms got lost. Pure
functional languages attempt to bring them back.

~~

Another field that might apply is linguistics, which might
allow to say that, sometimes, expressions are like (noun)
phrases, while statements are like complete sentences.

~~

The property of an expression to have both a value and an
effect is akin to properties of human servants (persons
assisting in the performance of obligations, vicarious
agents, auxiliary persons): You tell them what you want them
to do and they usually will:

- do something (have an effect)

- report back to you what they have done or observed
(have a value/answer)

 

[David Thompson]

The notions of "expression" and "statement" in different
languages may be similar, but they tend to differ in detail.

Yes. And like the rest of HLL definitions they aren't (mathematically)
formal. The only major ones I know to try were a68 and PL/I.

For example, C's assignment operator is an operator, hence
part of an expression, and the expression yields a value;
that's why you can write `x = y = 42'. In Fortran, though,
assignment is a kind of statement and not an expression, and
the `=' is just part of the syntax of the statement (at least,
that's how it was in the FORTRAN of my youth; the language has
since adopted lower-case as part of its name, and may have
taken on other baggage as well).

Yes. Fortran has taken on baggage quite a bit more significant than
lowercase (in program source and data as well as its name) but
assignment is still a statement, and nonvalued. As a result, for
structure types (which Ftn a bit confusingly calls 'derived', and are
now OOPly) assignment can be user-overloaded, like operator= in C++,
but by a SUBROUTINE, i.e. nonvalued, whereas computational operators
on such types can be overloaded as valued FUNCTIONs.

Going the other way, pretty much everything in Lisp is an
"expression," even things that in C would be "statements" or
"declarations." Lisp's `(for)' construct is an expression and
yields a value; C's `for' is a statement and does not yield a
value. (I know you said "imperative language," but I've never
found the definition of "functional language" all that clear-
cut, or convincing.)

Yes. As already said, LISP isn't pure functional, so of course it
blurs the distinction, but IMO doesn't make the concept useless.
As already noted, a68 makes it an operator and [sub]expression.
(I think BCPL didn't; I don't know if B did before C.)

PL/I -- it's been a *really* long time since I last saw
PL/I, but my recollection is that assignment was a kind of
statement, and not an operator. SNOBOL is the faintest of
fading memories; it was "imperative" but its expressions were
not much like C's. I never wrote COBOL (although I've debugged
it), but it seems to me there's a MOVE "statement" rather than
an "assignment operator" -- that's just an impression, not

PL/I yes; SNOBOL IDK; COBOL has (or had when I used it) both a MOVE
statement and several specific statements like ADD ... GIVING, and a
COMPUTE statement using = at top level but not allowing it nested for
assignment; the same token is also used for equality-test in contexts
where that is allowed (which as far as I can remember are disjoint so
it's never ambiguous).

Gospel truth. Languages that distinguish between "functions"
and "procedures" (or "subroutines") tend to call the former in
expressions and the latter in statements. And, of course, there
are languages that produce at least some of their side-effects
with built-in statements like `WRITE (6, 42) A,B,C' rather than
with expressions.

And builtin procedures like (Pascal) WRITELN (A, B, C);

Although this is only in the language as you see it. Under the cover
nontrivial 'builtin' statements like WRITE, READ, OPEN, STOP, SORT are
usually compiled into calls to 'runtime support' routines, while
'function' calls like ABS() LOG() MIN() are compiled to direct code
and 'functions' like BOUND() UNSPEC() disappear entirely.

And, IME noticed less often, when you get to the bottom (or center?)
of the expression structure to 'primary' or 'primitive' or 'element'
or 'term', the details differ there also.