Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!deccrl!news.crl.dec.com!shlump.nac.dec.com!decuac!haven!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.lang.misc
Subject: RE: Dynamic typing (part 3)
Message-ID: <8APR91.20240323@uc780.umd.edu>
Date: 8 Apr 91 20:24:03 GMT
References: <1593@optima.cs.arizona.edu> <28959@dime.cs.umass.edu>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 67
Nntp-Posting-Host: uc780.umd.edu

Victor Yodaiken writes:

>There seems no reason why we cant have a "static" programming
>language in which type declarations are more flexible than current
>definitions. Thus, if I declare "x,y" to range over numbers, then
>"x+y, x*y " are well defined, but "x/y" is not, because the semantics
>of / depends on more than the numberness of the arguments -- i.e.
>integer/integer -> integer, float/float -> float, integer/integer
>->(q,r) are all different functions.

In general, you need to be able to do more with a computer than add
and multiply :-)

Consider a function Lookup(symbol_table, symbol) -- what should the
type of the result be?  Or consider Set_value(symbol_table, symbol, value) 
what type should "value" be?

Could you imagine a symbolic math package which had to invoke a
compiler at each stage to construct "statically typed code"
appropriate to an expression?  How about developing such a package
in a language where you had to change declarations each time you
wanted to work on a different class of problem?

-----------------------------------

Consider the problem of function-rewriting.  Let's say you have some
function F(g(x), g(y)).  Let's say F and g are both O(n squared), but
that F(g, g) has properties that allow it to be computed in O(n).  In
a language where a significant part of the code is spent declaring how
x and y (and presumably the results of F and g) are stored, how is a
compiler supposed to be able to determine that it is appropriate to
re-write this usage of F?

I tend to think of static typing in the same light as side-effect
driven programming.  Both have "non-local" properties that make
re-writing code difficult.  [If static typing is purely local, then
you are not typing a variable, but a value.  If that "variable" is a
constant, then there may be no significant difference between static
and dynamic typing.]

Function-rewriting involves a number of issues besides dynamic/static
typing, but that's what I've been spending my spare time on...

-----------------------------------

Let me pose a "classic typing problem":

F(x) and f(x) are defined for some domain D -> D, but are not one-to-one
G(x) is an inverse to F(x) for some values in D
g(x) is an inverse to f(x) for some values in D

F, f, G and g are all implemented as user defined functions on some
computer system.  All are pure computation (no side-effects).

What type must x be for G(g(x)) to be meaningful?


An easy way to deal with this problem is issue "message not
understood" where x is invalid.  Note that significant computation (g)
may occur before this situation is recognized.

Sometimes it may be recognized that if x is limited to some sub-domain
d, then G(g(x)) will always be meaningful.  Sometimes the computer
might recognize this, sometimes the programmer might.  Sometimes the
problem is too hard.

Raul Rockwell