Списки и рекурсия - История изменений

Victor Yukhtenko: /* Разбор с использованием списков */

2008-01-17T12:10:34Z

Разбор с использованием списков

SergeMukhin: очепятки

2007-11-23T11:03:33Z

очепятки

← Предыдущая		Версия 13:03, 23 ноября 2007
Строка 254:		Строка 254:
	Итак, теперь задача - найти длину списка [3], которая есть 1, и мы добавляем 1 к этому значению, чтобы получить длину списка [2, 3], что будет 2. Ну и хорошо!.		Итак, теперь задача - найти длину списка [3], которая есть 1, и мы добавляем 1 к этому значению, чтобы получить длину списка [2, 3], что будет 2. Ну и хорошо!.

	Аналогично, length_of вызывает себя рекурсивно опять для получения длины списка [3]. Хвост [3] есть [], поэтому T ~~связвается~~ с [], и задача теперь - получение длины списка [] и добавление к ней 1, что дает длину списка [3].		Аналогично, length_of вызывает себя рекурсивно опять для получения длины списка [3]. Хвост [3] есть [], поэтому T связывается с [], и задача теперь - получение длины списка [] и добавление к ней 1, что дает длину списка [3].

	Теперь все просто. Цель:		Теперь все просто. Цель:

SergeMukhin: очепятки

2007-11-23T11:01:40Z

очепятки

← Предыдущая		Версия 13:01, 23 ноября 2007
Строка 805:		Строка 805:
	В этом руководстве раскрыта следующие важные моменты:		В этом руководстве раскрыта следующие важные моменты:

	''Списки'' могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки ('''''') в конце ранее ~~определенного~~ домена.		''Списки'' могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки ('''''') в конце ранее определённого домена.
	*Список является рекурсивным составным объектом, состоящим из головы и хвоста. Голова есть первый элемент, а хвост - остальная часть списка (без первого элемента). Хвост списка - всегда список; голова списка - всегда элемента. Список может содержать ноль или более элементов; Пустой список обозначается [].		*Список является рекурсивным составным объектом, состоящим из головы и хвоста. Голова есть первый элемент, а хвост - остальная часть списка (без первого элемента). Хвост списка - всегда список; голова списка - всегда элемента. Список может содержать ноль или более элементов; Пустой список обозначается [].
	*Элементами списка ~~можже~~ быть что угодно, включая ~~другиме~~ списки; все элементы списка должны принадлежать одному домену. В этом случае объявление домена элементов должно выглядеть так:		*Элементами списка может быть что угодно, включая другие списки; все элементы списка должны принадлежать одному домену. В этом случае объявление домена элементов должно выглядеть так:

	<vip>domains		<vip>domains
Строка 834:		Строка 834:
	<vip>Result = [ Argument \|\| myPredicate(Argument) ]</vip>		<vip>Result = [ Argument \|\| myPredicate(Argument) ]</vip>
	*Поскольку Visual Prolog требует, чтобы все элементы списка принадлежали бы одному и тому же домену, следует использовать функторы для создания списков, хранящих элементы различного типа.		*Поскольку Visual Prolog требует, чтобы все элементы списка принадлежали бы одному и тому же домену, следует использовать функторы для создания списков, хранящих элементы различного типа.
	*процесс ''разбора с использованием разностных списков (parsing by difference lists)'' работает путем сокращения задачи; пример в этом руководстве ~~преобрахует~~ строку входных данных в структуру, которая может обрабатываться позже.		*процесс ''разбора с использованием разностных списков (parsing by difference lists)'' работает путем сокращения задачи; пример в этом руководстве преобразует строку входных данных в структуру, которая может обрабатываться позже.

	==References==		==References==

SergeMukhin: очепятки

2007-11-23T10:59:53Z

очепятки

← Предыдущая		Версия 12:59, 23 ноября 2007
Строка 519:		Строка 519:
	==Все Решения Сразу==		==Все Решения Сразу==

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

	Однако есть одна вещь, которую, в отличие от рекурсии, могут делать откаты, а именно – искать все ~~альтернитивные~~ решения посредством одного вызова. Поэтому Вы можете оказаться в ~~затрудинтельном~~ положении: Вам нужно получить все решения за один вызов, и, при этом, они Вам нужны все сразу, как часть единой интегрированной структуры данных. Что делать?		Однако есть одна вещь, которую, в отличие от рекурсии, могут делать откаты, а именно – искать все альтернативные решения посредством одного вызова. Поэтому Вы можете оказаться в затруднительном положении: Вам нужно получить все решения за один вызов, и, при этом, они Вам нужны все сразу, как часть единой интегрированной структуры данных. Что делать?

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

	*Первый аргумент, VarName, определяет аргумент в вызываемом целевом предикате, значения которого будут собираться в список.		*Первый аргумент, VarName, определяет аргумент в вызываемом целевом предикате, значения которого будут собираться в список.
Строка 561:		Строка 561:
	stdio::write("Average=", Ave, ". ").</vip>		stdio::write("Average=", Ave, ". ").</vip>

	Клауз обработки списка в этой программе создает список L, который является списком всех возрастов, полученных от предиката person. ~~Еслы~~ бы потребовалось бы собрать список всех людей в возрасте 42 лет, можно было бы задать следующий цель-вызов:		Клауз обработки списка в этой программе создает список L, который является списком всех возрастов, полученных от предиката person. Если бы потребовалось бы собрать список всех людей в возрасте 42 лет, можно было бы задать следующий цель-вызов:

	<vip>List = [ Who \|\| my::person(Who, _, 42) ]</vip>		<vip>List = [ Who \|\| my::person(Who, _, 42) ]</vip>

SergeMukhin: очепятки

2007-11-23T10:57:49Z

очепятки

← Предыдущая		Версия 12:57, 23 ноября 2007
Строка 444:		Строка 444:
	isMember(Name, Tail).</vip>		isMember(Name, Tail).</vip>

	===Добавление списка к другому списку: декларативное и ~~рекурсоивное~~ решения===		===Добавление списка к другому списку: декларативное и рекурсивное решения===

	Рассмотренный предикат member программы e01.pro работает в двух направлениях. Вернемся к его клаузам:		Рассмотренный предикат member программы e01.pro работает в двух направлениях. Вернемся к его клаузам:
Строка 459:		Строка 459:
	**Name (Имя) принадлежит списку, если голова списка есть Name		**Name (Имя) принадлежит списку, если голова списка есть Name
	**иначе Name принадлежит списку, если оно (Имя) принадлежит хвосту.		**иначе Name принадлежит списку, если оно (Имя) принадлежит хвосту.
	*С процедурной точки зрения, эти же два клауза могут быть ~~интерепретированы~~ так:<br/>Чтобы найти элемент списка		*С процедурной точки зрения, эти же два клауза могут быть интерпретированы так:<br/>Чтобы найти элемент списка
	**Найдите его голову		**Найдите его голову
	**иначе найдите элемент хвоста списка.		**иначе найдите элемент хвоста списка.
Строка 482:		Строка 482:
	<vip>append([], List2, List2).</vip>		<vip>append([], List2, List2).</vip>

	Если список List1 не пустой, то можно преобразовать списки List1 и List2 к форме списка ''List3'', сделав голову списка List1 головой списка List3. В приведенном коде переменная H используется в качестве головы как списка List1, так и списка List3. ~~Хвось~~ списка List3 есть список L3, который составлен из остатка списка List1 (а именно, L1) и всего списка List2. Опять выразим это на Прологе:		Если список List1 не пустой, то можно преобразовать списки List1 и List2 к форме списка ''List3'', сделав голову списка List1 головой списка List3. В приведенном коде переменная H используется в качестве головы как списка List1, так и списка List3. хвост списка List3 есть список L3, который составлен из остатка списка List1 (а именно, L1) и всего списка List2. Опять выразим это на Прологе:

	<vip>append([H\|L1], List2, [H\|L3]) :-		<vip>append([H\|L1], List2, [H\|L3]) :-
	append(L1, List2, L3).</vip>		append(L1, List2, L3).</vip>

	Предикат append работает следующим образом: пока список List1 не пустой, рекурсивное правило дописывает один элемент каждый раз к списку List3. Когда список List1 становится пустым, первый клауз clause обеспечивает ~~дописыванеие~~ списка List2 в конец списка List3.		Предикат append работает следующим образом: пока список List1 не пустой, рекурсивное правило дописывает один элемент каждый раз к списку List3. Когда список List1 становится пустым, первый клауз clause обеспечивает дописывание списка List2 в конец списка List3.

	====Варианты использования одного предиката====		====Варианты использования одного предиката====
Строка 515:		Строка 515:
	Статус аргументов данного вызова предиката известен как ''поток (или шаблон) ввода-вывода''. Аргумент, который связан или наследуется в момент вызова является входным аргументом и обозначается как (i). Свободный аргумент является выходным аргументом и обозначается как (o).		Статус аргументов данного вызова предиката известен как ''поток (или шаблон) ввода-вывода''. Аргумент, который связан или наследуется в момент вызова является входным аргументом и обозначается как (i). Свободный аргумент является выходным аргументом и обозначается как (o).

	Предикат append обладает свойством поддерживать любой шаблон ввода-вывода, какой требуется. Однако не все предикаты имеют возможность вызова с различными шаблонами ввода-вывода. Когда клауз Пролога способен поддерживать множество шаблонов ввода-вывода, он ~~назвается~~ инверсным клаузом. Целый набор предикатов для обработки списков содержится в классе '''list'''.		Предикат append обладает свойством поддерживать любой шаблон ввода-вывода, какой требуется. Однако не все предикаты имеют возможность вызова с различными шаблонами ввода-вывода. Когда клауз Пролога способен поддерживать множество шаблонов ввода-вывода, он называется инверсным клаузом. Целый набор предикатов для обработки списков содержится в классе '''list'''.

	==Все Решения Сразу==		==Все Решения Сразу==

SergeMukhin: очепятки

2007-11-23T10:56:09Z

очепятки

← Предыдущая		Версия 12:56, 23 ноября 2007
Строка 403:		Строка 403:
	/* "name" принадлежит списку "name" /</vip>		/* "name" принадлежит списку "name" /</vip>

	В программе e01.pro первый клауз исследует голову списка. Если голова списка совпадает с искомым именем, то можно сделать заключение, что Name принадлежит списку. Поскольку хвост списка нас не интересует , то это мы представляем анонимной переменной. Благодаря первому клаузу, цель		В программе e01.pro первый клауз исследует голову списка. Если голова списка совпадает с искомым именем, то можно сделать заключение, что Name принадлежит списку. Поскольку хвост списка нас не интересует, то это мы представляем анонимной переменной. Благодаря первому клаузу, цель

	<vip>my::isMember("john", ["john", "leonard", "eric", "frank"])</vip>		<vip>my::isMember("john", ["john", "leonard", "eric", "frank"])</vip>
Строка 434:		Строка 434:
	Если голова списка не есть Name, то надо исследовать, не содержится ли Name в хвосте списка.		Если голова списка не есть Name, то надо исследовать, не содержится ли Name в хвосте списка.

	На ~~обычнои~~ языке:		На обычном языке:

	Name принадлежит списку, если Name является первым элементом списка, или<br />		Name принадлежит списку, если Name является первым элементом списка, или<br />
	Name принадлежит ~~списк~~, если Name принадлежит хвосту.		Name принадлежит списку, если Name принадлежит хвосту.

	Второй клауз предиката isMember ~~отосится~~ к этому отношению. Таким образом на Visual Prolog:		Второй клауз предиката isMember относится к этому отношению. Таким образом на Visual Prolog:

	<vip>isMember(Name, [_\|Tail]) :-		<vip>isMember(Name, [_\|Tail]) :-

Victor Yukhtenko: /* Заключение */

2007-11-09T14:20:31Z

Заключение

← Предыдущая		Версия 16:20, 9 ноября 2007
Строка 803:		Строка 803:
	==Заключение==		==Заключение==

	~~Два важных момента раскрыты в~~ этом руководстве:		В этом руководстве раскрыта следующие важные моменты:

	''Списки'' могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки ('''''') в конце ранее определенного домена.		''Списки'' могут содержать произвольное число элементов; Вы объявляете их простым добавление звездочки ('''''') в конце ранее определенного домена.

Victor Yukhtenko: /* Разбор с использованием списков */

2007-11-09T14:17:07Z

Разбор с использованием списков

← Предыдущая		Версия 16:17, 9 ноября 2007
Строка 754:		Строка 754:
	</vip>		</vip>

	~~Load and run this program, then enter the following goal~~:		Загрузите программу и выполните целевой вызов:

	<vip>goal		<vip>goal
Строка 760:		Строка 760:
	my_p::s_program(Ans, Res).</vip>		my_p::s_program(Ans, Res).</vip>

	Visual Prolog ~~will return the program structure~~:		Visual Prolog вернет структуру программы:

	<vip>Ans = ["b","=","2",";","if","b","then","a","=","1",		<vip>Ans = ["b","=","2",";","if","b","then","a","=","1",

Victor Yukhtenko: /* Разбор с использованием списков */

2007-11-09T14:14:06Z

Разбор с использованием списков

← Предыдущая		Версия 16:14, 9 ноября 2007
Строка 632:		Строка 632:
	==Разбор с использованием списков==		==Разбор с использованием списков==

	Ниже приведена программа, демонстрирующая [[wikipedia:parsing\|разбор (parsing)]] с использованием списков. Процесс разбора работает в ~~направлении упрощения (~~сворачивания~~) задачи~~. В этом примере входная строка ~~преобрахуется~~ в структуру данных ~~пролога~~, которая может быть использована далее.		Ниже приведена программа, демонстрирующая [[wikipedia:parsing\|разбор]] (parsing)с использованием списков. Процесс разбора работает в методом сворачивания. В этом примере входная строка преобразуется в структуру данных Пролога, которая может быть использована далее.

	Этот разборщик предназначен для примитивного формального языка. Хотя этот пример достаточно сложен с точки зрения этого руководства, мы решили поместит его здесь, поскольку разбор является одной из областей, где Visual Prolog очень эффективен. Если Вы чувствуете себя не вполне готовым для этого раздела, Вы можете этот пример пропустить и продолжить чтение руководства без потери содержательности.		Этот разборщик предназначен для примитивного формального языка. Хотя этот пример достаточно сложен с точки зрения этого руководства, мы решили поместит его здесь, поскольку разбор является одной из областей, где Visual Prolog очень эффективен. Если Вы чувствуете себя не вполне готовым для этого раздела, Вы можете этот пример пропустить и продолжить чтение руководства без потери содержательности.

Victor Yukhtenko: /* Разбор с использованием списков */

2007-11-09T14:11:39Z

Разбор с использованием списков

← Предыдущая		Версия 16:11, 9 ноября 2007
Строка 630:		Строка 630:
	stdio::write("Второй списко: ", Ans2, "\n\n&quot).</vip>		stdio::write("Второй списко: ", Ans2, "\n\n&quot).</vip>

	===Разбор с использованием списков===		==Разбор с использованием списков==

	~~The program demonstrates~~ [[wikipedia:parsing\|parsing]] ~~by ''difference lists''~~. ~~The process of parsing by difference lists works by reducing the problem; in this example we transform a string of input into a Prolog structure that can be used or evaluated later~~.		Ниже приведена программа, демонстрирующая [[wikipedia:parsing\|разбор (parsing)]] с использованием списков. Процесс разбора работает в направлении упрощения (сворачивания) задачи. В этом примере входная строка преобрахуется в структуру данных пролога, которая может быть использована далее.

	~~The parser in this example is for a very primitive computer language~~. ~~Although this example is very advanced for this point in the tutorial~~, ~~we decided to put it here because parsing is one of the areas where~~ Visual Prolog ~~is very powerful~~. ~~If you do not feel ready for this topic~~, ~~you can skip this example and continue reading the tutorial without any loss of continuity~~.		Этот разборщик предназначен для примитивного формального языка. Хотя этот пример достаточно сложен с точки зрения этого руководства, мы решили поместит его здесь, поскольку разбор является одной из областей, где Visual Prolog очень эффективен. Если Вы чувствуете себя не вполне готовым для этого раздела, Вы можете этот пример пропустить и продолжить чтение руководства без потери содержательности.

	<vip>#include @"pfc\exception\exception.ph"		<vip>#include @"pfc\exception\exception.ph"
Строка 654:		Строка 654:
	end implement		end implement

	/* * * * * * * * * * * * * * * * * *		/* * * * * * * * * * * * * * * * * * * * *
	* ~~This second part of the program~~		* Вторая часть этой программы - разборщик *
	* ~~is the parser~~ *		* * * * * * * * * * * * * * * * * * * * * */
	* * * * * * * * * * * * * * * * * */
	class my_p		class my_p
	domains		domains
	program = program(statement*).		program = program(statement*).
	/* * * * * * * * * * * * * * * *		/* * * * * * * * * * * * * * * * * * * * * *
	* ~~Definition of what constitutes~~		* Определение что есть языковая конструкция *
	* ~~a statement~~ *		* (предложение языка) *
	* * * * * * * * * * * * * * * */		* * * * * * * * * * * * * * * * * * * * * * */
	statement =		statement =
	if_Then_Else(exp, statement, statement);		if_Then_Else(exp, statement, statement);
Строка 670:		Строка 669:
	while(exp, statement);		while(exp, statement);
	assign(id, exp).		assign(id, exp).
	/* * * * * * * * * * * ~~* ~~		/* * * * * * * * * * * *
	* ~~Definition of expression~~ *		* Определение выражения *
	* * * * * * * * * * * ~~* ~~ /		* * * * * * * * * * * */
	exp =		exp =
	plus(exp, exp);		plus(exp, exp);
Строка 789:		Строка 788:
	)		)
	])		])
	~~1 Solution~~</vip>		</vip>

	The transformation in this example is divided into two stages: scanning and parsing. The tokl predicate is the scanner; it accepts a string and converts it into a list of tokens. All the predicates with names beginning in s_ are parser predicates. In this example the input text is a Pascal-like program made up of Pascal-like statements. This programming language only understands certain statements: IF THEN ELSE, IF THEN, DO WHILE, and ASSIGNMENT. Statements are made up of expressions and other statements. Expressions are addition, subtraction, variables, and integers.

	~~Here's how this example works:~~

	*The first scanner clause, s_program, takes a list of tokens and tests if it can be transformed into a list of statements.

	*The predicate s_statement_list takes this same list of tokens and tests if the tokens can be divided up into individual statements, each ending with a semicolon.

	*The predicate s_statement tests if the first tokens of the token list make up a legal statement. If so, the statement is returned in a structure and the remaining tokens are returned back to s_statement_list.

	*The four clauses of the s_statement correspond to the four types of statements the parser understands. ~~If the first s_statement clause is unable to transform the list of tokens into an~~ IF THEN ELSE ~~statement~~, ~~the clause fails and backtracks to the next s_statement clause, which tries to transform the list of tokens into an~~ IF THEN ~~statement. If that clause fails~~, ~~the next one tries to transform the list of tokens into a~~ DO WHILE ~~statement~~.		Преобразование в этом примере представлено двумя шагами: сканирование и разбор. Предикат tokl - это сканер. Он принимает строку и преобразует ее в список токенов. Все предикаты с именами, начинающимися с s_ являются предикатами парсера. В этом примере входный текст представляет программу на языке, подобном языку Паскаль, и состоящей из Паскале-подобных предложений. Этот язык программирования позволяет только предложения вида: IF THEN ELSE, IF THEN, DO WHILE и присваивание (ASSIGNMENT). Предложения состоят из выражений и вложенных предложений. Выражения - сложение, вычитание, переменные и целые.

	*If the first three s_statement clauses fail, the last clause for that predicate tests if the statement does assignment. This clause tests for assignment by testing if the first term is a symbol, the second term is "=", and the next terms make up a simple math expression.		Далее, как это работает:

	*~~The~~ s_exp, s_exp1, ~~and s_exp2 predicates work the same way~~, ~~by testing if the first terms are expressions and – if so – returning the remainder of the terms and an expression structure back to~~ s_statement.		*Первый клауз парсера, s_program, принимает список токенов и пытается преобразовать его в список предложений.
			*Предикат s_statement_list принимает тот же самый список токенов и проверяет возможность деления токенов на предложения, завершающиеся точкой с запятой.
			*Предикат s_statement проверяет могут ли начальные токены списка (токенов) представлять собой правильное предложение. Если да, то такое предложение возвращается в виде структуры, а остаток токенов передается рекурсивно вызываемому предикату s_statement_list.
			*Четыре клауза предиката s_statement соответствуют четырем типам, которые парсер понимает.<br\> Если первый клауз предиката s_statement не может преобразовать список токенов в предложение вида IF THEN ELSE, то клауз завершается неуспешно и в порядке отката переходит к следующему клаузу предиката s_statement. Теперь делается попытка преобразовать список токенов в конструкцию вида IF THEN. Если эта попытка неуспешна, то в следующем клаузе делается попытка преобразования к предложению вида DO WHILE.
			*Если первые три клауза предиката s_statement завершаются неуспешно, то последний клауз этого предиката провереяет представлена ли в списке токенов операция присваивания. Этот клауз проверяет "на присваивание" является ли первый терм символом, второй - знаком равно ("="), а следующие термы представляют простое математическое выражение.
			*Предикаты s_exp, s_exp1 и s_exp2 работают аналогично, путем проверки являются ли начальные термы выражениями и, если это так, то предикату s_statement предикат s_exp возвращает остаток термов и математическое выражение в виде структуры.

	==Заключение==		==Заключение==