Ирина Эланс

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

Списки, строки, файлы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет информационных технологий и робототехники (ФИТР)

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

КУРСОВОЙ ПРОЕКТ

по дисциплине: «Функциональное и логическое программирование»

на тему: «Списки, строки, файлы»

Исполнитель: студентка гр. 307228

Малиновская О.В.

Руководитель проекта: доцент

Ковальков А.Т.

Минск 2012

Белорусский национальный технический университет

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине «Функциональное и логическое программирование»

Тема «Списки, строки, файлы»____________________________

__________________________________________________________________

Исполнитель:___________________________________________(Малиновсая О.В.)

(подпись)

Студент___4____курса_307228__группы

Руководитель : _________________________________________(Ковальков А.Т.)

(подпись)

Минск 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

1 Постановка задачи 8

2. теоретическая часть 9

2.1 Общие сведения 9

2.2 Списки 11

2.2 Строки 14

2.2 Файлы 16

3. Структурная схема программы 18

4. ОПИСАНИЕ ПРЕДИКАТОВ 19

5 ТЕКСТ ПРОГРАММЫ 20

6 ТЕСТИРОВАНИЕ ПРОГРАММЫ 26

7 РУКОВОДСТВО ДЛЯ ПОЛЬЗОВАТЕЛЯ 27

ВЫВОДЫ 29

ЛИТЕРАТУРА 30

ПРИЛОЖЕНИЕ 31

ВВЕДЕНИЕ

Prolog (от “PROgramming in LOGic”) — декларативный язык программирования общего назначения.

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

Стандарт языка дан в ISO/IEC 13211-1 (1995 год).

Пролог — уникален по своей природе, он появился благодаря счастливому совпадению. Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.

Prolog — один из старейших и все еще один из наиболее популярных языков логического программирования, хотя он значительно менее популярен, чем основные императивные языки. Он используется в системах обработки естественных языков, исследованиях искусственного интеллекта, экспертных системах, онтологиях и других предметных областях, для которых естественно использование логической парадигмы. Так в данном курсовом проекте реализуется работа со списками, строками и файлами средствами языка Prolog.

Prolog был создан под влиянием более раннего языка Planner и позаимствовал из него следующие идеи:

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

Главной парадигмой, реализованной в языке Prolog, является логическое программирование. Как и для большинства старых языков, более поздние реализации, например, Visual Prolog, добавляют в язык более поздние парадигмы, например, объектно-ориентированное или управляемое событиями программирование, иногда даже с элементами императивного стиля.

Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Поэтому программа на Прологе не является таковой в традиционном понимании, так как не содержит управляющих конструкций типа if … then, while … do; нет даже оператора присваивания. В Прологе задействованы другие механизмы. Задача описывается в терминах фактов и правил, а поиск решения Пролог берет на себя посредством встроенного механизма логического вывода.

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

Пролог реализован практически для всех известных операционных систем и платформ. В число операционных систем входят OS для мэйнфреймов, всё семейство Unix, Windows, OS для мобильных платформ.

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

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

Наиболее заметные тенденции в истории развития языка Prolog

В развитии языка Prolog наблюдаются очень интересные тенденции. Этот язык быстро приобрел популярность в Европе как инструмент практического программирования. В Японии вокруг языка Prolog были сосредоточены все разработки компьютеров пятого поколения. С другой стороны, в США этот язык в целом был принят с небольшим опозданием в связи с некоторыми историческими причинами. Одна из них состояла в том, что Соединенные Штаты вначале познакомились с языком Microplanner, который также был близок к идее логического программирования, но неэффективно реализован. Определенная доля низкой популярности Prolog в этой стране объясняется также реакцией на существовавшую вначале “ортодоксальную школу” логического программирования, представители которой настаивали на использовании чистой логики и требовали, чтобы логический подход не был “запятнан” практическими средствами, не относящимися к логике. В прошлом это привело к широкому распространению неверных взглядов на язык Prolog. Например, некоторые считали, что на этом языке можно программировать только рассуждения с выводом от целей к фактам. Но истина заключается в том, что Prolog — универсальный язык программирования и на нем может быть реализован любой алгоритм. Далекая от реальности позиция “ортодоксальной школы” была преодолена практиками языка Prolog, которые приняли более прагматический подход, воспользовавшись плодотворным объединением нового, декларативного подхода с традиционным, процедурным.

ПОСТАНОВКА ЗАДАЧИ

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

1.Нахождение в списке двух наибольших элементов

2.Нахождение в списке элементов, кратных заданному числу

3.Подсчет в строке количества цифровых символов

4.Разбиение строки на две строки примерно одинаковой длины по границе слова

5.Объединение трех текстовых файла в один

6.Нахождение в текстовом файле двух самых коротких строк

Нужная операция выбирается с помощью меню.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Общие сведения

Prolog использует один тип данных, терм, который бывает нескольких типов:

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

Программы, написанные на чистом Prolog, описывают отношения между обрабатываемыми сущностями при помощи клауз Хорна. Клауза — это формула вида Голова :- Тело., которая читается как “чтобы доказать/решить Голову, следует доказать/решить Тело”. Тело клаузы состоит из нескольких предикатов (целей клаузы), скомбинированных с помощью конъюнкции и дизъюнкции. Клаузы с пустым телом называются фактами и эквивалентны клаузам вида Голова :- true. (true — не атом, как в других языках, а встроенный предикат).

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

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

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

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

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

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

Списки

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

Списки могут быть представлены как специального вида дерево. Список — это любой пустой список, не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [ ] — открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента 'а', есть .(а, []).

Аналогично список, состоящий из атомов a, b и с, мог бы быть записан как .(а,.(b,.(с,[]))).

Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[] и а.(b.(с.[]))). Второй список можно было бы записать просто как а.b.с.[], так как функтор точка — правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.b отличается от списка b.а.

Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка. Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде [a] и [а, b, с]. Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:

[ ]

[конкретный, человек, [любит, ловить, рыбу]]

[а, V1, b, [X, Y]]

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

Работа со списками основана на расщеплении их на голову и хвост списка. Голова списка — это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка — это второй аргумент функтора '.'.В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет список, состоящий из всех элементов исходного списка, за исключением первого его элемента.

Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой X и хвостом Y. Это записывается как [X|Y], где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, a Y — с хвостом списка.

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

Для кодировки литер используется код ASCII. Например, строка "system" преобразуется в Прологе в следующий список: [115, 121, 115, 116, 101, 109].

В разделе описания доменов списки описываются следующим образом:

DOMAINS

<имя спискового домена>=<имя домена элементов списка>*

Звездочка после имени домена указывает на то, что мы описываем список, состоящий из объектов соответствующего типа.

В классическом Прологе элементы списка могут принадлежать разным доменам, например: [monday, 1, "понедельник"].

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

Например, следующее описание:

DOMAINS

element = i(integer); c(char); s(string)

listE = element*

позволит иметь дело со списками вида

[i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"),

i(48),c('!')]

Дадим рекурсивное определение списка: список — это структура данных, определяемая следующим образом:

пустой список ([ ]) является списком;
структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

Строки

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

При прогарммировании на Прологе символы могу быть записаны при помощи кодов ASCII. Обратная связь, за которой следует код ASCII символа, интерпретируется как символ. Для представления одиночного символа выражение \N должно быть заключено в одинарные кавычки. Для представления строки символов их коды помещают друг за другом и вся строка заключается в двойные кавычки.

Стандартные предикаты для работы со строками

Определение длины строки

Str_len (строка, длина) (string, string) : (i, o) (i, i)

(i, o) – с параметром длина связывается количество символов в строке

(i, i) – выполняетсмя успешно, если строка имеет указанную длину.

Конкатенация строк

concat (Стр1, Стр2, Стр3) (string, string, string) : (i, i, o) (o, i, i) (i, o, i) (i, i, i)

(i, i, o) concat ("фут”, "бол”, X) X=”футбол”

(o, i, i) concat (X, "ball”, "football”) X= "foot”

(i, i, i) concat ("foot”, "ball”, "football”) True

Создание подстрок

frontstr (КопСтр, ВхСтр, ВыхСтр, Остаток) (integer, string, string, string) : (i, i, o, o).

Выходная строка получается из входной строки отрезанием начальных символов, количество которых определяется параметром КолСим. Остаток строки определяется параметром Остаток.

Разделение строки на две части

frontchar (строка, ПервСимвол, Остаток) (string, char, string) (i, o, o) (i, i, o) (i, o, i) (i, i, i)(o, i, i)

(i, o, o) frontchar ("Sad”, X, Y) X=’S’, Y=’ad’

(i, i, o) frontchar ("Sad”, ‘S’, X) X=’ad’

(i, o, i) frontchar ("Sad”, X, ‘ad’) X=’S’

(i, i, i) frontchar ("Sad”, ‘S’, ‘ad’) true

(o ,i, i) frontchar (X, ‘S’, ‘ad’) X=”Sad”

Используется для преобразования строки в список символов

convert (" ", [ ]).

convert (Str, [H|T]):- frontchar (Str, H, Ost), convert (Ost, T).

Прверка на строку

isname (строка) (string) : (i)

Имена испоьзуются для обозначения символических констант, предикатов и переменных.

Формирование атомов из строк

fronttoken (Строка, Атом, Остаток) (string, string, string) : (i, o, o) (i, i, o) (i, o, i) (i, i, i) (o, i, i)

Атом – последовательность символов, имеющих смысл. Атомы могут быть : именем ТП, строчным представлением числа, отдельным символом (кроме пробела).

(i, i, o) fronttoken ("Go to cursor”, X, Y) X=”Go” Y=”to cursor”

Файлы

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

Для открытия файлов в ТП существует четыре предиката:

openwrite(log_name, DOS_name),

openread(log_name, DOS_name),

openmodify(log_name, DOS_name),

openappend(log_name, DOS_name).

Предикаты open... устанавливают связь между внешним (для Пролога) DOS-именем файла и его внутренним (логическим) именем, используемым в пределах программы. Предикат openwrite создает новый файл и открывает его для записи, предикат openread открывает существующий файл для чтения, предикат openmodify открывает файл для чтения и записи, а предикат openappend- для добавления информации в конец существующего файла.

Для активизации объявленных файлов используются предикаты writedevice и readdevice. Предикат writedevice (log_name) выполняет переадресацию вывода в указанный файл, а предикат readdevice (log_name) производит переадресацию ввода с указанного файла. Для завершения работы с открытым ранее файлом используется предикат closefile (log_name).

В ТП следующие имена стандартных устройств ввода-вывода зарезервированы:

screen - стандартный вывод на экран (stdout);

keyboard - стандартный ввод с клавиатуры (stdin);

printer - вывод на устройство печати;

com1 - ввод-вывод через порт.

Все остальные логические имена будут восприниматься ТПкак имена файлов. Логические имена файлов должны быть объявлены в разделе domains при помощи ключевого слова file, например:

file=inp_file1; inp_file2; out_file.

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

Для выдачи информации на текущее устройство вывода используются стандартные предикаты ТП:

write (A1, A2,...);

writef ("формат ", A1,A2,...),

здесь А1,А2,...-аргументы предикатов, которые могут принимать значения констант или переменных, а "формат" - строка, описывающая формат вывода. В строке формата могут быть использованы следующие параметры:

% d - число со знаком (для типов char и integer);

% u - число без знака (для типов char и integer);

% X - шестнадцатеричное число (тип string);

% x - шестнадцатеричное число (для типов char и integer);

% S - строка символов ( типы symbol и string);

% c - одиночный символ (типы char и integer);

% g - действительное число в минимальном формате (тип real);

% e - экспоненциальная форма действительного числа;

% f - действительное число с фиксированной точкой.

Кроме того, в предикатах вывода могут использоваться следующие управляющие символы:

\n - переход на новую строку;

\t - табуляция вывода;

\xxx - вывод символа с кодом ххх.

Для приема информации различного типа с текущего устройства ввода в ТП существует группа предикатов:

readchar (char),

readint (integer),

readln (string),

readreal (real),

которые выполняют ввод значений в переменные типов char, integer,string и real соответственно.

СТРУКТУРНАЯ СХЕМА ПРОГРАММЫ

Структурная схема программы представлена на рисунке А1 графической части проекта. Схема состоит из следующих элементов:

Создание и отображение пользовательского меню

Вызов процедуры разбиения строки и вывод содержимого на экран

Процедура разбиения строки по две приблизительно одинаковые по границе слова

Процедура вызова и отображения количества цифр в строке

Процедура подсчета в строке количества числовых символов

Процедура поиска максимального цифрового элемента в списке

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

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

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

Процедура вызова процедуры записи трех файлов в один

Процедура вывода на экран и записи трех файлов в один

Процедура поиска и вывода на экран двух минимальных строк текстового файла

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

ОПИСАНИЕ ПРЕДИКАТОВ

В подготовленной программе используются следующие предикаты:

min(L,Min)(string*,string):(i,o) - поиск минимального элемента посредством сравнения каждого последующего элемента с предыдущим списка L , и вставки его в переменную Min.

del_min(Min1,L,L1)(string,string*,string*):(i,i,o) – создание нового списка L1 из старого L без не записывая в него элемент Min1.

read_list1(L)(string*):(o)-предикат создания списка L методом построчного чтения из текстового файла(readln(df)).

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

read_write – предикат читающий 3 файла, выводящий их на экран, записывающий их в 4 файл и выводящий его на экран.

kratn(N,L,L1)(integer,integer*,integer*):(i,i,o) – предикат ищущий в списке L числа кратные N и записывающий их в новый список L1.

max(L,Max)(integer*,integer):(i,o)- поиск максимального элемента посредством сравнения каждого последующего элемента с предыдущим списка L , и вставки его в переменную Max.

read_list(L)(integer*):(o)-предикат создания списка L методом построчного чтения того что ввел пользователь с клавиатуры.

del_max(Max1,L,L1)(integer,integer*,integer*):(i,i,o) – создание нового списка L1 из старого L без не записывая в него элемент Max1.

razbivka(S,S1,S2)(string,string,string):(i,o,o)- деление строки S на две приблизительно равные S1 и S2 по границе слова.

proverka(Str,N)(string,N):(i,o)-предикат исчет в строке Str каждый последующий цифровой элемент, и при получении оного прибавляет N+1.

сreatemenu – создает форму меню.

menu – заполняет меню содержимым и принимает выбор пункта пользователя с клавиатуры.

selects(Number)(integer):(i)-предикат выбора исполнения процедуры.

ТЕКСТ ПРОГРАММЫ

domains

i=integer

s=string

il=integer*

sl=string*

file=tf;df

predicates

min(sl,s)

del_min(s,sl,sl)

read_list1(sl)

read_write1

read_write

kratn(i,il,il)

max(il,i)

read_list(il)

del_max(i,il,il)

razbivka(s,s,s)

proverka(s, i)

createmenu

selects(i)

goal

createmenu.

clauses

%процедура создания окна и вызова меню

createmenu:-

makewindow(1,2,7,"Proga",0,0,25,80),

clearwindow,

menu.

%вывод содержимого меню и выбор действия

menu:-

cursor(2,0),

write(" 1 - Razbienie stroki po granice slova."),nl,

write(" 2 - Podschet kolichestva cifr v stroke."),nl,

write(" 3 - Dva naibolshih elementa v spiske."),nl,