Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!otter.hpl.hp.com!otter!sfk
From: sfk@otter.hpl.hp.com (Steve Knight)
Newsgroups: comp.lang.misc
Subject: Re: Re: Algol68 (and standards diatribe)
Message-ID: <2400046@otter.hpl.hp.com>
Date: 1 May 91 10:16:07 GMT
References: <1991Mar28.011025.16337@ico.isc.com>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 58

I wrote in an earlier message (amongst other topics) about the omission of
full lexical binding from Algol 68, comparing the Algol68 policy with that of
languages such as Lisp and Standard ML.

Charles comments:
> Yes, but all these languages pay a high run-time overhead for the facility.

I'd like to understand this claim.  

From my perspective, as a programmer in
1991, the implementation of lexical binding only involves a cost in two 
circumstances.  Firstly, when a procedure is returned as a result that 
captures a variable declared in a wider lexical scope than the procedure.
Since this is the situation that Algol68 outlaws, the Bauer Criterion (see
below) would allow any extra costs.  So this first case is not relevant.

The second situation is relevant.  In the case where a procedure is not
returned as a result but the compiler is unable to deduce this (without
inter-procedural reasoning) there is an associated cost.  An example would
typically be uses of "maplist" which maps a procedure of type A -> B across a
list of type list(A) to produce a result of type list(B).  When "maplist"
is used, the compiler may not know enough about maplist to 'realise' that the
lexical variables captured by the procedure can be implemented cheaply.

Although it is true that this second situation fails the Bauer Criterion, it
is not a disasterous failure.  It is not an especially common situation in
typical Algol programming (although it is in purely functional programming)
and there exist several obvious and effective heuristics for eliminating
the overhead in common cases.

This does not imply "high runtime overhead" to me.  But perhaps this is because
my perspective is different from that in 1968 (or whenever).  I would 
genuinely appreciate clarification.

> A lot of time was spent
> investigating implementation problems, but we wanted to adhere to the Bauer
> Criterion (that people who did not use a facility should not pay for it) and
> we kept coming across obscure problems which prevented this from being met.

Generally speaking the Bauer Criterion (as described above) is a good touch-
stone for the addition of features to a language.  I've frequently applied it
in the Pop11 standardisation work.  However, it does need to be taken as part
of a set of general principles, such as orthogonality and ease of learning,
and occasionally compromised.  (I appreciate this comment does not contradict
the original posting.)  Lexical scoping is one issue which demonstrates 
such a compromise.  We don't know how to resolve the efficiency criteria with
those of orthogonal language design.  Since we only have to relax the 
efficiency criteria very slightly, this is probably the best solution.

I am also struck by the different solutions adopted by Pascal and Algol68 on
this issue.  (Doubtless my colleagues will award me a second fruit-basket-on-
the-head for what follows.)  Pascal solved this conflict by forbidding 
procedural return values -- a restriction that is easy to understand.  The
Algol68 restriction, I believe, although more relaxed is harder to teach.
This is an example, in my view, of how Pascal is a more satisfactory 
language in terms of teaching and popularisation.

Steve