From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 08E3EE0128 for ; Wed, 31 Aug 2022 10:19:29 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=inria.fr; s=dc; h=subject:to:cc:references:from:message-id:date: mime-version:in-reply-to:content-transfer-encoding; bh=j5CNB59NqFKp1gIol3m6LW6nHrlwepaEFkPQ/YabouM=; b=D7cW7wqcJ8qDNoiZkKlNpkKExD8VfVk+oG3Ojk7/gdlEObckuvoYLzmM HZJIkqskZt0TcOZE9uYQPNHEBTa/JMAKcxoMuplCyAZddpCltEHFH5cqn BxxgqzAr/C4H9kh1lH7rX05aJrfT/mLwdBMiBNJF9K3gwwaNypqw4sF24 U=; Authentication-Results: mail2-relais-roc.national.inria.fr; dkim=none (message not signed) header.i=none; spf=SoftFail smtp.mailfrom=francois.pottier@inria.fr; dmarc=fail (p=none dis=none) d=inria.fr X-IronPort-AV: E=Sophos;i="5.93,277,1654552800"; d="scan'208";a="50646322" Received: from 91-175-127-215.subs.proxad.net (HELO MacBook-Pro-5.local) ([91.175.127.215]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 31 Aug 2022 10:19:30 +0200 To: Aaron Gray Cc: OCaML Mailing List References: <25e68e2c-04d2-7764-e189-00812c08a34a@inria.fr> <8078ad33-f220-b233-4863-06ce30cc8cff@inria.fr> From: =?UTF-8?Q?Fran=c3=a7ois_Pottier?= Message-ID: <57aa59a7-a7fd-4578-010b-25dfc1a1e12e@inria.fr> Date: Wed, 31 Aug 2022 10:19:28 +0200 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:68.0) Gecko/20100101 Thunderbird/68.12.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: fr Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] coinductive data types Hello, Le 30/08/2022 à 18:32, Aaron Gray wrote: > What I have gathered is that in order to have completeness of type > system and soundness you need the type system to be implemented as a > type lattice, there by underpinning the system on to a topological > space and thus being constructable and well founded. I am not sure what you mean by "soundness and completeness of the system". A type system is considered "sound" if a well-typed program cannot crash. A type-checking or type inference algorithm is considered "sound and complete" provided it declares a program well-typed if and only if this program is indeed well-typed. (I am simplifying the statement a bit.) This implies that the property of being well-typed is decidable. It is not necessary in principle for the subtyping relation to be a lattice. The lattice property can help (e.g. it can help simplify subtyping constraints, when performing type inference in the presence of subtyping). > I don't know how accessible OCaML's, type system code is. I have had a > brief look, I am used to Haskell, and Haskell's type annotations in > order to get my bearings. > > Are there any papers on OCaML's type system proper at all please ? The code of the OCaml type-checker is publicly available but is not easy to read. There are several papers covering several aspects of the type system, but I am not sure which one would be most relevant here. Perhaps "GADTs Meet Subtyping" by Gabriel Scherer and Didier Rémy, which discusses the combination of *generalized* algebraic data types and subtyping. I hope this helps, -- François Pottier francois.pottier@inria.fr http://cambium.inria.fr/~fpottier/