Subject: Re: Re: Re: Re: Re: Как следует компилиоват ь ре фаль скую операциюотождествлени
From: Arkady Klimov (klark@bagirra.net)
Date: Fri Dec 08 2000 - 15:34:50 MSK
----- Original Message -----
From: Andrey Slepuhin <pooh@msu.ru>
To: Arkady Klimov <klark@bagirra.net>
Cc: Sergei M. Abramov <abram@botik.ru>; <refal@botik.ru>; Anton Yu. Orlov <orlov@mccme.ru>
Sent: Thursday, December 07, 2000 3:34 PM
Subject: Re: Re: Re: Re: Re: Как следует компилироват ь ре фаль скую операциюотождествления
| Arkady Klimov wrote:
|
| > ----- Original Message -----
| > From: Andrey Slepuhin <pooh@msu.ru>
| > To: Arkady Klimov <klark@bagirra.net>
| > Cc: Sergei M. Abramov <abram@botik.ru>; <refal@botik.ru>; Anton Yu. Orlov <orlov@mccme.ru>
| > Sent: Wednesday, December 06, 2000 11:05 PM
| > Subject: Re: Re: Re: Re: Как следует компилировать ре фаль скую операциюотождествления
| >
| >
| > | Arkady Klimov wrote:
| > |
| > | > ----- Original Message -----
| > | > From: Andrey Slepuhin <pooh@msu.ru>
| > | > To: Arkady Klimov <klark@bagirra.net>
| > | > Cc: Sergei M. Abramov <abram@botik.ru>; <refal@botik.ru>; Anton Yu. Orlov <orlov@mccme.ru>
| > | > Sent: Wednesday, December 06, 2000 1:25 PM
| > | > Subject: Re: Re: Re: Как следует компилировать рефаль скую операциюотождествления
| > | >
| > | >
| > | > | Arkady Klimov wrote:
| > | > |
| > | > | > ----- Original Message -----
| > | > | > From: Andrey Slepuhin <pooh@msu.ru>
| > | > | > To: Arkady Klimov <klark@bagirra.net>
| > | > | > Cc: Sergei M. Abramov <abram@botik.ru>; <refal@botik.ru>; Anton Yu. Orlov <orlov@mccme.ru>
| > | > | > Sent: Wednesday, December 06, 2000 11:05 AM
| > | > | > Subject: Re: Re: Как следует компилировать рефальскую операцию отождествления
| > | > | >
| > | > | >
| > | > | > | Arkady Klimov wrote:
| > | > | > |
| > | > | > | > Сергей Михайлович, привет,
| > | > | > | > привет участникам дискуссии!
| > | > | > | > Спасибо за инициативу и интересные материалы.
| > | > | > | > Прошу прощения, что долго не включался, отвечать было недосуг, но я все
| > | > | > | > читал и более-менее разбирался. Все очень интересно. Для Р+ и вообще
| > | > | > | > отображение в массивное представление это то, что надо. Но в первом письме
| > | > | > | > ты писал, что эти методы будут также интересны для реализаторов Р-5 и т.п.,
| > | > | > | > то есть рефалов на списковом представлении. У меня есть в этом сомнения,
| > | > | > | > попробуй их развеять. Ты справедливо замечаешь, что сложность операций может быть
| > | > | > | > (и будет для списков) O(L). Но дальше ты писал, что алгоритм от этого не зависит.
| > | > | > | > Согласен, алгоритм не зависит, но сложность его зависит и возможно радикально.
| > | > | > | > Рассмотрим пример такого образца (из функции доступа к копилке):
| > | > | > | >
| > | > | > | > (e.name) (e.1 (e.name '=' e.value) e2)
| > | > | > | >
| > | > | > | > При существующей реализации его сложность - это объем символов из содержимого
| > | > | > | > правого списка, которые надо просмотреть при поиске. Когда сравнение неудачное,
| > | > | > | > это обычно 1-2 символа на одно имя. То есть время будет грубо пропорционально
| > | > | > | > количеству имен. Если же перед сравнением мы будет сначала вычислять длину,
| > | > | > | > тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
| > | > | > | > длине имени.
| > | > | > |
| > | > | > | С моей точки зрения правильная списковая реализация для рефал-выражений
| > | > | > | должна отслеживать их длину при конкатенациях и отщеплениях - это
| > | > | > | не вносит никакого оверхеда. Также могут существуют другие полезные
| > | > | > | инварианты, следить за которыми не мешало бы. Так, в новом рантайме
| > | > | > | рефала+ реализован флаг, указывающий, что выражение является "flat",
| > | > | > | т.е. не содержит скобочных термов.
| > | > | >
| > | > | > Что значит "отслеживать", "следить"? Хранить (длину содержимого)
| > | > | > внутри всех термов? В принципе, это, наверно, возможно. Правда,
| > | > | > по всей видимости, тогда придется смириться с таким минусом, как то,
| > | > | > что в следующей функции
| > | > | >
| > | > | > Dela
| > | > | >
| > | > | > 'a' e.1 = <Dela e.1>;
| > | > | > s.a e.1 = s.a <Dela e1>;
| > | > | > =;
| > | > | > }
| > | > | >
| > | > | > рекурсия уже не будет концевой. Не дорога ли цена?
| > | > |
| > | > | В первом случае будет нормальный хвостовой вызов и ничто этому
| > | > | не помешает, а во втором случае его не будет - куда конкатенацию девать?
| > | > | Хвостовой вызов там может быть, только если у нас семантика ленивая -
| > | > | сначала делаем конкатенацию с неготовым выражением, а потом вычисляем выражение.
| > | > |
| > | > Да, точнее, если реализация конкатенации у нас ленивая
| > | > (на семантику-то языка это не влияет),
| > | > а еще точнее - нестрогая (то есть выполняется раньше своих аргументов).
| > | > Именно такая сейчас в рефалах 5 и 6. Поэтому не будет большой проблемой
| > | > запустить указанную функцию над последовательностью из 1000000 символов.
| > |
| > | Ммм... Конкатенация-то может быть нестрогой, а вот как наччет хвостового
| > | вызова дальше? Хвостовой вызов предполагает, что мы полностью освобождаемся
| > | от контекста _вызывающей_ функции. Однако нам в итоге нужно в качестве
| > | результата вернуть результат конкатенации и _вызываемая_ функция ничего
| > | про него знать не должна, поскольку он не находится в рамках ее контекста.
| > | Если в рефалах 5 и 6 такое реализовано, то интересно, как при этом
| > | удалось обойтись без всяких нечестных хаков?
| >
| > Никаких "нечестных хаков". Это прямое следствие реализаци рефала на двусторонних списках.
| > Такая техника применялась в реализациях рефала с начала 70-х годов, если не раньше
| > (до Рефала Плюс). Каждый элемент имеет ссылку на предыдущий и на следующий элементы.
| > Каждая функция просто вставляет свой результат туда, где перед этим находился ее вызов,
| > на его место. При этом вызов - это один (так в шестом, в некоторых реализациях - больше)
| > элемент двустороннего списка, результат может состоять из нескольких элементов
| > или вообще не содержать ни одного (пусто). В последнем случае элементы,
| > окружающие вызов просто сшиваются друг с другом. Исходный вызов после вставки результата
| > (возможно, содержащего еще не вычисленные вызовы других функций) бросается в корзину.
|
| Ага, старая добрая конкретизация, которую я хорошо помню еше по рефалу-2.
| Все это замечательно с одной маленькой оговоркой: это честно работает
| только в интерпретирующих системах. В случае же компиляции в языки
| более низкого уровня или в машинный код такой фокус не пройдет.
Да, Андрей, тут Вы правы. Только, пожалуй, с одним "но": если речь идет о компиляции
в машинный код для списковой реализации, то скорее всего имеется в виду компиляция
в формате встроенных функций для интерпретирующей реализации - а это означает, что
и скомпилированные функции и нескомпилированные должны уметь работать совместно,
передавая друг другу данные - и данные одинаково устроенные. И тут мы возвращаемся
к тому с чего начали - практической невозможности организовать вычисление и хранение
длин списков с приемлемой для режима интерпретации сложностью. Короче, я бы
призывал не мудрствовать по поводу "единой для всех" схемы компиляции, а просто вести
ее разработку с прицелом на векторное представление, не оглядываясь на списки.
Аркадий.
| Андрей(С)
|
| --
| A right thing should be simple (tm)
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD