gudeman@cs.arizona.edu (David Gudeman) (03/06/91)
In article <1991Mar5.182130.15091@engage.enet.dec.com> grier@marx.enet.dec.com writes:
] Sorry for the confusion, your "definition" wasn't clear about what
]you meant.
The term "weak typing" has been used for this feature, but it has also
been said that Pascal and C are weakly typed languages, so I didn't
want to used that word. The word "untyped" has also been used, but I
don't like that term for two reasons. First, it tends to confuse
people when you say "Icon is an untyped language. It has ten
different types...". People assume "untyped" means that a language
has no types, but it really just means that syntactic elements don't
have types. Another reason I don't like the term "untyped" is that it
implies a sort of scale: (strongly typed ... weakly typed ... untyped)
and this is deceptive. Weakly typed languages (when they are
distinguished from untyped languages) still have this notion that you
can assign types to identifiers and other (syntactic) expressions.
Languages with runtime polymorphism (or runtime typing) do not have
this concept at all.
] Over the weekend, I was thinking about it and realized
]that I might have misinterpreted you. I'd never seen a definition
]of anything called "runtime polymorphism" before, and you didn't
]include any additional information or examples which made what you
]meant clear.
Well, my definition could have been clearer. I'll make the excuse
that everyone I talk to around here has enough experience with these
sorts of languages that a quick explanation is enough to let them know
what I mean. I didn't make allowance for different "programming
language cultures". I used the word "polymorphism" to mean "multiple
types for the same expression", not "multiple functions with the same
name". However, the term has enough baggage associated with it that
it was a poor choice. I'm going to arbitrarily change my term...
First:
Static typing: a programming language feature where identifiers and
other syntactic expressions are assigned types based on information
that is present in the text of the program -- usually involving
variable declarations. Functions and operators always assume that
the values passed to them are the expected type. Strong typing and
weak typing are relative terms that describe the amount of
information available from the text of the program.
Now instead of "runtime polymorphism":
Dynamic typing: a programming language feature where identifiers and
other syntactic elements cannot be assigned types. Any expression
may (in principle) produce a value of any type when it is evaluated.
Functions and operators must (in principle) always examine the types
of their arguments and do something reasonable for any possible type
(where "something reasonable" includes the possibility of aborting
the program with an error message).
] Your definition of "runtime polymorphism" doesn't really make
]sense in a type-safe system. so clearly what you're talking about
]can only occur in a weakly typed language
Although my suggestion in Part 2 does give a language with dynamic
typing that is type safe in the following sense: syntactic expressions
can be assigned types; and in an expression f(expr) where expr has
type top and f expects some fixed type T, it is guaranteed at runtime
that either (1) f is called with an argument of the correct type, or
(2) a runtime error occurs. This is just as "type safe" as if expr
was a tagged union and you had to explicitly test the type of the
union before calling f. It's just that the test is built in to the
language.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemangrier@marx.enet.dec.com (03/06/91)
In article <584@coatimundi.cs.arizona.edu>, gudeman@cs.arizona.edu (David Gudeman) writes: |> |> The term "weak typing" has been used for this feature, but it has |> also |> been said that Pascal and C are weakly typed languages, so I didn't |> want to used that word. That's interesting. I'd certainly agree that C is weakly typed, but with Pascal requiring name compatibilty of types (rather than structural, as in C and Modula-2,) I'd put it in the "strong typing" category. (Strong typing is not necessarily "good." Pascal's a neat language, but it lacks tons of features for modern software construction...) |> <stuff about untyped languages> This is besides the point, but what's an untyped language then? If a type defines a collection of values, by definition, every object in the language has a type, since every value is (reflexively) a value. I can't relate to your Icon example, I'm sorry to say it's a language which is a hole in my readings and experience. |> |> Well, my definition could have been clearer. I'll make the excuse |> that everyone I talk to around here has enough experience with these |> sorts of languages that a quick explanation is enough to let them know |> what I mean. I didn't make allowance for different "programming |> language cultures". I used the word "polymorphism" to mean "multiple |> types for the same expression", not "multiple functions with the same |> name". However, the term has enough baggage associated with it that |> it was a poor choice. I'm going to arbitrarily change my term... Ah! I've always seen polymorphism with respect to functions/ operators/arrows, not necessarily the types themselves. I couldn't reconcile your definition, it's much clearer now... :-) |> <definitions of Static and Dynamic Typing> I'm reading a book on Functional Languages right now, and the language being used as a model is Hope, which is strongly typed, but where an inference system is used to determine the static typing of the dynamically typed expression. Does this fall into your category? It seems to me that with global optimization, you can turn any seemingly weakly typed expression into a strongly typed one (and thus eliminate most if not all the inefficiencies which we're concerned with here.) The notable exception is what you mentioned: an operator like "read" where the type of the return value cannot be determined by static analysis of the program. My cut on that is that the value returned from something like "read" *does* fall into some type, and the return should be treated by the client as a "refany" is in CLU or Modula-3: you have to apply a type-case to the value in order to narrow the type of the expression. Is this contrary to your goals? I'm suggesting something (in a CLU/Modula-3 like procedural syntax) like: x : REFANY; BEGIN x := read(); TYPE_CASE x OF Integer : BEGIN /* integer-dependent operations and optimizations */ END; . . . END; END; Presumably the type_case statement can have an else arm where an exception could be raised or appropriate actions taken. (It's exactly this case of an opacity which can't be determined by any amount of compile-time static analysis where the inflexibility vs. inefficiency comes in. I've never used a "type inferred" language like Hope myself, but with the exception of this case, it seems usable and eliminates your worries.) The flexibility you desire is/can be obtained by having a type at the root of the hierarchy (which some consider artificial, others essential,) which can be used to represent values of any type, and then also a language operator to perform a modicum of run-time type checking, permitting significant optimizations within the narrowed scope, which I believe is the source of your concern. (There's been a lot of talk about adding in run-time accessable per-class tags to C++ objects lately, and it seems to me that if you can perform global analysis, you can make the run-time checking occur in linear time, costing space n^2 where n is the number of types/classes.) Or was it just academic interest in the topic in general? |> David Gudeman |> gudeman@cs.arizona.edu |> noao!arizona!gudeman |> ------------------------------------------------------------------------ I'm saying this, not Digital. Don't hold them responsibile for it! Michael J. Grier Digital Equipment Corporation (508) 496-8417 grier@leno.dec.com Stow, Mass, USA Mailstop OGO1-1/R6
new@ee.udel.edu (Darren New) (03/06/91)
>|> <stuff about untyped languages> > This is besides the point, but what's an untyped language then? Not to put words in anybody's mouth, but the post you are responding to says >People assume "untyped" means that a language >has no types, but it really just means that syntactic elements don't >have types. (Notice how I cleverly delete all "he wrote/she wrote" headers to avoid getting this wrong :-) Anyway, having a strong Smalltalk background, I interpret this to essentially to be saying that values have types but not variables. The declaration of a variable is just mentioning its name at the correct place within the method, without any formal declaration of the values that variable is allowed to hold. Values in Smalltalk most definitely have types, and types are even first-class objects. Also, in an `untyped' language, expressions return values (which have types) but since the same static expression can return values of different type, the expression itself cannot be siad to have a specific type. For example, Smalltalk allows arrays to have values of different types in different positions of the array. Hence, x := (array at: 5) is not a specific type, even though at any given time that expression will return a value of a given type and assign that value to x. x will nevertheless be untyped. Contrast with C, wherein one says (x = array[4]). Depending on the declaration of `array', I can tell the type of the value array[4]. I can also know the type of the variable x. Well, I hope that clears that up, and that I haven't misrepresented what was being said. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
icsu8209@khan.cs.montana.edu (Glassy) (03/07/91)
In article <1991Mar6.024730.19073@engage.enet.dec.com> grier@marx.enet.dec.com () writes: >In article <584@coatimundi.cs.arizona.edu>, gudeman@cs.arizona.edu >(David Gudeman) writes: >|> The term "weak typing" has been used for this feature, but it has >|> also been said that Pascal and C are weakly typed languages, so I didn't >|> want to used that word. > > That's interesting. I'd certainly agree that C is weakly typed, but >with Pascal requiring name compatibilty of types (rather than >structural, as in C and Modula-2,) I'd put it in the "strong typing" >category. (Strong typing is not necessarily "good." Pascal's a neat >language, but it lacks tons of features for modern software >construction...) Um, I don't think so. Pascal (at least ISO-something-something-6000) did not state which form type equivalence would take (structural vs. name equivalence). Vendors thus are free to do what they like, in this regard, which yields us an interoperability disaster. Modula-2, in Wirth's definition, uses name equivalence. All the Modulas I've used conform to this. Modula-3 by DECWRL, on the other hand, mandates structural equivalence. IRT the definitions of 'typing', discussions such as this thread are useful for helping all of us to communicate on the same (set of?) wavelength(s). The definitions of typing I've seen (in the literature) hew fairly closely to David Gudeman's. Interesting to note the variety of languages that can fall under a single category, WRT typing: static typing: FORTRAN ;all vars/funs declared explicitly ABC ;types determined implicitly at text-entry time by textual context and by example ML ;types determined at compile time via type inference. dynamic typing: Lisp ;"we'll find out (what type it has) when we get there." others??? typeless (aka untyped): BCPL ; everything's a machine word, so don't bother declaring stuff. "strong" typing: Modula, Euclid: static typing with tight controls on what may be coerced to what. "weak" typing: C: static typing with with loose/no controls on coercions. ------------------------ -- -- Lou Glassy </// "O Tempora!" icsu8209@caesar.cs.montana.edu \\\> --Cicero
grier@marx.enet.dec.com (03/07/91)
In article <46686@nigel.ee.udel.edu>, new@ee.udel.edu (Darren New) writes: |> <stuff deleted> |> Also, in an `untyped' language, expressions return values (which have |> types) but since the same static expression can return values of |> different type, the expression itself cannot be siad to have a specific |> type. For example, Smalltalk allows arrays to have values of different |> types in different positions of the array. Hence, x := (array at: 5) is |> not a specific type, even though at any given time that expression will |> return a value of a given type and assign that value to x. x will |> nevertheless be untyped. Contrast with C, wherein one says (x = |> array[4]). Depending on the declaration of `array', I can tell the type |> of the value array[4]. I can also know the type of the variable x. Ok, that makes sense. (I confess to not doing much in Smalltalk, probably a cardinal sin among OO folk.) But, at any given instant, the variable does represent a value which is a member of a given class. Even in expressions which are "untyped" (such as x := (array at: 5),) a globally scoped optimizer *could* infer the type of x. (Sounds to me like it's similar to a computability/halting- problem type of issue when you get into nontrivial recursive situations, but I haven't read that part of my func. lang. book yet... :-) In fact, it can always infer the type of the expression, although there are probably cases where a more general type is computed than the actual class of the value. (For instance, you could always punt and say "it's an Object". That's not very useful in aiding efficiency though... :-) Something that occurred to me is "what's the point here?" If the issue is to see what you *can* and *can't* do efficiently in an untyped/dynamically typed language, like I said, it seems related to the complexity and difficulty of the halting problem. There's no algorithm which is going to be able to infer the result type of an expression in all instances, but it seems like for many important ones, there are solutions. (The article posted to either comp.arch or comp.lang.c about optimizing Scheme, I believe it was, is a good example of what CAN be done, even if a single solution can't cover all cases. The point about the halting problem comes from some postings by Dan Bernstein where he claims a solution to the halting problem. What he *does* is solve a significant and useful portion of it, which is interesting. What's been proved is that every algorithm which will definitely produce an answer in finite time will have to make one of three decisions - halts, doesn't halt, can't determine. The "can't determine" seems very similar to "ummm... it's an Object!" in inferring the type of an expression.) I was approaching the issue with my engineering hat on, and looking at what problem was trying to be solved. My preference is towards strongly typed languages with mechanisms like I've outlined where the type can be strengthened within a given scope and so additional inferences about operations can be made. But if the desire is for discussion and academic interest, my ideas have little bearing, except that perhaps it's not a very fruitful or useful branch of study. (Of course that's what a lot of people have said about different branches of Mathematics which end up turning up in the strangest places explaining observed phenomonea.) |> |> Well, I hope that clears that up, and that I haven't misrepresented |> what was being said. -- Darren |> |> -- |> --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- |> ----- Network Protocols, Graphics, Programming Languages, |> Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- |> =+=+=+ Let GROPE be an N-tuple where ... +=+=+= |> ------------------------------------------------------------------------ I'm saying this, not Digital. Don't hold them responsibile for it! Michael J. Grier Digital Equipment Corporation (508) 496-8417 grier@leno.dec.com Stow, Mass, USA Mailstop OGO1-1/R6
gudeman@cs.arizona.edu (David Gudeman) (03/10/91)
In article <1991Mar6.024730.19073@engage.enet.dec.com> grier@marx.enet.dec.com writes:
]
] This is besides the point, but what's an untyped language then?
The term is usually used to refer to dynamically typed languages. I'd
just as soon drop the term completely, since it is misleading if a
language has any built-in types at all.
]... Hope, which is strongly typed,
]but where an inference system is used to determine the static typing
]of the dynamically typed expression.
]
] Does this fall into your category?
Hope is statically typed since you can give types to syntactic
expressions. The definition does not specify how the types are
derived (I said types _usually_ determined by declarations).
] It seems to me that with global optimization, you can turn any
]seemingly weakly typed expression into a strongly typed one
Do you mean "turn any dynamically typed language into a statically
typed one"? If so, it has been my experience that given a program in
a dynamically typed language, a human can determine unique types for
85% to 99% of the names in the language. Type inference generally is
a little weaker, but is getting pretty good.
] ...the value returned from something like
]"read" *does* fall into some type, and the return should be treated
]by the client as a "refany" is in CLU or Modula-3: you have to apply
]a type-case to the value in order to narrow the type of the
]expression.
]
] Is this contrary to your goals?
Yes, it is. I don't want to have to write extra code to express
something that should be obvious. If I write "3 + read()" it should
be obvious that I want the correct sort of addition to be done
depending on whether read() returns an int or a float. I shouldn't
have to say it explicitly. Another reason I don't want to write
type-case expressions for things like this is that I may later change
the definition of read() so that it always returns a float. I don't
want to have to go find every place I used it and remove all the
type-case stuff.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanpcg@cs.aber.ac.uk (Piercarlo Antonio Grandi) (03/11/91)
On 10 Mar 91 00:21:37 GMT, gudeman@cs.arizona.edu (David Gudeman) said:
gudeman> In article <1991Mar6.024730.19073@engage.enet.dec.com>
gudeman> grier@marx.enet.dec.com writes:
grier> This is besides the point, but what's an untyped language then?
gudeman> The term is usually used to refer to dynamically typed
gudeman> languages. I'd just as soon drop the term completely, since it
gudeman> is misleading if a language has any built-in types at all.
A point of order: I would not use 'dynamic types' here. I would say
'latent types'. The idea is that dynamically typed should be reserved
for the (currently rare!) case where the language allows the type of a
*value* to change dynamically, not for the case where the type of the
value of a *variable* is not manifest at compile time.
I would propose the following terminology:
<type> The equivalence class of all <values> to which
a given set of operations can be meanigfully
applied.
<typing> The ability to give an explicit name to a
<type>, and to have a 'typeof' operator (either
explicit or implicit) that returns the appropriate
name given a value.
<manifest typing> Being able to do <typing> for the <values>
denoted by <references> (i.e. variables) at
compiletime.
<latent typing> When the <value> denoted by a <reference> has a
<type> that cannot be determined at compiletime.
<static typing> When the <typing> of a <value> cannot change.
<dynamic typing> When the <typing> of a <value> can change during
program execution.
Examples (contrived, unfortunately):
We have the values from 0 to 2^32-1, and the operations +,-,* modulo
2^32 on these values. They form a type. We add an operation, 'typeof'
that given one such value returns a type name, say 'unsigned'.
We have typing. We write 'unsigned i'. This is manifest typing, as we
know by the inpesction of the program source that the values that the
reference bound to the 'i' identifier can only have typing 'unsigned'.
Now we switch to Scheme and we say '(define i 0)'. We have latent static
typing, because the typing of the value involved may change at runtime,
but whatever the value is, its typing will *not* change during the
execution of the program.
Now we switch to some more advanced language and we add while the
program is executing a new operation, say '/', with two arguments, one
is 'unsigned' and the other is 'positive' (nonzero). Then we can
dynamically chang the typing of the value '1', because now it can be
*both* an 'unsigned' and a 'positive'.
So, latent typing is when 'typeof' applied to a *variable* is not a pure
function, in that given the same variable it may give different results
at different times; dynamic typing is when this happens also when it is
applied to *values*, not just to variables.
Note that the distinction I make above between <type> and <typing> is
artificial but necessary, and it causes trouble.
Suppose that we have the <type> defined by the class of values to which
operations +,-,* modulo 32 can be applied as above; we can call it the
'unsigned' class in some nice contemporary language and we have
Suppose that we now also define the % operation to the unsigned class;
we have a *different* type, but the typing remains the same, because
'typeof' will continue to return 'unsigned' when applied to values
tagged as belonging to the 'unsigned' class.
This is not very dangerous in this particular situation, but inb others
it can be highly inconvenient especially when the definition of a class,
that is the <typing>, is allowed to change dynamically. For example it
can be very dangerous if we change the encoding for the values of that
class, e.g. from binary to BCD.
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.ukbbc@rice.edu (Benjamin Chase) (03/11/91)
>I would propose the following terminology: ><type> The equivalence class of all <values> to which > a given set of operations can be meanigfully > applied. Make certain that you don't proscribe certain views of the world through too narrow a definition. Consider the language Russell, where types are viewed not as data, but rather as collection of operations on data. You may consider this to be an argument over a glass of water being "half-empty" vs. "half-full", but I found the Russell outlook on the question of "what are types, really?" to be very pleasant. ><latent typing> When the <value> denoted by a <reference> has a > <type> that cannot be determined at compiletime. ><manifest typing> Being able to do <typing> for the <values> > denoted by <references> (i.e. variables) at > compiletime. Of course, the obvious name for manifest typing is really blatant typing, the obvious meaning being that the types of things are obvious enough that even a compiler can deduce them :-). That way, we have "latent" vs. "blatant", a very pleasant sounding pair. Of course, the invitation to incorrectly spell them either (or both?!?) as blatent (bleah!) or latant (fooey!) is too tempting for some... -- "it is perfectly safe to eat the yogurt under the green fuzz, and I do it fairly often" - brian reid Ben Chase <bbc@rice.edu>, Rice University, Houston, Texas
gudeman@cs.arizona.edu (David Gudeman) (03/12/91)
In article <PCG.91Mar10181749@aberdb.cs.aber.ac.uk> Piercarlo Antonio Grandi writes:
]
]A point of order: I would not use 'dynamic types' here. I would say
]'latent types'. The idea is that dynamically typed should be reserved
]for the (currently rare!) case where the language allows the type of a
]*value* to change dynamically,...
]<type> The equivalence class of all <values> to which
] a given set of operations can be meanigfully
] applied.
...
]Now we switch to some more advanced language and we add while the
]program is executing a new operation, say '/', with two arguments, one
]is 'unsigned' and the other is 'positive' (nonzero). Then we can
]dynamically chang the typing of the value '1', because now it can be
]*both* an 'unsigned' and a 'positive'.
This only happens in a statically typed language. In a dynamically
typed language you don't declare the types that an operator works on,
so this doesn't happen.
This definition of types originated with the implicit assumption that
the set of operations are fixed. When operations can be added at
runtime, bizarre situations arise where the type of a value can
change. This doesn't shouldn't prompt us to add complexity to the
language, trying to distinguish between <type> and <typing>. Rather
we should drop this notion of <type> altogether and define
<type> a set of values.
Then no seperate notion of <typing> is needed. In fact, this is what
is done in most dynamically typed languages. It makes it trivial to
do useful things like define hierarchies of types (subsets) and to
have values that are of several different types (membership in
different sets). It also gives you powerful machinery for defining
complex types and for deciding type membership. It also gives you a
fairly simple way to define the result of the 'typeof' function(s)
even though a value may have may types: you just define some arbitrary
(but useful) partition of the set of all values, and give each set a
name.
(There are people who complain about using the word "set" here since it
makes it problematic to make <type> a value. (eg: T is the type that
contains all types that do not contains themselves. Is T in the type
T?) However, that is a problem cause by defining <type> to be a
value. It is not inherent in defining a type as a set.)
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanbrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/12/91)
I really think we need a Frequently Used Definitions list here... In article <601@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > <type> a set of values. Yeah, this is the definition I'm familiar with. Also: <reference> a section of program text that refers to a value. Any language lets you express certain types. In general the expressible types are a small, fixed set of basic types, plus the transitive closure of a fixed set of type composition operations upon those basic types. In C, for example, the basic types are int, double, etc., and the type composition operations are array, struct, function, etc. In C, every reference has a value with a fixed, expressible type, known to the compiler. The value of that reference may change during program execution, but it is always in that compile-time type. I believe this is what most people mean by static typing. Note: If a statically typed language gives you ``the set of expressible types'' and ``the set of all values'' as basic types, and struct as a type composition operation, then you can implement runtime polymorphism in that language. I.e., the set of pairs (type,value) is a type, and you can restrict yourself to using those pairs. The typing is still static: in fact, every value in your program has the same type, namely the set of all (type,value). Typechecking in this context means making sure that the value inside (type,value) is a member of the given type. Given this, I fail to see how dynamic typing can be regarded as more than a syntactic feature. If you're given a program that uses dynamic typing, you can just convert every reference in the program to refer to a (type,value) pair, and poof! you have a statically typed program. (That doesn't mean I have no appreciation for dynamic typing; syntactic features are often quite worthwhile, and can represent quite a lot of work. In C, for example, the set of all types is not a basic type, so you have to create the type for yourself and arrange that every type definition be accompanied by creation of a member of the type of all types. Then you have to carry (type,value) pairs everywhere, and handle all the typechecking. This is still a syntactic conversion from the original program. It requires no support from the compiler.) ---Dan You are in a maze of twisty little types, all alike.
pcg@test.aber.ac.uk (Piercarlo Antonio Grandi) (03/12/91)
On 11 Mar 91 20:35:48 GMT, gudeman@cs.arizona.edu (David Gudeman) said:
gudeman> In article <PCG.91Mar10181749@aberdb.cs.aber.ac.uk> Piercarlo
gudeman> Antonio Grandi writes:
pcg> A point of order: I would not use 'dynamic types' here. I would say
pcg> 'latent types'. The idea is that dynamically typed should be reserved
pcg> for the (currently rare!) case where the language allows the type of a
pcg> *value* to change dynamically,...
pcg> <type> The equivalence class of all <values> to which
pcg> a given set of operations can be meanigfully
pcg> applied.
pcg> Now we switch to some more advanced language and we add while the
pcg> program is executing a new operation, say '/', with two arguments,
pcg> one is 'unsigned' and the other is 'positive' (nonzero). Then we
pcg> can dynamically change the typing of the value '1', because now it
pcg> can be *both* an 'unsigned' and a 'positive'.
gudeman> This only happens in a statically typed language. In a
gudeman> dynamically typed language you don't declare the types that an
gudeman> operator works on, so this doesn't happen.
No, no, we have *two* misunderstanding here. I have never said that in
this example one need declare *explicitly* the types of the arguments of
an operator; simply, that a type is defined by the operators that can be
meaningfully applied to the values of that type. Since / cannot be
meaningfully applied to zero, adding it to the language means that one
implicitly is distinguishing between the <type> 'unsigned' and
'positive', because the second argument to / cannot be zero.
gudeman> This definition of types originated with the implicit assumption that
gudeman> the set of operations are fixed. When operations can be added at
gudeman> runtime, bizarre situations arise where the type of a value can
gudeman> change. This doesn't shouldn't prompt us to add complexity to the
gudeman> language, trying to distinguish between <type> and <typing>.
But changing <type> is of the essence. It happens all the time. Every
time you use an interactive lanfguage like Scheme and you define a new
function. Also, when you edit the definition of a C++ struct and
recompile.
Consider the latter example; the <typing> has not changed, but the
<type> has. This is dangerous; for example all the values created under
the old definition may well be no longer meaningful. Data restructuring
is needed then.
This si for example well understood in the capability architecture
business; a capability architecture only has <typing>, and tags each
value with a type code. Each type code is associated with a type
manager, the module that implements all the operations on values with
that type code (this will be well known to you, but I repeat just to
provide context). Now if the type manager changes, often one has to
assign a new type code to it, because changes in the <type> should be
reflected in changes in the <typing>. Not necessarily, for example we
can keep the same <typing> if the new <type> is a superset (or even
subset) of the old, of course, as when we don't change the
encoding/decoding functions for composite values. Example in C++:
struct Complex { float re, im; };
Complex operator +(const Complex &a, const Complex &b) { ... };
If we change this to
struct Complex { float real, imaginary; };
Complex operator +(const Complex &a, const Complex &b) { ... };
We need not change the <typing> of complex <type> values; we just have
to edit and recompile 'operator +' with the names of the new
decomposition functions.
But if we change it to
struct Complex { float im, re; }
Complex operator +(const Complex &a, const Complex &b) { ... };
The <typing> has not changed, but the <type> has changed in a way such
that the <typing> chould change.
Naturally most people are blinkered in that they ignore the issue of
persistency, but unfortunately in the real world almost all data are
persistent, and the difference between <type> and <typing> is thus
terribly important.
An example of this is the protocol revision level field in many
protocols; each protocol is really a type specification, where each
packet header is a value in the type defined by the protocol operations
that it triggers.
I will venture as far as saying that the difference between <type> and
<typing> which is inherent in most all languages, operating systems,
databases out there is regrettable and is only really an efficiency
hack, just like the one between 'eq' and 'equal', and it generates much
the same class of problems.
gudeman> Rather we should drop this notion of <type> altogether and
gudeman> define
gudeman> <type> a set of values.
This is wrong, as far as I can see, because then there is no way to know
the <type> or <typing> of a value. As soon as you instead have a
'typeof' operation, you create equivalence classes. Please note: in my
porposed definitions, <value> is just a number, and absolutely nothing
else, and it does not carry any other information than that number.
I think you are wrongly assuming, in other words, in your definition
above, that there is some magic way to know which set a value belongs
to, without encoding it into the value itself. This is not possible, I
am afraid. On the other hand if you encode the set into the value
itself, then you are defining types as equivalence classes, and your
definition and mine are exactly equivalent, except maybe that yours
hides the difference between <type> (a concept) and <typing> (an
economical implementation of that concept).
gudeman> Then no seperate notion of <typing> is needed.
Quite the opposite... The end result of your proposal is to drop the
notion of <type> and keep only that of <typing>, not viceversa.
gudeman> In fact, this is what is done in most dynamically typed
gudeman> languages.
In this you are right. Indeed in most languages, whatever their typing
discipline, one can only handle <typing>, not <types>. This is a gross
limitation, and one that is simply unacceptable when you have persistent
values. The limitation can be gotten around using gross hacks; for
example when the <type> changes but not the <typing>, e.g. when a new
release of Unix switches the implementation of /etc/passwd from a text
file to an hash file, you need a program to convert formats, whose role
is essentially that of converting one <type> to another to maintain ther
illusion that <typing> has not changed.
gudeman> It makes it trivial to do useful things like define hierarchies
gudeman> of types (subsets) and to have values that are of several
gudeman> different types (membership in different sets).
Actually it makes it incredibly opaque. I know no language that IMNHO
does a satisfactory job of reconciling the gross rigidities of doing
<typing> with the reality that <types> are equivalence classes. For
example, to repeat my usual party line, there ar eno languages that have
any decent algebra on the various aspects of <typing>; they all limit
the <typing> algebra to an awakward subset of the possibilities demanded
by applications.
gudeman> It also gives you powerful machinery for defining complex types
gudeman> and for deciding type membership. It also gives you a fairly
gudeman> simple way to define the result of the 'typeof' function(s)
gudeman> even though a value may have may types: you just define some
gudeman> arbitrary (but useful) partition of the set of all values, and
gudeman> give each set a name.
This is just <typing>, according to my terminology. You have thrown away
the notion of <type> entirely.
gudeman> (There are people who complain about using the word "set" here
gudeman> since it makes it problematic to make <type> a value. (eg: T
gudeman> is the type that contains all types that do not contains
gudeman> themselves. Is T in the type T?) However, that is a problem
gudeman> cause by defining <type> to be a value. It is not inherent in
gudeman> defining a type as a set.)
While a <type> is an equivalence class, and thus not a value, a <typing>
can be represented as a value, e.g. by assigning to each <typing> class
an arbitrary code. Then these codes *do* form a <type>. This is like the
solution to paradoxes in Russell's (the mathematician, not the like
minded functional language :->) Principia...
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.ukgudeman@cs.arizona.edu (David Gudeman) (03/13/91)
In article <19728:Mar1208:45:2291@kramden.acf.nyu.edu> Dan Bernstein writes: ] ]Given this, I fail to see how dynamic typing can be regarded as more ]than a syntactic feature. If you're given a program that uses dynamic ]typing, you can just convert every reference in the program to refer to ]a (type,value) pair, and poof! you have a statically typed program. Alternatively: I fail to see how static typing can be regarded as more than a syntacitic feature. If you're given a program that uses static typing, you can just check the types at every reference in the program to make sure they are correct... BTW, you can't just change the program to refer to a (type,value) pair, you also have to insert code to do the right thing based on the type. For "x + y", you have to generate: switch (x.type) { case int_type: switch (y.type) { case int_type: return x.val.int + y.val.int case float_type: return x.val.int + y.val.float; default: type_error(y); } ... } and so on, for each combination of types. For more general expressions like "x = y", you have to give code that works for any possible combination of types -- not just numbers. -- David Gudeman gudeman@cs.arizona.edu noao!arizona!gudeman
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/13/91)
In article <608@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > Alternatively: I fail to see how static typing can be regarded as more > than a syntacitic feature. If you're given a program that uses static > typing, you can just check the types at every reference in the program > to make sure they are correct... That is correct. Since most people, most of the time, seem to want to use statically typed values, and since compilers have an easier time optimizing statically typed programs than dynamically typed programs, it makes sense to provide static typing as the default. You can implement dynamic typing on top of this if you think people will find it useful. What is the argument here? > BTW, you can't just change the program to refer to a (type,value) > pair, you also have to insert code to do the right thing based on the > type. Didn't I say that? Yes, you have to do this, and it can represent a significant amount of work (about as much as writing a C++ translator). It's still a syntactic transformation. ---Dan
gudeman@cs.arizona.edu (David Gudeman) (03/13/91)
In article <25293:Mar1221:01:4491@kramden.acf.nyu.edu> Dan Bernstein writes:
]... Since most people, most of the time, seem to want to
]use statically typed values
This is open to debate. And in any case, I claim that most people who
say they want static typing are ignorant of the alternative. I'll bet
that programmers who have programmed equally in both types of language
will overwhelmingly prefer dynamic typing (after correcting for the
stupid syntaxes that these languages seem prone to). I know of many
people who started out programming in C or Pascal and fell in love
with Icon when they first tried it (me for example). I doubt there
are many cases of programmers who started out with a dynamically typed
languages and grew to prefer static typing (yes, there _are_ some
places where the first programming class uses a dynamically typed
language).
] and since compilers have an easier time
]optimizing statically typed programs than dynamically typed programs, it
]makes sense to provide static typing as the default.
Only if you are designing the language to be implemented. If you
are designing the language to be used, then this argument fails.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemangudeman@cs.arizona.edu (David Gudeman) (03/13/91)
I'm not entirely sure I understand what you are getting at, but that's
never stopped me from talking before...
In article <PCG.91Mar12135254@aberda.test.aber.ac.uk> Piercarlo Antonio Grandi writes:
...
]No, no, we have *two* misunderstanding here. I have never said that in
]this example one need declare *explicitly* the types of the arguments of
]an operator; simply, that a type is defined by the operators that can be
]meaningfully applied to the values of that type.
What does "meaningfully applied" mean? In a dynamically typed
language, any function can be legally applied to any value. So are
you suggesting that every value has the same <type>? Or do you want
"meaningfully applied" to mean that the function doesn't produce an
error message when called with that value? Then what do you do with
something like
procedure foo(x1,x2)
if number(x1) then return x1 + x2
else return x2
end
where x2 must be a number if x1 is, but otherwise can have any type?
I think the whole concept is on shakey ground.
]... is regrettable and is only really an efficiency
]hack, just like the one between 'eq' and 'equal', and it generates much
]the same class of problems...
An aside, 'eq' and 'equal' are semantically distinct. I would
consider the language to be lacking an important operation if it were
missing either one. The same applies to 'eql'. They all serve
different purposes.
]This is wrong, as far as I can see, because then there is no way to know
]the <type> or <typing> of a value...
]I think you are wrongly assuming, in other words, in your definition
]above, that there is some magic way to know which set a value belongs
]to, without encoding it into the value itself...
I wasn't making any assumptions about the representation of values.
Frankly, I'm surprised to see representation come up at all, since I
don't see what it has to do with the subject at hand (unless you are
thinking of <type> as a particluar way of interpreting a group of
bytes as a value. That doesn't fit your definition though.)
]... On the other hand if you encode the set into the value
]itself, then you are defining types as equivalence classes, and your
]definition and mine are exactly equivalent.
Not at all. Your definition has the <type> of a value changing when
new functions are added. Mine doesn't.
]gudeman> Then no seperate notion of <typing> is needed.
]
]... The end result of your proposal is to drop the
]notion of <type> and keep only that of <typing>, not viceversa.
I'm throwing away your concept of <type>, as I said.
]... when a new
]release of Unix switches the implementation of /etc/passwd from a text
]file to an hash file, you need a program to convert formats, whose role
]is essentially that of converting one <type> to another to maintain ther
]illusion that <typing> has not changed.
The job of the program is to convert from one representation to
another. The set of operations on the file has not changed, so the
the <type> hasn't changed, by your definition. Again though, it looks
like you mean <representation> when you say <type>.
]... I know no language that IMNHO
]does a satisfactory job of reconciling the gross rigidities of doing
]<typing> with the reality that <types> are equivalence classes.
Are you familiar with Common Lisp? What sort of type do you need that
you can't define in that language? How is an equivalence class
different from a set? And what equivalence relation are you refering
to? It looks at times as though you mean $equiv(x,y) iff typeof(x) =
typeof(y)$ -- which makes <type> and <typing> identical.
]gudeman> ... It also gives you a fairly
]gudeman> simple way to define the result of the 'typeof' function(s)...
]
]This is just <typing>, according to my terminology. You have thrown away
]the notion of <type> entirely.
Yeah, that's what I said. (I get the feeling we aren't
communicating...)
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanpcg@test.aber.ac.uk (Piercarlo Antonio Grandi) (03/14/91)
On 12 Mar 91 08:45:22 GMT, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) said: Incidentally, I hereby announce my defeat; I have realized that too many people are using dynamic and static typing to indicate when the type of *variables* is known. So I will use these terms like that myself. I propose the use of mutable/immutable typing for the case where the typing of *values* can or cannot be changed at runtime. brnstnd> <reference> a section of program text that refers to brnstnd> a value. Normally this is called the scope, except in Algol 68 where there is a distinction between range and reach. In all texts that I know reference is more or less synonymous with pointer. People use reference after the Algol 68 revised report, usually, or after Simula 67, which both use reference in the way indicated above. The normal definition of reference is something like "a value that may refer to another value or to no particular value". brnstnd> Note: If a statically typed language gives you ``the set of brnstnd> expressible types'' and ``the set of all values'' as basic brnstnd> types, and struct as a type composition operation, then you can brnstnd> implement runtime polymorphism in that language. [ ... ] Of course... But after you say: brnstnd> Given this, I fail to see how dynamic typing can be regarded as brnstnd> more than a syntactic feature. If you're given a program that brnstnd> uses dynamic typing, you can just convert every reference in brnstnd> the program to refer to a (type,value) pair, and poof! you have brnstnd> a statically typed program. This is entirely uninteresting! Recursion is merely a "syntactic feature" too, by the same argument, as it can always be obviated by the use of stacks or by iteration. Yet a lot of people think that recursion should be provided as a "syntactic feature". What we are interested here is in *architecture*, that is designing boundaries between layers. In our particular case the boundary between what the language provides directly and what the programmer can achieve building on top of that. Dynamic typing as a concept is simply necessary in a wide class of applications; one has four choices, with respect to it and static typing: 1) Don't provide dynamic typing as a language primitive and make it prohibitive to implement it on top of the provided language primitives. 2) Don't provide dynamic typing as a language primitive, and make it possible to implement it more or less grossly on top of the provided language primitives. 3) Provide dynamic typing only as a language primitive, and make it possible to implement static typing by explicit checks. 4) Provide *both* dynamic and static typing as language primitives, with no solution of continuity, as one becomes the other depending on which variable's values are known at compiletime. I reckon that Gudeman thinks that Bernstein advocates 1), while Bernstein really advocates 2); Gudeman himself advocates 3), and I advocate 4). While I advocate 4), I think that there are good reasons to think that 3) is acrtually a more tnable proposition than 2): an efficient implementation of dynamic typing as language primitive is not much worse (thanks to caching and hinting) than one of static typing, or at least the difference is not large for many complex *applications*, while a clean implementation of dynamic typing given static typing primitives is much harder to do, as the X windows example demonstrates so clearly. -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.uk
augustss@cs.chalmers.se (Lennart Augustsson) (03/14/91)
In article <614@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > ... And in any case, I claim that most people who >say they want static typing are ignorant of the alternative. I'll bet >that programmers who have programmed equally in both types of language >will overwhelmingly prefer dynamic typing (after correcting for the >stupid syntaxes that these languages seem prone to). I don't agree. I think that a lot of people who prefer dynamically typed languages are ignorant of the alternatives. Exactly as you I dislike to have to type all the extra type information that you have to do in Pascal, C etc. I also dislike not being able to make polymorphic functions (without cheating). But with languages like ML and Haskell with polymophic type systems and type inference you get static typing without the extra baggage. (Sure, there are still things you can do with dynamic typing that can't be done as easily with static typing; you can't get it all.) Taking your example and translating it to Haskell you'll get Icon: record tree(data,left,right) Haskell: data Tree a = Node a (Tree a) (Tree a) | Null Icon: # insert x into tree t and return the new tree procedure tree_insert(t,x) if t === &null return tree(x) if x <<< t.data then t.left := tree_insert(t.left,x) else t.right := tree_insert(t.right,x) return t end Haskell: (well, a side effect free version of the procedure above) tree_insert Null x = Node x Null Null tree_insert (Node y l r) x | x < y = Node (tree_insert l x) r tree_insert (Node y l r) x = Node l (tree_insert r x) The compiler infers the type (i.e. you don't have to write it!) tree_insert :: (Ord a) => Tree a -> a -> Tree a which means that tree_insert will work on any type of data that is a member of class Ord (i.e. has < defined). -- Lennart Augustsson [This signature is intentionally left blank.]
gudeman@cs.arizona.edu (David Gudeman) (03/14/91)
In article <1991Mar13.195039.22587@mathrt0.math.chalmers.se> Lennart Augustsson writes: ]In article <614@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: ]I don't agree. I think that a lot of people who prefer dynamically ]typed languages are ignorant of the alternatives. I doubt there are many people who are only experienced with dynamically typed languages. If you are refering to type inference as the alternative, you may be right -- people who prefer dynamically typed languages may tend to be unaware of it (like everyone else), but I doubt they would like it, ignoring efficiency issues and sticking strictly to expressiveness and program reliability. When worried about efficiency, everyone prefers statically typed languages, I never meant to claim otherwise. Statically typed languages without declarations are a step in the right direction, but not far enough for my taste. You are still too restricted in the sorts of expressions you are allowed to write (not to mention that for non-toy languages, compilation is slow as a beejeeber). But at least it solves the problems of errors in declarations and having to make pervasive changes to the code when you change declarations. ] tree_insert Null x = Node x Null Null ] tree_insert (Node y l r) x | x < y = Node (tree_insert l x) r ] tree_insert (Node y l r) x = Node l (tree_insert r x) ]The compiler infers the type (i.e. you don't have to write it!) ] tree_insert :: (Ord a) => Tree a -> a -> Tree a ]which means that tree_insert will work on any type of data that is a ]member of class Ord (i.e. has < defined). Can you use this function to insert different types in the same tree? If so, how is it different from dynamic typing? -- David Gudeman gudeman@cs.arizona.edu noao!arizona!gudeman
augustss@cs.chalmers.se (Lennart Augustsson) (03/15/91)
In article <628@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >Statically typed languages without declarations are a step in the >right direction, but not far enough for my taste. You are still too >restricted in the sorts of expressions you are allowed to write (not >to mention that for non-toy languages, compilation is slow as a >beejeeber). I don't know what implementations you have tried, I don't think ML style type inference is particularely slow (except on pathological examples). >] tree_insert Null x = Node x Null Null >] tree_insert (Node y l r) x | x < y = Node (tree_insert l x) r >] tree_insert (Node y l r) x = Node l (tree_insert r x) >]The compiler infers the type (i.e. you don't have to write it!) >] tree_insert :: (Ord a) => Tree a -> a -> Tree a >]which means that tree_insert will work on any type of data that is a >]member of class Ord (i.e. has < defined). > >Can you use this function to insert different types in the same tree? >If so, how is it different from dynamic typing? No, one particular tree can only contain values of one type. I know you find this too restrictive, I was just trying to point out that compile time type checking does not imply that you have to declare the type of the functions you define. -- Lennart Augustsson [This signature is intentionally left blank.]
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/15/91)
In article <PCG.91Mar13185855@aberdb.test.aber.ac.uk> pcg@test.aber.ac.uk (Piercarlo Antonio Grandi) writes: > On 12 Mar 91 08:45:22 GMT, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) said: > Incidentally, I hereby announce my defeat; I have realized that too many > people are using dynamic and static typing to indicate when the type of > *variables* is known. On the contrary. Typing refers to the typing of every single reference in the program, not just ``x'' and ``y''. > brnstnd> <reference> a section of program text that refers to > brnstnd> a value. > Normally this is called the scope, No. The scope of a variable is the largest section X of program text such that any part of X may contain a reference to that variable. > In all texts that I know reference > is more or less synonymous with pointer. Yes. The program text ``x + y'', for example, refers to the value computed as the sum of x and y. You can draw an arrow from ``x + y'' to that value if you want. There are languages where a variable may have a reference---a section of program text referring to a value---as a value in and of itself. Sometimes the program text can be made implicit when you have a reference, as in C++. > 2) Don't provide dynamic typing as a language primitive, and make it > possible to implement it more or less grossly on top of the provided > language primitives. So why do you consider this ``gross'' when it's implemented outside the compiler but (presumably) not gross when it's inside the compiler? As long as the language has good syntax, you can hide all the ugliness of (e.g.) polymorphism inside a header file or library. I advocate that this be done for any essentially syntactic feature. > I reckon that Gudeman thinks that Bernstein advocates 1), while > Bernstein really advocates 2); Gudeman himself advocates 3), and I > advocate 4). Actually, I think Gudeman thinks he advocates (4). > an efficient > implementation of dynamic typing as language primitive is not much worse > (thanks to caching and hinting) than one of static typing, For me compile time and typechecking are both important while I'm writing a program. I cannot afford to choose between fast compilations with no typechecking and slow compilations with full typechecking. (Similarly, many programs take a noticeable amount of time for each debugging run. I cannot afford to choose between fast compile time with slow run time and slow compile time with fast run time. My solution for those programs is to optimize by hand, once.) Do you optimize programs while you're testing? Probably not. But when each test run takes a noticeable amount of time, don't you wish that you could make them run faster without wasting so much time on optimization? Similarly, in a dynamically typed language, would you turn on strict typechecking and other optimizations while you're testing? Probably not. But when you make type errors, don't you wish that you could have found them without wasting so much time on optimization? Well, you could. All you had to do was use static typing. ---Dan
gudeman@cs.arizona.edu (David Gudeman) (03/15/91)
In article <PCG.91Mar13185855@aberdb.test.aber.ac.uk> Piercarlo Antonio Grandi writes:
]...
]1) Don't provide dynamic typing as a language primitive and make it
]prohibitive...
]
]2) Don't provide dynamic typing as a language primitive, and make it
]possible to implement it...
]
]3) Provide dynamic typing only...
]
]4) Provide *both* dynamic and static typing...
]
]I reckon that Gudeman thinks that Bernstein advocates 1), while
]Bernstein really advocates 2); Gudeman himself advocates 3), and I
]advocate 4).
No, Gudeman thinks that Bernstein advocates (2), Gudeman himself
advocates (4), and Gudeman is willing to accept Grandi's word that
Grandi advocates (4).
Didn't anyone read "Runtime Polymorphism... part 2"? OK, maybe part 1
one was so uninspiring that no one bothered with the sequal. Anyway,
in that posting I described my preference for a system with optional
static typing.
Maybe my bickering with the B&D language people over the importance of
static typing has lead people to believe that I am opposed to static
typing in all forms, but I am not. I am opposed to any language
feature that restricts my options and increases my effort in the name
of security. The language designer has no idea how much security my
program requires.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemanaipdc@castle.ed.ac.uk (Paul Crowley) (03/16/91)
In article <650@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >Maybe my bickering with the B&D language people So C is a B&D language. Wow. ____ \/ o\ Paul Crowley aipdc@uk.ac.ed.castle \ / /\__/ Part straight. Part gay. All queer. \/
pcg@test.aber.ac.uk (Piercarlo Antonio Grandi) (03/16/91)
On 13 Mar 91 07:48:23 GMT, gudeman@cs.arizona.edu (David Gudeman) said:
gudeman> I'm not entirely sure I understand what you are getting at, but
gudeman> that's never stopped me from talking before...
Same feelings on my side. I actually think that I expressed myself quite
obscurely, because it seems that we talking of different things...
gudeman> In article <PCG.91Mar12135254@aberda.test.aber.ac.uk> Piercarlo
gudeman> Antonio Grandi writes:
pcg> No, no, we have *two* misunderstanding here. I have never said that
pcg> in this example one need declare *explicitly* the types of the
pcg> arguments of an operator; simply, that a type is defined by the
pcg> operators that can be meaningfully applied to the values of that
pcg> type.
gudeman> What does "meaningfully applied" mean? In a dynamically typed
gudeman> language, any function can be legally applied to any value. So
gudeman> are you suggesting that every value has the same <type>? Or do
gudeman> you want "meaningfully applied" to mean that the function
gudeman> doesn't produce an error message when called with that value?
Let's say then that a type is the intersection of the codomains of a
given group of functions , or something like that.
gudeman> Then what do you do with something like
gudeman> procedure foo(x1,x2)
gudeman> if number(x1) then return x1 + x2
gudeman> else return x2
gudeman> end
gudeman> where x2 must be a number if x1 is, but otherwise can have any
gudeman> type?
This is the problem of procedures with multiple arguments. We all know
that it can be argued that functions with multiple arguments either have
a single structured argument or are functionals...
This said, let's arbitrarily choose the single composite argument view:
the procedure defines the type of all cartesian products where as you
say either the argument are both numeric, or are of any type at all. In
other words, this procedures by itself defines the type of all pairs,
because it will never fail on any pair of values.
gudeman> I think the whole concept is on shakey ground.
Not much more than other definitions of type... And probably much less,
because it gives an operative definition. Look at the intersection of
the codomains of a given group of functions, and that's a type.
Note that this includes the encoding functions, the typeof function, if
any, and so on. I know it is terribly difficult to "see". Maybe I have
not made very clear that that values and their denotations are *very*
different things in my view, thus encoding (and representation) is
crucial to my argument.
pcg> ... is regrettable and is only really an efficiency hack, just like
pcg> the one between 'eq' and 'equal', and it generates much the same
pcg> class of problems...
gudeman> An aside, 'eq' and 'equal' are semantically distinct. I would
gudeman> consider the language to be lacking an important operation if
gudeman> it were missing either one. The same applies to 'eql'. They
gudeman> all serve different purposes.
No, all, except 'equal', are redundant. We have already been thru this
discussion, and I still maintain that ideally if two values are the same
number, they *must* represent the same denotation. Saying that they
actually encode different denotations simply means, IMNHO, that actually
part of the value has been encoded in its address, which is an
efficiency hack.
pcg> This is wrong, as far as I can see, because then there is no way to
pcg> know the <type> or <typing> of a value... I think you are wrongly
pcg> assuming, in other words, in your definition above, that there is
pcg> some magic way to know which set a value belongs to, without
pcg> encoding it into the value itself...
gudeman> I wasn't making any assumptions about the representation of
gudeman> values.
Neither I am, but maybe I did not make it clear that to me <value> is
the same as <number>. Period.
gudeman> Frankly, I'm surprised to see representation come up at all,
gudeman> since I don't see what it has to do with the subject at hand
Because I am interested in <type> as in a computer, where all
denotations must be represented by a number which is some string of
digits base 256 (usually).
So, what's a type? Essentially, the (finite!) set of all the the bit
strings that a given set of functions can operate upon, because that's
about as good as you can get. Again, note that typeof maybe one of these
functions, and used by these functions as a filter, and then we have
<typing>, which is a far more restrictive idea.
gudeman> (unless you are thinking of <type> as a particular way of
gudeman> interpreting a group of bytes as a value. That doesn't fit
gudeman> your definition though.)
Well, it's close to that. Maybe we are reading different thing sin my
definition, maybe you are assuming that we have the same idea of what is
a <value>.
pcg> ... On the other hand if you encode the set into the value itself,
pcg> then you are defining types as equivalence classes, and your
pcg> definition and mine are exactly equivalent.
gudeman> Not at all. Your definition has the <type> of a value changing
gudeman> when new functions are added. Mine doesn't.
No, not necessarily, depends on two things: whether you add the new
functions to the group that defines the <type>, and then on whether the
new functions are more restrictive or not.
For example, if 'unsigned' is define by + and -, adding * does not
change the relevant set of values. But adding / does, because its
second argument can only belong to a set smaller than 'unsigned'.
So we have that bitstring '1' belongs to two <types> then.
Note: in the above the curried function view of multiple
argument is implicitly used.
gudeman> Then no separate notion of <typing> is needed.
pcg> ... The end result of your proposal is to drop the notion of <type>
pcg> and keep only that of <typing>, not viceversa.
gudeman> I'm throwing away your concept of <type>, as I said.
But I am trying to persuade you that <type> as distinct from <typing> is
a useful notion, at least as an ideal. Having a concept of <type> as I
see it does easily account for example for things like coercions,
multiple inheritance, and mutable typing, which are hard to explain well
if you only have <typing>.
pcg> ... when a new release of Unix switches the implementation of
pcg> /etc/passwd from a text file to an hash file, you need a program to
pcg> convert formats, whose role is essentially that of converting one
pcg> <type> to another to maintain ther illusion that <typing> has not
pcg> changed.
gudeman> The job of the program is to convert from one representation to
gudeman> another. The set of operations on the file has not changed, so
gudeman> the the <type> hasn't changed, by your definition.
No, it has, it has, because the set of operations also includes, and
here you miss I think one of the crucial points, the set of *encoding*
functions. I tried to be very clear about this; for example I have
written that under my definition
struct complex1 { float re,im; }
struct complex2 { float im,re; }
are two different *<types>*, even if their denotation is the same. Why?
Because the following two functions are *different*:
complex1 operator + (const complex1 a, const complex1 b)
{ return complex1(a.re+b.re,a+im,b+im); }
complex2 operator + (const complex2 a, const complex2 b)
{ return complex2(a.re+b.re,a+im,b+im); }
Because the .re and .im functions in each are *different*.
I think that you are missing that in my view of the world, given the two
struct definitions given above, .re and .im are two *functions* from 64
bit values into 32 bit values, and that they are overloaded on complex1
and complex2; something like:
float operator .re(complex1 c) { ... }
float operator .re(complex2 c) { ... }
float operator .im(complex1 c) { ... }
float operator .im(complex2 c) { ... }
Just to show you how radical is my approach, to me 32 bit floats are
just four digit base 256 numbers with peculiar definitions of +,-,...
(on most byte machines, that is).
gudeman> Again though, it looks like you mean <representation> when you
gudeman> say <type>.
Not the same thing, but it *includes* the encoding. I am not discussing
category theory, I am discussing <types> in computers languages, where
for example, all types are necessarily finite sets.
Maybe you are assuming that to me <value> == denotation, which is not
what I have written (this is a difficulty I have had with somebody else
by e-mail).
pcg> ... I know no language that IMNHO does a satisfactory job of
pcg> reconciling the gross rigidities of doing <typing> with the reality
pcg> that <types> are equivalence classes.
gudeman> Are you familiar with Common Lisp? What sort of type do you
gudeman> need that you can't define in that language?
In Common Lisp (minus CLOS) I can define the <typings> I want
(defstruct), but not <types>, not at all.
gudeman> How is an equivalence class different from a set? And what
gudeman> equivalence relation are you refering to?
We are really talking past each other. Let's say that at a level in
which unfortunately <typing> is already there, CLOS comes pretty close
to implementing my idea of types as equivalence classes of all values to
which a group of functions is applicable.
gudeman> It looks at times as though you mean $equiv(x,y) iff typeof(x)
gudeman> = typeof(y)$ -- which makes <type> and <typing> identical.
No, no, that is what *you* mean. That's <typing>:
gudeman> ... It also gives you a fairly simple way to define the result
gudeman> of the 'typeof' function(s)...
pcg> This is just <typing>, according to my terminology. You have thrown
pcg> away the notion of <type> entirely.
gudeman> Yeah, that's what I said. (I get the feeling we aren't
gudeman> communicating...)
I get the distinct feeling that while I see all your points, you disagree
because you don't see some of mine. It may be that maybe I have been too
terse :-).
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.ukram+@cs.cmu.edu (Rob MacLachlan) (03/16/91)
>>From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) >Subject: Re: Dynamic typing -- To Have and Have Not (was Runti >Date: 14 Mar 91 22:18:56 GMT > >For me compile time and typechecking are both important while I'm writing a >program. [...] Do you optimize programs while you're testing? Probably not. >But when each test run takes a noticeable amount of time, don't you wish >that you could make them run faster without wasting so much time on >optimization? > >Similarly, in a dynamically typed language, would you turn on strict >typechecking and other optimizations while you're testing? Probably not. I debug and test with typechecking on in Common Lisp, and so does everyone else I know. When properly supported (as in CMU Common Lisp), a powerful dynamic type system is a fairly general assertion mechanism, addressing consistency constraints outside the scope of conventional static typing systems. For example, you can: (declare (type (integer 3 27) i)) to say that I ranges from 3 to 47. And this assertion will be checked. The Common Lisp type system is general enough to express many interesting consistency constraints, but simple enough so that compilers can use it to do quite a bit of type inference. >But when you make type errors, don't you wish that you could have found >them without wasting so much time on optimization? Compilation speed is much less of a concern in environments that support incremental compilation. Although Lisp compilers tend to be rather slow compared to conventional compilers, Lisp seems faster because changes require much less recompilation. >Well, you could. All >you had to do was use static typing. Do your programs ever dump core? That's a run-time error check, just not a very graceful one. Most run-time type errors in Lisp systems are of the "dereferenceing off into space" sort, which can't be detected at compile time. Robert A. MacLachlan (ram@cs.cmu.edu)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/18/91)
In article <1991Mar16.052952.10201@cs.cmu.edu> ram+@cs.cmu.edu (Rob MacLachlan) writes: > I debug and test with typechecking on in Common Lisp, and so does everyone > else I know. I can't afford to use Lisp either: I don't find its slight advantages in expressiveness to outweigh its slowness for all but the simplest programs. Sure, these tradeoffs between compile time, run time, compile space, run space, programming time, maintenance time, etc. will vary by project and programmer---but static typing appears to greatly reduce debugging time without hurting speed or space or effort for the vast majority of projects. Why not take what you can get for free? In contrast, the supposed conciseness of dynamically typed languages costs dearly in compile time, run time, and (for projects with many debugging runs) programming time. For these disadvantages it would have to provide a huge benefit for maintenance, yet its proponents never seem to come up with examples showing such a benefit. > >Well, you could. All > >you had to do was use static typing. > Do your programs ever dump core? That's a run-time error check, just not a > very graceful one. Yes, and one which could quite often have been prevented by stronger compile-time checks. ---Dan
ram+@cs.cmu.edu (Rob MacLachlan) (03/19/91)
>From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) >Subject: Re: Dynamic typing -- To Have and Have Not (was Runti >Date: 18 Mar 91 03:21:05 GMT > >I can't afford to use Lisp either: I don't find its slight advantages in >expressiveness to outweigh its slowness for all but the simplest >programs. > If you are writing programs that can't afford a to run 50% to 100% longer than a tense C implementation, then don't use Lisp. The advantage of Lisp (and of object-oriented programming) is not in efficiency, but in ease of evolving solutions to poorly understood problems. I agree that compile time type checking is a good thing -- the Python compiler that I wrote for CMU Common Lisp does compile-time type checking wherever possible. If you want to, you can write statically type-checked programs in Common Lisp. This will get a compile-time type warning in CMU CL: (defvar *var* '(a b c)) (declaim (list *var*)) (defun foo () (+ *var* 13)) As I see it, the main difference between CL and a language such as C is that CL knows that it doesn't always know the types of objects, whereas C pretends that it does. I think that dynamic typing is especially valuable in an object-oriented programming system, since OO programs intensively manipulate references to mutable objects. It is very difficult to do static type checking in such an environment. Determining the power of the type system is a language design decision: -- The more of the language semantics you bring into the type system, the more complex inferences you can do at compile time. -- It is impossible to bring all the language semantics into the type system, since the only way to really find out what a program is going to do is to run it (the halting problem, etc.) This means that: -- More powerful type systems offer more opportunities for optimization, but are also harder for compilers to understand. -- In any language, some programming errors can only be detected at run time. > [...] static typing appears to greatly reduce >debugging time without hurting speed or space or effort for the vast >majority of projects. Well, you say it's so, and I say it ain't... Static type checking detects superficial errors; errors that would be detected if you tested that branch in the code just once. Such bugs may be common, but fixing them is quite easy in any language. Here is a concrete example of a programming problem that exemplifies what programmers in any OO language spend most of their *time* debugging: (do ((current foo (foo-next current))) ((eq (foo-a current) 'yow!) current)) We search down a linked list of FOOs for a FOO whose A is YOW!. If for some reason, it isn't there, then we fly off the end of the list (and get a run-time error.) This is a nasty bug, because the problem isn't determining *that* we flew off the end of the list, the problem is determining *why* YOW! wasn't in the list. And the only relevant tool that current languages offer is run-time assertions: (assert (find-in #'foo-next 'yow! foo :key #'foo-a))) Of course, you can do run-time consistency checks in any language. The point is that for finding the hard bugs, that is what you end up doing in any language. >> Do your programs ever dump core? That's a run-time error check, just not a >> very graceful one. > >Yes, and one which could quite often have been prevented by stronger >compile-time checks. I do seem some potential in powerful type-inferencing systems such as in ML, but even in these languages, run-time assertions are important. Rob MacLachlan (ram@cs.cmu.edu)
gudeman@cs.arizona.edu (David Gudeman) (03/19/91)
In article <PCG.91Mar15201131@aberdb.test.aber.ac.uk> Piercarlo Antonio Grandi writes:
]gudeman> What does "meaningfully applied" mean? In a dynamically typed
]gudeman> language, any function can be legally applied to any value...
]
]Let's say then that a type is the intersection of the codomains of a
]given group of functions , or something like that.
OK, so what is the codomain of a function? You have only pushed off
the problem, not solved it.
]This is the problem of procedures with multiple arguments. We all know
]that it can be argued that functions with multiple arguments either have
]a single structured argument or are functionals...
Not unless the appropriate tuples or functionals are in the language.
Otherwise you have to deal with real multi-argument functions. In any
case, you still haven't said what you mean by "meaningfully applied".
I don't believe you can make it mean anything outside of a statically
typed language.
]...values and their denotations are *very*
]different things in my view, thus encoding (and representation) is
]crucial to my argument.
OK, this is what you seem to be saying
<value> -- a bitstring
<encoding> -- a rule for translating <value>s to values and vice versa.
<denotation> -- the value represented by some <value> under some
<encoding>.
<type> -- an <encoding>.
The obvious question is: why try to redefine two useful commonly
understood terms, namely <value> and <type> to mean things that
already have perfectly good terms, respectively "bitstring" and
"encoding"? I know, you claim that <encoding> is only a part of
<type>, but I don't see it. You just say that a certain set of
functions use a certain <encoding> to interpret their arguments, and
that these functions define a <type>. But that is no different than
saying that a <type> is an <encodig>.
[about 'eq, 'eql, and 'equal]
]No, all, except 'equal', are redundant. We have already been thru this
]discussion,
(not with me)
]and I still maintain that ideally if two values are the same
]number, they *must* represent the same denotation.
Why?
] Saying that they
]actually encode different denotations simply means, IMNHO, that actually
]part of the value has been encoded in its address, which is an
]efficiency hack.
First, it is unlikely that the same bitstring represents two different
values. Rather, two different bitstrings may represent the same
value. But this is low-level implementation detail, and shouldn't
enter into a discussion of semantic issues.
Semantically, Lisp objects can be mutable, and when you have mutable
objects there is a difference between identicality of objects and
equivalence of values. Furthermore the difference is important for
algorithmic reasons, not for efficiency reasons. When you have two
lists, A and B, and you want to know if a side effect to A might
change B, you can't find out with 'equal.
]gudeman> I wasn't making any assumptions about the representation of
]gudeman> values.
]
]Neither I am, but maybe I did not make it clear that to me <value> is
]the same as <number>. Period.
You are assuming that values (<denotations>) are represented as
numbers (actually bitstrings). You are also assuming that the same
bitstring must represent a different value for different types.
Neither assumption is reasonable.
]... I am interested in <type> as in a computer, where all
]denotations must be represented by a number which is some string of
]digits base 256 (usually).
I am interested in <type> as in programming languages, where you don't
have to specify the hardware representation of values. Your
definitions are no more than a formalization of the way types and
values are implemented in statically typed languages. They are not
suitable for discussion of more general types of programming languages
nor for discussion of high-level, abstract issues.
]... Having a concept of <type> as I
]see it does easily account for example for things like coercions,
]multiple inheritance, and mutable typing, which are hard to explain well
]if you only have <typing>.
These things are all quite trivial to explain using the notion that a
type is a set or a unary predicate.
--
David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudemankers@hplb.hpl.hp.com (Chris Dollin) (03/19/91)
Dan Bernstein writes:
In contrast, the supposed conciseness of dynamically typed languages
costs dearly in compile time, run time, and (for projects with many
debugging runs) programming time. For these disadvantages it would have
to provide a huge benefit for maintenance, yet its proponents never seem
to come up with examples showing such a benefit.
Perhaps Dan would like to explain why dynamically typed languages "cost dearly
in compile-time", since the compiler is performing fewer checks? I can think of
three possible interpretations:
(a) The compiler is slower, because it has to generate extra code for the
necessary run-time checks.
Planting a few extra procedure calls is unlikely to take as much time as (say)
doing ML-style type unification.
(b) The compiler is faster, *but* it will be called on to compile entities very
many more times as their trivial type errors are detected.
Removing type errors doesn't tka that long (by observation). Also, for entities
that are complex enough that they take several passes before their type errors
are removed dynamically, they'll probably take several passes through the
static checking compiler - trashing any presumptive speed advantage.
(c) The compiler is written in the language it compiles, hence is dynamically
typed, hence is slow.
Begs the question. Also the compiler (being a relatively fixed application) may
have had optimisations applied to it - such as optional type declarations - to
make it go faster. It may have had optimisations applied to it that are only
possible by virtue of being dynamically typed.
Dan being Dan, he probably has some alternative (i) in mind; perhaps he would
enlighten us.
--
Regards, Kers. | "You're better off not dreaming of the things to come;
Caravan: | Dreams are always ending far too soon."oz@yunexus.yorku.ca (Ozan Yigit) (03/19/91)
In article <see ref> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I can't afford to use Lisp either: I don't find its slight advantages in >expressiveness to outweigh its slowness for all but the simplest >programs. Lisp or Scheme's advantages in expressiveness are not slight at all, but still, it is amusing to see you acknowledge the expressiveness of those languages you do not know much about _exceed_ those languages that you do know something about. Also, do you really understand what "expressiveness" mean? >In contrast, the supposed conciseness of dynamically typed languages >costs dearly in compile time, run time, and (for projects with many >debugging runs) programming time. Dan, you have no idea what you are talking about. oz
tmb@ai.mit.edu (Thomas M. Breuel) (03/20/91)
In article <22032@yunexus.YorkU.CA>, oz@yunexus.yorku.ca (Ozan Yigit) writes: |> >In contrast, the supposed conciseness of dynamically typed languages |> >costs dearly in compile time, run time, and (for projects with many |> >debugging runs) programming time. |> |> Dan, you have no idea what you are talking about. I wouldn't be quite so harsh. Static type checking is very good at eliminating a large fraction of those mistakes that people commonly make. As a side-benefit, simpler compilers are able to generate better code if type information is available at compile time. To me, polymorphic statically typed programming languages like ML are currently the best compromise between flexibility, compile-time checking, and efficiency.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/20/91)
In article <22032@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > Lisp or Scheme's advantages in expressiveness are not slight at all, but > still, it is amusing to see you acknowledge the expressiveness of those > languages you do not know much about _exceed_ those languages that you do > know something about. Indeed, and I'm glad to hear that you've stopped beating your children. Of the languages that I've used much, I find Forth the most expressive. Lisp and C come in way below, and several other languages (which, naturally, I've given up on) compete with Pascal and Fortran for the bottom of the bucket. I don't know enough about Scheme to judge it, but by all accounts it is more expressive than Fortran or C. Yet I continue to use C (and, when necessary, Fortran) much more than any other. Why? Because Forth is not portable, Lisp on anything but a Symbolics is so slow that my test runs often take ten times as long, and Ada compilers are snails. Expressiveness is nice. Anything syntactic is nice. But I don't need niceties. I need portability. I need fast compile times and run times so that the machine's turnaround time during testing and debugging doesn't become a significant part of my turnaround time. I need language power: full access to what the machine can do. Lisp doesn't have any of this. > Also, do you really understand what "expressiveness" mean? Yes, I think so. Do you? > >In contrast, the supposed conciseness of dynamically typed languages > >costs dearly in compile time, run time, and (for projects with many > >debugging runs) programming time. > Dan, you have no idea what you are talking about. Actually, I have a reasonably good idea of what I'm talking about. My comments on dynamically typed languages are based not only on my experience but also on many objective and subjective articles by both detractors from and proponents of such languages. As a matter of fact, if you want to buck the establishment, it's your problem to prove that dynamically typed languages aren't as inefficient as most experiments have found them to be. Would you write a compressor in a dynamically typed language? ---Dan
ram+@cs.cmu.edu (Rob MacLachlan) (03/20/91)
Subject: Re: blip [Re: Dynamic typing -- To Have and Have Not ...] Date: 19 Mar 91 23:59:35 GMT >Of the languages that I've used much, I find Forth the most expressive. Lisp >and C come in way below [...] Yet I continue to use C (and, when necessary, >Fortran) much more than any other. Why? Because Forth is not portable, Lisp >on anything but a Symbolics is so slow that my test runs often take ten times >as long, and Ada compilers are snails. Are you doing number crunching? If so, non-Symbolics Lisp products perform badly. But for other problems, Lispms have been surpassed in speed by Lisps running on conventional workstations (MIPS, SPARC, etc.) And CMU Common Lisp provides better-than-Lispm safety and debuggability with better-than-Lispm speed (not to mention cost-effectiveness.) CMU CL also offers good number crunching performance in real programs (5x Allegro.) >I need portability. I need fast compile times and run times so >that the machine's turnaround time during testing and debugging doesn't >become a significant part of my turnaround time. I need language power: >full access to what the machine can do. Lisp doesn't have any of this. I think that you overstate the case. Common Lisp is at least as portable as C, and Lisp systems offer unsurpassed compile-debug turnaround times (through incremental compilation.) "Full access to what the machine can do" is somewhat more nebulous. If you mean writing device drivers, then Lisp is not for you. But if you just mean that you want to use all the machine's primitive datatypes with reasonable efficiency, then Lisp *can* do this (although not all implementations provide as consistent support as CMU CL.) Common Lisp certainly wins big compared to, say Pascal, in that it has about all the operations that hardware implements (boolean arithmetic, bit-vectors, decode-float, all the flavors of division, etc.) >[...] if you want to buck the establishment, it's your problem to prove that >dynamically typed languages aren't as inefficient as most experiments have >found them to be. Some statements I am willing to defend: -- For some uses, efficiency isn't everything (research, prototyping, development.) -- For the things that C, Pascal, Modula, C++, etc. are used for, it is almost always possible to get a Lisp program to come withing a factor of two of the performance of these more conventional languages. (I am confining myself to general or "systems" programming, as opposed to data processing and scientific computing.) -- It can be very, very hard to get this good performance, but many of the performance tar-pits can be reliably negotiated when there is good compiler feedback. >Would you write a compressor in a dynamically typed language? If you mean something like the Unix system program "compress", then I wouldn't. But if your goal was to compress a complex input (like natural language) down to the smallest amount of space, with run-time relatively unimportant, then Lisp would be a good candidate. Rob MacLachlan (ram@cs.cmu.edu)
cs450a03@uc780.umd.edu (03/20/91)
Chris Dollin writes: >Perhaps Dan would like to explain why dynamically typed languages >"cost dearly in compile-time", since the compiler is performing fewer >checks? I can think of three possible interpretations: ... You missed one: That the compiler was thrown together in a "short" period of time, etc. And another: Because the compiler is intended to optimize the hell out of critical sections of code, it spends quite a bit of CPU on optimizing. Another one: That there is a poor match between language operations and machine architecture. Part of the fix for this is coding style, but it still feeds the other problems (makes them nice, healthy, well-fed problems). C'Est la vie. Raul Rockwell
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/20/91)
In article <KERS.91Mar19082354@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: > Perhaps Dan would like to explain why dynamically typed languages "cost dearly > in compile-time", since the compiler is performing fewer checks? You're right, I should have said ``costs dearly in either compile time or run time, and in either case (for projects with many debugging runs) programming time.'' My point is that I can't afford to make that choice except for projects where the compile time or run time is going to be very small no matter what language I use. That's rarely the case. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/20/91)
In article <1991Mar20.041716.4486@cs.cmu.edu> ram+@cs.cmu.edu (Rob MacLachlan) writes: > I think that you overstate the case. Common Lisp is at least as portable as > C, What world do you live in? About two-thirds of the UNIX systems I use can't even compile any of the available Lisps. In any case, portability is defined by what's out there, not what could be out there; and about 95% of the machines I use do *not* support Lisp even if they *could*. > and Lisp systems offer unsurpassed compile-debug turnaround times (through > incremental compilation.) ``Unsurpassed'' is exaggeration, and even if compile times were instant I'd spend forever just waiting for most programs to run. > But if you just mean that you want to use all the machine's > primitive datatypes with reasonable efficiency, No. A machine is much more than its ``primitive datatypes.'' But Lisp doesn't even provide full access to pointers. > >[...] if you want to buck the establishment, it's your problem to prove that > >dynamically typed languages aren't as inefficient as most experiments have > >found them to be. > -- For some uses, efficiency isn't everything (research, prototyping, > development.) In fact, I've been focusing on the prototyping and development stage of a program, because that's when it's most important to get good compile times *and* run times. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/20/91)
In article <896@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > In article <11820:Mar1923:59:3591@kramden.acf.nyu.edu> Dan Bernstein writes: > ]Of the languages that I've used much, I find Forth the most expressive. > Urp. OK, now I know you have a completely different concept of > expressiveness than I do. As they say, de syntactic gustibus non disputandum. Or something like that. It's natural that different people should find expressions more natural in different languages. What language do you find most expressive? Let me guess: BCPL? :-) ---Dan
quale@picard.cs.wisc.edu (Douglas E. Quale) (03/20/91)
In article <11820:Mar1923:59:3591@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >Actually, I have a reasonably good idea of what I'm talking about. My >comments on dynamically typed languages are based not only on my >experience but also on many objective and subjective articles by both >detractors from and proponents of such languages. As a matter of fact, And Dan also claims that debugging and program development is faster in a statically typed language than in a dynamically typed language. Since you claim your beliefs are based on your vast knowledge of the applicable literature, please give us a reference supporting this dubious claim. In another article Dan claims that Gnu Emacs is mostly written in C, "with a small amount of helper code." This is absolutely false. -- Doug Quale quale@khan.cs.wisc.edu
oz@yunexus.yorku.ca (Ozan Yigit) (03/21/91)
In article <see ref> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Indeed, and I'm glad to hear that you've stopped beating your children. I have no children, and likewise the suggested fallacy does not exist. My observation is based on your past and present statements indicating significant lack of insight into other programming languages you like to _talk_ about, e.g.: | No. A machine is much more than its ``primitive datatypes.'' But Lisp | doesn't even provide full access to pointers. Imagine that! ;-) >Of the languages that I've used much, I find Forth the most expressive. Good for you. It must be all the nice syntax. > I need fast compile times and run times so >that the machine's turnaround time during testing and debugging doesn't >become a significant part of my turnaround time. Use the right compiler [and the right machine] for fast compile times, right language for prototyping, and right environment for testing and debugging. [yawn] > I need language power: full access to what the machine can do. You seem to be confusing language "power" with language "level". > Lisp doesn't have any of this. Is this "have" the same as your previously re-defined "have" to mean something in relation to general computability, or is this something more meaningful and useful? >Actually, I have a reasonably good idea of what I'm talking about. My >comments on dynamically typed languages are based not only on my >experience but also on many objective and subjective articles by both >detractors from and proponents of such languages. Of course. Just as interesting, the neighbourhood cabbie was telling me about how he gave a ride to Elvis, and he had witnesses to prove it. So? >Would you write a compressor in a dynamically typed language? Silly question, despite its answer. 1988, compress.lisp [UN*X compress in Common Lisp] by Paul Fuqua, done. oz --- In seeking the unattainable, simplicity | Internet: oz@nexus.yorku.ca only gets in the way. -- Alan J. Perlis | Uucp: utai/utzoo!yunexus!oz
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/21/91)
In article <22075@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes: > In article <see ref> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > | No. A machine is much more than its ``primitive datatypes.'' But Lisp > | doesn't even provide full access to pointers. > Imagine that! ;-) It doesn't. I can't even find a Lisp for the Convex that takes advantage of array indexing: in C, p[i] runs as fast as *p on that machine, but since Lisp doesn't truly grok pointers it falls flat. Or is it heresy in your faith to even conceive of the idea that Lisp doesn't understand pointers as well as C? > > I need fast compile times and run times so > >that the machine's turnaround time during testing and debugging doesn't > >become a significant part of my turnaround time. > Use the right compiler [and the right machine] for fast compile times, Oh, what a *useful* suggestion. ``Your programs don't run fast enough? Buy a Cray.'' Believe it or not, even on the Cray, the compiler takes a noticeable amount of time, and there do exist programs that run for longer than a second. > > I need language power: full access to what the machine can do. > You seem to be confusing language "power" with language "level". No. Ada is in some ways more powerful than C: among its primitives, for example, are tasks. This doesn't make it higher-level or lower-level than C; it just adds some power, by providing more access to what the machine (in this case, OS) can do. > > Lisp doesn't have any of this. > Is this "have" the same as your previously re-defined "have" to mean > something in relation to general computability, or is this something > more meaningful and useful? Does ``any of this'' refer to some semantic feature of a programming language? No. Therefore my previously defined ``have'' does not apply here. You understand overloaded operations; why don't you understand overloaded words? > Of course. Just as interesting, the neighbourhood cabbie was telling me > about how he gave a ride to Elvis, and he had witnesses to prove it. So? Hey, bud, you started. > >Would you write a compressor in a dynamically typed language? > Silly question, despite its answer. 1988, compress.lisp [UN*X compress in > Common Lisp] by Paul Fuqua, done. You didn't answer the question. Would you write a compressor in a dynamically typed language? I wouldn't, because each compile run takes a noticeable amount of time, and each test run takes a noticeable amount of time. If I used a dynamically typed language, I'd lose big on either compile time, run time, or both. That can mean the difference between a week and a month in project turnaround time, not to mention a slower final program. The dynamic-typing people claim that I'll get it all back in maintenance, because my program will be shorter. I don't believe them: dynamic typing wouldn't simplify my huptrie.h, for example. They claim that I won't have as many testing and debugging runs. Sorry, but it just isn't true: practically every bug I found and behavior I changed would have been found and changed the same way in most languages, and I have the project logs to prove it. Maybe it's a silly question, but for me it exemplifies what's wrong with dynamically typed languages. ---Dan
kers@hplb.hpl.hp.com (Chris Dollin) (03/21/91)
Dan tails with: Would you write a compressor in a dynamically typed language? Odd you should ask that, but when I was trying to understand LZ compression, I did just that. It was fast enough. For a production version, I would have tightened up the code, using my knowledge of the properties of the program - including types, of course. [Actually I rewrote it in C because Pop11 wasn't - and alas, still isn't - available on my home machine, but C is. Over the next year or so my Pop clone should gradually start to generate native code; it will be an interesting experiment to compare speeds then.] -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
kers@hplb.hpl.hp.com (Chris Dollin) (03/21/91)
Dan replies: You're right, I should have said ``costs dearly in either compile time or run time, and in either case (for projects with many debugging runs) programming time.'' My point is that I can't afford to make that choice except for projects where the compile time or run time is going to be very small no matter what language I use. That's rarely the case. OK, but I'm still puzzled as to why you included the option of dearer compile-time costs at all. Can you illustrate a case where a compiler for a dynamically-typed language is *slower* than a compiler for a statically typed language - when the compiler is written in the same language for both (ie, we're comparing apples and apples)? As it happens, I have been writing a program in a dynamically-checked language recently - a typechecker [ironic, eh?] for a specification language. I am happy to report that the number of *type* errors that occurred was trivially small; perhaps once there was a type error that took me longer then fiven minutes to track dowm. [Usually it's a case of "bugger, forgot to change the call of rename_sigentry in copy_module"; static typechecking would have caught it about thirty seconds earlier.] I am also happy to report that the genuine logical errors could not have been caught by anything short of a full theorem prover operating from a fully correct abstract specification. [I just timed how long it took to load the complete typechecker into the system, starting from Unix command-line prompt and including the time it took to type "load loader.p" to the editor; 1min 6sec for compiling 8000 lines of source to MC68K machine code, on an HP9000/350. This time includes the program setup-time (it constructs various tables of built-in identifiers on the way, and reads a file describing the parse-tree magic numbers). Compiling the database component from the toolset - written in C with a small Yacc grammar - took 8 minutes for about 12000 lines of code, not including the time it would take to build the standard library components; same machine, of course. The figures are open to interpretation, but they're datapoints.] [By the way, Dan, if you find Forth "expressive", you might like Pop; Forth's open stack, sort-of Lispy datatypes, conventional syntax.] -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
lavinus@csgrad.cs.vt.edu (03/22/91)
Hello, Type warriors...
I was meaning to stay out of this, but alas...
Do people out there really think that any one language is good for all applications?
Obviously, if you want to write a UN*X device driver, you do it in C, and if you want
to do heavy number crunching, you do it in Fortran (for speed), or better yet, in
Occam or something on a multiprocessor. There are some applications for which dynamic
typing makes programming infinitely easier, and there are some for which dynamic
typing gains you little, and thus is not worth the efficiency hit (which is often
minor - compare programs written in C and Yale's T dialect of Lisp/Scheme sometime).
Aside from all that, expressiveness is more a matter of taste than anything else -
some people just naturally think in one paradigm or another. The arguments are thus
rendered rather pointless - it's not as though when this argument is won, we're
going to remove from existence all languages which belong to the losing side (that's
assuming the argument *can* be won). It all comes down to something like, "Oh yeah,
well my Scheme compiler can beat up your C compiler..." :-)
Ah well, on with the flames...
Joe
--
_______________________________________________________________
_ _ __
Joseph W. Lavinus (lavinus@csgrad.cs.vt.edu) | / \ |_
Virginia Tech, Blacksburg, Virginia __| \_/ |_amanda@visix.com (Amanda Walker) (03/22/91)
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > | Lisp doesn't even provide full access to pointers. > Imagine that! ;-) It doesn't. That depends on the Lisp. T, for example, not only has a very good compiler, but provides a data type called a "locative" that acts like a pointer, but doesn't even get confused when GCs happen. Most modern Lisps provide just as much machine-level access as, say, C does. Or is it heresy in your faith to even conceive of the idea that Lisp doesn't understand pointers as well as C? In my case, it's more experience than faith. Have you actually looked at what's been going on in the Lisp world over the past 5-7 years? You might be very surprised. Would you write a compressor in a dynamically typed language? Yes. In fact, I'd *rather* write a compressor in a dynamically typed language. I wouldn't, because each compile run takes a noticeable amount of time, and each test run takes a noticeable amount of time. That has mostly to do with the particular compiler you are using, and not much to do with any inherent properties of the language itself. The fact that C may be easier to compile (for some value of "easier") than Lisp is a separate claim, and one I would be happy to concede. However, ease of compilation is not the constraining factor in software development. If it were, we'd all be using assembler. Not that C is very much of an improvement, mind you... Maybe it's a silly question, but for me it exemplifies what's wrong with dynamically typed languages. From what you've said so far, it sounds like descriptions of what's wrong with the state of much the commercial dynamically-type language market. On that I have no argument, but I think that blaming this on the fact that a language is dynamically typed is bordering on religious belief. -- Amanda Walker amanda@visix.com Visix Software Inc. ...!uunet!visix!amanda -- "Many of the truths we cling to depend greatly on our point of view." --Obi-Wan Kenobi in "The Empire Strikes Back"
kend@data.UUCP (Ken Dickey) (03/23/91)
{Warning: I have not been following this thread}
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>... Would you write a compressor in a
>dynamically typed language? I wouldn't, because each compile run takes a
>noticeable amount of time, and each test run takes a noticeable amount
>of time. If I used a dynamically typed language, I'd lose big on either
>compile time, run time, or both. That can mean the difference between a
>week and a month in project turnaround time, not to mention a slower
>final program.
Interesting. I don't know what languages you typically use [Pascal,
Eiffel, C?], but find many more good environments for fast program
development in dynamically typed languages. If you want fast code,
there are some good Scheme compilers around.
Of course, I write software systems, not just programs. If you are
doing device drivers, and really require speed, make use of your local
assembler and the hardware caches.
-Ken Dickey kend@data.uucpbrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/26/91)
In article <KERS.91Mar21121931@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: > OK, but I'm still puzzled as to why you included the option of dearer > compile-time costs at all. Can you illustrate a case where a compiler for a > dynamically-typed language is *slower* than a compiler for a statically typed > language - when the compiler is written in the same language for both (ie, > we're comparing apples and apples)? Many people have spent many years trying to optimize dynamically typed languages (i.e., to get rid of the dynamic typing in the object code), with some success. When a compiler *doesn't* optimize a dynamically typed language, the final code is hellishly slow (as in most Lisps). ---Dan
rick@cua.cary.ibm.com (Rick DeNatale) (03/26/91)
In article <14160@life.ai.mit.edu> tmb@ai.mit.edu writes: >I wouldn't be quite so harsh. Static type checking is very good >at eliminating a large fraction of those mistakes that people >commonly make. There seems to be a discrepancy between reporters on this issue that is language dependent. Type errors seem to be a big source of errors in C but seem to appear rarely in Smalltalk programs. At least this is true in my own experiences and others that I have talked to agree. In Smalltalk the most common errors seem to be object state problems. I think that there is a reason for this, and it has to do with the purity of object orientation extending down to the implementation/realization level. In most 'normal' programming languages, a type error occurs when you present a string of bits to a piece of code that expects to interpret that string of bits in a particular way (short integer, float, char *, class foo), and the bits aren't actually the right type of bits. In a pure object oriented implementation, you just can't give the wrong string of bits to a piece of code, the method dispatching sees to that. I'm actually a little bit surprised that people put so much faith in compile time type checking systems that they are willing to accept an implementation that allows type errors that escape the compiler to cause wild branches and other unsavory acts, and then demand that such stuff is required for "industrial strength". I haven't seen a strong typing system yet that doesn't require you to (hopefully carefully) circumvent it at times, or that is absolutely bullet proof even without circumvention (array bounds checking, overflows etc.). It takes real confidence to work in dangerous environments without safety equipment. Or maybe it's a less desirable quality than confidence! Rick DeNatale
kers@hplb.hpl.hp.com (Chris Dollin) (03/26/91)
Dan responds: In article [one of mine] Chris Dollin writes: > OK, but I'm still puzzled as to why you included the option of dearer > compile-time costs at all. Can you illustrate a case where a compiler for a > dynamically-typed language is *slower* than a compiler for a statically typed > language - when the compiler is written in the same language for both (ie, > we're comparing apples and apples)? Many people have spent many years trying to optimize dynamically typed languages (i.e., to get rid of the dynamic typing in the object code), with some success. When a compiler *doesn't* optimize a dynamically typed language, the final code is hellishly slow (as in most Lisps). Sorry, Dan, but this doesn't answer my question - can you tell us about a case where a compiler in language L for a dynamically typed language D was slower than a compiler in L for a statically typed language S, because of the absence of compile-time type-testing? As for ``the final code is hellishly slow'' when the compiler does not attempt to optimise out dynamic typing, what sort of factor are you talking about? 2? 10? 100? [I'm prepared to pay a factor of 2, I'd be reluctant about a factor of 10, and would regard a factor of 100 as dreadful.] As one of my earlier postings remarked, the Pop compiler (written in Pop11, a DTL) compiles Pop code about 5 times faster than an HP-UX ANSI C compiler (written in C, an STL). All other things are grossly unequal, of course, because the C compiler is repeatedly re-reading header files because of separate compilation, and because we are liberal with our use of repeated include files; if all that accounts for a factor of 5 I'd be surprised. I presume you mean that ``optimising out dynamic typing can be slow''. Sure. Optimising compilers can be slow - gcc takes what seems an outlandishly long time compiling one of my modules, because it's a single 800 line procedure. (The Acorn C compiler is even slower on this example.) More will follow when I've time to gather my thoughts ... -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (03/27/91)
In article <KERS.91Mar26111126@cdollin.hpl.hp.com> kers@hplb.hpl.hp.com (Chris Dollin) writes: > Sorry, Dan, but this doesn't answer my question Look, static typing gives me both fast compile times and fast run times. Dynamic typing used to lose big on run times; all the interesting recent work on dynamically typed languages has been in optimization, but for those reasonably competitive run times they lose big on compile times. Why should I pay that price, especially during development when I need both fast compiles and fast runs for good turnaround? > As for ``the final code is hellishly slow'' when the compiler does not attempt > to optimise out dynamic typing, what sort of factor are you talking about? 2? > 10? 100? Between 2 and 10. It usually depends on how many of the library routines have been written in a faster language. ---Dan
jls@rutabaga.Rational.COM (Jim Showalter) (03/27/91)
>I'm actually a little bit surprised that people put so much faith in compile >time type checking systems that they are willing to accept an implementation >that allows type errors that escape the compiler to cause wild branches and >other unsavory acts, and then demand that such stuff is required for >"industrial strength". Who are these people? I'D certainly never accept such an implementation. I demand strong compile time checking AND a validated compiler. But then. that's why I prefer to work in Ada. >I haven't seen a strong typing system yet that doesn't require you to >(hopefully carefully) circumvent it at times, Agreed. But the point is that in a properly designed language you have to go out of your way (by design) to effect such circumvention. >or that is absolutely bullet >proof even without circumvention (array bounds checking, overflows etc.). Ada may not be completely bulletproof, but the examples you cite it certainly detects and traps. -- ***** DISCLAIMER: The opinions expressed herein are my own. Duh. Like you'd ever be able to find a company (or, for that matter, very many people) with opinions like mine. -- "When I want your opinion, I'll read it in your entrails."
rick@cua.cary.ibm.com (Rick DeNatale) (03/28/91)
In article <jls.670045356@rutabaga> jls@rutabaga.Rational.COM (Jim Showalter) writes: >>I'm actually a little bit surprised that people put so much faith in compile >>time type checking systems that they are willing to accept an implementation >>that allows type errors that escape the compiler to cause wild branches and >>other unsavory acts, and then demand that such stuff is required for >>"industrial strength". > >Who are these people? I'D certainly never accept such an implementation. >I demand strong compile time checking AND a validated compiler. But then. >that's why I prefer to work in Ada. > >>I haven't seen a strong typing system yet that doesn't require you to >>(hopefully carefully) circumvent it at times, > >Agreed. But the point is that in a properly designed language you have >to go out of your way (by design) to effect such circumvention. > So even with a validated compiler, you still need validated programmers, or you have to limit what you can do. Rick Denatale ** Of course my opinion is my own, who else would have it!
px@fct.unl.pt (Joaquim Baptista [pxQuim]) (04/02/91)
In article <879@puck.mrcu> paj@mrcu (Paul Johnson) writes:
On the other hand I am interested in the assertion that type errors
are rare in Smalltalk development. Does anyone have any statistics to
back this up? I think this discussion could probably do with an
injection of fact, lest it degenerate into a language flame war.
I do not have any hard data, but I believe that I can give you a give
argument for it.
In a strongly typed language such as Eiffel, the programmer must
declare the type of all its variables, arguments, and such. If the
programmer later changes its mind, these type declarations must be
updated everywhere, which is a tedious and error-prone process.
Having no types just means that this sort of error does not happen,
while the other kinds of error probably remain at the same level.
--
Joaquim Manuel Soares Baptista, aka px@fct.unl.pt, px@unl.uucp
Snail: CRIA, UNINOVA, FCT/UNL, 2825 Mt Caparica, Portugal
So long, and thanks for all the fish.pallas@eng.sun.com (Joseph Pallas) (04/03/91)
In <PX.91Apr1225918@hal.fct.unl.pt> px@fct.unl.pt (Joaquim Baptista [pxQuim]) writes: >Having no types ... Nope, try again. How about, "Having no declared types ..." >just means that this sort of error does not happen, Nope, try again. How about, "just means that this sort of error is not detected at compile time, but at run time," >while the other kinds of error probably remain at the same level. People who think that dynamically typed languages result in typeless programs need to reflect on what they are doing when they write their programs. If your program operates on some object, you can be certain that there is a type implied by that operation. joe
new@ee.udel.edu (Darren New) (04/03/91)
In article <879@puck.mrcu> paj@uk.co.gec-mrc (Paul Johnson) writes: >On the other hand I am interested in the assertion that type errors >are rare in Smalltalk development. Does anyone have any statistics to >back this up? Well, I have one statis. :-) My dissertation project is implemented in Smalltalk. I've been working on it for four years or so, and I've gotten three types of type-mismatch errors (i.e., "message not understood"): 1) Looked up a name in the wrong dictionary, didn't check the result because I "knew" it would always be there, sent the result (nil, because it wasn't found) a message, and "nil" didn't understand it. Not a type error because the problem was the wrong dictionary, not the wrong type. Some other runtime error (subscript out of bounds, say) would have happened in another language. 2) Sent a message to a string instead of to the result of looking up that string in a dictionary. Always caught on the first test run. 3) Sent a message to an object which should have implemented that message but didn't because I didn't think it would be called on this particular test run. Always caught the first time. In summary, "wrong type" errors just never really came up because they were the wrong type except number 2. In that case, it was always invariably caught on the first run of that method. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, FDTs ----- +=+=+ My time is very valuable, but unfortunately only to me +=+=+ + When you drive screws with a hammer, screwdrivers are unrecognisable +
px@fct.unl.pt (Joaquim Baptista [pxQuim]) (04/03/91)
REPOST WITH CORRECTION:
In a strongly typed language such as Eiffel, the programmer must
declare the type of all its variables, arguments, and such. If the
programmer later changes its mind, these type declarations must be
updated everywhere, which is a tedious and error-prone process.
---vv---
Having no declared types just means that this sort of error does not happen,
while the other kinds of error probably remain at the same level.
REPLY TO JOSEPH PALLAS:
In article <pallas.670613621@red-dwarf> pallas@eng.sun.com (Joseph Pallas) writes:
In <PX.91Apr1225918@hal.fct.unl.pt> I wrote:
>Having no types ...
Nope, try again. How about, "Having no declared types ..."
Thank you. That was what I wanted to say.
>just means that this sort of error does not happen,
Nope, try again. How about, "just means that this sort of error is
not detected at compile time, but at run time,"
>while the other kinds of error probably remain at the same level.
People who think that dynamically typed languages result in typeless
programs need to reflect on what they are doing when they write their
programs. If your program operates on some object, you can be certain
that there is a type implied by that operation.
My previous posting obviously was ill written if people can interpret
it to mean something that I do not think at all.
Programmers ALWAYS think in types, even when the language is typeless
(in the sense of having a single universal "type", as Lisp or Prolog).
An entirely different matter is wether the programmer should be
required to declare the types of everything. I state that doing this
is error-prone, specially when the programmer changes some type.
Type declarations detect type errors, but these errors tend to be
"book keeping errors", instead of errors in the logic of the algorithm
or some other "higher" errors.
About compile time versus run tim