28-SEP-78 13:53:02-PDT,17821;000000000000
Date: 28 Sep 1978 1:48 pm (Thursday)
From: Horning
Subject: Re: A reminder
To: Deutsch

Subject: DRAFT Mesa -> Lisp Requirements
To: Programming Environment Interest: Bobrow, Deutsch, Horning, Lampson,
Levin, McDaniel, Masinter, Mitchell, Morris, Satterthwaite, Suzuki, Swinehart,
Taft, Teitelman;

DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT

[This is a draft, being circulated now for comment.  Sept 28, 1978]

[We recognize the considerable merits of the Interlisp programming
environment.  This document is intended to point out what we consider to be the
correspondingly major advantages of the Mesa environment.  We feel strongly
that these features should be preserved in any EPE.  To sharpen the discussion,
we have made our remarks quite pointed.  We trust that in most cases our
"challenges" can be met (with varying difficulty); the reason for posing them is
to ensure that they are not overlooked.]
 
[Items drafted by Horning:]

>>Static Checking

ISSUES: One of the major advantages of the Pascal family of languages (of which
Mesa is a member) is the substantial amount of consistency checking that is
possible statically (i.e., independent of program execution).  Examples of this are
syntax checking, which catches many transcription/input errors, and checking
for declaration of all names used in a program, which catches both spelling
errors and misunderstandings of the environment.  However, probably the most
important form of static checking is for type consistency, which is very effective
at catching many forms of errors, including many "logical" errors.

There are several reasons for preferring static to dynamic checking:
	-it occurs sooner, thereby giving quicker feedback;
	-errors are more easily related to their sources;
	-many errors can be detected in a single run, rather than being
		identified one at a time;
	-complete checking is not dependent on executing an exhaustive set of
		test cases (once a program is accepted, one KNOWS that it has
		no lurking bugs of this sort);
	-the overhead of checking can be paid once, rather than repeatedly at
		execution time.

If programs developed in the EPE are to achieve laboratory-wide usage (like
Bravo and Laurel), then their robustness cannot depend on run-time interaction
with their developers.  (Not only is there no debugger in Peoria, there generally
isn't one here, either!)

Many Mesa programmers are willing to accept "long" turnaround times for
program changes.  Perhaps one reason is that they have much more confidence
that their programs will actually work once they are accepted by the Mesa
compiler.

CHALLENGE: How can the LISP system be modified to allow a comparable
amount of static checking?  In particular, can static tests be performed that
ensure freedom from type errors and use of undeclared names?

>>Static Scoping

ISSUES: Mesa and LISP have quite different rules for accessing non-local
("global") variables.  In Mesa, the association between name and variable (or, if
you prefer, access algorithm) is determinable statically, and is a function of the
procedure declaration and its environment.  If this association cannot be fixed, it
is difficult to develop robust procedures to manipulate data structures that
out-live particular procedure activations.  It is completely unacceptable for
accidental re-use of some name in a calling environment to affect a procedure's
access to its non-local data.

Scope rules serve another very useful function.  They provide two sorts of limits:
	-they limit the set of names accessible within the program at any given
		point (the amount of "relevant environment" that the
		programmer need consider), and
	-they limit the range of text within which a name can be accessed,
		and hence the amount of text that need be considered when
		considering a change or searching for a bug involving the
		named entity.

CHALLENGE: How can LISP provide a satisfactory mechanism for statically
associating names and non-local variables?  How can names be suitably
localized?

>>Encapsulation

ISSUES: Even packages that have a large amount of local state should have
narrow interfaces.  Ideally, the user should know (and use) only the published
interface.

In Mesa it is possible to declare items (data, functions, procedures, types, etc.) to
be PRIVATE to a module, and inaccessible outside.  This is invaluable in
building packages, because it ensures that only the PUBLIC interface is used by
clients; assumptions made by the implementation cannot be violated from the
outside through either inadvertance or malice.

Mesa allows a program to create multiple instances of a module, supplying, if
desired, different parameters to each instantiation.  This supports an "object
oriented" style of programming, in which each object is referenced only through
its associated suite of functions and procedures.

CHALLENGE: How can LISP provide an adequate encapsulation facility for
packages?  Can LISP support multiple instances of package prototypes, and
object-oriented programming?

>>Explicit Interfaces

ISSUES: Mesa provides a special type of module (a definitions module)
specifically for the purpose of declaring interfaces.  This makes it possible to
separate the development of implementing and client modules; with few
exceptions, the changes that don't affect the definitions module are invisible to
the client, and those that do require corresponding changes in the client.

Explicit documentation of interfaces, of course, is good programming style, and
mandatory for effective multi-programmer cooperation.  Static checking that
interfaces are adhered to is a bonus.

By separating the definitions module from the implementing module(s), Mesa
makes it convenient to test a module in an environment designed for the
purpose, and have some assurance that it will continue to work properly when
substituted into a larger system with the same interface.

CHALLENGE: How can explicit, enforced interfaces be introduced into LISP?

>>Consistent Version Checking

ISSUE: Programs are developed through many versions.  The problems that result
from inconsistent versions can be extremely subtle, yet it is not always easy to
ensure that a set of components being run together are actually consistent.  This
program is alleviated (but not completely solved) in Mesa by enforcement of the
rule that the components must use the same versions of interfaces (definitions
modules).

CHALLENGE: How can LISP prevent the accidental execution of systems built
from inconsistent versions of components?

>>Efficiency

ISSUE: One of the key principles of Mesa is that the programmer shall have
effective access to the full power of the machine, and that implicit run-time
overheads imposed on all programs shall be kept to a minimum.  It seems clear
that there will always be some experimental programs whose computational
requirements will equal (or exceed) the power of the available hardware, and
hence that it will always be necessary to avoid implicit overheads.

One advantage of a (reasonably) optimizing compiler is that increased efficiency
can be obtained with little or no effect on the program form and semantics by
supplying tighter (or earlier) bindings (e.g., by replacing variables by constants).

CHALLENGE: Is there a LISP subset within which the full power of the machine
is available and implicit overheads such as garbage collection and indirection on
data reference are eliminated?  Can the efficiency of some LISP programs be
made comparable to Mesa by simply accepting earlier bindings?

>>Exportation of Programs from Environment

ISSUE: Programs developed in the EPE must not be restricted to use within the
EPE.  Mesa provides a mechanism (image files) for producing essentially
standalone systems that carry along with them only those parts of the Mesa
world on which they rely.  This is important because users may not be Mesa
programmers and may not be willing to pay the overhead of keeping the Mesa
world in their machine.  (E.g., the typical Laurel user should neither know nor
care that Laurel is written in Mesa.)  Among other things, this means that it
must be possible for the program itself to intercept all error reports, and dispose
of them appropriately.

CHALLENGE: Can LISP programs be packaged for standalone use?  Is it possible
to use systems written in LISP without either knowing anything about LISP or
paying the overhead of the LISP system?  Can LISP programs be made to process
all internal and system error reports?

[Items drafted by Mitchell:]

>>Exception Handling

ISSUE: There are three situations in programs that correspond to exceptions:
	(a) impossible states from which recovery is unlikely (usually an
	indication of a bug),
	(b) low-frequency states from which the program should be able to
	extricate itself (e.g., difficulty in reading a page from a disk), and
	(c) in interactive systems, user-initiated exceptions (e.g., kill this
	procedure call and the two previous and then retry).

In case (a), whatever mechanism is used to inform the programmer (assuming he
is there) of the error must have the feature that it does not destroy any of the
state information that he needs to investigate the bug.  In particular this means
that the execution stack should not automatically be rolled back as part of raising
the error.

In case (b), the errors that a procedure may raise should be part of its interface
specifications (they are not currently in Mesa).  The program that is selected to
handle the exception must be able to receive information (parameters) along with
the exception notification, and it must be able to permanently acquire control in
order to terminate the action.  This will require rolling back the execution state
(note that I am very carefully avoiding the phrase "cutting back the stack" -
that is not what is needed ina multi-process environment).  Such execution
unwinding must be done in such a way that each outstanding activation that is
to be terminated have a chance to handle the fact that it is about to die; this
makes the decisions about what special actions are needed for termination a local
one within the activation being killed.  The order of cutback must also be
reasonable; e.g., in a procedural environment, they must be done in a LIFO
order, sort of like backward execution.

Case (c) raises no issues that (a) and (b) have not already proboked.  It is
included here only for completeness and because an integrated EPE will need to
do this.

CHALLENGE: Can Lisp provide an error-handling mechanism with local
handling of termination and with the state-preserving property for debugging
purposes?

>>Processes and Monitors

ISSUES: Processes and monitors provide a well-engineered way for introducing
parallelism in one's programs.  I doubt that they are the ultimately best way for
doing so, but they represent the state of the art and there is much experience
with using them and with proving properties of programs that use them.

CHALLENGE: What does Lisp have?

>>Coroutines

ISSUES: Some form of coroutines are needed to handle situations such as text
formatting.  The Mesa control structures are built from a common underlying
primitive that allows one to call another program in a uniform manner without
being aware of its control regime.  The called program could be implemented as a
procedure or as a coroutine (there is more than one flavor).  This makes a control
abstraction facility that is useful for object-oriented programming, since the user
of an object can treat all operations as if they are procedures no matter what
their exact implementation is.

>>Records, Parameters, Constructors, and Extractors

ISSUES: Record constructors are most frequently used as parameter records to
procedures in Mesa.  Keyword notation eliminates errors of ordering of two or
more parameters of the same type (e.g., COPY[from: x, to: y, nWords: 256], for
which I could never remember the correct order of "to" and "from" in the
positional notation).  Making records first-class values requires that one be able
to write record-valued expressions.  Programs are clearer when an entire value is
specified at once, rather than by a number of assignment statements.  Also,
writing a constructor enables the compiler to check that one has specified some
value (possibly "don't care") for each component and enables one to have default
values for some componenets.  This also provides a way of having default
parameters for procedures as well.

Procedures need to be able to return multi-part values and not be limited to a
single value returned in order to avoid some uses of "output parameters."  Mesa
extractors then allow the programmer to perform multiple assignments of those
multi-part values to separate variables for further processing.  This is heavily
used in Juniper.

CHALLENGE: Can the Mesa record/parameter facilities be provided in Lisp?

>>Efficient Random Access to Files

>>Debugger Access to Source

ISSUES: One of Mesa's strong points as a system programming language is that
the programmer can debug at the source level.  This requires the ability to
specify and set breakpoints by reference to the source program (either by context
or by pointing).  If the Mesa compiler were to do more global optimization (such
as Fortran H's, for instance), the programmer would still need to be able to
compile his program in a mode permitting the correspondence between source
and object probrams to be maintained.

CHALLENGE: I presume that Lisp has these features normally.  What about the
block compiler?

[Items drafted by Suzuki:]

>>Readable Programs 

ISSUE: It is important that one can express his algorithms clearly so they can be
easily understood by others.  This is a non-trivial aspect of language design. 
Mesa has some features that help people to write clear and understandable
programs.  

Mesa provides the generally accepted control and data structures in forms whose
syntax corresponds well with their semantics.  It follows many accepted
conventions of mathematics and conventional programming languages.  Infix
operators, precedence of operators, and structural keywords all eliminate the need
for many parentheses and reduce the parenthesis matching problems faced by
LISP users.

CHALLENGE: Can LISP get rid of the parentheses and enhance readability of
programs without falling into ambiguity?

>>Precise Syntax 

ISSUE: One advantage of Mesa is that the syntax is rigorously defined so that
when one writes a program it is known a priori whether it is acceptable or not
and how it is parsed and executed.

In CLISP the syntax is tied to the error checking mechanism in order to
implement language extension.  Therefore,  it is not easy to know in advance
whether what one writes is acceptable and even accepted whether it will be
parsed as the programer wishes.  If the program is not accepted or misinterpreted,
then it may be difficult to guess the style of writing which CLISP likes.

CHALLENGE: Can LISP be liberated from error-driven syntax?  Can a precise,
yet reasonably compact, syntax for acceptable programs be given?

>>Enumerated Types

ISSUE: A very useful tool in programming is the ability to create a type whose
elements have programmer-defined names.  One example is a parse tree in a
compiler where each node belongs to one of a finite number of classes like
"assignment" and "addition".  

Mesa enumerated types provide this facility.  They offer the following
advantages:
	-efficient use of storage,
	-usable as array indices and for iteration control,
	-safe when used as array indices (no subrange overflow),
	-compact notation for subsets,
	-combined with Case selection, we can attain an efficient
		implementation of multiple-branch control mechanism.

CHALLENGE: Provide an equivalent facility in LISP.

>>Case Selection

ISSUES: As noted above, Case selection in conjunction with enumerated and
subrange types can lead to efficient multiple branches utilizing the hardware
dispatch control mechanism.

Another feature of Mesa SELECT statements is that one can write relation tails as
selection criteria so that evaluation of the first operands can be saved.

CHALLENGE: Provide an equivalent selection capability in LISP.

>>Control of Storage Structures 

ISSUES: Mesa makes it possible to increase storage utilization (possibly at the
expense of access time) by using the PACKED option.  Fields can be as small as
one bit.

Mesa also enables the precise control of the layout of fields within a record for
dealing with externally-defined structures (e.g., interrupt words).


CHALLENGE: Can LISP provide equivalent density and control where required?
 
>>Constant declaration

ISSUE: Constant declaration is a mechanism to bind a name with a value
throughout the execution of a program, so that no statements can overwrite the
value.  The mechanism is very useful in constructing reliable software, since
this property can be checked locally.  

There are two levels of constant declarations in Mesa.  One is "module constant"
by which a name is bound to a unique constant throughout the life of a
module.  One cannot even overwrite the value.  The other is "local constant" by
which a name is bound to a value, which may be different for each procedure
invocation, but cannot be overwritten.

CHALLENGE: How can LISP ensure the security of name-constant bindings?

DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT - DRAFT