Как стать автором
Обновить

Комментарии 46

Проверим, пустой ли рюкзак. Если пустой, задача решена, тушёнки нет. Иначе вынимаем из рюкзака первый попавшийся предмет.

Вы точно сами понимаете, что такое рекурсия?

Я точно сам понимаю, что такое рекурсия. В процитированных вами полутора терминальных ветвях алгоритма её нет.

Что вы хотели сказать своим вопросом?

Вы сами написали, что это пример рекурсии, понятный даже ребёнку.

На мой скромный взгляд, в рюкзаке должен быть рюкзак. В котором (внезапно!) может быть и тушёнка. Или снова рюкзак, etc.

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

Рекурсивен в данном случае алгоритм наших действий, а не структура рюкзака.

Здрасьте-приехали. А как же «решение задачи через сведение её к самой себе»? Что-то в копошении в рюкзаке нет подобия задачи «самой себе». Простой поиск.

Задача поиска тушёнки в рюкзаке с N предметами сводится к задаче поиска тушёнки в рюкзаке с N-1 предметами, если первый вынутый предмет не тушёнка и есть ещё предметы. Там же код написан ниже.

Так-то да. Но метафора с рюкзаком по-прежнему кажется мне неудачной.

По-моему, метафора с рюкзаком обладает двумя полезными свойствами:

  1. Это реальная жизненная ситуация, которая точно показывает, что происходит, когда мы вынимаем предметы из рюкзака по одному.

  2. После понимания этой ситуации в жизни она позволяет написать рекурсивный код, понятный ребёнку, явным образом отображающий рассмотренные ранее действия.

Конечно, можно было бы происходящее с тем же успехом объяснить и циклом, поскольку простая рекурсия вообще эквивалентна циклу. В этом смысле нельзя сказать, что поиск в рюкзаке сам по себе рекурсивен. Но он может быть описан рекурсивным алгоритмом, что я и имел в виду.

Мне кажется, для «понимания ребёнком» гораздо нагляднее работают метафоры матрёшки или рекурсивного вызова по вытягиванию репки. Всё-таки, это точнее «по духу» рекурсии.

Ладно, я понял вас, рюкзак – так рюкзак.

Вытягивание репки в моём понимании вообще не является примером рекурсии, это суперпозиция семи разных функций.

Что касается матрёшки, то для меня этот пример не очень очевиден. Видимо, у вас в голове рекурсия каким-то образом разворачивается в пространстве (то же и в вопросе с фракталом), а у меня – во времени.

Невероятно интересно (я искренне). Никогда не думал об этом в таком ключе. Ради одной этой формулировки стоило затеять эту ветвь обсуждения.

С матрёшкой в качестве примера получилась бы абсолютно прекрасная статья, если взять матрёшки 90-х, с генсеками и т.п. (Ленин, в нём Сталин и так далее до Горбачёва). А на КДПВ поставить кадр из Ширли-Мырли с Табаковым – "Я этого [] в Химках видел. Деревянными членами торгует!" (Деревянные члены тут – это матрёшки с членами ПолитБюро)

Да не, приемлемо. Тем более на лиспе, где основная структура данных – пара car.cdr, и представление рюкзака будет именно таким: в car первый предмет, в cdr рюкзак со всеми остальными.

Upd: Язык диктует мышление. Было бы интересно, как тот же автор написал бы эту статью, если бы был привычен к простой императивщине. Или, напротив, если бы для него родным языком был Хаскель (ленивое вычисление сильно меняет мышление – можно использовать бесконечные списки и всякое такое, что сильно упрощает и сокращает код, делая его очень читабельным, зато оценить требования по времени и памяти на порядок сложнее).

НЛО прилетело и опубликовало эту надпись здесь

Довольно сложно проинтерпретировать такое понимание в реальном мире.

Рюкзак — это просто мутабельная ссылка на иммутабельный список.

Почему это? Если рюкзак из статьи, то как раз содержимое изменяется, а рюкзак тот же.

НЛО прилетело и опубликовало эту надпись здесь

Сэр, не желаете ли с рюкзаком попутешествовать по этой блок-схеме? ;)

Мне кажется, более удачную иллюстрацию отличия одного от другого в мире вряд ли найдёте..

Схема отличная! Но, справедливости ради, на ней нарисовано понятие фрактала.

Эмммм... Фрактал ведь и рядом не стоял с рекурсией, да? Только рюкзак, только хардкор.

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

Спасибо за этот коммент, кстати: что-то в словах "бесконечное самоподобие" вызвало сомнения (ну, я просто помню, что это не основной признак фрактала, название как бы намекает) и я стал гуглить "несамоподобные фракталы". Результаты оказались весьма интересными, вплоть до утверждения, что большинство фракталов не является самоподобными.

У Вас в статье все правильно описано, кроме примера с рюкзаком - это классический плоский цикл с пост-условием. Как агитплакат на чиновничьи деньги в современном мире - плакат “за Родину”, а картинка из Интернета сами понимаете с кем.

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

Да уж, дочитав до первой вставки "псевдокода на языке Лисп" я понял, что эту вставку никто никогда не поймет, если он не изучал тему символьного программирования ранее, а кто изучал, уже, скорее всего, будет иметь хотя бы приблизительное представление о том, что такое рекурсия. Чтобы понять, что в ней написано, надо уже знать, что такое S-выражения, скобочная нотация, defun, cond, null, и t. И даже если до этих перечисленных понятий еще можно как-то догадаться, то что такое car и cdr - надо только знать. Что ж, вот как они расшифровываются: "car" расшифровывается как "content of address register", а "cdr" - "content of decrement register", а семантика их, соответственно, исторически значит "первый элемент списка" и "остаток списка". Скорее всего, в первых LISP-машинах в этих регистрах хранились соответствующие указатели (но это не точно).

Справедливое замечание, но я постарался семантику объяснить сразу после кода.

Язык Лисп нравится мне тем, что он очень формален и математичен. Код программы сам представляет собой те самые списки символов, которые он и обрабатывает. Этим он по своей глубокой структуре подобен машинному коду, позволяя программам полностью рефлектировать самих себя. В этом тоже есть рекурсия :)

Всё-таки другие языки по сравнению с Лиспом уродливы для объяснения вопросов вычислимости. Хотя гораздо более практичны.

Хе-хе, вот с последним утверждением можно поспорить – см. вторую теорему Чёрча-Россера, она же теорема о стандартизации.

Корявый пересказ с минимумом терминов: если записать какое-то лямбда-выражение (лисповская запись вполне подойдёт: первый элемент списка – функция, дальше аргументы) и это выражение в принципе можно вычислить – то есть определённый порядок вычисления ("нормальный порядок редукции"), который точно подойдёт. Но Лисп использует не его, а аппликативный порядок.

Пример: пусть есть функция, которая возвращает бесконечный список чисел. Надо найти, в какой позиции встречается число 13. На Лиспе такое не прокатит (ну, в лоб), для Хаскеля – просто ищем по результату функции)))

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

Надо сказать, что и в Common лиспе с этим не то чтобы совсем здорово на практике, но как концепция срабатывает. И есть Scheme.

Забавно, но Хаскель только и занимается что вычислением тела программы). Такой трюк, чтобы в рамках чисто функционального языка (без side-эффектов, присваивания и т.п.) взаимодействовать с внешним миром: просто пишем функцию, которой можно скормить в качестве аргумента что-то из внешнего мира и получить как результат новую функцию.

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

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

Кстати, забавно, что некоторые наиболее идеологические чистые трансляторы Лиспа оказалось невозможно портировать на Apple Silicon из-за неотключаемого W^X.

Ну, такая штука на Хаскеле бессмысленна, проблема будет не в том, чтобы мемоизировать, а в том, чтобы отключить обойти имеющуюся мемоизацию).

Ну а в плане работы с исходниками – теоретически, можно было бы преобразовывать thunks (недовычисленные хаскелевские выражения) обратно в код. По сути, они очень похожи на лисповские выражения, только порядок вычисления другой (что позволяет, к примеру, сделать if и cond обычными функциями, а не специальными конструкциями, как в lisp)

НЛО прилетело и опубликовало эту надпись здесь

А что такое формальная грамматика, как не порождающая сама себя последовательность символов?

Конечно, на практике обычно отделяют порождаемый код от исполняемого. Но в теоретических моментах полезно иметь удобную абстракцию.

Код реализации Лиспа, написанный на Лиспе, занимает две страницы. Я помню, ещё на 8-разрядной машине работал с транслятором Лиспа, у которого загрузочный модуль был килобайт эдак 30, из которых значительную часть занимала реализация большинства функций просто в виде текстового лисповского кода, определяющего их через основные функции. Язык определяет сам себя.

В практическом плане это позволило окончательно зафиксировать стандарт Лиспа в 1994 году и все дальнейшие изменения проводить библиотеками в исходном коде.

НЛО прилетело и опубликовало эту надпись здесь

Она не порождает сама себя. Её порождают некоторые правила. И эти правила вполне себе можно удобно описывать и в негомоиконных языках.

Эти правила в общем случае могут сами состоять из используемых грамматикой символов. В связи с чем строится понятие самоприменимых грамматик.

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

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

Очень круто, но ≥99.9% программистам в ≥99.9% ситуаций не нужно.

На самом деле, вся идеология работы в Лиспе построена на динамической модификации кода и расширении языка проблемно-ориентированными конструкциями.

НЛО прилетело и опубликовало эту надпись здесь

Если вы внимательно посмотрите на доказательство теоремы останова, оно как раз оперирует написанием программы, анализирующей свой собственный код. Само доказательство написано на метаязыке, так как доказательство - это не алгоритм, но используемый в нём алгоритм самоприменяется. И оно оперирует чисто синтаксическим алгоритмом, вынося семантику останова, если так можно выразиться, в свободный параметр синтаксиса.

Любая же динамическая модификация затрудняет рассуждения о коде.

Чего тут думать, тут трясти надо. В смысле, динамический подход построен на автоматическом анализе и преобразовании кода.

Проблемно-ориентированные конструкции можно добавлять и в не-лисповых языках, где статичнее некуда, и при этом синтаксис не будет вырвиглазным, а будет очень близок к математической нотации:

Посмотрите, как происходит разработка на Лиспе. Я примерно об этом говорю:

https://youtu.be/kyXriUBppMk

Наша дискуссия, однако, напомнила мне "Анафем" Стивенсона.

НЛО прилетело и опубликовало эту надпись здесь

Там обычный диагональный метод

Диагональный метод является только заключительным шагом доказательства. Основная идея – это как раз выяснение значений, которые вы назвали Table [i, j], предполагающее, что программа анализирует исходный текст программ, в том числе и самой себя.

(нам совершенно наплевать, как он работает)

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

Ну и почему для нас вообще важна эта программа и откуда она возникла в доказательстве? Потому что она представляет собой неподвижную точку. А дальше уже от понятия неподвижной точки идём к самоприменимым грамматикам.

Здесь нет ничего принципиально нового по сравнению с доказательством, например, несчётности множества вещественных чисел.

Множество вещественных чисел вполне представимо актуально. Множество алгоритмов конструируется только потенциально. Хотя множество цепочек с текстами программ актуально.

Я не люблю смотреть (тем более, видео на час в 360p/10fps), я люблю читать. Можно почитать исходники, где строится адекватный, удобный и читабельный eDSL для какой-либо данной задачи?

Вопрос-то здесь не в исходниках, а в технологии процесса программирования. Конечно, перемотав ролик в конец вы увидите исходники (я его, впрочем, до конца не смотрел), но дело не в этом.

НЛО прилетело и опубликовало эту надпись здесь

Множество алгоритмов является подмножеством (собственным или нет — здесь неважно) множества текстов программ.

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

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

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

Например, определим язык Лисп++, отличающийся от Лиспа всего двумя деталями:

(1) Программа на Лисп++ состоит ровно из одного S-выражения (это чисто стилистическое преобразование, которое не умаляет возможностей Лиспа, так как любую последовательность S-выражений можно объединить в одно при помощи PROGN).

(2) Грамматика Лисп++ содержит правило, согласно которому к любой программе необходимо добавить в конец правую скобку.

Таким образом, язык Лисп++ будет иметь следующие особенности:

a) любая программа на Лисп++ имеет бесконечную длину, так как заканчивается бесконечным количеством правых скобок, возникающих от бесконечно рекурсивного применения правила (2);

б) на Лисп++ можно написать любую программу, которую можно написать на Лисп, и она будет исполнена и завершится за конечное время, если это происходит с прообразом программы на Лиспе (на самом деле транслятору Лисп++ в силу свойства (1) неинтересны символы после S-выражения).

Очевидно, что к языку Лисп++ неприменимо доказательство теоремы останова, хотя в смысле способности к останову он ничем не отличается от языка Лисп.

НЛО прилетело и опубликовало эту надпись здесь

> А никто ведь не обещал, что любой алгоритм можно так сериализовать.

Обещали по любому определению языка записи алгоритмов.

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

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

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

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

НЛО прилетело и опубликовало эту надпись здесь

Чтобы понять рекурсию нужно понять рекурсию.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации