Re: Синтаксический анализ в Рефале

[Eisymont Leonid verger-lk_AT_yandex . ru]

Быстродействие мы в итоге на программах оценивали, не только по отдельным операторам.

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

Про триады - нам надо было ускоряться. Триады - это специальная запись деревьев разбора в компиляторах, еще некоторые используют тетрады. Мы это и реализовали.

По параллельной реализации в НИЦЭВТ-е у меня Александр Фролов занимался, сейчас он там начальник отдела. У него диплом был в МИФИ по этой теме. Работающую версию он сделал и аккуратно исследовал. Потом жизнь закрутила, он стал заниматься у меня темой СКСН Ангара. А я, все-таки, еще надеюсь эту тему реанимировать, даже с использованием ускорителей на клеточных автоматах.

 

10.02.2019, 15:34, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Добрый день, Леонид!

«Александр, односвязная память позволила и быстродействие поднять, мы это в своё время исследовали.»

Просто в препринте, который я когда-то читал, было написано, что наоборот быстродействие снизилось. Поэтому и спросил.

«По памяти это также важно, особенно сейчас будет, поскольку адрес связи в слово сейчас уже маловато, нужен 64-х разрядный адрес…»

Я думал, что на 64-разрядных машинах слово и есть 8 байт.

«Мы в реализации Рефала-2 плотные структуры данных давно ввели.»

Значит, и мне нужно вводить плотные структуры данных. Либо использовать массивное представление объектных выражений (как в Рефале Плюс или Рефале-Java), которое само по себе плотное.

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

Не понял. Можно поподробнее?

«Последнее — параллелизм, что этим не занимаются — большое упущение.»

Когда-то занимался Скоробогатов, потом забросил. L

 

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

 

From: Eisymont Leonid verger-lk_AT_yandex.ru [mailto:refal@botik.ru]
Sent: Sunday, February 10, 2019 3:21 PM
To: refal@botik.ru
Subject: Re: Синтаксический анализ в Рефале

 

Александр, односвязная память позволила и быстродействие поднять, мы это в свое время исследовали. По памяти это также важно, особенно сейчас будет, поскольку адрес связи в слово сейчас уже маловато, нужен 64-х разрядный адрес, ведь в настоящих суперах оперативные памяти уже от десятков до сотен петабайт, а в американских перспективных суперах поставлена задача дойти до экзабайта. Это я про оперативную память говорю даже.

Мы в реализации Рефала-2 плотные структуры данных давно ввели. Начали с хеш-таблиц, это для компиляторов было нужно, потом вектора ввели и массивы. Более того, были вектора специализированные, их элементами были триады, это структуры для линейной записи деревьев разбора, мы такими векторами квазилинейные участки представляли.

Если говорить об изменениях Рефала, то они были очень деликатными. Основная проблема, с которой такими изменениями сражались, вынужденные накладные расходы выполнения простых действий, когда вычисление в функции незначительное.

Мы собирали статистику на реализациях рефала, на это много тратилось.

Но вот что мне давно хотелось вставить, это принципиально, так это то, что есть в AMBITe - отождествление относительно указателей, а не только относительно левой и правой скобки конкретизации внутрь. Варианты получались кривые, так это и не решил. А ведь заманчиво, это ход к обработке графовых структур. Сейчас это как никогда актуально.

Последнее - параллелизм, что этим не занимаются  - большое упущение. Моя любимая тема и высоко оценивалась моими научными руководителями в ИПМ, но они же меня много лет назад с большими извинениями от этой темы оторвали - нужны были практические приложения рефала при решении важных задач в государственных проектах. Другие не брались из-за сложности, а мы вытягивали. Ну, об этом я уже докладывал, по моим публикациям в сети это видно. Направление по параллельным реализациям безумно перспективное, надо тут молодых подключать, оно сильно с современными высокопроизводительными микропроцессорами пересекается (массово-мультитредовые архитектуры, мы этим немного стали опять заниматься, раньше занимались по линии СКСН Ангара) и играми в кибервойны.

Л.Эйсымонт

 

10.02.2019, 14:27, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Добрый день, Леонид!

«Условно её можно назвать Мансуровской, хотя я её с ним делал (руководил), но больше алгоритмы придумывал реализации языка сборки на односвязной памяти с кольцевыми цепочками.»

А в чём преимущество односвязных списков с кольцевыми цепочками кроме экономии памяти?

«Можно начать с простых компиляторов, у меня такие примеры есть. Какие-нибудь действия с полиномами. Потом графовые типа BFS, раскраски графа, BWС.

Потом действия над плотнозаполненными матрицами и разреженными матрицами. Злободневно — нейроалгоритмы.»

Всё, что после простых компиляторов, требует структуры данных с эффективным произвольным доступом (массивы, вектора). Ни в одной моей реализации Рефала векторов нет. И объектные выражения представлены простыми двусвязными списками. А ещё у меня нигде нет вещественных чисел, только целые.

Параллелизм я тоже пока не умею.

 

С уважением,
Александр Коновалов

 

From: Eisymont Leonid verger-lk_AT_yandex.ru [mailto:refal@botik.ru]
Sent: Friday, February 1, 2019 8:08 PM
To: refal@botik.ru
Subject: Re: Синтаксический анализ в Рефале

 

Конкретно на последнюю строчку пока мне наиболее интересно ответить - с чем сравнивать и на чем.

Полагаю, наиболее проверенная реализация - это которой мы пользовались, начиная с Бурана и потом для специализированных суперкомпьютеров спецслужб, потом в проектах суперкомпьютеров с новой архитектурой (СКСН Ангара). Условно ее можно назвать Мансуровской, хотя я ее с ним делал (руководил), но больше алгоритмы придумывал реализации языка сборки на односвязной памяти с кольцевыми цепочками. Эта реализация обросла в итоге таким количеством машинных операций. Коле надо отдать должное, сделал хорошо, да и другие руку приложили по библиотекам.

По поводу тестов очень злободневно и перспективно. Тут можно ориентироваться на разные области, не только на обработку символьной информации, но и на работу с графами, обработку числовой информации (особенно важно - разреженные матрицы).

Числовая обработка может показаться странным направлением тестирования, но я интуитивно полагаю, что функциональный язык типа Рефала вообще ляжет в будущем в основу процессоров с по-настоящему не Фон-Неймановской архитектурой. Мы это в ИПМ еще в конце семидесятых - начале восьмидесятых обсуждали, но тогда было не время. Собственно говоря, такую мысль и Бэкус высказывал по поводу функционального языка в своей знаменитой Тьюринговской лекции "Может ли программирование освободиться от фон-Неймановского стиля".

Можно начать с простых компиляторов, у меня такие примеры есть. Какие-нибудь действия с полиномами. Потом графовые типа BFS, раскраски графа, BWС.

Потом действия над плотнозаполненными матрицами и разреженными матрицами. Злободневно - нейроалгоритмы.

Сравнивать не только версии Рефалов, но и с реализациями на СИ, чтобы оценить отставание и понять, можно ли его компенсировать и далее оторваться за счет аппаратных реализаций и распараллеливания. Распараллеливание - главное.  

Для студентов интересные задачки, сразу результат виден. Тестирование обычно объединяет и активизирует совместные работы, вовлекает молодежь, а этого сейчас страшно не хватает при решении важных для государства задач.

Л.Эйсымонт

 

01.02.2019, 19:30, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Леонид!

Сначала скажу за себя. Свой Рефал-5λ я пока не рекомендую для боевого применения. Реализация применялась мной (поскольку написана на себе) и десятком студентов при выполнении простых домашек. И они находили ошибки.

По быстродействию она медленнее Рефала-5 (refc/refgo) примерно в два раза. Я заметил это, когда компилировал Рефал-05 собой, Рефалом-5 и Рефалом-5λ. Рефал-05 чуть-чуть быстрее, чем Рефал-5.

Пошаговый отладчик есть чисто номинально. Трассировщик, распечатывающий поле зрения на каждом шаге, глючит и я не добрался его отладить как следует. Поэтому остаётся отладка Prout’ами.

Динамических ящиков нет, и пока не планируются.

Преимущество реализации: удобно добавлять машинные операции (у меня они называются нативными функциями).

 

Реализация Рефала-5 достаточно стабильная (хотя Андрей Немытых прячет более свежую версию с исправлением некоторых ошибок), но она интерпретатор. Поэтому добавлять машинные операции неудобно — нужно лезть в исходники интерпретатора.

 

А с быстродействием какого Рефала-2 нужно сравнивать? И на каких тестовых примерах?

 

С уважением,
Александр Коновалов

 

From: Eisymont Leonid verger-lk_AT_yandex.ru <refal@botik.ru>
Sent: Friday, February 1, 2019 5:50 PM
To: refal@botik.ru
Subject: Re: Синтаксический анализ в Рефале

 

Спасибо. Для СБИС мы моделировали на уровне временных диаграмм выполнения команд, это уже проходили много раз, последнее - в НИР Вектор (заказчик - Квант) и НИР Беркут(заказчик Министерство)  в НИЦЭВТ-е.

Нормально работает. Самое главное, что это не кропотливое программирование на Си, быстрота создания и изменения в процессе исследования.

Аркадий, ты не сказал про библиотеки машинных операций в новых реализациях. Распараллеливания, как понимаю нет?

Еще меня давно занимает вопрос, ну а по скорости работы как соотносится с Рефалом-2 на одних и тех же платформах?

Ну и конечно, насколько хорошо оттестировано, кто сопровождает реализацию.

Игорь Щенков активно работает, какие у него успехи?

Л.Эйсымонт

 

01.02.2019, 17:25, "Arkady Klimov arkady.klimov_AT_gmail.com" <refal@botik.ru>:

Да наверно можно пользоваться любым из упомянутых, хотя лично я, конечно же, привержен рефалу-6, как его соавтор в какой-то мере. Документацию (подробное описание входного языка с примерами) можно посмотреть на сайте refal.net:

http://refal.net/~arklimov/refal6/manual.htm

Там есть и дистрибутив, но если начинать пользоваться, то лучше, наверно, брать у меня.

К сожалению, все никак не дойдут руки на github выложить.

Готовый вариант есть для Windows-32, если нужен для других ОС, надо будет компилировать и собирать с исходников на С.

Любителям Java могу рекомендовать версию Refal-Java. Входной язык там практически такой же, добавлены межмодульные связи в стиле Java. Скорость выше в 2-3 раза. И "машинные операции" легко добавлять. Но есть проблемы: например, стек может переполниться.

И по большому счету им еще никто не пользовался.

А у варианта на С под виндами есть пока два полноценных пользователя: я и И.Щенков. Еще в прошлом году ошибки, обнаруженные Игорем, исправлял.

По применению к моделированию СБИС не понятно, что тут может быть - не логику же потактовую  на рефале крутить! Еще понимаю, если компилятор с языка специфического делать, да?

Аркадий

 

пт, 1 февр. 2019 г. в 16:32, Eisymont Leonid verger-lk_AT_yandex.ru <refal@botik.ru>:

Аркадий, интересно было бы посмотреть, чем сейчас реально можно пользоваться.

Есть ли опыт использования новых Рефалов в больших проектах типа тех, где использовался ранее Рефал-2. Я совершенно серьезно говорил о том, что вероятность применения Рефала в работах по созданию новых СБИС на этапах моделирования и отработки архитектуры или микроархитектуры , а также ПО достаточно высока. Я сейчас в Модуле и Кванте, возможны очень крупные совместные работы, вижу, что необходимость в этом назревает.

В общем, здравствуйте опять 70-80-е годы.

Л.Эйсымонт

PS - Рефал-2 у нас сохранился с очень богатой библиотекой, в нем даже доделали некоторые примитивы MPI через машинные операции, есть еще экспериментальная реализация Александра Фролова с динамическим распараллеливанием конкретизаций (это все НИЦЭВТ уже был начало 2000-х). На этой реализации мы хорошо "руку набили".

 

01.02.2019, 16:14, "Arkady Klimov arkady.klimov_AT_gmail.com" <refal@botik.ru>:

Интересно услышать, что практикующие (практиковавшие в прошлом) рефал-программисты считают сложным в новых версиях языка (5-6-плюс-7).

Вложенные блоки? Откаты? Условия?

Сам я считаю лишними только разные экзотический элементы вроде отсечений-заборов, отрицаний, $iter, двойного двоеточия. Откаты-блоки-условия считаю полезными.

Откатность явная или неявная? Можно спорить, это также зависит от семантики "=".

Форматы  функций? Сам не использую, оценить не могу. В рефале-6 их нет. Но для более эффективного интерфейса с С наверно полезны.

Анонимные функции не считаю полезными, на мой взгляд они даже вредны - толкают на плохой стиль (потакают экономить на придумывании имен и понятий, тогда как хорошие имена и понятия облегчают читабельность и дальнейшее сопровождение). Понимаю, что есть и другие мнения.

 

Александр правильно подметил, что в новых рефалах нет спецификаторов, которые были в рефале-2. Мне кажется, они тоже подталкивают на не очень хороший стиль, когда вместо отдельно описанного лексера, распознавание лексем разбросано по всему парсеру. В этом смысле интересен опыт и мнение Игоря Щенкова - кажется единственного пользователя, которые реально переходил с Рефала-2 на Рефал-6 с большим комплексом программ.

Раньше был существен вопрос об эффективности лексера - отсюда и спецификаторы. Теперь он столь остро не стоит. (А в случае большой нужды можно применить полусуперкомпиляцию и отображение в С).

 

Насчет простоты - рефал-6 тоже не громоздок. 

Интерпретирующая реализация - около 10 тыс. строк на С и компилятор - 1.5 тыс строк на рефале. 

В варианте Refal-Java: рантайм - 4.5 тыс. строк на Java, компилятор - 2.5 тыс строк на рефале.

 

С уважением,

Аркадий Климов.

 

чт, 31 янв. 2019 г. в 23:55, Eisymont Leonid verger-lk_AT_yandex.ru <refal@botik.ru>:

У меня в письме главным другое было...

 

31.01.2019, 22:00, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

«Балансировка скобок одновременно шла с лексическим анализом. Прохода два было.»

Поэтому я употребил слово «концептуально». Потому что можно проводить синтаксический анализ, не выделяя явно скобки. В Рефале-05 я так и сделал (ссылка в предыдущем письме).

На Рефале вообще скобки можно сильно по-разному обрабатывать. Особенно, в компиляторах Рефала.

Можно лексический анализ делать одновременно с синтаксическим — иметь функцию NextToken, которая возвращает очередной токен программы, и её вызывать в тот момент, когда требуется следующий токен. Можно вообще смешать лексический и синтаксический анализ — строить синтаксическое дерево сразу из потока символов.

«Последующие версии Рефала мне явно не нравятся, сложные.»

Упомянутый мной Рефал-05 семантически проще Рефала-2:
https://github.com/Mazdaywik/Refal-05/

Но, впрочем, я этот диалект промышленным не считаю. Это был эксперимент по написанию минималистичного компилятора Рефала.

А Рефал-5λ действительно громоздок и сложен, тут согласен.

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

Можно витиеватыми средствами и не пользоваться.

На Рефале-2 удобно писать лексические анализаторы благодаря тому, что язык поддерживает спецификации переменных. Другие Рефалы возни требуют больше.

 

С уважением,
Александр Коновалов

 

From: Eisymont Leonid verger-lk_AT_yandex.ru [mailto:refal@botik.ru]
Sent: Thursday, January 31, 2019 9:06 PM
To: refal@botik.ru
Subject: Re: Синтаксический анализ в Рефале

 

Балансировка скобок одновременно шла с лексическим анализом. Прохода два было.

А вот действительно не для каждого языка это можно было применить, неприятным был язык Си, там другое применяли.

А вставка скобок была удобна и далее в процессе кодогенерации.

У меня такое впечатление, что сейчас это придется все вспоминать, как в 70-е - 90-е года, в этот 20-летний период. Потом было использование лет пять в НИР Беркут, это уже середина первой декады 2000-х.  Сейчас причина - необходимость быстрой разработки новых микропроцессорных СБИС и их ПО, особенно в России. Это уже связано с обеспечением национальной безопасности, доигрались.

Явно потребуется быстродействующая реализация Рефала с глубоким распараллеливанием выполнения программ. Я бы даже ориентировался просто на Рефал-2 с небольшими инженерными расширениями и богатому набору машинных операций. Собственно, к тому, куда развилась наша реализация с Колей Мансуровым.

Последующие версии Рефала мне явно не нравятся, сложные. Опираюсь на опыт разработки компиляторов на Рефале около 30 лет. Программы компиляторов были огромные и сложные по реализуемым алгоритмам и целевой архитектуре, там было не до витиеватости средств Рефала.

Л.Эйсымонт

 

31.01.2019, 20:25, "Александр Коновалов a.v.konovalov87_AT_mail.ru" <refal@botik.ru>:

Добрый вечер, Леонид!

Вообще-то, я писал про суперкомпиляцию… Но и про компиляцию мне уже есть, что сказать.

<<< опущено >>> 

 

 

 

--

_______________

С уважением,

Аркадий Климов,
с.н.с. ИППМ РАН,
+7(499)135-32-95
+7(916)072-81-48