Subject: Hughes.-.Type.Specialisation.for.the.Lambda-Calculus.(1996).djvu
From: Sergei Romanenko (roman@integrum.ru)
Date: Tue Jun 15 2004 - 15:35:49 MSD
Добрый день!
Интересно было бы разобраться, как "тИповая специализация" (или
"специализация типов", или "специализация по типам") соотносится с
суперкомпиляцией:
ed2k://|file|[Functional.Programming,.Partial.Evaluation].Hughes.-.An.Introd
uction.to.Program.Specialisation.by.Type.Inference.(1996).djvu|49176|CC1513B
AC951AAF204E697F7DB4010FA|/
ed2k://|file|[Functional.Programming,.Partial.Evaluation].Hughes.-.A.Type.Sp
ecialisation.Tutorial.(1998).djvu|126136|55724CBEA735E9B3023B1C837ABE1809|/
ed2k://|file|[Functional.Programming,.Partial.Evaluation].Hughes.-.Type.Spec
ialisation.for.the.Lambda-Calculus.(1996).djvu|136118|BA52B3919D8FCDCD0491D3
08CC652104|/
Понятно, что "простые" специализаторы не делают "ретипирование": т.е.
"статические" выражения полностью вычисляются и превращаются в константы, а
"динамические" выражения вываливаются в остаточную программу, и при этом
представление "динамических" данных, остается таким же, как и в исходной
программе. (С соответствующими неприятными последствиями при специализации
интерпретаторов.)
И "повышатель арности"
ed2k://|file|[Functional.Programming,.Partial.Evaluation].Romanenko.-.Arity.
Raiser.and.its.Use.in.Program.Specialization.(1990).djvu|170908|EDC6CB5E6BD0
A6944FBDD3F22DAF81FE|/
ed2k://|file|[Functional.Programming,.Partial.Evaluation].Romanenko.-.Povy`s
hatel`.arnosti.i.ego.ispol`zovanie.pri.specializacii.programm.(1990)(ru).djv
u|122357|5A4B5C9F5303F439B3635C7609C60D47|/
был присобачен к такому специализатору, чтобы частично снять остроту этой
проблемы (особенно при самоприменении таких специализаторов).
А при работе Суперкомпилятора представление данных в остаточной программе
может отличаться от оного в исходной программе. Т.е. и вычисления над
константами, и "ретипирование" происходят одновременно. При этом, хотя сам
Рефал является "бестиповым" (в смысле, языком с "динамической типизацией"),
при работе Суперкомпилятора "типы" появляются на метауровне, в виде
"образцов", "окрестностей" и др. При этом информация о константах в
Суперкомпиляторе именно в "типах" и хранится...
А у Хьюза как раз происходит одновременное преобразование фрагмента
программы вместе с "типом" этого фрагмента.
Интересно, имеет ли то, что делает Хьюз какое-то отношение к "смешанным
вычислениям". В свое время общественность пыталась разобраться в разнице
между "частичными" и "смешанными" вычислениями, но вопрос так и остался
темным. (Может быть из-за того, что имевшиеся определения как "частичных",
так и "смешанных" вычислений были такими "резиновыми", что их можно было без
большого труда "натягивать" одно на другое... :-) )
Еще одна интересная особенность подхода Хьюза в том, что информация о
"типах" может течь и в "прямом" и в "обратном" направлении. Это - вполне
естественно в его парадигме, поскольку при типизации в духе Хиндли-Милнера
"проверка типов" (type checking), которая на самом-то деле является
"выявлением типов" (type inference), основана на решении системы уравнений.
А методы решения таких уравнений основаны на унификации с последующим
распространением информации по всей системе уравнений. (Кстати, эти методы
фактически были придуманы еще Диафантом, но он их применял для решения
систем линейных уравнений в целых числах.)
А одна из особенностей Суперкомпилятора в том, что в нем информация может
течь и в "прямом" и в "обратном" направлении. Например, стоят рядом два
(невложенных друг в друга) вызова функций. Начинаем раскрывать один из них.
При этом выполняются сужения, из-за которых аргумент другого вызова
становится более "конкретным", что дает возможность выполнить какие-то
"статические" вычисления.
В общем, возникает ощущение, что Хьюз забрел в ту же степь, где находится и
Суперкомпилятор. Однако, степь - она большая, и насколько близко он
находится от Суперкомпилятора - сразу неочевидно.
Сергей Романенко
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:25:01 MSD