[28025] in Perl-Users-Digest
Perl-Users Digest, Issue: 9389 Volume: 10
daemon@ATHENA.MIT.EDU (Perl-Users Digest)
Tue Jun 27 03:10:42 2006
Date: Tue, 27 Jun 2006 00: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 Tue, 27 Jun 2006 Volume: 10 Number: 9389
Today's topics:
Re: What is Expressiveness in a Computer Language <marshall.spight@gmail.com>
Re: What is Expressiveness in a Computer Language <cfc@shell01.TheWorld.com>
Re: What is Expressiveness in a Computer Language <cfc@shell01.TheWorld.com>
Re: What is Expressiveness in a Computer Language <marshall.spight@gmail.com>
Re: What is Expressiveness in a Computer Language <cdsmith@twu.net>
Re: What is Expressiveness in a Computer Language <pjb@informatimago.com>
Re: What is Expressiveness in a Computer Language <cdsmith@twu.net>
Digest Administrivia (Last modified: 6 Apr 01) (Perl-Users-Digest Admin)
----------------------------------------------------------------------
Date: 26 Jun 2006 19:20:01 -0700
From: "Marshall" <marshall.spight@gmail.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <1151374801.003139.68680@u72g2000cwu.googlegroups.com>
George Neuner wrote:
>
> I can know that my conversion of floating point to integer is going to
> produce a value within a certain range ... but, in general, the
> compiler can't determine what that range will be. All it knows is
> that a floating point value is being truncated and the stupid
> programmer wants to stick the result into some type too narrow to
> represent the range of possible values.
>
> Like I said to Ben, I haven't seen any _practical_ static type system
> that can deal with things like this. Writing a generic function is
> impossible under the circumstances, and writing a separate function
> for each narrow type is ridiculous and a maintenance nightmare even if
> they can share the bulk of the code.
This is the partial function question again, in a different guise.
Marshall
------------------------------
Date: 27 Jun 2006 00:37:05 -0400
From: Chris F Clark <cfc@shell01.TheWorld.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <sddmzbzjjta.fsf@shell01.TheWorld.com>
I wrote:
> The important thing is the dynamicism of lisp allowed one to write
> polymorphic programs, before most of us knew the term.
Chris Smith <cdsmith@twu.net> writes:
> Sure. In exchange for giving up the proofs of the type checker, you
> could write all kinds of programs. To this day, we continue to write
> programs in languages with dynamic checking features because we don't
> have powerful enough type systems to express the corresponding type
> system.
And to me the question is what kinds of types apply to these dynamic
programs, where in fact you may have to solve the halting problem to
know exactly when some statement is executed. I expect that some
programs have type signatures that exceed the expressibility of any
static system (that is Turing complete). Therefore, we need something
that "computes" the appropriate type at run-time, because we need full
Turing power to compute it. To me such a system is a "dynamic type
system". I think dynamic tags are a good approximation, because they
only compute what type the expression has this time.
> I believe that, in fact, it would be trivial to imagine a type system
> which is capable of expressing that type. Okay, not trivial, since it
> appears to be necessary to conceive of an infinite family of integer
> types with only one value each, along with range types, and
> relationships between them; but it's probably not completely beyond the
> ability of a very bright 12-year-old who has someone to describe the
> problem thoroughly and help her with the notation.
Well, it look like you are right in that I see following is a Haskell
program that looks essentially correct. I wanted something that was
simple enough that one could see that it could be computed, but which
was complex enough that it had to be computed (and couldn't be
statically expressed with a system that did no "type computations").
Perhaps, there is no such beast. Or, perhaps I just can't formulate
it. Or, perhaps we have static type checkers which can do
computations of unbounded complexity. However, I thought that one of
the characteristics of type systems was that they did not allow
unbounded complexity and weren't Turing Complete.
> You would, of course, need a suitable type system first. For example,
> it appears to me that there is simply no possible way of expressing what
> you've described in Java, even with the new generics features. Perhaps
> it's possible in ML or Haskell (I don't know). My point is that if you
> were allowed to design a type system to meet your needs, I bet you could
> do it.
Or, I could do as I think the dynamic programmers do, dispense with
trying to formulate a sufficiently general type system and just check
the tags at the appropriate points.
> Sure. The important question, then, is whether there exists any program
> bug that can't be formulated as a type error.
If you allow Turing Complete type systems, then I would say no--every
bug can be reforumlated as a type error. If you require your type
system to be less powerful, then some bugs must escape it.
-Chris
------------------------------
Date: 27 Jun 2006 00:43:47 -0400
From: Chris F Clark <cfc@shell01.TheWorld.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <sddac7zjji4.fsf@shell01.TheWorld.com>
"Greg Buchholz" <sleepingsquirrel@yahoo.com> writes:
> Chris F Clark wrote:
> > Thus, as we traverse a list, the first element might be an integer,
> > the second a floating point value, the third a sub-list, the fourth
> > and fifth, two more integers, and so on. If you look statically at
> > the head of the list, we have a very wide union of types going by.
> > However, perhaps there is a mapping going on that can be discerned.
> > For example, perhaps the list has 3 distinct types of elements
> > (integers, floating points, and sub-lists) and it circles through the
> > types in the order, first having one of each type, then two of each
> > type, then four of each type, then eight, and so on.
>
> Sounds like an interesting problem. Although not the exact type
> specified above, here's something pretty similar that I could think of
> implementing in Haskell. (I don't know what a "sub-list" is, for
> example). Maybe some Haskell wizard could get rid of the tuples?
>
>
> data Clark a b c = Nil | Cons a (Clark b c (a,a)) deriving Show
>
> clark = (Cons 42 (Cons 3.14 (Cons "abc"
> (Cons (1,2) (Cons (1.2,3.4) (Cons ("foo","bar")
> (Cons ((9,8),(7,6)) (Cons ((0.1,0.2),(0.3,0.4)) Nil))))))))
>
> main = print clark
Very impressive. It looks right to me and simple enough to
understand. I must find the time to learn a modern FP language. Can
you write a fold for this that prints the data as a binary tree of
triples? I have to believe it isn't that hard....
-Chris
------------------------------
Date: 26 Jun 2006 22:01:51 -0700
From: "Marshall" <marshall.spight@gmail.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <1151384511.223582.305760@m73g2000cwd.googlegroups.com>
Chris F Clark wrote:
>
> And to me the question is what kinds of types apply to these dynamic
> programs, where in fact you may have to solve the halting problem to
> know exactly when some statement is executed. I expect that some
> programs have type signatures that exceed the expressibility of any
> static system (that is Turing complete). Therefore, we need something
> that "computes" the appropriate type at run-time, because we need full
> Turing power to compute it. To me such a system is a "dynamic type
> system". I think dynamic tags are a good approximation, because they
> only compute what type the expression has this time.
Yes, an important question (IMHO the *more* important question
than the terminology) is what *programs* do we give up if we
wish to use static typing? I have never been able to pin this
one down at all.
Frankly, if the *only* issue between static and dynamic was
the static checking of the types, then static typing woud
unquestionably be superior. But that's not the only issue.
There are also what I call "packaging" issues, such as
being able to run partly-wrong programs on purpose so
that one would have the opportunity to do runtime analysis
without having to, say, implement parts of some interface
that one isn't interested in testing yet. These could also
be solved in a statically typed language. (Although
historically it hasn't been done that way.)
The real question is, are there some programs that we
can't write *at all* in a statically typed language, because
they'll *never* be typable? I think there might be, but I've
never been able to find a solid example of one.
> Perhaps, there is no such beast. Or, perhaps I just can't formulate
> it. Or, perhaps we have static type checkers which can do
> computations of unbounded complexity. However, I thought that one of
> the characteristics of type systems was that they did not allow
> unbounded complexity and weren't Turing Complete.
The C++ type system is Turing complete, although in practical terms
it limits how much processing power it will spend on types at
compile time.
> If you allow Turing Complete type systems, then I would say no--every
> bug can be reforumlated as a type error. If you require your type
> system to be less powerful, then some bugs must escape it.
I don't think so. Even with a Turing complete type system, a program's
runtime behavior is still something different from its static behavior.
(This is the other side of the "types are not tags" issue--not only
is it the case that there are things static types can do that tags
can't, it is also the case that there are things tags can do that
static types can't.)
Marshall
------------------------------
Date: Mon, 26 Jun 2006 23:48:00 -0600
From: Chris Smith <cdsmith@twu.net>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <MPG.1f0a747a457f0a2898971e@news.altopia.net>
Chris F Clark <cfc@shell01.TheWorld.com> wrote:
> And to me the question is what kinds of types apply to these dynamic
> programs, where in fact you may have to solve the halting problem to
> know exactly when some statement is executed.
Yes, I believe (static) type systems will always end up approximating
(conservatively) the possible behavior of programs in order to perform
their verification.
> Or, perhaps we have static type checkers which can do
> computations of unbounded complexity. However, I thought that one of
> the characteristics of type systems was that they did not allow
> unbounded complexity and weren't Turing Complete.
Honestly, I suspect you'd get disagreement within the field of type
theory about this. Certainly, there are plenty of researchers who have
proposed type systems that potentially don't even terminate. The
consensus appears to be that they are worth studying within the field of
type theory, but I note that Pierce still hasn't dropped the word
"tractable" from his definition in his introductory text, despite
acknowledging only a couple pages later that languages exist whose type
systems are undecidable, and apparently co-authoring a paper on one of
them. The consensus seems to be that such systems are interesting if
they terminate quickly for interesting cases (in which case, I suppose,
you could hope to eventually be able to formalize what cases are
interesting, and derive a truly tractable type system that checks that
interesting subset).
Interestingly, Pierce gives ML as an example of a language whose type
checker does not necesarily run in polynomial time (thus failing some
concepts of "tractable") but that does just fine in practice. I am just
quoting here, so I don't know exactly how this is true. Marshall
mentioned template meta-programming in C++, which is definitely Turing-
complete.
--
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation
------------------------------
Date: Tue, 27 Jun 2006 07:57:26 +0200
From: Pascal Bourguignon <pjb@informatimago.com>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <87odwf3zuh.fsf@thalassa.informatimago.com>
"Marshall" <marshall.spight@gmail.com> writes:
> Yes, an important question (IMHO the *more* important question
> than the terminology) is what *programs* do we give up if we
> wish to use static typing? I have never been able to pin this
> one down at all.
Well, given Turing Machine equivalence...
I'd mention retrospective software. But you can always implement the
wanted retrospective features as a layer above the statically typed
language.
So the question is how much work the programmer needs to do to
implement a given program with static typing or with dynamic typing.
> The real question is, are there some programs that we
> can't write *at all* in a statically typed language, because
> they'll *never* be typable? I think there might be, but I've
> never been able to find a solid example of one.
More than *never* typable, you want to identify some kind of software
that is not *economically* statically typable.
Was it costlier to develop the software developed in non statically
typed programming languages than in a statically typed programming
language?
--
__Pascal Bourguignon__ http://www.informatimago.com/
"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."
------------------------------
Date: Tue, 27 Jun 2006 00:06:02 -0600
From: Chris Smith <cdsmith@twu.net>
Subject: Re: What is Expressiveness in a Computer Language
Message-Id: <MPG.1f0a78b132a01d5998971f@news.altopia.net>
Marshall <marshall.spight@gmail.com> wrote:
> Yes, an important question (IMHO the *more* important question
> than the terminology) is what *programs* do we give up if we
> wish to use static typing? I have never been able to pin this
> one down at all.
You'd need to clarify what you mean by "use static typing". Clearly, if
you use forms of static typing that currently exist for Java, there's
considerable limitation in expressiveness. If you mean a hypothetical
"perfect" type system, then there would be no interesting programs you
couldn't write, but such a system may not be possible to implement, and
certainly isn't feasible.
So it seems to me that we have this ideal point at which it is possible
to write all correct or interesting programs, and impossible to write
buggy programs. Pure static type systems try to approach that point
from the conservative side. Pure dynamic systems (and I actually think
that design-by-contract languages and such apply here just as well as
type tagging) try to approach that point via runtime verification from
the liberal side. (No, this has nothing to do with George Bush or Noam
Chomsky... :) Either side finds that the closer they get, the more
creative they need to be to avoid creating development work that's no
longer commensurate with the gains involved (whether in safety or
expressiveness).
I think I am now convinced that the answer to the question of whether
there is a class of type errors in dynamically checked languages is the
same as the answer for static type systems: no. In both cases, it's
just a question of what systems may be provided for the purposes of
verifying (more or less conservatively or selectively) certain program
properties. Type tags or other features that "look like" types are only
relevant in that they encapsulate common kinds of constraints on program
correctness without requiring the programmer to express those
constraints in any more general purpose language.
As for what languages to use right now, we are interestingly enough back
where Xah Lee started this whole thread. All languages (except a few of
the more extreme statically typed languages) are Turing complete, so in
order to compare expressiveness, we'd need some other measure that
considers some factor or factors beyond which operations are
expressible.
> There are also what I call "packaging" issues, such as
> being able to run partly-wrong programs on purpose so
> that one would have the opportunity to do runtime analysis
> without having to, say, implement parts of some interface
> that one isn't interested in testing yet. These could also
> be solved in a statically typed language. (Although
> historically it hasn't been done that way.)
I'll note veryh briefly that the built-in compiler for the Eclipse IDE
has the very nice feature that when a particular method fails to
compile, it can still produces a result but replace the implementation
of that method with one that just throws an Error. I've taken advantage
of that on occasion, though it doesn't allow the same range of options
as a language that will just go ahead and try the buggy operations.
> The real question is, are there some programs that we
> can't write *at all* in a statically typed language, because
> they'll *never* be typable? I think there might be, but I've
> never been able to find a solid example of one.
This seems to depend on the specific concept of equivalence of programs
that you have in mind.
--
Chris Smith - Lead Software Developer / Technical Trainer
MindIQ Corporation
------------------------------
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 9389
***************************************
