Встречайте новый язык программирования — Sifflet 1.0

> Вот честное слово, я ещё ни разу не видел человека, который бы не понимал, что такое рекурсия.

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

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

Такое чувство, что многие не понимают, что понимание рекурсии не приравнивается к умению представить задачу в рекурсивном виде.

Тред конечно замечательный, в стиле ЛОРа.

А объясните мне, уважаемые коллеги по генерации каментов, что мне SABJ даст?
Допустим на секунду что я кодер-императивщик, к тому же самоучка. И рекурсию видел пару раз при обходе папочек :) и может иерархических структур данных еще парочку.

А какие навыки и для примерно каких целей мне даст эта штука?

Вдогонку. И вот это можно расшифровать?

Такое чувство, что многие не понимают, что понимание рекурсии не приравнивается к умению представить задачу в рекурсивном виде.

Эта штука даст тебе просветление.

> Эта штука даст тебе просветление.

Хм. Как Готаме Будде? А поподробнее?

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

«Война и мир» в виде комикса.

>мммм, новый велосипед?

Причем с треугольными колесами.

>не поверишь, но найду. покажи мне язык, который не имеет циклов.

Daedalus. На нем скрипты для «Готики» пишутся. Циклов в нем нет.

>Опять же, изначальный FORTRAN, ЕМНИП, никаких циклов не имел.

Имел. Просто в FORTRAN IV появились новые виды циклов.

Эта штука даст тебе халявный stack overflow.

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

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

Приводи примеры таких языков.

>Более менее согласен (но только если привязаться к тому как сделано в GHC), только вот мне кажется неправильно называть полноправные функции «сахаром» (тогда что не сахар?):

Сахар, это то, для чего есть очевидное преобразование к основным конструкциям языка. В хаскеле много таких вспомогательных конструкций, облегчающих чтение программы, но это не значит, что из за DO-синтаксиса или не дай БГ, forM вдруг в хаскеле появилась императивщина или циклы.

Обратная сторона сахара, если программист наивно принимает сахар за базовую конструкцию, не понимая смысла преобразования этого сахара в базовые конструкции, то жди беды. Баги будут эпичные.

Почему мы не можем определить этот foldr как последовательность инструкций для State Machine (Тьюринг-Полной)?

можем, да не обязаны. Это вопрос имплемента, но не языка.

упоротый? Например, хаскель.

ты научишься выражать не ход исполнения, но описывать цель оного.

Другими словами «Метод Илоны Давыдовой в программировании». «Учись программированию во сне», «Учись программированию играя»...

«Прочти и раскрась»

Вообще, генерить схемокод из блок-схем - это круто, но скриншоты выглядят странновато.

Сахар, это то, для чего есть очевидное преобразование к основным конструкциям языка. В хаскеле много таких вспомогательных конструкций, облегчающих чтение программы, но это не значит, что из за DO-синтаксиса или не дай БГ, forM вдруг в хаскеле появилась императивщина или циклы.

Ок, буду иметь ввиду.

можем, да не обязаны. Это вопрос имплемента, но не языка.

Это тоже хорошо.

Но вот тут у меня опять непонимание:

ты научишься выражать не ход исполнения, но описывать цель оного.

Выражение задачи в циклах/присваиваниях это описание хода выполнения. Но решение в виде рекурсии - это описание хода редукций, фактически того же выполнения (просто не в парадигме SM а в парадигме LC). ``выражать не ход исполнения, но описывать цель оного" это если бы мы не использовали ни циклы, ни рекурсию, а выразили бы функцию через fold. Разве не так?

> Такое чувство, что многие не понимают, что понимание рекурсии не приравнивается к умению представить задачу в рекурсивном виде.

Истину глаголешь, анон. Вот я рекурсию видел и понимаю, а применить к месту не могу. :(

>Такое чувство, что многие не понимают, что понимание рекурсии не приравнивается к умению представить задачу в рекурсивном виде.

Опять уклонение. Изначальный тезис, с которым я спорил, звучал как «А по-моему рекурсия сложная штука для понимания». Про способность решать задачи речи не было, только про понимание.

тьюринг

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

> С помощью условий и переходов можно организовать циклы, но от этого условия и переходы не превращаются в новую сущность:)

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

>>изначальный FORTRAN, ЕМНИП, никаких циклов не имел.

Имел.

Освежил память - да, как и в случае с Бейсиком упустил из виду параметрический цикл. Всё же, под циклом я в глубине души подразумевал условные циклы. А они только в FORTRAN 77 появились.

>Приводи примеры таких языков.

Hope?

>Вроде как прыжок назад (на инструкцию, которая уже ранее выполнялась) как правило является циклом.

Напомню контектс: «покажи мне язык, который не имеет циклов»

Иметь циклы и уметь их организовывать иными синтаксическими средствами - это разные вещи.

«Иметь циклы» в моём восприятии означает иметь соответствующие конструкции в синтаксисе.

>>Ой, а давайте дружно закопаем все эти новые языки програмирования

предлагаю закопать всех олдфагов, а то орут «закопать! ненужно!» на всё «принципиально новое», а спорить с ними трудно, и потому что опытные

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

ну в LLVM используется SSA-представление переменных, и как-то обходятся с phi конструкциями

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

>предлагаю закопать всех олдфагов, а то орут «закопать! ненужно!»

Как раз, олдфаги так никогда не орут. Ибо они «этих новых языков программирования» за свою жизни очень много встречали.

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

а спорить с ними трудно, и потому что опытные

И спорить с такими ньюбами смысла нет. Они просто не поймут, о чём идёт спор :) Так что они или со временем станут олдфагами, всегда открытыми для чего-то нового, или уйдут со сцены :)

Туда же Clean еще запишите.

Теперь верю. Но все равно оно превращается в рекурсию, которую компилятор разворачивает в цикл... Короче, костыль.

Вот три примера.

Запись в терминах вычислителей:

1) reverse как цикл:

(defun reverse. (list)
  (let (new-list)
    (dolist (e list)
      (push e new-list))
    new-list))

2) reverse рекурсивно:

revers (x:[]) = [x]
revers (x:xs) = (reverse xs) ++ [x]

Декларативная запись (тут _нет_ вычислителей):

reverss list = foldr (++) [] list

Если принципиальной разницы между 1 и 2 нет, то отличие 3 от и 1 и 2 - просто принципиальное.

В ghc, например, это циклом не будет. Однако и лишнего места в стеке тоже не сожрет.

> reverss list = foldr (++) [] list

Прекрати бредить уже, а? Это даже не reverse, это concat.

Теперь верю. Но все равно оно превращается в рекурсию, которую компилятор разворачивает в цикл... Короче, костыль.

Тут было замечено, что некоторые реализации не используют рекурсию (в любом случае - это возможно, я проверял :)) а транслируют напрямую в императив. Т.е. это абстрактные циклы в виде монадического сахара над императивными циклами. Ещё бы не костыль :)

Любой компилятор использует трансляцию в императивные конструкции. Исполнимый код процессора - императивный (я говорю о НОРМАЛЬНЫХ, РАСПРОСТРАНЕННЫЙ процессорах, а не о всяких лисп-машинах).

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

Да, поправка:

reverss list = foldl (\ a b -> b : a) [] list

Я про то что можно транслировать

foldr -> рекурсия -> императив

а можно напрямую

foldr -> императив

> reverss list = foldl (\ a b -> b : a) [] list

дада, реверс стал просто очевиден :)

Прекрати бредить уже, а?

А это суггестивное оставляй при себе :) Или у тебя есть абсолютное знание вопроса - чтобы отделить бред от чего-то наделённого смыслом.

дада, реверс стал просто очевиден :)

Ну по крайней мере это 1 строка и в ней не может быть ошибки (иначе она не пройдёт тестов, да и вообще). А в типичном коде на 5 строк, хм, тоже не может быть ошибок - но 1 < 5.

> Ну по крайней мере это 1 строка и в ней не может быть ошибки

бугага )))

reverss list = foldr (++) [] list

бугага )))

Ну а что вы хотели - тут цирк.

>Исполнимый код процессора - императивный (я говорю о НОРМАЛЬНЫХ, РАСПРОСТРАНЕННЫЙ процессорах, а не о всяких лисп-машинах).

Кстати, есть ещё аналоговые вычислительные машины. И не только электронные ;)

> Приводи примеры таких языков.

Haskell

> Качество образования и молодёжи на столько упало

Согласен, молодежь сейчас необразованная - в данном случае «настолько» должно писаться слитно :D

>>Как раз, олдфаги так никогда не орут.

разные олдфаги, у меня препод был, засрал на лекциях ВСЁ(!), виндовс, линукс, майкрософт, 1с, оракл... вообщем всё, что появилось после 80 года.. но лекции были очень толковые, и видно, что спорить бесполезно, потому что не выиграть его

>Выражение задачи в циклах/присваиваниях это описание хода выполнения.

Верно. Ибо присваивание не нужно и цикл не есть цель. Нужен ответ.

Но решение в виде рекурсии - это описание хода редукций, фактически того же выполнения (просто не в парадигме SM а в парадигме LC)

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

Суть в том, что в функциональном ЯП есть только функции, параметры и результат. И никакого времени. Отсюда монады, отсюда и рекурсия, как способ в рамках одного такта описать всю задачу. Это как два зеркала, образующие коридор. Они одномоментны, хотя императивно это выливается в цикл или рекурсивный вызов каждого из зеркал с параметром-изображения с другого зеркала.

а выразили бы функцию через fold. Разве не так?

свертка или рекурсия, тут нет разницы. Все это способы описать результат, а не метод исполнения.

> А это суггестивное оставляй при себе :) Или у тебя есть абсолютное знание вопроса - чтобы отделить бред от чего-то наделённого смыслом.

Но морфизм есть!