Re: [NON-SUBSCRIBER POST] Fwd: Refal и ChatGPT 4.0
> См. ниже результат. Видно, что скобки оно НЕ понимает. Короче, они искренне верят, что пднпсвязанный линейный список однотипных элементов это самое сложное, что бывает в мире значений. Кто ее этому учил? С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: [NON-SUBSCRIBER POST] Fwd: Refal и ChatGPT 4.0
А еще в рефале есть сконки. Интересно, как зверушке зайдет такая функция?
f {
= ;
s.1 e.2 = s.1
(e.1) e.2 = ();
}
Ну, там стандартные вопросы: чему равно > и т.п.
Всего доброго,
Сергей Абрамов
Вы писали 05 апреля 2023 г., 19:31:15:
> ChatGPT ведёт себя даже не как студент, а как участник некоторого
> интеллектуального блица, в котором нет времени подумать, т.к. ответ
> нужно давать как можно быстрее. В принципе, из общих соображений
> понятно, почему так происходит -- каждое слово ответа порождается за
> константное время, так что чем сложнее вопрос, тем хуже ответ.
> Тем не менее, грамотно составленный запрос может существенно
> улучшить качество ответа. В частности, очень помогает, если удаётся
> заставить модель порассуждать, а не прямо сразу выдавать ответ.
> Я тут провёл такой эксперимент -- дал модели пример подробного
> объяснения работы рефал-программы, а потом попросил так же точно
> объяснить работу другой программы. Вот, что получилось (мои запросы
> -- зелёный цвет, ответы ChatGPT -- синий цвет):
> Here is a function in Refal language:
> ```
> f {
> = ;
> t.1 e.2 = ;
> }
> ```
> Someone explains, how this function works:
> 1. Function `f` has two sentences:
> * first sentence states, that if we pass empty expression to
> function `f`, it will return empty expression;
> * pattern in the left side of the second sentence means, that
> we must bind variable `t.1` to the first term of an expression,
> passed to function `f`, and then bind variable `e.2` to the rest terms of the
> expression.
> 2. If we call function `f` with empty expression, this expression
> will satisfy the pattern in the first sentence, and the function will return
> empty sentence.
> 3. If we call function `f` with non-empty expression (e.g. ` 20 30>`), then this expression will satisfy the pattern in the
> second sentence, and will be split into two parts -- first term (10)
> will go to the variable `t.1`, and other terms (20 and 30) will go
> to the variable `e.2`. Then, as it is described at the right side of
> the second sentence, function `f` will be called recursively with
> the value of variable `e.2` as its argument.
> 4. We see that at every level of recursion the argument passed to
> function `f` gets shorter by one term. So at some moment it will
> become empty, and the first sentence of function `f` will fire,
> returning the empty sentence as a result.
> 5. Therefore, function `f` always returns empty expression.
> Please, give the same explanation of how the following function `g` works:
> ```
> g {
> = ;
> t.x e.X = t.x;
> }
> ```
> 1. Function `g` has two sentences:
> * The first sentence states that if we pass an empty expression
> to function `g`, it will return an empty expression.
> * The pattern in the left side of the second sentence means
> that we must bind variable `t.x` to the first term of an expression
> passed to function `g`, and then bind variable `e.X` to the rest of the terms
> in the expression.
> 2. If we call function `g` with an empty expression, this
> expression will satisfy the pattern in the first sentence, and the
> function will return an empty expression.
> 3. If we call function `g` with a non-empty expression (e.g. ` 20 30>`), then this expression will satisfy the pattern in the
> second sentence, and will be split into two parts -- the first term
> (10) will go to the variable `t.x`, and the other terms (20 and 30)
> will go to the variable `e.X`. Then, as it is described on the right
> side of the second sentence, function `g` will be called recursively
> with the value of variable `e.X` as its argument, and the result of
> this recursive call will be followed by the value of variable `t.x`.
> 4. We see that at every level of recursion, the argument passed to
> function `g` gets shorter by one term. So at some moment, it will
> become empty, and the first sentence of function `g` will fire,
> returning the empty expression as a result. However, unlike function
> `f`, function `g` appends the value of `t.x` to the result of the
> recursive call at each level of recursion.
> 5. Therefore, function `g` reverses the input expression. For
> example, if we call ``, the function will return the expression
> `30 20 10`.
> Как видим, ChatGPT воспроизвела мои рассуждения, подкорректировав
> их под другую функцию, и в результате догадалась, что функция переворачивает
> выражение.
> Теперь у ChatGPT можно спросить, что будет, если применить функцию
> к результату применения этой же функции:
> Imagine, that we call function `g` twice: `>`, where X denotes some
> expression.
> Explain, what expression will function `g` return.
> When we call function `g` twice as `>`, the following steps occur:
> 1. The outer call to function `g` receives the result of the inner
> call to function `g` as its argument. Let's first consider the inner call ` X>`.
> 2. As we explained earlier, function `g` reverses the input
> expression. So, the
Re: Refal и ChatGPT 4.0
> Можно было бы и по-русски, но по-английски меньше расходуется... Спасибо! Содержательное знание. Теперь по сути: 1. Все что увидел -- это поверхносный перевод с одного языка (Haskell) на другой (гипотетический Рефало-суржик) 2. Конечно, типизация это гораздо серьезнее, чем сказано. И даже не в смысле детализации. А в смысле отсутствия важной части: как программист строит свои собственные типы. В мире типов программист должен иметь возможность создавать свои конструкторы типов. Если конструкторы ограничены предопределенными тремя -- [Тип], Тип1 -> Тип2 и (Тип1,... ТипN),-- то не интересно. Это не язык для реализации Турчинской цели -- "построение формальных лингвистических моделелй" 3. Рефал Плюс редкий язык программирования с честной реализацией не только арности функций, но и коарности. Честной коарности нет в Хаскелле, например. И в типизированном Рефале лично я это хочу увидеть. Это все субъективно. И, конечно, не надо об этом говорить ей (ему, ему), чтобы не расстраивалась. Всего доброго, Сергей Абрамов
Re: рефал всё же скорее умер :(
> Это видимо о том, что котик Шредингера может быть и жив и мертв > одновременно. Зависит от наблюдателя. Да. Смотрите, насколько разнятся впечатления у разных наблюдателей. Причем -- все правы. Всего доброго, Сергей Абрамов
Re: рефал всё же скорее умер :(
> По ощущениям от прошлого года, «пациент скорее жив». И ничему-то нас Шредингер не научил... С.
Re: Рефал "мертв"? Да здравствует Рефал.
День добрый, > 3. А еще хочется отметить неявную конкатенацию - хотя почему она > лучше явного конструктора, сказать трудно. Ой, это я всегда понимал: два больше одного. Вот и все. В Лиспе все пораждается из атомов (один из которых Nil) одним конструктором (Cons _ _), причем он жесткий: (Cons A1 B1) == (Cons A2 B2) <==> A1==A2 && B1==B2 В Рефале два конструктора (_) и _ _ При этом второй не жесткий. Это противоречит лозунгу минимализма из п.4 письма Аркадия. Зато делает предметную область языка гораздо богаче, а жизнь программиста гораздо веселее. А метапрограммиста -- метавеселее. С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: Вопрос к выпускникам физматшкол или математикам/программистам
> Мне она напомнила другую задачку, про которую тоже утверждалось, что > академик в здравом уме решить её не в состоянии, при этом дети, не > испорченные ещё всякими иррациональностями, решают её на ура (это я > сам наблюдал): Понравилось, спасибо! PS. А почему 42? ;-) Два раза "очко"... Всего доброго, Сергей Абрамов
Вопрос к выпускникам физматшкол или математикам/программистам
Не бейте сильно за офф-топик! https://www.facebook.com/sergei.abramov.96/posts/10225409374317673 Вопрос к выпускникам физматшкол или математикам/программистам Вот внизу есть две задачи. И еще ссылка на видео про историю этих задач (просьба поставить на паузу в 6:30). Автор ролика (да и я сам) интересуется, для какой доли выпускников физматшкол (или просто математиков, программистов) первая задача проще второй задачи. Буду благодарен за Ваши мысли и репосты (для более широкого опроса). Мне история (про чаепитье академиков с этой парой задач) показалась удивительной. PS. В видео есть мой комментарий на эту тему... Но его стоит читать когда для Вас все закончится ;-) == Задача 1. Придумайте непрерывную функцию, которая была бы определена на всей действительной оси, принимала рациональные значения в рациональных точках, иррациональные значения в иррациональных точках, и при этом не являлась бы линейной ни на каком промежутке. Задача 2. Шоколадка имеет размер 6×10 клеток. За один ход разрешается разломать один из уже имеющихся кусков на два по какой-нибудь ложбинке. За какое наименьшее число ходов можно разбить всю шоколадку на единичные клетки? https://youtu.be/GyruSwKAro0 С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: Изобретение велосипеда
> Знаки < и > Турчин стал использовать уже в Америке, там их ему на > конференции предложил МакКарти. Что-то мне запомнилось, что это был Бэкус. И понятно почему именно Бэкус. Есть связь между граматиками и Рефалом С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: Рефал-5, Рефал Плюс и форматы
День добрый, всем! >> Но есть один нюанс. Рефал Плюс использует массивное представление >> данных с дорогой конкатенацией. >> ... >> Эту проблему создатели языка решили жёстко: форматы функций >> (которые, вообще-то, идиома, рекомендация) сделали частью языка. > Мне видится, что было немного не так. Не "язык Рефал Плюс такой, > потому что он использует массивное представление", а наоборот: "он > использует массивное представление, как наиболее подходящее (с точки > зрения авторов в тот момент времени) для реализации возможностей > языка Рефала Плюс". А возможности и особенности языка проистекают из > цели: сделать язык, замкнутым относительно суперкомпиляции. Последнее предложение самое важное и наиболее часто забываемое во всех обсозрных материалах про историю рефала. У С.А.Романенко перед Рефалом Плюс был препринт, про диалект Рефала, в котором выразимы результаты разных оптимизаций (например, отсечения удлинений, КУД-ы), включая суперкомпиляцию. Мне нестерпимо горько, что массово так и не понято, что любая разумная суперкомпиляция из любого диалекта Рефала, в котором арнострь и коарность равна единички, строит результат, в котором арности и коарности базовых функций (конфигураций) остаточной программы оказываются любыми, не обязательно единицами. Это и только это и есть форматы фуннкций. Арности и коарности. И для меня было знаково, что Рефал Плюс был (как мне известно) первым (а на мой вкус -- и единственным) функциональным языком, с внятной реализацией не только арности, но и коарности. Как результат, в рамках Обнинского семинара мною и Рутиком была написана программка "глюкало", которая брала вывод тогдашнего суперкомпилятора Турчина (это был S-граф) и преобразовывала его в Рефал Плюс програму. С арностью и коарностью. Вот так. На входе в Турчинский суперкомпилятор Рефял-5, на выходе S-граф и по нему Рефал Плюс, нашей "глюкалой". А до того, сам Турчин как-то и не брался откинуть S-граф обратно в Рефал-5. Ну, мол рук не хватало. Вот он рефал-мальчиков и просил поучаствовать... ;-) Но, на мой вкус, не рук не хватало, а проблемы были с тем, что Рефал-5 не совсем пригоден для изображемия результата своей суперкомпиляции... В силу ровно указанных сложностей. >> На сколько я знаю, когда-то были планы реализации front-end’а >> Рефала-5 в компиляторе Рефала Плюс. > Да, планы были, но, как я помню, в прямом виде осуществлены не были > (Сергей Михайлович, Антон, поправьте, если ошибаюсь). Планов было много, увы, не все сделано... > Однако, в 2000г. был другой проект. У SCP4 результат > суперкомпиляции сначала строится в виде графа, а затем уже > транслируется к Рефал 5. Был проект поменять backend SCP4 и > генерировать из графа не Рефал 5, а Рефал Плюс. Этот проект > назывался CGRp (http://rfp.botik.ru/cgrp) и был выполнен Антоном > Орловым и мной (в нашем студенчестве). Тут многие возможности > Рефала Плюс и пригодились, т.к. в этом графе есть и форматы > функций, и другие особенности. Это уже была взрослая и зрелая реинкарнация "глюкалы". Да, про имя: наша первая программка была названа в честь Роберта Глюка, который написал перед этим рабпту "В нутре суперкомпилятора" и изложил некие технические детали, которые помогали понимать, что же там происходят. Читать S-граф было не легко. И перевод из него в человеческий язык -- это была работа того же плана, который сделал Роберт в своей публикации... > Поэтому компилировать (вернее суперкомпилировать) Рефал 5 в Рефал > Плюс можно с помощью SCP4 ;). ;-) В точку >> Но есть один нюанс. Рефал Плюс использует массивное представление >> данных с дорогой конкатенацией. > Возвращаясь к конкатенации. В языке две основные операции с > выражениями: разбор (взятие подвыражений, копирование) и сбор > (контакетанция) . По сути следует рассматривать одну обобщенную > операцию: разобрать выражение на части, а потом из частей собрать > новое выражение (говорю в первую очередь про разбор-сбор на одном > уровне выражения, без "спуска" в скобки). Если какая-то часть > размножается или нужно сохранить исходное выражение (чтобы, > например, использовать в другой ветке программы), то копирование той > или иной части будет необходимо независимо от представления. > Поэтому массивные представления Рефала Плюс или Рефала 6 показывают > сравнимые результаты с другими представлениями (правда, не знаю > глубоких исследований). > И небольшой оффтоп о представлениях. Мне было бы интересно, если бы > студенты поисследовали "необычные" представления данных: Rope и > Finger Tree. Если я правильно помню, то на их основе разбор-сбор > выражений будет по сложности всегда логарифмический. Вот, хорошая постановка проблемы. > Мы узнали об этих представлениях на одном контесте. Каждый год > проводится ICFP Programming Contest - соревнования при конференции > по функциональному программированию. Это три дня (72 часа) на одну > необычную Задачу (студентам рекомендую! там задачи очень необычные: > из условия обычно совершенно непонятно, что же в итоге
Re: Запахи кода и антипаттерны в Рефале
День добрый, всем! > А какие вы можете назвать запахи кода и антипаттерны, характерные > для Рефала? Все, что вскрывает (или скрывает?) недостатки используемого представления объектных выражений и приводит к чудовищному (для пониманию) кода: 1. Выворачивание скобок наизнанку, для организации прохода по выражению. 2. Боязнь копирования кусков выражений в разные "дочерние" функции. Этим страдают многия языки. Например, в Эрланге целый культ на тему "стремись к хвостовой рекурсии!" и "пиши с аккумулятором, а потом выдай результат, навесив на него reverse (Который, видимо, у них написан на не Erlang-е)". Если мы стремимся к самодокументированному коду без комментариев, то такие фенечки должны не приветствоваться. С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: Сортировка в Рефале-5
День добрый, > И таким образом ещё и может экономиться память: вторая ссылка на > равный скобочный терм может оказаться ненужной и удалиться как > мусор. Так точно. Нулевое время при повторной проверке на равенство (мемоизация) и освобождение пямяти. И это реализуемо во всех представлениях выражений с "подвешенными" скобками. Структура, e1 = '*' e2 = (е1)(е1) e3 = (е2)(е2) ... занимающая при печати O(2^N) знаков может требовать для хранения O(2*N) звеньев. Да. Всего доброго, Сергей Абрамов
Re: Сортировка в Рефале-5
День добрый, всем! > Вряд ли такое возможно, Александр! > Интуиция подсказывает, что при "элементарных" преобразованиях > порядок сложности алгоритма не должен измениться... -- Колапсирующие джунгли порядок меняют, и понятно почему. Ну, и ручками, мемоизация (а именно ее колапс поднимает) позволяет изменить порядок. PS. К слову, в рефале плюс встроены колапсирующие джунгли над данными: если понадобилось сравнить два терма-скобок (а скобки у нас подвешенны) и они оказались равными, то оба терма-скобок делаются "такими же" -- в смысле указывают на одно место и имеют равную длину. То есть, термы становятся не просто "равный", а "тот же ссамый". С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: семинар ИПС
День добрый, всем! 1. Надеюсь, Андрей (psime...@gmail.com) увидел ответ на вопрос "хоть кому-то это интересно?" -- да, народ желает ознакомиться. 2. Дата всем будет сообщена загося. 3. Все, кто сможет приехать -- всем будем рады. 4. Будет ли возможность поучаствовать дистанционно? Это вопрос к Андрею (psime...@gmail.com). Технологии онлайн трансляций со всякими заморочками -- они в Институте освоены, и к кому обращаться с этим -- тоже ясно. Ждем финальных решений распорядителей семинара С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308 Вы писали 11 февраля 2020 г., 16:58:36: > Добрый день всем! > «Тема интересная. А нельзя ли послушать дистанционно? Я не в Москве.» > Ну так и семинар не в Москве! J > > А если серьёзно, когда будет известна дата семинара? Я бы съездил. > > С уважением, > Александр Коновалов > > From: Александр Гусев gusev_aleksandr_AT_mail.ru > Sent: Tuesday, February 11, 2020 4:40 PM > To: refal@botik.ru > Cc: Andrei P. Nemytykh ; Belyshev D. > ; Evgeny P.Kurshev ; > Guliev Y.O. ; Komarov S. ; > Malych V. L. ; Sergej. V. Znamenskij > ; Valeriy Yumaguzhin > ; Анатолий Цирлин ; > Вячеслав Хачумов ; Ирина Расина > ; Николай Непейвода ; > Сергей Амелькин ; Тищенко И.П. > ; Хаткевич Марк Иванович > ; Виноградов Андрей Николаевич > ; Yuri Sachkov ; > Ponomareva S.M. > Subject: Re[2]: семинар ИПС > > Добрый день, коллеги! > > Тема интересная. А нельзя ли послушать дистанционно? Я не в Москве. > > Вторник, 11 февраля 2020, 16:31 +03:00 от Sergei M. Abramov > abram_AT_botik.ru : > >> Я получил предложение о докладе на семинаре ИПС, прилагаю ниже. > Это я направил Vladislav Protasov >> Прошу вас написать мне --- кому-нибудь в ИПС интересна эта тема? > Насколько он мне говорил, автор опирается на MST-теорию В.Ф.Турчина. > Соответсвенно, я бы хотел иметь возможность (совместимость с моим > расписанием) послушать доклад. > Ожидаю такой же реакции от рефал-компании. > С уважением, > Абрамов С.М. > ab...@botik.ru > мобильный: +7(903)2928308 >> Соответственно найдутся ли желающие прослушать и квалифицированно >> оценить доклад? >> С уважением, >> Ю.Л.Сачков >> >> Прошу включить в программу Вашего >> семинара доклад "Основы теории и >> практика применения систем >> коллективного интеллекта". >> Краткая аннотация. >> Акторами систем КИ могут быть эксперты, >> компьютерные программы, нейронные >> сети. Введена абсолютная шкала, система >> сертификации и единица измерения >> интеллектуальной силы акторов - 1 ИНТ. >> Доказаны базовые теоремы, получены и >> обоснованы эффекты усиления >> интеллекта в системах КИ и снижения до >> малых величин вероятностей принятия >> ошибочных решений. >> Доцент МАИ, к.ф.-м.н. Протасов Владислав >> Иванович >> *** > > > > С уважением, > Александр Гусев > gusev_aleksa...@mail.ru > -- С уважением, Абрамов С.М. mailto:ab...@botik.ru
Re: семинар ИПС
> Я получил предложение о докладе на семинаре ИПС, прилагаю ниже. Это я направил Vladislav Protasov > Прошу вас написать мне --- кому-нибудь в ИПС интересна эта тема? Насколько он мне говорил, автор опирается на MST-теорию В.Ф.Турчина. Соответсвенно, я бы хотел иметь возможность (совместимость с моим расписанием) послушать доклад. Ожидаю такой же реакции от рефал-компании. С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308 > Соответственно найдутся ли желающие прослушать и квалифицированно > оценить доклад? > С уважением, > Ю.Л.Сачков > > Прошу включить в программу Вашего > семинара доклад "Основы теории и > практика применения систем > коллективного интеллекта". > Краткая аннотация. > Акторами систем КИ могут быть эксперты, > компьютерные программы, нейронные > сети. Введена абсолютная шкала, система > сертификации и единица измерения > интеллектуальной силы акторов - 1 ИНТ. > Доказаны базовые теоремы, получены и > обоснованы эффекты усиления > интеллекта в системах КИ и снижения до > малых величин вероятностей принятия > ошибочных решений. > Доцент МАИ, к.ф.-м.н. Протасов Владислав > Иванович > ***
Re: Нужна ли "Ленинская простота" в Рефале?
> Так что Рефал Плюс — не единственный язык с коарность, или слово > «коарность» я понял не так. Понял так, как надо. > В языке Go функции тоже могут возвращать несколько значений: > https://ru.wikipedia.org/wiki/Go#Функции_могут_возвращать_несколько_значений Не знал, Да, сделано "как надо". > В Common Lisp’е функции могут возвращать несколько значений (и это не возврат > списка): > http://lisper.ru/pcl/the-special-operators#Множественные значения Да, тоже не знал. Но, конечно, наворочено... > Языки, которые поддерживают кортежи, не считаются. Ну можно вернуть > кортеж из нескольких значений, но это всё равно будет возврат одного > значения — кортежа, а не нескольких. В точку. Можно эмулировть коарность (коместность) через картежи, списки, записи и другие подобные механизмы. Например, Haskell: splitAt, divMod и т.д... А разница между эмуляцией и истинной коарностью в одном: при эмуляции два результата (несколько) конструктором упаковываются в одну стриктуру чтобы через мгновение разламывать эту структуру в точке приема на составные части (селекторы). Истинная коарность экономит на конструкторе и селекторах. Всего доброго, Сергей Абрамов
Re: Нужна ли "Ленинская простота" в Рефале?
День добрый, всем! > «Постепенно, по мере усложнения задач, возникли желания по > оптимизации и оказалось, что проще вводить новые конструкции в язык, > чем интеллектуализировать исполнение программы изнутри.» > Не понял мысль. Речь о каких новых конструкциях? Ох, для меня важнее другая мотивация: я ее писал и она просто отслеживается в статьях С.А.Ромяненко: 1. Рефал задумывался как метаязык. 2. Результат метавычислений над Рефалом должен естественно изобрабаться на Рефале. А это было не так. И первая (минимальная не пустая) "неподвижная точка" -- Рефал Плюс. PS. Конечно попросят примеров. Напомню один: суперкомпиляция с рассечением стеков пораждает функции с коарностью. Рефал Плюс едиснтвенный из Рефалов с коарностью (если дабе не единственный язык программирования с коарностью в мире). Всего доброго, Сергей Абрамов
Re: Список всех простых чисел
День добрый, всем!
> Прошу прощения за некропостинг, но на письмо отвечу.
> Я остановился на 40 000, поскольку решето Эратосфена на Рефале
> оказалось сильно медленным, и его время растёт нелинейно от длины
> исходного списка. Причём, мне показалось, что даже квадратично.
> Поэтому результата в 176 100 я просто не дождусь.
> Время я замерял для переславской реализации Рефала-5. Рефал-5λ
> сильно медленнее (в разы), поэтому мне стыдно было показывать эти числа .
> В последующей переписке Антон Орлов продолжил оффтопик, мне уже лень
> пытаться переписывать его примеры на Рефал.
Вся переписка очень интересная и содержательная.
То, что нарыл Антон я ввел в свой курс по FP (Хаскелль) под заголовком
"Эратосфен это про вычеркивание, а не про делимость".
Действительно, Эратосфен говорил: оставь P как очередное простое и иди
с шагом P дальше и вычеркивай. То есть, он не про делимость, а про
удаление из изходного множества арифметической прогрессии:
[2P, 3P ..]
С этой точки зрения, чистый Эротосфен выглядит так (это все можно
описать на Рефале, но у меня нет Рефала):
primesE1 :: [Integer]
primesE1 = sieve [2..]
where sieve (p:xs) = let c1 = 2*p
c2 = c1 + p
in p : sieve (minusOS xs [c1, c2 ..])
> primesE1!!2000
> 17389
> (14831010 reductions, 27298448 cells, 2 garbage collections)
здесь minusOS -- вычитание "упорядоченных множеств", представленных
отсортированными ленивыми бесконечными списками:
minusOS :: [Integer] -> [Integer] -> [Integer]
minusOS (x:xs) (y:ys)
| x < y = x : minusOS xs (y:ys)
| x == y= minusOS xs ys
| x > y = x : minusOS xs ys
То, что нашел Антон, это следующих шаг: давайте вычеркивать будем не
как сказал Эратосфен, а вычеркнем ОБъЕДИНЕНИЕ всего, что советовал
вычеркивать Эратосфен. Появляется функция объединения бесконечного
множетсва "упорядоченных множеств", причем они перечислены в порядке
роста первого элемента:
primesE :: [Integer]
primesE = 2 : minusOS [3 ..] cs
where
cs = unionOS
[ [c1, c2 ..] | p <- primesE,
let c1 = 2*p,
let c2 = c1+p
]
unionOS :: [[Integer]] -> [Integer]
unionOS ((x:xs) : xss) = x : unionOS (ins xs xss)
where ins (x:xs) ((y:ys) : yss)
| x < y = (x:xs) : (y:ys) : yss
| x > y = (y:ys) : ins (x:xs) yss
| x == y= (y:ys) : ins xs yss
и этот вариант не лучше, а хуже (в 3+ раз) обычного Эратосфена:
> primesE!!2000
> 17393
> (47292483 reductions, 83601402 cells, 8 garbage collections)
А вот дальше можно сообразить, что первое число, которое удастся
простому P действительно вычеркнуть своей арифметической прогрессией
[2P, 3P..] будет P*P -- все меньшие члены прогрессии уже вычеркнуты до
него. Поэтому прогрессию можно заменить на [P*P, P*P+P ..]
В коде выше это замена всех c1 = 2*p на c1 = p*P
И это ускоряет обычный Эратосфен совсем немного, а Эратосфен с
объединением unionOS -- радикально и он на порядок (раз в 6) обгоняет
обычного!
> primesE1!!2000
> 17387
> (14692824 reductions, 27114235 cells, 2 garbage collections)
> primesE!!2000
> 17393
> (2731729 reductions, 4790869 cells)
Тупое прозрачное опредленеие "N -- простое, если не делется ни на одно
простое P, которое P*P<=K" дает лишь втрое хуже результат:
primes1 = 2 : filter (isPrime1) [3..]
where isPrime1 n = null(filter (\ p -> n`mod`p == 0)
(takeWhile (\ k -> (k*k <= n)) primes1))
> primes1!!2000
> 17393
> (7394774 reductions, 10355414 cells, 1 garbage collection)
И, наконец, мное описанное решето Абрамова-Дейкстры(?), которое не про
вычеркивание, не про делимость, а про взаимную простоту с
произведением простых (gcd pp n)==1 дает такой результат:
primesA = sieve 1 1 2 [2..]
where sieve pp n' lim ns@(n:ns1)
| n <= lim = n : sieve (pp*n) n lim ns1
| otherwise = sieve 1 1 (n'*n') (filter ((== 1).(gcd pp)) ns)
> primesA!!2000
> 17393
> (4254611 reductions, 7465819 cells)
что хуже ("всего" в 1.55 раз) Эратосфена вычеркивания с объединением
unionOS.
Это все.
Есть еще одна идея ускорения, но она применимы ко всем. И если
исследовать ее эффект, то применяя ее ко всем. В коде, который Антон
Орлов нашек на Haskell.org эта идея применена для No=1.
Идея состоит в том, что можно "в уме" вычеркнуть из [2..] все числа,
которые делятся на 2, 3, 5, ... p (взято No первых простых чисел).
Пусть ns результат вычеркивания. Тогда он определяется вот так:
Пусть pp произведение 2, 3, 5, ... p. Тогда:
ns = [ n+r | n <- [pp, 2*pp ...], r <- rs ]
where rs = filter ((==1).(gcd pp)) [p+1-pp .. p]
Если взять No простых, то после фильтрации в rs останется не pp
элементов, a меньше -- length rs. И от исходного множества у нас
останется вот такая доля: (length rs) / pp. Как-то так:
No length rs pp Доля
1 1 2 50.0%
2
Re: Список всех простых чисел
> Мог ошибиться в границах, но смысл должен быть понятен: каждая > следующая граница (lim) получается из предыдущей примерно > возведением в квадрат, так ведь? Так, так, именно! > Поколение - то, что выходит после очередной фильтрации как кусок > списка простых и служит сомножителями в следующем pp. Меня > интересует сколько (какую долю) отсеивает каждая следующая > фильтрация. Понятно, что сначала это 1/2, далее 1-(2/3)*(4/5), > далее 1-(6/7)*(10/11)*...*(22/23) и т.д. Произведение - это доля > остающихся. Просто хотел бы увидеть десятичные числа, как они > меняются, наверно, убывают к 0. Насколько быстро? Алик, я думаю, мое второе письмо (про bs) отвечает на этот вопрос. Хотя и не напрямую. >> Интересно, для Хаскела это тоже актуально, или там умножение pp*n ленивое? > > Ленивое, несомненно. > Неужели? Ну да. Пока кому-то не понадобиться это значение... > Значит на Хаскеле будет автоматически накапливаться в форме терма > 7*11*13*..., да? Да. А понадобиться это только, когда действительно случится прохождение через lim и начнется первый gcd с накопленным, но не посчитанным, произведением. Вот там случится need результата. Все жадные операции перечислены в Haskell-е. И я не вижу среди них умножения, тем более Integer. Всего доброго, Сергей Абрамов
Re: Список всех простых чисел
>> То есть для последнего "поколения" эта работа лишняя. Про поколения. Замечу, что если взять несколько первых простых чисел p1...pK, их произведение pp и профильтровать (\ k -> (gcd pp k) == 1) весь бесконечный список [(pk+1).. ], то результат фильтрации имеет очень простое, эффективное, конструктивное представление на Haskell-е. Q это в своих этюдах использовал. То есть, несколько поколеий можно прогнать в статике, на этапе написания программы. >> А еще хотелось бы посмотреть статистику по числу (доле) отсеянных >> (прошедших) через каждый из фильтров (это мне уже как математику >> интересно). Например, если взять 2 и 3. pp=6, то результатом фильтрации будет знакомое с детсва 6n-1, 6n+1: [ n+r | n <- [6, 12..], r <- [-1, 1]] Если взять 2, 3, 5 (pp=30), то: [ n+r | n<-[30, 60 ..], r<-[-23,-19,-17,-13,-11,-7,-1,1]] Если взять 2, 3, 5, 7 (pp=210), то: [ n+r | n <- [210, 420 ..], r <- bs] bs = [-199,-197,-193,-191,-187,-181,-179,-173,-169,-167, -163,-157,-151,-149,-143,-139,-137,-131,-127,-121, -113,-109,-107,-103,-101,-97,-89,-83,-79,-73,-71,-67, -61,-59,-53,-47,-43,-41,-37,-31,-29,-23,-19,-17,-13, -11,-1,1] :: [Integer] Сжатие серч-спэйса (доля неотсортированного), о чем спросил Алик, состaвит для этих трех случаев: 2/6, 8/30, 48/210 Программка, которая по заданному начальному списку [2, 3,..pK] строит bs, для выражения: [ n+r | n <- [pp, 2*pp ..], r <- bs] очень простая. Всего доброго, Сергей Абрамов
Re: Список всех простых чисел
День добрый, всем! > То есть для последнего "поколения" эта работа лишняя. А что такое последнее поколение, если я строю список всех простых чисел? > Наверно, лучше накапливать в виде списка, а при подаче на Filter > для следующего шага все перемножить. > Интересно, для Хаскела это тоже актуально, или там умножение pp*n ленивое? Ленивое, несомненно. > А еще хотелось бы посмотреть статистику по числу (доле) отсеянных > (прошедших) через каждый из фильтров (это мне уже как математику > интересно). Алик, а мне интересно от математиков (может знакомые есть?) узнать, есть ли хоть какие-то работы (а если есть, то какие) в этой отрасли, где используется (\ k -> (gcd pp k) == 1)? > Нужно спасать рассылку от офтопа. Спамера забанить! > Понятно, что вызов e.ns> на Рефале будет выполняться медленно. Вот, хочу сказать, что меня удивило: ns' = filter (\ k -> (gcd pp k) == 1) ns работает немного медленнее, чем ns' = filter ((== 1).(gcd pp)) ns Вот нифига ж себе? Всего доброго, Сергей Абрамов
Список всех простых чисел
День добрый, всем! Простите, что не про Рефал. Просто не могу вспомнить то, что (как мне помнится) случилось в обстабовке рефал-компании на заре моей профессиональной деятельности (практика в НИЦЭВТе или работа в нем). По каким-то причинам я задумался тогда над построением списка всех простых чисел. И в некий момент сам придумал алгоритм, которрый опирался вот на какое определение последовательности простых чисел: 1. Очередное натуральное число n будет простым, если оно взаимнопросто со всеми ранее найдеными простыми числами. или (что то же самое, но уже совсем близко к коду) 2. Очередное натуральное число n -- простое, если gcd(pp,n)==1, где pp -- произведение всех ранее найденых простых чисел. Понятно, что нужна сверхдлинная целочисленная арифметика. Но, gcd(pp,n) обещал посчитаться быстрее, чем деление n по очереди на все сомножители из pp. Я этот алгоритм (точнее подход, поскольку сам алгоритм похитрее, о нем в конце) придумал сам и очень этим гордился. Но потом в рефал-компании кто-то мне дал книжку. Серегей Романенко? Андрей или Алик Климов? Колля Кондратьев? -- не помню. Книжка была кого-то из великих... Дейскстра? Вирт? И, почему-то, мне кажется, что называлась она "Записки из башни слоновой кости". А в книжке, как мне сегодня кажется, были программистсткие побасенки. Ну, и был коротенький шутливый этюд (близко к тексту): Цитата по памяти === Для эффективной генерации всех простых чисел мнe достаточно всего двух ячеек памяти: integer pp, n; n := 2; pp := 1; while ( True ) do begin if ( gcd(pp, n)=1 ) then begin println(n); pp := pp * n; end; n := n + 1; end; == С тех пор я узнал, что хотя я и самостоятельно нашел такой подход к генерации простых, но я был не единственным (и, скорее всего, не первым) ПРОСЬБА О ПОМОЩИ: 1. Коллеги, если кто-то может мне дать имя автора, название книги, которая мне помнится, то я буду благодарен. 2. И если есть еще какие-либо ссылки на такой подход к проверке простоты -- gcd(pp, n)=1,-- то тоже полезно. Почему вспомнил? Вспомнил я про эту историю во время очередной своей лекции по Хаскеллю в ЯрГУ. Ну, и сегодня написал немного строк на Хаскелле -- приложены. Взгляните, для интереса. primesAD -- это генератор, прямо в лоб переписан приведенный выше паскале-подобный текст. А теперь поговорим про решето. Решето вообще (не обязательно Эратосфена) -- это когда берем начальное пространство поиска -- например, [2..]. И дальше всегда делаем такую пару операций: 1. Некие первые элементы (один или больше) в текущем прастранстве поиска -- заведомо простые числа -- выдаем их в результат. 2. Затем при помощи только что найденых простых фильтруем (сужаем) пространство поиска. Если брать только одно простое n из пространства поиска и фильтровать предикатом ((/=0).(`mod`n)) -- то это решето Эратосфена. А если брать много заведомо простых из пространства поиска, вычислять их произведение pp и фильтровать предикатом ((==1).(gcd pp)) -- то это решето ... назову решетом Абрамова ;-) Пока Вы мне не подскажете другого автора такого же подхода (или где искать). Три остальные программки в Хаскелле -- это разные варианты решета: primesE, primesE1 -- решето Эратосфена (отличии в изобразительных средствах). primesА -- решето Абрамова. А заканчивается файл статистикой (время счета и память) прогона некоторых тестов в HUGSе и в GHCi. Посмотрите статистику... Шуточный этюд "достаточно две ячейки памяти" имеет нешуточное приложение, как мне кажется ;-) Я уж молчу про то, что gcd по Евклиду (как оно описано в прелюдии хаскелля) не самая эффективная реализация gcd (по Кнуту). Всего доброго, Сергей Абрамов primes-AD.hs Description: Binary data
Re: Лесоочистка в Рефале
День добрый, всем! - Чем почтовый список рассылки хуже формата Форумов? - Дык... лайк негде оставить... Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
День добрый, Антон! Спасибо за пояснения! Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
День добрый, всем! > ... По мере тасования памяти скорость падает до 2 раз. Тема диссертации Светланы Подколзиной (Трубицыной): реализация Лиспа с массивным представлением по направлению CDR. CAR -- ссылка, CDR -- соседняя ячейка (близось адресов). Тракторная сборка мусора, которая как бульдозер сдвигала все нужное, собирая свободные ячейки в крупные массивы. С чем боролись? Кэша тогда не было, а вот виртуальная память была. И по мере "тасования памяти" шаг в с;едующую ячейку списка с большой вероятностью приводил к пэйдж-фолту. Вот с этим и боролись. Так что, грусть по массивному представлению имеет давнюю историю. А тот поход за массивным лиспом помню с удовольствием... Мы опирались на реализацию лиспа на фортране с исходными текстами. Фортрановская колода, не очень здоровая. В начале которой просто были описаны два COMMON массива: CAR(100) и CDR(100). ;-) Ну а мы это дело перелопатили потом. Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
День добрый, > Запустил исходный пример Аркадия на Рефале+ (с компиляцией C++). > Heap пришлось увеличить до 2GB. Время - 2.05 секунды. Юра, сделайте с двумя $iter-ами, пожалуйста. Хочется и на текст полюбоваться, и на прогон. Под руками системы нет, а в сухую (без воды в бассейне) и облажаться могу... Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
> Сергей, там два $Iter-а: один во вспомогательной функции > Unacceptable? Ну, да :) Просто второй совсем очевиден... Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
День добрый, всем! > Решение на Рефал Плюс из руководства тоже жадно до стека. > Интересно, какие там пределы? Я не очень понял, какой там стек... Там явно $iter по переменной s.N напрашивается. Всего доброго, Сергей Абрамов
Re: Сравнение веток Рефала
>> (Получилось очень длинно. Интересно, кто-нибудь дочитает до конца?) > Дочитал! Я дочитал вот до сюда: >>А кто дочитал — молодец! И присоединяюсь к сказанному: > Александр, большое спасибо за замечательный обзор и отличий > синтаксиса Рефалов, и основных принципов реализации. Всего доброго, Сергей Абрамов
Re: Потенциальная востребованность
> Да, я в 80-х как раз вдохновился книжкой с подборкой японских статей > об их проекте: пролог, пролог- процессоры и т.п. Но всё пожрала > массовость. Да, да. ЭВМ пятого поколения. В Лиманчике на всесоюзной школе программирования был один заезд про это... А у пиш.машинке (так материалы готовились в те года) буква П западала... И поэтому было многократно написано: "ЭВМ пятого околения". Это предсказало их судьбу... Увы. Всего доброго, Сергей Абрамов
Re: Потенциальная востребованность
> Это просто весеннее обострение... Ну, еще не весна... Хотя, Сретенье Господнее! С.
Re: Синтаксический анализ в Рефале
> Замысловатый ответ ни о чем. Так какой результат, если есть статьи, > то ссылки где?. http://www.botik.ru/PSI/RCMS/publications/publications.html А далее Гуугл "site:www.botik.ru/PSI/RCMS/publications Рефал Плюс" И там сразу находим: http://www.botik.ru/PSI/RCMS/publications/publ-texts/04-Abramov-Novyj-podkhod-p-373.pdf С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308
Re: Синтаксический анализ в Рефале
>>> ... Представлением выражений массивами не советую заниматься. >> Не согласен ;-) > Еще бы понять, почему. Эту реализацию довели до ума? Конечно. Она доступна. Под Эклипсом, со всеми бантиками. И есть публикации, как и что. Новый подход к отождествлению (связанный с решением уравнений над известными и искомыми длинами фрагментов данных) -- есть подробные статьи. Наконец, разные представления накладывают разный стиль для эффективного программирования на Рефале. Увы, это так. Классический пример -- трюк с выворачиванием скобок, при программировании сквозного прохода на Рефалах со списковым представлением. Это красивый фукциональный стиль? -- Нет. Про каждое представление можно аккуратно выписать сильные и слабые стороны. И понять их влияние на стиль программирования. Массивное представление позволяет легко любой фрагмент данных отдавать в разные функции в неограниченном количестве. И это функционально. Всего доброго, Сергей Абрамов
Re: Синтаксический анализ в Рефале
> ... Представлением выражений массивами не советую заниматься. Не согласен ;-) Всего доброго, Сергей Абрамов
Re: Очередная проверка почты № 4
Ответил! С уважением, Абрамов С.М. ab...@botik.ru мобильный: +7(903)2928308 Вы писали 25 января 2019 г., 13:24:02: > Добрый день всем № 4! > Админы botik.ru попробовали починить рассылку, сейчас её проверяем. > Если Вы читаете это письмо, то ответьте на него, желательно > сохраните получателей копии письма (там Андрей Климов, администратор > botik.ru Юрий Шевчук и я на всякий случай). > С уважением, > Александр Коновалов
Re: А как будет по-английски «копилка»?
Подавил я в себе начальные ассоциации и написал "грядка". И что толку? Правда, как утопленник: все равно всплывет! Вот и всплыла > ... Не копилка, а могилка :) Всего доброго, Сергей Абрамов
Re: А как будет по-английски «копилка»?
День добрый, всем! > В учебнике Турчина по Рефалу-5 копилка вообще никак не называется > (ни в русском, ни в английском варианте). Глава называется «4.3 The > Bury-Dig Functions». Закопать и выкопать -- значит грядка, garden bed. Всего доброго, Сергей Абрамов
Re: Рабочее совещание ИПС РАН и МГТУ имени Баумана по Рефалу - слайды докладов и задача
> Сергей, какие-то ошибки в рефальских предложениях, либо я отстал? Да, Андрей все правильно сказал. После правки: F e1 sx e2 sx e3 = sx e1 e2 e3 Сергей
Re: Лесоочистка в Рефале
День добрый, Александр! > В статье от 1993 года «A short cut to deforestation» > http://research.microsoft.com/en-us/um/people/simonpj/papers/deforestation-short-cut.pdf > рассказывается об оптимизации, которая реализована в GHC. Но она не > является оригинальной дефорестацией по Вадлеру (авторы сами об этом > пишут). Ух, не знал! > Там рассматривается простое синтаксическое преобразование для > устранения промежуточных списков и оно чисто синтаксическое. Тоже интересно. Сведение многопроходных алгоритмов к однопроходному с удалением промежуточных структор данных (захватил память -- построил структуру -- разобрал структуру -- освободил память) мне всегда казалось серьезным пробным камнем именно для суперкомпиляции. А тут тебе "на" -- простое синтаксическое преобразование. Удивлен Всего доброго, Сергей Абрамов
Re: Лесоочистка в Рефале
> В личной переписке Андрей Немытых подсказал мне, что дефорестация — > по сути разновидность суперкомпиляции. Об этом была формальная статья (авторов и статью не помню, но там очень формально все разобрано). И своим стидентам я так и говорю: суперкомпиляция уже внедрена в промуышленное программирования -- дефористация (обезлешивание) есть как фаза компиляции в GHC. Всего доброго, Сергей Абрамов
Re: Рефал Плюс как замыкание Рефала относительно суперкомпиляции?
> Xi -- список выражений. Длина списка равна арности функции Fi. В > выражениях из Xi можно использовать (помимо конструкторов, атомов и > конфигурационных переменных-параметров) все лиазон-переменные из Xj, > где j < i. Это верно и для X(N+1) Опечатка. Правильно так: > конфигурационных переменных-параметров) все лиазон-переменные из Yj,
Re: Семинар памяти В.Ф.Турчина в четверг 19 апреля 2018 в ИПМ
День добрый, Танечка! Пара фоток имеется здесь: https://www.facebook.com/sergei.abramov.96/posts/10215806745497954 Всего доброго, Сергей Абрамов
Re: 7 апреля - день памяти В.Ф. Турчина
Вечная Память Учителю! Сергей и Медэя Вы писали 07 апреля 2018 г., 16:45:48: > Дорогие друзья и коллеги! > Сегодня, 7 апреля, день памяти Валентина Федоровича (1931-2010). > Уже 8 лет, как мы живем без него. Он в наших душах, в нашей памяти > и в тех наших делах, которые мы стараемся осуществлять, заразившись > его идеями, и дальше двигать эволюцию в тех областях, к которым > каждый из нас по своему причастен. > Современный технологический, информационный, > "искусственно-интеллектуальный", компьютерный взрыв поражает. > Одновременно происходят колоссальные изменения в обществе и > выявляются многие проблемы. > На наших глазах с большой скоростью разворачивается очередной > крупномасштабный метасистемный переход. И "простым обывателям", и > "крупным ученым" трудно улавливать, что происходит, следить за > событиями, не говоря уж о том, чтобы участвовать. > И теперь особенно чувствуется, как общие эволюционные взгляды > Валентина Федоровича помогают ориентироваться, выделять главное и, > исходя из этого, планировать свою жизнь и дела (хотя и на это > требуется кон-гениальное Турчину умственное усилие, которое далеко > не всегда удается). > Поминая Валентина Федоровича, желаю всем его последователям быть > достойными его памяти. > Всего наилучшего, > Андрей Климов
Re: Не понял про ограниченный РЕФАЛ
> У меня в таком базовом философском ключе не всегда получается > думать… Надо учиться. Так и у меня не было ;-) меня учили ;-) Я себе (и студентам) объясняю себе так: Турчин сначала физик. Потом он метафизик. Потом идут теоретические обознования информатики (да и математики). Это объясняет [мне], почему у него все построения такие "материальные" и "натуральные". И почему у него именно "процесс-ориентированный подход". Вычисление программы? -- Построение стартового состояния и цепочка переходов (процесс) из состояния в состояние, пока не достигнем тернимального. Состояние? Конечная строка в некотором конечном алфавите (и в некотором синтаксисе). Никаких математических абстракций! Никакой денотационщины. Все очень материально и физично. Натурально. Всего доброго, Сергей Абрамов
Re: Не понял про ограниченный РЕФАЛ
>> Но еще ближе к практике общая идея: рассматривать систему уравнений >> на длины всех неизвестных. > Ближе к практике в том смысле, что из уравнений надо выводить > оптимизации? Если угодно, то да. Но, на самом деле, более обще скажу: всегда надо отсекать (не допускать возникновения; терминировать, если возникли) все состояния (варианты, ветки, обороты циклов), в которых нарушены условия материального баланса или иные законы Природы (инварианты, законы сохранения). Уравнение материального баланса (аналоги: закон Киргофа или уравнения на равенство длин правой и левой части отождествления) штука натуральная (природная) и ее неиспользовать не правильно. Глаза на роль закона материального баланса мне (мой исторический субъективный опыт) открыл С.А.Романенко. У него в обобщенном отождествлении было правило -- рассмотрим перестройку: expr1 : expr2 Рассмотрим множество элементов левой части и правой части. Удалим в множествах одинаковые элементы. Если остались только жесткие и их разное количество, то неотождествление (если остаклись разные знаки, то тоже неотож). Классика: e.X : '*' e.X *' e.X : е.X Слава Богу, у нас не Haskell: x = '*' : x. Всего доброго, Сергей Абрамов
Re: Не понял про ограниченный РЕФАЛ
> Но это, всё-таки, искусственный пример, призванный > продемонстрировать возможности алгоритма. Примеры образцов выше > всё-таки ближе к практике. Да, приведенные примеры ближе к практике. Но еще ближе к практике общая идея: рассматривать систему уравнений на длинны всех неизвестных. Это же уравнение материального баланса! Ну что еще может быть таким натуральным (естетсвенным). Это правильная идея. ;-) С.
Re: Рефал умер
День добрый, всем! Вот за что я и люблю Рефал Плюс. И это объесняет мое молчание. Даже когда обсуждается геерация Си кода по рефал-программе (ведь там такие статьи написаны и доступны про правильную компиляцию отождествления). Ни, и, конечно, представление рефал-выражений обязано быть массивным. Всего доброго, Сергей Абрамов Вы писали 04 февраля 2018 г., 01:46:37: > Не согласен.Рефал хорош был своей простотой, технологичностью. Это > и старшее поколение специалистов, наших учителей, ценило в этом > языке прежде всего. Что было сделано Сергеем и Андреем в Рефале-2 - > это, наверное, оптимальный уровень его усложнения для практического > применения.Мы на протяжении десятилетий на этом диалекте языка > создавали очень сложные компиляторы языков высокого уровня для > необычных новых машин советского времени. Причем именно эта > технология была решающей, когда требовалось быстро создать > компилятор для новой машины. Никто не брался, а мы в Институте > Прикладной Математики им.М.В.Келдыша АН СССР вытягивали один проект > за другим. Примеры с Бураном и Булатами - наиболее яркие, а ведь > были еще и язык НОРМА, ПС-3000, ЕС-1195, это последний > суперкомпьютер Советского Союза. Далее, уже в середине первого > десятилетия двухтысячных годов, первые исследования по НИР "Беркут", > это мультитредовый суперкомпьютер Ангара стратегического назначения, > были очень быстро проведены с использованием именно Рефала.Мы > применяли и применяем реализацию Рефала-2 на односвязных списках с > кольцевыим цепочками, которую с Колей Мансуровым сделали в свое > время также в ИПМ. Эта реализация жива, исходники есть, имеется > очень богатая библиотека машинных операция с продуманными > нестандартными возможностями, просто я не стал вмешиваться в > переписку в силу разных причин. Она у нас в горячем резерве, когда > потребуется будем использовать в своих работах. Время-то > приближается лихое...будет невероятно много разработок > специализированных высокопроизводительных устройств.Новые версии > Рефала - хорошее дело. Только я не знаю, был ли у них такой объем > практического применения в сложных проектах, как у нас. Тем не > менее, с уважением отношусь к этим работам, но уж очень много в > новых версиях текста и сложностей, поэтому мы это использовать вряд > ли будем в своих проектах. А вот параллельная версия реализации > обычного Рефала явно не помешала бы.В далеких семидесятых Рефал мои > руководители и я рассматривали не только как технологичный язык для > задач обработки символьной информации, но и как прототип внутреннего > машинного языка символьного процессора с отличной от > фон-Неймановской архитектурой. С этой точки зрения компилировать > Рефал в Си с невероятными оптимизациями - это "бег на месте или даже > ход назад", в угоду старых архитектур, хотя на сегодняшний день, > м.б. и имеет практический мысл. Да и этот Си слишком сильный > конкурент на поляне существующих архитектур, он, как сорняк, все > забивает, не дает новым языкам подняться в полный рост, причем дело > не только в новых версиях Рефала. Даже PGAS языки не пошли. Выбиться > сейчас с новым языком без фантастических преимуществ практически > невозможно. Кстати, одна из причин, почему мы изначально брались с > Рефалом за самые "гиблые" с точки зрения возможной выполнимости > проекты - стремление доказать привлекательность этого языка. Ну а > потом, приобрели соответствующую известность из-за этого и > популярность "пожарной команды". Затянуло, особенно если "просили" > из ЦК КПСС или уважаемых ведомств. Доказывали несколько десятилетий, > результат - какой есть. Если честно, то не очень, ведь техника > приходит и уходит, заслуги забываются, а жизни своей немного жаль. > Можно было бы и более фундаментальными делами заняться, диссертации > писать по этому поводу. В итоге цель наша с продвижением реализаций > этого функционального языка с глубоким распараллеливанием, вплоть до > применения клеточных автоматов, как это видели в семидесятых, пока > не достигнута.С другой стороны, слишком большие перемены ожидаются в > архитектуре вычислительной техники в предстоящие десять лет в связи > с достигнутым пределом развития КМОП-технологий и приближением > пост-Муровской элементной базы, а там - своя схемотехника, это > скорее всего, многие аналитики предсказывают. Там и место новым > языкам, в том числе и Рефалу, хотя бы упрощенной версии, об этом и > думали много лет назад.Будущее загадочно, не всем его дано увидеть, > да и не так быстро оно наступает. Вот и я не претендую, м.б. и > ошибаюсь, но мы об этом мечтали в свое время. Дано ли будет это > увидеть или разочароваться? На всякий случай, не стоит отчаиваться и > делать поспешные выводы, перечеркивать достижения и опрежавшие время > работы предшественников, причем целых двух - трех поколений, да и > хоронить само это детище Валентина Федоровича. Таким людям, как он, > дано увидеть сквозь годы, я в это верю, вижу признаки его правоты в > современных проявлениях и грядущих изменениях.Л.Эйсымонт >
Re: FW: Рефал умер?
>> Плата за структурное программирование. В варианте Сергея Абрамова
>> (в следующем письме) вводится дополнительная булевская переменная и
>> тоже требуется дополнительная проверка
> И, кроме того, дополнительная переменная оказывается нелокальной
> для цикла,-ов, хотя ей лучше быть локальной, ведь дальше она не
> используется.
Ну, это я так написал. Перетащите ее мышкой правее первого слова for и
она станет локальной.
По поводу "дальше она не используется"... это зависит от задачи ;-)
Ее смысл: уже нашли или еще нет. То есть, это то самое <элемент
обнаружен>. И в этом смысле, то, что я написал
НИКАК не отличается от:
> <установить на начало>
> while (! <достигли конца> && ! <элемент обнаружен>)
> <вычисление следующего и переход к нему>
> if (<достигли конца>)
> <действия, если элемент не найден>
> else
> <действия, если элемент найден>
Считать, что вот такой переход в 2D-массиве:
>, ++col;
> if (col == MAXCOL) {
>col = 0;
>++row;
> }
лучше вложенного цикла... Ну, не знаю ;-) Дело вкуса ;-) А о нем не
спорят.
Мои предпочтения давно в области прозрачности кода для чтения, а не в
области эффективности для исполнения.
Лет семь назад встретил цитаты из великих (не помню кто и цитата по
памяти, не точный текст):
> Под флагом и по причине борьбы за эффективность в программировании
> совершено больше преступлений, чем по всем остальным причинам вмести
> взятын. Включая непроходимую тупость.
С тей пор как прочитал, как и отрезало ;-)
PS. Я не уверен, что нормальный компилятор не удалит в моем тексте
так называемую "лишнюю проверку" ;-) А "лишняя переменная" это не
более, как экономия вычислений за счет табулирования ранее
посчитанного значения. Кстати, если окажется, что она действительно
лишняя, то и ее компилятор должен удалить (дефорестация). А читать
приятнее с нею (опять, дело вкуса).
Всего доброго,
Сергей Абрамов
Re: FW: Рефал умер?
День добрый, всем!
> ... легко переписать и стандартными for:
> for (row=0; row < MAXROW; ++row)
> for (col=0; col < MAXCOL; ++col)
> if (elem_at(row,col)) goto x;
> x:
> По-моему, так текст и короче, и разобрать легче, а и выполняемых на
> каждом шагу действий меньше. Если goto очень раздражает (не меня),
> то можно и без него:
> for (row=0; row < MAXROW; ++row) {
> for (col=0; col < MAXCOL; ++col)
> if (elem_at(row,col)) break;
> if (col < MAXCOL) break;
> }
управление легко разменять на дополнительные переменные. Так докаывают
теорему о структурном программировании.
И я часто так делаю, примерно в таком стиле:
bool goon = true;
for (row=0; row < MAXROW && goon; ++row)
for (col=0; col < MAXCOL && goon; ++col)
goon = elem_at(row,col) == 0;
Всего доброго,
Сергей Абрамов
