From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 9FA6D7F108 for ; Sat, 28 Nov 2015 13:32:08 +0100 (CET) IronPort-PHdr: 9a23:rzNzTBAgTaH1shWE3u70UyQJP3N1i/DPJgcQr6AfoPdwSP79pcbcNUDSrc9gkEXOFd2CrakU1qyG7uu5BCQp2tWojjMrSNR0TRgLiMEbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpQAbFhi3DwdpPOO9QteU1JTqkbDvsMSOKyxzxxODIppKZC2sqgvQssREyaBDEY0WjiXzn31TZu5NznlpL1/A1zz158O34YIxu38I46FppIZ8VvDxdqE8BaFDAS49ezQ+7cjv8B3CVhen530GU2xQnAAeUCbf6xSvdZfrszDmsfJ97wkEMsDsBeQ/WS6j9LtsUB+uiCAKODMj2H3Kz8Z9lqZaplStqkoskMbvfIiJOa8mLevmdtQASD8ZUw== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=christoph.hoeger@tu-berlin.de; spf=None smtp.mailfrom=christoph.hoeger@tu-berlin.de; spf=None smtp.helo=postmaster@mail.tu-berlin.de Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of christoph.hoeger@tu-berlin.de) identity=pra; client-ip=130.149.7.33; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="christoph.hoeger@tu-berlin.de"; x-sender="christoph.hoeger@tu-berlin.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of christoph.hoeger@tu-berlin.de) identity=mailfrom; client-ip=130.149.7.33; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="christoph.hoeger@tu-berlin.de"; x-sender="christoph.hoeger@tu-berlin.de"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail.tu-berlin.de) identity=helo; client-ip=130.149.7.33; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="christoph.hoeger@tu-berlin.de"; x-sender="postmaster@mail.tu-berlin.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0B6AADlnVlWnCEHlYJehA5vvi6BZhcChyU5EwEBAQEBAQEBEAEBAQEBCAsJCSEugi2CMQ8BewIFIQIRAkwNBgIBAYgqBJw/j3CPdYEBkgwMLhOBMQWWV4EDhCeCco44k0UjAYIJAQtRgV5xhXEBAQE X-IPAS-Result: A0B6AADlnVlWnCEHlYJehA5vvi6BZhcChyU5EwEBAQEBAQEBEAEBAQEBCAsJCSEugi2CMQ8BewIFIQIRAkwNBgIBAYgqBJw/j3CPdYEBkgwMLhOBMQWWV4EDhCeCco44k0UjAYIJAQtRgV5xhXEBAQE X-IronPort-AV: E=Sophos;i="5.20,356,1444687200"; d="scan'208";a="189499817" Received: from mail.tu-berlin.de ([130.149.7.33]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 28 Nov 2015 13:32:08 +0100 X-tubIT-Incoming-IP: 91.65.128.77 Received: from ip5b41804d.dynamic.kabel-deutschland.de ([91.65.128.77] helo=[192.168.178.42]) by mail.tu-berlin.de (exim-4.76/mailfrontend-8) with esmtpsa [UNKNOWN:AES128-SHA:128] for id 1a2efe-00024j-kI; Sat, 28 Nov 2015 13:32:07 +0100 To: caml users From: =?UTF-8?Q?Christoph_H=c3=b6ger?= Organization: =?UTF-8?Q?Technische_Universit=c3=a4t_Berlin?= Message-ID: <56599EC6.90204@tu-berlin.de> Date: Sat, 28 Nov 2015 13:32:06 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-PMX-Version: 6.0.0.2142326, Antispam-Engine: 2.7.2.2107409, Antispam-Data: 2015.11.28.122415 X-PMX-Spam: Gauge=IIIIIII, Probability=0%, Report='' Subject: [Caml-list] Avoiding type unfolding Dear all, I asked about this back in August but only now I had the time to get back at the issue. Consider the following script: #!/usr/bin/bash echo "class ['t] c_0 (t:'t) = object method child = t end" > c_0.ml for x in {1..15}; do ((y = $x - 1)) ; echo "class ['t] c_$x (t:'t) = object method child_2 = ((new C_$y.c_$y) t) method child_1 = (new C_$y.c_$y) t end" > c_$x.ml /usr/bin/time ocamlc.opt -c c_$x.ml done It demonstrates that type unfolding during the check of implementation/interfaces generates an exponential runtime. The problem is that each constructor is parametric and has to be expanded in order to access the normal form of its rhs. This is done for each element in the hierarchy. Is there any trick, hack or encoding that enables compilation of the same (or equivalent) classes in constant time? thanks, Christoph -- Christoph Höger Technische Universität Berlin Fakultät IV - Elektrotechnik und Informatik Übersetzerbau und Programmiersprachen Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin Tel.: +49 (30) 314-24890 E-Mail: christoph.hoeger@tu-berlin.de