Файл: Обзор языков программирования высокого уровня (СИСТЕМЫ ПРОГРАММИРОВАНИЯ).pdf

Dick – ребенок Meri? – child(mery,dick).

Главные понятия ПРОЛОГа: списки, рекурсия, унификация, бэктрекинг. Списки – основная структура данных, применяемая в этом языке. Списки являются основой для организации всех сложных вычислений. Одно из основных свойств списка – отсутствие ограничений на элементы и размер списка. Вложенность списков также ничем не ограничивается. Список в языке трактуется как структура из двух элементов – «головы» и «хвоста». Это разделение является основой вычислений над списками, поэтому наиболее часто применяемый паттерн списка имеет вид [H|T].

Первый элемент списка может иметь любую структуру, а второй – также является списком. Пустой список не содержит элементов и обозначается как [ ].

Вторая базовая структурная единица языка – предикат имеет вид — p(A1,A2,..). Предикаты удобны для группирования данных в одну смысловую единицу. В отличие от списка, количество аргументов предиката фиксировано. Имя предиката пишется с малой буквы, как и все константы в языке.

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

Примеры списковых паттернов:

[H|T] – не пустой список;

[ ] – пустой список;

[A1,A2,A3] – список из трех произвольных элементов;

[A,A,A|T] – список, в котором первые три элемента совпадают;

[x,10|T] – список, в котором на первом месте стоит символьная константа “x”, а на втором – числовая константа 10.

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

Рекурсивность списков обеспечивает возможность простой формулировки алгоритма операций над списками.

Пример: Вычисление длины списка.

length([H|T],N):-length(T,N1), N is N1+1.

length([],0).

Пример: Инвертирование списка.

nrev([H|T],L) :- nrev(T,L1), append(L1,[H],L).

nrev([],[]).

В ПРОЛОГе нет функций, поэтому нельзя вставить, например, длину списка length(L) в качестве аргумента, как это делается во всех процедурных языках.

В то же время, ПРОЛОГ можно рассматривать как вполне императивный язык, в котором все операции, за исключением бэтрекинга, прописываются явно.

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

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

---

Пример: соединение списков.

append([H|T], L, [H|L2]):-append(T, L, L2).

append([], L, L).

Правильнее было бы записать второй аргумент в виде [H1|T1], поскольку второй аргумент должен быть списком, но это усложнит предикат, поскольку второй аргумент может быть и пустым списком.

Переменные в ПРОЛОГе – логические, т.е. повторная унификация внутри одной процедуры невозможна. Нельзя написать L = [a,b,c], а потом — L=[12]. Логичность переменных приводит к усложнению унификации, поскольку все унификации в теле одной процедуры не могут быть пересмотрены в процессе вычисления, а значит, они не могут противоречить друг другу.

Унификация логических переменных приводит к неожиданным эффектам, которые имеют вполне императивное объяснение.

Пример: варианты использования предиката соединения списков.

Соединение:

append([a,b,c],[d,e,f],L).

L = [a,b,c,d,e,f] =>

yes.

Проверка связи списков:

append([a,b,c],[1,2,3],[a,b,c,1,2,3]).

yes.

Разложение списка:

append(L1,L2,[a,b,c]).

L1=[a,b,c]

L2=[] ->;

L1=[a,b]

L2=[c] ->;

L1=[a]

L2=[b,c] ->;

L1=[]

L2=[a,b,c] ->;

no.

Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.

Вычитание списков:

append([a,b], L, [a,b,c,d]).

L=[c,d].

В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).

Пример недетерминированного предиката: Решение числовой головоломки.

/*

D O N A L D

+

G E R A L D

— R O B E R T */

sum(L1,L2,L3):-

sum1(L1,L2,L3,L1,L2,L3,0,[0,1,2,3,4,5,6,7,8,9]).

sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-

dl(L11,L111,E1),

dl(L12,L121,E2),

dl(L13,L131,E3),

val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),

sd(E1,E2,E3,Ii,Io),

sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).

sum1(L1,L2,L3,[],_,_,0,_):-!..

dl([H|T],[H|T1],E):- dl(T,T1,E).

dl([H],[],H).

val(E,L,L):-nonvar(E).

val(E,L1,L2):-del(E,L1,L2).

sd(A,B,C,Ii,Io):-

C1 is A+B+Ii,

C is C1 mod 10,

Io is C1 // 10

del(E,[E|T],T).

del(E,[H|T],[H|T1]):-del(E,T,T1).

s:-

A1=[D, O, N, A, L, D],

A2=[G, E, R, A, L, D],

A3=[R, O, B, E, R, T],

sum(A1,A2,A3),

write(A1),nl,

write(A2),nl,

write(A3),nl.

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

Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.

Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.

---

Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.

Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.

Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:

A+B+Ii = C+Io*10

Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.

Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.

Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.

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

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

Для этого надо делать такие операции как лексический и синтаксический анализ.

ЗАКЛЮЧЕНИЕ

Высокоуровневые языки программирования, в плане создания ПО, стали всё по большей части удаляться от машинных кодов и реализовывать различные, помимо процедурного, парадигм программирования. К ним относят также и реализацию объектно-ориентированных принципов. C++, Java, Python, JavaScript, Ruby… – спектр языков данного типа наиболее популярен и востребован сегодня. Они предоставляют больше возможностей для реализации разнообразного ПО и нельзя однозначно определить «специализацию» каждого из них.

В последнее время набирает популярность и иной вид программирования - функциональное (дальнейшее развитие уровня языка). Здесь уже другой вид абстракции для вычислений – функции, которые берут в качестве аргументов набор функций и возвращают другую. Роль переменных играют те же функции (привычные нам переменные – просто константные выражения, аналогичные final перед объявлением типа в Java). Собственно функция замкнута в своей области видимости, результат её работы зависит только от переданных аргументов. Отсюда вытекают два замечательных свойства:

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

---

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

Однако и порог вхождения выше, чем для ООП: для эффективного кода необходимо строить программу, описывая в виде функций алгоритм выполнения. Но также для чистого функционального стиля неплохо бы знать азы логики и теории категорий. Наиболее популярные – Haskell, Scala, F#. Но не бойтесь, в Java (как и в других современных языках третьего поколения) появились элементы функционального программирования и их возможно комбинировать вместе с ООП.

Область логического программирования (следующий уровень языков) пока не нашла широкого практического применения в силу малой востребованности.

Построение программ требует знание основ дискретной математики, логики предикатов, средств ограничений и других разделов математической логики. Наиболее популярный активный язык – Prolog.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Доусон М. Программируем на Pyton. – СПб.: Питер, 2017. – 416
2. Мэтиз Э. Изучаем Python. Программирование игр, визуализация данных, веб-приложения. – Спб.: Питер, 2017. – 496 c.
3. Химич А.В. Сравнительный анализ языков программирования: Паскаль, C++, Python // Молодежный научный форум: электр. сб. ст. по мат. XI междунар. студ. науч.-практ. конф. № 10(11). URL: https://nauchforum.ru/archive/MNF_interdisciplinarity/10(11).pdf (дата обращения: 21.08.2019) Базовые средства программирования/ В.Н. Шакин. - М.: Форум: НИЦ ИНФРА-М, 2015. - 304 с.
4. Введение в специальность программиста: Учебник / В.А. Гвоздева. - 2-e изд., испр. и доп. - М.: ИД ФОРУМ: НИЦ Инфра-М, 2013. - 208 с.
5. Голицына О.Л. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. - 3-e изд., перераб. и доп. - М.: Форум: ИНФРА-М, 2015. - 400 с
6. Ездаков, А. Л. Функциональное и логическое программирование: учебное пособие / А.Л.Ездаков. - 2-е изд. - М. : БИНОМ. Лаборатория знаний, 2011. - 119 с.
7. Информатика, автоматизированные информационные технологии и системы: Учебник / В.А. Гвоздева. - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. - 544 с.
8. Каймин В.А.Информатика: Учебник/ Каймин В. А., 6-е изд. - М.: НИЦ ИНФРА-М, 2015. - 285 с
9. Культин Н. Б. Основы программирования в Delphi XE. — СПб.: БХВ-Петербург, 2011. — 405 с.
10. Культин, Н. Б. Основы программирования в Delphi 7 / Н.Б. Культин. — 2-е изд., перераб. и доп. — СПб.: БХВ-Петербург, 2011. — 640 с.
11. Масленникова, О. Е. Основы искусственного интеллекта: учеб. пособие / О. Е. Масленникова, И. В. Гаврилова. - 2-е изд., стер. - М.: ФЛИНТА, 2013. - 282 c.
12. Машнин Т. С. Современные Java-технологии на практике. — СПб.: БХВ-Петербург, 2010. — 560 с.
13. Монахов В. В. Язык программирования Java и среда NetBeans. — 3-е изд., перераб. и доп. — СПб.: БХВ-Петербург, 2011. — 703 с.
14. Окулов, С. М. Основы программирования / С. М. Окулов. - 5-е изд., испр. - М.: БИНОМ. Лаборатория знаний, 2011. - 440 с.
15. Осипов Д. Л. Базы данных и Delphi. Теория и практика. — СПб.: БХВ-Петербург, 2011. — 746 с.
16. Основы алгоритмизации и программирования: Учебное пособие / В.Д. Колдаев; Под ред. Л.Г. Гагариной. - М.: ИД ФОРУМ: ИНФРА-М, 2015. - 416 с.
17. Программирование на языке Object Pascal: Учеб. пос. / Т.И.Немцова и др; Под ред. Л.Г.Гагариной. - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2013. - 496 с.
18. Программирование на языке высокого уровня. Учебное пособие / Т.И. Немцова; Под ред. Л.Г. Гагариной. - М.: ФОРУМ: ИНФРА-М, 2015. - 496 с.
19. Программирование на языке Си/А.В.Кузин, Е.В.Чумакова - М.: Форум, НИЦ ИНФРА-М, 2015. - 144 с.
20. Технология разработки программного обеспечения: Учеб. пос. / Л.Г.Гагарина, Е.В.Кокорева, Б.Д.Виснадул; Под ред. проф. Л.Г.Гагариной - М.: ИД ФОРУМ: НИЦ Инфра-М, 2013. - 400 с.
21. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. - 3-e изд., перераб. и доп. - М.: Форум: ИНФРА-М, 2015. - 400 с.

---