Написание однострочников в Python всегда было довольно интересным для меня, и однажды я заинтересовался - а любой ли алгоритм возможно реализовать всего в одну строчку Python кода ?
Оказалось - да!
Немного теории
Исполнитель называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию, и наоборот. То есть, чтобы доказать что в одну строку на Python можно написать какой угодно код, необходимо доказать Тьюринг-полноту однострочных программ на python. Как это сделать ?
Довольно простой способ, который я и выбрал - имитировать другую исполнительную систему, для которой уже доказано, что она обладает полнотой по Тьюрингу. Например, я мог бы написать интерпретатор языка PHP, который, естественно, является Тьюринг-полным, как и почти все существующие языки программирования. В этом, однако, нет никакой необходимости, ведь есть гораздо более простые системы, полные по Тьюрингу. Например, клеточный автомат, под названием Правило 110.
Чёткие правила данного автомата изложены в Википедии по ссылке здесь.
Вкратце, мы имеем бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния (0 и 1), будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей и рассчитывается по определённому несложному алгоритму.
Получается, что если мы сможем написать в одну строчку этот клеточный автомат, значит и любой другой алгоритм написать в одну строчку тоже будет возможно.
Реализация
Сразу уточню, что символ ";" я считал началом новой строки, чем он по сути и является, иначе задача превращается в тривиальную.
Итак, опредилившись с тем что же именно я собираюсь написать, я, недолго думая, запустил VSCode и... И завис. Потому что неясно было что писать. Ясно было, что нужен цикл while, ввод начального состояния, которое нужно как-то обработать, действия над ним в цикле, Кроме того, цикл надо ещё как-то остановливать, если состояние системы стабилизировалось и больше не меняется.
Как это всё уместить в одну строчку, было не очень понятно. Например даже результат вызова input() нельзя никак занести в обычную в переменную и потом работать с ним дальше одной строкой.
# А не работает так!
while (a=int(input()) or a!=0):print(a)
На некоторое время я оставил свою идею, пока, читая хабр, вдруг не наткнулся на следующую мысль - для объявления переменной в одну строку в python можно использовать глобальные переменные. Например, вот так:
#Объявление
globals().update({"a":0})
#Получение значения
globals().get("a")
# Простейший цикл while
while (globals().update({"a":int(input())}) or globals().get("a")!=0):print(globals().get("a"))
В этом примере мы также пользуемся тем, что исполняемая функция globals.update() возвращает None, а условие (None or value) почти всегда вернёт value, кроме некоторых случаев. То есть, по факту, условный оператор or можно использовать, чтобы встраивать любой исполняемый код в условие. Разумеется, можно написать сколько угодно ... or ... or ... подряд, так что задача существенно упрощается.
В целом, достаточно сложная задача и была решена при помощи этих двух приёмов - глобальные переменные и фиктивный условный оператор. Исходники лежат здесь, если кому-то интересно, можно посмотреть, а сейчас я немного распишу как итоговый код работает.
https://github.com/Thane784/rule_110
Куда же тыкать ?
Основной файл - code.py Там, правда есть некоторые проблемы с выводом - для человека он не очень читаем. Можно запустить файл show.py , там цикл искусственно ограничен 25 итерациями и всё видно нагляднее.
Итоговый код и как он работает
Итак, нам необходимо каждый проход цикла проверять состояние системы и заканчивать выполнение программы, если оно такое же, как предыдущее(состояние стабилизировалось).
Для этого заведем две глобальные переменные "s" (string) и "l" (last). Да, я знаю, что s и l - не очень хорошие названия для переменных, но для одноразового кода, который никто в дальнейшем поддерживать не будет, думаю нормально.
Сперва, мы должны запросить на вход начальное состояние, причем сделать это лишь один раз. Также мы будем сравнивать текущее состояние системы с предыдущим. Для этого используем следующий код:
# Записываем нач. состояние в переменную,
# выводим его же в консоль,
# причём только если предыдущего состояния нет,
# то есть на первой иттерации цикла,
# используем оператор or для исполнения кода.
# По факту в сравнение пойдет лишь globals().get("s")),
# которое мы и сравниваем с предыдущим состоянием globals().get("l"))
while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): print('')
Далее, уже в теле цикла мы объявляем фиктивную переменную a которой присваиваем значение длинного длинного сравнения через оператор or. На самом деле, оператор сравнения здесь нужен чтобы выполнить большое количество исполняемого кода, в котром каждая вызываемая функция вернёт None. Возможно, можно было реализовать подобное более красиво, но это самое быстрое рабочее решение, которое пришло мне в голову.
#Скелет
while last_code: a = (func1() or func2() or func3() or 1)
В полном же варианте нарощенном на данный скелет мы обновляем l (предыдущее состояние), проходим один цикл клеточного автомата, перезаписывая переменную s, и выводим новое состояние.
Для хранения состояния используем строку, постепенно обрабатывая её, собираем массив, который содержит новое состояние. Этот массив затем приводим к строке при помощи функции ''.join() и перезаписываем глобальную переменную s. Скорее всего, можно было бы обойтись без массива, но оптимизация здесь не слишком важна. Также, при определённых условиях расширяем наблюдаемую область(если в результате работы алгоритма "оживились" клетки, ранее нами не отслеживаемые(поле, естесственно бесконечно), откуда кстати и проблемы с выводом - довольно скоро поле становится ОЧЕНЬ большим). Большую часть кода занимает вычисление следующего состояния на основе предыдущего, это просто множество условий if elif else записанных в одну строчку.
Вот так выглядит финальный код.
while (( ( globals().update({"s": input()}) or print(globals().get("s"))) if globals().get("l") == None else None) or globals().get("s")) != globals().get("l"): a = ( globals().update({"l": (globals().get("s"))}) or globals().update({"s": (''.join(['1' if globals().get("s")[0] == '1' else '']+[('0' if (n != 0 and n!=(len(globals().get("s"))-1) and (globals().get("s")[n-1:n+2] == '000' or globals().get("s")[n-1:n+2] == '100' or globals().get("s")[n-1:n+2] == '111') ) else '0' if (n == (len(globals().get("s"))-1) and ( ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '00' or ((globals().get("s")[-2] if len(globals().get("s"))>1 else '0')+globals().get("s")[-1]) == '10') ) else '0' if (n == 0 and globals().get("s")[0]+(globals().get("s")[1] if len(globals().get("s"))>1 else '0') == '00' ) else '1') for n in range(0,len(globals().get("s")))]) )}) or (print(globals().get("s")) if globals().get("s") != globals().get("l") else None) or 1)
Что же в итоге ?
Итак ! Мы написали в одну строчку Тьюринг-полную систему, чем доказали, что однострочники на python обладают Тьюринг-полнотой. Что же это значит ? Это значит, что в одну строчку python кода можно написать всё что угодно ! Даже Windows 11 или ядро Linux.
Правда, скорее всего, код получится слегка нечитаемым да и дебаггинг будет затруднён...)
P. s.
Автор знаком с python на любительском уровне и не пишет на нём ничего серьёзного, поэтому прошу простить, если проглядел какие-то очевидные вещи и возможности. Автор понимает, что написание подобного кода в реальном проекте, чревато некоторым непониманием со стороны коллег и не призывает никого повторять изложенные здесь эксперименты)
Комментарии (22)
dimaaannn
13.11.2021 15:02+5На СИ-подобных языках можно вообще полностью удалить переносы строк из кода.
Становится ли код после этого однострочным - вопрос философский.
Thane784 Автор
13.11.2021 15:12+3В python тоже можно разделять код знаком ";" и в этом случае задача резко упрощается. Однако, вряд ли можно уже считать это одной строкой кода. Хотя формально строка одна, но всё-таки для интерпретатора их уже несколько. Любопытная же гибкость же языка в том, что можно не прибегать к этому средству и записать любой код в "настоящую" одну строку. Впрочем, что считать "настоящим" и "не настоящим", вопрос и вправду философский)
CaptainFlint
13.11.2021 17:50+3Не все строки можно объединить таким способом. Скажем, условный оператор ругается, если обнаруживает else в той же строке, даже отделённый точкой с запятой.
netch80
14.11.2021 16:53+1> На СИ-подобных языках можно вообще полностью удалить переносы строк из кода.
После того, как убраны все директивы препроцессора. А это ой неполезно.
arthuriantech
13.11.2021 16:07+5Как это всё уместить в одну строчку, было не очень понятно. Например даже результат вызова input() нельзя никак занести в обычную в переменную и потом работать с ним дальше одной строкой.
C моржовым оператором вполне возможно на 3.8+
while ((a := int(input())) or a != 0): print(a)
stan_volodarsky
13.11.2021 16:10+6eval(compile(<строка с вашей любимой программой на Питоне>, '', 'exec'))
stan_volodarsky
13.11.2021 16:23+4lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
Факториал совместимый с комбинатором (или любая рекурсивная функция):
lambda f: lambda n: (1 if n<2 else n*f(n-1))
Запускаем:
@>>> (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(args))))(lambda f: lambda n: (1 if n<2 else nf(n-1)))(10)
3628800Лямбда-исчисление позволяет записать любой алгоритм в одну строку.
MentalBlood
13.11.2021 17:50+2Вот это круто, примерно такого ждал от статьи, когда прочитал название)
zede
13.11.2021 19:57+2Как раз хотелось написать про лямбды)
Хотя реализовать хотя бы комбинатор неподвижной точки на питон-лямбдах будет уже страшно смотреться)
А вообще лучший мануал по лямбдам на одну ссылку ниже в гугле
stan_volodarsky
13.11.2021 20:13На питон-лямбдах достаточно сделать интерпретатор нормальной лямбда-нотации. Программа будет состоять из небольшого интерпретатора и большого текста собственно программы. Нормально?
nickolaym
13.11.2021 22:30+2Не, ну это мошенничество. Запихать несколько стейтментов - дурное дело нехитрое.
Надо в один стейтмент.
Про лямбды и рекурсию на Y уже написали.
Можно посмотреть в сторону генераторов. Но для этого нам понадобятся бесконечные циклы, а за ними надо слазать в модуль itertools.
А чтобы импортировать модуль, есть не только стейтмент import, но и функция
__import__
gearbox
14.11.2021 12:08А чем стрелка Пирса или штрих Шеффера не угодили? Да и банальная связка сложения и умножения уже Тьюринг полные (или являются базисом, если по умному). Можно также сэмулировать команду mov x86 архитектуры, тоже Тьюринг полная, да.
Но вообще прикольно получилось, спасибо.
vda19999
14.11.2021 17:12Про написание ОС в одну строку на Питоне вы погорячились все же. Её и во много строк на Питоне написать невозможно.
realchel
14.11.2021 17:12-4молодёжь читай Чистый код и другие книги автора, и выкиньте из головы подобную однострочную чушь.
JQuery567
15.11.2021 00:29у меня какой-то не тот питон, или тут очередная статья с неработающим кодом?
Python 3.8.10 (tags/v3.8.10:3d8993a, May 3 2021, 11:48:03) [MSC v.1928 64 bit (AMD64)] on wi n32 Type "help", "copyright", "credits" or "license" for more information. >>> >>> globals.update({"a":0}) Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'builtin_function_or_method' object has no attribute 'update' >>> globals() {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_frozen_ importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>} >>> z = 8 >>> globals() {'__name__': '__main__', '__doc__': None, '__package__': None, '__loader__': <class '_frozen_ importlib.BuiltinImporter'>, '__spec__': None, '__annotations__': {}, '__builtins__': <module 'builtins' (built-in)>, 'z': 8} >>> dir(globals) ['__call__', '__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge_ _', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__l t__', '__module__', '__name__', '__ne__', '__new__', '__qualname__', '__reduce__', '__reduce_ ex__', '__repr__', '__self__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '_ _text_signature__']
szobin
15.11.2021 01:04+1Python 3.8.10 (tags/v3.8.10:3d8993a, May 3 2021, 11:48:03) [MSC v.1928 64 bit (AMD64)] on win32 Type "help", "copyright", "credits" or "license" for more information. >>> globals().update({'a': 0}) >>> globals().get('a') 0
нужно скобочки к
globals()
добавить. финальный код у автора уже написан правильно
erdbeeranke
17.11.2021 00:11+1а условие (None or value) почти всегда вернёт value, кроме некоторых случаев.
какие такие случаи есть?
Thane784 Автор
17.11.2021 14:06Не очень хорошо знаю такие тонкости, но было предположение что с некоторыми значениями (False,0,[],'' и т.д) может работать некорректно.
Сейчас немного протестировал (python 3.8.10), с (None or value) проблем действительно не нашёл(Не значит ещё что их нет) ), а вот если мы напишем (value or None), то возможны неожиданные результаты работы.
Например, print(0 or None) возвращает None, а не ноль как нам хотелось бы.
monane
Вот примерно за такие шутки меня и обзывают погромистом. А скобочек мало, да мало