<figure><img src="image_1.png" /></figure>

HAL
open science

# Programming with dummy variables

Bernard Lang

► To cite this version:

Bernard Lang. Programming with dummy variables. [Research Report] IRIA-RR-122, IRIA. 1975, pp.7. hal-04716069

HAL Id: hal-04716069

https://inria.hal.science/hal-04716069v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Programming with dummy
variables.

B. Lang

Rapport de Recherche n° 122

Mai 1975
PROGRAMMING WITH DUMMY VARIABLES

Bernard Lang

Résumé :

Les variables muettes sont couramment utilisées dans la notation mathématique et permettent l'écriture d'expressions concises, expressives et élégantes. Cependant elles sont ignorées par les langages de programmation, si ce n'est pour les définitions de fonction et certaines boucles POUR. Nous montrons pourquoi les langages existant se prêtent mal à l'utilisation des variables muettes. Nous décrivons ensuite un ensemble de primitives permettant de remédier à cette situation. Quelques applications sont données comme exemples.

Abstract :

Dummy variables are frequently used in mathematical notation and allow
the writing of expressions which are at the same time concise, expressive
and elegant. However programming languages make little use of them, except
for function definitions and sometimes FOR loops. We first show why existing
languages are inadequate for a generalized use of dummy variables, and then
describe one set of facilities that would give a language enough power for
it. A few examples illustrate some possible applications.

Communication presented at the International Computing Symposium. Antibes - Juan-les-Pins, June 2 to 5, 1975.
# PROGRAMMING WITH DUMMY VARIABLES

Bernard LANG.

IRIA-LABORIA

Domaine de Voluceau

78150 ROCQUENCOURT.

Dummy variables are frequently used in mathematical notation and allow the writing of expressions which are at the same time concise, expressive and elegant. However programming languages make little use of them, except for function definitions and sometimes FOR loops. We first show why existing languages are inadequate for a generalized use of dummy variables, and then describe one set of facilities that would give a language enough power for it. A few examples illustrate some possible applications.

## INTRODUCTION

Dummy variables are an essential feature of mathematical notation, frequently used in many different contexts :

- function definition : $\lambda(x)(x^2+3x-2)$

- limit : $\lim_{x \to a} f(x)$

- derivative and integral : $\frac{\partial f(x)}{\partial x} \int_a^b f(x) dx$

- quantification : $(\exists)x p(x) \quad (\forall)x p(x)$

- set definition : $\{x | p(x)\}$

- generalized operations : $\sum_{x=a}^{b} u_x \cup_{x \in S} x$

In general, an indentifier "x" occurring in some construct L is said to denote a dummy variable iff the meaning of L is not changed when all occurrences of "x" are replaced by some other identifier not already occurring in L.

We will call *muting expressions* those expressions introducing dummy variables. A muting expression is composed of a *muting operator* (often syntactically distributed over the whole expression), an *muting occurrence* of the dummy variable to specify which identifier denotes it, a *body* in which the dummy variable usually occurs (but does not have to), and zero or more *parameters*.

For example, in the muting expressions $\sum_{x=a}^{b} u_x$ and $\{x | p(x)\}$, we have respectively the muting operators $\sum$ and $|$}, the dummy variable x specified by its first occurrence (which is the muting occurrence) in both expressions, the bodies $u_x$ and $p(x)$ and the parameters a and b for the first expression and no parameter for the second.

It is in fact possible to have a muting expression with several bodies and/or several dummy variables such as the following :

$$ \exists(x, p(x), f(x)) \qquad (1) $$

which has $p(x)$ and $f(x)$ as bodies, and means (for instance) "if there is an x such that the boolean expression $p(x)$ takes value true, then evaluate the expression $f(x)$ for one such x".

Dummy variables also appear in some programming constructs :

- as formal parameters for the definition of functions and procedures (somewhat as in the lambda-calculus [4]).

- as index of the so-called FOR-loop in some languages (Algol 68 [13], Algol W [1], EL1[15]).

In Algol 60 [12], a loop such as

```
for x:= 1 step 2 until 15 do begin ... end;
```

requires that x be declared in the block enclosing the loop. Thus x has a meaning outside the loop and is not a dummy variable.

In Algol 68, even if an integer variable x exists in the external environment of the loop

```
for x from 1 to 15 by 2 do begin ... end;
```

the variable x occurring in the loop is distinct from the one in its external environment. This FOR-loop is a muting expression (or maybe a muting statement) having x as dummy variable (indicated by its occurrence following for), having the loop body "begin ... end" as body, and having the parameters 1, 15 and 2.

The use of dummy variables has been formalized by Church [4] with the abstracting $\lambda$ as only muting operator. Indeed any muting expression may be considered as an operator applied to some functional argument(s), the muting effect being achieved by the $\lambda$ used to define those functions. Example (1) could be rewritten :

$$ \exists(\lambda x. p(x), \lambda x. f(x)) \qquad (2) $$

or even $\exists(\lambda x. p(x), \lambda y. f(y)) \qquad (3)$

where '$\exists$' is now just a function applied to two functional arguments. Although equivalent to (1) this does not reproduce the structure of the problem as we usually perceive it. The bound variable x explicitly links the two bodies in (1) but loses this role in (2) and (3).

It is conceivable even to eliminate completely dummy variables and come up with a formalism such as combinators [5]; still we believe that every step to reduce the role of dummy variables,
although it may simplify the theory, reduces the intuitive meaning of the expressions constructed.

Those considerations on λ-calculus apply also to programming languages for which procedural abstraction is the only widely accepted muting construct. It is clear that we can program without muting expressions anything that can be programmed with them, but we contend, with the backing of mathematical practice, that muting expressions are often more elegant and appropriate than equivalent constructs possible in usual programming languages. This is especially the case when one is constructing by extension from a base language a specialized dialect for a specific class of users, or just building a library oriented toward some specialized applications. It is then often useful to implement some complex functions of standard use in the dialect as muting operators similar to the FOR-loop. The purpose of this paper is to study the problems involved with the definition of new muting operators in a programming language. We will generally ignore syntactic sugaring and represent muting expressions like procedure calls.

We will first show features of existing languages with which one can construct entities similar to muting operators. All those constructs being defective in some respect, we will then present new and more effective primitives to build those operators, and we will actually use them with a few examples.

## 1. MUTING OPERATORS IN EXISTING PROGRAMMING LANGUAGES.

In the few languages that have features permitting the construction of some close equivalent to muting operators, these seem to have been considered more as curiosities than as examples of good programming practice. This is probably due to their inefficiency and their inability to properly express their intended semantics, because the programming primitives used to build them are not quite appropriate.

We will use as example a muting operator called SUM. The syntax chosen for the muting expression is that of an ordinary procedure call. The first actual parameter is the body, the second is the indicative occurrence of the dummy variable, and the last two are the parameters of the muting expression. The result of evaluating the expression is the sum of the partial results obtained by evaluation of the body for all the values of the dummy variable varying between the bounds specified by the two parameters. SUM is the programming equivalent to the mathematical operator Σ for generalized addition.

As for usual subprograms, we have two classes of techniques to build muting operators :

- syntactic techniques : using macros or more elaborate syntax extension facilities.

- semantic techniques : using procedures and various run-time facilities for parameter passing.

### 1.1. Semantic techniques.

In Algol 60 it is possible to build a procedure similar to the operator SUM; it is well known Jensen's device :

```real procedure sum(exp, i, min, max) ;
    value min, max ;
    int min, max, i ; real exp ;
    comment exp and i are called by name ;
    begin real s ;
        s := 0 ;
        for i := min step 1 until max do s := s + exp ;
        sum := s
    end ;
```

This procedure can then be called as if it were the desired muting operator :

```pascal
z := sum(x*x + 3*x - 2, x, 0, 15) ;
```

this statement assigns to z the value

$$ \sum_{x=0}^{15} (x^2 + 3x - 2) . $$

However there are defects in this construct :

a) the 'dummy' variable x must have been declared in the environment of the call. Thus it does not really behave like a dummy variable, which is meaningful only within the muting expression using it. The procedure call is not a true muting expression.

b) as the variable x is declared in some enclosing block, the storage for it has to be kept as long as that block is in existence. However the intended semantics requires only x to exist as a local variable of sum when sum is called. Hence there is some space inefficiency.

c) the variable x is called by name in sum from the external environment. Thus every access to x during the evaluation of sum is extremely time-inefficient, and there is more wasted memory (thunk).

In Algol 68 the situation is similar but better with respect to item c) because it is possible for the 'dummy' variable x to be called by reference rather than by name. In the definition of sum, the 'body' parameter exp is not specified as a real called by name, but as a real procedure. Then, for every call, the implicit proceduring of the expression given as first actual parameter to the procedure sum is in effect equivalent to the call by name of Algol 60. (We refer to the original Algol 68 report, the revised report does not allow implicit proceduring).

In other languages that do not provide passing parameters by name or implicit proceduring, it is necessary to procedure explicitly the expression which is to be the 'body' of the 'muting
PROGRAMMING WITH DUMMY VARIABLES.

expression'. For example in EL1 we would write :

Z←SUM(EXPR(;REAL)( X*X↑3*X-2),X, 0, 15) ;

Then we can even remove objections a) and b) by
declaring X as formal parameter passed by refe-
rence :

Z←SUM(EXPR(X:INTEGER BYREF;REAL)(X*X+3*X-2),0,15);

with a good optimizing compiler, this would pro-
bably be as efficient as any other solution.

Still explicit proceduring is awkward to write,
and is not consistent with the usual mathemati-
cal notations that requires an expression, not a
function, as the body of a muting expression.
Besides, as shown for lambda-expressions in the
introduction, it does not reflect the intended
meaning as well as dummy variables. If syntax
extension facilities are available, it is possi-
ble to use them to hide the explicit proceduring
but this may be inconvenient in some circumstance
because syntax extensions are static (i.e. compi-
le-time) facilities.

1.2. Syntactic techniques

When the necessary semantic facilities are not
available, it is sometimes possible to build
syntactic 'muting operator' based on macros, or
some more sophisticated syntax extension facility.
For example, with obvious notations (parameters
are enclosed in angle-brackets) and assuming a
language in which the evaluation of a block
yields the value of its last statement, we could
define the operator sum as the following macro :

macro sum (<exp>, <i>, <min>, <max>)

is begin real s ; int <i> ;

s := 0;

for <i> := <min> step 1 until <max> do s := s + <exp> ;

S

end

macroend ;

However this solution also has defects :

a) If the program is compiled rather than interpreted, the macro calls are expanded in line and cannot be called like procedures. This has two consequences :

- it is more expensive to store the program code.

- it is not possible to use macro defined operators as run-time objects, as it is done with procedure values in many languages.

b) Most languages do not have syntax extension
facilities and adding them is a significant and
expensive transformation (parsing, syntax libra-
ries).

c) the identifier s declared in the macro body
may conflict with some identifier occurring in
the actual string for the parameters, for example

z := sum(s*s + 3*s - 2, s, 0, 15);

This well known problem is easily solved with a
unique identifier generator for all locals such
as s.

Combinations of the above syntactic and semantic
techniques are not much more successful and al-
ways keep some of the defects of one or both
components.

2. SUGGESTED TECHNIQUES FOR CONSTRUCTING MUTING OPERATORS.

As none of the techniques usually available in
programming languages is totally satisfactory,
one might attempt to define a standard mechanism
to build muting operators about as easily as pro-
cedures. It turns out that the task is not
easy because the usual identification and scoping
rules for identifiers do not cover such a situa-
tion and have no trivial extension that does it.
It is easy to find pathological cases requiring
complex rules to define their semantics, such as
conflicts between the identifiers of :

- a variable local to the muting operator,

- a variable local to some procedure local to
the operator,

- a variable standing as formal for the dummy
variable of the operator,

- the actual dummy variable used in a call of
the operator.

If the language allows dynamic identification of
free variables (instead of, or as well as static
identification [9, 11, 16]) then things become
even more complicated. In addition, it is diffi-
cult to define a mechanism that is general enough
(which does not always mean more costly to imple-
ment) because of our limited experience in this
domain ; in his first trials at such a definition,
this author forgot to provide enough generality
to handle recursion.

So, rather than defining an integrated mechanism
with complicated rules and a limited range, it
seems advisable to start with simple primitives
from which one can construct easily whatever is
desired. As usual the advantage is that, when
the semantics of the primitives are precisely
defined and 'checked' to be consistent, this
work does not have to be repeated for the more
sophisticated constructs built from those primi-
tives.

2.1. The primitives

Some primitives are now presented that provide
hopefully satisfactory means to program muting
operators. Their presentation is deliberately
brief and some more elaborate details may be
found in [9, 14] along with justifications and
PROGRAMMING WITH DUMMY VARIABLES.

other examples of their usefulness than muting
operators. Implementing those primitives is no
more difficult or inefficient than implementing
call by name or dynamic identification which are
presently used by several compilable languages.

The language we want to use has the following
features :

a) It is a block structure language.

b) There are procedure-valued variables, as in Algol 68.

c) There are identifier-valued variables. This
is usual in SNOBOL [7] and possible in Lisp
1.5. [10] (using quoted atoms as identifier
values) or in EL1 (using the data-type
SYMBOL).

The convention for identifier parameter passing
is that the actual argument is not evaluated
(similar to parameter UNEVAL in EL1). For example,
if procedure p takes an identifier argument, the
call p(x) passes to p the identifier value 'x'
instead of the value of x. The evaluation of the
actual parameter may be forced by preceding it
with val.

d) In programming languages using static iden-
tification, like Algol 60 or Algol 68, the free
variables of a procedure are associated with
(the memory location associated with) the varia-
ble identically named in the environment where
the procedure definition is elaborated. Some
other languages, such as APL [8] or SNOBOL, use
dynamic identification, i.e. free variables of
procedures are associated with some memory
location only when the procedures are actually
called. We say that a free variable is *loose*
before it is associated with a memory location,
and tied to the associated location afterwards.
In our language it is possible to create proce-
dure values with some loose variables (which is
not possible in Algol 60 or Algol 68).

e) There is a mechanism called closure to tie
loose variables of procedures. A closure expres-
sion is an expression whose evaluation yields a
procedure value. It has the following format :

close<id-expr> with <expr> in<proc-expr>

The evaluation of the expression <id-expr> must
yield an identifier value ID. The evaluation of
the expression <proc-expr> must yield a proce-
dure value P in which the identifier ID denote
a loose variable. The expression <expr> is eva-
luated like the left-hand side of an assignment
to yield a memory location L. The result of the
evaluation of the closure expression is a proce-
dure value P' identical to P except that the
variable denoted by ID is now tied to the loca-
tion L.

Example :

```
begin real z;
    procedure p, q;
        p := lambda(x,y) begin loose real w;
            w := (x*x + y*y) ** 0.5;
            end;
        q := close "w" with z in p;
        z := 0;
        q(3,4);
        print(z)
    end;
```

The double quotes are used to denote identifier
valued constants. In the procedure assigned to p
the identifier "w" denotes a loose variable. (The
option loose in the declaration prevent w from
being a local or a statically identified global).
We assign to q the same procedure, but with w
tied to the same location as z. Thus, when q is
called, z get assigned the value 5 which is there-
after printed.

f) Implicit proceduring is available.
There is no problem if the language uses dynamic
identification. If static identification is the
rule (at least for variables occurring in impli-
cit procedures) then we need means for keeping
loose the dummy variable. This is achieved by
allowing to specify, for any formal parameter
of type identifier, whether it is a muting para-
meter. For example we can define :

```
p := lambda (x, exp);
    muting identifier x;
    boolean procedure exp;
    begin ... end;
```

Then, in the call "p(z,z*z>x)" the expression
"z*z>x" is abstracted into a procedure, x being
bound in the environment of the call and z being
left loose.

To allow easy but efficient compilation it may
be useful to be able to specify a type associated
with the muting identifier formal.

2.2. Some examples

a) the FOR operator :
The FOR operator is equivalent to the FOR loop
as found in Algol 68 or EL1.
PROGRAMMING WITH DUMMY VARIABLES.

for := lambda(id, min, max, step, exp)
    muting identifier id; procedure exp;
    integer min, max, step; value min, max, step;
begin
    exp := close id with min in exp;
    if step ≥ 0 then while min ≤ max do
        begin exp(); min := min+step end
    else while min ≥ max do
        begin exp(); min := min+step end;
end;

It is then semantically equivalent to write

`for i from 0 to 15 by 2 do begin ... end`

as in Algol 68,

or `for(i, 0, 15, 2, begin ... end)` with the
above operator. The first is expanded in line,
while the second results in a procedure call.

b) the SUM operator :

The semantics of this operator have been described in section 1 of this paper.

sum := lambda(id, min, max, exp)
    muting identifier id; real procedure exp;
    integer min, max; value min, max;
begin real s;
    exp := close id with min in exp;
    s := 0;
    while min ≤ max do begin s := s + exp();
        min := min + 1
    end;

`end;`

c) The LFOR operator :

The LFOR operator is similar to the FOR loop,
but the successive values of the control varia-
ble, i.e. the dummy, are the elements of a linear
list rather than a sequence of integers specified
by bounds and step. An object of mode `list` is
either the list-end marker `nil` or a pointer to a
list element. A list element is a structure com-
posed of various fields including one of mode
`list` and denoted by "next".

lfor := lambda(id, 1, exp)
    muting identifier id; procedure exp;
    list 1; value 1;
begin
    exp := close id with 1 in exp;
    while 1 ≠ nil do begin exp(); 1 := 1.next end
end;

d) the TFOR operator :

The TFOR operator is similar to LFOR but operates
on binary trees rather than linear lists, and
thus has to be recursive. An object of mode `tree`
is either `nil` or a pointer to a node. A node is

a structure including two fields of mode `tree`
denoted by "right" and 'left'.

tfor := lambda(id, t, exp)
    muting identifier id; procedure exp;
    tree t; value t;
begin
    procedure p is close id with t in exp
    while t ≠ nil do begin
        p();
        tfor (val id, t.left, exp);
        t := t. right;
    end;
end;

The reserved word `is` is used to declared identi-
fiers with a constant value. When a formal para-
meter of a procedure is not listed in its value
clause, it is passed by reference rather than by
value (we tried to stay close to Algol 60); this
is the case in `tfor` for the parameters `t` and `exp`.

e) The SUBSET operator :

The SUBSET operator computes the set of those
elements of a given set `s` that satisfy a predic-
te `p`. A `set` is represented by a `list` (it is a
subclass of `list` in Simula 67 [6] terminology)
and thus the operator LFOR can be applied to it.
In addition to the field denoted "next", a list
element for a `set` has a field of mode `element`
denoted by "elem".

subset := lambda(id, s, p)
    muting identifier id; boolean procedure p;
    set s; value s;
begin set result; element e;
    result := nil;
    p := close id with e in p;
    lfor(x, s, begin
        e := x elem;
        if p() then result :=
            new set(e, result);
        end);
    result
end;

The evaluation of the expression `new set` (`e`, `result`) creates a new `set` object pointing to a list element which has the values of `e` and `result` assigned to its "elem" and "next" fields.

The execution of the statement
`t := subset(x, s, x≥a)` results in the assign-
ment to `t` of the value represented by the mathe-
matical expression `{x∈s | x≥a}`.
PROGRAMMING WITH DUMMY VARIABLES.

3. CONCLUSION

Our aim in this paper was to show that dummy variables and muting expressions are elegant programming tools, and that it is actually possible to make them available in a programming language. The primitives exhibited here are quite easy to add (in some form, when not already there) to most high-level programming languages. Algol 60 practically has implicit proceduring through its call by name. A loose variable may be implemented with an indirection, and closure as a store into the indirect word. The only serious constraint is that identifiers have to be known at run-time; this is already realized in many systems.

One must also consider that a primitive such as closure has many other useful applications [14] (see also "partial application" in [3]).

We do not contend that our primitives are the best possible. Block structure is not really necessary and was used for expository purposes. Implicit proceduring could be replaced by calling parameters unevaluated as in EL1, and using environment variables and a function like the enveval described in [2]. It is also possible to eliminate closure and have implicit procedures with parameters corresponding to the dummy variables (though it may not be such a good idea in a language with dynamic identification). What solution should be retained depends on the other features of the language and is a great deal a matter of taste.

Acknowledgements

Thanks are due to J.R. Abrial, F. De Remer, G. Huet and the referees for helpful comments and criticisms.

REFERENCES.

[1] Bauer, H., Becker, S., Graham, S.L., Satterthwaite, E.H., and Sites, R.L., "ALGOL W language description", in *Algol W Reference Manual*, CS 230, Computer Science Dept., Stanford University (February 1972).

[2] Bobrow, D.G., and Wegbreit, B. "A model and stack implementation of multiple environments". *Comm. ACM* 16, 10 (Oct. 1973).

[3] Burstall, R.M., Collins, J.S., and Poplestone, R.J. "Programming in Pop-2" Edinburgh University Press (1971).

[4] Church, A. "The calculus of lambda-conversion" *A.M.S.*, n°6, Princeton (1941).

[5] Curry, H.B. and Feys, R. "Combinatory logic" vol 1, North Holland (1958).

[6] Dahl, O.J., Myhrhaug, B., Nygaard, K. "SIMULA 67 Common base language" Publication S-22, Norwegian Computing Center, Oslo, Norway (oct. 1970).

[7] Griswold, R.E., et al. "The SNOBOL 4 programming language" Prentice-Hall Inc., Englewood Cliffs, New Jersey (1968).

[8] IBM, APL/360 user's manual. GH20-0683.

[9] Lang B., "The binding of variables", Unpublished working paper, (June 1973).

[10] McCarthy, J., et al. "Lisp 1.5 programmer's Manual". The M.I.T. press, Cambridge, Mass. (1962).

[11] Moses, J., "The function of FUNCTION in Lisp" *SIGSAM Bulletin* (July 1970), 13-27.

[12] Naur, P. (Ed.) "Revised report on the algorithmic language Algol 60". *Comm. ACM* 6, 1 (Jan. 1963), 1-17.

[13] van Wijngaarden, A. (Ed.) et al. "Report on the algorithmic language Algol 68", *Num. Math.* 14, 2 (Dec. 1969).

[14] Wegbreit, B. "Procedure closure in EL1". *Computer Journal* 17, 1 (Feb. 1974), 38-44.

[15] Wegbreit, B., et al. "The ECL programmer's manual" Technical report, Center for Research in Computing Technology, Harvard University (Oct. 1971).