Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Martin Ward Newsgroups: comp.compilers Subject: Re: Are there "compiler generators"? Date: Sun, 29 May 2022 12:00:12 +0100 Organization: Compilers Central Lines: 54 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-05-059@comp.compilers> References: <22-05-054@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="54404"; mail-complaints-to="abuse@iecc.com" Keywords: tools, theory Posted-Date: 29 May 2022 18:16:48 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <22-05-054@comp.compilers> Content-Language: en-GB Xref: csiph.com comp.compilers:3031 On 28/05/2022 23:27, Roger L Costello wrote: > There are lexer generators. Flex is a lexer generator. > > There are parser generators. Bison is a parser generator. > > Are there compiler generators? Suppose a program F(x, y) takes two inputs and produces an output. Suppose input x is known at compile time. Then we can optimise the program F(x, .) by precomputing all the computations that depend on x to give a program G(.) which can be applied to y to produce the output F(x, y): G(y) = F(x, y) This optimisation process is called "partial evaluation" or "specialisation". An interpreter is a program F(p, d) which takes a program p and some input data d and produces the result of executing p on d. In theory a partial evaluator (a "specialiser") can be applied to an interpreter and the source code for a program to give an executable which is a specialised version of the interpreter which only runs the given source code, does not require the source code to be applied and runs faster than the original combination of interpreter and source code. To take this to the next level: specialising the specialiser for the interpreter generates a compiler for the interpreted language. So this is a type of "compiler generator". Finally, specialising the specialiser for itself gives a tool that can convert any interpreter into an equivalent compiler. https://en.wikipedia.org/wiki/Partial_evaluation Futamura, Y. (1999). "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler". Higher-Order and Symbolic Computation. 12 (4): 381–391. CiteSeerX 10.1.1.10.2747. doi:10.1023/A:1010095604496. S2CID 12673078. In practice, there is a lot more to writing a compiler than just partially evaluating an interpreter. (The difference between theory and practice is that in theory there is no difference between theory and practice, but in practice there is.) -- Martin Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4