From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id B9C1FBC69 for ; Thu, 4 Oct 2007 10:56:04 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAALpHBEfAXQInemdsb2JhbACOOAEBCQo X-IronPort-AV: E=Sophos;i="4.21,228,1188770400"; d="scan'208";a="17276541" Received: from concorde.inria.fr ([192.93.2.39]) by mail4-smtp-sop.national.inria.fr with ESMTP; 04 Oct 2007 10:56:04 +0200 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l948u2jT027308 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Thu, 4 Oct 2007 10:56:03 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAALpHBEdA6ba/mGdsb2JhbACOOAEBAgcEBiU X-IronPort-AV: E=Sophos;i="4.21,228,1188770400"; d="scan'208";a="17276539" Received: from nf-out-0910.google.com ([64.233.182.191]) by mail4-smtp-sop.national.inria.fr with ESMTP; 04 Oct 2007 10:56:03 +0200 Received: by nf-out-0910.google.com with SMTP id g13so96527nfb for ; Thu, 04 Oct 2007 01:56:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding:sender; bh=iv3RZe1/I52+qcqGblMOfHpofK0JXaKz7XC4tq+TT/w=; b=alvciZF8tQTJPTxcPmuulH4k1wDHiPVMB0c4x4fm52HAvM4Lv8gV31Gmk6/s7AZSKxq5d6rr22k2AGLDSioYCVdtlQH1tXidzrKBw5imK22Y3lAltMRCtL3mFBsTzlvpLxZhj+jrFQgBxT3i67T+TpcTMMZRvGYfeazs+H6TGsM= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:user-agent:mime-version:to:subject:references:in-reply-to:content-type:content-transfer-encoding:sender; b=cTDsrZMqb0aiBJgtTDRQ855GcWVSVgyC3zMXKjfzlKbfopxCsrEMizFbe3/jt1kdjrS1axpSk5QQkxpP5gjkPSwxINp0C8Wu++6pOz9sWuNTuXR1jGMN8H5rrmsco7Ird3OrKtk2W/iqn4IL3BofHwZO2I/R5Whpk5j/M3VkDcc= Received: by 10.86.58.3 with SMTP id g3mr1274426fga.1191488162817; Thu, 04 Oct 2007 01:56:02 -0700 (PDT) Received: from ?192.168.0.5? ( [87.88.165.197]) by mx.google.com with ESMTPS id e9sm2707599muf.2007.10.04.01.55.59 (version=SSLv3 cipher=RC4-MD5); Thu, 04 Oct 2007 01:56:00 -0700 (PDT) Message-ID: <4704AAA8.9080602@lix.polytechnique.fr> Date: Thu, 04 Oct 2007 10:56:08 +0200 From: Arnaud Spiwack User-Agent: Thunderbird 2.0.0.6 (Windows/20070728) MIME-Version: 1.0 To: caml-list@inria.fr Subject: Re: [Caml-list] Unsoundness is essential References: <20071003083529.40DA2A99F@Adric.metnet.fnmoc.navy.mil> <4703FDEF.7030900@univ-savoie.fr> <1191451810.7218.86.camel@rosella.wigram> <1191462724.7542.76.camel@rosella.wigram> <47049A6D.6020201@univ-savoie.fr> In-Reply-To: <47049A6D.6020201@univ-savoie.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Sender: Arnaud Spiwack X-Miltered: at concorde with ID 4704AAA2.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; lix:01 christophe:01 pointers:01 pointers:01 downcasting:01 arbitrarily:01 coq:01 decidability:01 non-zero:01 int-:01 isomorphism:01 runtime:01 inherently:01 axioms:01 axioms:01 Hi everybody, Christophe already said much of what I have to do, but it's compulsively impossible to me to avoid posting on such a thread. My own psychopathologies coerce me into meddling into here. First of all, as some sort of an introductory thing, I'd like to mention that Java is probably the currently most popular language among programmers, and it's strongly typed. Indeed, there are quite a few unsafe feature (null pointers, down casting), but they are gradually removed (well, I guess null pointers won't ever): since the addition of generics wild downcasting to use generic structures is largely deprecated, if one would provide with a primitive ternary guarded cast operator, one wouldn't have to resort to write it by hand "if (blah.isClass...", etc... Anyway, back to Mr. Gödel and his theorem. What he stated indeed is that truth and provability never coincide (provided we're talking of something at least as expressive as arithmetic). That is, as some people already mentionned: either everything can be proved, or there is at least a statement A such that neither A is provable neither its negation. Still there is something peculiar in the interpretation of Gödel theorem, since if we are in a classical logical system (where ~~A (not not A) and A are equivalent). If neither A nor ~A are provable, then both can be "the real one". By that I mean that both can be chosen as true, without impacting the consistency of the system (quick proof sketch : A -> ~A is equivalent to A -> (A -> False) which is equivalent to A&A -> False wich is equivalent to ~A). A conclusion I can draw from that is that we don't care about what is true, we care about what is provable, since it is at least welle defined, where truth is very much unclear (an example of such weirdness is the axiom of choice, which is a very pratical axiom in classical mathematics, and widely accepted. Except when you are doing probabilities where it is very convenient to have the "measurability axiom" stating that "everything is mesurable" (more or less) and which contradicts the axiom of choice). Now let's move to programming again. Type systems can be arbitrarily complex, see for instance, Coq, Agda2, Epigram, PML and many other that I'm less familiar with. In this language, evidences show that everything one needs to prove for proving a program (partially) correct, is provable. There we must draw a clear line between two concept which have been a bit mixed up in this thread : provability and decidability. Of course, it is not possible to decide in all generality that whoever integer is non-zero, thus a type system able to express (int -> int-{0} -> int) as a type for division cannot decide type checking without extra information. The extra information is no more than a proof that we never provide an 0-valued integer (at each application). And curry-howard isomorphism allows to stick it inside the type system. That's what Type Theorist yearn for (by the way that is cool because many runtime check consume time unneedlessly, and time is money, and money is precious). Of course, there is still a lot of work to do around these. But this is more than promissing, and one should be able to never need unsafe features (though there actually is a more or less unsafe feature inherently in these type systems, it's called "axioms", since you can generaly enhance the theory with any additional claim. However axioms are usually kept out of very sensitive areas). At any rate, this does not say anything about the mostly untype languages. It is a different issue, typed vs untyped or decidable type inference vs more expressiveness in type system. The untyped world has its perks, especially C, which allow quite a few low level manipulation which are very useful. What I mean here is that if we need types (and I believe that a vast majority of programming application do), then we should have as expressive typing as possible, and not need to rely on unsafe feature which give headaches and segfaults. I realize that I got lost in my way, so I'll stop here, but I may be back (this is a much more prudent claim than that of another AS) in followups ;) . Arnaud Spiwack Christophe Raffalli a écrit : > skaller a écrit : > >> On Wed, 2007-10-03 at 19:28 -0400, Joshua D. Guttman wrote: >> >>> skaller writes: >>> >>> >>>> Goedel's theorem says that any type system strong enough >>>> to describe integer programming is necessarily unsound. >>>> >> I paraphrased it, deliberately, in effect claiming an analogous >> situation holds with type systems. >> >> > > Not unsound, incomplete ! > you mixup first and second incompleteness theorem. Let's clarify ? > > - first if a type system does not contain arithmetic nothing can be said > (this implies ML), but in this case, the meaning of complete needs to be clarified. > Indeed, there are complete type system ... > > - The 1st incompleteness theorem states that no theory containing > arithmetic is complete. This means that there will always be correct programs > that your type system can not accept. However, I thing a real program that > is not provably correct in lets say ZF, does not exists and should be rejected. > you do not accept a program whose correctness is a conjecture (do you ?) > > - The second incompleteness theorem, states that a system that proves its own > consistency is in fact inconsistent. For type system (strong enough to express > arithmetic, like ML with dependant type, PVS, the future PML, ..). This means > that the proof that the system is consistent (the proof that "0 = 1 can not be proved") > can not be done inside the system. However, the proof that your implementation > does implement the formal system correctly can be done inside the system, and > this is quite enough for me. > > - The soundness theorem for ML can be stated as a program of type "int" will > - diverge > - raise an exception > - or produce an int > I think everybody except LISP programmers ;-) want a sound type system like this. > OK replace everybody by I if you prefer ... For PML, we are more precise : exception > and the fact the a program may diverge must be written in the type. > > - ML type system is sometimes too incomplete, this is why the Obj library is here. > However, the use of Obj is mainly here because ML lacks dependant types. In fact, > the main use of Obj is to simulate a map table associating to a key k a type t(k) and > a value v:t(k). > > - All this says that a type-system only accepting proved programs is possible and > a good idea (it already exists). The question for researcher is how to produce a > type system where the cost of proving is acceptable compared to the cost of debugging, > and this stars to be the case for some specific application, but we are far from > having to remove the word "bug" from our vocabulary ;-) > > > ------------------------------------------------------------------------ > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs >