Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watcgl!kdmoen
From: kdmoen@watcgl.UUCP
Newsgroups: comp.lang.misc
Subject: Re: Static typing with Dynamic binding
Message-ID: <624@watcgl.UUCP>
Date: Thu, 19-Feb-87 23:59:25 EST
Article-I.D.: watcgl.624
Posted: Thu Feb 19 23:59:25 1987
Date-Received: Fri, 20-Feb-87 05:46:15 EST
References: <364@oracle.tc.fluke.COM> <814@unc.unc.UUCP> <1040@tekchips.TEK.COM> <588@watcgl.UUCP> <1060@tekchips.TEK.COM>
Reply-To: kdmoen@watcgl.UUCP (Doug Moen)
Distribution: comp.lang.misc
Organization: U. of Waterloo, Ontario
Lines: 81

Will Clinger (willc@tekchips.UUCP):
>I would like to thank Doug Moen and others for their precise definitions.
>My example wasn't very good, so a number of people still don't see why
>dynamic scoping is incompatible with static type checking.

It seems my original posting wasn't clear enough.
To rectify this, I am going to define a language called "Dynamically
Scoped Pascal".  It is exactly like standard Pascal, except that
free variables within procedures and functions are bound in the
environment from which they are called, instead of the environment
in which they are defined.  Unlike standard Pascal, procedures and
functions must explicitly declare all of their free variables in an
"imports" clause.

Here is a definition of a dynamically scoped function "FOO"
which inherits a variable X from the environment from which it is called:

    function FOO(N: integer): integer
	imports(X: integer)
	begin
		FOO := X + N;
	end;

Here are the rules for "Dynamically Scoped Pascal":

* Every variable mentioned in the body of a function must be a formal
  parameter, a local variable, or a variable declared in an "imports"
  clause, which is inherited from the calling environment.

* A function can only be called from an environment which defines
  variables whoses names and types match the names and types of
  the variables that the function declares using "import".
  For example, the function FOO may only be called from an environment
  that declares an integer variable called X, otherwise a type error
  will be detected at compile time.

* The set of variables "imported" by a function is part of its type.
  Therefore, if FOO were passed as a function parameter, then the
  corresponding formal parameter would have to be declared like this:
	  function F(N: integer): integer imports (X: integer)
  In other words, procedure and function parameters do not interfere
  with our ability to do static type checking.

Will Clinger:
>Type declarations aren't enough to support static type checking when the
>language is dynamically scoped.  Yes, the compiler can check that all uses
>of X within FOO are consistent with the "import" declaration.  That's easy.
>The problem is that the compiler cannot check statically to make sure that
>FOO will be called only when X is an integer variable in the dynamic
>calling environment.

In "Dynamically Scoped Pascal", it is straightforward for a compiler
to do exactly this.  A function can be called either the main block of
the program, or from another procedure or function.
Suppose FOO is called from a function called BAR.
In the environment of BAR, every variable is either a local variable,
a parameter, or an imported variable.  Each of these variables has a
declaration which can be found within the definition of BAR.
Since "imports (X: integer)" is part of the type of FOO,
the compiler must check that one of the variables
declared within BAR is called X, with type INTEGER.  If no such binding
for X can be found, then a type error is declared.  This can be done
statically.

Note that there really isn't a concept of "global variable" in DSP,
only imported variables.  If you tried to write a real program in DSP,
then you would find that most procedures and functions would end up
with rather long import lists.  But that's okay, because DSP exists
solely to prove that it is possible for a statically typed, dynamically
scoped language to exist.

Will Clinger:
>This is the reason that dynamic scoping is incompatible with static type
>checking.

If anyone still believes this after reading this article, then they
are invited to mail me an example of a DSP program
that cannot be statically type checked.
-- 
Doug Moen (watmath!watcgl!kdmoen)
University of Waterloo Computer Graphics Lab