Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!watnot!watcgl!kdmoen
From: kdmoen@watcgl.UUCP
Newsgroups: comp.lang.misc
Subject: Static typing with Dynamic binding
Message-ID: <588@watcgl.UUCP>
Date: Thu, 12-Feb-87 17:50:04 EST
Article-I.D.: watcgl.588
Posted: Thu Feb 12 17:50:04 1987
Date-Received: Fri, 13-Feb-87 05:41:15 EST
References: <364@oracle.tc.fluke.COM> <814@unc.unc.UUCP> <1040@tekchips.TEK.COM>
Reply-To: kdmoen@watcgl.UUCP (Doug Moen)
Distribution: comp.lang.misc
Organization: U. of Waterloo, Ontario
Lines: 99
Summary: They *can* coexist in a programming language

In article <814@unc.unc.UUCP> rentsch@unc.UUCP (Tim Rentsch) writes:
>Side comment:  I detect a hint of confusion between static binding
>and static typing.  At the risk of repeating myself I caution against
>such confusion -- static type checking is perfectly compatible with
>dynamic binding.  This compatibility does not, however, mean that
>statically checked systems can be statically bound.  And, I apologize
>if in fact no confusion indeed exists.  [And, glad to see more people
>realizing the value of inheritance etc as an improvement over (ugh!)
>C.] (End of side comment.)  

In article <1040@tekchips.TEK.COM> willc@tekchips.UUCP (Will Clinger) writes:
>To the contrary, static type checking is incompatible with dynamic
>binding.

Unfortunately, what Tim means by dynamic binding is not what Will means.
(And I maintain that Will is, in any case, wrong).
To clear up the misunderstanding, I will make some definitions:

Lexical Scoping:
   Free variables in a function are inherited from the environment
   in which the function is *defined*.  Examples: Pascal, Scheme.
Dynamic Scoping:
   Free variables in a function are inherited from the environment
   in which the function is *called*.  Examples: Lisp 1.5, Apl.
   Will Clinger (and much of the Lisp community) also refer to this
   as Dynamic Binding.

Dynamic Message Lookup:
   In Smalltalk and other object oriented languages, messages are bound
   to methods at run time, based on the class of the reciever.
   In Common Loops, the classes of all of the arguments of a message
   are taken into account.  This is what Tim Rensch calls dynamic binding.
   In other languages, messages (operation names) are bound to methods
   (procedure bodies) according to the scoping rules.
   
Static Type Checking:
   Type errors are detected at compile time.  Examples: Pascal.
Dynamic Type Checking:
   Type errors are detected at run time.  Examples: Lisp, Smalltalk.

Here is my thesis:
It is possible for a programming language to have any combination
of lexical/dynamic scoping, dynamic message lookup (or not), and
static/dynamic type checking.  In particular, static type checking
does *not* conflict with dynamic scoping.

To see why, I will first have to note that, in general, static type
checking requires type declarations.  There are some statically typed
languages (like ML) in which you can write programs with no type declarations;
these languages will infer the types of every variable and formal parameter.
However, type inference is a tricky problem, and can't be done in every
language.  There are a number of extensions of ML for which type inference
has been shown to be undecidable.

As Will Clinger has already pointed out, it is probably impossible to
infer the types of free variables in a language with dynamic scoping.
This means that in a language with dynamic scoping and static type
checking, a function will have to declare the types of its free variables,
which it 'imports' from the callers environment.  If a function is called
from an environment in which the declared types of its imported variables
do not match the actual types, then a type error is reported by the compiler.

Will Clinger:
>To understand why static type checking is incompatible with dynamic
>binding, let us consider the example of a dynamically bound Lisp in
>which the + operation applies only to objects of type number.  It
>is impossible to perform static type checking on the procedure foo
>defined by
>
>    (define (foo n)
>      (+ x n))
>
>because the compiler has no idea what x is going to be bound to
>dynamically.

In the (fortunately nonexistent) language "dynamically scoped Ada",
this example would be written as:

	FOO: function (N: INTEGER) return INTEGER is
		import X: INTEGER;
	begin
		return X + N;
	end FOO;

In general, every variable mentioned in the body of a function in DSAda
must be a formal parameter, a local variable, or an imported variable,
which is inherited from the calling environment.

Now don't get me wrong, I am not saying that anybody would actually
want to *use* a strongly typed language with purely dynamic scoping,
I'm just saying that it is *possible*.  Frankly, I don't like languages
with pure dynamic scoping.  I had some bad experiences with large APL
programs in my childhood.  

However, a hybrid language with strong typing, default lexical scoping
and optional dynamic scoping is worth investigating.
-- 
Doug Moen (watmath!watcgl!kdmoen)
University of Waterloo Computer Graphics Lab