Написание однострочников в 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)


  1. monane
    13.11.2021 14:43
    +5

    Вот примерно за такие шутки меня и обзывают погромистом. А скобочек мало, да мало


  1. dimaaannn
    13.11.2021 15:02
    +5

    На СИ-подобных языках можно вообще полностью удалить переносы строк из кода.

    Становится ли код после этого однострочным - вопрос философский.


    1. Thane784 Автор
      13.11.2021 15:12
      +3

      В python тоже можно разделять код знаком ";" и в этом случае задача резко упрощается. Однако, вряд ли можно уже считать это одной строкой кода. Хотя формально строка одна, но всё-таки для интерпретатора их уже несколько. Любопытная же гибкость же языка в том, что можно не прибегать к этому средству и записать любой код в "настоящую" одну строку. Впрочем, что считать "настоящим" и "не настоящим", вопрос и вправду философский)


      1. CaptainFlint
        13.11.2021 17:50
        +3

        Не все строки можно объединить таким способом. Скажем, условный оператор ругается, если обнаруживает else в той же строке, даже отделённый точкой с запятой.


    1. netch80
      14.11.2021 16:53
      +1

      > На СИ-подобных языках можно вообще полностью удалить переносы строк из кода.

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


  1. arthuriantech
    13.11.2021 16:07
    +5

    Как это всё уместить в одну строчку, было не очень понятно. Например даже результат вызова input() нельзя никак занести в обычную в переменную и потом работать с ним дальше одной строкой.

    C моржовым оператором вполне возможно на 3.8+

    while ((a := int(input())) or a != 0): print(a)


  1. stan_volodarsky
    13.11.2021 16:10
    +6

    eval(compile(<строка с вашей любимой программой на Питоне>, '', 'exec'))


  1. stan_volodarsky
    13.11.2021 16:23
    +4

    Y Combinator :

    lambda 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

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


    1. MentalBlood
      13.11.2021 17:50
      +2

      Вот это круто, примерно такого ждал от статьи, когда прочитал название)


    1. zede
      13.11.2021 19:57
      +2

      Как раз хотелось написать про лямбды)

      Хотя реализовать хотя бы комбинатор неподвижной точки на питон-лямбдах будет уже страшно смотреться)

      А вообще лучший мануал по лямбдам на одну ссылку ниже в гугле


      1. stan_volodarsky
        13.11.2021 20:13

        На питон-лямбдах достаточно сделать интерпретатор нормальной лямбда-нотации. Программа будет состоять из небольшого интерпретатора и большого текста собственно программы. Нормально?


  1. nickolaym
    13.11.2021 22:30
    +2

    Не, ну это мошенничество. Запихать несколько стейтментов - дурное дело нехитрое.

    Надо в один стейтмент.

    Про лямбды и рекурсию на Y уже написали.

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

    А чтобы импортировать модуль, есть не только стейтмент import, но и функция __import__


  1. gearbox
    14.11.2021 12:08

    А чем стрелка Пирса или штрих Шеффера не угодили? Да и банальная связка сложения и умножения уже Тьюринг полные (или являются базисом, если по умному). Можно также сэмулировать команду mov x86 архитектуры, тоже Тьюринг полная, да.

    Но вообще прикольно получилось, спасибо.


  1. Qubi
    14.11.2021 17:12

    Зачем проверять Тьюринг полноту, когда можно проверит МНР?

    Проще же


  1. vda19999
    14.11.2021 17:12

    Про написание ОС в одну строку на Питоне вы погорячились все же. Её и во много строк на Питоне написать невозможно.


  1. realchel
    14.11.2021 17:12
    -4

    молодёжь читай Чистый код и другие книги автора, и выкиньте из головы подобную однострочную чушь.


  1. 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__']
     


    1. szobin
      15.11.2021 01:04
      +1

      Python 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() добавить. финальный код у автора уже написан правильно


      1. Thane784 Автор
        15.11.2021 08:32

        Спасибо, исправил.


      1. JQuery567
        15.11.2021 12:51

        спасибо


  1. erdbeeranke
    17.11.2021 00:11
    +1

    а условие (None or value) почти всегда вернёт value, кроме некоторых случаев.

    какие такие случаи есть?


    1. Thane784 Автор
      17.11.2021 14:06

      Не очень хорошо знаю такие тонкости, но было предположение что с некоторыми значениями (False,0,[],'' и т.д) может работать некорректно.

      Сейчас немного протестировал (python 3.8.10), с (None or value) проблем действительно не нашёл(Не значит ещё что их нет) ), а вот если мы напишем (value or None), то возможны неожиданные результаты работы.

      Например, print(0 or None) возвращает None, а не ноль как нам хотелось бы.