From: Jacques Carette <carette@mcmaster.ca>
To: skaller <skaller@users.sourceforge.net>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Unsoundness is essential
Date: Wed, 03 Oct 2007 19:13:06 -0400 [thread overview]
Message-ID: <47042202.4070906@mcmaster.ca> (raw)
In-Reply-To: <1191451810.7218.86.camel@rosella.wigram>
skaller wrote:
> To be bold I propose type theorists have got it totally wrong.
>
> Goedel's theorem says that any type system strong enough to
> describe integer programming is necessarily unsound.
>
No, that's wrong. Any *complete* type system that strong is unsound.
It says nothing about incomplete systems.
My position is that looking for decision procedures everywhere is what
is blocking real progress. People doing dependent types have gotten
over most of that.
> I want an unsound type system!
No you don't, you want an incomplete one. You want one where the type
system will tell you when you are obviously wrong, and will ask you for
a proof when it's not sure. If you insist on unsound, then when the
type system doesn't know, it might let things through anyways, and then
all bets are off. I don't want that.
> It much better than the useless
> but 'sound' type system of Python, in which the type inference
> engine decides all values have type Object and proves
> in vacuuo that all programs are type-safe, only to do the
> dependent type checks at run time anyhow -- a cheat known
> as dynamic typing.
>
Again, I disagree. It's much better to do most type checks statically,
and then to residualize some type checks to run-time if you absolutely
must. This is roughly what my Master's student Gordon Uszkay did for a
"scientific computation" language, using CHRs. Unfortunately, his work
was already way too ambitious as it was, so all he succeeded in doing is
an implementation [that works], but no formal proofs.
> In particular, the ability to write proper type annotations
> such as
>
> divide: int * (int - {0}) -> int
>
> and fail to reject programs which violate the typing is an
> essential and useful feature.
I would rather say that what should be done is that run-time type checks
should be residualized into the program, so that no unsound program
would be allowed to run to completion, an assertion would be triggered
first.
> In fact, the idea of C is the right one.
When I was forced to write a C program (after enjoying Ocaml so much),
and even with
gcc -W -Wall -Werror -pedantic something.c
I got a clean compile which, when run, core dumped, I was seriously
unhappy.
> Stop CHEATING by refusing to allow
> me to write types you can't check -- because this forces
> ME as the programmer to cheat on the type annotations:
>
> divide: int * int -> int
> hd : 'a list -> 'a
>
Here we agree. Both of those types are 'cheating'.
Jacques
next prev parent reply other threads:[~2007-10-03 23:22 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-10-03 8:35 Locally-polymorphic exceptions [was: folding over a file] oleg
2007-10-03 11:27 ` kirillkh
2007-10-03 11:48 ` [Caml-list] " Daniel de Rauglaudre
2007-10-03 12:19 ` kirillkh
2007-10-03 12:32 ` Daniel de Rauglaudre
2007-10-03 14:34 ` kirillkh
2007-10-03 20:39 ` Christophe Raffalli
2007-10-03 22:50 ` Unsoundness is essential skaller
2007-10-03 23:13 ` Jacques Carette [this message]
2007-10-04 1:24 ` [Caml-list] " skaller
2007-10-04 11:26 ` David Allsopp
2007-10-04 12:45 ` Vincent Hanquez
2007-10-04 15:07 ` skaller
2007-10-03 23:13 ` Vincent Aravantinos
2007-10-04 1:49 ` skaller
2007-10-03 23:28 ` Joshua D. Guttman
2007-10-04 1:52 ` skaller
2007-10-04 2:35 ` Brian Hurt
2007-10-04 7:46 ` Christophe Raffalli
2007-10-04 8:56 ` Arnaud Spiwack
2007-10-04 14:49 ` skaller
2007-10-04 15:00 ` Harrison, John R
2007-10-04 15:29 ` Andrej Bauer
2007-10-04 16:25 ` skaller
2007-10-04 18:17 ` Arnaud Spiwack
2007-10-04 20:54 ` skaller
2007-10-04 22:24 ` Arnaud Spiwack
2007-10-04 16:37 ` skaller
2007-10-04 18:59 ` Christophe Raffalli
2007-10-04 15:04 ` Andrej Bauer
2007-10-04 15:57 ` Christophe Raffalli
2007-10-04 16:03 ` skaller
2007-10-04 20:02 ` Ken Rose
2007-10-04 21:00 ` skaller
2007-10-04 15:31 ` Lukasz Stafiniak
2007-10-04 17:56 ` rossberg
2007-10-04 19:56 ` skaller
2007-10-04 21:07 ` rossberg
2007-10-04 22:23 ` skaller
2007-10-05 2:48 ` Bárður Árantsson
2007-10-04 2:16 ` Locally-polymorphic exceptions [was: folding over a file] oleg
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=47042202.4070906@mcmaster.ca \
--to=carette@mcmaster.ca \
--cc=caml-list@inria.fr \
--cc=skaller@users.sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).