Subject: Re: Как следует компилировать рефальску операцию отождествлени
From: Arkady Klimov (klark@bagirra.net)
Date: Tue Dec 05 2000 - 12:12:46 MSK
Сергей Михайлович, привет,
привет участникам дискуссии!
Спасибо за инициативу и интересные материалы.
Прошу прощения, что долго не включался, отвечать было недосуг, но я все
читал и более-менее разбирался. Все очень интересно. Для Р+ и вообще
отображение в массивное представление это то, что надо. Но в первом письме
ты писал, что эти методы будут также интересны для реализаторов Р-5 и т.п.,
то есть рефалов на списковом представлении. У меня есть в этом сомнения,
попробуй их развеять. Ты справедливо замечаешь, что сложность операций может быть
(и будет для списков) O(L). Но дальше ты писал, что алгоритм от этого не зависит.
Согласен, алгоритм не зависит, но сложность его зависит и возможно радикально.
Рассмотрим пример такого образца (из функции доступа к копилке):
(e.name) (e.1 (e.name '=' e.value) e2)
При существующей реализации его сложность - это объем символов из содержимого
правого списка, которые надо просмотреть при поиске. Когда сравнение неудачное,
это обычно 1-2 символа на одно имя. То есть время будет грубо пропорционально
количеству имен. Если же перед сравнением мы будет сначала вычислять длину,
тратя O(L), то время поиска резко увеличится в разы - пропорционально средней
длине имени.
Но, повторяю, мое сомнение касается только применимости этих методов к списковой
реализации. А для массивной все в основном замечательно. Есть только опасение в том,
что значительная часть кода в компиляторе и интелекта при его создании будут потрачены
как бы зря, поскольку в практических программах не будут востребованы - примерно так,
как это уже когда-то было с Теоретическими Основами Синтаксического Отождествления,
реализованными в т.н. Большом Компиляторе. Но это я так написал, чтобы иметь в виду,
на самом деле надо продолжать в том же духе, и смотреть, что получается. А там видно
будет. Потом интересно будет посмотреть, нельзя ли сделать заметное упрощение
в арсенале приемов, при котором типичные случаи практически не пострадали бы.
Успехов в данном начинании!
Аркадий.
----- Original Message -----
From: Sergei M. Abramov <abram@botik.ru>
To: <refal@botik.ru>; Andrey Slepuhin <pooh@msu.ru>; Anton Yu. Orlov <orlov@mccme.ru>
Sent: Monday, November 27, 2000 5:47 PM
Subject: Re: Как следует компилировать рефальскую операцию отождествления
| День добрый, всем!
|
| Неделю назад прошло устное обсуждение (Абрамов, Слепухин, Орлов) ранее
| опубликованного pm.txt "Как следует компилировать рефальскую операцию
| отождествления".
|
| Антон и Андрей высказали несколько важных идей, в дискуссии всеми нами они были
| подшлифованы и после дальнейшего автономного обдумывания ...
|
| (***
| некие вещи высказанные мною на месте были ошибочны, вроде мысли о том, что
| "ограничение сверху на длину открытой переменной" есть монотоный объект--
| все оказалось проще!
| ***).
|
| ... я излагаю здесь резюме того обсуждения: pm1.txt.
|
| Файл pm1.txt есть:
| =1= краткий взгляд на pm.txt (для полного понимания стоит его иметь)
| + =2= новые идеи (отмечены как [New!]).
|
| Удачи,
|
| Сергей
|
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD