Александр!

Мы столкнулись в одной их таких реализаций (Finger Trees, кажется) при
решении (вернее, при анализе результатов) одного из ICFPC (ICFP Programming
Contest). Как оказалось, что в той задаче такие реализации показывают
существенно более  высокую скорость, чем обычные (на порядки большую).Так
что есть реализации и задачи, в которых это k достаточно мало, чтобы это
было всё осмысленно. Но дальше анализа у нас дело не пошло :(.

Юра

2018-02-04 14:01 GMT+03:00 Александр Коновалов <a.v.konovalo...@mail.ru>:

> Добрый день, Юрий!
>
> У меня нет опыта программирования на Рефалах, имеющих представление,
> отличное от классического спискового. На сколько я знаю, Рефал-6 (как и
> FLAC) использует «компромиссное» представление, но я на нём
> программировал мало. На Рефале Плюс с векторным представлением я вообще
> ни разу не программировал.
>
> Был опыт реализации старой версии Простого Рефала на векторно-списковом
> представлении (предложенном Скоробогатовым [неопубликовано]) — при
> достаточном объёме кучи и доводке исходного текста (минимизация
> конкатенаций) обгонял списковую реализацию.
>
> А на счёт новых представлений — многообещающа структура данных rope, O(log
> N) на конкатенацию, индексирование и выборку подстроки. Плюс ещё есть
> деки с конкатенацией Окасаки — у них вообще амортизированный O(1) все
> операции: конкатенация собственно, приписывание терма к началу/концу
> и отделение терма от начала/конца, притом чисто функциональная структура
> данных. Индексирование по произвольному номеру не поддерживается. Сам Крис
> Окасаки в своей книге («Чисто функциональные структуры данных») упоминает
> существование деков с конкатенацией с даже неамортизированным O(1), но я
> ту публикацию не искал.
>
> Но проблема всех этих представлений в буковке «O». O(f(N)) ≈ k·f(N), а «k»
> каково? Надо исследовать…
>
> С уважением,
> Александр Коновалов
>
> P.S. Что-то мы Леониду спамим, автоматически проставляя его в копию.
>
>
>
> *From:* Yuri Klimov [mailto:y...@klimov.net]
> *Sent:* Sunday, February 4, 2018 1:43 PM
> *To:* refal@botik.ru
> *Cc:* Eisymont Leonid <verger...@yandex.ru>
> *Subject:* Re: Рефал умер
>
>
>
> Добрый день, Александр!
>
>
>
> > Ну, и, конечно, представление рефал-выражений обязано быть массивным.
> Обязано быть с дорогущей конкатенацией? В языке, где конкатенация — один
> из двух конструкторов?
>
> ...
>
> ИМХО, дорогое копирование переменных портит стиль программирования гораздо
> меньше.
>
>
>
> Зато есть возможность дешевого доступа к любому элементу выражения (хоть
> слева, хоть справа) и взятия подвыражений. Так что тут вопрос что кому
> нравится и какие цели у реализации. И, наверное, с больших программах
> операций прочитать=разобрать больше, чем записать=собрать ;). Поэтому
> чтение (взятие подвыражений, копирование) должно быть дешевле, чем запись
> (конструирование). Хотя, опять, кому что больше нравится.
>
>
>
> Давно есть мысли сделать реализацию на интересных структурах данных, в
> которых и операция конкатенации, и операция взятия подвыражения имели бы
> логарифмическую сложность. Было интересно посмотреть, как это отразиться на
> Рефале.
>
>
>
> С уважением,
>
>     Юрий Климов
>
>
>
>
>
> 2018-02-04 11:06 GMT+03:00 Александр Коновалов <a.v.konovalo...@mail.ru>:
>
> Доброе утро, Сергей!
>
> На сколько я знаю, Рефал Плюс имеет front-end’ы для Рефала-5 и Рефала-6.
> На сколько они совместимы с оригинальными реализациями?
>
> > Ну, и, конечно, представление рефал-выражений обязано быть массивным.
>
> Обязано быть с дорогущей конкатенацией? В языке, где конкатенация — один
> из двух конструкторов?
>
> Дорогая конкатенация пагубно влияет на стиль программирования. Я читал
> архив рассылки (старый, которого сейчас нет) за, по-моему, начало нулевых.
> Там кто-то сравнивал программу Fab на Рефале-5 и Рефале Плюс. Первая
> программа гораздо компактнее и элегантнее, чем на втором.
>
> ИМХО, дорогое копирование переменных портит стиль программирования гораздо
> меньше.
>
> (Знаю, что эта тема уже обсуждалась много лет назад, но архив рассылки
> поглотила пучина времени.)
>
> С уважением,
> Александр Коновалов
>
> -----Original Message-----
> From: Sergei M. Abramov [mailto:ab...@botik.ru]
> Sent: Sunday, February 4, 2018 9:45 AM
> To: Eisymont Leonid <verger...@yandex.ru>; refal@botik.ru
> Subject: Re: Рефал умер
>
> День добрый, всем!
>
> Вот за что я и люблю Рефал Плюс.  И это объесняет мое молчание.  Даже
> когда обсуждается геерация Си кода по рефал-программе (ведь там такие
> статьи написаны и доступны про правильную компиляцию отождествления).
>
> Ни, и, конечно, представление рефал-выражений обязано быть массивным.
>
> Всего доброго,
>
> Сергей Абрамов
>
> Вы писали 04 февраля 2018 г., 01:46:37:
>
> > Не согласен.Рефал хорош был своей простотой, технологичностью. Это и
> > старшее поколение специалистов, наших учителей, ценило в этом языке
> > прежде всего. Что было сделано Сергеем и Андреем в Рефале-2 - это,
> > наверное, оптимальный уровень его усложнения для практического
> > применения.Мы на протяжении десятилетий на этом диалекте языка
> > создавали очень сложные компиляторы языков высокого уровня для
> > необычных новых машин советского времени. Причем именно эта технология
> > была решающей, когда требовалось быстро создать компилятор для новой
> > машины. Никто не брался, а мы в Институте Прикладной Математики
> > им.М.В.Келдыша АН СССР вытягивали один проект за другим. Примеры с
> > Бураном и Булатами - наиболее яркие, а ведь были еще и язык НОРМА,
> > ПС-3000, ЕС-1195, это последний суперкомпьютер Советского Союза.
> > Далее, уже в середине первого десятилетия двухтысячных годов, первые
> > исследования по НИР "Беркут", это мультитредовый суперкомпьютер Ангара
> > стратегического назначения, были очень быстро проведены с
> > использованием именно Рефала.Мы применяли и применяем реализацию
> > Рефала-2 на односвязных списках с кольцевыим цепочками, которую с
> > Колей Мансуровым сделали в свое время также в ИПМ. Эта реализация
> > жива, исходники есть, имеется очень богатая библиотека машинных
> > операция с продуманными нестандартными возможностями, просто я не стал
> > вмешиваться в переписку в силу разных причин. Она у нас в горячем
> > резерве, когда потребуется будем использовать в своих работах.
> > Время-то приближается лихое...будет невероятно много разработок
> > специализированных высокопроизводительных устройств.Новые версии
> > Рефала - хорошее дело. Только я не знаю, был ли у них такой объем
> > практического применения в сложных проектах, как у нас. Тем не менее,
> > с уважением отношусь к этим работам, но уж очень много в новых версиях
> > текста и сложностей, поэтому мы это использовать вряд ли будем в своих
> > проектах. А вот параллельная версия реализации обычного Рефала явно не
> > помешала бы.В далеких семидесятых Рефал мои руководители и я
> > рассматривали не только как технологичный язык для задач обработки
> > символьной информации, но и как прототип внутреннего машинного языка
> > символьного процессора с отличной от фон-Неймановской архитектурой. С
> > этой точки зрения компилировать Рефал в Си с невероятными
> > оптимизациями - это "бег на месте или даже ход назад", в угоду старых
> > архитектур, хотя на сегодняшний день, м.б. и имеет практический мысл.
> > Да и этот Си слишком сильный конкурент на поляне существующих
> > архитектур, он, как сорняк, все забивает, не дает новым языкам
> > подняться в полный рост, причем дело не только в новых версиях Рефала.
> > Даже PGAS языки не пошли. Выбиться сейчас с новым языком без
> > фантастических преимуществ практически невозможно. Кстати, одна из
> > причин, почему мы изначально брались с Рефалом за самые "гиблые" с
> > точки зрения возможной выполнимости проекты - стремление доказать
> > привлекательность этого языка. Ну а потом, приобрели соответствующую
> > известность из-за этого и популярность "пожарной команды". Затянуло,
> > особенно если "просили"
> > из ЦК КПСС или уважаемых ведомств. Доказывали несколько десятилетий,
> > результат - какой есть. Если честно, то не очень, ведь техника
> > приходит и уходит, заслуги забываются, а жизни своей немного жаль.
> > Можно было бы и более фундаментальными делами заняться, диссертации
> > писать по этому поводу. В итоге цель наша с продвижением реализаций
> > этого функционального языка с глубоким распараллеливанием, вплоть до
> > применения клеточных автоматов, как это видели в семидесятых, пока не
> > достигнута.С другой стороны, слишком большие перемены ожидаются в
> > архитектуре вычислительной техники в предстоящие десять лет в связи с
> > достигнутым пределом развития КМОП-технологий и приближением
> > пост-Муровской элементной базы, а там - своя схемотехника, это скорее
> > всего, многие аналитики предсказывают. Там и место новым языкам, в том
> > числе и Рефалу, хотя бы упрощенной версии, об этом и думали много лет
> > назад.Будущее загадочно, не всем его дано увидеть, да и не так быстро
> > оно наступает. Вот и я не претендую, м.б. и ошибаюсь, но мы об этом
> > мечтали в свое время. Дано ли будет это увидеть или разочароваться? На
> > всякий случай, не стоит отчаиваться и делать поспешные выводы,
> > перечеркивать достижения и опрежавшие время работы предшественников,
> > причем целых двух - трех поколений, да и хоронить само это детище
> > Валентина Федоровича. Таким людям, как он, дано увидеть сквозь годы, я
> > в это верю, вижу признаки его правоты в современных проявлениях и
> > грядущих изменениях.Л.Эйсымонт 03.02.2018, 23:19, "Александр
> > Коновалов"
> > <a.v.konovalo...@mail.ru>:Добрый вечер всем!
>
> > Судя по тому, что на это письмо никакой реакции не воспоследовало,
> > экосистема Рефала уже никому не интересна.
>
> > А ведь я предложил маленький шаг по борьбе с «вавилонской башней
> > Рефала» — проблемой наличия нескольких несовместимых диалектов. Если
> > что, темой, обозначенной в предыдущем письме, я никого не призываю
> > заняться — я сам могу за это взяться вместе со своими студентами.
>
> > Александр Коновалов
>
> >
>
> > From: Александр Коновалов [mailto:a.v.konovalo...@mail.ru]
> > Sent: Saturday, January 27, 2018 3:22 PM
> > To: refal@botik.ru
> > Subject: Общее подмножество Рефала-5 и Рефала-6
>
> >
>
> > Добрый день всем!
>
> > В одном из своих предыдущих писем я затронул вопрос общего
> > подмножества Рефала-5 и Рефала-6. Сейчас раскрою этот вопрос подробнее.
>
> > На сколько мне известно, Рефал-6 изначально писался как альтернативная
> > реализация Рефала-5 Турчина, и, по-видимому, был совместим с ним на
> > уровне исходного кода. Позже развитие обоих диалектов разошлось. В
> > августе 2000-го Рефал-5 обзавёлся новым
> > синтаксисом: идентификаторы, в частности, стали чувствительными к
> > регистру, появились escape-последовательности, были запрещены
> > переменные без точки, а также изменился формат функции Type. Рефал-6
> > обзавёлся синтаксисом и семантикой действий и неуспехов из Рефала Плюс
> > много раньше 2000-го года, тут я уже не в курсе. И в итоге сейчас
> > практически любая программа для Рефала-5 не будет компилироваться
> > Рефалом-6 и наоборот.
>
> > Однако, можно выделить подмножество программ, которые будут успешно
> > компилироваться и одинаково выполняться актуальными (доступными на
> > 2018-01-27 в интернете) реализациями Рефала-5 (PZ Oct 29 2004) и
> > Рефала-6 («Обновлено 08.02.2001»). Если программа на Рефале-5
> > удовлетворяет следующим требованиям:
>
> > ·         После каждой «}» обязательно ставится «;».
>
> > ·         Имена функций и идентификаторов (без кавычек) всегда
> начинаются с большой буквы.
>
> > ·         Используются только escape-последовательности \n, \r, \t,
> > \', \", \\, \xHH (только в 'литерах' и "составных символах").
>
> > ·         Не используются никакие встроенные функции кроме коротких
> > синонимов для арифметики: <+…>, <−…>, <*…>, </…>, <%…>, при этом после +
> и − обязателен пробел.
>
> > ·         Результаты арифметических вычислений не должны быть
> > отрицательными и не должны превышать 2³²−1.
>
> > ·         Стартовая функция всегда пишется как GO.
>
> > То в этом случае программа может быть успешно откомпилирована и
> > выполнена Рефалом-6 ключами по умолчанию (компилируется при помощи rfc
> > program.ref, выполняется при помощи ri i+program+*GO).
>
> > Поясню некоторые пункты списка.
>
> > Синтаксис функций Рефала-5 имеет вид «[$ENTRY] Имя Блок», синтаксис
> > функций Рефала-6 — «[$ENTRY] Имя ОбразцовоеОкончание», причём
> > «ОбразцовоеОкончание» должно завершаться точкой с запятой. Однако,
> > синтаксис Рефала-5 допускает на верхнем уровне грамматики использовать
> > незначащие точки с запятой.
>
> > Рефал-5 допускает имена, начинающиеся с маленькой буквы, Рефал-6 не
> > допускает. Поэтому запись «eq» первый воспримет как имя, второй — как
> переменную.
>
> > Рефал-5 также допускает escape-последовательности «\<», «\>», «\(»,
> > «\)» которые обозначают те же символы, что и без «\». При этом текущая
> > реализация refc допускает запись escape-последовательностей вне
> > кавычек — это альтернативная запись для литер: \n эквивалентно '\n'.
> > Это нигде не документированная возможность, но она есть (и
> > поддерживается Рефалом-5λ, кстати). Другие escape-последовательности,
> > кроме вышеперечисленных и недокументированных, Рефал-5 не
> > поддерживает.
>
> > Встроенные функции текущей реализации Рефала-5 начинаются с прописной
> > буквы и пишутся строчными: Open, Add и т.д. Встроенные функции
> > Рефала-6 пишутся целиком прописными буквами: OPEN, ADD.
> > Соответственно, их множество пересекается только на коротких
> > синонимах. Нюанс со знаками «+» и «−» объясняется тем, что слитная
> > запись знака с целым числом описывает отрицательное число, т.е. <−10
> > 5> в Рефале-5 будет проинтерпретировано вычитание из десяти пяти, в
> > Рефале-6 как вызов числа «минус десять» в роли функции с аргументом
> > «пять». Можно переопределить функцию APPLY_OBJECT, чтобы и это
> > работало, но я пока не касаюсь переопределения библиотеки.
>
> > Длинная арифметика в Рефале-5 описывается цепочками макроцифр, причём
> > признак отрицательного числа обозначается литерой '−'. В
> > Рефале-6 сами символы-числа являются числами произвольной разрядности
> > со знаком. Поэтому отрицательные или слишком большие результаты
> > арифметических операций будут выглядеть по-разному.
>
> > Последний пункт про GO — мне не удалось запустить программу (с ключами
> > запуска по умолчанию), стартовой функцией которой является функция Go.
>
> > Но, у Рефала-6 есть слой совместимости с Рефалом-5, который позволяет
> > расширить общее подмножество. Именно расширить, поскольку слой устарел
> > + синтаксические различия. Во-первых, это стартовый модуль i5.rex,
> > содержащий определения некоторых встроенных Рефала-5.
> > Во-вторых, чтобы можно было воспользоваться r5.rex без его
> > модификации, компилировать программу следует с ключом /U — все
> > незакавыченные слова в upper case. В этом случае программа на
> > Рефале-5 должна ограничиваться следующими требованиями:
>
> > ·         Опять после «}» обязательно должна быть «;».
>
> > ·         Имена функций и идентификаторов пишутся с большой буквы.
> > Нельзя в программе использовать функции и идентификаторы, которые
> > различаются только регистром символов. Не следует предполагать, что AbCd
> == "AbCd".
>
> > ·         Escape-последовательности см. выше.
>
> > ·         Можно использовать встроенные функции с номерами от 1 «Mu»
> > до 35 «Sysfun». Номера функций можно посмотреть в выводе функции
> > «ListOfBuiltin» (но она имеет номер 67). Короткими синонимами для
> > арифметики пользоваться нельзя.
>
> > ·         Не следует делать никаких предположений о размере
> > макроцифры. В Рефале-5 отрицательные числа записываются как '−' s.1
> > s.2 s.3…, положительные — как '+' s.1 s.2 s.3… или s.1 s.2 s.3…; в
> > Рефале-6 — '−' s.One, '+' s.One или s.One соответственно.
>
> > ·         Запрещено пользоваться функцией Type, ибо форматы
> > возвращаемого значения в обоих реализациях различны.
>
> > ·         Функция Step может показывать разные значения на обоих
> > реализациях. В Рефале-6 библиотечные функции написаны на Рефале и
> > поэтому они могут выполняться за несколько шагов рефал-машины, в отличие
> от Рефала-5.
>
> > ·         Стартовую функцию можно называть Go или GO.
>
> > Чтобы ещё больше расширить подмножество, можно в первую очередь
> > обновить библиотеку совместимости — добавить синонимы функций с
> > именами в правильном регистре, обновить функцию Type и (что потребует
> > расширения интерпретатора) добавить новые встроенные функции. С точки
> > зрения синтаксиса можно поступить по-разному: от разрешения не писать
> > «;», когда тело функции задаётся одним блоком (это не должно привести
> > к противоречиям в грамматике) до разработки отдельного front-end’а для
> > синтаксиса Рефала-5. Но даже разрешение отсутствия точек с запятой на
> > верхнем уровне вместе с модификацией библиотеки сделает Рефал-6 точным
> > надмножеством Рефала-5.
>
> > С уважением,
> > Александр Коновалов
>
>
>
>
> --
> С уважением,
> Абрамов С.М.                          mailto:ab...@botik.ru
>
>
>

Ответить