Большая техническая энциклопедия
2 4 7
D L N
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
Я- ЯБ ЯВ ЯГ ЯД ЯЗ ЯЙ ЯК ЯЛ ЯМ ЯН ЯП ЯР ЯС ЯУ ЯЧ ЯЩ

Я-исчисление

 
Я-Исчисление может быть также дополнено произвольным набором констант, таких, как целые числа, и связанных с ними функций, называемых 6-правилами.
В Я-исчислении вполне возможно записать два выражения, которые являются семантически идентичными, но синтаксически отличаются друг от друга из-за различных имен переменных.
Удалив б-правила, мы получим чистое Я-исчисление. В нем можно выразить любые функции, несмотря на отсутствие б-правил.
Рекурсивные функции могут быть выражены в Я-исчислении с помощью специальной функции, называемой У-комбинатором, которая находит наименьшую фиксированную точку функции.
Здесь мы отходим от модели редукции, предлагаемой в Я-исчислении, где вычисление выражений записывается в чисто текстовой форме.
Я нахожу очень странным то обстоятельство, что мои модели Я-исчисления не были найдены кем-либо ранее, но я очень воодушевлен тем, что новые типы моделей с новыми свойствами, как, например, домены Гордона Плоткина [10], открываются сейчас. Лично я уверен, что для этого все уже подготовлено как на теоретическом, так и на прикладном уровнях. Джон Рейнолдс и Роберт Милн независимо друг от друга ввели новый индуктивный метод доказательства эквивалентностей; Робин Милнер продолжает в Эдинбурге интересную работу по LCF и технике доказательств. Начало направлению доказательства через модели было положено теоремой Дэвида Парка о связи оператора неподвижной точки с так называемым парадоксальным комбинатором Я-исчисления, и это положило начало изучению бесконечных, но вычисляемых операторов, которое продолжается по многим линиям. Другое направление разрабатывается в Новосибирске под руководством Ю. Л. Ершова, а Карл X.
Вершина применения выполняет наиболее сложную операцию, эквивалентную ( З - редукции в Я-исчислении. Имеются две входящие дуги. Первая из них, которая по соглашению рисуется с левой стороны, соответствует применяемой функции, а вторая соответствует аргументу этой функции, как показано ниже. Обе входящие дуги должны иметь данные в модели, управляемой данными, а в ленивой модели, управляемой запросами, данные необходимы только на входной дуге, соответствующей функции. Результат применения в конце концов помещается на выходящую дугу, иногда после подстановки подграфа, представляющего тело функции пользователя, которая подается на функциональный вход.
С / С /, показав, что / является нормальной формой SKK в Я-исчислении, или с помощью правил редукции для применений 5 и / С, предполагая экстенсиональность в КЛ.
Вторая цепочка изоморфизмов. Мы обрисовали, почему & - ж, пространство функций бесконечного порядка, является моделью Я-исчисления.
Особое значение здесь, однако, имеет тот факт, что У может быть записан в виде Я-выражения, что очень важно для чистого Я-исчисления, не имеющего встроенных функций.
Связь между именами переменных и их значениями обычно называется контекстом, и мы говорим, что механизм редукции является основанным на контексте, а не на копировании, как в Я-исчислении. Мы более подробно рассмотрим контексты в гл.
Исчисление было использовано как средство для описания ( чисто синтаксического) свойств математических функций и эффективной обработки их в качестве правил. Я-исчисления особенно удобна для формального описания манипулирования функциями и даже в качестве промежуточного кода, в который можно транслировать исходную программу.
Мы рассмотрим наиболее общую реализацию, основанную на контексте, которая интерпретирует выражения - исчисления. Как мы видели, Я-исчисление имеет достаточную мощность для представления любого функционального языка и поэтому обеспечивает хорошую основу для построения практических реализаций. Мы видели также, как функциональные языки транслируются в такую форму, чтобы было возможно принять некоторый вариант Я-исчисления в качестве удобного промежуточного кода для их реализации. Он использует четыре стека, обозначаемые S, Е, С и D для обеспечения механического вычисления Л - выражений.
Мы рассмотрим наиболее общую реализацию, основанную на контексте, которая интерпретирует выражения - исчисления. Как мы видели, Я-исчисление имеет достаточную мощность для представления любого функционального языка и поэтому обеспечивает хорошую основу для построения практических реализаций. Мы видели также, как функциональные языки транслируются в такую форму, чтобы было возможно принять некоторый вариант Я-исчисления в качестве удобного промежуточного кода для их реализации. Он использует четыре стека, обозначаемые S, Е, С и D для обеспечения механического вычисления Л - выражений.

Мостовски, который в это же время находился в Оксфорде, просто не мог поверить, что тип функциональных пространств, который я определил, вообще мог иметь конструктивное описание. При появлении сомнений в полезности принудительной жесткости логических типов, в чем я пытался убедить Стречи, я пришел к выводу, что одно из этих пространств изоморфно своему собственному функциональному пространству, которое обеспечивает модель бестипового Я-исчисления. Окончание этой истории описано в литературе.
Интересные сведения, проливающие свет на историю Я-ис-числения, дает участие в ней Алана Тьюринга. Конечно, поздние взгляды Тьюринга на компьютеры оказали на Стречи большое влияние, однако сейчас не время проводить полный исторический анализ. Хотя я никогда не встречался с Тьюрингом ( он умер в 1954 г.), соприкосновение с ним через Черча, Стречи и моих нынешних коллег по Оксфорду, Ле Фокса и Робина Ганди, оказалось достаточно близким несмотря на то, чщ в то время я только заканчивал университет, Черч больше не занимался Я-исчислением и мы никогда не обсуждали его работу с Тьюрингом.
Я нахожу очень странным то обстоятельство, что мои модели Я-исчисления не были найдены кем-либо ранее, но я очень воодушевлен тем, что новые типы моделей с новыми свойствами, как, например, домены Гордона Плоткина [10], открываются сейчас. Лично я уверен, что для этого все уже подготовлено как на теоретическом, так и на прикладном уровнях. Джон Рейнолдс и Роберт Милн независимо друг от друга ввели новый индуктивный метод доказательства эквивалентностей; Робин Милнер продолжает в Эдинбурге интересную работу по LCF и технике доказательств. Начало направлению доказательства через модели было положено теоремой Дэвида Парка о связи оператора неподвижной точки с так называемым парадоксальным комбинатором Я-исчисления, и это положило начало изучению бесконечных, но вычисляемых операторов, которое продолжается по многим линиям. Другое направление разрабатывается в Новосибирске под руководством Ю. Л. Ершова, а Карл X.
Поскольку в каноническом А-исчислении нет имен переменных, там нет эквивалента правилу а-преобразования выражений, и это ставит вопрос о возможности выполнения р-редукции в присутствии свободных переменных. Оказывается, можно выполнять преобразование, эквивалентное Р - редукции в А. Но правило р - редукции является более сложным по сравнению с правилом р-редукции, так как оно перенумеровывает канонические переменные в теле функции, даже если эти переменные не нужно замещать; это во многом похоже на ос-преобразование. Интересное свойство Р - редукции в присутствии свободных переменных состоит в том, что такое переименование ( перенумерация) связанных переменных с целью сделать их имена уникальными по отношению к свободным переменным аргумента становится формальным алгоритмом ( фактически частью самого правила р - редукции) в Я-исчислении де Брейна.
Я родился в Калифорнии и приступил к работе в области математической логики, будучи студентом младших курсов в - Беркли в начале 1950 - х годов. Больше всего на меня повлияли, конечно, Альфред Тарский, его коллеги и студенты Калифор - - нийского университета. Наряду с другими предметами под руководством Рафаэля и Джулии Робинсон, которых я хочу поблагодарить за многие ценные идеи, я изучал теорию рекурсивных функций. Эти концепции, как вы знаете, до сих пор широко обсуждаются в философии естественного языка. Я пытался применить идеи подхода Тарского к алгоритмическим языкам, преимущество которых заключается по крайней мере в том, что они достаточна хорошо синтаксически формализованы. Возможно, требует обсуждения, действительно ли мне удалось, руководствуясь схемами Стречи и других ученых, найти правильные определения терминов. Именно я первым заявил о том, что не все проблемы решаются одним лишь подбором денотатов к некоторым языкам: для языков типа ( чистого) Я-исчисления нужные определения в большинстве случаев найдены, однако многие понятия программирования до сих пор остаются неопределенными.
 
Loading
на заглавную 10 самыхСловариО сайтеОбратная связь к началу страницы

© 2008 - 2014
словарь online
словарь
одноклассники
XHTML | CSS
Лицензиар ngpedia.ru
1.8.11