Функциональное программирование и интеллектуальные системы

Министерство образования и науки Российской Федерации 
 
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) 
 
ФАКУЛЬТЕТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ (ФДО) 
 
 
 
 
Н. Ю. Салмина 
 
 
 
 
 

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ  
И ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ 
 

 
 
 
 
 
Учебное пособие 
 
 
 
 
 
 
Томск 
2016

УДК
004.42.046 + 004.89 
ББК 
32.973.2-018я73 + 32.813я73 
 
С 164 
 
Рецензенты: 
А. В. Ковшов, старший преподаватель кафедры 
автоматизированных систем управления ТУСУР; 
В. Ф. Тарасенко, д.т.н., профессор кафедры теоретической кибернетики ТГУ 
 
Салмина Н. Ю. 
С 164 
Функциональное программирование и интеллектуальные системы : учебное пособие / Н. Ю. Салмина. – Томск : ФДО, ТУСУР, 
2016. – 100 с. 
 
В настоящем учебном пособии изложены основные положения функционального программирования на примере языка Лисп. Рассматриваются принципы функционального программирования, применения лямбда-выражений и 
написания собственных функций. Большое внимание уделено использованию 
рекурсии при написании программ. Проанализированны две модели представления знаний: фреймы и семантические сети, а также способы их построения и 
использования средствами языка Лисп. 
Теоретический материал иллюстрируется многочисленными примерами. 
Для студентов, обучающихся по направлению 38.03.05 «Бизнесинформатика» и родственным направлениям. 
 
 
 
 
 
 
 
 
 
© Салмина Н. Ю., 2016 
© Оформление. 
ФДО, ТУСУР, 2016

Оглавление 
Предисловие ..................................................................................................... 5 
Введение ............................................................................................................ 7 
1 Язык Лисп. Основы программирования .............................................. 13 
1.1 Лисп. Элементарные понятия .............................................................. 13 
1.1.1 Атомы и списки как основные объекты языка Лисп ................. 13 
1.1.2 Внутреннее представление списков ............................................. 14 
1.1.3 Понятие функции ........................................................................... 16 
1.2 Программа на языке Лисп. Вычислимые выражения ....................... 17 
1.3 Базовые функции языка ........................................................................ 18 
1.4 Лямбда-выражения и определение новых функций .......................... 27 
2 Рекурсивные функции .............................................................................. 30 
2.1 Понятие рекурсии ................................................................................. 30 
2.2 Как работает рекурсивная функция .................................................... 31 
2.3 Правила записи рекурсивной функции ............................................... 32 
2.4 Рекурсия с несколькими терминальными или рекурсивными  
ветвями ..................................................................................................... 34 
2.5 Вспомогательные функции над списками .......................................... 38 
3 Технология программирования на языке Лисп .................................. 44 
3.1 Передача параметров. Глобальные и локальные переменные ......... 44 
3.2 Диалоговый режим работы. Функции ввода-вывода ........................ 45 
3.3 Разрушающие функции ........................................................................ 50 
3.4 Функционалы ......................................................................................... 53 
3.5 Циклы и блочные функции .................................................................. 57 
3.5.1 Блочные функции ........................................................................... 57 
3.5.2 Циклические предложения ........................................................... 60 
3.6 Массивы ................................................................................................. 66 
3.7 Свойства символов ................................................................................ 68 
3.8 Ассоциативные списки ......................................................................... 70 
3.9 Работа с файлами .................................................................................. 72 
3.9.1 Определение входных и выходных потоков ............................... 72 
3.9.2 Чтение символов из файла ............................................................ 75 
4 Модели представления знаний ................................................................ 77 
4.1 Фреймы ................................................................................................... 77 
4.1.1 Понятие и состав фрейма .............................................................. 77 
4.1.2 Пример построения фреймовой структуры на Лиспе ................ 79 

4.2 Семантические сети .............................................................................. 88 
4.2.1 Представление знаний с помощью семантических сетей .......... 88 
4.2.2 Пример построения семантической сети с помощью Лиспа..... 93 
Заключение ..................................................................................................... 96 
Литература...................................................................................................... 97 
Глоссарий ........................................................................................................ 98 
 
 
 

Предисловие 

Функциональное программирование называется так, потому что программа полностью состоит из функций. Сама программа тоже является функцией, которая получает исходные данные в качестве аргумента, а выходные 
данные выдает как результат. Как правило, основная функция определена в 
терминах других функций, которые в свою очередь определены в терминах еще 
большего количества функций, вплоть до функций – примитивов языка на самом нижнем уровне. Эти функции очень похожи на обычные математические 
функции.  
Особенности и преимущества функционального программирования 
обычно излагаются следующим образом. Функциональные программы не содержат операторов присваивания, а переменные, получив однажды значение, 
никогда не изменяются. Более того, функциональные программы вообще не 
имеют побочных эффектов. Обращение к функции не вызывает иного эффекта 
кроме вычисления результата. Это устраняет главный источник ошибок и делает порядок выполнения функций несущественным: так как побочные эффекты 
не могут изменять значение выражения, оно может быть вычислено в любое 
время. Программист освобождается от бремени описания потока управления. 
Поскольку выражения могут быть вычислены в любое время, можно свободно 
заменять переменные их значениями и наоборот, то есть программы «прозрачны по ссылкам». Эта прозрачность ссылок делает функциональные программы 
более удобными для математической обработки, по сравнению с общепринятыми аналогами.  
В данном пособии в качестве одного из функциональных языков рассматривается язык Лисп.  
В практических интеллектуальных системах наибольшее внимание привлекают два блока: база знаний и решатель задач. Качество работы интеллектуальной системы в значительной мере определяется тем, как устроены эти блоки 
и насколько удачно организовано взаимодействие между ними.  
Выбор модели представления знаний связан с видом зависимостей знаний 
с описанием тех или иных процессов во времени, прогнозом этих процессов. 
В данном учебном пособии рассмотрены два класса моделей представления 
знаний: фреймы и семантические сети. 

Другой проблемой в построении интеллектуальных систем является выбор инструментального средства и его реализация. В качестве инструментального средства предлагается использовать функциональный язык Лисп. 
Для усвоения основных результатов и понятий, приведенных в учебном 
пособии, достаточно знания курса информатики в объеме университетской программы. Во всех главах содержатся многочисленные примеры, иллюстрирующие основные принципы функционального программирования. 
Основной задачей курса «Функциональное программирование и интеллектуальные системы» является формирование у студентов профессиональных 
знаний и практических навыков по разработке алгоритмов и написанию программ средствами функционального программирования, представлению знаний 
и разработке моделей интеллектуальных систем. 

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

 

 ·····························································  
Эта пиктограмма означает определение или новое понятие. 
 ·····························································  
 ·····························································  
Эта пиктограмма означает «Внимание!». Здесь выделена важная информация, требующая акцента на ней. Автор может поделиться с читателем опытом, чтобы помочь избежать некоторых 
ошибок. 
 ·····························································  

 ························  
 Пример  ··························  

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

Введение 

Концепция функционального программирования 
В основе функционального программирования лежит понятие функции. 
Вспомнив историю математики, можно оценить возраст понятия «функция»: 
ему уже около четырехсот лет, и математики придумали очень много теоретических и практических аппаратов для оперирования функциями, начиная от 
обыкновенных операций дифференцирования и интегрирования, заканчивая заумными функциональными анализами, теориями нечетких множеств и функций 
комплексных переменных. 
Математические функции выражают связь между исходными данными и 
итоговым продуктом некоторого процесса. Процесс вычисления также имеет 
вход и выход, поэтому функция – вполне подходящее и адекватное средство 
описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования.  
Функциональным называется программирование при помощи функций в 
математическом их понимании. Функциональное программирование основано 
на следующей идее: в результате каждого действия возникает значение, которое может быть аргументом следующего действия. Программы строятся из логически расчлененных определений функций. Каждое определение функции 
состоит из организующих вычисления управляющих структур и из вложенных, 
в том числе вызывающих самих себя (рекурсивных), вызовов функций. При 
выполнении программы функции получают параметры, вычисляют и возвращают результат, при необходимости вычисляя значения других функций. На 
функциональном языке программист не должен описывать порядок вычислений. Нужно просто описать желаемый результат как систему функций. 
Выделим основные особенности и преимущества языков функционального программирования (ФП). 
Особенности функционального программирования [1]: 
1. Вызов функций является единственной разновидностью действий, выполняемых в функциональной программе. 
2. В алгоритмических языках программа является последовательностью 
операторов, вызовов процедур в соответствии с алгоритмом. В функциональном программировании программа состоит из вызовов функций и описывает то, 

что нужно делать и что собой представляет результат решения, а не как нужно 
действовать для получения результата. 
3. Основными методами программирования являются суперпозиция 
функций и рекурсия.  
4. Функциональное программирование есть программирование, управляемое данными. В строго функциональном языке однажды созданные (введенные) данные не могут быть изменены! 
5. В алгоритмических языках с именем переменной связана некоторая область памяти, соответствие строго сохраняется в течение всего времени выполнения программы. В функциональном программировании переменная обозначает только имя некоторой структуры, имена символов, переменных, списков, 
функций и других объектов не закреплены предварительно за какими-либо типами данных. В ФП одна и та же переменная в различные моменты времени 
может представлять различные объекты. 
6. В языках функционального программирования программа и обрабатываемые ею данные имеют единую списочную форму представления.  
7. Функциональное программирование предполагает наличие функционалов – функций, аргументы и результаты которых могут быть функциями. Всякий язык функционального программирования предполагает наличие ядра, 
называемого строго функциональным языком.  
Требования к строго функциональному языку: 
1. Всякая функция должна однозначно определять результат по любому 
набору аргументов.  
2. Отсутствует оператор присваивания.  
3. Переменная обозначает только имя структуры.  
4. В языке присутствуют функционалы. 
Основные преимущества языков ФП [1]: 
1. Краткость программы. Программы на функциональных языках обычно 
короче и проще, чем те же самые программы на императивных языках. 
2. Функции – это значения. Функциональные программы поддаются формальному анализу легче своих аналогов на алгоритмических языках за счет использования математической функции в качестве основной конструкции: функции могут быть переданы другим функциям в качестве аргумента или 
возвращены в качестве результата. 
3. Чистота. В императивных языках функция в процессе своего выполнения может читать и изменять значения глобальных переменных и осуществлять 

операции ввода-вывода. Поэтому, если вызвать одну и ту же функцию дважды 
с одним и тем же аргументом, может случиться так, что в качестве результата 
будет вычислено два различных значения. Изменение функцией состояния программы иначе, чем через возвращение значения, называется побочным эффектом. В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать 
новые путем разбора и сбора уже существующих объектов. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых 
функциональных языках все функции свободны от побочных эффектов.  
4. Возможность реализации на ЭВМ с параллельной архитектурой. Раз 
все функции для вычислений используют только свои параметры, мы можем 
вычислять независимые функции в произвольном порядке или параллельно, на 
результат вычислений это не повлияет. Причем параллелизм может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. 
В нескольких научных лабораториях уже разработаны и используются экспериментальные компьютеры, основанные на подобных архитектурах. В качестве 
примера можно привести Lisp-машину. 
Основные свойства функциональных языков: 

• краткость и простота: программы на функциональных языках обычно 
короче и проще, чем те же самые программы на императивных языках; 

• строгая типизация; 

• модульность; 

• функции – это значения; 

• чистота (отсутствие побочных эффектов); 

• отложенные (ленивые) вычисления. 
Символьная обработка и искусственный интеллект 
Искусственный интеллект (ИИ) – это область исследований по моделированию интеллектуальной деятельности человека для решения различных задач. 
ИИ находится на стыке ряда наук: информатики, языкознания (математической 
лингвистики), психологии (когнитивной науки) и философии. Задачи ИИ требуют работы с данными и знаниями в виде символьных структур. В обработке 
символьной информации важна не только форма рассматриваемых знаний, но и 
их содержание и значение. Причиной возникновения в конце 1950-х гг. потребности в специализированных инструментальных программных средствах символьной обработки послужила неспособность процедурных языков отражать 

естественным образом в виде чисел и массивов объектов и ситуаций реального 
мира. Указанный недостаток процедурных средств, в частности, затруднял реализацию применяемых в решении задач ИИ эвристических методах. 
Функциональное программирование, как и логическое программирование, нашло большое применение в теории искусственного интеллекта и ее приложениях.  
Как известно, теоретические основы императивного программирования 
были заложены еще в 1930-х гг. Аланом Тьюрингом и Джоном фон Нейманом. 
Теория, положенная в основу функционального подхода, также родилась в 
1920–1930-х гг. В числе разработчиков математических основ функционального программирования можно назвать Моисея Шейнфинкеля и Хаскелла Карри, 
разработавших комбинаторную логику, и Алонзо Черча, создателя λисчисления. 
Теория так и оставалась теорией, пока в конце 1950-х гг. Джон Маккарти 
не разработал язык Лисп, который стал первым функциональным языком программирования и многие годы оставался единственным таковым. Лисп все еще 
используется, после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно 
бо́льшую но́шу на компилятор, облегчив таким образом свой труд. Нужда в 
этом возникла из-за все более возрастающей сложности программного обеспечения. 
Широкое распространение язык получил в конце 1970-х – начале 
1980-х гг. с появлением необходимой мощности вычислительных машин и соответствующего круга задач. В настоящее время Лисп является одним из главных инструментальных средств систем искусственного интеллекта. Он принят как один из двух основных языков программирования для Министерства 
обороны США и постепенно вытесняет второй язык – Ада. На Лиспе разработана и система AutoCAD.  
Основные особенности Лиспа [2]: 

• представление программы и данных производится одинаково – через 
списки: основными объектами, с которыми оперирует Лисп, являются 
списки. Отсюда происходит и название языка: словосочетание list 
processing означает «обработка списков». Это позволяет программе 
обрабатывать другие программы и даже саму себя; 

• Лисп, как правило, является интерпретирующим языком;