Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!uwvax!daffy!saavik.cs.wisc.edu!quale
From: quale@saavik.cs.wisc.edu (Douglas E. Quale)
Newsgroups: comp.lang.misc
Subject: Re: Run-time Type Errors in Smalltalk (LONG)
Message-ID: <1991May22.161814.15196@daffy.cs.wisc.edu>
Date: 22 May 91 16:18:14 GMT
References: <1991May17.011209.29486@tkou02.enet.dec.com> <1991May17.051840.26916@daffy.cs.wisc.edu> <1991May21.155753.8615@watson.ibm.com>
Sender: news@daffy.cs.wisc.edu (The News)
Organization: University of Wisconsin -- Madison
Lines: 109

>|> >In article <1991May16.153308.4054@spool.cs.wisc.edu> quale@picard.cs.wisc.edu (Douglas E. Quale) writes:
>|> >
>|> >>Dynamically typed languages are safer than primitive statically typed
>|> >>languages such as C.
>|> >

I just realized that perhaps my use of the word primitive was taken as a
perjorative aimed at all statically typed languages, rather than only
statically typed languages with particularly poor type systems such as C as
I had intended.

About a year ago, I wrote a short nqueens function in Scheme

(define (nqueens n)
  (letrec ((try-col (lambda (c b)
		      (if (= c 0)
			  b
			  (try-row n c b))))
	   (try-row (lambda (r c b)
		      (cond ((= r 0) '())
			    ((safe? r b) (append (try-col (- c 1) (cons r b))
						 (try-row (- r 1) c b)))
			    (else (try-row (- r 1) c b)))))
	   (safe? (lambda (r b)
		    (let loop ((up (+ r 1))
			       (dn (- r 1))
			       (bd b))
			   (or (null? bd)
			       (and (not (= (car bd) r))
				    (not (= (car bd) up))
				    (not (= (car bd) dn))
				    (loop (+ up 1) (- dn 1) (cdr bd))))))))
	(try-col n '())))

A simple test,

> (nqueens 4)
(2 4 1 3 3 1 4 2)

and I see I made a type error.  Looking at the source it was trivial to
fix, but it occurred to me that the SML compiler would have rejected the
program immediately.  This shows that some programmers (namely me) can make
elementary type errors even in very, very simple programs.  Unfortunately
it's so trivial it doesn't show much else.

I looked up the CACM reference given re: type errors in statically vs
dynamically typed languages.  Unfortunately the experiment really dealt
only with an untyped language.  The only untyped languaged that I've used
is assembly language.  Bliss and BCPL are still in use, but in general I
wouldn't think that untyped languages have much to recommend them.  I still
have to treat the assertion that "programs in dynamically typed languages
have more type errors than those in statically typed languages" as having
no objective evidence either way.  (Remember, statically typed languages
give many more chances to make type errors.  Some programs with type errors
in a statically typed language cannot have type errors in a dynamically
typed language.)

Static typing brings up the problem of type equivalence:  should the
language use name equivalence or should it use structural equivalence?
This question got a lot of attention in Pascal, but I don't know that the C
community has given it thought.  C uses structural equivalence which can be
less than helpful, especially when a large program typedefs dozens of
different things to int.  As an example from X Windows again, Xlib typedefs
XID as unsigned long.  Window ids are XIDs, so the call

	XDestroyWindow(display, 2 + 2);

is accepted by the compiler even though this is really a type error.
Although this is rather unlikely, pixels in Xlib are also unsigned longs so

	XDestroyWindow(display, pixel);

is another type error that can't be caught.  In order to catch these errors
using structural equivalence XID would have to become a struct, and that is
a somewhat unpleasant arrangement.  In SML we could simply write

datatype Window = Win of int

fun XDestroyWindow (Display dpy) (Win win) = ....

and in fact although Window is a structure, the compiler doesn't need to
tag it so it gives the same efficiency as an int but is much safer.  You
can also greatly increase type safety --

datatype voltage = Volt of real
datatype current = Amp of real
datatype resistance = Ohm of real

fun ohms_law (Amp i) (Ohm r) = (Volt i * r)

(Pattern matching is great -- inside the function ohms_law we can treat i
and r as reals and use ordinary multiplication.  To the outside world they
look like structures.)

This is a big win for sophisticated static typing.  Dynamic typing can do
this, but it's slow and painful.  The types would have to be explicitly
tagged, untagging them before performing arithmetic etc.

Static + dynamic typing in the same language might overcome any problem.
Suppose however, that only static typing is supported.  How does Ada or SML
handle the resource problem in the X Toolkit?  It must be possible for a
widget writer to add arbitrary types to his widgets, and not have to
recompile libXt.a, the X Toolkit library.  The C implementation simply uses
unchecked dynamic typing.  This is much worse than using a language that
supports dynamic typing because no type checks are performed even at run
time.  Is there a better way?

-- Doug Quale
quale@saavik.cs.wisc.edu