В.Н. Пильщиков - Язык Плэнер (1156455), страница 24
Текст из файла (страница 24)
д. Когда л в развилке .не останется нерассмотренных альтернатив, программа прм очередном неуспехе возвращается уже к предыдущей развилке (в программе может быть много раззилок), чтобы те,'/ перь здесь изменить ранее сделанный выбор. Описанный способ вьпюлнеРис. 1. ния программы, при котором оп- ределяются развилки, в них выбираются альтернативы, а в случае неуспеха осуществляются возвраты назад, и есть режим возвратов. Удобство его для программистов заключается в том, что ответственность аа аапоминание развилок и их альтернатив, за осуществление возвратов к ним с восстановлением прежнего состояния программы берет па себя язык — это делается автоматически.
Задача же пользователя — в нужных местах определить нужные развилин и в соответствующие моменты сигнализировать о неуспехе. Можно сказать, что режим возвратов — зто ерамказ, вставляя в которую подходящие операции, можно легко получить конкретные алгоритмы перебора. Для иллюстрации режима возвратов рассмотрим работу следующей функции: [ОЕР1ХЕ ЯОМ (1АМВОА 11 Х) [РЕОО (К (М ()) (Я 0)) А [ЯЕТ К [АМОг(О .Ц] ,[ЯЕТ М (!.М .К)) [ЯЕТ Я [+ .Я .КЦ [СОг)В ([ЕО .Я .Щ .М) ([1.Т.Я.Щ [ОО А)) (Т [РА1Ц))))) Зта функция находит такие числа иэ ааданного списка Ь положительных чисел, сумма которых равна заданному положительному числу г1 (числа в искомом наборе могут повторяться). Най» денные числа функция накапливает в М, а нх сумму — в Я. Функция ЯОМ вычисляется следующим образом.
На каждом шаге цикла она подбирает очередное число для набора. Им может быть любое число из списка Ь, поэтому выбор его — раавилка в программе. -Такую развилку определяет специальная функция АМОНО, которая в качестве своего значения. может выдать любое число иа списка Ь. То число, которое она действительно выдала, запоминается в М и прибавляется к Б. Далее Я сравнивается с Ж. Если Б и Н равны, то нужный набор уже лайден (он в М), и в этом случае функция БОМ заканчивает свою работу.
Если же Б меньше Н, то чисел в наборе еще недостаточно, поэтому подыскиваиле чисел продолжается: осуществляется переход на следующий шаг цикла, где определяется новая развилка и т. д. Но если Я оказалось больше Х, то продолжать вычисление функции Я()М нелъая, так как она аашла в тупик: сумма выбранных чисел оказалась слишком боаъшой.
Причиной этого может быть то, что на текущем шаге цикла из списка Ь было выбрано неподходящее число, поэтому надо изменить прежний выбор и рассмотреть другое число. Для этого с помощью специальной функпии РА(Ь вырабатывается сигнал о неуспехе, по которому программа автоматически возвращается к своей последней развилке — к функции АМОКО с текущего шага цикла. При возврате также автоматически восстанавливаются прежние эна гения первменных М и Б — те значения, которые они имели до выбора отвергнутого числа.
Итак, неудачный выбор забыт. Функция АМОНС, хотя она ранее и закончила свою работу, вновь зожиэаетз и теперь в качестве своего аначения выдает какое-то другое число из списка Ь. С этого момента выполнение программы возобновляется: она повторяет текущлй шаг цикла, но уже для нового числа. Если и опо не подойдет, тогда программа вновь будет возвращена нааад к функции АМОКО, которая выберет ие списка Ь третье число. Такие 'воавраты будут повторяться до тех пор, пока сумма Я не окажется меньшей или равной числу Х или пока функция АМОНС не исчерпает всех своих возможиостей.
В последнем случае очередной неуспех вернет программу к предпоследней развилке — к АМОКО с предыдущего шага цикла, чтобы теперь именно адесь исправить ранее сделанный выбор; при этом будут автоматически восстановлены соответствующие значения переменных М н Б. На рис. 2 схематично показано вычисление выражения [ЯУМ (6 3 2 т) 5). На этом рисунке пунктирными линиями обозначены неуспешные альтернативы, сплошными — успыпный путь вычисления, волнистыми — остаюпиеся не рассмотренными альтернативы.
Опираясь на наш пример, уточним некоторые особенности режима возвратов. М:=~61ь~ У=с,' )' Неуспех М:=У Бс' 5 =Я,' неуспех не5спех Рис. 2 Преясде всего отметим, что возвраты по неуспеху яе имеют ничего общего с переходами иаэад. При переходах программа дияамически продвигается вперед. Так, в нашем примере после перехода по метке А осуществляется новый вылов фуикции АМОКО, которая иачияает яовый, независимый от выборов в дру- гих активациях втой же функ- и п55 5НМ ция, выбор элементов из спиока Ь.
При неуспехе же действительио происходит возврат к лрежяей активации функции АМОКО, которая «зяает», каи:=(), у:=и кие альтернативы ею уже рассматривались, а какие — еще яет, и поэтому, возобновив свою работу, оиа выбирает Б' 5 еледуэяцую альтернативу. Кроме того, при переходах те- я=И кушке зпачепия перемекпых сохраняются, тогда кап при возвратах по неуспеху ояи емрнй уничтожаются и восстакавли- ваются прежние зяачекия. О Следует отличать кеуспе,'и:Мед и =у '1 хи от ошибок.
Ошибиа — это иарушекие правил языка, при су.=Б й:=5 котором эьшсккекие программы прекращается, в то время как появление кеуасеха озяачает; что программа работает правильна, яо из яесколвких возможвых вариантов своего вычисления оиа расоматризает яе тот.вариакт, который яам нужен.
В любой развилке каждая альтернатива выбирается только раз,' и ранее сделанный выбор никогда больше ве повторяется. В частлости, функция АМОКО каждый раз выбирает из списка- аргумента новый элемент. Порядок выбора альтернатив всегда детерминировал. Ои, .как и сам набор альтеряатив в развилке, строго фиксирован: либо указывается пользователем, либо определяется правилами языка и текущим состоянием программы. Например, функция АМОКО в качестве своего первого аиачеяия всегда выдает первый элемент ив списка-аргумента, в качестве второго зкачеяия — второй элемент и т.
д. Никакого произвола, никакого бросания жребия при выборе альтернатив кет.' При появлении пеуспеха программа всегда возвращается к по- следкей (по времеяи) яе существующих развилок, Развилка цэ- рестает существовать лишь тогда, когда в ней не осталось ни одной нерассмотренной альтернативы. В нашем примере раавилла, определенная функцией АМОХО, уничтожается тогда, когда функция в качестве своего очередного значения выдает последний элемент списка Ь.
С етого момента последней, развилкой программы становится раавилка, которую определила функция АМОХО с предыдущего шага цикла, поэтому именно'л ней и произойдет возврат при следующем неуспехе. В то же время любая развилка, в которой осталась хотя бы одна нерассмотренная альтернатива, продолжает существовать, даже если эанончнлось вычисление процедур; внутри которых она была определена. Иэ рис, 2 видно, что по окончании вычисления выражения [БУМ (6 3 2 1) 5] внутри функции БУМ остались развилки с нерассмотренными альтернативами, поэтому оии продолжают существовать и после выхода ие функции БУМ. Это означает, что если по окончании вычисления функции ЯУМ выра-, ботать неуспех, то он вернет программу к последней иэ этих раэвилок — к АМОХО со второго шага цикла. При этом автоматически возобновляется работа фулкции БУМ, восстанавливается существование всех ее локальных переменных с соответствующи«аи аначепинми, возобновляется и работа функции АМОХО со второго шага цикла.
На этот раэ она выберет число 1, которое и будет теперь аналиаироваться функцией ЯОМ (см, рис. 3). Новым эначением функции Я()М будет список (8 1 1), являющийся другам решением нашей вадачи. Вырабатывая снова и снова неуспехи, можно эаставить функцию Я()М найти третье, четвертое и друвие решения нашей задачи. Например, прн вычислении выражения [РВОО (Х) [ЯЕТ Х [БОМ (6 3 2 1) 5]] [СОХО ([ХЕ«) [1ЕХОТН .Х] 4] [РА1Ц)] .Х] -«(2111) неуспехи, вырабатываемые функцией РА1Ь иа условного оператора, будут возобновлять работу функции ЯУМ до тех пор, пока она ле найдет решение из четырех чисел.
Этот пример показывает, что неуспех можно использовать не только как сигнал о том, чтм программа эашла в тупик, но и для того чтобы эастав~ть некоторую процедуру генерировать все или нужное количество вариантов ее успешной работы. Рассматриваемая нами эадача может и не иметь решения, как, например, в случае [БОМ (4 2) 7]. Здесь в каждой развилке функцпл БОМ будут рассмотрены все альтернативы, но нл одна иа них не приведет и успеху.
В конце концов в ЯСМ не останется ««в одной развилки, поэтому неуспех, выбранный в очередной раэ функцией РАНе эаставит программу вернуться к раэвиляе, которая была определена до входа в функцию ЯПМ. Тем самым мы сталкиваемся с новой дли нас ситуацией. До онх пор, вычисляя какую-.нибудь форму, мы обяаательно получали некоторое аначепие. Прн вычислении же формы ~ЯПМ (4 2) 71 ии о каком ее аначении не может быть и речи, поскольку вычисление функции Вхы Оуии Е:=~В 5 г ф И =5 м=<),5:=В а Р Выхоа оа оо онаоеное Неуооех Выхоа ю ЛФ оо она наноее М 1 Ц Рис. 3. БПМ не доходит до конца и происходит «выскакивание» иа функции по неуспеху. Таким обрааом, в пленере наряду с обычным услошвыл исходом вычисления, когда оно полностью эавершается и в реаультате вырабатывается некоторое аиачеиие, возможен и иной исход — неуовешный.
Вычисление выражения наэываетсн неуспешным, если во время этого вычисления был выработан неуспех, по которому программа должна вернуться к раэвилие, определенной . ИЗ до начала вычисления данного выражения. Значения такое выражение не имеет. Следовательно, вычисление выражения [Б11М (4 2) 7) неус пешно. Неуспешным является и вычисление ранее рассмотренного условного выражения [СОКО ([КЕО РЛКСтН-.Х) 4) [РА(Ц)) в том случае, если длина списка Х не равна 4. Друэне примеры неуспешных вычислений; [БЕТ Х (А [РА1Ц)], [СО [РА1Ц), 3.2. Функции для режима возвратов Рассмотрим встроенные фуриции планера, которые используются для органпаации вычислений в режиме ооэвратов.
Функция РАП «): [РАП е7), БПВВ. Данная функция, как уже иввестно, вырабатывает неуспех, который прерывает выполнение программы и возвращает ее к последней развилке, восстанавливая при этом прежние состояния объек- ' тов программы (переменных, списков свойств и т. д.). Кроме того, функция связывает с втим неуспехом сообэ1ение; им является аначение аргумента функции, а если его нет — пустой список (). В пленере с любым неуспехом связывается некоторое сообщение.
Сообщения позволяют идентифицировать неуспехи: большинство встроенных функций языка, которые вырабатывают неуспех, в качестве сообщения указывают свое имя, "и по таким сообщениям можно установить, капая именно функция выработала неуспех. Сообщения можно использовать и для указания пр~ьчины появления неуспеха; в этом случае обычно применяется функция РАП, которая поаволяет связать с неуспехом произвольное выражение. Воспользоваться' сообщениями моясно в развилке после возврата к ней по неуспеху: в зависимости от того, каков сообщение было свяаако с неуопехом, можно по-равному прореагировать на этот воаврат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
