Небольшая коллекция sed-скриптов.

Апрель, 2020

Содержание:

Нецелевое использование поточного редактора.
Минирепозитории
Скрипты других авторов.

Нецелевое использование поточного редактора.

На данной странице представлен краткий аннотированный список некоторых непрактичных сценариев для широко известного поточного редактора sed. В работе этой утилиты основное место занимает команда s/<шаблон>/<замещающий_текст>/ (вместо символа / может использоваться и другой разделитель), ищущая и заменяющая фрагмент текста, удовлетворяющий некоторому регулярному выражению-шаблону.

Эта команда, могущая показаться далёкой по своей функциональности от обеспечения Тьюринг-полноты входного языка sed, вместе с метками и командами перехода (условного и безусловного) всё же делает данный редактор вычислительно-универсальным. Фактически, он может рассматриваться в качестве реализации нормальных алгорифмов Маркова (хотя это и не общепринятое мнение), а полнота по-Тьюрингу обуславливает саму возможность всех произошедших с sed приключений [с его нестандартным использованием].

В основном, здесь представлены мои скрипты, но в конце приводится список некоторых из похожих на них в своей непрактичности (а нередко кратно превышающих мои поделки в своей удивительности и технологической сложности реализации) скриптов других авторов.

Сложно, а быть может уже и вовсе невозможно сказать, какие ещё необычные сценарии писались за всю историю существования этого редактора, использовавшегося с начала/середины семидесятых годов прошлого века; так что остаётся лишь продолжать неспешные поиски аналогичных артефактов и, конечно, писать свои.

Итак, моя учетная запись на GitHub содержит следующие репозитории со скриптами для sed:

ocr-in-sed

Этот скрипт написан под впечатлением от однострочной C-программы некоего Эрика Копчинского (Eryk Kopczynski), написанной для небезызвестного конкурса ioccc за 2004 год и выполняющей оптическое распознавание текста находя эйлерову характеристику его «триангуляции» (насколько вообще можно говорить о триангуляции для картинки в стиле ASCII-арт).

Да, меня тоже сначала сбила с толку возможность распознавания на основе именно этого топологического инварианта, очевидно имеющего одинаковые значения вообще для всех планарных графов; поэтому интересующихся пока переадресую на статью (S.B.Gray, Local Properties of Binary Images in Two Dimensions, 1971), предположительно являющуюся основой для программы Копчинского. По-сути, авторы расчитывают инвариант, равный разности между количеством связных областей и количеством дырок, но расчитывают его подсчитывая различные чисто локальные конфигурации пикселей в $\text{[math]}$ -окне, пробегая им по всему изображению (в статье этот сверточный подход распространен и на $\text{[math]}$ -окна, но у Копчинского применено маленькое окно).

Увы, особая простота этой логики сильно ограничивает функциональность основанной на ней программы распознования символов… И кроме целых из, скажем так, не очень большого промежутка $\text{[math]}$ эта OCR-программа ничего распознать толком не может.

В любом случая, я решил реализовать этот же алгоритм, написав аналогичный скрипт для sed; естественно вообще не стремясь к однострочности.

drawing-in-sed

Простой графический редактор, выполняющий команды со стандартного ввода и реализующий некоторое подмножество/версию черепашьей графики и систем Линденмайера. Сгодится для рисования некоторых геометрических фигур, символов, фракталов. Не самое очевидное применение sed, не так ли?

computus-in-sed

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

langton-ant-in-sed

Симуляция известного автомата «муравей Лангтона», интересного, среди прочего, своей Тьюринг-полнотой и интересной открытой проблемой, связанной с аттракторами («дорога» с периодом 104 шага) этой динамической системы для всех конечных начальных конфигураций.

elementary-ca-in-sed

Элементарные одномерные конечные автоматы по-Вольфраму. Достаточно полезная возможность для sed, позволяющая создавать узоры, генерировать псевдослучайные числа, моделировать некоторые физические процессы.

life-in-sed

Игра «жизнь» Конвея, теперь и на sed.

music-in-sed

Пианино на sed! Кто же не делал что-то вроде cat /dev/urandom > /dev/audio или sudo cat /dev/mem > /dev/audio? Редактор sed вполне может приняв со стандартного ввода нотную запись, синтезировать последовательность символов, которая будучи отправленной в oss-устройство /dev/audio (или его аналог), приводит к проигрыванию соответствующей мелодии через звуковую карту. Всё очень просто. :)

Поводом для написания этого скрипта явилось сообщение Kyle Keen об этом способе генерации звука. Но там был применен полноценный язык программирования awk, позволивший легко получить более качественный чем у меня звук за счет использования треугольной формы сигнала. Так появилась музыкальная программа-синтезатор на гораздо более ограниченном sed, именно в силу ограниченности и представляющем больший спортивный интерес.

maze-in-sed

В попытке понять написанную на sed одним [предположительно Сингапурским] хакером программу поиска выхода из лабиринта я написал свою версию, включив в поставку [пока не полностью работоспособный] комплементарный генератор лабиринтов (естественно тоже на sed).

sieve-in-sed

Решето Эратосфена на sed. Кроме собственно решета, реализованного в sieve.sed, в репозитории можно найти скрипт factor.sed, разлагающий данное число на его простые делители. А для демонстрации применения простых чисел (и в соответствии с эзотерической направленностью подобных развлечений с редактором sed) позже были добавлены скрипты anagram.sed и collatz.sed, – для детектирования анаграмм, и для реализации динамической системы из гипотезы $\text{[math]}$ (гипотезы Коллатца), соответственно.

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

Объяснение работы данных скриптов содержится в отдельном сообщении этого дневника.

superpermutations-in-sed

Генерация [вообще говоря, не являющихся минимальными] суперперестановок.

cw-in-sed

Этот скрипт принимает на вход текстовое сообщение и генерирует тональный телеграфный сигнал (код Морзе), проигрываемый звуковой картой компьютера по принципу, описанному выше в разделе о синтезаторе мелодий.

r2d2-in-sed

Синтезатор «речи» робота r2d2 из вселенной «Звёздных Войн» Д.Лукаса. Применен тот же принцип генерации текстового потока, озвучиваемого перенаправлением в /dev/audio. В отличии от программы-пианино или от генератора «морзянки», здесь кроме чистых нот (на самом деле всего-лишь прямоугольного сигнала вместо синусоиды) имеется возможность создания белого шума, а также возможность случайного выбора нот.

Интересно, можно ли научить r2d2 говорить [по-человечески]? Пора внести синтезатор речи в TODO-список. :)

infix-compiler-in-sed

Даже будучи текстовым редактором, sed не предоставляет удобных инструментов для разбора (синтаксического анализа) контекстно-свободных грамматик. Наиболее простой метод разбора, а именно рекурсивно-нисходящий анализ, сложен в реализации на sed из-за отсутствия адекватной поддержки рекурсии. Однако в теории ничто не мешает написать рекурсивно-нисходящий парсер, и даже компилятор, для какого-нибудь простого языка, например для арифметических формул (с обычной инфиксной нотацией).

Конкретно этот проект является маленьким (и страшно неэффективным) компилятором формул, принимающим арифметическое выражение (скажем, (1+2)*3) и продуцирующим настоящий машинный код ([пока] только для x86-архитектуры и для 32 битного Linux в качестве ОС). На данный момент, мой скрипт не умеет генерировать полноценный исполняемый файл (хотя это в принципе и возможно), поэтому для добавления всех необходимых заголовков я рекомендую воспользоваться Perl-скриптом m2elf.pl.

banner-in-sed

Упрощенный аналог утилит типа banner/sysvbanner или figlet. Для данной строки печатает её «ASCII-art» вариант (c большими символами), просто склеивая соответствующие её знакам фрагменты текста из специально подготовленного «шрифта». Поддерживается автоматическая коррекция межбуквенных интервалов, т.е. автокернинг (с возможностью наблюдения за бесполезной, но забавной анимацией этого процесса).

quine-kleene-generator

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

Подробности можно найти в серии сообщений «Занимательное квайноводство».

Минирепозитории

Кроме этого на http://gist.github.com/Circiter/ хранятся следующие «минирепозитории» (gists):

sleep-sort.sed – реализация алгоритма «спящей сортировки».
von-neumann-extractor.sed – скрипт преобразует данную $\text{[math]}$ -битную последовательность в $\text{[math]}$ -битную с выравниванием частот/количеств единиц и нулей. Скрипт написан по мотивам работы (Von Neumann, Various techniques used in connection with random digits, 1951).
binary-multiplication.sed – реализация алгоритма умножения двоичных чисел, написанная по мотивам (и путем упрощения) кода умножения десятичных чисел, взятого со страницы http://codegolf.stackexchange.com/a/49442.

Пусть $\text{[math]}$ – цифры двоичного представления числа $\text{[math]}$ , причём $\text{[math]}$ – младший бит $\text{[math]}$ , тогда примерный вид алгоритма для умножения чисел $\text{[math]}$ и $\text{[math]}$ будет таков:
1. $\text{[math]}$ (инициализация аккумулятора).
2. Конец если $\text{[math]}$ ; результат лежит в $\text{[math]}$ .
3. Если $\text{[math]}$ , то $\text{[math]}$ .
4. $\text{[math]}$ ; $\text{[math]}$ .
5. Перейти к шагу 2.
Алгоритм непосредственно следует из двоичного разложения $\text{[math]}$ . Действительно, $\text{[math]}$ , где $\text{[math]}$ . (Операция $\text{[math]}$ на каждой итерации удаляет один самый младший бит числа $\text{[math]}$ , т.о. сдвигая двоичную запись числа: $\text{[math]}$ .)

Актуальный код на sed достаточно точно следует этому наброску.
binary-addition.sed – реализация алгоритма сложения двоичных чисел, используется в вышеприведенном коде умножения чисел.

Если, как и прежде, подразумевается, что числа $\text{[math]}$ , $\text{[math]}$ я $\text{[math]}$ могут быть представлены как строки цифр $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ , соответственно, а нулевые элементы этих последовательностей суть младшие цифры чисел $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , то псевдокод для вычисления $\text{[math]}$ может быть таким:
1. $\text{[math]}$ .
2. Если $\text{[math]}$ или $\text{[math]}$ , то конец (ответ находится в $\text{[math]}$ ).
3. $\text{[math]}$
4. $\text{[math]}$
5. Если $\text{[math]}$ , то $\text{[math]}$ ,
6. Иначе $\text{[math]}$ , $\text{[math]}$ .
7. $\text{[math]}$ ; $\text{[math]}$ .
8. Перейти к шагу 2.
N.B., здесь «цифры» $\text{[math]}$ – это произвольные неотрицательные целые, необязательно удовлетворяющие $\text{[math]}$ ; также следует учесть, что при модификации одного из представлений, автоматически обновляется и другое.

Соответствующий код на sed следует этому плану, за исключением работы со счётчиком $\text{[math]}$ – для добавления очередной цифры к результату, эта цифра просто приписывается в начало хранящей его строки, без какого либо счётчика.
dec-to-bin.sed – перевод десятичного числа в двоичную систему счисления.
dec-to-hex.sed – основанный на предыдущем скрипте (dec-to-bin.sed) код преобразования числа из десятичной системы счисления в шестнадцатиричную. При необходимости оба примера сравнительно легко обобщаются и на другие системы счисления по основанию 2 (e.g. на восьмиричную).
permutations.sed – перестановки, самые обычные перестановки.
sushi.sed – попытка имитации эффекта «цифровой дождь», популяризованного в одном известном артефакте массовой культуры (имеется ввиду экранизация Вачовскими эсхатологических мотивов из «откровений Иоанна» с привлечением идей в двухе лемовских «странных ящиков профессора Конкорана»).

Выглядит как осыпающийся набор типографских символов (в оригинале, модифицированных японских, но здесь используется всего-лишь маленькое подмножество ASCII), оставляющих за собой послесвечение как на старых ЭЛТ-мониторах или осциллографах.

(В моей апокрифической интерпретации, этот эффект можно рассматривать как дискретизированный вариант водопадной визуализации временной развертки РЧ-спектра, хорошо известной всем знакомым с SDR-техникой; в фильме этот инструмент применялся для отладки эмулятора, а также для «обратной отладки» – не только хакеры, несанкционированно подключившиеся к эмулятору/симулятору, но и некоторые программы, запущенные в эмуляторе, могли каким-то образом получать инженерный доступ к его недокументированным функциям и изучать/модифицировать перехватываемые потоки данных.)

Скрипт, с гастрономическим названием sushi.sed, написан в некотором смысле «по-ошибке», но пригоден для демонстрации возможности генерации псевдослучайных чисел в редакторе sed (тот же самый ГПСЧ применён, например, в модифицированном sed-тетрисе или в имитаторе вокально-речевых звуков r2d2).

Реализация с вызовом датчика случайных чисел по необходимости для каждого очередного символа отрисовываемых треков работает достаточно медленно, поэтому я выложил небольшую заплатку, позволяющую вычислять некоторое количество случайных чисел заранее, а затем просто брать их из этого резервуара энтропии по очереди. Такая модификация требует дополнительного времени для запуска скрипта, но после инициализации работает быстрее (хотя и с ожидаемым снижением качества случайности). После скачивания обеих файлов, sushi.sed и sushi.patch, можно выполнить следующие команды:
```
chmod +x sushi.sed
cp sushi.sed sushi.fast.sed
patch sushi.fast.sed sushi.patch
 ...
echo | ./sushi.fast.sed
```
up-n-down.sed – экспериментальный способ перемещения вверх и вниз в sed путем матричного транспонирования буфера редактирования.
transpose.sed – транспонирование матрицы.
sliding-window.sed – другой подход к перемещению вверх и вниз. Последняя строка матрицы дублируется и используется как референсный счетчик. От текущей клетки движутся два маркера в противоположных направлениях (вправо и влево), на каждом шаге декрементируя референсный счётчик. Как только счётчик обнулится, мы можем утверждать, что один (левый) маркер находится над текущей клеткой (т.е. выше неё), правый – под ней. Далее вокруг текущей клетки выделяется 8-окрестность $\text{[math]}$ , окрашивается, отображается. И так для всех клеток с их последовательным обходом (слева-направо, сверху-вниз).

Сам я последнее время использую другой подход к вертикальной навигации в sed, основанный на добавлении маркеров в начало каждой строки с последующим синхронным перемещением всех маркеров вправо до столкновения одного из них с текущей выбранной клеткой. В этот момент мы можем двигаться вверх-вниз вдоль маркеров, затем удалить их и начать работать с другой клеткой (счетчик не нужен). Элементарно.

Nota bene, я почти всегда пишу на диалекте GNU sed, что, увы, создаёт проблемы с использованием моих sed-скриптов на всяких там Mac’ах, BSD’ях и этих ваших Android’ах. Возможен ли конвертер (может быть даже написанный, о ужас, на самом sed) из GNU в Posix и смогло ли бы это решить проблему портабельности?

Post scriptum. Многие из моих sed-сценариев, — ровно как и настоящий список, — носят чисто развлекательно-экспериментальный характер и перманентно находятся в режиме написания/дописывания; функциональность может менятся кардинально без предварительных уведомлений и рациональных обоснований.

Скрипты других авторов.

Выше была описана задача трансляции между диалектами sed. Ближайшие по смыслу найденные мною проекты – sedcheck.sed за авторством Laurent Vogel, проверяющий скрипты на Posix-совместимость; и транслятор sed-bin от Quentin L’Hours, конвертирующий sed в C (примечательно, что оба проекта сами являются sed-скриптами).

Наконец, транслятор https://github.com/shinh/elvm позволяет преобразовать C-код снова в sed. И хотя сам он и не написан на sed, но может оттранслировать самого себя с C на sed. Поэтому, можно считать, что sed-bin и elvm совместно могли бы использоваться для «нормализации» sed-скриптов.

Продолжим обзор мира sed.

На страницах http://sed.sourceforge.net и http://sed.sourceforge.net/grabbag (автор: Paolo Bonzini) можно найти неплохую коллекцию sed-скриптов разной степени полезности. Стоить отметить некоторые из представленных там вещей:

http://sed.sourceforge.net/grabbag/scripts/dc.sed – постфиксный калькулятор (использует обратную польскую нотацию); поддерживает арифметику, корни, перевод между системами счисления и т.д.
http://sed.sf.net/grabbag/tutorials/hanoi.htm – Ханойские башни.
http://www.oocities.org/mettw/personal/software/src/sedhttpd.txt – http-сервер на sed.
http://sed.sourceforge.net/grabbag/scripts/turing.sed – машина Тьюринга на sed; да, это – готовое [конструктивное] доказательство вычислительной универсальности языка sed.
http://sed.sourceforge.net/grabbag/scripts/sokoban.sed – широко известная игра (сокобан); эта реализация интересна, разумеется, перемещением персонажа во всех направлениях (в т.ч. вверх-вниз), чего обычно на sed достичь не так-то просто.
http://sed.sourceforge.net/grabbag/scripts/bf2c.sed – транслятор из, — ну кто же его не знает, — bf в C. (Т.к. bf является разновидностью универсальной машины Тьюринга, то такой транслятор тоже является «простым» доказательством Тьюринг-полноты sed.)

Так же на просторах интернета были найдены:

sedlisp – написанный японцем Shinichiro Hamaji интерпретатор небольшого подмножества lisp’а.
sel – аналогичная реализация lisp-интерпретатора на sed, написанная Mark Barbone.
bf.sed – написанный Stephen Dolan компилятор bf, генерирующий x86-код, обернутый в готовый к выполнению elf-файл [для Linux].
SedChess – шахматы, реализованные Евгением Степанищевым из Казани; больше 1000 строк. Описание можно найти в habr/191006.
sedtris – реализация игры «тетрис», выполненная Юлией Йомантайте (из Нью-Йорка). У меня есть производный репозиторий, «fork», с небольшим улучшением (добавлен ГПСЧ на основе клеточного автомата, реализующего «правило 30» по-Вольфраму).
https://gist.github.com/xsot/99a8a4304660916455ba2c2c774e623a – написанная Wei Heng (aka xsot) программа решения лабиринтов (т.е. поиска пути, в данном случае обходом в ширину).
http://laurent.le-brun.eu/pub/path.sed – другая, более минималистичная, реализация обхода лабиринтов, написанная Laurent Le Brun.
http://codegolf.stackexchange.com/a/49442 – умножение чисел на sed.
quine.sed из «музея квайнов» – квайн на sed; самостоятельно его написать не так-то и просто, но у его автора, Tsuyusato Kitsune (см. http://quine.codes/), богатый опыт в квайноводстве (им были написаны квайны для более чем 260 (да, двухсот шестидесяти [или даже двухсот шестидесяти семи, кажется]) разных языков программирования).
https://github.com/mame/quine-relay – «итеративный» многоязыковой квайн, или цепной квайн (авторы: Yusuke Endoh, даже написавший книжку, на японском, об эзотерическом программировании вообще и квайнах в частности; и hirekoke), а именно программа, написанная на одном языке, при запуске выдающая программу на другом языке, в свою очередь печатающую программу на третьем, и т.д., пока последняя программа не напечатает снова самую первую. Конкретно этот многоязыковой квайн, пробегает при своей работе 128 языков (на начало 2020 года), в том числе и sed.

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

(Термины «итеративный/цепной квайн», «поликвайн», «мультиквайн» нельзя назвать общепринятыми и они используются здесь просто чтобы дать соответствующим понятиям подходящие имена; официальной квайнологической терминологии, боюсь, пока нет.)
https://github.com/jinchizhong/sed-snake – игра «змейка»; автор – Chizhong Jin.
https://github.com/ValeriyKr/sfb – sed-реализация игры «flappy bird»; автор – Валерий Киреев.
https://github.com/ValeriyKr/gravity-defied – ещё одна sed-игрушка, от Вольдемара.
https://github.com/jinchizhong/sed-nqueens – классическая задачка о расстановке нескольких ферзей на шахматной доске. Обычно решается с помощью обхода в глубину, что подразумевает использование рекурсии, поддержки которой в sed нет (и её как обычно приходится эмулировать с помощью искусственного ~~интеллекта~~ стека и команды b).

Неболь­шая кол­лек­ция sed-скриптов.

Содер­жа­ние:

Неце­ле­вое исполь­зо­ва­ние поточ­ного редак­тора.

Мини­ре­по­зи­то­рии

Скрипты дру­гих авто­ров.

Небольшая коллекция sed-скриптов.

Содержание:

Нецелевое использование поточного редактора.

Минирепозитории

Скрипты других авторов.