Абрамов С.М. Методы метавычислений и их применение

Подождите немного. Документ загружается.

8.3. Эффективная реализация нестандартных языков 119

8.3 Эффективная реализация

нестандар тны х языков

Рассмотрим произвольный модификатор m семантик. Допустим, что m реализован

на языке R. Тогда, в соответствии с определением 40, для любого языка L и любой

программы p∈L, любых данных d∈D

выполнено:

d = m [intL,p,d]

Как было отмеченно в разделе 8.1, вычисления p

d по данной схеме весьма неэффек-

тивны из-за наличия двух уров ней интерпретации.

Воспользуемся специализа цией для повышения эффективности вычисления p

d = m [intL,p,d]

= s[m

SDD

,intL] [p,d]

= s[s

SDD

] [intL] [p,d]

= s[s

] [m

SDD

] [intL] [p,d]

Построены три новые программы:

• miL=s[m

SDD

,intL], для любой программы p∈L и любых данных d ∈D

выполнено:

miL[p,d]=p

d. Таким образом, реализована одноуровневая m-нестандартная ин-

терпретация программы p. Назовем miL—m-нестандартным интерпретатором язы-

ка L.

• gmi=s[s

SDD

], для любого языка L, если intL∈R—интерпретатор L, то выполне-

но: gmi[intL]=miL. Назовем gmi генератором m-нестандартных интерпретаторов.

• ggnsi=s[ s

], для любого модификатора m выполнено следующее:

ggnsi[m

SDD

]=gmi.

Назовем ggnsi—генератором генераторов нестандартных интерпретаторов.

Получены проекции, описывающие построение средств эффективной (одноуровне-

вой) нестандартной интерпретации для произвольных модификаторов m и произволь-

ных языков L.

Еще раз применим основное свойство специализатора к определению нестандартной

семантики, но будем при этом выполнять фиксацию аргументов в ином порядке:

d = m [intL,p,d]

= s[m

SSD

,intL,p] [d]

= s[s

SSD

,intL] [p] [d]

= s[s

SSD

] [intL] [p] [d]

= s[s

SSD

] [m

SSD

] [intL] [p] [d]

Построены четыре новые программы:

• mpR=s[m

SSD

,intL,p], mpR—программа на языке R, для любых d∈D

выполнено:

mpR d = p

d. Таким образом, mpR—результат m-нестандартной компиляции с

языка L в язык R, компиляции, в процессе которой происходит два преобразо-

вания: преобразуется функция программы в соответствии с модификатором m и

генерируется текст на языке R, реализующий функцию p

120 Глава 8. Нестандартные семантики

• mcL=s[s

SSD

,intL], для любой p∈L выполнено: mcl[p]=mpR . Таким образом,

mcL—m-нестандартный компилятор с языка L на язык R.

• gmc=s[s

SSD

], для любого языка L, если intL∈R—интерпретатор L, то вы-

полнено: gmc[intL]=mcL. На зов ем gmc генератором m-нестандартных компилято-

ров.

• ggnsc=s[ s

SSD

], для любого модификатора m выполнено gg ns c[ m

SSD

]=gmc.

Таким образом, ggnsc—генератор генераторов нестандартных компиляторов.

Получены проекции, описывающие построение для произвольных модификаторов m

средств m-нестандартной компиляции с произвольного языка L в язык R.

Приведенные выше формулы, при их практическом воплощении, должны обеспе-

чить эффективную реализацию нестандартных семантик. Программист, имея на своем

рабочем столе эффективные средства метавычислений (инверторы, окрестностные ана-

лизаторы, специализаторы и многие другие, не названные здесь или еще не “открытые”

исследователями), будет способен не писать, а вычислять новые программы из старых.

И именно в этот момент можно будет говорить о том, что мы достигли автоматизации

программирования.

Приведенные выше семь проекций пока еще не были осуществлены на практике.

И хотя последние примеры выполнения специализации при помощи суперкомпилятора

[21, 22] демонстрируют возможность устранения двойных уровней интерпретации, все

же практическая реализация данных проекций потребует большего развития методов

метавычислений.

К счастью, совершенствовать методы метавычислений можно беспредельно (одно

из следствий теории суперкомпиляции и общей теории рекурсивных функций). Точ-

но так же не видно ограничений в создании все новых и новых методов применения

метавычислений в пра ктическом программировании.

Таким образом, метавычисления всегда останутся непбъятным и благодатным

полем для новых исследований.

Литература

[1] Турчин В.Ф. Эквивалентные преобразования рекурсивных функций описанных

на Рефале // Теория языков и методы программирования. Труды Симпозиума по

теории языков и мет одам программирования. Киев–Алушта. стр.31–42.

[2] Turchin V.F. The Phenomenon of Science // Columbia University Press, New York

1977. (Турчин В.Ф. Феномен науки: Кибернетический подход к эволюции // М.,

Наука, 199 3, 296 с.)

[3] Turchin V.F. A supercompiler system based on the language Refal // SIGPLAN

Notices, 14(2): 46-54, 1979.

[4] Turchin V.F. The language Refal, the theory of compilation and metasystem analysis //

Courant Institute of Mathematical Sciences, New York University. Courant Computer

Science Report No. 20, 1980.

[5] Turchin V.F., Nirenberg R., Turchin D.V. Experiments with a supercompiler //

Conference Record of the ACM Symposium on Lisp and Functional Programming.

p.47–55, ACM Press 1982.

[6] Turchin V.F. Program transformation by supercompilation //

Ganzinger H., Jones N.D. (ed.), Programs as Data Objects. (Copenhagen, Denmark).

Lecture No tes in Computer Science, Vol. 217, p.257–281 , Springer-Verlag 1 985 .

[7] Turchin V.F. The concept of supercompiler // ACM TOPLAS, 8(3): 292-325, 1986.

[8] Turchin V.F. Refal: a language for linguistic cybernetics // City College of the City

University of New York. 1986

[9] Turchin V.F. The algorithm of generalization in the supercompiler // Børner D., Ershov

A.P., Jones N. (ed.), Partial Evaluation and Mixed Computation. (Gammel Avernæs,

Denmark). pp.34 1– 35 3, North-Holland, 1988 .

[10] Romanenko A.Yu. The generation of inverse functions in Refal // Børner D., Ershov

A.P., Jones N. (ed.), Partial Evaluation and Mixed Computation. (Gammel Avernæs,

Denmark). pp.42 7– 44 4, North-Holland, 1988 .

[11] Gl¨uck R. Transformation of Refal graphs into Refal programs // City University New

York. Technical Report (Presented at the International Seminar on Metacomputation.

February 21-22, 1989, New York) 1989.

[12] Gl¨uck R. Inside the supercompiler // City University New York. Technical R eport

1989.

121

122 Литература

[13] Gl¨uck R., Turchin V.F. Experiments with a self-applicable supercompiler // City

University New York. Technical Report 1989.

[14] Gl¨uck R., Turchin V.F. Application of metasystem transition to function inversion and

transformation // Pro ce edings of the ISSAC ’90. (Tokyo, Japan). 286-287, ACM Press

1990.

[15] Абрамов С.М. Метавычисления и логическое программирование // Программи-

рование No 3, 1991, стр.31–44.

[16] Romanenko A.Yu. Inversion and metacomputation // Proceedings of the Symposium

on Partial Evaluation and Semantics-Based Prog ram Manipulation. (Yale University,

Connecticut). p.12–22, ACM Press 199 1.

[17] Romanenko A.Yu. A language for direct and inverse programming and its semantics

// Institute for the Physical Chemistry, Academy of Sciences of the USSR, Moscow.

1992.

[18] Gl¨uck R., Klimov And. Occam’s razor in metacomputation: the notion of a perfect

process tree // Cousot P., Falaschi M., Fil´e G., Rauzy A. (ed.), Static Analysis.

Proceedings. (Padova, Italy). Lecture Notes in Computer Science, Vol. 72 4, 112 -12 3,

Springer-Verlag 1993.

[19] Turchin V.F. Program transformation with metasystem transitions // Journal of

Functional Programming, 11, 1993

[20] Gl¨uck R., Klimov And. Metacomputation as a Tool for Formal Linquistic Modeling //

Cybernetics and Systems Research’94. World Scientiﬁc: Singapure 1994

[21] Nemytykh A.P., Turchin V.F. Metavariables: Their Implementation a nd Use in

Program Transformation //

Technical Report TR 95.6.5.002, The City College of New York, 1995.

[22] Nemytykh A.P., Turchin V.F. A Self-applicable Supercompiler // Technical Report TR

95.6.5.001, The City College of New York, 1995.

[23] Futamura Y. Partial evaluation of computation process—an approach to a compiler-

compiler // Systems, Computers, Controls, 2(5): 45-50, 1971.

[24] R.M.Burstall, J.Darlington. A transformational system for developing recursive pro-

gramms // JACM, 24(1), 1977, pp. 44–67.

[25] J.Darlington. An experimental programm transformation and synthesis system.—

Artiﬁtial intelligense, 16(1), 1981, pp. 1–46.

[26] Romanenko S. A compiler generator produced by a self-applicable specializer can have

a surprisingly natural and understandable s tructure // Børner D., Ershov A.P., Jones

N. (ed.), Partial Evaluation and Mixed Computation. (Gl. Avernæs, Denmark). pp.445-

463, North-Holland, 1988.

Литература 123

[27] Jones N.D., Sestof t P., Søndergaard H. Mix: a selfapplicable partial evaluator for

experiments in compiler g eneration //

Lisp and Symbolic Computation, 2(1): 9-50, 198 9.

[28] Кальниньш А.А., Борзов Ю.В. Инвентаризация идей тестирования программ. Ме-

тодическая разработ ка по математическому обеспеченю ЭВМ // Рига, ЛГУ, 1981.

[29] Ramamoorthy C.V., Yj S.B.F., Chen W.T. On the automated generation of program

test data // IEEE Transactions on Software Engineering, 1976, SE-2, No 4, p.293–300.

[30] Alberts D.S. The economics of software quality asurance // AFIPS Conf.Proc., 1976

NCC, Montvale, 1976, p.433–442.

[31] Kernighan B.W., Plauger P.J. The elements of programming style. New York, McGraw-

Hill, 1974.

[32] Moranda P.B. Asymptotic limits to program testing // INFOTECH State of the Art

Report: Software Testing, vol.2, 1979, p.201–212.

[33] Мессих И.Г.Б, Штрик А.А. Методика и средства анализа структуры и характери-

стик сложных комплексов программ реального времени // Синтез, тестирова ние,

верификация и о тладка программ. Рига: ЛГУ, 1981, с.152-153.

[34] Rault J.-C., Bouissou B. Quantitative measures for software reliability: a review //

INFOTECH State of the Art Repo rt: Software Testing. 1979, v.2, p.213-229.

[35] Abramov S.M. Metacomputation and program testing // 1st International Workshop

on Automated and Algorithmic Debugging. (Link¨oping, Sweden). p.121–135, Link¨opi-

ng University 1993.

[36] Братко И. Программирование на языке Пролог для искусственного интеллекта //

Мисква, “Мир”, 1990. 559 с.

[37] Kowalski R. Logic for Problem Solving // Artiﬁcal Intellegence Series, North Holland,

1979.

[38] Hudak P., Wadler Ph. et al. Report on the programming language Haskell, a non-strict

purely functional language (Version 1.1) // Technical report Yale University/Glasgow

University. August 1991.

[39] Manna Z. Theory of computation // New York, 1974, 448 p.

124 Литература

Абрамов С.М.

Методы метавычислений и их применение

Оригинал-макет подготовлен С.М.Абрамовым в системе L

X 2e