Newsgroups: comp.lang.misc
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!decwrl!stanford.edu!neon.Stanford.EDU!brm
From: brm@neon.Stanford.EDU (Brian R. Murphy)
Subject: Re: Dynamic typing (part 3)
Message-ID: <1991Apr22.234707.7023@neon.Stanford.EDU>
Keywords: type inference static dynamic lisp ml
Sender: brm@cs.stanford.edu
Organization: Computer Science Department, Stanford University, Ca , USA
References: <boehm.670539603@siria> <1991Apr9.021700.2688@neon.Stanford.EDU> <3092@opal.cs.tu-berlin.de>
Date: Mon, 22 Apr 1991 23:47:07 GMT
Lines: 169

In article <3092@opal.cs.tu-berlin.de> wg@opal.cs.tu-berlin.de writes:
>[LANGUAGE WARNING: You might going to see a lot of spelling errors,
> notion errors, style errors, etc.]  
>
>brm@neon.Stanford.EDU (Brian R. Murphy) writes:
>
> >My complaint about statically typed languages is that I _can't_ do
> >some things in them that I _do_ in dynamically typed languages (such
> >as Lisp).  For example, I can't I write a function which returns
> >either a boolean or an integer in a complex way.  I can't write my own
> >Y combinator.  I can't write a function which allows either a sequence
> >of functions which range over numbers or a sequence of numbers as an
> >argument.
>
>Your examples are quite abstract. Maybe its missing phantasy 
>-- but i cannot imagine the use of a function which returns
>either a boolean or an integer unless there is some relationship
>between this values, e.g. the boolean is an error value and 
>normally an integer is expected, in which case either subsorting 
>(multiple supersorts, of course) or parameterization is sufficient. 

I fail to see how parameterization is relevant.  But yes, the case of
of a possible error value _is_ a more common case of my example.  For
example, a Lisp expression such as
	(if (= y 0) (error) (/ x y))
would have type [something like] (error + int).  So either we must
automatically include errors in every base type, introduce an explicit
union declaration in just about every function, or complicate things a
bit by going to a continuation-passing semantics.  Other examples
besides errors _do_ come up, though, so why not just adopt a more
general solution?

>And i see no need to write your own Y combinator, unless you use a
>language for a ground course in lambda calculus. (BTW, you can
>model it in strongly typed functional languages using recursive
>data types; of course a bit cumbersome).

Almost any sort of `meta-interpreter/compiler' (a la Abelson &
Sussman) which constructs functions in a generalized way contains
expressions with recursive function types.  The Y combinator was just
a particularly simple example.  Such translators are very convenient
to be able to write.

>I do not see the difference between primitive functions, in which 
>case you regard type safety as essential, and user defined onces.

Well, to facilitate debugging, the primitive functions have to behave
in some defined way on _every_ input, preferably some sort of error
signal/report to the user.  No static type system I know of can
eliminate all run-time errors (cf divide by 0, array index out of
bounds, disk full, out of memory, etc), so there must be a run-time
mechanism.

Similarly, there must be some mechanism for a user-defined partial
function to signal an error when given bad arguments.  The language
designer cannot possibly anticipate which domains a user-defined
function should be defined on, so the user must be given a way to
_explicitly_ signal an error (for example, if that sorted input array
turns out not to be sorted).  Providing strong static typing is merely
a partial solution; no type system/language can describe all function
domains (sorted arrays, for example).  An error-signalling mechanism
must be there anyway.

In a dynamically-typed language, the user has no static typing
`crutch' to lean on: if he wants to signal errors on bad arguments, he
can code his own test to discover these arguments; if not (perhaps on
quick-and-dirty throwaway code), he can omit them.  Presumably
user-defined functions intended for reuse and use by others would
signal an error on bad arguments.  Type declarations cover certain
cases, making it easy for programmers in statically-typed languages to
believe more precise argument validity checks (is that array sorted?)
aren't needed.  

[To be honest, I wouldn't really check an array for sortedness in most
cases, but just specify what happens if it's not, but hopefully you
get the idea.]

> >				   [Thus] I want a type system which
> >  (a) allows me to omit many type declarations (where unnecessary)
> >  (b) allows me to be very specific in constraining some arguments
>
>Yes, i'am too.
>
> >With dynamic typing, I can simply write predicates to constrain
> >arguments/variables (Common Lisp, FL, some implementations of Scheme
> >do this).
>
>... but i regard it as an abuse of notion to call such dynamic 
>calculated predicates types. You can model them just using conditionals 
>and an error halt function. What Common Lisp gives you here is simply
>syntactic sugar in an essential untyped environment, and some
>(rather restricted) kind of partial evaluation of this
>predicates.

Actually, what Common Lisp gives you isn't adequate at all.  It allows
primitives to behave in an undefined way on arguments out of their
specified domain.  Perhaps I'm biased, but having been exposed to CLU
and FL, which both have completely specified primitive functions (with
specific errors signalled on bad arguments or other error conditions),
I really don't like a language with incompletely determined behavior.
Your program may work one minute, but not the next, or on a different
machine, and there will be no way to tell why...

> >You static typing advocates claim that a static type system can do
> >this for me, but I claim that it can't.  A type language powerful
> >enough to constrain arguments anywhere near as precisely as I need
> >won't allow me to omit many types.  
> 
>My experience is the other way around. It would allow me to omit
>many types, and in some rare cases, if have to add declarations.

Perhaps you don't demand as powerful a type language as I do...
(arbitrary type union, intersection, dependent types, higher-order
functions)

>However, unless I'am going to hack a one-night program, i would
>always declare signatures at least for the exported functions
>of a module even if they could be inferred. This seems to me
>a reasonable kind of documentation.

So would I.  But, as I keep saying, any type language which allows
internal declarations to be inferred won't allow me to specify the
interfaces with the precision I need...

> >Type inference is only possible
> >for a limited class of type languages, and they tend to be fairly
> >weak. In addition, certain programs are forbidden simply because they
> >utilize types which can't be described by the type language used.  
>
>This is theoretically right. But the question is, how often 
>instances outside this limited, weak class are required in
>practice? For example, tell me an instance of practical evidence
>for the need of self application!

I can't come up with a quick example of self-application.
However, I have written Lisp programs for which no type inference
system could ever figure out what arguments certain functions would be
applied to---for example, a lookup table of functions, each constrained
in a complex way by program control to only be applied to correct
arguments.  Sure, I could build a big union type describing what
sorts of functions could be in the table, and explicitly extract one
of the appropriate type, but that just increases the number of things
I have to keep up-to-date when I modify the program and add a new
function to the table.  I'd rather not have to cope with that when
first trying something out.

>Whats irritating me more and more in this discussion (as long as
>I'am following it; the last week) is that the advocates of dynamic 
>typing claim for more expressivness, which *looks* like 
>the arguments of practical men, but in fact seems to be 
>more of philosophical nature. (This would be quite alright, but say 
>it like it is.)

Actually, I think the practical argument is this: In certain
situations (such as in protyping), I want to program in a completely
unconstrained way.  If one way of expressing things makes things
easier, I should be able do it.  ANYTHING which forces me to think
about my program in an unnatural way will distract me from the problem
at hand.  A static type system forces upon me someone else's idea of
how things should be done.  A dynamic type system leaves me more free
to do what ever moves me.  Later I can worry about going back and
making things safe for other people to use, or more efficient, or
whatever.

>Wolfgang Grieskamp 
>wg@opal.cs.tu-berlin.de tub!tubopal!wg wg%opal@DB0TUI11.BITNET

					-Brian Murphy
					 brm@cs.stanford.edu