Return-Path: Delivery-Date: Received: from ted.cs.uidaho.edu (no rfc931) by swan.cl.cam.ac.uk with SMTP (PP-6.4) outside ac.uk; Tue, 9 Feb 1993 13:56:47 +0000 Received: by ted.cs.uidaho.edu (16.6/1.34) id AA06980; Tue, 9 Feb 93 05:38:33 -0800 Sender: info-hol-request@edu.uidaho.cs.ted Errors-To: info-hol-request@edu.uidaho.cs.ted Precedence: bulk Received: from swan.cl.cam.ac.uk by ted.cs.uidaho.edu (16.6/1.34) id AA06975; Tue, 9 Feb 93 05:38:27 -0800 Received: from auk.cl.cam.ac.uk (no rfc931) by swan.cl.cam.ac.uk with SMTP (PP-6.4) to cl; Tue, 9 Feb 1993 13:37:54 +0000 To: info-hol@edu.uidaho.cs.ted Subject: Re: Basic Rules In-Reply-To: Your message of Tue, 09 Feb 93 12:46:24 +0000. <"swan.cl.ca.344:09.02.93.12.46.33"@cl.cam.ac.uk> Date: Tue, 09 Feb 93 13:37:47 +0000 From: John Harrison Message-Id: <"swan.cl.ca.635:09.02.93.13.38.03"@cl.cam.ac.uk> Richard Boulton writes: > The important point is that any rules implemented using mk_thm should be > trustworthy. Thus, having the smallest number of rules possible is not the > most important thing. It is more important for them to be simple, so that > they can readily be seen to be correct (or better, can be formally > verified). I agree -- and this seems a very good argument not to have SUBST as primitive, but rather AP_TERM and AP_THM (or just MK_COMB), which are in any case ubiquitous in the depth conversions, and hence rewriting. One could then implement SUBST using the following sort of scheme: A |- x = y ------------------------------------ AP_TERM A |- (\z. u[z]) x = (\z. u[z]) y ------------------------------------ BETA_CONV at depth A |- u[x] = u[y] It wouldn't be as fast, especially for multiple substitutions, but it's rewriting that really matters. Furthermore, people might start to understand how SUBST does its renaming. John.