Conference turris::languages

329.0. "Expressiveness of imperative programming languages." by SUOSWS::RIEDRICH () Fri Mar 06 1992 14:55

Hi folks,

after reading awhile in this conference, I found that a lot of space and time
is devoted to lighting flames about one's own favorite programming language.

As an alternate topic, -and an alternate style of discussion-, I would like to
initiate a comparison of imperative programming languages with respect to
"expressive power": What properties must programming languages have to make
them suitable for people to express their ideas in?

With the term imperative programming languages I mean those languages with
which one specifies the dynamics of systems. Declarative languages don't fit.
If anyone wants to start a fight about imperative vs. declarative, I suggest
starting a new note about that. If anybody wants to state that there are
other languages besides imps and decs, that's yet another note. You get the
idea, stick to the subject.

Other nongoals are discussions about:

  - syntax;
  - mappings of programs onto computers (this is a discussion of languages!);
  - richness of runtime libraries;
  - ease of learning;
  - personal taste.

As an initial contribution, I will present a subjective choice of programming
language features that with one exception have helped me write my programs in 
the past. I would appreciate corrections and extentions.

As a second task, (wizards, speak up!) we could compile a table of 
entries stating to what extent a given language supports a particular feature.
I'll participate as far as knowledge and time allows, if interest in this
topic shows up.

Following the end-of-page is the announced list of language features.

See you, /Thomas

List of programming language features:
--------------------------------------

    -assignment, sequencing, conditionals and iteration    
 
    -function calling
    -programmer-defined functions
    -overloading of names of functions
     
    -free, but nonglobal variables
    -dynamic binding of variables
    -static  binding of variables
      
    -programmer-defined data-types
    -single inheritance
    -multiple inheritance
     
    -object identity
    -object identity for functional objects
    -object identity for threads of function calls
     
    -illusion of infinite memory
     
    -non-local transfer of control, static
    -non-local transfer of control, dynamic
    -protection of dynamic extent
     
    -programmed source code rewrites

Here are short definitions of the above terms, as I understand them:

*assignment, sequencing, conditionals and iteration*: you're lost without them, 
unless you prefer a pure functional style of programming.

*function calling* is featured by almost any imperative language, and most
languages come with a rich set of predefined functions: functions that add
numbers, concatenate strings, shift bit arrays, perform i/o etc. To call a 
function, the programmer must somehow specify which function to call, and what
arguments the function should operate on. In the sequel I will not 
differentiate between functions that return values and functions that perform 
side effects. (functions vs procedures in many languages)

The meaning of *programmer defined functions* is simple. As a programmer, you
give the beast a name, supply names and types of the parameters and then write
the code for the function. When the function is called at runtime, the code
will execute with the parameters bound to the arguments of the function. When
the code for the function is exhausted, the function returns, and the
parameters are unbound. The span of time between function call (binding) and
function return (unbinding) is the dynamic extent of the call. At any given
point T of runtime, the ordered set of all function calls whose dynamic extent
wraps around the spoken of point of time is the thread of calls at time T. The
ordering is given by the times at which the calls occured.
  Actually, the discussion of binding, dynamic extent and threads belongs to
the function calling feature above, but it fits well with the concepts of
parameter and arguments, and that's why I wrote it here.

*overloading* of names of functions relieves the programmer from the bothersome
task of having to invent new names for a whole bunch of functions that do
nearly the same thing. In each function call expression to a function of an 
overloaded name, the compiler will infer from the types and the number of 
arguments which code is actually to be run. Ada is very friendly here.

*free, but nonglobal variables* effectively means that function definitions may
be nested. The expressive power comes when functions defined at inner levels
are passed around as arguments.

*dynamic binding of variables* is the exception. When a dynamically bound 
variable is referred to at runtime, its value will be determined by the last
binding that took place in time. An example for the expressive power that 
this feature offers is the print function in Lisp. That function senses the
values of about a million global variables, but imagine each call to print
coming along with arguments for a million parameters! Instead, the caller
of print does so within dynamic bindings that are appropriate for that specific
call.

*static binding of variables* is the default case. When a statically bound 
variable is referred to at runtime, its value will be determined by the
innermost binding that occured in the program text for that variable. Because
this is the default case, and binding of variables and function calls are
synonyms, this is not really a feature.

*programmer defined data types* means that there is support for the concepts
of the problem domain that the program deals with. A simulation program dealing
with roads, traffic lights and cars is not well expressed in terms of bits
and bytes.

*single inheritance* allows you to express that every x is a y, as long as you
don't express that every x is a z too. Let x be "male human" and y be "human".
Then if you need a function to determine the age of a male human being, and 
you've already got a function that does this for humans, there is no more work
to do. Inheritance facilitates code sharing across objects *and* data types,
while the usual concept of function definition and calling facilitates code
sharing across objects of the same data type only. (Well, roughly)

*multiple inheritance* allows you to express that every x is a y, even if you
also express that every x is a z. Multiple inheritance is a common situation
in the taxonomy of all sciences, so why not let a programming language feature
it?

*object identity* for a data type T is featured if variables can hold objects
of type T, if objects of type T can be dynamically created and if objects of
type T can be compared for identity, that is, "same-ness". The first aspect
implies that objects of type T can be passed as arguments to functions and be
returned from functions. Many programming languages facilitate object identity
through use of "pointers".

*object identity for functional objects* means all of the above for functions.
(Of course, one cannot determine wether two different functions will always 
behave identically as functions.) This feature is *very* expressive in
conjunction with free variables.

*object identity for threads of function calls* allows programmers to state
that a computational process is interruptable (and restartable) at certain
milestones. (To be honest, I have not the slightest idea what this is good
for. But I have a hint: Does anybody have a solution to the samefringe problem
using the scheme primitive call-with-current-continuation? I'd like to read
and understand it.)

*illusion of infinite memory* is actually a misnomer, but it is a promise
that the lifetime of computational objects eventually ends when it can be 
proved that they are no longer needed, thus freeing computational resources.

*non-local transfer of control, static or dynamic* enables the programmer to
force the dynamic extent of a whole swoop of function calls to end
simultaneously. The difference between static or dynamic is one of scope. Most
languages offer static exits through return statements or gotos, among 
others. The language C offers dynamic exits through setjmp/longjmp, I think.

*dynamic extent protection* allows the programmer to hook into the point
of time when the dynamic extent of a function call ends, and to specify
what computations should take place at this time. This is only meaningful
in languages that provide non local exits. (see above) Exception handling
is a rather structured instance of this feature.

*programmed source code rewrites* enables programmers to deal with the 
language at the expression level, writing macros. In doing so, the
programmer specifies transformation rules to be applied to source code at the
time of compilation. One of the phases of the compiler will then be the 
expansions of all the macro calls that appear in the original source. Macros
facilitate readability and embedded languages.

-- end of list --

   Re:                     <<< Note 329.0 by SUOSWS::RIEDRICH >>>

You have presented a list of "technical features" of many, if
not most, imperative languages.  So far, so good.  However,
"expressiveness", for me, goes much farther.  An "expressive"
language should let me describe how I analyze information
processing problems I come across frequently.

An imperative language is going to have to have at least two
parts of speech, verbs and nouns.  The verbs are, at least
partially, determined by the kinds of nouns available.  Here are
some I need.

I use concepts derived from hierarchical and relational
databases, files, command line interfaces (or "shells"),
procedures, mathematical functions, lexical functions, system
status, user entries, mail messages, device characteristics and
many others.  As you can see, I need many nouns.  And clearly, I
will need many verbs.

Today's technology forces me to switch languages between DCL,
SQL, Pascal, C, Cobol, ..., because none of them is expressive
enough outside of its own territory.  So I must be a polyglot.

Bottom line, my judgement is that our current languages, be they
imperative or declarative have such limited vocabularies that
the form of the language is not of great concern.

fwiw,

Dick