[28010] in Perl-Users-Digest
Perl-Users Digest, Issue: 9374 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Sun Jun 25 09:10:12 2006
Date: Sun, 25 Jun 2006 06:10:06 -0700 (PDT)
From: Perl-Users Digest <Perl-Users-Request@ruby.OCE.ORST.EDU>
To: Perl-Users@ruby.OCE.ORST.EDU (Perl-Users Digest)
Perl-Users Digest Sun, 25 Jun 2006 Volume: 10 Number: 9374
Today's topics:
Re: What is Expressiveness in a Computer Language <gneuner2/@comcast.net>
Re: What is Expressiveness in a Computer Language <anton@appsolutions.com>
Re: What is Expressiveness in a Computer Language <anton@appsolutions.com>
Re: What is Expressiveness in a Computer Language rossberg@ps.uni-sb.de
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Re: What is Expressiveness in a Computer Language <jo@durchholz.org>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: Sun, 25 Jun 2006 03:26:33 -0400
From: George Neuner <gneuner2/@comcast.net>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <1kcs92pmg156qdg89ksfuuslgv6njcvkt3@4ax.com>
On 22 Jun 2006 08:42:09 -0700, rossberg@ps.uni-sb.de wrote:
>Darren New schrieb:
>> I'm pretty sure in Pascal you could say
>>
>> Type Apple = Integer; Orange = Integer;
>> and then vars of type apple and orange were not interchangable.
>
>No, the following compiles perfectly fine (using GNU Pascal):
>
> program bla;
> type
> apple = integer;
> orange = integer;
> var
> a : apple;
> o : orange;
> begin
> a := o
> end.
You are both correct.
The original Pascal specification failed to mention whether user
defined types should be compatible by name or by structure. Though
Wirth's own 1974 reference implementation used name compatibility,
implementations were free to use structure compatibility instead and
many did. There was a time when typing differences made Pascal code
completely non-portable[1].
When Pascal was finally standardized in 1983, the committees followed
C's (dubious) example and chose to use structure compatibility for
simple types and name compatibility for records.
[1] Wirth also failed to specify whether boolean expression evaluation
should be short-circuit or complete. Again, implementations went in
both directions. Some allowed either method by switch, but the type
compatibility issue continued to plague Pascal until standard
conforming compilers emerged in the mid 80's.
George
--
for email reply remove "/" from address
------------------------------
Date: Sun, 25 Jun 2006 07:38:53 GMT
From: Anton van Straaten <anton@appsolutions.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <h4rng.108670$H71.33586@newssvr13.news.prodigy.com>
David Hopwood wrote:
> But since the relevant feature that the languages in question possess is
> dynamic tagging, it is more precise and accurate to use that term to
> describe them.
So you're proposing to call them dynamically-tagged languages?
> Also, dynamic tagging is only a minor help in this respect, as evidenced
> by the fact that explicit tag tests are quite rarely used by most programs,
> if I'm not mistaken.
It sounds as though you're not considering the language implementations
themselves, where tag tests occur all the time - potentially on every
operation. That's how "type errors" get detected. This is what I'm
referring to when I say that dynamic tags support latent types.
Tags are absolutely crucial for that purpose: without them, you have a
language similar to untyped lambda calculus, where "latent type errors"
can result in very difficult to debug errors, since execution can
continue past errors and produce completely uninterpretable results.
> IMHO, the support does not go far enough for it to be
> considered a defining characteristic of these languages.
Since tag checking is an implicit feature of language implementations
and the language semantics, it certainly qualifies as a defining
characteristic.
> When tag tests are used implicitly by other language features such as
> pattern matching and dynamic dispatch, they are used for purposes that are
> equally applicable to statically typed and non-(statically-typed) languages.
A fully statically-typed language doesn't have to do tag checks to
detect static type errors.
Latently-typed languages do tag checks to detect latent type errors.
You can take the preceding two sentences as a summary definition for
"latently-typed language", which will come in handy below.
>>>or that languages
>>>that use dynamic tagging are "latently typed". This simply is not a
>>>property of the language (as you've already conceded).
>>
>>Right. I see at least two issues here: one is that as a matter of
>>shorthand, compressing "language which supports latent typing" to
>>"latently-typed language" ought to be fine, as long as the term's
>>meaning is understood.
>
>
> If, for the sake of argument, "language which supports latent typing" is
> to be compressed to "latently-typed language", then statically typed
> languages must be considered also latently typed.
See definition above. The phrase "language which supports latent
typing" wasn't intended to be a complete definition.
> After all, statically typed languages support expression and
> verification of the "types in the programmer's head" at least as well
> as non-(statically-typed) languages do. In particular, most recent
> statically typed OO languages use dynamic tagging and are memory safe.
> And they support comments ;-)
But they don't use tags checks to validate their static types.
When statically-typed languages *do* use tags, in cases where the static
type system isn't sufficient to avoid them, then indeed, those parts of
the program use latent types, in the exact same sense as more fully
latently-typed languages do. There's no conflict here, it's simply the
case that most statically-typed languages aren't fully statically typed.
> This is not, quite obviously, what most people mean when they say
> that a particular *language* is "latently typed". They almost always
> mean that the language is dynamically tagged, *not* statically typed,
> and memory safe. That is how this term is used in R5RS, for example.
The R5RS definition is compatible with what I've just described, because
the parts of a statically-typed language that would be considered
latently-typed are precisely those which rely on dynamic tags.
>>But beyond that, there's an issue here about the definition of "the
>>language". When programming in a latently-typed language, a lot of
>>action goes on outside the language - reasoning about static properties
>>of programs that are not captured by the semantics of the language.
>
>
> This is true of programming in any language.
Right, but when you compare a statically-typed language to an untyped
language at the formal level, a great deal more static reasoning goes on
outside the language in the untyped case.
What I'm saying is that it makes no sense, in most realistic contexts,
to think of untyped languages as being just that: languages in which the
type of every term is simply a tagged value, as though no static
knowledge about that value exists. The formal model requires that you
do this, but programmers can't function if that's all the static
information they have. This isn't true in the case of a fully
statically-typed language.
>>This means that there's a sense in which the language that the
>>programmer programs in is not the same language that has a formal
>>semantic definition. As I mentioned in another post, programmers are
>>essentially mentally programming in a richer language - a language which
>>has informal (static) types - but the code they write down elides this
>>type information, or else puts it in comments.
>
>
> If you consider stuff that might be in the programmer's head as part
> of the program, where do you stop? When I maintain a program written
> by someone I've never met, I have no idea what was in that programmer's
> head. All I have is comments, which may be (and frequently are,
> unfortunately) inaccurate.
You have to make the same kind of inferences that the original
programmer made. E.g. when you see a function that takes some values,
manipulates them using numeric operators, and returns a value, you have
to either figure out or trust the comments that the function accepts
numbers (or integers, floats etc.) and returns a number.
This is not some mystical psychological quality: it's something that
absolutely must be done in order to be able to reason about a program at
all.
> (Actually, it's worse than that -- if I come back to a program 5 years
> later, I probably have little idea what was in my head at the time I
> wrote it.)
But that's simply the reality - you have to reconstruct: recover the
latent types, IOW. There's no way around that!
Just to be concrete, I'll resurrect my little Javascript example:
function timestwo(x) { return x*2 }
Assume I wrote this and distributed it in source form as a library, and
now you have to maintain it. How do you know what values to call it
with, or what kind of values it returns? What stops you from calling it
with a string?
Note that according the formal semantics of an untyped language, the
type of that function is "value -> value".
The phrase "in the programmer's head" was supposed to help communicate
the concept. Don't get hung up on it.
>>We have to accept, then, that the formal semantic definitions of
>>dynamically-checked languages are incomplete in some important ways.
>>Referring to those semantic definitions as "the language", as though
>>that's all there is to the language in a broader sense, is misleading.
>
>
> Bah, humbug. The language is just the language.
If you want to have this discussion precisely, you have to do better
than that. There is an enormous difference between the formal semantics
of an untyped language, and the (same) language which programmers work
with and think of as "dynamically typed".
Use whatever terms you like to characterize this distinction, but you
can't deny that the distinction exists, and that it's quite a big,
important one.
>>In this context, the term "latently-typed language" refers to the
>>language that a programmer experiences, not to the subset of that
>>language which is all that we're typically able to formally define.
>
>
> I'm with Marshall -- this is way too mystical for me.
I said more in my reply to Marshall. Perhaps I'm not communicating
well. At worst, what I'm talking about is informal. It's easy to prove
that you can't reason about a program if you don't know what types of
values a function accepts or returns - which is what an untyped formal
model gives you.
Anton
------------------------------
Date: Sun, 25 Jun 2006 08:10:34 GMT
From: Anton van Straaten <anton@appsolutions.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <_xrng.108673$H71.2451@newssvr13.news.prodigy.com>
Marshall wrote:
> Chris F Clark wrote:
>
>>I'm particularly interested if something unsound (and perhaps
>>ambiguous) could be called a type system. I definitely consider such
>>things type systems.
>
>
> I don't understand. You are saying you prefer to investigate the
> unsound over the sound?
The problem is that there are no useful sound definitions for the type
systems (in the static sense) of dynamically-typed languages. Yet, we
work with type-like static properties in those languages all the time,
as I've been describing.
If you want to talk about those properties as though they were types,
one of the options is what Chris Clark described when he wrote "I reason
about my program using types which I can (at least partially) formalize,
but for which there is no sound axiomatic system."
>>However, I like my definitions very general and
>>vague. Your writing suggests the opposite preference.
>
>
> Again, I cannot understand this. In a technical realm, vagueness
> is the opposite of understanding. To me, it sounds like you are
> saying that you prefer not to understand the field you work in.
The issue as I see it is simply that if we're going to work with
dynamically-typed programs at all, our choices are limited at present,
when it comes to formal models that capture our informal static
reasoning about those programs. In statically-typed languages, this
reasoning is mostly captured by the type system, but it has no formal
description for dynamically-typed languages.
>>To me if
>>something works in an analogous way to how a known type system, I tend
>>to consider it a "type system". That probably isn't going to be at
>>all satisfactory to someone wanting a more rigorous definition.
>
>
> Analogies are one thing; definitions are another.
A formal definition is problematic, precisely because we're dealing with
something that to a large extent is deliberately unformalized. But as
Chris Clark pointed out, "these types are locally sound, i.e. I can
prove properties that hold for regions of my programs." We don't have
to rely entirely on analogies, and this isn't something that's entirely
fuzzy. There are ways to relate it to formal type theory.
>>Of
>>course, to my mind, the rigorous definitions are just an attempt to
>>capture something that is already known informally and put it on a
>>more rational foundation.
>
>
> If something is informal and non-rational, it cannot be said to
> be "known."
As much as I love the view down into that abyss, we're nowhere near
being in such bad shape.
We know that we can easily take dynamically-typed program fragments and
assign them type schemes, and we can make sure that the type schemes
that we use in all our program fragments use the same type system.
We know that we can assign type schemes to entire dynamically-typed
programs, and we can even automate this process, although not without
some practical disadvantages.
So we actually have quite a bit of evidence about the presence of static
types in dynamically-typed programs.
Besides, we should be careful not to forget that our formal methods are
incredibly weak compared to the power of our intelligence. If that were
not the case, there would be no advantage to possessing intelligence, or
implementing AIs.
We are capable of reasoning outside of fully formal frameworks. The
only way in which we are able to develop formal systems is by starting
with the informal.
We're currently discussing something that so far has only been captured
fairly informally. If we restrict ourselves to only what we can say
about it formally, then the conversation was over before it began.
Anton
------------------------------
Date: 25 Jun 2006 01:40:44 -0700
From: rossberg@ps.uni-sb.de
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <1151224844.569347.167420@r2g2000cwb.googlegroups.com>
Marshall wrote:
> >
> > This means that there's a sense in which the language that the
> > programmer programs in is not the same language that has a formal
> > semantic definition. As I mentioned in another post, programmers are
> > essentially mentally programming in a richer language - a language which
> > has informal (static) types - but the code they write down elides this
> > type information, or else puts it in comments.
> >
> > [...]
> >
> > In this context, the term "latently-typed language" refers to the
> > language that a programmer experiences, not to the subset of that
> > language which is all that we're typically able to formally define.
That language is not a subset, if at all, it's the other way round, but
I'd say they are rather incomparable. That is, they are different
languages.
> That is starting to get a bit too mystical for my tastes.
I have to agree.
\sarcasm One step further, and somebody starts calling C a "latently
memory-safe language", because a real programmer "knows" that his code
is in a safe subset... And where he is wrong, dynamic memory page
protection checks will guide him.
- Andreas
------------------------------
Date: Sun, 25 Jun 2006 13:42:45 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7lsr6$iqm$1@online.de>
George Neuner schrieb:
> The point is really that the checks that prevent these things must be
> performed at runtime and can't be prevented by any practical type
> analysis performed at compile time. I'm not a type theorist but my
> opinion is that a static type system that could, a priori, prevent the
> problem is impossible.
No type theory is needed.
Assume that the wide index type goes into a function and the result is
assigned to a variable fo the narrow type, and it's instantly clear that
the problem is undecidable.
Undecidability can always be avoided by adding annotations, but of
course that would be gross overkill in the case of index type widening.
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 13:48:04 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7lt55$kff$1@online.de>
Dimitri Maziuk schrieb:
> That is the basic argument in favour of compile time error checking,
> extended to runtime errors. I don't really care if it's the compiler
> or runtime that tells the luser "your code is broken", as long as it
> makes it clear it's *his* code that's broken, not mine.
You can make runtime errors point to the appropriate code. Just apply
"programming by contract": explicitly state what preconditions a
function is requiring of the caller, have it check the preconditions on
entry (and, ideally, throw the execption in a way that the error is
reported in the caller's code - not a complicated thing but would
require changes in the exception machinery of most languages).
Any errors past that point are either a too liberal precondition (i.e. a
bug in the precondition - but documenting wrong preconditions is still a
massive bug, even if it's "just" a documentation bug), or a bug in the
function's code.
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 14:12:47 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7lujg$q2r$1@online.de>
rossberg@ps.uni-sb.de schrieb:
> Joachim Durchholz wrote:
>> > A type is the encoding of these properties. A type
>>> varying over time is an inherent contradiction (or another abuse of the
>>> term "type").
>> No. It's just a matter of definition, essentially.
>> E.g. in Smalltalk and Lisp, it does make sense to talk of the "type" of
>> a name or a value, even if that type may change over time.
>
> OK, now we are simply back full circle to Chris Smith's original
> complaint that started this whole subthread, namely (roughly) that
> long-established terms like "type" or "typing" should *not* be
> stretched in ways like this, because that is technically inaccurate and
> prone to misinterpretation.
Sorry, I have to insist that it's not me who's stretching terms here.
All textbook definitions that I have seen define a type as the
set/operations/axioms triple I mentioned above.
No mention of immutability, at least not in the definitions.
Plus, I don't see any necessity on insisting on immutability for the
definition of "type". Otherwise, you'd have to declare that Smalltalk
objects truly don't have a type (not even an implied one), and that
would simply make no sense: they do in fact have a type, even though it
may occasionally change.
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 14:36:48 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7m00h$tq3$1@online.de>
Chris F Clark schrieb:
> Chris F Clark schrieb:
>> In that sense, a static type system is eliminating tags, because the
>> information is pre-computed and not explicitly stored as a part of the
>> computation. Now, you may not view the tag as being there, but in my
>> mind if there exists a way of perfoming the computation that requires
>> tags, the tag was there and that tag has been eliminated.
>
> Joachim Durchholz replied:
>> On a semantic level, the tag is always there - it's the type (and
>> definitely part of an axiomatic definition of the language).
>> Tag elimination is "just" an optimization.
>
> I agree the tag is always there in the abstract.
Well - in the context of a discussion of dynamic and static typing, I'd
think that the semantic ("abstract") level is usually the best level of
discourse.
Of course, this being the Usenet, shifting the level is common (and can
even helpful).
> In the end, I'm trying to fit things which are "too big" and "too
> slow" into much less space and time, using types to help me reliably
> make my program smaller and faster is just one trick. [...]
>
> However, I also know that my way of thinking about it is fringe.
Oh, I really agree that's an important application of static typing.
Essentially, which aspects of static typing is more important depends on
where your problems lie: if it's ressource constraints, static typing
tends to be seen as a tool to keep ressource usage down; if it's bug
counts, static typing tends to be seen as a tool to express static
properties.
These aspects are obviously not equally important to everybody.
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 14:40:29 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7m07f$tq3$2@online.de>
Darren New schrieb:
> John W. Kennedy wrote:
>> 360-family assembler, yes. 8086-family assembler, not so much.
>
> And Burroughs B-series, not at all. There was one "ADD" instruction, and
> it looked at the data in the addresses to determine whether to add ints
> or floats. :-)
I heard that the Telefunken TR series had a tagged architecture.
This seems roughly equivalent to what the B-series did (does?).
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 14:52:15 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7m0th$vgu$1@online.de>
Anton van Straaten schrieb:
> Marshall wrote:
>> Can you be more explicit about what "latent types" means?
>
> Sorry, that was a huge omission. (What I get for posting at 3:30am.)
>
> The short answer is that I'm most directly referring to "the types in
> the programmer's head".
Ah, finally that terminology starts to make sense to me. I have been
wondering whether there's any useful difference between "latent" and
"run-time" typing. (I tend to avoid the term "dynamic typing" because
it's overloaded with too many vague ideas.)
> there are usually many possible static
> type schemes that can be assigned to a given program.
This seems to apply to latent types as well.
Actually the set of latent types seems to be the set of possible static
type schemes.
Um, well, a superset of these - static type schemes tend to be slightly
less expressive than what the programmer in his head. (Most type schemes
cannot really express things like "the range of this index variable is
such-and-so", and the boundary to general assertions about the code is
quite blurry anyway.)
> There's a close connection between latent types in the sense I've
> described, and the "tagged values" present at runtime. However, as type
> theorists will tell you, the tags used to tag values at runtime, as e.g.
> a number or a string or a FooBar object, are not the same thing as the
> sort of types which statically-typed languages have.
Would that be a profound difference, or is it just that annotating a
value with a full type expression would cause just too much runtime
overhead?
In your terminology:
> So, where do tagged values fit into this? Tags help to check types at
> runtime, but that doesn't mean that there's a 1:1 correspondence between
> tags and types.
Would it be possible to establish such a correspondence, would it be
common consensus that such a system should be called "tags" anymore, or
are there other, even more profound differences?
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 14:59:33 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7m1b6$nf$1@online.de>
Marshall schrieb:
> It seems we have languages:
> with or without static analysis
> with or without runtime type information (RTTI or "tags")
> with or without (runtime) safety
> with or without explicit type annotations
> with or without type inference
>
> Wow. And I don't think that's a complete list, either.
>
> I would be happy to abandon "strong/weak" as terminology
> because I can't pin those terms down. (It's not clear what
> they would add anyway.)
Indeed.
>> Programmers infer and reason about these latent types while they're
>> writing or reading programs. Latent types become manifest when a
>> programmer reasons about them, or documents them e.g. in comments.
>
> Uh, oh, a new term, "manifest." Should I worry about that?
I think that was OED usage of the term.
> Well, darn. It strikes me that that's just a decision the language
> designers
> made, *not* to record complete RTTI. (Is it going to be claimed that
> there is an *advantage* to having only incomplete RTTI? It is a
> serious question.)
In most cases, it's probably "we don't have to invent or look up
efficient algorithms that we can't think of right now".
One could consider this a sorry excuse or a wise decision to stick with
available resources, both views have their merits IMHO ;-)
>> But "function" is not a useful type. Why not? Because if all you know
>> is that timestwo is a function, then you have no idea what an expression
>> like "timestwo(foo)" means. You couldn't write working programs, or
>> read them, if all you knew about functions was that they were functions.
>> As a type, "function" is incomplete.
>
> Yes, function is a parameterized type, and they've left out the
> parameter values.
Well, in JavaScript, the explicit type system as laid down in the
run-time type information is unparameterized.
You can criticize this as unsound, or inadequate, or whatever you wish,
and I'd like agree with that ;-), but the type of timestwo is indeed
just "function".
*Your mental model* is far more detailed, of course.
> Question: if a language *does* record complete RTTI, and the
> languages does *not* have subtyping, could we then say that
> the runtime type information *is* the same as the static type?
Only if the two actually use the same type system.
In practice, I'd say that this is what most designers intend but what
implementors may not have gotten right ;-p
Regards,
Jo
------------------------------
Date: Sun, 25 Jun 2006 15:01:40 +0200
From: Joachim Durchholz <jo@durchholz.org>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <e7m1f5$nf$2@online.de>
Anton van Straaten schrieb:
>> It seems we have languages:
>> with or without static analysis
>> with or without runtime type information (RTTI or "tags")
>> with or without (runtime) safety
>> with or without explicit type annotations
>> with or without type inference
>>
>> Wow. And I don't think that's a complete list, either.
>
> Yup.
What else?
(Genuinely curious.)
Regards,
Jo
------------------------------
Date: 6 Apr 2001 21:33:47 GMT (Last modified)
From: Perl-Users-Request@ruby.oce.orst.edu (Perl-Users-Digest Admin)
Subject: Digest Administrivia (Last modified: 6 Apr 01)
Message-Id: <null>
Administrivia:
#The Perl-Users Digest is a retransmission of the USENET newsgroup
#comp.lang.perl.misc. For subscription or unsubscription requests, send
#the single line:
#
# subscribe perl-users
#or:
# unsubscribe perl-users
#
#to almanac@ruby.oce.orst.edu.
NOTE: due to the current flood of worm email banging on ruby, the smtp
server on ruby has been shut off until further notice.
To submit articles to comp.lang.perl.announce, send your article to
clpa@perl.com.
#To request back copies (available for a week or so), send your request
#to almanac@ruby.oce.orst.edu with the command "send perl-users x.y",
#where x is the volume number and y is the issue number.
#For other requests pertaining to the digest, send mail to
#perl-users-request@ruby.oce.orst.edu. Do not waste your time or mine
#sending perl questions to the -request address, I don't have time to
#answer them even if I did know the answer.
------------------------------
End of Perl-Users Digest V10 Issue 9374
***************************************
