lab1

Отчет по лабораторной работе №1

Работа со списками и реляционным представлением данных

по курсу "Логическое программирование"

Введение

Любой список в Прологе можно представить как двоичное дерево, в листьях которого находятся элементы списка или пустой список. Элементами списка могут быть любые объекты. То есть он либо пуст, либо состоит из 2х частей: головы и хвоста, который сам является списком.

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

Набор стандартных предикатов обработки списков наводит на мысль, что списки можно применять для представления множеств, только в множестве порядок элементов не существенен, а для списка порядок имеет значение, кроме того один и тот же объект может встретиться в списке несколько раз.

Задание 1.1: Предикат обработки списка

add_last_std(E,L1,L2) - добавляет элемент в конец списка с помощью стандартных предикатов add_last(E,L1,L2) - добавляет элемент в конец списка без использования стандартных предикатов

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

| ?- add_last_std(1,[],X).
X = [1]
| ?- add_last_std(1,[2,1,2,1,2],X).
X = [2,1,2,1,2,1]
| ?- add_last(2,[0,0,0],X).
X = [0,0,0,2]
| ?- add_last(5,[1,2,3,4,5,6,7,8,9,10,11,12,13,14],X).
X = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,5]

Реализация:

add_last_std(X, L1, L2):-append(L1, [X], L2).

С помощью стандартного предиката append объединяем исходный список и список, состоящий из элемента, который нужно вставить в конец. Т.к. его нужно вставить в конец, то он будет стоять на втором месте в предикате append.

add_last(X, [], [X]).
add_last(X, [H|T], [H|R]):-add_last(X, T, R).

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

Задание 1.2: Предикат обработки числового списка

is_arithm(L) - проверяет список на арифметическую прогрессию

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

| ?- is_arithm([1,2,3,4,5]).
yes
| ?- is_arithm([0,10,20,30,40,50]).
yes
| ?- is_arithm([1,3,4,7,10]).
no
| ?- is_arithm([1,3,5,7,9,10]).
no
| ?- is_arithm([1,3,5,7,9,11]).
yes

Реализация:

is_arithm([X,Y,Z|T]):-
    !,
    X - Y =:= Y - Z,
    is_arithm([Y,Z|T]).
is_arithm(_).

"Обрезаем" в голове списка 3 элемента. Используем отсечение, чтобы выйти из рекурсии при неуспехе. Сравниваем разности 1ого и 2ого и 2ого и 3его элементов. Если равенство не выполняется, то выходим из рекурсии с неуспехом. Иначе рекурсивно обрабатываем список без 1ого элемента.

Задание 2: Реляционное представление данных

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

Мое представление условно можно обозначить как списки групп и журнал успеваемости по предметам. Главный недостаток такого представления в том, что все факты об оценках находятся внутри структур, составляющих список. И оценки находятся в общем списке, т.е. нет разделения по группам. Не всегда удобно обращаться со списками, когда нужно получить информацию об оценках. Отношения вида "группа -- предмет" сложно задаются. Возможно, было бы удобно воспользоваться встроенными предикатами assert/asserta/assertz, но, во-первых, мы должны знать, что находится внутри списка со структурами grade, во-вторых, это модификация исходных данных, что, обычно, нежелательно. Факты со списками групп оказались почти бесполезны. Думаю, было бы удобнее, если информация о группе хранилась бы в структуре grade. Из плюсов можно отметить простоту анализа успеваемости по отдельному предмету и сравнение оценок по разным предметам.

Для своего представления данных я выбрала 2 вариант.

1 задание: Напечатать средний балл для каждого предмета.

average_mark(Sub,Mark) - печатает средний балл для заданного предмета.

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

| ?- average_mark('Логическое программирование',X).
X = 4.1071428571428568
| ?- average_mark('Математический анализ',X).
X = 4.0357142857142856
| ?- average_mark('Психология',X).
X = 3.8571428571428572

Реализация:

% Сумма оценок по предмету
% (список оценок, сумма оценок)
sum_grades([],0).
sum_grades([grade(X,Y)|T],N):- sum_grades(T,M), N is Y + M.

% Средний балл для предмета
% (название предмета, средняя оценка)
average_mark(Sub,Mark):-
    subject(Sub,Y),
    sum_grades(Y, Sum),
    length(Y, Len),
    Mark is Sum / Len.

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

2 задание: Для каждой группы, найти количество несдавших студентов

do_not_pass_group(Gr,Count) - находит количество несдавших студентов в заданной группе

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

| ?- do_not_pass_group(101,X).
X = 3
| ?- do_not_pass_group(102,X).
X = 3
| ?- do_not_pass_group(103,X).
X = 2
| ?- do_not_pass_group(104,X).
X = 2

Реализация:

% Список всех оценок по всем предметам
% (список предметов, список оценок)
all_marks([],L).
all_marks([H|T], List_pass):-subject(H,X), all_marks(T, New_list), append(X, New_list, List_pass).

% Удаление повторяющихся оценок, чтобы если в списке один и тот же студент получил больше одной 2 по разным предметам, он посчитался лишь один раз
delete_all(_,[],[]).
delete_all(X,[X|L],L1):-delete_all(X,L,L1).
delete_all(X,[Y|L],[Y|L1]):- X \= Y, delete_all(X,L,L1).

remove_same([],[]).
remove_same([H|T],[H|T1]):-delete_all(H,T,T2), remove_same(T2,T1).

% Проверяем, сколько студентов, получивших 2, имеются в нужной группе
% (список всех оценок, список группы, количество несдавших студентов из группы)
check([],L,0).
check([grade(X,Y)|T],L,N):- Y < 3, my_member(X, L), !, check(T,L,M), N is M + 1.
check([_|T],L,N):-check(T,L,N).


% Количество несдавших студентов в группе
% (номер группы, число несдавших)
do_not_pass_group(Gr,Count):-
    group(Gr, Lgroup),
    findall(Sub, subject(Sub,_), Subs),
    all_marks(Subs, List_pass),
    remove_same(List_dont_pass, New),
    check(New, Lgroup, Count).

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

3 задание: Найти количество несдавших студентов для каждого из предметов

do_not_pass_sub(Sub,Count) - находит количество несдавших студентов для заданного предмета

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

| ?- do_not_pass_sub('Логическое программирование',X).
X = 3
| ?- do_not_pass_sub('Математический анализ',X).
X = 1
| ?- do_not_pass_sub('Психология',X).
X = 2

Реализация:

%(список оценок, число несдавших)
count_do_not_pass([],0).
count_do_not_pass([grade(X,Y)|T],N):- Y < 3, !, count_do_not_pass(T,M), N is M + 1.
count_do_not_pass([_|T],N):-count_do_not_pass(T,N).

% (название предмета, число студентов)
do_not_pass_sub(Sub,Count):-
    subject(Sub,Y),
    count_do_not_pass(Y,Count).

Получаем список оценок по нужному предмету, считаем сколько из них двойки.

Выводы

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