Решаемые задачи - Лекция введение. Логическая программа. Основные

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

  1. Получение остаточной процедуры.

Если даны последующие объекты:

P (x1, x2, ..., xn) — некая процедура.

x1 = a1, x2 = a2 — известные значения характеристик Решаемые задачи - Лекция введение. Логическая программа. Основные.

x3, ..., xn — неведомые значения характеристик.

Требуется получить остаточную функцию P1 (x3, ..., xn). Эта задачка решается лишь на узеньком классе программ.

  1. ^ Построение математического описания функций.

Пусть имеется программка P. Для неё определены входные Решаемые задачи - Лекция введение. Логическая программа. Основные значения и выходные значения . Требуется выстроить математичекое описание функции
f : Dx1  ...  Dxn  Dy1  ...  Dym.

  1. Определение формальной семантики языка программирования.

  2. Описание динамических структур данных.

  3. Автоматическое построение «значительной» части программки по описанию структур Решаемые задачи - Лекция введение. Логическая программа. Основные данных, которые обрабатываются создаваемой программкой.

  4. Подтверждение наличия некого характеристики программки.

  5. ^ Эквивалентная трансформация программ.

Все эти задачки довольно просто решаются средствами многофункционального программиро­вания, но фактически неразрешимы в властных языках.
^ Справочный материал Решаемые задачи - Лекция введение. Логическая программа. Основные Языки многофункционального программирования
В этом разделе приведено короткое описание неких языков многофункционального прог­раммирования (очень немногих). Дополнительную информацию можно почерпнуть, прос­мотрев ресурсы, перечисленные в последующем разделе.


^ Лекция 1. «Структуры данных и базовые операции»
Как уже говорилось в первой лекции, основой Решаемые задачи - Лекция введение. Логическая программа. Основные многофункциональной парадигмы прог­рам­ми­ро­вания в большей мере являются такие направления развития математической мысли, как комбинаторная логика и -исчисление. В свою очередь последнее более плотно сплетено с многофункциональным программированием, и конкретно -исчисление Решаемые задачи - Лекция введение. Логическая программа. Основные именуют те­о­ре­ти­чес­ки­ми основами многофункционального программирования.

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

Пусть заданы объекты некого первичного типа A. На данный момент совсем не принципиально, что конкретно представляют собой эти выделенные объекты. Обычно считается, что на этих объ Решаемые задачи - Лекция введение. Логическая программа. Основные­ектах определён набор базовых операций и предикатов. По традиции, которая пошла ещё от МакКарти (создатель Lisp’а), такие объекты именуются атомами. В теории фак­ти­чес­кий метод реализации базовых операций и предикатов Решаемые задачи - Лекция введение. Логическая программа. Основные совсем не важен, их су­щес­т­во­вание просто постулируется. Но каждый определенный многофункциональный язык ре­а­ли­зу­ет базовый набор по-своему.

В качестве базовых операций обычно (и сначала это Решаемые задачи - Лекция введение. Логическая программа. Основные разъясняется те­о­ре­тической не­об­хо­димостью) выделяются последующие три:

  1. Операция сотворения пары — prefix (x, y)  x : y  [x | y]. Эта операция также именуется кон­структором либо составителем.

  2. Операция отсечения Решаемые задачи - Лекция введение. Логическая программа. Основные головы — head (x)  h (x). Это 1-ая селективная операция.

  3. Операция отсечения хвоста — tail (x)  t (x). Это 2-ая селективная операция.

Селективные операции отсечения головы и хвоста также именуют просто селекторами Решаемые задачи - Лекция введение. Логическая программа. Основные. Вы­деленные операции связаны вместе последующими 3-мя теоремами:

  1. head (x : y) = x

  2. tail (x : y) = y

  3. prefix (head (x : y), tail (x : y)) = (x : y)

Всё огромное количество объектов, которые можно сконструировать из объектов первичного Решаемые задачи - Лекция введение. Логическая программа. Основные ти­па в итоге случайного внедрения базовых операций, носит заглавие огромное количество S-выражений (обозначение — Sexpr (A)). К примеру:

a1 : (a2 : a3)  Sexpr

Для последующих исследовательских работ вводится фиксированный атом, который также при­над Решаемые задачи - Лекция введение. Логическая программа. Основные­ле­жит первичному типу A. Этот атом в предстоящем будет называться «пустым списком» и обозначаться знаками [] (хотя в различных языках многофункционального програмирования мо­гут существовать свои обозначения для пустого перечня). Сейчас можно Решаемые задачи - Лекция введение. Логическая программа. Основные найти то, чем фактически занимается функциональное программирование — собственное под­мно­жес­тво List (A)  Sexpr (A), которое именуется «список над A».

Определение:

1. Пустой перечень []  List (A)

2. x  A & y  List (A)  x Решаемые задачи - Лекция введение. Логическая программа. Основные : y  List (A)

Главное свойство перечня: x  List (A) & x  []  head (x)  A; tail (x)  List (A).

Для обозначения перечня из n частей можно употреблять огромное количество разных но­та­ций, но Решаемые задачи - Лекция введение. Логическая программа. Основные тут будет употребляться только такая: [a1, a2, ..., an]. Применяя к такому спис­ку спецефическим образом операции head и tail можно добраться до хоть какого элемента спис­ка, т.к.:

head Решаемые задачи - Лекция введение. Логическая программа. Основные ([a1, a2, ..., an]) = a1

tail ([a1, a2, ..., an]) = [a2, ..., an] (при n > 0).

Не считая списков вводится очередной тип данных, который носит заглавие «списочная струк­тура над A» (обозначение — List_str (A)), при всем Решаемые задачи - Лекция введение. Логическая программа. Основные этом можно выстроить следющую струк­туру отношений: List (A)  List_str (A)  Sexpr (A). Определение списочной струк­ту­ры смотрится последующим образом:

Определение:

1. a  A  a  List_str (A)

2. List (List Решаемые задачи - Лекция введение. Логическая программа. Основные_str (A))  List_str (A)

Т.е. видно, что списочная структура — это перечень, элементами которого могут быть как атомы, так и другие списочные структуру, в том числе и простые списки. При­ме Решаемые задачи - Лекция введение. Логическая программа. Основные­ром списочной структуры, которая в тоже время не является обычным перечнем, может слу­жить последующее выражение: [a1, [a2, a3, [a4]], a5]. Для списочных структур вводится та­кое понятие, как уровень вложенности.


reshenie-15-noyabrya-2010g-40-stranica-8.html
reshenie-15-oktyabrya-2012-goda.html
reshenie-17-04-2013.html