Subject: Re: Лямбда-исчисление в рефале
From: Arkady Klimov (klark@bagirra.net)
Date: Tue Aug 28 2001 - 19:52:08 MSD
----- Original Message -----
From: Mike Potanin <potanin@mccme.ru>
To: <refal@botik.ru>
Sent: Monday, August 27, 2001 12:38 PM
Subject: Лямбда-исчисление в рефале.
|
| С моей точки зрения очень неестественно то что в функциональном языке
| не поддерживается лямбда-исчисление. Может это вызладет как попытка
| сделать из рефала haskell, но я решил расширить рефал в порядке
| эксперемента. В общем то добавилась всего одна существенная конструкция (и
| одна дополнительная для оптимизации) и расширилась семантика функции Mu.
| Я добавил к существующим типам (символ, целое и терм) еще один -
| замыкание (closure). Синтаксис естественный
| Adder {
| s1 = { s2 = <Add s1 s2>; };
| }
Как я понял, речь идет о введении лямбда-абстракции в рефал. Согласен с Сергеем
Абрамовым, что нужно как-то синтаксически разнести ее с обычными блоками.
В контесте рефала-6 я давно подумываю об аналогичном расширении со знаком '*'
перед '{'.
Правда, пример тут убогий. Фактически оно тут использовано лишь для закарривания.
Это же самое в рефале выразимо гораздо проще:
Adder {
s1 = *Add s1 ;
}
Я пишу как в рефале-6: звездочка перед именем делает его символом-ссылкой (в Р+ это знак '&').
Поскольку далее можно написать <<Adder 1> 2> и получить 3.
[ Ежели желаемо в роли функции иметь всегда терм, то пишите
Adder {
s1 = (*Add s1) ;
}
Результат будет тот же, поскольку в рефале-6 <(e1) e2> вычисляется как <e1 e2>.]
Пример похитрее будет такой:
Map sf sx ey = <sf ex> <Map sf ey>;
sf =;
Halfs ex = <Map *{ sd = <DIV sd 2> } ex>;
| И с замыканием можно работать функцией Mu
| <Mu <Adder 1> 2>
А функцию Mu здесь не при чем. Она семантически как бы состоит из двух частей:
1) разрешения имени (т.е. идентификатора) в контексте модуля - превращения его в
(ссылку на) функцию и 2) последующего вызова этой функции.
А поскольку результат <Adder ...> - замыкание, то есть сама функция, а не ее имя
(идентификатор), то и писать надо просто <<Adder1> 2>. Правда в рефале-5 такая
запись невозможна (в отличие от рефалов 6 и +).
| Второе расширение не принципиально - замыкания можно использовать вместо
| имени функции
| <{ s2 = <Add 1 s2>; } 2>
| эквивалентно
| <Mu { s2 = <Add 1 s2>; } 2>
| но у меня реализованно немного эффективней (и на пол-часа раньше :-)).
| Что же это дает?
| Во первых это покрывает with-блок
| e1, e1 : { блок };
| полностью эквивалентно
| e1 = <{ блок } e1>
| и по моему немного естественней.
Это для кого как. Мне всегда было естественней то, что Вы назвали with-блок
(для меня это похоже на let-терм).
Потому что *сначала* вычисляется e1 (это может быть сложное выражение),
а уж *потом* к нему применяется функция { блок }. То есть порядок чтения
слева направо соответствует логике вычислений (сначала аргумент,
потом функция). [Обратный порядок может выглядеть естественным разве что
в контексте ленивого языка].
| Во вторых функции - достаточно общий объект, и через него можно
| реализовать произвольные структуры, например атрибутированный набор.
| Person {
| (e1) (e2) = { 'name' = e1; 'secondname' = e2; };
| }
| Работать с такими объектами по моему удобнее, чем таскать за собой сложную
| структуру. (В прочем это субъективно, возможно это привычка пришла из
| scheme и была усилена haskell, а в рефале она лишняя).
Но это уже не структура, а функция от имени атрибута. Ее можно только
применять к именам. Но, например, от нее уже никак не получишь
<ListAttrNames <Person ...> >, ожидая что-то вроде ('name')('secondname') .
|
| Хотя мне такое расширение нравится, все-таки возникли вопросы.
| На сколько это усложнит суперкомпиляцию (мне кажется что в языке стоит
| оставлять только те конструкции, для которых суперкомпиляция эффективна)?
| Создает ли это проблемы для введения в рефал статической типизации?
Это расширение никак не усложнит суперкомпиляцию, поскольку
оно легко выразимо в терминах рефала без этого расширения -
через компиляцию в этот последний. Но осложнить может
не замыкание, а использование его в контексте <sf ex>
для определения "функций высших порядков" типа Map,
когда sf - неизвестная функция.
Всего наилучшего
Аркадий.
|
| P.S. Исходный текст этой эксперементальной реализации лежит
| http://pm.kmost.express.ru/~pm/hrefal.tgz
| Слиль в них плохой (первая моя программа на haskell), но
| поэксперементировать можно. Накоплю опыта, я ее с нуля перепишу.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD