FW: Рефал умер?
Александр Коновалов
В начале 2000-х годов язык Рефал ещё как-то развивался, выходили новые версии компиляторов: РЕФАЛ-5, Рефал-6, была некоторая активность на сайте http://wiki.botik.ru/Refaldevel/, был написан компилятор SCP4. Я читал старый архив рассылки refal@botik.ru, в нём тоже были обсуждения Рефала и не только (например, сравнивали его с Си++). Потом, практически синхронно со смертью Турчина, активность спала практически до нуля (архива рассылки refal-devel в сети не нашёл, судить не могу).
В текущей рассылке (судя по новому архиву) в основном рекламируются конференции по метавычислениям, выкладываются сканы старых архивных материалов и Сергей Михайлович Абрамов поздравляет с Новым Годом.
Я правильно понимаю ситуацию, что Рефал появился не от хорошей жизни: Турчину нужен был инструмент (формальный язык) для выражения идей метавычислений, суперкомпиляции, существовавшие тогда Фортран и Алгол для этого не подходили, а о Лиспе в СССР никто тогда не знал? И теперь, когда появились новые, современные функциональные языки программирования, для реализации идей суперкомпиляции стали применять уже их? Те же Юрий Климов и Илья Ключников свои суперкомпиляторы писали отнюдь не на Рефале. А язык Рефал остался в прошлом.
И то, чем я занимаюсь (https://github.com/bmstu-iu9/simple-refal (смотреть ветку refal-5-lambda), https://github.com/Mazdaywik/mrefal) уже в проекте устарело на десятилетия? Не, своим хобби я заниматься продолжу, мне это интересно. Хоть и бесперспективно.
--
Коновалов Александр Владимирович, преподаватель
кафедра ИУ9 «Теоретическая информатика и компьютерные технологии»
МГТУ имени Н. Э. Баумана, Москва
Arkady Klimov
s...@cnshb.ru
Большое спасибо, Аркадий, за развернутый ответ!
Полностью с Вами согласен, что рефал жив его пользователями.
Я в своей производственной и др. деятельности активно использую рефал. Правда, я задержался на рефале/2 (с метакодом B), и пользуюсь последнее время своей версией. В паре задач использовал рефал-5, но потом от него отказался, т.к. мне удобнее думать на 2-м, к которому давно привык...
Большую работу по пропаганде рефала проводил научивший меня рефалу Топунов В.Л., но его уже давно нет, и, мне кажется, после него пропаганда рефала в вузах резко сократилась...
http://www.cnshb.ru/vniitei/sw/refal/
http://ito.edu.ru/1999/I/2/278.html
http://sw710.narod.ru/For_ITO-2000.htm
http://swi.16mb.com/
Александр Коновалов
Добрый день, Аркадий!
Большое спасибо за развёрнутый ответ. Сейчас я задам несколько развёрнутых вопросов. Заранее прощу прощения у подписчиков за многабукаф.
… а именно, с включением вложенных анонимных функций -- аналога лямбда-абстракции.…
Эта идея не моя, впервые она была предложена Сергеем Скоробогатовым в диалекте Refal-7 в 2006 году:
https://waybackmachine.org/web/20070813011422/http://iu9.bmstu.ru/science/refal.pdf
(даю ссылку на Wayback Machine, поскольку с сайта кафедры этот файл удалили). Вероятно, вы знакомы с ним (и со Скоробогатовым, и с диалектом), но ссылку я даю для всех читателей рассылки.
…(только поверхностно посмотрел доки)…
Основная дока (manul.pdf), к сожалению, (а) недописана, (б) частично неактуальна. Основной массив знаний (если углубляться) скрывается тут: https://github.com/bmstu-iu9/simple-refal/issues (включая закрытые задачи). Но на беглый просмотр там слишком много.
…было бы интересно и важно наработать множество примеров и техник с использованием этих новых средств, демонстрирующих их удобство и преимущество.
Пользуюсь вложенными функциями уже с 2009 года, мне нравится. Когда добавил их в язык, почувствовал прирост своей производительности, по сравнению с подмножеством Базисного Рефала. Пример их использования (несколько извращённый) вот:
https://github.com/bmstu-iu9/simple-refal/tree/master/doc/examples/inifile
Более нормальные примеры использования есть в исходных текстах самого компилятора.
Есть основания полагать, что Рефал создавался Турчиным именно как язык первого порядка, и в этом была интенция автора. … Рефал-5 -- это максимум того, что он был готов допустить.
Есть у меня идеи по статической типизации Рефала (но о них сейчас пока рано, через несколько месяцев будет в самый раз), и обдумывая их, я понял гений Турчина. РЕФАЛ-5 — это довольно компактное и выразительное подмножество, которое разрабатывалось не только и не столько для промышленного программирования (хотя писать большие программы на нём можно — SCP4), сколько для автоматического анализа. Поэтому и язык первого порядка, и нет неуспехов (но есть условия), и замкнутый набор встроенных функций. Мои идеи по выводу и проверке типов хорошо ложатся на РЕФАЛ-5, в то время как с функциями высшего порядка, неуспехами и сторонними функциями всё не так очевидно.
А в чём согласование с интенцией первого порядка таких особенностей, как выражения с двусторонним доступом, концепция поля зрения и динамическая типизация? Мне это немного не очевидно. И что подразумевается под явной активацией (мне не знаком этот термин)?
Вообще, я недавно начал смотреть лекции Абрамова по метавычислениям и задумался: а каким должен быть промышленный инструмент программиста для выполнения метавычислений? Подумалось, что это должен быть язык программирования и компилятор к нему, с хорошей поддержкой рефлексии (возможность как разобрать в рантайме AST любой функции, так и наоборот, её построить из AST и тут же вызвать), с возможностью интерпретации во время компиляции (как в C++14 constexpr), с возможностью сдампить набор функций в готовый для выполнения модуль. И если в такой среде реализовать специализатор как обычную библиотечную функцию, то вполне реализуются все три проекции Футамуры-Турчина. А потом вспомнил «пятикнижие Турчина» — описанный там язык и описанная там среда вполне подходят под это описание, разве что constexpr там нету.
Функциональные объекты этим условиям не удовлетворяют, они эктенсиональны: функцию можно вызвать, но нельзя препарировать, рассмотреть ее устройство.
Да, кстати. У меня (и у Скоробогатова в Refal’е-7) функциональные объекты сопоставляются с s-переменными.
Но конечно, это не значит, что последователи не вправе делать по-своему, с опорой на новые знания и опыт. И может быть, особенности Рефала дадут возможность по новому увидеть и понять функциональные объекты.
Я разрабатывал (и разрабатываю) диалект Рефал-5λ (который сначала назывался Простой Рефал), ориентированный на промышленное программирование. Вложенные функции повышают продуктивность программиста — они есть. Необходимо расширение возможностей языка — библиотека функций не закрыта, можно написать свою функцию на Си++. Даже больше. Есть удобный синтаксис для написания таких функций — вставки кода на Си++ (https://github.com/bmstu-iu9/simple-refal/issues/11, https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/Library.sref). Т.е. не надо править и менять интерпретатор для написания ещё одной примитивной функции. Сейчас я работаю над унификацией с РЕФАЛом-5 (планирую сделать точное надмножество).
Что касается меня, как приложившего руку к созданию Рефала-6, могу только сказать, что в последние годы, уже лет 15, выступаю только как пользователь "своего" диалекта и пока вполне им доволен. Но это, конечно, не промышленное использование. Есть у Рефала-6 еще по-меньшей мере один активный пользователь - Игорь Щенков, и он время от времени высказывает претензии. Но к сожалению сил на них активно откликаться сейчас у меня очень мало. Се ля ви.
Когда я начинал программировать на Рефале, я начал с РЕФАЛа-5, пару программ написал на Рефале-6, а потом начал писать свой диалект J. Поэтому с идеями Рефала-6 знаком, программы читать могу, но программировать навыка нет, извините, что не стал вашей пользовательской базой. Кстати, завидую вам. Ваша пользовательская база по-меньшей мере в два раза больше моей J.
Александр Коновалов
Здравствуйте, Василий!
Да, Рефал жив его пользователями. Но, если уйдёт поколение пользователей, то и Рефал умрёт. Может я и ошибаюсь, но по моим наблюдениям поколение воспроизводится как-то слабо (если вообще воспроизводится).
Спасибо за ссылки. Я их пока поверхностно посмотрел, думаю, потом изучу внимательнее. А мне наоборот, проще воспринимать языки с «современным» синтаксисом: РЕФАЛ-5, Рефал-6, Рефал Плюс. А вот читать Рефал-2 я ещё не привык — глаза не привыкли к k/F/что-то. Вашу реализацию постараюсь посмотреть в свободное время (видел, что исходник целиком написан в одном файле REFAL.REF, а внутри сплошной метакод B).
Кстати, студентов я пытаюсь привлекать к Рефалу. В частности, в моей реализации уже есть исходный код нескольких курсовых и дипломных проектов (в папке https://github.com/bmstu-iu9/simple-refal/tree/master/doc и её подпапках есть несколько записок по проектам, можно почитать). Но, к сожалению, их он не особо интересует (сдали и забыли).
--
Коновалов Александр Владимирович, преподаватель
кафедра ИУ9 «Теоретическая информатика и компьютерные технологии»
МГТУ имени Н. Э. Баумана, Москва
s...@cnshb.ru
Посмотрел на Ваш, Александр, Простой Рефал...
Вы меня извините, господа, я конечно понимаю: унификация, суперкомпиляция, имена, отражающие суть...
Безусловно, меня гнетет груз привычки к рефалу/2, с которым я познакомился в конце 70-х...
Но использовать рефал в производственных условиях я начал с 1998-го, когда для ПК написал собственную версию.
Правда, я еще раньше для Turbo-C написал функцию "рефальское отождествление"...
Т.е. уже более 19 лет использования в практических задачах.
За что я его (рефал) ценю?
1) наглядность
Я использую как редактор far, раньше был Norton Commander.
Основной код программы на рефале (в метакоде B), которым занимаюсь при программировании (та часть,которую сейчас пишу), обычно помещается на экране (в окне редактора).
Не нужно никуда листать, смотреть и т.п.
В этом смысле, чем компактнее исходный код, тем лучше!!! А значит короткие односимвольные имена переменных предпочтительнее длинных-мнемонических. Чем меньше строк - тем нагляднее!!!!
В новых версиях есть внутренние функции. Безусловно, с их помощью можно спрограммировать и спецификации рефала/2 и еще много чего! НО!!!
Но они затуманивают алгоритм выполнения программы!!!
На самом деле, когда пишешь программу, каждый раз для себя доказываешь (теорему), что тот код, который пишешь, действительно решает ту задачу, которую надо решить...
3) привычка
Когда я смотрю на метакод B - я его читаю.
Когда ж "современный" синтаксис - приходится переводить... как с другого языка...
Особенно, когда несколько встроенных функций (как, например, в "декартовом произведении" п. 3.3.5.3 из
https://github.com/bmstu-iu9/simple-refal/blob/master/doc/manul.pdf )
Безусловно - красиво!
Но писать, думаю, быстрее проще, да и в случае возникновения ошибок, мне кажется, легче разбираться с простым кодом.
4) возможность программной оптимизации не обязательна!
Мне кажется, сейчас, когда ПК становятся всё быстрее и мощнее, вопрос производительности так остро не стоит!
(тем более, что вообще решили обратиться к рефалу ;) )
Я после фортрана, PL/1 и ассемблера ЕС ЭВМ долго к рефалу привыкал, а после того как уже свободно "читал" программы, "писать" начал только через полгода.
http://swi.16mb.com/
Александр Коновалов
Доброе утро, Василий, доброе утро, господа!
Я, в свою очередь, посмотрел на ваш Рефал/2: исходники и интерпретатора, и компилятора. Довольно любопытная и минималистичная реализация, по всей видимости, ориентированная на написание каких-то небольших ежедневных скриптов, для которых часто под Unix используют sed, awk, Perl. Иначе нельзя объяснить, например, зашитую на уровне дизайна языка интерпретацию параметров командной строки. Сюда же: язык не предполагает никакую модульность — исходная программа должна писаться в виде единого файла — но для небольших скриптов этого вполне достаточно.
Стандартная библиотека языка выглядит так, как будто проектировалась именно для написания такого самоприменимого компилятора, иначе я не могу объяснить наличие буфера с произвольным доступом на запись (названного в документации загадочной формулой «X+LX»), куда запись производится по смещениям и который сохраняется в файл (третий аргумент интерпретатора) по завершении работы программы.
Интересной выглядит реализация поля зрения: вместо двусвязного списка узлов с полями «тег», «информация», «вперёд», «назад», используются четыре массива со смыслом данных полей (массивы «вперёд» и «назад» содержат не указатели, а целочисленные смещения). Массив «тегов» имеет символьный тип, что позволяет экономить память, которая терялась бы на выравнивание.
Язык сборки реализует систему команд, предложенную Романенко в диссертации 1978 года. По той же схеме, на сколько мне известно, реализованы «официальный» Рефал-2 Белоуса и Рефал-5.
Исходный код выглядит как написанный в прошлом веке, когда ещё не были распространены современные практики написания сопровождаемых программ. В коде на Си относительно часто используется goto (часть из них можно объяснить ручным дословным перекодированием псевдокода из диссертации Романенко), глобальные переменные с именем из одной буквы (часть из них тоже «переехала» из диссертации, например, Г1 и Г2). Впрочем, тем же страдают и исходные тексты Рефала-5 (я их когда-то внимательно изучал).
Исходник на Рефале выглядит как шифровка: многие функции названы по схеме «буква» + «число», иногда с суффиксом, названным по той же схеме (F20, F2E0, W15, F2E_S2…). Чтобы понять смысл каждой конкретной функции, приходится искать её место вызова (в других функциях) и пытаться понять, что же ей передаётся. Однако, если внимательно читать программу от начала и до конца, то понять целиком всё можно.
«Т.е. уже более 19 лет использования в практических задачах.»
Я им пользуюсь где-то с 2005 года, но больше в теоретических задачах: пишу для него компиляторы(ы). Просто сам язык для меня интересен. Также применяю его в (около)научной работе на кафедре. Например, чудовищно интересными были оптимизации совместного сопоставления с образцом (с выводом т.н. «глобального сложнейшего обобщения») и построения результата (используя алгоритм жадного строкового замощения, используемого обычно при поиске плагиата).
«За что я его (рефал) ценю?
0) удобно производить символьные преобразования»
Полностью согласен. Может заменить и Perl с AWK’ом, перемалывающие строки текста, и Lisp, преобразующий сложные символьные конструкции (например, в задачах компиляции).
«1) наглядность
Я использую как редактор far, раньше был Norton Commander.
Основной код программы на рефале (в метакоде B), которым занимаюсь при программировании (та часть,которую сейчас пишу), обычно помещается на экране (в окне редактора).
Не нужно никуда листать, смотреть и т.п.
В этом смысле, чем компактнее исходный код, тем лучше!!! А значит короткие односимвольные имена переменных предпочтительнее длинных-мнемонических. Чем меньше строк - тем нагляднее!!!!»
Я использую как редактор Far и Vim. Причём исторически начинал с Far’а (и мне не влом было набирать длинные имена переменных без автодополнения).
С тем, что чем компактнее исходный код, тем лучше, я не согласен. Я считаю, что чем легче читается и воспринимается, тем нагляднее. Например, что делает функция F2E_K? Для ответа на этот вопрос нужно прочитать её код, а также прочитать то, как она вызывается из других функций. А что делает функция PairResultBrackets? Имя нам подсказывает, что она спаривает скобки в результатном выражении. А значит, чтобы понять, что происходит в месте её вызова, тупо не надо читать другое место. Аналогична история с переменными. Что хранится в переменной T3? Нужно посмотреть, где эта функция вызывается и что по этому параметру передаёт. А что хранится в t.NextToken? Следующий токен.
«2) спецификации
В новых версиях есть внутренние функции. Безусловно, с их помощью можно спрограммировать и спецификации рефала/2 и еще много чего! НО!!!
Но они затуманивают алгоритм выполнения программы!!!
На самом деле, когда пишешь программу, каждый раз для себя доказываешь (теорему), что тот код, который пишешь, действительно решает ту задачу, которую надо решить...»
Вообще-то вложенные функции не могут заменить спецификации Рефала-2. Заменить спецификации можно только условиями Рефала-5 или более общей конструкцией — действиями с неуспехом Рефала-6, Рефала-Плюс, Рефала-7.
То, что они затуманивают выполнение программы, я не согласен. Они наоборот её проясняют. Например, функция Map, отображающая одну последовательность термов в другую:
Map SF TN ET = kSF TN. k/Map/ SF ET.
SF =
PlusOnes EX = k/Map/ /P1/ EX.
UnBracket EX = k/Map/ /UnBracket1/ EX.
UnBracket1 (EX) = EX
PutLines EX = k/Map/ /PutLine/ EX.
PutLine (EX) = k/P/ EX.
Здесь для примера функция PlusOnes прибавляет к каждому терму единицу, UnBracket, принимая список скобочных термов, все их разворачивает, PutLines распечатывает последовательность строк. Преимущество функции Map в том, что не надо описывать обработку всей последовательности — достаточно описать обработку одного элемента и сказать «сделай со всеми так».
Вообще, вложенные функции сейчас присутствуют практически во всех распространённых языках общего назначения: Си++ (с 2011 года), Java, C#, JavaScript, Python, Ruby, Scala, Kotlin, Rust, Go. Относительно Visual Basic не в курсе, не слежу за ним. И люди этим активно пользуются. Вложенные функции стали такой же общей практикой, что и ООП.
«3) привычка
Когда я смотрю на метакод B - я его читаю.
Когда ж "современный" синтаксис - приходится переводить... как с другого языка...
Особенно, когда несколько встроенных функций (как, например, в "декартовом произведении" п. 3.3.5.3 из
https://github.com/bmstu-iu9/simple-refal/blob/master/doc/manul.pdf )
Безусловно - красиво!
Но писать, думаю, быстрее проще, да и в случае возникновения ошибок, мне кажется, легче разбираться с простым кодом.»
Исключительно вопрос привычки и практики.
«4) возможность программной оптимизации не обязательна!»
Простой Рефал самоприменяется 10 секунд, поэтому оптимизация не лишняя. Кроме того, это очень интересно (писал уже выше).
s...@cnshb.ru
Я Вами восхищаюсь! Как быстро Вы разобрались в чужом коде. Всё что Вы написали правильно.
Я действительно в мае 1998-го (прошлый век) писал "маленькую" версию для себя и под MS DOS на Turbo-C. В ней много ограничений.
Одно из них - длина предложения (на языке сборки) не более 255 иногда жмет. Приходится вводить доп.функции
Что же это за задача такая? может быть ее лучше разбить на две? ;)
Тем более, что когда я писал -мне было понятно, а уже много лет я в код не заглядывал. Есть еще сложность. Мне обычно трудно выразить смысл функции несколькими словами, которые можно записать в ее названии, а т.к. я не знаю англ., то мне это не мнемонично :(
Спасибо за пример на метакоде В.
У меня он тоже будет работать (если переменную T заменить на W). в нем нет вложенных функций.
Под вложенными функциями я из Вашего п.3.3.5.3 (стр.15-16) понял использование тела др. (вложенной) функции внутри тела "внешней" (Ваши примеры функций N1 и N2 на стр.16)
Про оптимизацию кода на языке сборки. Мне показалось, что в реальных задачах время может сократиться процентов на 10... ради этого возиться показалось лишним...
Александр Коновалов
Доброе утро, Василий!
«Другое - величина кода программы не более 32К»
Я писал большую программу на Рефале, которая не укладывалась 64 Кбайта для РЕФАЛа-5. Это компилятор Модульного Рефала (проект временно сдох):
https://github.com/Mazdaywik/mrefal
Он умеет компилировать программу из нескольких модулей, отслеживая зависимости между ними (при этом проверяется, что если модуль не менялся с момента последней перекомпиляции, и зависимые модули тоже не менялись, перекомпиляция не выполняется). Парсит свой входной диалект «Модульный Рефал», может порождать код на РЕФАЛе-5, Простом Рефале и Си++. Плюс строит таблицу перекрёстных связей между функциями. Такой вот комбайн. Ограничение на размер кода (при запуске версии, скомпилированной в РЕФАЛ-5) сейчас стоит в 300 Кбайт.
«Мне обычно трудно выразить смысл функции несколькими словами, которые можно записать в ее названии, а т.к. я не знаю англ., то мне это не мнемонично :(»
Ну это, скорее, вопрос стиля и привычки. Когда приходится писать на Базисном Рефале, то приходится вводить очень много промежуточных функций и приходится их именовать. Я обычно их именую так.
Если есть некоторая функция «Func», выполняющая роль точки входа в некий алгоритм, то служебные функции я как правило называю Func-Пояснение. «Пояснение» как-то определяется из контекста.
Если цель функции — вызвать другую функцию, а потом просто преобразовать её результат, то обычно называю такие функции как Func-Aux (auxiliary — вспомогательный).
Если вызывается промежуточная функция для выполнения цикла, то функция получает префикс Do: DoFunc (синтаксис циклов во многих языках программирования предполагает ключевое слово «do»).
Если цель функции — вызвать другую функцию и уже принять решение на основе её результата, то промежуточная функция получает префикс Sw: SwFunc или Func-SwПояснение (от слова switch — переключатель).
Вот пара примеров:
https://github.com/Mazdaywik/mrefal/blob/master/Sources/Compiler/Driver/MClusters.mref
https://github.com/Mazdaywik/mrefal/blob/master/Sources/Compiler/Driver/MCompiler.mref
Кстати, там есть пример функции с адовым числом суффиксов: «Synthesis-Recompile-Resolve-TablePrepared-Aux».
Вложенные безымянные функции избавляют от необходимости придумывать им имена. «Func-Aux» и «SwFunc» уходят за счёт того, что сразу можно написать вызываемую безымянную функцию, принимающую результат другой функции (см. функцию Fetch в руководстве). Do-функции уходят за счёт того, что многие циклы выражаются через функции Map и MapReduce (Map с состоянием).
Кстати, в вашем Рефале/2 в именах функций можно использовать любые непробельные символы (если быть точным, функции могут начинаться на любой символ, кроме «*» и не могут содержать знаки пробела и «/»). Так что по-русски тоже можно. J
Вложенные функции в Простом Рефале, кстати, являются синтаксическим сахаром. При компиляции они преобразовываются в обычные глобальные функции Базисного Рефала + операции связывания с заимствованными переменными. Об этом есть в немного устаревшей презентации по устройству Простого Рефала (сейчас устройство стало гораздо сложнее, но общие принципы в основе те же):
https://github.com/bmstu-iu9/simple-refal/blob/master/doc/historical/%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%20%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B3%D0%BE%20%D0%A0%D0%B5%D1%84%D0%B0%D0%BB%D0%B0.pdf
В принципе, вложенные функции можно добавить и в Рефал-2 по аналогии с конструкцией «where» языка Хаскель (Хаскель своим синтаксисом немного близок к Рефалу-2). Правда, тогда синтаксис станет двумерным — нужно будет учитывать величину отступа в начале строки (сейчас только учитывается «пробел/не пробел» начале):
CartProd (EA) (EB) = k/Map/ /ByA/ EA.
WHERE ByA WA = k/Map/ /ByB/ EB.
WHERE ByB WB = (WA WB)
Вложенная функция ByA заимствует из своего окружения переменную EB (её нет в её левой части, но есть в правой). Функция ByB заимствует из своего окружения WA.
Вот реальный пример, как можно переписать программу с использованием WHERE-конструкции.
F4 SLSRST('('E2)E3=(/1/K/RDR//^СКОБ/.)K/F4/STK/P1/ST.K/P2/ST.E2.+
(/3/K/RDR//^УГР/.K/P1/ST.SR)K/F4/K/P1/ST.SRK/^T/.E3.
SLSRST('0'E2)E3=(K/F4OZ/K/RDR//^ЗНАЧО/.K/LENGW/E2..)+
K/F4/K/P1/ST.SRK/P2/ST.E3.
SLSRST('4'E2)E3=(/4/K/RDR//^ЗНАЧ/./4/K/F4D//0/E2.)+
K/F4/STSRK/P1/ST.E3.
SLSRST('2'E2)E3=(/2/K/RDR//^ЗНАЧ/./2/)(/0/E2)+
K/F4/STSRK/P1/ST.E3.
SLSRST('S'E2)E3=K/F4S/ST('S'E2)K/^ИД/..K/F4/STSRK/P1/ST.E3.
SLSRST('W'E2)E3=(K/F4W/K/P1/ST.('W'E2)K/^ИД/..)+
K/F4/K/P1/ST.SRK/P2/ST.E3.
SLSRST(S('EV')1E2)=K/F4E/K/P1/ST.(S1E2)K/^ИД/..K/^T/K/P2/ST..
SLSRST=(/1/K/RDR//^ПРОВ/.)K/^T/ST.
SLSRST(S('EV')1E2)E3=K/E/SLSRST(S1E2)E3.
F4 SLSRSTW2E3=k/SwW2/W2.
WHERE SwW2 ('('E2)=(/1/K/RDR//^СКОБ/.)+
K/F4/STK/P1/ST.K/P2/ST.E2.+
(/3/K/RDR//^УГР/.K/P1/ST.SR)+
K/F4/K/P1/ST.SRK/^T/.E3.
('0'E2)=(K/F4OZ/K/RDR//^ЗНАЧО/.K/LENGW/E2..)+
K/F4pair/.
('4'E2)=(/4/K/RDR//^ЗНАЧ/./4/K/F4D//0/E2.)+
K/F4sym/.
('2'E2)=(/2/K/RDR//^ЗНАЧ/./2/)(/0/E2)+
K/F4sym/.
('S'E2)=K/F4S/ST('S'E2)K/^ИД/..+
K/F4sym/.
('W'E2)=(K/F4W/K/P1/ST.('W'E2)K/^ИД/..)+
K/F4pair/.
(S('EV')1E2)=k/SwEmptyE/ E3.
WHERE SwEmptyE =K/F4E/K/P1/ST.(S1E2)K/^ИД/..K/^T/K/P2/ST..
E3=K/E/SLSRST(S1E2)E3.
F4sym =K/F4/STSRK/P1/ST.E3.
F4pair =K/F4/K/P1/ST.SRK/P2/ST.E3.
SLSRST=(/1/K/RDR//^ПРОВ/.)K/^T/ST.
Здесь функция SwW2 проверяет, чем является очередной терм, и, в зависимости от этого выбирает дальнейший путь. Функции F4sym и F4pair вызывают F4 для продолжения разбора остатка, увеличивая вершину стека ST на 1 или на 2. Но это, наверное, несколько надуманный пример.
Да, после введения этой where-конструкции Рефал-2 перестанет быть метакодом B. Вернее даже, вообще перестанет быть метакодом по определению метакода.
«Про оптимизацию кода на языке сборки. Мне показалось, что в реальных задачах время может сократиться процентов на 10... ради этого возиться показалось лишним...»
Не, ускорение, вроде, больше чем на 10 процентов суммарное. Но вообще оптимизация затеивалась только потому, что её делать было интересно.
Arkady Klimov
Добрый день, Аркадий!
Большое спасибо за развёрнутый ответ. Сейчас я задам несколько развёрнутых вопросов. Заранее прощу прощения у подписчиков за многабукаф.
… а именно, с включением вложенных анонимных функций -- аналога лямбда-абстракции.…
Эта идея не моя, впервые она была предложена Сергеем Скоробогатовым в диалекте Refal-7 в 2006 году:
https://waybackmachine.org/web/20070813011422/http://iu9.bmstu.ru/science/refal.pdf
(даю ссылку на Wayback Machine, поскольку с сайта кафедры этот файл удалили). Вероятно, вы знакомы с ним (и со Скоробогатовым, и с диалектом), но ссылку я даю для всех читателей рассылки.
…(только поверхностно посмотрел доки)…
Основная дока (manul.pdf), к сожалению, (а) недописана, (б) частично неактуальна. Основной массив знаний (если углубляться) скрывается тут: https://github.com/bmstu-iu9/simple-refal/issues (включая закрытые задачи). Но на беглый просмотр там слишком много.
…было бы интересно и важно наработать множество примеров и техник с использованием этих новых средств, демонстрирующих их удобство и преимущество.
Пользуюсь вложенными функциями уже с 2009 года, мне нравится. Когда добавил их в язык, почувствовал прирост своей производительности, по сравнению с подмножеством Базисного Рефала. Пример их использования (несколько извращённый) вот:
https://github.com/bmstu-iu9/simple-refal/tree/master/doc/examples/inifile
Более нормальные примеры использования есть в исходных текстах самого компилятора.
Есть основания полагать, что Рефал создавался Турчиным именно как язык первого порядка, и в этом была интенция автора. … Рефал-5 -- это максимум того, что он был готов допустить.
Есть у меня идеи по статической типизации Рефала (но о них сейчас пока рано, через несколько месяцев будет в самый раз), и обдумывая их, я понял гений Турчина. РЕФАЛ-5 — это довольно компактное и выразительное подмножество, которое разрабатывалось не только и не столько для промышленного программирования (хотя писать большие программы на нём можно — SCP4), сколько для автоматического анализа. Поэтому и язык первого порядка, и нет неуспехов (но есть условия), и замкнутый набор встроенных функций. Мои идеи по выводу и проверке типов хорошо ложатся на РЕФАЛ-5, в то время как с функциями высшего порядка, неуспехами и сторонними функциями всё не так очевидно.
А в чём согласование с интенцией первого порядка таких особенностей, как выражения с двусторонним доступом, концепция поля зрения и динамическая типизация? Мне это немного не очевидно. И что подразумевается под явной активацией (мне не знаком этот термин)?
Вообще, я недавно начал смотреть лекции Абрамова по метавычислениям и задумался: а каким должен быть промышленный инструмент программиста для выполнения метавычислений? Подумалось, что это должен быть язык программирования и компилятор к нему, с хорошей поддержкой рефлексии (возможность как разобрать в рантайме AST любой функции, так и наоборот, её построить из AST и тут же вызвать), с возможностью интерпретации во время компиляции (как в C++14 constexpr), с возможностью сдампить набор функций в готовый для выполнения модуль. И если в такой среде реализовать специализатор как обычную библиотечную функцию, то вполне реализуются все три проекции Футамуры-Турчина. А потом вспомнил «пятикнижие Турчина» — описанный там язык и описанная там среда вполне подходят под это описание, разве что constexpr там нету.
Функциональные объекты этим условиям не удовлетворяют, они эктенсиональны: функцию можно вызвать, но нельзя препарировать, рассмотреть ее устройство.
Да, кстати. У меня (и у Скоробогатова в Refal’е-7) функциональные объекты сопоставляются с s-переменными.
Но конечно, это не значит, что последователи не вправе делать по-своему, с опорой на новые знания и опыт. И может быть, особенности Рефала дадут возможность по новому увидеть и понять функциональные объекты.
Я разрабатывал (и разрабатываю) диалект Рефал-5λ (который сначала назывался Простой Рефал), ориентированный на промышленное программирование. Вложенные функции повышают продуктивность программиста — они есть. Необходимо расширение возможностей языка — библиотека функций не закрыта, можно написать свою функцию на Си++. Даже больше. Есть удобный синтаксис для написания таких функций — вставки кода на Си++ (https://github.com/bmstu-iu9/simple-refal/issues/11, https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/Library.sref). Т.е. не надо править и менять интерпретатор для написания ещё одной примитивной функции. Сейчас я работаю над унификацией с РЕФАЛом-5 (планирую сделать точное надмножество).
Что касается меня, как приложившего руку к созданию Рефала-6, могу только сказать, что в последние годы, уже лет 15, выступаю только как пользователь "своего" диалекта и пока вполне им доволен. Но это, конечно, не промышленное использование. Есть у Рефала-6 еще по-меньшей мере один активный пользователь - Игорь Щенков, и он время от времени высказывает претензии. Но к сожалению сил на них активно откликаться сейчас у меня очень мало. Се ля ви.
Когда я начинал программировать на Рефале, я начал с РЕФАЛа-5, пару программ написал на Рефале-6, а потом начал писать свой диалект J. Поэтому с идеями Рефала-6 знаком, программы читать могу, но программировать навыка нет, извините, что не стал вашей пользовательской базой. Кстати, завидую вам. Ваша пользовательская база по-меньшей мере в два раза больше моей J.
Александр Коновалов
Добрый вечер, Аркадий!
Большое спасибо за ответы на мои вопросы.
«Насколько я понял, там у него вложенные именованные функции, а у Вас только анонимные, да? И отсутствие именованных для случая рекурсивных функций вы компенсируете использованием комбинатора Y. Это действительно очень круто и интересно.»
У меня только анонимные, и это, отчасти, вытекает из ограничения промежуточного представления. Используется классическая списковая реализация (как в Рефале-2 или Рефале-5), а замыкания реализованы как объекты (кольца двусвязного списка) со счётчиком связей. Некоторое представление можно извлечь из этой презентации (некоторые детали в ней уже устарели, но общая идеология осталась прежней), последние два слайда:
https://github.com/bmstu-iu9/simple-refal/blob/master/doc/historical/%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%20%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B3%D0%BE%20%D0%A0%D0%B5%D1%84%D0%B0%D0%BB%D0%B0.pdf
Именованные вложенные функции позволят программисту писать рекурсивные и взаиморекурсивные функции, которые смогут возвращать ссылку на себя (своё имя, которое тоже будет замыканием). Например:
Foo {
t.A t.B
= $func F { = &G; 0 = t.A }
$func G { = &F; 0 = t.B }
: s.X s.Y = s.X;
}
Bar {
1 = <Foo 'xy'> : s.1 = <Eq s.1 <<s.1>>>;
2 = <Foo 'xy'> <Foo 'ab'> : s.1 s.2 = <Eq s.1 s.2>;
}
Eq {
s.A s.A = True;
s.A s.B = False;
}
С моей точки зрения вызов <Bar 1> должен возвращать True, поскольку в функции Eq сравнивается с самим собой один и тот же объект. В то же время <Bar 2> обязательно должен возвращать False, поскольку сравниваются на равенство два разных объекта, созданных в разное время, по разному себя ведущих.
Вот. Реализовать именованные взаиморекурсивные функции с подобными требованиями к равенству экземпляров замыкания и при этом поверх списковой реализации со счётчиком ссылок я не придумал как. Если разрешать циклические связи во время выполнения, то уже нужно делать сборку мусора. Технически, конечно, не сложно (я писал сборщики мусора), но как-то не хочется вводить лишних сущностей. Поэтому для простоты реализации только анонимные.
Комбинатором Y я не компенсирую. Я его когда-то давно написал из любопытства и положил в библиотеку, но с тех пор не пользовался. Компенсирую я функциями Map и MapReduce (ну, иногда — Reduce) — они реально заменяют циклы. А там, где их не достаточно, использую обычную рекурсию.
«Это интересно. Когда-то я тоже думал о выводе статитческих типов типов, но до реализации руки не дошли.»
У меня два студента должны опробовать два подхода статической типизации РЕФАЛа-5: один на курсовом, второй на дипломе. Если у них что-то получится, то напишу в рассылку. Кстати, РЕФАЛ-5 идеальный для этого модельный объект (о чём писал в прошлом письме).
«Да, это неочевидная, может даже спорная мысль. Я имел в виду, что в соответствие с интенцией первого порядка хорошо, когда все объекты могут иметь образы на бумаге, а еще лучше, когда объект можно отождествить с его образом. А на бумаге мы обычно пишем тексты, которые имеют начало и конец, могут содержать вложенные структуры, то есть быть деревом. И обрабатывать такие структуры уместно с любого конца. А когда всякий объект тождествен своему текстовому структурному образу, естественно говорить о динамической типизации, а не о статической (статический тип это что-то дополнительное к объекту, а динамический он тут же в образе представлен). Концепция поля зрения - это полный образ всей переменной части состояния рефал машины, для обычных языков это стек фреймов или даже что-то более сложное и не имеющее явного "бумажного" образа.
Явная активация это такая нотация, при которой вызов функции синтаксически отличается от терма, содержащего символ функции и параметры, и который можно активировать позже. Насколько я понимаю, этим рефал отличается от лиспа, где терм (F x y) в одном контексте интерпретируется как вызов функции F, а в другом (под Quote) как пассивный список из трех элементов. Явная активация в каком-то смысле тоже "вытекает" из принципа тождественности объекта его образу (что вижу, то и имею, ничего лишнего или подразумеваемого).»
Большое спасибо, теперь всё стало на свои места.
«Да, надо "всего лишь" уметь извлекать функции из поля памяти в метакоде и класть обратно. Между прочим, в рефале-6 для этого почти все есть, надо только чуток модифицировать (и перекомпилировать) компилятор (чтобы представление в метакоде оставалось где-то в конце выражения, являющегося кодом языка сборки). Проблема лишь в том, чтобы договориться о формате метакода, а на это не хватило духу.»
Или другой вариант: написать декомпилятор языка сборки «на лету». Я как-то изучал формат языка сборки РЕФАЛа-5 методом обратного инжиниринга (о диссертации Романенко я не знал, в исходники не лез из спортивного интереса), и мне показалось, что реконструировать исходный текст по нему было бы не сложно. До декомпилятора, правда, руки не дошли.
«Да, наверно это правильно. А функция TYPE их как-то выделяет?»
Не, не выделяет. И это скорее бага, чем фича (хотя в документации на стр. 21 об этом написано). Создал баг: https://github.com/bmstu-iu9/simple-refal/issues/103. Хотя там по факту добавить одну ветку в switch: https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/Library.sref#L934-L979.
«А замыкание, это наверно уже не символ, а скобочный терм, да?»
Не, символ. Символ содержит указатель на кольцевой список, содержащий указатель на глобальную функцию и набор связанных переменных. Об этом есть в презентации по ссылке выше на страницах 6, 11–13, 35–36. В принципе, их можно рассматривать и как своего рода скобочный терм, который, однако, нельзя расщепить образцом.
«И в пользу коротких есть следующий аргумент: Рефал, в отличии от классических императивных языков является двумерным: предложение естественно пишется в строку, а группа предложений в столбец.»
Соглашусь, что это вопрос вкуса. Я, например, принципиально избегаю вертикального выравнивания в своих программах. Основная причина: низкая сопровождаемость. Если приходится изменить текст в одной из «ячеек», и при этом он оказывается шире ширины столбца, то приходится подгонять строки выше и ниже. Или, например, массово переименовал какое-нибудь имя (идентификатор или имя функции) и все «таблицы», где он был, поехали. Во-вторых, я предпочитаю ограничивать длину строки 80 символами (удобно бить окно редактора по вертикали пополам), а выравнивание текста в виде таблицы часто приводит к длинным строкам, причём, если длинную строку разбить на две, то теряется красота таблицы.
Но, опять-таки, это дело вкуса.
Кроме того, я никогда не программировал с использованием коротких имён переменных, всегда писал длинные. Обсуждение с Василием Стеллецким и вами натолкнуло на мысль, что мой стиль может быть не идеальным. В частности, вполне, оказывается, можно читать программы на Рефале-2 с односимвольными именами. Надо будет попробовать писать иначе.
--
Александр Коновалов aka Маздайщик
Boyko Bantchev
> Именованные вложенные функции позволят программисту писать
На мой взгляд, большинство, если не почти все случаи, когда кажется,
что нужны именованные функции для рекурсии или взаимной рекурсии,
исчезают, если позволить любой функции цитировать себя и охватывающую
функцию при помощи предназначенной именно для этого стандартной пары
знаков или имен. Почему такое средство отсутствует почти во всех
ЯП, мне уже много лет совершенно непонятно.
(А применима ли эта идея конкретно к вашей реализации я не знаю,
так как следил посты поверхностно.)
Еще вметка. Взглянув на ваши слайды, заметил несколько конструкций
вида
typedef struct Node *NodePtr;
typedef struct Node { T data; Node* next; } Node;
На C++ нет потребности писать таким усложненным образом, поскольку
struct Node { T data; Node* next; };
вполне хорошо работает. (И вообще, везде в программе Node
равнозначно struct Node — создавать синоним не приходится.)
Бойко Банчев
Александр Коновалов
Спасибо за интересные замечания!
Вы не могли бы пояснить, что вы имеете ввиду под «цитированием себя и охватывающей функции при помощи … стандартной пары знаков или имён»? Просто мне не очень понятна ваша терминология. И, если не сложно, приведите, пожалуйста, пример, используя какой-нибудь псевдокод (не обязательно Рефала).
Рантайм я писал достаточно давно, как и давно писал презентацию. Зачем писал эти избыточные конструкции? Мне они тогда нравились почему-то, потому и писал. В текущей версии исходников их уже нет:
https://github.com/bmstu-iu9/simple-refal/blob/master/src/srlib/refalrts.h
Руки дошли удалить их примерно год назад:
https://github.com/bmstu-iu9/simple-refal/commit/da7867
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Thursday, August 3, 2017 4:41 PM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Boyko Bantchev
> Вы не могли бы пояснить, что вы имеете ввиду под «цитированием
> себя и охватывающей функции при помощи … стандартной пары знаков
> или имён»?
себя через какое-то фиксированное, универсальное для этой роли имя.
Ну, или передавать свой адрес кому-то еще. Подобно местоимениям «я»
или «себя»/«себе» в человеческой речи — человек говорит о себе, не
нуждаясь в имени. Местоимение одно и то же, но относится к разным
людям в зависимости от того, кто говорит. Конкретный синтаксис
неважен.
Один из совсем немногих языков, где это имеется — это JavaScript.
Дам пример на нем.
В этом языке у каждой функций имеется (составная) переменная
arguments, а у arguments имеется часть callee. Так вот,
arguments.callee — это то, о чем я говорю. В результате можно
написать, скажем, анонимный рекурсивный факториал:
function(n) {return n<2 ? 1 : n*arguments.callee(n-1)}
и вызвать его можно так:
(function(n) {return n<2 ? 1 : n*arguments.callee(n-1)})(5)
(или передать кому-нибудь как значение, а вызывать будет уже он сам).
Еще пример: обращение связанного списка функцией reverse.
reverse создает вложенную функцию с двумя аргументами (из первого
она накапливает результат во второй) и тут же ее вызывает. Вложенная
функция рекурсивна и анонимна.
function reverse(x) {
return (function(x,y) {
if (x) {
var r = x
x = x.next
r.next = y
return arguments.callee(x,r)
}
return y
})(x,null)
}
(А список может быть, скажем, такой:
list = {data:1}
list = {data:2, next:list}
list = {data:3, next:list}
)
Иногда полезно подобным стандартным анонимным образом вызывать и
охватывающую функцию, возможно даже и ту, которая, в свою очередь,
ее охватывает — это позволяет уже взаимную анонимную рекурсию, но
таких средств ни в JavaScript, ни в других языках не видел. (Сам
я такое свойство вложил в своем полуреализованном языке, но миру
от этого мало пользы :) )
Бойко
Александр Коновалов
Понял вашу мысль. Вы фактически предлагаете аналог указателя «this» (или «self») применительно к безымянным функциям. Идея интересная, но у меня затык не с синтаксической конструкцией, а с представлением во время выполнения. Хоть с именами, хоть с this’ом взаимная рекурсия с возвратом указателя неизбежно конфликтует (а) с требованиями к равенству двух указателей на функцию, (б) с использованием простого счётчика ссылок для управления памятью.
Почему нет такой конструкции в большинстве языков программирования? Во-первых, инертность мышления (а что, и так тоже можно?), во-вторых, нужна редко. Обычно ко вложенной безымянной функции относятся не как к функции, а как к блоку кода, который воспринимается как некий фрагмент устойчивой конструкции, функции map, играющей роль цикла. Вложенные безымянные функции обычно небольшие и играют роль части выражения. Если нужно выразить более сложную логику, то её оформляют как отдельную функцию, которой уже логично дать соответствующее имя (независимо от наличия рекурсии внутри). Вообще, лучший способ прокомментировать блок кода — не писать комментарий перед ним, а вынести его в отдельную функцию и дать ей ясное понятное название.
Не могу не поделиться одной историей. В этом году я разрешил студентам сдавать лабораторные на необычных языка программирования, при этом одна лабораторная засчитывалась за три. Среди таких языков был Smalltalk. Порог вхождения у него низкий: посмотрев на примеры кода и найдя документацию по стандартной библиотеке, уже можно писать немаленькие (сотни строк кода) работающие программы. При этом вникать в устройство языка не обязательно.
Так вот. «Условный оператор» в Smalltalk выглядит так: (x < y) ifTrue: […] ifFalse: […]., «цикл» — [x < y] whileTrue: […].. Так вот. Это не условный оператор и не цикл. Текст в квадратных скобках — это не блок кода (как {…} в C++), а лямбда. Безымянная функция (вернее, безымянный класс с методом call, если я ничего не путаю). Булевский класс имеет двух потомков, соответственно, True и False. У первого метод ifTrue: f1 ifFalse f2. выполняет замыкание f1, у второго — f2. У самого класса замыкания, помимо метода call, есть метод whileTrue: func., который вычисляет себя и свой аргумент в цикле, пока сам себе возвращает значение True.
А значит, вместо (x < y) ifTrue: […] ifFalse: [……]. можно написать: f1 := […]. f2 := [……]. (x < y) ifTrue: f1 ifFalse f2. Аналогично с «циклом» whileTrue: f3 := [x < y]. f4 := […]. f3 whileTrue: f4..
Когда я это объяснял студентам (и делал замены из предыдущего абзаца), только что написавшим (и правильно написавшим) лабораторную, они удивлялись. Оказывалось, что в языке нет управляющих конструкций кроме создания блока, вызова метода и ^ (так обозначается возврат из метода). Ветвление и цикл — методы библиотечных классов.
Это я рассказал к тому, что безымянные функции вкупе с функциями стандартной библиотеки (map, fold, filter и другие) воспринимаются как цельные синтаксические конструкции, фактически, как встроенные операторы языка. Помимо Smalltalk’а (а он позиционируется как объектно-ориентированный, а не функциональный), могучая синтаксическая поддержка таких конструкций есть в Ruby и Kotlin’е (не программировал, могу что-то путать ошибаться). В последнем, например, если функция/метод принимает последним аргументом функцию, то её можно записывать как просто блок в фигурных скобках _вне_ круглых скобок: вместо foo(x, y, {…}) можно писать foo(x, y) {…}. Если аргумент единственный — скобки не нужны: foo({…}) эквивалентно foo {…}. Что и позволяет писать конструкции, выглядящие почти как нативные синтаксические конструкции (типа if(…) {…}).
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Friday, August 4, 2017 10:28 AM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Boyko Bantchev
> Почему нет такой конструкции в большинстве языков программирования? Во-первых, инертность мышления (а что, и так тоже можно?), во-вторых, нужна редко. Обычно ко вложенной безымянной функции относятся не как к функции, а как к блоку кода, который воспринимается как некий фрагмент устойчивой конструкции, функции map, играющей роль цикла. Вложенные безымянные функции обычно небольшие и играют роль части выражения. Если нужно выразить более сложную логику, то её оформляют как отдельную функцию, которой уже логично дать соответствующее имя (независимо от наличия рекурсии внутри). Вообще, лучший способ прокомментировать блок кода — не писать комментарий перед ним, а вынести его в отдельную функцию и дать ей ясное понятное название.
отношениях я другого мнения, или, по крайней мере, не разделяю
стремление абсолютизировать утверждения.
Вот, например, в истинности утверждения
«лучший способ прокомментировать блок кода — не писать комментарий
я очень сомневаюсь. Названия помогают понять смысл только в том
случае, когда этот смысл настолько простой, что его можно передать
буквально одним словом. Во всех остальных случаях имя функции, даже
самое удачное, никак нельзя считать «лучшим способом комментирования».
Если вообще комментировать, то придется подробнее, другими способами.
Но к этой дилемме вопрос, какое у функции название и есть ли вообще
оно у нее, не очень относится.
Более того, вы пишете, что возможность самоцитирования (и цитирования
охватывающей функции) для безымянных функций «нужна редко». С этим
тоже не могу согласиться. В своем утверждении вы исходите из своих
же представлений о роли и использовании функций. Они, конечно, не
лишены основания, но мне кажутся несколько размытыми. Что есть
«фрагмент», который не функция в функциональном языке? Какая именно
логика является «более сложной»? По какому критерию «логично»
закреплять имя за функцией как часть ее реализации (а не только
интерфейса — ведь когда имя рекурсивной функции цитируется в ее теле
это касается реализации)? На такие вопросы, полагаю, ответить можно
по-разному, поэтому и выводы будут неоднозначными.
(Впрочем, по поводу утверждения «нужна редко», вспомнил о цикле со
след-условием (do-while или repeat-until). Он часто используется?
Судя по моей практике, крайне редко. Тем не менее, он есть в почти
всех императивных языках. А зачем нужен while в языке C и подобных,
когда он — всего лишь частный случай for, с тяжелыми ограничениями?
Насколько часто нужно написать цикл без ни вводной, ни обновляющей
частей? По-моему, очень редко. Но и эта конструкция присутствует
практически везде в императивных языках.)
Вообще, выдвинутые вами соображения насчет именования я считаю
частично справедливыми, но кроме них имеются и другие.
Свои соображения в пользу возможности _не_именования любых функций,
в т.ч. рекурсивных, я разделяю на две группы — принципиальные и
практические.
Принципиально в языке, в котором функции являются значениями —
это не требовать именовать функции, так как нет такого требования
и в отношении других видов значений. Ведь формирование значения —
числа, строки, булевого или же функции, при помощи подходящего
выражения — это одно дело, а именование ;— другое. Присваивать имя
значению — возможность для программиста, а выбор именовать или нет
должен быть за ним, а не навязывать ему что делать.
Также принципиальным является отличие функции, которая является
значением, от функции с закрепленным в ее теле ее же именем. Тело
первой функции можно подставить везде, где требуется ее значение
(для вызова или другой цели) — отсюда, в частности, вытекает удобство
механических манипуляций с программой — а со второй так сделать
невозможно. Уместно ли обязательно ставить функцию во второй,
ограниченный класс, только потому что она рекурсивная?
В плане практическом, возьмем такую ситуацию. Часто бывает так, что
вызов рекурсивной функции ее пользователем отличается от самовызова —
например, из-за того, что при первом вызове нужно что-то сделать один
раз: как правило, установить какие-то начальные значения. Но чаще
всего, вызываемой функции нечем отличить первый вызов от самовызовов,
а даже если это возможно, то невыгодно проверять каждый раз.
Это противоречие устраняется вложением в основную функцию
«вспомогательной», которая на самом деле выполняет работу по существу
и, в частности, самовызывается рекурсивно. «Основная» же функция
только подготавливает начальные параметры к ее работе и, возможно,
как-то изменяет результат до того как передать его пользователю.
(Второй данный мной раньше пример (с обращением списка) — именно
такой случай.) Но тогда получается так, что вложенную функцию мы
именуем только для того, чтобы она могла себя вызывать; имя ее
пользователю основной функции не нужно. А может быть и так, что
основная и вложенная функции вызываются взаимнорекурсивно. В любом
случае нет причины _требовать_ именовать вложенную функцию, ее имя
несущественно — пусть программист сам решит, стоит ли.
Если, вдобавок, вложенная вызывает внешнюю не через фиксированное
имя, а именно как свою охватывающую, то удаляется ненужная связанность
реализаций обеих функций через имена: имя каждой можно изменять, не
трогая реализацию другой; а вложенную функцию можно даже скопировать
в другое подходящее окружение, не изменяя ничего в ней, в частности —
интерфейс к «родителю».
Я не случайно указал на аналогию с местоимениями в естественных
языках – ими тоже пользуются не из каприза, а потому что так разумнее.
Похожие взаимосвязи возникают и в программах, и мне кажется полезным
не пренебрегать этим фактом, а воспользоваться для улучшения их
структуры.
Что касается блоков в Smalltalk-е (и перенятых из него в Ruby):
как подобия безымянных функций они безусловно полезны, но не есть
полноценные функции, так как не являются замыканиями, и даже
значениями являются только в ограниченном смысле. Конечно, эта
ограниченность в ряде случаев и не мешает.
Александр Коновалов
Спасибо за ценные, интересные аргументы.
К теме комментирования.
Вообще, моя точка зрения, что если что-то можно выразить в коде (функции, имена переменных, типы и их имена), то комментарии не нужны. Комментарии нужны для объяснения вещей на уровень выше самого кода: например, реализуется согласно такому-то RFC, то, что ниже явный баг сохраняется для совместимости со старой версией другого ПО, то, что что-то описано слишком низкоуровнево ради оптимизации (скажем, вместо использования библиотеки regexp’ов написан ручной анализ некоторой строки). Если нужно объяснить непонятный код — значит написан говнокод, требующий переписывания с нуля. Или рефакторинг. На этом предлагаю закрыть тему комментариев или продолжить её в «личке».
> Более того, вы пишете, что возможность самоцитирования (и цитирования охватывающей функции) для безымянных функций «нужна редко»…
В предыдущем письме вы привели пример кода на JavaScript, тем самым подтолкнув меня в сторону императивной парадигмы. А там рекурсия бывает редко, а значит, раз потребовалось рекурсия, значит задача достаточно сложна, циклами её не решить. И для подобной задачи имеет смысл реализовывать именно именованную функцию (иначе может быть вообще не понятно). В рамках функциональной парадигмы, где циклов нет, действительно, напрягает именовать каждую функцию, которая по смыслу эквивалента while или for.
> Впрочем, по поводу утверждения «нужна редко», вспомнил о цикле со след-условием (do-while или repeat-until). Он часто используется?…
(В Python’е, кстати, его нет. Именно потому, что он используется редко — это следует из идеологии языка. Но это отступление.)
> А зачем нужен while в языке C и подобных, когда он — всего лишь частный случай for, с тяжелыми ограничениями?
> Насколько часто нужно написать цикл без ни вводной, ни обновляющей частей? По-моему, очень редко.
Рантайм компилятора Простого Рефала и стандартная библиотека:
>git grep -w for | bash -c "wc -l"
45
>git grep -w while | bash -c "wc -l"
28
Коммерческий проект, над которым я тружусь на второй работе (я не только преподаю):
>git grep -w for *.[ch] | bash -c "wc -l"
509
>git grep -w while *.[ch] | bash -c "wc -l"
183
Поиск осуществлялся только по исходникам *.h и *.c.
Интерпретатор Рефала/2 Стеллецкого — while не используется, for используется так:
>git grep -w for
refalb.cpp: for(;;)
refalb.cpp: for(i=0;i<j;i++) if(fputc(X[LX+2000+i],F)==EOF) goto labew;
swfmk.c: for(i=LX;;i++)
swfmk.c: for(i=LX;;i++)
swfmk.c: for(i=LX;cc!=REFTM.next1;i++,cc=sl(cc)) X[i]=(char) par(cc);
swfmk.c: for(i=LX;cc!=REFTM.next1;i++,cc=sl(cc)) X[i]=(char) par(cc);
swfmk.c: for(cc=sl(i);cc!=REFTM.next1;cc=sl(cc),j++) X[LX+2000+j]=(char) par(cc);
swfmk.c: for(;G0!=REFTM.gkop;)
swfmk.c: for(i=sl(REFTM.prev1),cc=sl(G0);i!=REFTM.next1;i=sl(i),cc=sl(cc))
swfmk.c: for(;G0!=REFTM.gkop;)
swfmk.c: for(i=sl(REFTM.prev1),cc=sl(G0);i!=REFTM.next1;i=sl(i),cc=sl(cc))
swfmk.c: {for(cc=sl(cc);cc!=G2;cc=sl(cc))
swfmk.c: for(i=sl(REFTM.prev1);i!=REFTM.next1;i=sl(i))
swfmk.c: for(i=0;s[i]!=0;i++)
swfmk.c: for(cc=sl(j);cc!=j;cc=sl(cc))
swfysb.c: for(i=0;i<arg;i++)
swfysb.c: for(i=arg;i>0;i--)
swfysb.c: for(;;)
swfysb.c: for(;;)
swfysb.c: {for(k=spG1;k!=sl(spG2);k=sl(k))
swfysb.c: for(cc=0,i=0;i<j;i++)
swfysb.c: for(k=0;k<arg;k++)
swfysb.c: for(;pr(ast)!=TE[arg];ast=sl(ast))
swrefmf.cpp: {for(i=a;i!=sl(b);i=sl(i))
swrefmf.cpp: {for(i=a,n=0;i!=sl(b) && n<c;i=sl(i),n++)
swrefmf.cpp: for(i=4+1;i<n+4;i++) sv(i-1,i)
swrefmf.cpp: for(;;REFTM.nsh++)
Обнаружилась пара циклов while, записанных как for(;…;) и пара бесконечных циклов. А ещё в исходниках можно найти один цикл на goto :-).
Исходные тексты компилятора и интерпретатора языка Рефал-5:
>git grep -e "for\s*(" | bash -c "wc -l"
235
>git grep -e "while\s*(" | bash -c "wc -l"
151
Здесь использовал более хитрый шаблон поиска, поскольку предлог for часто используется в комментариях, написанных по-английски. В других проектах такой проблемы нет.
Цикл while применяется реже, но не «очень редко», 38 % в одном проекте, 26 % в другом, в третьем вообще нет, в четвёртом 39 %. Видно, что зависит от стиля программирования, но используется, по-моему, достаточно часто. Для других языков программирования статистика может быть и иной.
> Принципиально в языке, в котором функции являются значениями — это не требовать именовать функции, так как нет такого требования и в отношении других видов значений. Ведь формирование значения — числа, строки, булевого или же функции, при помощи подходящего выражения — это одно дело, а именование ;— другое. Присваивать имя значению — возможность для программиста, а выбор именовать или нет должен быть за ним, а не навязывать ему что делать.
> Также принципиальным является отличие функции, которая является значением, от функции с закрепленным в ее теле ее же именем. Тело первой функции можно подставить везде, где требуется ее значение (для вызова или другой цели) — отсюда, в частности, вытекает удобство механических манипуляций с программой — а со второй так сделать невозможно. Уместно ли обязательно ставить функцию во второй, ограниченный класс, только потому что она рекурсивная?
* Создать области видимости для меток. Например, ограничить область видимости подпрограммой или файлом.
* Ввести «локальные» метки. Такая метка может повторяться в программе несколько раз, но goto на неё связывается с ближайшей по тексту. Такое практикуется в синтаксисе некоторых ассемблеров.
* Ввести конструкцию, не требующую именованной метки: структурный цикл, подразумевающий в конце переход в начало, замаскированные goto, связываемые с ближайшим окружающим циклом — break и continue. К слову, развитием этой мысли являются break и continue с метками, например, в Java.
Фактически, вы предлагаете конструкцию, аналогичную continue, но для рекурсии (аналог break уже есть, называется return).
> В плане практическом, возьмем такую ситуацию. Часто бывает так, что вызов рекурсивной функции ее пользователем отличается от самовызова — например, из-за того, что при первом вызове нужно что-то сделать один
раз: как правило, установить какие-то начальные значения. Но чаще всего, вызываемой функции нечем отличить первый вызов от самовызовов, а даже если это возможно, то невыгодно проверять каждый раз.
> Это противоречие устраняется вложением в основную функцию «вспомогательной», которая на самом деле выполняет работу по существу и, в частности, самовызывается рекурсивно. «Основная» же функция только подготавливает начальные параметры к ее работе и, возможно, как-то изменяет результат до того как передать его пользователю.
Если бы я программировал на Рефале с именованными вложенными функциями, и там бы мне потребовался бы цикл, то я написал бы: $func Loop { …… }. А внутри функции вызывал бы <Loop …>. Для дважды вложенных функций использовал бы имена вроде Loop-ЧтоТоОдно, Loop-ЧтоТоДругое. Сейчас подумываю о соответствующих ключевых словах, например <$repeat …>, <$repeat0 …> (синоним $repeat), <$repeat1 …> (для окружающей)… Либо, <$loop …>, <$rec …> или какое-нибудь иное слово. Вообще, такое ключевое слово можно использовать и в обычных глобальных именованных функциях для рекурсивного вызова. Тоже смотрелось бы неплохо.
В общем, вы предложили благодатную идею для функциональных языков вообще, и для Рефала в частности. Мне нравится.
> …а вложенную функцию можно даже скопировать в другое подходящее окружение, не изменяя ничего в ней, в частности — интерфейс к «родителю».
Копипаст — зло. Если нужно скопировать код, чтобы повторить одинаковую логику, то эту логику нужно вынести в отдельную функцию, которую следует вызывать из двух мест. А функция будет именованной :-). Впрочем, если язык поддерживает макросы, то можно такой фрагмент кода использовать внутри макроса. Пишут же на Си макросы, содержащие, скажем, break, continue или return.
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Saturday, August 5, 2017 10:27 PM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Mike Potanin
в джаваскрипте - решение неудачное, так как оно не позволяет
производить TCO. В функциональном языке какие-то варианты TCO очень
важны, так как руками рекурсию в цикл превратить не получится.
Boyko Bantchev
Спасибо за комментарии!
Сделаю еще несколько заметок по теме.
Прошу прощения у тех, кому она неинтересна.
> В предыдущем письме вы привели пример кода на JavaScript, тем самым подтолкнув меня в сторону императивной парадигмы. А там рекурсия бывает редко
та конструкция, о которой говорил, при этом язык повсеместно
распространен, так что приведенными примерами можно реально
поиграть, даже не выходя из браузера с имейлом :)
При этом, конечно, о возможности решить те же самые задачи императивно
я намеренно забыл — ведь нужно было иллюстрировать функциональное
поведение, так что для явного выражения повторности ограничиваемся
рекурсией.
По поводу частоты циклов while в Си-подобных ЯП: вы привели статистику,
чтобы показать, что while встречается нередко, с чем я вполне согласен.
Но я и указывал на низкую частоту не употребления, а потребности в нем.
(Прошу, обратите внимание на мои слова, которые вы цитировали до
статистики.) Дело в том, что нередко программист поленится выделить,
скажем, обновляющую часть и соответственно применить for, а оставит ее
в теле цикла while, который пришел ему в голову первым. Но при этом
факт остается — по существу требовалось for, а не while.
Выражаясь крайным образом, можно сказать так: цикл с условием, но без
обновляющей части вообще невозможен, так как, если значения участвующих
в условии переменных не обновляются, цикл не завершится :)
А все это только в связи с тем, что наблюдаемое применение конструкций
не есть достаточный критерий их обоснованности или полезности.
Вокруг полно несоответствий между одним и другим — так и в
императивных, и в функциональных языках.
> Копипаст — зло.
В целом — да. Но бывает и так, что копипаст сопровождается удалением
оригинала, т.е. имеет место не копирование, а перемещение. И вообще,
даже избегая копипаст, сохранять «копипастуемость» частей программы
невредно.
Наконец, приведу еще две соображения в пользу безымянного самовызова.
Пусть мы написали функцию для чего-то — небольшую, но с рекурсией.
Хотелось бы функцию не именовать, так как она используется лишь в
одном месте, где она вызывается или передается как значение или
результат другой функции. Но в отсутствии возможности безымянного
самовызова именовать требует рекурсия. А потом вдруг спохватились,
что данная функция — всего лишь fold или zip и т.д., и переписали,
и уже именовать не требуется, так как и рекурсии нет. Но тогда что
получается? Именовать или нет зависит не от значительности функции
или других факторов, а полностью от наличия в ее реализации рекурсии.
Способ реализации диктует не относящиеся к реализации решения!
И последнее, представим, что безымянный вызов реализован в каком-то
языке в виде особой переменной: в нормальном случае, если эта
переменная встречается в теле функции, она соответствует вызову той
же функции. Как и обсуждалось. А теперь представим, что значение
этой переменной можно в явном виде задать при вызове функции —
каким-то особым дополнительным аргументом или вообще особым видом
вызова. Теперь уже эта переменная будет соответствовать не вызванной
функции, а некоторой другой. (Подразумевается, что возможность делать
такие особые вызовы тоже встроена в языке.)
Что получаем в итоге?
Если вызывать функцию обычным способом, через свою особую переменную
она будет вызывать себя. А если значение этой переменной подменить
при помощи специального вызова, то уже вызывать она будет того, кого
ей указали.
Последнее знакомо? Это как раз то преобразование функции, которое
мы делаем, чтобы к этой функции применить комбинатор Y или функцию,
которая сделает из нее ее мемо-вариант. И Y, и мемо-генератор делают
свою работу вполне автономно, но им обоим нужно подать подходящим
образом уже преобразованную функцию. А поскольку этот начальный шаг
пока делается вручную, ни нахождение неподвижной точки, ни переход
от функции к ее мемо-варианту не могут быть вполне автоматическими
процессами. Мое предложение устраняет данное неудобство. Понятно,
что его применимость этим не ограничена — оно скажется положительно
и на другие преобразования рекурсивных функций.
Вывод такой: обеспечение анонимного самовызова в свою очередь
открывает путь к дальнейшим усовершенствованиям языка.
Andrei Klimov
Mike Potanin
семантика неконстантных методов объекта-функции. В исходном
джаваскрипте TCO не было. Сейчас она допускается и для этого, как
минимум, метод arguments у объектов-функций объявлен deprecated.
Andrei Klimov
Boyko Bantchev
> > > в джаваскрипте - решение неудачное, так как оно не позволяет
> > > производить TCO. В функциональном языке какие-то варианты TCO очень
> > > важны, так как руками рекурсию в цикл превратить не получится.
> >
> > По идее, если вызов действительно хвостовой (поверх него ничего нет),
> > то что мешает это заметить и преобразовать в цикл?
>
> семантика неконстантных методов объекта-функции. В исходном
> джаваскрипте TCO не было. Сейчас она допускается и для этого, как
> минимум, метод arguments у объектов-функций объявлен deprecated.
JavaScript, полюбопытствовал, заглянув в стандарт JavaScript — версии
2015 и 2017 года. Последняя здесь:
http://ecma-international.org/publications/standards/Ecma-262.htm.
Это тоже не помогло прояснить ситуацию, так как слово deprecated там
вообще не встречается, а читать всё подряд не стал.
Но должен уточнить: вопрос о возможном удалении чего-то из JavaScript
и не имеет никакого отношения к сути того, о чем я писал.
То, что я обсуждал, это возможность безымянной функции цитировать себя.
Это по существу синтаксическое средство и ненужно его связывать с
«фреймами вызова» — функции незачем ждать быть вызванной, чтобы узнать
кто она; она это должна знать с рождения.
А что в JavaScript, на котором давал примеры, имеются свои особенности,
к вопросу совершенно несущественно.
П.П. Только что видел, что и Андрей Климов писал о том же.
Александр Коновалов
> даже не выходя из браузера с имейлом :)
> Но я и указывал на низкую частоту не употребления, а потребности в нем.
Например, поиск первого ненулевого элемента в двумерной таблице:
int row = 0, col = 0;
while (row < MAXROW && elem_at(row, col) == 0) {
++col;
if (col == MAXCOL) {
col = 0;
++row;
}
}
if (row == MAXROW) {
ничего не нашли, обрабатываем этот случай
} else {
обрабатываем случай, когда что-то нашли, скажем 30 строк кода.
}
освобождаем память, закрываем файлы, делаем другую общую очистку
Другой пример, посимвольная обработка файла:
FILE *f = fopen(…, "rb");
if (! f) {
закрыть другие файлы, освободить память, return
}
int c;
while ((c = fgetc(f)) != EOF) {
что-то делаем с символом
}
fclose(f);
В этих двух примерах на мой вкус лучше писать while (в последнем случае можно for, если хочется ограничить область видимости переменной int c).
> … место не копирование, а перемещение. И вообще, даже избегая копипаст, сохранять «копипастуемость» частей программы невредно.
Всецело поддерживаю этот тезис!
> И последнее, представим, что безымянный вызов реализован в каком-то языке в виде особой переменной: в нормальном случае, если эта переменная встречается в теле функции, она соответствует вызову той же функции. Как и обсуждалось. А теперь представим, что значение этой переменной можно в явном виде задать при вызове функции — каким-то особым дополнительным аргументом или вообще особым видом вызова. Теперь уже эта переменная будет соответствовать не вызванной функции, а некоторой другой. (Подразумевается, что возможность делать такие особые вызовы тоже встроена в языке.)
>
> Что получаем в итоге?
> Если вызывать функцию обычным способом, через свою особую переменную она будет вызывать себя. А если значение этой переменной подменить при помощи специального вызова, то уже вызывать она будет того, кого ей указали.
http://www.quizful.net/interview/csharp/optional-named-parameters
Можно представить себе такое расширение C#’а, которое позволяет организовывать именно такую рекурсию. А именно, предположить, что любая функция принимает в качестве «скрытого» именованного параметра переменную rec (от слова recursion), которой по умолчанию присвоена сама эта функция. То есть в списке формальных параметров он явным образом не записывается, но внутри функции им пользоваться можно. А вот при вызове функции этот необязательный именованный параметр можно указать, передав ему совместимую функцию. Например, вызов f(3, 4) вызовет функцию f, и если функция f содержит вызов переменной rec, то она будет рекурсивно вызывать себя. Вызов же f(3, 4, rec: g) подменит переменную rec внутри неё.
> Вывод такой: обеспечение анонимного самовызова в свою очередь открывает путь к дальнейшим усовершенствованиям языка.
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Monday, August 7, 2017 12:55 PM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Boyko Bantchev
> Вот и выросло поколение, которое не пользуется почтовыми клиентами.
уже давно не вижу причин пользоваться самостоятельными программами
для имейла.
> Иногда логика продвижения, обновляющая часть сильно переплетена с логикой обработки текущей итерации. Иногда продвижение выполняется как побочный эффект проверки.
> Иногда продвижение требует, скажем, условного оператора. А сишный for в качестве операции обновления требует только одно выражение. При этом, желательно, довольно короткое (выражение в три строки в операторе for будет выглядеть и читаться не самым лучшим образом)
конструкции типа for, а вовсе не об адекватности while для решения
таких задач.
Какое-то время назад я исследовал использование циклов в программах
на C. Подтвердилось предположение о значительном доминировании
циклов с хорошо различимыми частьями, даже когда while. Т.е. и в
теле многих while можно было четко разглядеть обновляющую часть,
а инициализация висела вне цикла, хотя по смыслу несомненно
относилась к нему.
Кстати, повышать выразительность циклов в C и C++ можно за счет
макросов — тут и любое число локальных переменных, и развернутые
прологи/епилоги/обновления, и окончания непосредственно на
синтаксическом уровне тела цикла (чего break и continue не могут).
Через макросы можно и специализировать (упрощать) циклы. Я все это
делал в качестве эксперимента и даже считаю, что стоит пользоваться,
когда нет причин, заставляющих к обратному.
Александр Коновалов
> Не знаю. Лично я ближе к пенсии. Но, хотя живу все время в линуксе, уже давно не вижу причин пользоваться самостоятельными программами для имейла.
> Да. Однако это говорит о потребности в более усовершенствованной конструкции типа for, а вовсе не об адекватности while для решения таких задач.
> Кстати, повышать выразительность циклов в C и C++ можно за счет макросов — тут и любое число локальных переменных, и развернутые прологи/епилоги/обновления, и окончания непосредственно на синтаксическом уровне тела цикла (чего break и continue не могут).
> Через макросы можно и специализировать (упрощать) циклы. Я все это делал в качестве эксперимента и даже считаю, что стоит пользоваться, когда нет причин, заставляющих к обратному.
Boyko Bantchev
> С интересом бы посмотрел на такую библиотеку макросов. Попробовал бы переписать с её использованием два примера циклов while из предыдущего письма. У вас она где-нибудь в интернете опубликована?
шаблонных определений. Выложил здесь:
http://www.math.bas.bg/bantchev/misc/m.cpp
Чудес не ожидайте, вещи совсем простые.
С другой стороны, там не только о циклах, но и пара других, как мне
кажется, полезных вещей. Буду рад, если что-то вам пригодится.
В следующем тексте написано немного об идеологии:
http://www.math.bas.bg/bantchev/misc/neater.pdf ,
но он немного различается как раз в отношении макроопределений для
циклов. Впрочем, в этом разберетесь легко.
Что касается вашего первого примера с while
int row = 0, col = 0;
while (row < MAXROW && elem_at(row, col) == 0) {
++col;
if (col == MAXCOL) {
col = 0;
++row;
}
}
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;
}
Sergei M. Abramov
> ... легко переписать и стандартными 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;
Всего доброго,
Сергей Абрамов
Александр Коновалов
> Библиотекой назвать вряд ли стоит, там всего несколько макро- и шаблонных определений. Выложил здесь:
> http://www.math.bas.bg/bantchev/misc/m.cpp
> http://www.math.bas.bg/bantchev/misc/neater.pdf , но он немного различается как раз в отношении макроопределений для циклов. Впрочем, в этом разберетесь легко.
Понравилась реализация необязательного параметра n в макросе fora:
#define fora(a,i,n,...) {__VA_ARGS__; int _ = #n[0]=='\0' ? asize(a) : n+0; \
for(int i=0; i<_; ++i) { // entire array processing
Когда его нет, #n раскрывается в пустую строчку, а n+0 в +0, что является корректным выражением. Не удивлюсь, если современные компиляторы истинность строки #n[0]=='\0' определят во время трансляции и во время выполнения ветвления уже не будет.
Мой пример выглядел бы так:
int row, col; // используются после цикла, нельзя объявлять внутри.
loop (
row = 0; col = 0
, row < MAXROW && elem_at(row, col) == 0
, ++col;
col = 0;
++row;
}
// тело пустое, как я и предполагал
fin();
Цикл с пустым телом.
Фишка этого примера в том, что он записывается целиком в рамках структурного программирования: без goto, break и return. И, кроме того, пример демонстрирует идиому структурного программирования для поиска элемента в последовательности:
<установить на начало>
while (! <достигли конца> && ! <элемент обнаружен>)
<вычисление следующего и переход к нему>
if (<достигли конца>)
<действия, если элемент не найден>
else
<действия, если элемент найден>
Просто поразительно, как часто такой подход позволяет распутывать сложные циклы. Сам порой удивляюсь, что через эту идиому красиво описываются иные сложные задачи. Главное сформулировать задачу как задачу поиска. Сравнить две строки на равенство — _найти_ первый неравный символ, например.
А пример — поиск в двумерной таблице — потому и выбран, что большинство программистов не представляют, как его решить без двух вложенных циклов и нелокального перехода. Даже в учебниках его демонстрируют как пример, когда «goto необходимо».
> то, мне кажется, его легко переписать и стандартными 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;
> }
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Tuesday, August 8, 2017 11:31 PM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Boyko Bantchev
> Понравилась реализация необязательного параметра n в макросе
А вот полным решением проблемы с избыточностью имен в struct в Си
я горжусь :)
И в учебниках по программированию на Си, и в реальных программах —
тонны этой избыточности, но решение показывает, что она не нужна.
> Мой пример выглядел бы так:
>
> int row, col; // используются после цикла, нельзя объявлять внутри.
> loop (
> row = 0; col = 0
> , row < MAXROW && elem_at(row, col) == 0
> , ++col;
> if (col == MAXCOL) {
> col = 0;
> ++row;
> }
> )
> // тело пустое, как я и предполагал
> fin();
То, что в файле m.cpp, является более поздним и с ним данный фрагмент
не сработает. Ваш вариант поиска я записал бы так:
loop (row = 0; col = 0 , row < MAXROW)
exitif (elem_at(row, col) != 0)
upd (if (++col == MAXCOL) { col = 0; ++row;})
fin();
Преимущества:
проверка нахождения нужного элемента выделена самостоятельно;
искомое условие для элемента сформулировано положительно;
тело цикла не пусто;
обновление индексов лучше сосредоточено в одной конструкции.
> Фишка этого примера в том, что он записывается целиком в рамках структурного программирования: без goto, break и return.
Но данная точка зрения не единственная.
> Плата за структурное программирование. В варианте Сергея Абрамова (в следующем письме) вводится дополнительная булевская переменная и тоже требуется дополнительная проверка
для цикла,-ов, хотя ей лучше быть локальной, ведь дальше она не
используется.
Плата за структурное программирование? Скорее, по-моему, это
плата за определенное, очень конкретное понимание структурного
программирования. Но единого определения этого понятия, с которым
все были бы согласны, нет. Зачем подгонять решения задач под
какое-то представление о структурности, которое даже не является
общепризнанным? Что получаем за «плату»? Ведь решения становятся
в той или иной мере искусственными (признаком чего является
избыточность имен и действий), а что получаем навстречу и так ли
оно ценно? Не лучше ли пересмотреть наше понимание о структурности?
Допустим, кто-то постановил, что программировать структурно — это
только через while и простую последовательность. Даже if не нужен, он
выражается через while. Но такое понимание структурности не берет
во внимание ни локальность связываний имен, ни количество тех же
имен и вообще элементов программ, ни обоснованность введения всех
этих элементов с точки зрения решаемой задачи (а не соблюдения
заранее придуманных правил «структурности»).
Признано, что придерживаться какого-нибудь множества структурных схем
нужно, но по-моему так же нужно выбор этого множества время от времени
пересматривать. Иначе в императивном программировании мы бы остались
с Фортраном или Алголом-60, у каждого из которых имеется единственный
оператор цикла. А в функциональном программировании так и не пришли
бы к лексическому связыванию, частичному применению, одноаргументности
и композиции функций и сопоставлению с образцом — остались бы с Лиспом,
у которого их и сегодня нет, за исключением лексического связывания.
Впрочем, вред слишком узкого понимания структурности для императивного
программирования был осознан и подробно обоснован еще в начале 1970-х.
Sergei M. Abramov
>> (в следующем письме) вводится дополнительная булевская переменная и
>> тоже требуется дополнительная проверка
> И, кроме того, дополнительная переменная оказывается нелокальной
> для цикла,-ов, хотя ей лучше быть локальной, ведь дальше она не
> используется.
она станет локальной.
По поводу "дальше она не используется"... это зависит от задачи ;-)
Ее смысл: уже нашли или еще нет. То есть, это то самое <элемент
обнаружен>. И в этом смысле, то, что я написал
НИКАК не отличается от:
> <установить на начало>
> while (! <достигли конца> && ! <элемент обнаружен>)
> <вычисление следующего и переход к нему>
> if (<достигли конца>)
> <действия, если элемент не найден>
> else
> <действия, если элемент найден>
>, ++col;
> if (col == MAXCOL) {
> col = 0;
> ++row;
> }
спорят.
Мои предпочтения давно в области прозрачности кода для чтения, а не в
области эффективности для исполнения.
Лет семь назад встретил цитаты из великих (не помню кто и цитата по
памяти, не точный текст):
> Под флагом и по причине борьбы за эффективность в программировании
> совершено больше преступлений, чем по всем остальным причинам вмести
> взятын. Включая непроходимую тупость.
С тей пор как прочитал, как и отрезало ;-)
PS. Я не уверен, что нормальный компилятор не удалит в моем тексте
так называемую "лишнюю проверку" ;-) А "лишняя переменная" это не
более, как экономия вычислений за счет табулирования ранее
посчитанного значения. Кстати, если окажется, что она действительно
лишняя, то и ее компилятор должен удалить (дефорестация). А читать
приятнее с нею (опять, дело вкуса).
Всего доброго,
Сергей Абрамов
Александр Коновалов
> А вот полным решением проблемы с избыточностью имен в struct в Си я горжусь :) И в учебниках по программированию на Си, и в реальных программах — тонны этой избыточности, но решение показывает, что она не нужна.
> Это если принять, что в структурном программировании их нет.
> Но данная точка зрения не единственная.
Но, понятно, это сильные ограничения на стиль программирования, и бывают задачи, когда чистый структурный код читается и поддерживается хуже, чем прагматичный неструктурный. Например, бывают случаи, когда даже goto существенно упрощает и проясняет программу (но это не значит, что можно писать по одному goto на каждые 10 строк кода, если конечно, речь идёт не о ассемблере).
Я, лично, предпочитаю писать структурно, если задача не требует иного. И люблю ту идиому с while для поиска.
> Признано, что придерживаться какого-нибудь множества структурных схем нужно, но по-моему так же нужно выбор этого множества время от времени пересматривать. Иначе в императивном программировании мы бы остались с Фортраном или Алголом-60, у каждого из которых имеется единственный оператор цикла. А в функциональном программировании так и не пришли бы к лексическому связыванию, частичному применению, одноаргументности и композиции функций и сопоставлению с образцом — остались бы с Лиспом, у которого их и сегодня нет, за исключением лексического связывания.
https://github.com/kroki/Cuckoo-hash/blob/master/src/cuckoo_hash.h#L159-L192
> …или Алголом-60, у каждого из которых имеется единственный оператор цикла
Удивился, поскольку помнилось, что в Алголе есть и for, и while. Открыл отчёт по Алголу (revised report, 1962) — был очень витиеватый цикл for, который мог быть даже while.
for j := 1 step 1 until 10 do — переберёт числа 1…10
for j := 1 step 1 until 10, 20 step 1 until 30 do — переберёт 1…10, 20…30
for j := 2, 3, 5, 7, 11, 13 do — переберёт несколько простых чисел
for j := 42 while x > 7 do — будет повторять тело цикла с параметром 42, пока x > 7
for j := 42 while x > 7, 666 while x > 0, 100, 1 step 1 until 10 do — сначала прокрутит некоторое количество раз 42, потом несколько раз 666, потом один раз 100, потом числа от 1 до 10.
В Алголе-68 тоже был один оператор цикла, который мог быть и for, и while, и гибридом. Кстати, вопрос на засыпку: почему в Алголе-68 и Bash нет цикла с постусловием (управляющие конструкции Bash слизаны с Алгола-68 почти дословно)?
> Впрочем, вред слишком узкого понимания структурности для императивного программирования был осознан и подробно обоснован еще в начале 1970-х.
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Wednesday, August 9, 2017 1:58 PM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
s...@cnshb.ru
Лет семь назад встретил цитаты из великих (не помню кто и цитата по
памяти, не точный текст):С тей пор как прочитал, как и отрезало ;-)
Нас - "пацанов" в конце 70-х Владимир Леонидович Топунов учил что, если предполагаемый эффект от оптимизации меньше 10%, то не следует даже браться...
Александр Коновалов
> Под флагом и по причине борьбы за эффективность в программировании
> совершено больше преступлений, чем по всем остальным причинам вмести
И это цитирует специалист по метавычислениям и суперкомпиляции — технологии оптимизации программ. :-)
-----Original Message-----
From: Sergei M. Abramov [mailto:ab...@botik.ru]
Sent: Wednesday, August 9, 2017 5:07 PM
To: Boyko Bantchev <boy...@gmail.com>; re...@botik.ru
Subject: Re: FW: Рефал умер?
Boyko Bantchev
> for (row=0; row < MAXROW && goon; ++row)
> for (col=0; col < MAXCOL && goon; ++col)
> goon = elem_at(row,col) == 0;
Сергей Абрамов правильно отметил, что goon вполне может
быть локальной во внешнем цикле.
Но есть проблемма посерьезнее: программа просто не формирует
правильный результат.
Избежание goto и break considered harmful ;)
Boyko Bantchev
Хочешь не хочешь, а for и «управляющая переменная» обязательны для
цикла. Даже когда переменная никак не нужна и нигде не используется.
Поэтому написал, что оператор цикла в Алголе-60 единственный.
А в Алголе-68 не так: там никакая часть не обязательна. Можно
счетчик использовать, можно и условие, но все на выбор.
(Еще более это развито в ПЛ/1 — в нем голова кружится от возможностей
написать цикл, как впрочем и почти все остальное. Цикл ПЛ/1 скопирован
в REXX, который и ныне здравствует.)
> Впрочем, и польза от разумной структурности тоже вполне обоснована
Проблема в том, что принято только пользу подчеркивать, а о вреде
умалкивают. Ниже приведу пример в этом духе.
> Читал как-то отечественную книжку 80-х годов про Симулу-67. Редкий метод в ней обходился без goto
отношении. Книг по программированию на русском у меня много, а
покупал их как раз в это время. (Тогда у нас их продавали в большом
количестве, очень недорого, и у меня накопилась библиотека приличного
размера.) Но злоупотребление goto нигде не встречал.
> Под флагом и по причине борьбы за эффективность в программировании
> совершено больше преступлений, чем по всем остальным причинам вмести
> взятын. Включая непроходимую тупость.
Роджер Хюи, автор (совместно с К.Айверсоном) и главный реализатор
языка J (наследника APL) утверждает, что никакую оптимизацию не стоит
делать, если приведет к улучшению не больше чем в два раза!
Но! Под оптимизацией можно понимать разные вещи. Меня в этой
дискуссии мотивирует не оптимизация в смысле повышения быстродействия,
а экономия. Не вводить лишнее, не повторять действия, расставить
нужное где ему лучше быть. Организовать программу из таких
соображений, а не из соображений придерживания к неясно чем полезным
на практике правилам.
Приведу пример: процедура проталкивания в пирамиду. У меня она
получается так:
void sift(T a[], unsigned n, unsigned p) {
unsigned j;
T x = a[p];
for (;;) {
if (j=2*p+1, j+1<n && a[j]<a[j+1]) ++j;
if (j>=n || a[j]<=x) break;
a[p] = a[j]; p = j;
}
a[p] = x;
}
Как во многих других случаях, цикл естественнее всего пишется с
выходом из середины тела.
А это вариант Н.Вирта из его известной книги — текст то ли на Модуле,
то ли на Обероне:
PROCEDURE sift(L, R: INTEGER);
VAR i, j: INTEGER; x: Item;
BEGIN i := L; j := 2*i+1; x := a[i];
IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END;
WHILE (j <= R) & (x < a[j]) DO
a[i] := a[j]; i := j; j := 2*j+1;
IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END
END;
a[i] := x
END sift;
Есть различия несущественные, но главная в моем понимании проблема
здесь — дублирование строк 4 и 7, только из желания избежать выхода
из тела цикла, быть «структурным». Не знаю чем это может быть
полезным, для меня оно выглядит нелепо. Хоть и из уст великих.
В самом первом варианте книги (на Паскале) Вирт использовал goto для
выхода из цикла и дублирования действий нет. Потом «эволюировал».
Anton Korzh
Sent from a Cellphone, sorry for misprints
Sergei M. Abramov
not_found...
Всего доброго,
Сергей
PS. Впрочем Гугль переводчик переводит как "шрпдплжай" (основной
вариант) и только потом все остальные варианты: неуклюжий, громила,
головорез, болван, тупица, неловкий человек, неуклюжий человек,
наемный бандит.
Александр Коновалов
Bash, цикл с предусловием:
while
prog1
do
prog2
prog3
od
Bash, цикл с выходом посередине:
while
prog1
prog2
do
prog3
od
Bash, цикл с выходом посередине и пустым телом == цикл с постусловием:
while
prog1
prog2
prog3
do
:
od
Этот цикл будет продолжаться, пока программа prog3 будет выдавать нулевой, успешный код возврата. И цепочка prog1; prog2; prog3 выполнится хотя бы один раз. Цикл с постусловием. (Двоеточие в Bash — специальное обозначение пустой команды, которая всегда выполняется успешно.)
> void sift(T a[], unsigned n, unsigned p) {
> unsigned j;
> T x = a[p];
> for (;;) {
> if (j=2*p+1, j+1<n && a[j]<a[j+1]) ++j;
> if (j>=n || a[j]<=x) break;
> a[p] = a[j]; p = j;
> }
> a[p] = x;
> }
proc sift = (ref [] T a, int n, int p) void: (
int j;
if (j := 2*p + 1; j + 1 < n) and a[j] < a[j + 1] then j +:= 1;
j < n and a[j] > x
) do
a[p] := x
)
Красота. И никаких break’ов и goto. Структурное программирование :-).
Книжка про Симулу следующая:
Андрианов А. Н., Бычков С. П., Хорошилов А. И. Программирование на языке симула-67.— М.: Наука. Глав. ред. физ.-мат. лит., 1985.— 288 с.
Процитирую один фрагмент из книги, интересный в контексте рассылки re...@botik.ru:
Стр. 8:
«Авторы считают приятным долгом выразить благодарность … А. А. Веденову, С. А. Романенко, А. Е. Фирсову за помощь в использовании рефал-систем на БЭСМ-6 и ЕС ЭВМ …»
И ещё, стр. 169:
«При реализации широко применялся язык рефал [5], ориентированный на программирование сложных символьных преобразований. Наличие на машинах БЭСМ-6 и ЕС ЭВМ реализаций рефала [5, 14], практически полностью совместимых по входному языку, позволило значительно сократить трудоёмкость разработки симула-компиляторов, особенно компилятора для ЕС ЭВМ, основу которого составили программы ранее разработанного транслятора с языка симула-67 для БЭСМ-6.»
Ссылки списка литературы (см. выше):
«5. Базисный РЕФАЛ. Описание языка и основные приемы программирования (методические рекомендации). Вып. V-33.— М.: ЦНИПИАСС, 1974.— 95 с.
…
14. Климов Ан. В., Романенко С. А. Рефал в мониторной системе Дубна. Интерфейс рефала и фортрана.— М., 1975.— 34 с. (Препринт/ИПМ им. М. В. Келдыша АН СССР)»
Boyko Bantchev
Что и есть по вашему определению структурность. Или отреклись уже? :)
При этом у меня процедура вроде правильно работает. А ваша на
Алголе-68 ошибится индексированием — операция and в Алголе-68 не
ленивая :)
Александр Коновалов
> Что и есть по вашему определению структурность. Или отреклись уже? :)
> При этом у меня процедура вроде правильно работает. А ваша на
> Алголе-68 ошибится индексированием — операция and в Алголе-68 не ленивая :)
proc sift = (ref [] T a, int n, int p) void: (
int j;
T x := a[p];
while (
(j < n| a[j] > x | false)
a[p] := a[j]; p := j
od;
a[p] := x
)
-----Original Message-----
From: Boyko Bantchev [mailto:boy...@gmail.com]
Sent: Thursday, August 10, 2017 11:57 AM
To: re...@botik.ru
Subject: Re: FW: Рефал умер?
Arkady Klimov
Александр Коновалов
Согласен, там понятнее. Я просто хотел проиллюстрировать, что в Алголе-68 есть синтаксис для цикла, условие которого проверяется в середине. И для этого _дословно_ переписал алгоритм, предложенный Бойко на Си (у него был бесконечный цикл с единственным выходом по break в середине). Т.е. исходный алгоритм на Си на пару писем раньше тоже был запутанным.
Boyko Bantchev
запутанную процедуру. Допишу имейл и предприму самобичевание плетью
с крючками.
> А все-таки на следующей странице оно понятнее (функция siftDown)
двух мест вместо одного и многократное подталкивание значения мелкимми
шажками (вместо того, чтобы найти его место и поставить раз) – все это
чрезвычайно способствует ясности.
> А чтобы добиться структурности вам приходится ...
Хотите — верьте, хотите — нет, но я не стремился к структурности
и в принципе не стремлюсь, так как мне и непонятен смысл слова в
контексте программ. Многолетное и чтение литературы, и собственная
практика не помогли в этом. А стремлюсь к тому, чтобы текст отвечал
смыслу того, что я хочу выразить и, по возможности, не было лишних
имен, действий и прочих сущностей. Что, конечно, глубоко ошибочно
с моей стороны.
> Да к тому же обеспечить доступ в теле цикла к вычисленному внутри условий индексу j, объявив j вне цикла.
От этого доступность не пострадает, а j используется в каждой
строке цикла.
> Стало, конечно, структурно, но более запутанно.
имею. А насчет «запутанно» я уже согласился устами и обеими руками.
Чтобы хоть немного прояснить непроглядный мрак запутанности, приведу
перевод содержания цикла — т.е. практически всей процедуры — с Си на
русском, строка за строкой. Читаем строго последовательно, слева
направо.
if (j=2*p+1, j+1<n && a[j]<a[j+1]) ++j;
пусть он будет наследником.
if (j>=n || a[j]<=x) break;
a[p] = a[j]; p = j;
Поднимаем к себе наследника. Занимаем его место.