程序优化技术：部分评估与自动程序生成详解

需积分: 7 57 浏览量更新于2024-07-18 收藏 1.66MB PDF 举报

"《部分评估与自动程序生成》是一本深度探讨程序优化技术——偏应用（partial evaluation）或程序专门化——的著作。作者Neil D. Jones、Carsten K. Gomard和Peter Sestoft来自丹麦的计算机科学领域，他们在书中阐述了构建针对多种编程语言的偏应用器的一般原则。本书不仅提供理论基础，还通过实例和实际应用展示了这一技术在实践中的应用，并引用了大量的相关文献，以便读者深入了解这一领域的最新进展。章节内容丰富，涵盖了偏应用的核心概念，即如何通过对程序进行部分求值，根据特定输入或上下文条件，自动生成优化后的代码，从而提高程序执行效率。这一过程涉及抽象代数、类型系统、编译原理等多个方面，对于理解程序如何在运行时动态适应环境变化具有重要意义。书中特别强调了偏应用的实用价值，包括但不限于代码重用、编译器优化、智能代理设计以及自适应软件等方面的应用。作者们通过详细的章节划分，引导读者逐步掌握偏应用的原理和实施方法，同时也分享了他们在教学和研究中的实践经验。此外，该书还介绍了如何构建偏应用器的工具和技术，以及在实践中遇到的挑战和解决方案。由于版权问题，原由Prentice Hall International出版的书籍在某个时间点回归到了作者手中，他们提供了在线资源，如书的主页<http://www.dina.kvl.dk/~sestoft/pe/book/pe_book.html>，供读者查阅和交流。《部分评估与自动程序生成》是一本深入浅出的学术著作，为编程语言研究者、开发者和对程序优化感兴趣的读者提供了宝贵的理论指导和实践案例，是理解和应用偏应用技术的重要参考文献。"

Introduction

1.2.3 A sampler of applications

Because of its generality and conceptual simplicity, partial evaluation is applicable

to a wide range of problems. The essence of applying partial evaluation is to solve

a problem indirectly, using some relatively static information to generate a faster

special-purpose program

, which is then run on various data supplied more dynam-

ically. Many applications b egin with general and rather `interpretive' algorithms.

First, we give some examples which follow this line of thought, but do not use

a partial evaluator as such. An early example is a `symb olic' solution metho d

for sparse systems of linear equations [107]. Another is sp eeding up execution of

functional programs by `re-op ening closures' [13]; and gaining signicant parser

sp eedups by compiling LR parsing tables into machine co de [216]. A recent appli-

cation is a very fast op erating system kernel which uses on-the-y co de generation

[221].

Related problems and a variety of others have b een solved using general-purp ose

partial evaluators. Applications include circuit simulation [14], computer graphics

[186], neural net training [126], numerical computations [22], optimizing hard real-

time systems [205], and scientic computing of several sorts [21].

The most developed area, programming language pro cessors and esp ecially com-

piling, will be discussed in detail in several later chapters and thus are not men-

tioned here. Related applications include pattern matching in general [54], and as

applied to a lazy language [138] or constraint logic programming [252]; eciently

implementing term rewriting systems [250]; and Lafont's interaction nets [18].

The following sketches give something of the avor of problem-solving by pro-

gram sp ecialization.

Computer graphics.

`Ray tracing' rep eatedly recomputes information ab out the

ways light rays traverse a given scene from dierent origins and in dierent di-

rections. Sp ecializing a general ray tracer to a xed scene to transform the scene

into a sp ecialized tracer, only good for tracing rays through that one scene, gives

amuch faster algorithm.

Database queries.

Partial evaluation can compile a query into a sp ecial-purp ose

search program, whose task is only to answer the given query. The generated

program may b e discarded afterwards. Here the input to the program generator is

a general query answerer, and the output is a `compiler' from queries into search

programs.

Neural networks.

Training a neural network typically uses much computer time,

but can b e improved by sp ecializing a general simulator to a xed network top ology.

Scientic computing.

General programs for several diverse applications including

orbit calculations (the

-body problem) and computations for electrical circuits

have b een sp ed up by sp ecialization to particular planetary systems and circuits.

Computation in one stage or more

1.3.3 Semantics-directed compiler generation

By this we mean more than just a to ol to help humans write compilers. Given

a sp ecication of a programming language, for example a formal semantics or an

interpreter, our goal is

automatical ly

and

correctly

to transform it into a compiler

from the sp ecied `source' language into another `target' language [195,215].

Traditional compiler writing to ols such as parser generators and attribute gram-

mar evaluators are not semantics-directed, even though they can and do pro duce

compilers as output. These systems are extremely useful in practice | but it is

entirely up to their users to ensure generation of correct target co de.

The motivation for automatic compiler generation is evident: thousands of

p erson-years have b een sp ent constructing compilers by hand; and many of these

are not correct with resp ect to the intended semantics of the language they com-

pile. Automatic transformation of a semantic sp ecication into a compiler faithful

to that semantics eliminates such consistency errors.

The three jobs of writing the language sp ecication, writing the compiler, and

showing the compiler to be correct (or debugging it) are reduced to one: writing

the language sp ecication in a form suitable as input to the compiler generator.

There has b een rapid progress towards this research goal in the past few years,

with more and more sophisticated practical systems and mathematical theories

for the semantics-based manipulation of programs, including compiler generation.

One of the most promising is partial evaluation.

1.3.4 Executable sp ecications

A still broader goal is

ecient implementation of executable specications

. Exam-

ples include compiler generation and parser generation, and others will be men-

tioned later. One can naturally think of programs

int

and

parser

ab oveas

speci-

cation executers

: the interpreter executes a source program on its inputs, and the

parser applies a grammar to a character string. In each case the value of the rst

input determines how the remaining inputs are to b e interpreted. Symbolically:

[[

spec-exec

]]

[spec,in

...

,in

]

output

The interpreter's source program input determines what is to be computed. The

interpreter thus executes a sp ecication, namely a source

-program that is to be

run in language

. The rst input to a general parser is a grammar that denes

the structure of a certain set of character strings. The sp ecication input is thus

a grammar dening a parsing task.

A reservation is that one can of course also commit errors (sometimes the most

serious ones!) when writing sp ecications. Achieving our goal do es not eliminate

all errors, but it again reduces the places they can o ccur to one, namely the sp eci-

cation. For example, a semantics-directed compiler generator allows quick tests of

剩余424页未读，继续阅读

_夜空的繁星_

粉丝: 7
资源: 6

程序优化技术：部分评估与自动程序生成详解

Automatic trimap and alpha-matte generation for digital image matting

JStillery通过PartialEvaluation实现的高级JavaScript反混淆

D:\百杉\前端\c#\01.cs(3,7): error CS0260: 类型“Program”的声明上缺少 partial 修饰符；存在此类型的其他分部声明 [D:\百杉\前端\c#\c#.csproj]

题目：设 \( e^z - xyz = 0 \)， 求 \(\frac{\partial^2 z}{\partial x \partial y}\)

数据库系统 partial participation

partial is not defined

public partial class MaintainServices 中的partial 代表什么

partial frequency trajectory

name 'expect_partial' is not defined

最新资源

题目：设 \( e^z - xyz = 0 \)，求 \(\frac{\partial^2 z}{\partial x \partial y}\)