helm/www/lambdadelta/specification.html

   1 <?xml version="1.0" encoding="UTF-8"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml" dir="ltr" lang="en-us">
   4   <head>
   5     <meta http-equiv="Content-Language" content="en-us" />
   6     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
   7     <meta http-equiv="Content-Style-Type" content="text/css" />
   8     <meta name="author" content="Ferruccio Guidi" />
   9     <meta name="description" content="\lambda\delta home page" />
  10     <title>\lambda\delta home page</title>
  11     <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/ld_web.css" />
  12     <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/lddl.css" />
  13     <link rel="stylesheet" type="text/css" href="http://lambdadelta.info/css/xhtbl.css" />
  14     <link rel="shortcut icon" href="http://lambdadelta.info/images/crux_16.ico" />
  15   </head>
  16   <body lang="en-US">
  17     <div class="spacer">
  18       <a href="http://lambdadelta.info/">
  19         <img class="icon32" alt="[\lambda\delta home]" title="\lambda\delta home" src="http://lambdadelta.info/images/crux_32.png" />
  20       </a>
  21     </div>
  22     <div class="head1">The Formal Systems of the λδ (\lambda\delta) Family</div>
  23     <div class="spacer">
  24       <img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png" />
  25     </div>
  26     <div xmlns:ld="http://lambdadelta.info/" class="spacer">
  27       <br />
  28     </div>
  29     <div xmlns:ld="http://lambdadelta.info/" class="text">
  30       <table cellpadding="4" cellspacing="0">
  31         <tbody>
  32           <tr>
  33             <td class="snns capitalize italic sky">
  34               <a href="http://lambdadelta.info/index.html">home</a>
  35             </td>
  36             <td class="snns capitalize italic magenta">
  37               <a href="http://lambdadelta.info/news.html">news</a>
  38             </td>
  39             <td class="snns capitalize italic white">
  40               <a href="http://lambdadelta.info/specification.html">specification</a>
  41             </td>
  42             <td class="snnn capitalize italic white">
  43               <br />
  44             </td>
  45             <td class="snnn capitalize italic white">
  46               <br />
  47             </td>
  48             <td class="snns capitalize italic orange">
  49               <a href="http://lambdadelta.info/documentation.html">documentation</a>
  50             </td>
  51             <td class="snns capitalize italic green">
  52               <a href="http://lambdadelta.info/implementation.html">implementation</a>
  53             </td>
  54             <td class="ssnn capitalize italic green">
  55               <br />
  56             </td>
  57           </tr>
  58           <tr>
  59             <td class="snns capitalize sky">
  60               <a href="http://lambdadelta.info/index.html#foreword">foreword</a>
  61             </td>
  62             <td class="snns capitalize magenta">
  63               <a href="http://lambdadelta.info/news.html#milestones">milestones</a>
  64             </td>
  65             <td class="snns capitalize white">
  66               <a href="http://lambdadelta.info/specification.html#v2">version 2</a>
  67             </td>
  68             <td class="snnn capitalize white">(<a href="http://lambdadelta.info/ground_2.html">background</a> - <a href="http://lambdadelta.info/basic_2.html">core</a> - <a href="http://lambdadelta.info/apps_2.html">applications</a>)</td>
  69             <td class="snnn capitalize white">
  70               <br />
  71             </td>
  72             <td class="snns capitalize orange">
  73               <a href="http://lambdadelta.info/documentation.html#v2">version 2</a>
  74             </td>
  75             <td class="snns capitalize green">
  76               <a href="http://lambdadelta.info/implementation.html#helena">helena</a>
  77             </td>
  78             <td class="ssnn capitalize green">
  79               <br />
  80             </td>
  81           </tr>
  82           <tr>
  83             <td class="snss capitalize sky">
  84               <a href="http://lambdadelta.info/index.html#citations">citations</a>
  85             </td>
  86             <td class="snss capitalize magenta">
  87               <a href="http://lambdadelta.info/news.html#visibility">visibility</a>
  88             </td>
  89             <td class="snss capitalize white">
  90               <a href="http://lambdadelta.info/specification.html#v1">version 1</a>
  91             </td>
  92             <td class="snsn capitalize white">(<a href="http://lambdadelta.info/ground_1.html">background</a> - <a href="http://lambdadelta.info/basic_1.html">core</a>)</td>
  93             <td class="snsn capitalize white">(<a href="http://lambdadelta.info/static/matita/lambdadelta/">static HELM directory</a>)</td>
  94             <td class="snss capitalize orange">
  95               <a href="http://lambdadelta.info/documentation.html#v1">version 1</a>
  96             </td>
  97             <td class="snss capitalize green">
  98               <a href="http://lambdadelta.info/implementation.html#lddl">library</a>
  99             </td>
 100             <td class="sssn capitalize green">(<a href="http://lambdadelta.info/static/lddl/">static LDDL directory</a>)</td>
 101           </tr>
 102         </tbody>
 103       </table>
 104     </div>
 105     <div xmlns:ld="http://lambdadelta.info/" class="head2dx" id="specifications">Computer-checked formal specifications <img class="icon37" alt="[spacer]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b15.png" />
 106     </div>
 107     <div xmlns:ld="http://lambdadelta.info/" class="text">
 108       The systems of the λδ family are developed as machine-checked digital specifications,
 109       and are listed in the next table, which includes the major milestones.
 110    </div>
 111     <div xmlns:ld="http://lambdadelta.info/" class="text">
 112       The life cycle of a specification consists of four periods.
 113       <span class="emph alpha">Alpha:</span>
 114       the definitions are designed and the major propositions are proved,
 115       then the calculus is announced with a presentation.
 116       <span class="emph beta">Beta:</span>
 117       major changes and additions may occur before the calculus is released on paper.
 118       <span class="emph gamma">Gamma:</span>
 119       subsequent improvements occur until the specification is completed or superseded,
 120       while major changes and additions are announced and reported on paper.
 121       <span class="emph delta">Delta:</span>
 122       after its conclusion, the specification is modified just for maintenance.
 123    </div>
 124     <div xmlns:ld="http://lambdadelta.info/" class="text">
 125       <table cellpadding="4" cellspacing="0">
 126         <tbody>
 127           <tr>
 128             <td class="snns top capitalize italic gray">version</td>
 129             <td class="snnn top capitalize italic gray">name</td>
 130             <td class="snnn top capitalize italic gray">developed with</td>
 131             <td class="snnn top capitalize italic gray">stage</td>
 132             <td class="snnn top capitalize italic gray">started</td>
 133             <td class="snnn top capitalize italic gray">announced</td>
 134             <td class="snnn top capitalize italic gray">released</td>
 135             <td class="snnn top capitalize italic gray">concluded</td>
 136             <td class="ssnn top capitalize italic gray">references</td>
 137           </tr>
 138           <tr>
 139             <td class="snns top yellow">
 140               <a href="http://lambdadelta.info/specification.html#v3">Version 3</a>
 141             </td>
 142             <td class="snnn top yellow">"basic_3"</td>
 143             <td class="snnn top yellow" />
 144             <td class="snnn top yellow" />
 145             <td class="snnn top yellow" />
 146             <td class="snnn top yellow" />
 147             <td class="snnn top yellow" />
 148             <td class="snnn top yellow" />
 149             <td class="ssnn top yellow">
 150               <a href="http://lambdadelta.info/documentation#ldJ3a">J3a</a>
 151             </td>
 152           </tr>
 153           <tr>
 154             <td class="snns top orange">
 155               <a href="http://lambdadelta.info/specification.html#v2">Version 2</a>
 156             </td>
 157             <td class="snnn top orange">"basic_2"</td>
 158             <td class="snnn top orange">
 159               <a href="http://matita.cs.unibo.it/">Matita 0.99.2</a>
 160             </td>
 161             <td class="snns top orange">"A2"</td>
 162             <td class="snnn top orange">October 2015</td>
 163             <td class="snnn top orange" />
 164             <td class="snnn top orange" />
 165             <td class="snnn top orange" />
 166             <td class="ssnn top orange">
 167               <br />
 168             </td>
 169           </tr>
 170           <tr>
 171             <td class="nnns top orange">
 172               <br />
 173             </td>
 174             <td class="nnnn top orange">
 175               <br />
 176             </td>
 177             <td class="nnnn top orange">
 178               <br />
 179             </td>
 180             <td class="snns top orange">"A1"</td>
 181             <td class="snnn top orange">April 2011</td>
 182             <td class="snnn top orange">June 2014</td>
 183             <td class="snnn top orange">October 2014</td>
 184             <td class="snnn top orange">August 2015</td>
 185             <td class="ssnn top orange">
 186               <a href="http://lambdadelta.info/documentation#ldV2a">V2a</a>
 187               <a href="http://lambdadelta.info/documentation#ldR2c">R2c</a>
 188             </td>
 189           </tr>
 190           <tr>
 191             <td class="snns top orange">Abandoned</td>
 192             <td class="snnn top orange" />
 193             <td class="snnn top orange">
 194               <a href="http://coq.inria.fr/">Coq 7.3.1</a>
 195             </td>
 196             <td class="snnn top orange" />
 197             <td class="snnn top orange">March 2008</td>
 198             <td class="snnn top orange" />
 199             <td class="snnn top orange" />
 200             <td class="snnn top orange">February 2011</td>
 201             <td class="ssnn top orange">
 202               <br />
 203             </td>
 204           </tr>
 205           <tr>
 206             <td class="snss top red">
 207               <a href="http://lambdadelta.info/specification.html#v1">Version 1</a>
 208             </td>
 209             <td class="snsn top red">"basic_1"</td>
 210             <td class="snsn top red">
 211               <a href="http://coq.inria.fr/">Coq 7.3.1</a>
 212             </td>
 213             <td class="snsn top red" />
 214             <td class="snsn top red">May 2004</td>
 215             <td class="snsn top red">December 2005</td>
 216             <td class="snsn top red">November 2006</td>
 217             <td class="snsn top red">May 2008</td>
 218             <td class="sssn top red">
 219               <a href="http://lambdadelta.info/documentation#ldV1a">V1a</a>
 220               <a href="http://lambdadelta.info/documentation#ldJ1a">J1a</a>
 221             </td>
 222           </tr>
 223         </tbody>
 224       </table>
 225     </div>
 226     <div xmlns:ld="http://lambdadelta.info/" class="text">
 227      Informational pages on the specifications are provided.
 228    </div>
 229     <ul xmlns:ld="http://lambdadelta.info/" id="notice1">
 230       <li>
 231         <span class="emph alpha">Notice on displayed numerical acounts:</span>
 232       nodes are counted according to the "intrinsic complexity measure"
 233       [F. Guidi: "Procedural Representation of CIC Proof Terms"
 234       Journal of Automated Reasoning 44(1-2), Springer (February 2010), pp. 53-78].
 235    </li>
 236     </ul>
 237     <ul xmlns:ld="http://lambdadelta.info/" id="notice2">
 238       <li>
 239         <span class="emph alpha">Notice on displayed logical structures:</span>
 240       from the logical standpoint, the source scripts are grouped in "planes"
 241       and these are grouped in "components";
 242       the notation for the relations or functions
 243       introduced in each script, is shown in parentheses (? are placeholders).
 244    </li>
 245     </ul>
 246     <!-- VERSION 3 =========================================================== -->
 247     <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="v3">
 248       <img class="icon37" alt="[spacer]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b8.png" /> λδ version 3 (proposed)</div>
 249     <div xmlns:ld="http://lambdadelta.info/" class="text">
 250       The formal specification of λδ version 3
 251       is forthcoming.
 252    </div>
 253     <!-- VERSION 2 =========================================================== -->
 254     <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="v2">
 255       <img class="icon37" alt="[spacer]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b4.png" /> λδ version 2 (active)</div>
 256     <div xmlns:ld="http://lambdadelta.info/" class="text">
 257       The formal specification of λδ version 2
 258       is available in the following formats:
 259    </div>
 260     <ul xmlns:ld="http://lambdadelta.info/" id="source2">
 261       <li>
 262         <div class="text">
 263           <a href="http://lambdadelta.info/download/lambdadelta_2A1.tar.gz">lambdadelta_2A1 for Matita 0.99.2</a>
 264          (revised <span class="emph gamma">2014-10</span>).
 265          Source scripts.
 266          <a href="http://lambdadelta.info/documentation.html#ldR2c">Documentation (R2c)</a>.
 267       </div>
 268         <div class="text">
 269          The scripts are grouped in directories, first by part, then by component.
 270       </div>
 271         <div class="text">
 272           <span class="emph alpha">Notice:</span>
 273          the scripts are checked by the latest version of Matita from
 274          <a href="http://matita.cs.unibo.it/download.shtml">HELM Subversion repository</a>
 275          at path &lt;trunk/matita/&gt;.
 276       </div>
 277       </li>
 278     </ul>
 279     <div xmlns:ld="http://lambdadelta.info/" class="text">
 280       Informational pages on the parts of the specification:
 281       <a href="http://lambdadelta.info/ground_2.html">Background</a>,
 282       <a href="http://lambdadelta.info/basic_2.html">Core</a>,
 283       <a href="http://lambdadelta.info/apps_2.html">Applications</a>.
 284    </div>
 285     <!-- VERSION 1 =========================================================== -->
 286     <div xmlns:ld="http://lambdadelta.info/" class="head3sn" id="v1">
 287       <img class="icon37" alt="[spacer]" title="\lambda\delta butterfly" src="http://lambdadelta.info/images/b6.png" /> λδ version 1 (superseded)</div>
 288     <div xmlns:ld="http://lambdadelta.info/" class="text">
 289       The formal specification of λδ version 1
 290       is available in the following formats:
 291    </div>
 292     <ul xmlns:ld="http://lambdadelta.info/" id="source1">
 293       <li>
 294         <div class="text">
 295           <a href="http://lambdadelta.info/download/lambdadelta_1.tar.gz">lambdadelta_1 for Coq 7.3.1</a>
 296          (revised <span class="emph delta">2015-09</span>).
 297          Source scripts.
 298          <a href="http://lambdadelta.info/documentation.html#ldJ1a">Documentation (J1a)</a>.
 299          <ul>
 300             <li>
 301               <span class="emph delta">2015 January 15.</span>
 302             17 new lemmas and former lemma "eq_nat_dec" renamed as "nat_dec_neg".
 303          </li>
 304           </ul>
 305         </div>
 306         <div class="text">
 307          The scripts are grouped in directories, one for each part.
 308       </div>
 309       </li>
 310     </ul>
 311     <ul xmlns:ld="http://lambdadelta.info/" id="static1">
 312       <li>
 313         <a href="http://lambdadelta.info/static/matita/lambdadelta/">lambdadelta_1 for Matita 0.5</a>
 314       (revised <span class="emph delta">2011-09</span>).
 315       Static HTML pages generated by the <a href="http://helm.cs.unibo.it/">HELM</a> rendering engine.
 316       <ul>
 317           <li>
 318             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/pr3/pr3/pr3_confluence.con.html">
 319             Confluence of reduction</a>
 320          (Church-Rosser property).
 321       </li>
 322           <li>
 323             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/props/ty3_correct.con.html">
 324             Correctness of types</a>.
 325       </li>
 326           <li>
 327             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/props/ty3_unique.con.html">
 328             Uniqueness of types up to conversion</a>.
 329       </li>
 330           <li>
 331             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/pr3/ty3_sred_pr3.con.html">
 332             Subject reduction of the type assignment</a>.
 333       </li>
 334           <li>
 335             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/arity_props/ty3_sn3.con.html">
 336             Strong normalization of the typed terms</a>.
 337       </li>
 338           <li>
 339             <a href="http://lambdadelta.info/static/matita/lambdadelta/basic_1/ty3/dec/ty3_inference.con.html">
 340             Decidability of the type inference problem</a>.
 341       </li>
 342         </ul>
 343       </li>
 344     </ul>
 345     <ul xmlns:ld="http://lambdadelta.info/" id="dynamic1">
 346       <li>
 347         <a href="http://mowgli.cs.unibo.it:58080/apply?keys=RT&amp;xmluri=http://helm.cs.unibo.it/helm//html/folder/index.html&amp;prop.media-type=text/html&amp;param.thmedia-type=text/html&amp;param.thkeys=T1%2CT2%2CL%2CE&amp;param.embedkeys=d_c%2CTC1%2CHC2%2CL&amp;param.thencoding=UTF-8&amp;prop.encoding=UTF-8&amp;prop.doctype-public=-//W3C//DTD%20XHTML%201.0%20Transitional//EN&amp;param.doctype-public=-//W3C//DTD%20XHTML%201.0%20Transitional//EN&amp;param.encoding=UTF-8&amp;param.media-type=text/html&amp;param.keys=d_c%2CC1%2CHC2%2CL&amp;profile=default&amp;param.profile=default&amp;param.CICURI=theory:/matita/lambdadelta/">
 348          lambdadelta_1 for Matita 0.5</a>
 349       (revised <span class="emph delta">2011-09</span>).
 350       <a href="http://helm.cs.unibo.it/">HELM</a> directory.
 351       <span class="emph alpha">Notice: the HELM rendering engine is offline.</span>
 352       </li>
 353     </ul>
 354     <div xmlns:ld="http://lambdadelta.info/" class="text">
 355       Informational pages on the parts of the specification:
 356       <a href="http://lambdadelta.info/ground_1.html">Background</a>,
 357       <a href="http://lambdadelta.info/basic_1.html">Core</a>.
 358    </div>
 359     <div class="spacer">
 360       <img class="rule" alt="[Spacer]" title="\lambda\delta rainbow rule" src="http://lambdadelta.info/images/rainbow.png" />
 361     </div>
 362     <div xmlns:ld="http://lambdadelta.info/" class="spacer">
 363       <br />
 364     </div>
 365     <div xmlns:ld="http://lambdadelta.info/" class="spacer">
 366       <a href="http://validator.w3.org/check?uri=referer">
 367         <img class="w3c" alt="[Valid XHTML 1.1]" title="Valid XHTML 1.1" src="http://www.w3.org/Icons/valid-xhtml11-blue" />
 368       </a>
 369       <a href="http://jigsaw.w3.org/css-validator/check/referer">
 370         <img class="w3c" alt="[Valid CSS level 2]" title="Valid CSS level 2" src="http://www.w3.org/Icons/valid-css2-blue" />
 371       </a>
 372       <a href="http://www.w3.org/XML/">
 373         <img class="w3c" alt="[Generated from XML via XSL]" title="Generated from XML via XSL" src="http://lambdadelta.info/images/xml_xsl2.png" />
 374       </a>
 375       <a href="http://www.w3.org/Graphics/PNG/">
 376         <img class="w3c" alt="[PNG used here]" title="PNG used here" src="http://lambdadelta.info/images/PNGnow2.png" />
 377       </a>
 378       <a href="http://www.anybrowser.org/campaign/">
 379         <img class="w3c" alt="[Viewable with any browser]" title="Viewable with any browser" src="http://www.anybrowser.org/campaign/bvgraphics/abtfile.png" />
 380       </a>
 381     </div>
 382     <div xmlns:ld="http://lambdadelta.info/" class="spacer">
 383       <br />
 384     </div>
 385     <div xmlns:ld="http://lambdadelta.info/" class="spacer">Last update: Sat, 21 May 2016 22:22:39 +0200</div>
 386   </body>
 387 </html>