Александр, а где взяли статью про AMBIT. У меня она была, но было давно, сейчас уже нет. Через сеть - это старый журнал Communucations of ACM. Про статистику - десятки секунд это мало, надо, чтобы программа минуты выполнялась. Наши программы, на которых делались замеры, - это компиляторы с языков высокого уровня - несколько тысяч рефал-предложений и разные программы средней длины. Вот таблица. По отождествлению похожие с вашими результаты, но основное время тратится на жесткие элементы. А боялись все в то время открытых переменных, т.е. удлинений.
 
Вектора и таблицы вы ввели как объекты, которые можно породить машинной операцией, а в рефале они выглядят как один символ-ссылка на этот объект. Я просто новой терминологии не знаю, сказал, как есть.
Обработка графов - это графовые базы данных, т.е. базы данных с неоднородной информацией. В компьютерах часто используется их представление разреженными матрицами. Сейчас даже проект идет DARPA HIVE - создание специализированного микропроцессора для работы с такими базами данных. Графы + функциональные средства с глубоким динамическим распараллеливанием - очень перспективно и важно по оборонной тематике.
Л.Эйсымонт
Л
 
04.02.2018, 18:00, "Александр Коновалов" <a.v.konovalo...@mail.ru>:

Леонид!

«Кстати, мы в семидесятых-восьмидесятых собирали статистику, куда уходит время при выполнении рефал-программ. То, что вы обсуждаете, к реальности не имеет отношения. На больших программах отождествление не очень много времени занимало, это вопреки сложившемуся еще тогда мифу, а вот накладные расходы на вызовы функций и выполнение машинных операций занимали много времени.»

Презентацию я ещё посмотрю внимательнее (помню, что там что-то было), то письмо требует обстоятельного ответа с моей стороны.

В своей реализации я тоже делаю замеры производительности, но не по отдельным командам, а более крупными категориями. Типичный запуск самоприменения моего компилятора выдаёт статистику такого рода:

Total program time: 15.078 seconds (100.0 %).
(Total refal time): 12.812 seconds (85.0 %).
Linear pattern time: 6.827 seconds (45.3 %).
Linear result time: 4.348 seconds (28.8 %).
Native time: 1.329 seconds (8.8 %).
t- and e-var copy time: 0.904 seconds (6.0 %).
Runtime time overhead: 0.765 seconds (5.1 %).
Open e-loop time (clear): 0.670 seconds (4.4 %).
Context copy time: 0.172 seconds (1.1 %).
Repeated e-var match time (inside e-loops): 0.063 seconds (0.4 %).
Step count 14908900
Memory used 383417 nodes, 383417 * 16 = 6134672 bytes
Identifiers allocated: 789

На «машинные операции» (у меня они называются «нативные функции») уходит 8,8 %, на выполнение кода на Рефале — 85 %. Остальные 5,1 % — это некий оверхед на рантайм, который не помню, откуда берётся. По всей видимости, это аналог вышеупомянутых накладных расходов на вызовы функций. Под линейным временем здесь подразумевается время, зависящее от синтаксиса программы и не зависящее от входных данных: без сравнения повторных переменных, удлинения открытых, копирования переменных (у меня же списковая реализация). Так вот. 45,3 % времени уходит на линейное сопоставление с образцом, 28,8 % — линейное время построения результата. Если включить оптимизации — цифры будут другими, мне лень сейчас их анализировать.

«Еще мне давно нравится возможность отождествления не от левой-правой скобки конктеризации внутрь, а от некоторого указателя влево и вправо, это как в американском языке AMBIT, похожем на Рефал.»

Сегодня начал читать про AMBIT, тоже заметил это любопытное отличие от Рефала.

«При такой возможности можно было бы и с графами удобно работать, что они и сделали. Вот это принципиально.»

Про работу с графами я ещё не читал.

«Еще посредством машинных операций мы в стиле макроцифр ввели вектора и хеш-таблицы в Рефал…»

Вектора и хеш-таблицы чисто функциональные или мутабельные? Если мутабельные, то такие есть и в Рефале-6, и в Рефале Плюс, и мне в свою реализацию их добавить несложно.

«…еще по пути к параллельному рефалу ввели машинные операции типа возможностей MPI.»

Про MPI не знаю, не программировал с ним. Надо будет посмотреть.

Спасибо,
Александр Коновалов

 

From: Eisymont Leonid [mailto:verger...@yandex.ru]
Sent: Sunday, February 4, 2018 2:35 PM
To: refal@botik.ru
Subject: Re:
Рефал умер

 

Да уж ладно, интересно наблюдать. Кстати, мы в семидесятых-восьмидесятых собирали статистику, куда уходит время при выполнении рефал-программ. То, что вы обсуждаете, к реальности не имеет отношения. На больших программах отождествление не очень много времени занимало, это вопреки сложившемуся еще тогда мифу, а вот накладные расходы на вызовы функций и выполнение машинных операций занимали много времени. По-моему, в презентации с Дивноморской конференции эти цифры приведены. Еще мне давно нравится возможность отождествления не от левой-правой скобки конктеризации внутрь, а от некоторого указателя влево и вправо, это как в американском языке AMBIT, похожем на Рефал. Кстати, AMBIT возник в серьезном месте - лаборатории AFRL, это центральная исследовательская лаборатория ВВС США. При такой возможности можно было бы и с графами удобно работать, что они и сделали. Вот это принципиально. По сегодняшним тенденциям в ИТ актуально. Еще посредством машинных операций мы в стиле макроцифр ввели вектора и хеш-таблицы в Рефал, еще по пути к параллельному рефалу ввели машинные операции типа возможностей MPI. Вот это все было по делу.

Л.Эйсымонт

 

04.02.2018, 14:01, "Александр Коновалов" <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: Eisymon
t 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

 

Ответить