Логическое программирование
Все мы более или менее знакомы с понятием алгоритма и с алгоритмическими языками программирования. Тем не менее мир компьютерных языков ими далеко не исчерпывается. Я бы рискнул сказать, что все языки программирования можно разделить на три большие группы: низкоуровневые, алгоритмические и математические.
Это деление совершенно нестрогое и ненаучное, но оно представляется мне практичным и достаточно содержательным. К низкоуровневым можно, например, отнести языки ассемблера, язык С (признанный переносимый ассемблер) и Forth. Их отличительная особенность - близость к языку машинных кодов. Другими словами, строение и особенности языка скорее определяются требованием легкости и очевидности перевода программ с этих языков в исполнимый код.
К алгоритмическим относится подавляющее большинство языков, с которыми мы обыкновенно сталкиваемся: Basic, Cobol, PL/1, Fortran, Pascal и так далее. Создавая их, разработчики преследовали цель получения языков, использование которых удобно в некоторой предметной области. То есть языков, приспособленных для выражения алгоритмов, свойственных определенному кругу задач.
Языки математические, или научные, пошли еще дальше. К ним относятся LISP, ML, SmallTalk, Prolog и многие другие. Каждый из них скорее является воплощением аппарата своей математической теории, чем прикладным языком программирования. С математикой всегда так. Прикладной математический аппарат современного инженерного дела создавался 150-200 лет назад. Кто в силах сказать, когда упомянутые языки, точнее, выраженные в них математические идеи, безоговорочно перейдут в разряд прикладных инструментов? А пока на них лежит клеймо академической науки и ограниченной сферы применения.
Логическое программирование в первую очередь ассоциируется с языком Prolog. Prolog гораздо менее распространенный и известный язык, чем COBOL, Fortran или С. Сразу возникает вопрос: зачем он может понадобиться практическому программисту?
Инженер-программист и ученый-программист в первую очередь сосредоточены на том, чтобы выпускать рабочие продукты. Тем же озабочен и программист-практик, пишущий shareware: его программы должны работать. Это очевидно. Одно из многих различий состоит в том, что практика ведет некая комбинация интуиции, вдохновения и опыта, а инженер должен к тому же иметь доказательство, что его программа будет надежно и бесперебойно служить весь запланированный срок.
Пойдем дальше. Инженер-механик может подтвердить свою разработку расчетами, основанными на теоремах соответствующих наук и абстрактной модели собственного механизма. Он может обсчитать легкий, тяжелый и средний режим работы своей конструкции. Абстрактная модель записывается на языке математики. Этот язык хорошо известен и понятен. Например, мы имеем дело с формулой "3 + 9 x 4". Мы знаем все: значение цифр и знаков операций, правила арифметики и порядок вычислений.
А теперь перенесем этот же пример на почву программирования. Если мы пишем программу на С, осуществляющую расчеты по указанной формуле, то на деле мы не знаем, как доказать, что эта программа работоспособна. Процесс отладки не поможет, поскольку в ходе отладки один набор ошибок просто-напросто замещается другим. Если быть оптимистом, то можно сказать следующее: отладка может выявить ошибки, но не доказать их отсутствие.
Можно попробовать пойти несколько иным путем. Например, имея программу на С, попробовать записать смысл написанной программы на некотором абстрактном языке. Прибегнуть к тому же приему, каким пользуется инженер-механик, описывая создаваемую конструкцию языком математики. Проблема в том, что очень трудно найти подходящий абстрактный язык.
В конечном счете, чтобы записать значение программы, разработанной на C, Pascal, Fortran, Cobol или чем-то похожем, придется описывать ее действие в терминах результата исполнения программы на произвольном абстрактном компьютере. На "голой" архитектуре фон Неймана, если можно так выразиться.
Для тех, кто вырос рядом с компьютерами или с отроческих лет на них работал, архитектура фон Неймана кажется совершенно нормальной. Однако, попробуйте объяснить в терминах машины фон Неймана процедуру, скажем, сортировки списка имен другому разумному существу, например, марсианину. Или, ладно, просто человеку с высшим образованием, который не имеет опыта работы с ЭВМ. Вероятнее всего, собеседник будет поражен до немого изумления тем, что вы, будучи в здравом уме, находите нормальным делать такое количество мелких операций над ничтожно малыми частицами информации при помощи такой тупой машины.
Если вам покажется, что это преувеличение, то вернемся с нашему арифметическому примеру. Предположим, что смысл выражения 3 + 9 x 4 записан так:
Нажать ON/CLEAR
Нажать 9
Нажать х
Нажать 4
Нажать =
Нажать МС
Нажать М+
Нажать ON/CLEAR
Нажать 3
Нажать +
Нажать МR
Нажать =
Прочесть 39 на индикаторе.
Эта запись - не что иное, как одна из возможных последовательностей нажатий клавиш на калькуляторе. Можете представить себе, на что она станет похожа, если в качестве базовых операций будут использованы команды занесения в память компьютера кодов данных, кодов программы, инициализация служебных регистров процессора и так далее.
Так можно ли назвать нашу первоначальную "калькуляторную" запись записью смысла процесса вычислений? Если да, то она достаточно эффективно выражает суть дела и не предполагает знания конструкции какой-либо конкретной машины. Языки семейства C, Pascal, Fortran, Basic называют процедурными. Смысл написанных на них программ невозможно выразить иначе, чем описанием процедуры того, как они исполняются машиной фон Неймана.
Декларативные языки отличаются от процедурных именно тем, что о смысле написанных на них программ можно говорить, не упоминая об исполняющей машине. Причина этого уже упоминалась: такие языки воплощают абстрактный математический аппарат.
Хотите верьте, хотите не верьте, но объектно-ориентированные возможности проникли в С++, Delphi и т.п. из научных языков программирования, построенных на основе математической теории объектов. Ну, так есть после этого польза от научных языков для практики, или нет?
Говоря о декларативных языках, обычно указывают на существование двух больших семейств. Функциональные языки используют для выражения смысла программ язык математических функций. Программы представляют собой описание набора математических функций, каждая из которых возвращает результат. Значение вызова функции выражается в терминах возвращаемого результата. Поэтому функцию можно назвать объявлением (декларацией) ее результата.
Логические языки, как предполагается их названием, для целей передачи смысла программ используют средства математической логики. Сама по себе логика была изобретена как инструмент человеческой мысли, позволяющий упорядочить знания и получить из них соответствующие выводы. Поэтому кажется довольно естественным прибегнуть к логике и для программирования компьютеров.
На деле применяется аппарат не всей математической логики, а только ее раздел, относящийся к исчислению предикатов первого порядка. Правду говоря, он используется частично. Точнее говоря, на исчисление в общем виде наложен ряд довольно сильных ограничений. К счастью, чтобы воспользоваться языком логического программирования, вовсе не нужно знать логику предикатов: она уже встроена в язык. Достаточно изучить сам язык и привыкнуть к его выразительным средствам.
Язык Prolog, самый известный из представителей семейства, вырос из работ Алана Колмерауэра по обработке естественного языка (Монреаль, Марсель) и независимых работ Роберта Ковалького по приложениям логики к программированию (Лондон).
У Prolog были также предтечи и в США: Micro-Planner, на котором Терри Виноград создал пионерскую модель мира кубиков и язык манипуляций SHRDLU и Conniver. (За подробностями отсылаю читателей к классической истории искусственного интеллекта.) Однако, оба языка не сумели потеснить LISP, обладателя короны среди языков ИИ того времени, потому что были чрезвычайно неэффективными с вычислительной точки зрения.
Преодолеть проблемы Micro-Planner'а и Conniver'а удалось Дэвиду Уоррену и его коллегам из Эдинбургского университета, сумевшим эффективно реализовать Prolog. Имя Уоррена вошло в историю логического программирования. В его честь названа базовая техника реализации Prolog, получившая название абстрактной машины Уоррена.
Итак, для чего используется логическое программирование? Было бы неверным считать его в целом и Prolog в частности исключительно инструментом искусственного интеллекта. Prolog нашел применение и в ряде других областей, например, при решении задач составления сложных расписаний, поиска информации и анализа баз данных.
Другое впечатляющее приложение логические языки нашли благодаря своей нацеленности на манипуляцию и трансформацию математических объектов. Чтобы в полной мере понять следствие этой их особенности, нужно вспомнить, что сама программа на декларативном языке также является математическим объектом. Подвергнув исходный текст программы инвариантным относительно семантики кода преобразованиям, можно получить программу, служащую тем же целям, но работающую гораздо эффективнее.
Пытаясь осознать эту возможность, невольно приходишь к жутковатой мысли о теоретической возможности самомодифицирующихся и саморазвивающихся программ. Да, в науке об искусственном интеллекте есть и такое направление. Наконец, ведутся работы, в которых предпринимается попытка создания систем, основыванных на этом принципе, которые по исходным формальным спецификациям могли бы генерировать готовые прикладные программы. И все это только благодаря наличию у декларативных языков абстрактных семантических систем.
Последнее применение языков логического программирования, которое мне известно, лежит в области параллельных вычислений. Знаменитый Prolog на деле был адаптирован к исполнению на последовательных машинах. В своей чистой форме логическое программирование имеет ряд свойств, которые позволяют говорить о логических языках, как о параллельных.
Одним из примеров является язык Parlog, разработанный Стивом Грегори в середине 80-х в Имперском колледже в Лондоне. Этот параллельный язык широко распространен в британской высшей школе.
Евгений Щербатюк
Это деление совершенно нестрогое и ненаучное, но оно представляется мне практичным и достаточно содержательным. К низкоуровневым можно, например, отнести языки ассемблера, язык С (признанный переносимый ассемблер) и Forth. Их отличительная особенность - близость к языку машинных кодов. Другими словами, строение и особенности языка скорее определяются требованием легкости и очевидности перевода программ с этих языков в исполнимый код.
К алгоритмическим относится подавляющее большинство языков, с которыми мы обыкновенно сталкиваемся: Basic, Cobol, PL/1, Fortran, Pascal и так далее. Создавая их, разработчики преследовали цель получения языков, использование которых удобно в некоторой предметной области. То есть языков, приспособленных для выражения алгоритмов, свойственных определенному кругу задач.
Языки математические, или научные, пошли еще дальше. К ним относятся LISP, ML, SmallTalk, Prolog и многие другие. Каждый из них скорее является воплощением аппарата своей математической теории, чем прикладным языком программирования. С математикой всегда так. Прикладной математический аппарат современного инженерного дела создавался 150-200 лет назад. Кто в силах сказать, когда упомянутые языки, точнее, выраженные в них математические идеи, безоговорочно перейдут в разряд прикладных инструментов? А пока на них лежит клеймо академической науки и ограниченной сферы применения.
Логическое программирование в первую очередь ассоциируется с языком Prolog. Prolog гораздо менее распространенный и известный язык, чем COBOL, Fortran или С. Сразу возникает вопрос: зачем он может понадобиться практическому программисту?
Инженер-программист и ученый-программист в первую очередь сосредоточены на том, чтобы выпускать рабочие продукты. Тем же озабочен и программист-практик, пишущий shareware: его программы должны работать. Это очевидно. Одно из многих различий состоит в том, что практика ведет некая комбинация интуиции, вдохновения и опыта, а инженер должен к тому же иметь доказательство, что его программа будет надежно и бесперебойно служить весь запланированный срок.
Пойдем дальше. Инженер-механик может подтвердить свою разработку расчетами, основанными на теоремах соответствующих наук и абстрактной модели собственного механизма. Он может обсчитать легкий, тяжелый и средний режим работы своей конструкции. Абстрактная модель записывается на языке математики. Этот язык хорошо известен и понятен. Например, мы имеем дело с формулой "3 + 9 x 4". Мы знаем все: значение цифр и знаков операций, правила арифметики и порядок вычислений.
А теперь перенесем этот же пример на почву программирования. Если мы пишем программу на С, осуществляющую расчеты по указанной формуле, то на деле мы не знаем, как доказать, что эта программа работоспособна. Процесс отладки не поможет, поскольку в ходе отладки один набор ошибок просто-напросто замещается другим. Если быть оптимистом, то можно сказать следующее: отладка может выявить ошибки, но не доказать их отсутствие.
Можно попробовать пойти несколько иным путем. Например, имея программу на С, попробовать записать смысл написанной программы на некотором абстрактном языке. Прибегнуть к тому же приему, каким пользуется инженер-механик, описывая создаваемую конструкцию языком математики. Проблема в том, что очень трудно найти подходящий абстрактный язык.
В конечном счете, чтобы записать значение программы, разработанной на C, Pascal, Fortran, Cobol или чем-то похожем, придется описывать ее действие в терминах результата исполнения программы на произвольном абстрактном компьютере. На "голой" архитектуре фон Неймана, если можно так выразиться.
Для тех, кто вырос рядом с компьютерами или с отроческих лет на них работал, архитектура фон Неймана кажется совершенно нормальной. Однако, попробуйте объяснить в терминах машины фон Неймана процедуру, скажем, сортировки списка имен другому разумному существу, например, марсианину. Или, ладно, просто человеку с высшим образованием, который не имеет опыта работы с ЭВМ. Вероятнее всего, собеседник будет поражен до немого изумления тем, что вы, будучи в здравом уме, находите нормальным делать такое количество мелких операций над ничтожно малыми частицами информации при помощи такой тупой машины.
Если вам покажется, что это преувеличение, то вернемся с нашему арифметическому примеру. Предположим, что смысл выражения 3 + 9 x 4 записан так:
Нажать ON/CLEAR
Нажать 9
Нажать х
Нажать 4
Нажать =
Нажать МС
Нажать М+
Нажать ON/CLEAR
Нажать 3
Нажать +
Нажать МR
Нажать =
Прочесть 39 на индикаторе.
Эта запись - не что иное, как одна из возможных последовательностей нажатий клавиш на калькуляторе. Можете представить себе, на что она станет похожа, если в качестве базовых операций будут использованы команды занесения в память компьютера кодов данных, кодов программы, инициализация служебных регистров процессора и так далее.
Так можно ли назвать нашу первоначальную "калькуляторную" запись записью смысла процесса вычислений? Если да, то она достаточно эффективно выражает суть дела и не предполагает знания конструкции какой-либо конкретной машины. Языки семейства C, Pascal, Fortran, Basic называют процедурными. Смысл написанных на них программ невозможно выразить иначе, чем описанием процедуры того, как они исполняются машиной фон Неймана.
Декларативные языки отличаются от процедурных именно тем, что о смысле написанных на них программ можно говорить, не упоминая об исполняющей машине. Причина этого уже упоминалась: такие языки воплощают абстрактный математический аппарат.
Хотите верьте, хотите не верьте, но объектно-ориентированные возможности проникли в С++, Delphi и т.п. из научных языков программирования, построенных на основе математической теории объектов. Ну, так есть после этого польза от научных языков для практики, или нет?
Говоря о декларативных языках, обычно указывают на существование двух больших семейств. Функциональные языки используют для выражения смысла программ язык математических функций. Программы представляют собой описание набора математических функций, каждая из которых возвращает результат. Значение вызова функции выражается в терминах возвращаемого результата. Поэтому функцию можно назвать объявлением (декларацией) ее результата.
Логические языки, как предполагается их названием, для целей передачи смысла программ используют средства математической логики. Сама по себе логика была изобретена как инструмент человеческой мысли, позволяющий упорядочить знания и получить из них соответствующие выводы. Поэтому кажется довольно естественным прибегнуть к логике и для программирования компьютеров.
На деле применяется аппарат не всей математической логики, а только ее раздел, относящийся к исчислению предикатов первого порядка. Правду говоря, он используется частично. Точнее говоря, на исчисление в общем виде наложен ряд довольно сильных ограничений. К счастью, чтобы воспользоваться языком логического программирования, вовсе не нужно знать логику предикатов: она уже встроена в язык. Достаточно изучить сам язык и привыкнуть к его выразительным средствам.
Язык Prolog, самый известный из представителей семейства, вырос из работ Алана Колмерауэра по обработке естественного языка (Монреаль, Марсель) и независимых работ Роберта Ковалького по приложениям логики к программированию (Лондон).
У Prolog были также предтечи и в США: Micro-Planner, на котором Терри Виноград создал пионерскую модель мира кубиков и язык манипуляций SHRDLU и Conniver. (За подробностями отсылаю читателей к классической истории искусственного интеллекта.) Однако, оба языка не сумели потеснить LISP, обладателя короны среди языков ИИ того времени, потому что были чрезвычайно неэффективными с вычислительной точки зрения.
Преодолеть проблемы Micro-Planner'а и Conniver'а удалось Дэвиду Уоррену и его коллегам из Эдинбургского университета, сумевшим эффективно реализовать Prolog. Имя Уоррена вошло в историю логического программирования. В его честь названа базовая техника реализации Prolog, получившая название абстрактной машины Уоррена.
Итак, для чего используется логическое программирование? Было бы неверным считать его в целом и Prolog в частности исключительно инструментом искусственного интеллекта. Prolog нашел применение и в ряде других областей, например, при решении задач составления сложных расписаний, поиска информации и анализа баз данных.
Другое впечатляющее приложение логические языки нашли благодаря своей нацеленности на манипуляцию и трансформацию математических объектов. Чтобы в полной мере понять следствие этой их особенности, нужно вспомнить, что сама программа на декларативном языке также является математическим объектом. Подвергнув исходный текст программы инвариантным относительно семантики кода преобразованиям, можно получить программу, служащую тем же целям, но работающую гораздо эффективнее.
Пытаясь осознать эту возможность, невольно приходишь к жутковатой мысли о теоретической возможности самомодифицирующихся и саморазвивающихся программ. Да, в науке об искусственном интеллекте есть и такое направление. Наконец, ведутся работы, в которых предпринимается попытка создания систем, основыванных на этом принципе, которые по исходным формальным спецификациям могли бы генерировать готовые прикладные программы. И все это только благодаря наличию у декларативных языков абстрактных семантических систем.
Последнее применение языков логического программирования, которое мне известно, лежит в области параллельных вычислений. Знаменитый Prolog на деле был адаптирован к исполнению на последовательных машинах. В своей чистой форме логическое программирование имеет ряд свойств, которые позволяют говорить о логических языках, как о параллельных.
Одним из примеров является язык Parlog, разработанный Стивом Грегори в середине 80-х в Имперском колледже в Лондоне. Этот параллельный язык широко распространен в британской высшей школе.
Евгений Щербатюк
Компьютерная газета. Статья была опубликована в номере 10 за 2000 год в рубрике программирование :: разное
