рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Функциональное программирование на языке ЛИСП

Функциональное программирование на языке ЛИСП - Конспект Лекций, раздел Информатика, ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Назначение И Общая Характеристи...

НАЗНАЧЕНИЕ И ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА

В программировании помимо процедурного подхода, представителями которого являются такие универсальные языки высокого уровня как Бейсик, Паскаль, Си, и логического подхода, представленного языком Пролог, существует еще одно направление - функциональное. Оно возникло в 1962 г. вместе с созданием Дж. Маккарти языка программирования Лисп (Lisp). Долгое время этот язык занимал особое место. Подавляющее большинство программ искусственного интеллекта составлено на языке Лисп. До сих пор он считается стандартным языком разработки систем искусственного интеллекта. Его популярность особенно велика в США. В нашей стране этот язык не получил широкого распространения (одна из причин - недостаток литературы о нем на русском языке), однако в настоящее время популярность этого языка быстро растет. Несмотря на то, что Лисп - один из самых старых используемых языков программирования, у него многое еще впереди.

Язык Лисп - один из первых языков обработки данных в символьной форме. Его название происходит от английских слов «list processing » - «обработка списков». В Лиспе и программа, и обрабатываемые ею данные представляются в одной и той же форме - в форме списка. Таким образом, программы могут обрабатывать и преобразовывать другие программы и даже самих себя.

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

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

Имеется большое число систем программирования на Лиспе, реализованных для компьютеров различных типов. Как правило, это интерпретирующие системы, работающие в интерактивном (диалоговом) режиме. Соответствующие описания и команды вводятся с клавиатуры после приглашения ("_"), затем прочитывается результат.

ОСНОВНЫЕ ЭЛЕМЕНТЫ ПРОГРАММЫ НА ЛИСПЕ. СПИСКИ

Программы на языке Лисп строятся из простейших неделимых элементов, называемых атомами. Символы и числа представляют собой атомы, из них состоят все остальные структуры.

Символ - это имя, состоящее из букв, цифр и специальных знаков, которое обозначает какой-нибудь предмет или действие из реального мира, а также число, функцию (программу) и другие объекты. Наряду с символами используются и числа (значения), которые могут быть целыми (например, 543), десятичными (например, 3.789) и в представлении с мантиссой и порядком (например, 1.0243Е-6).

Главной структурой в Лиспе является список.

Списком называется упорядоченная последовательность, элементамикоторойявляются либо атомы, либо списки (подсписки). Списки заключаются в круглые списки, аих элементы разделяются пробелами. Например,

 


(ab(cd)e)

(В группе 18 студентов)

(((((первый) 2) третий) 4) 5).

 

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

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

 

(а1 а2 ... aN) = (а1. (а2.... (aN.Nil)...)).

 

Здесь Nil - это предопределенная константа, означающая пустой список (и одновременно логическое значение «Ложь»).

Атомы и списки называютсяS-выражениями. Все вышесказанное можно обобщить в следующих формах Бэкуса - Наура

 

<S-выражение> :: = <атом> | <список>

<список> :: = (<внутренняя часть>)

<внутренняя часть> :: = NIL | <S-выражение> [{внутренняя часть}}

<атом> :: = цепочка алфавитно-цифровых символов без пробелов или специальных символов (,);.

 

Списки в Лиспе - основное средство представления знаний. Например,с помощью вложенных списков может быть представлена характеристика человека:

(сотрудник

(имя Петр)

(отчество Петрович )

(фамилия Иванов)

( образование ( среднее (с 1969 по 1979))

(высшее ( ВГУ г.Воронеж (с 1979 по 1982)

(МГУ г. Москва (с 1982 по 1984)) ( специальность

(техническая кибернетика)

(программирование)

(стаж (с 1984 по 1997)

)

ФУНКЦИИ

Функции в Лиспе аналогично математическим функциям ставят в соответствие элементам из одного множества - определения (аргументов) - единственный элемент из множества значений. В программах следует различать определение функций и вызов (применение) функции.

В языке Лисп принята единообразная префиксная форма записи, при которой как имя функции или действия, так и аргументы записываются внутри скобок:

 

(f x)

(g x y) (сумма_квадратов 2 3).

 

Аналогично записываются и арифметические действия:

 

(+ х у)

(*x(+yz))

(+ (^ х х) (+ у у)).

 


Определение функций и их вычисление в Лиспе основано на лямбда-исчислении Черча. В 1-исчислении Черча функция записывается в виде

 

1(х1,х2,... ,xn) .fn

 

В Лиспе 1-выражение имеет вид (LAMBDA (xl, x2,..., xn).fn).

Символ LAMBDA означает, что мы имеем дело с определением функции. Символы xi являются формальными параметрами, они образуют список, называемый лямбда-списком; fn - это тело функции, которая может иметь произвольную форму, допускаемую интерпретатором Лиспа. Телом функции может быть, например, константа или композиция из вызовов функций. Функцию, вычисляющую сумму квадратов двух чисел, можно, например, определить так:

 

(lambda(xy)(+(*xx)(*yy))).

 

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

 

(лямбда-выражение а1 а2 ... an)

 

Здесь ai - фактические параметры, с которыми происходит вычисление.

Например

((lambda (х у) (+ (* х х) (* у у))) 3 4).

Результат: 25.

Определить новую функцию и дать ей имя для последующих вызовов можно с помощью функции DEFUN (define function):

 

(DEFUN имя лямбда-список тело).


DEFUN соединяет символ с лямбда-выражением, и символ начинает представлять (именовать) определенные этим лямбда-выражением вычисления. Значением этой формы является имя новой функции:

 

(defun sumsquare (х у) (+ (* х х) (* у у))) .

 

Результат: sumsquare.

Вызов (применение) этой функции:

(sumsquare 34)

Результат: 25.

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

В Лиспе передача параметров происходит по значению. Формальные параметры функций являются статическими и локальными, т.е. действительны только внутри той формы, в которой они определены.

Основу для построения различных функций образует набор небольшого числа примитивных встроенных функций. Базовыми функциями обработки S-выражений являются функции

 

CAR, CDR, CONS, ATOM, EQ, EQL, =

 

и другие, смысл которых отражен в табл. 7.1

 


Таблица 7.1

Базовые функции обработки S-выражений

Функция Вызов Действие Пример использования
CAR (CAR список) Возвращает головною часть списка - его 1-й элемент (CAR(1 234)) Результат:1
CDR (CDR список) Возвращает хвостовую часть списка- все. кроме 1-го элемента (CDR(! 234)) Результат:(2 3 4)
CONS (CONS S-выражение список) Строит список из переданных в качестве аргументов головы и хвоста (CONS I (2 3 4)) Результат: (1234)
ATOM (ATOMS-выражение -) Предикат; проверяет, является ли аргумент атомом, и возвращает либо t (истина), либо Nil или ("(ложь) (ATOM A) : t (ATOM (1 2 3)): Nil
EQ (EQ символ Символ) Предикат: проверяет тождественность символов-аргументов, неприменим для чисел (EQ A A): (EQ X (CAR (X Y Z))): t t
EQL (EQL число число) Предикат, проверяет тождественность чисел одного типа (EQL 3.0 3.0): t
= (= число число) Предикат, проверяет тождественность чисел различных типов (=30.3el):t
EQUAL (EQUAL число или список число или список) Аналогична EQL, но, кроме того, проверяет идентичность списков (EQUAL(xyz)(xyz)):t
EQUALP (EQUALP объект объект) Проверка наиболее общего равенства  
NULL (NULL список) Проверка, является ли аргумент пустым списком  
NOT (NOT логическая величина) Логическое отрицание  
NTH (NTH n список) Выделение n-го элемента списка (NTH 2 (1 2 3)): 3 (индексы начинаются с 0)
FIRST   Предикаты, выделяющие  
SECOND   Соответствующие элементы списка  
LAST      
LIST (LIST apr арг2 ...) Строит из аргументов список (LIST a b (с)): (a b c)

 

Отметим, что в программах на Лиспе надо тщательно отличать значения от их обозначений.

В Лиспе константы обозначают самих себя. Выражения типа (* 2 2) сразу вычисляются. Чтобы избежать нежелательного вычисления выражения используется функция QUOTE или знак апострофа (') перед выражением:

 

(* 2 2) : 4

' (* 2 2) :' (* 2 2) – список

 

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

 

(SET 'операции'(+ - */))

 

Знак ' используется для подавления вычисления аргументов функции SET. Функция SETQ не вычисляет значения 1-го аргумента (а 2-го вычисляет).

На значение символа можно сослаться, указав его без апострофа (').

Для занесения значений в ячейку памяти, связанной с символом, можно пользоваться обобщенной функцией присваивания SETF, размещающей значения в соответствующей ячейке памяти:

 

(SETF ячейка_памяти значение).

 

Переменная «ячейка_памяти» без апострофа указывает на ячейку памяти. Присвоение, выполняемое функциям» SET, SETQ и SETF, является побочным эффектом , этих функций, помимо того, данные функции возвращают присваиваемые значения.

ФОРМЫ. УПРАВЛЯЮЩИЕ КОНСТРУКЦИИ В ЛИСП-ПРОГРАММЕ

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

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

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

– Конец работы –

Эта тема принадлежит разделу:

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ Конспект лекций для студентов специальности Прикладная информатика по отраслям...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Функциональное программирование на языке ЛИСП

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Определение информационной технологии
Технология при переводе с греческого (techne) означает искусство, мастерство, умение, а не что иное, как процессы. Под процессом следует понимать определенную совокупность действий, напра

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

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

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

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

Признак деления-проблемы, стоящие на пути информатизации общества
  1-й этап ( до конца 60-х гг.) характеризуется проблемой обработки больших объемов данных в условиях ограниченных возможностей аппаратных средств. 2-й этап ( до конца 70-х г

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

Признак деления - виды инструментария технологии
  1-й этап ( до второй половины XIX в.)-”ручная” информационная технология, инструментарий которой составляли: перо, чернильница, книга. Коммуникации осуществлялись ручным способом пу

Устаревание информационной технологии
  Для информационных технологий является вполне естественным то, что они устаревают и заменяются новыми. Пример 3.1. На смену технологии пакетной обработки п

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

Характер и назначение
Информационная технология обработки данных предназначена для решения хорошо структурированных задач, по которым имеются необходимые входные данные и известны алгоритмы и другие стандартные процедур

Основные компоненты
Представим основные компоненты информационной технологии обработки данных и приведем их характеристики. Сбор данных .По мере того как фирма производит продукцию или ус

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

Основные компоненты
Входная информация поступает из систем операционного уровня. Выходная информация формируется в виде управленческих отчетов в в удобном для принятия решения виде. Содержимое базы данных при

Характеристика и назначение
Исторически автоматизация началась на производстве и затем распространилась на офис, имея вначале целью лишь автоматизацию рутинной секретарской работ .По мере развития средств коммуникаций автомат

Основные компоненты
База данных .Обязательным компонентом любой технологии является база данных. В автоматизированном офисе база данных концентрирует в себе данные о производственной системе фирмы так

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

Основные компоненты
Рассмотрим структуру системы поддержки принятия решений (рис. 3.16.), а также функции составляющих ее блоков, которые определяют основные технологические операции.

Характеристика и назначение
Наибольший прогресс среди компьютерных информационных систем отмечен в области разработки экспертных систем, основанных на использовании искусственного интеллекта. Экспертные системы дают во

Основные компоненты
Основными компонентами информационной технологии, используемой в экспертной системе являются (рис. 3.17.): интерфейс пользователя, база знаний, интерпретатор, модуль создания системы. &nbs

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

Модели передачи, обработки, накопления данных
  Информация передаётся в виде сообщений от некоторого источника информации к её приёмнику посредством канала связи

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

ЛЕКЦИЯ №6. МОДЕЛИ, МЕТОДЫ И СРЕДСТВА РЕАЛИЗАЦИИ НИТ
  Начинают широко использоваться в различных областях глобальные и локальные компьютерные сети. Ей предсказывают в ближайшем будущем бурный рост, обусловленный популярностью ее основа

Динамическое управление вычислением
• THROW, CATCH, а также BLOCK. Эти управляющие формы (кроме QUOTE и лямбда-вызова, а также вызовов функций), в основном, используются в теле лямбда-выражений, определяющих функции.

Логическое программирование на языке ПРОЛОГ
  Язык Пролог является представителем семейства языков логического программирования и в сравнении с традиционными языками программирования, предназначенными для записи алгоритмов, так

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

Рабочая документация (рабочий проект)
На данном этапе осуществляется адаптация базовых средств программного обеспечения (операционной системы, СУБД, методо-ориентированных ППП, инструментальных сред конечного пользователя — текс

Структура программных продуктов
  В большей степени программные продукты не являются монолитом и имеют конструкцию (архитектуру) построения — состав и взаимосвязь программных модулей. Модуль

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

Графический интерфейс пользователя
Графический интерфейс пользователя (Graphics User Interface—GUI)— ГИП является обязательным компонентом большинства современных программных продуктов, ориентированных на работу конечного пол

НИСХОДЯЩЕЕ ПРОЕКТИРОВАНИЕ
Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы ("сверху-вниз"). В результате с

Свойства модуля
Модульное программирование основано на понятии модуля — логически взаимосвязанной совокупности функциональных элементов, оформленных в виде отдельных программных модулей. Модуль харак

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

СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
Структурное программирование основано на модульной структуре программного продукта и типовых управляющих структурах алгоритмов обработки данных различных программных модулей (рис. 18.

ОСНОВНЫЕ ПОНЯТИЯ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОЕКТИРОВАНИЯ
Метод объектно-ориентированного проектирования основывается на: · модели построения системы как совокупности объектов абстрактного типа данных; · модульной структуре програ

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги