Кто создал идею первой конструкции цикла?

53
while (1) {
      if (1+1==2) {
             print "Yes, you paid attention in Preschool!";
      } else {
             print "Wait... I thought 1+1=2";
      }
 }

Как разработчик, мы все должны использовать циклы очень часто. Мы знаем это. Что мне было интересно, так это то, кто думал об идее иметь петли? На каком языке введены циклы? Какой была первая конструкция цикла? Это была whileпетля? forЦикл? и т.д?

динамический
источник
22
Чарльз Бэббидж и Ада Лавлейс, скорее всего.
Макфинниган
28
Это было изобретено в инструкции шампуня, промыть, вспенить, повторить. :-)
Гай Сиртон
13
@GuySirton, не будь глупым, это рекурсия.
Mowwwalker
18
@ user838584 - если бы это была рекурсия, каждый вызвал repeatбы другую repeat- вы бы никогда не закончили. Я думаю, что, возможно, женщины читают инструкции по использованию шампуня таким образом, но мужчины читают это как итерацию, и им нужно всего несколько минут, чтобы вымыть волосы.
Steve314
3
Компьютер без петель - это калькулятор.
звездный синий

Ответы:

102

Как отметили Мувичиэль и Эмилио Гаравалья , концепция предшествует компьютерным вычислениям. Тем не менее, первым экземпляром программного цикла был цикл Ада Лавлейс, использованный для вычисления чисел Бернулли , как описано в примечании G ее перевода « Эскиза аналитического механизма, изобретенного Чарльзом Бэббиджем » Л. Ф. Менабреа . Способность Аналитического Механизма к циклу уже отмечена Менабреа:

Понятно, что в начале серии операций, которые мы хотим выполнить, поместите иглу C в деление 2, иглу B в деление 5 и иглу A в деление 9. Позвольте нам молот циферблата С ударить; он ударит дважды, и в то же время стрелка B пройдет через два деления. Затем последний укажет число 7, которое следует за номером 5 в столбце первых различий. Если теперь мы позволим молотку циферблата B ударить в свою очередь, он ударит семь раз, в течение которого стрелка A продвинется на семь делений; эти числа, добавленные к уже отмеченным девяткам, дадут число 16, представляющее собой квадратное число, следующее за 9. Если мы сейчас возобновим эти операции, начиная с стрелки C, которую всегда следует оставлять в делении 2,

Механизм зацикливания Аналитического двигателя непосредственно унаследован от механического ткацкого станка Джозефа Мари Жаккарда (1801), как отмечено в мемуарах Менабреа:

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

Два вида нитей обычно различают в тканых материалах; одна представляет собой основную или продольную нить, другая - поперечную или поперечную нить, которая передается инструментом, называемым челноком, и пересекает продольную нить или основание. Когда требуются вещи из парчи, необходимо, в свою очередь, не допускать пересечения определенных нитей определенными нитями, и это в соответствии с последовательностью, которая определяется характером конструкции, которая должна быть воспроизведена. Раньше этот процесс был длительным и сложным, и было необходимо, чтобы рабочий, следя за дизайном, который он должен был скопировать, сам регулировал движения, которые должны были выполнять нити. Отсюда и дороговизна этого описания материалов, особенно если в ткань вошли нити разных цветов. Чтобы упростить это производство, Жаккард разработал план соединения каждой группы нитей, которые должны были действовать вместе, с отдельным рычагом, принадлежащим исключительно этой группе. Все эти рычаги оканчиваются стержнями, которые объединены в один пучок, обычно в форме параллелепипеда с прямоугольным основанием. Стержни имеют цилиндрическую форму и отделены друг от друга небольшими интервалами. Таким образом, процесс поднятия нитей сводится к перемещению этих различных рычагов в необходимом порядке. Для этого берется прямоугольный лист картона, несколько большего размера, чем участок пучка рычагов. Если этот лист будет применен к основанию связки, и затем передаточное движение будет сообщаться к монтажному щиту, этот последний будет перемещать вместе с ним все стержни связки, и, следовательно, темы, которые связаны с каждым из них. Но если бы картон, вместо того, чтобы быть простым, был пробит отверстиями, соответствующими конечностям рычагов, которые встречают его, тогда, так как каждый из рычагов проходил бы через картон во время движения последнего, они все оставались бы в их мест. Таким образом, мы видим, что так легко определить положение отверстий в картоне, что в любой данный момент должно быть определенное количество рычагов и, следовательно, участков нитей, поднятых, а остальные остаются там, где они мы. Предположим, что этот процесс последовательно повторяется в соответствии с законом, указанным в шаблоне, который должен быть выполнен, мы понимаем, что этот шаблон может быть воспроизведен на материале. Для этого нам нужно просто составить серию карточек в соответствии с требованиями закона, и расположите их в подходящем порядке один за другим; затем, заставляя их проходить через многоугольную балку, которая соединена таким образом, чтобы при каждом ударе челнока поворачивать новую грань, эта грань затем должна быть прижата параллельно себе к пачке рычажных рычагов, операция подъема темы будут регулярно выполняться. Таким образом, мы видим, что парчовые ткани могут быть изготовлены с точностью и скоростью, которые раньше было трудно получить.

Жаккардовый ткацкий станок - это очень раннее применение цикла в контексте заказа машины для получения повторного вывода :

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

Жаккардовый ткацкий станок также считается очень ранней формой хранимой программы :

Если стимул, стоящий за большой частью разработки вычислительных машин, о которой говорилось до сих пор, возник из численных вычислений, мотивация, которая привела к самой ранней форме «хранимой программы», должна была исходить из совершенно другого источника: текстильной промышленности. Ранее мы видели, что одним из фундаментальных аспектов вычислительных систем является концепция представления информации, и, хотя мы не сделали этого явно, применение этой идеи можно обнаружить во всех артефактах, которые мы исследовали до сих пор: в развитии письменных представлений для числовых значений и механических параллелей, которые возникли из них. Таким образом, выравнивание камешков на раме счёта, наложение движущихся весов на линейку скольжения и конфигурация зубчатых колес на устройствах Шикарда, Паскаля и Лейбница, Все примеры методов представления, которые стремятся упростить сложные процессы, лежащие в основе арифметических задач. Однако существуют категории информации и их представления, отличные от числа, для которого могут выполняться вычислительные процессы. Технология ткачества, разработанная Жозефом-Мари Жаккардом в 1801 году, иллюстрирует один из примеров такой категории.

Чарльз Бэббидж также адаптировал процедуру хранения Жаккарда в Аналитическом движке , наличие или отсутствие отверстия сообщало машине простую команду включения-выключения:

Аналитический движок имеет много важных функций, которые можно найти в современном цифровом компьютере. Его можно было программировать с помощью перфокарт - идея, заимствованная из жаккардового станка, использовалась для плетения сложных рисунков в текстиле. У двигателя был «Магазин», в котором могли храниться числа и промежуточные результаты, и отдельный «Мельница», где выполнялась арифметическая обработка. Он имел внутренний репертуар из четырех арифметических функций и мог выполнять прямое умножение и деление. Он также был способен выполнять функции, для которых у нас есть современные имена: условное ветвление, зацикливание (итерация), микропрограммирование, параллельная обработка, итерация, фиксация, опрос и формирование импульсов, среди прочего, хотя Бэббидж нигде не использовал эти термины. У него было множество выходов, включая распечатку, перфокарты,

Условные ветви Analytical Engine в сочетании с механическими петлями и процедурой хранения, вдохновленными Жаккардом, очень похожи (концептуально) на ваш пример, особенно если мы добавим принтер Бэббиджа в смесь для print "...";деталей.

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

Тем не менее, я думаю, что в контексте вычислений (а не вычислений или чего-либо еще), алгоритм Analytical Engine и алгоритм вычисления чисел Аду Бернулли могут быть зачтены для введения циклов, разделяя, по крайней мере, некоторую часть заслуг с жаккардовым станком, непосредственно адаптировав концепцию из Это.

Яннис
источник
3
Перед жаккардовым ткацким станком вы можете найти механические петли в карильонах, например, в Брюгге, где колокольчики управляются вращением цилиндра .
Mouviciel
6
@mouviciel Я вижу твое чудовище в колоколе и поднимаю тебе механизм Антикитера. ; P
Яннис
2
+1 за ваш энциклопедический ответ, включая 2000-летний компьютер!
Mouviciel
2
этот красивый ответ сделал меня любимым вопросом. Он не только отвечает на вопрос, но и служит примером того, «как ответить на вопрос». Хорошая работа, дорогой сэр.
Чани
Принял этот ответ, потому что он был и убедительным, и энциклопедическим, и просто потрясающим!
Динамичный
50

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

повторить знак

mouviciel
источник
2
Это может быть отличным ответом, если добавить к нему немного больше деталей. Тем не менее, отличная работа.
Динамичный
Пожалуйста, дайте больше ссылок (самая ранняя дата, самая ранняя музыкальная нотация, чтобы показать конструкции петли / повторения)
Skippy Fastol
@SkippyFastol Это в той статье: en.wikipedia.org/wiki/Repeat_sign#Other_notation
cwallenpoole
32

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

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

Самый простой цикл - это цикл между двумя состояниями (часы). Учитывая, что любое большее количество состояний может быть результатом подсчета с него, каждая более сложная машина создается на «счетчике», увеличиваемом часами, которые могут «прыгать» на определенные флаги, представляющие определенные комбинаторные операции. Это ядро ​​машины фон Неймана, на которой основан каждый микропроцессорный компьютер.

В машинном коде закодирован переход JP-Z-nnnn(где Z - любой флаг, на котором основано ваше условие). На языке более высокого уровня это почти сразу переводится на

if(z) goto x;

Цикл - это не что иное, gotoкак метка x, предшествующая самой инструкции goto.

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

Эмилио Гаравалья
источник
4

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

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

GordonM
источник
6
В лямбда-исчислении нет петель (и нет условий или скачков), но оно завершено по Тьюрингу. Рекурсия так же мощна, как итерация.
3
Вы можете переписать любой цикл в рекурсивную функцию и устранить циклы
ratchet freak
5
Статья в википедии о циклах описывает рекурсию как способ выражения цикла, а не как совершенно не связанную концепцию. en.wikipedia.org/wiki/Program_loop#Loops Что касается процессоров, не имеющих циклов, у них действительно есть инструменты, необходимые для их реализации (переход на произвольный адрес памяти)
GordonM
8
Точно, рекурсия может использоваться, чтобы выразить циклы. Это является совершенно другая концепция, несмотря на то, что они изоморфны друг другу. Кофейная кружка не пончик только потому, что топологи якобы путают их.
4
Да, но любая система, полная по Тьюрингу, должна иметь способ выражения концепции выполнения одной и той же последовательности несколько раз, механизм может быть рекурсивным, или переходить назад в списке команд, или что-то еще, что достигает того же эффекта. Если система не предоставляет никакого способа повторения набора инструкций (кроме физического повторения инструкций в списке), то выполнение Тьюринга не может быть завершено. Аналитический механизм был завершен по Тьюрингу, поэтому он должен реализовывать циклы в той или иной форме.
GordonM
3

Предполагая, что вы имеете в виду современные текстовые языки программирования.

У Algol60 есть «ЗА», «ДО», «ДО» и «ПОЧЕМУ», так было до 1960 года.

Музей ретро-вычислений имеет несколько языков до 1960 года.

Квиккалкуль , язык 50-х для программирования шведских атомных подводных лодок имеет только GOTO. (Однако Квиккалкуль - почти наверняка обман 90-х, а не настоящий исторический язык.)

Plankalkül от Конрада Цузе - самое раннее, что я смог найти. Имеет конструкцию «фюр».

Чад Brewbaker
источник
До недавнего времени Планкалкюль был практически неопубликован, и, по слухам, Квиккалкул давно был обманом. В этом свете, вероятно, следует отдать должное Джону Бакусу и команде FORTRAN , у которой в 1957 году был работающий компилятор на местах с DOциклами.
Росс Паттерсон
2

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

Тем не менее, идея последовательностей повторения и подсчета контролируемых циклов, а также того, что мы назвали бы циклами циклов , обсуждаются в работе человека, для которого названы алгоритмы: Мухаммед ибн Муса аль-Хорезми из девятого века. Его вторая книга «Аль-Китаб аль-Мухтасар фи Хисаб Аль-Джабр ва'л-Мукабала» («Компендиум по расчетам по завершению и балансировке») была известна Ньютсу, Либбесу, Либбесу, Либбезу, Либбесу ,

Конечно, аль-Хорезми полагался, в частности, на древних греков. В какой-то момент мы, вероятно, вернемся к версии Адама и Евы о полоскании, пене, повторении.

Для получения дополнительной информации об Аль-Хваризми и его работе см .:

http://www-groups.dcs.st-andrews.ac.uk/history/Mathematicians/Al-Khwarizmi.html

Чак Герберт
источник