[Prolog] Предикат, находящий длину гипотенузы прямоугольного треугольника по длинам катетов.

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

Как пишут предикаты поясню на примере: p1(a,b) :- a=b. Здесь возможны варианты 1) a неопределенно, b - определено, тогда a примет значение b, предикат p1 примет значение истина. 2) a и b определены, тогда результатом p1 будет сравнение a и b. 3) a определено, b - неопределено или a и b неопределены, тогда будет fail и откат.

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

>А как реально можно написать функцию нахождения квадратного корня?

sqrt(X).

Нужно каким-то образом из астрала узнать, что в прологе есть встроенная функция нахождения квадратного корня?

Этот астрал называется manual.

http://www.swi-prolog.org/man/arith.html

>Например, корректна ли такая запись вычисления куба: cube:-(X, X*X*X).

cube(Y,X) :- Y is X * X * X

Я писал на только TurboProlog, там формы is не было, там я бы написал просто:

cube(X,Y) :- X*X*X = Y.

Хочу заметить, что если вызвать cube(x1, x2) и обе переменных будут определены, то предикат просто вернет истину=)

если разумеется x2 будет равно x1*x1*x1

А почему не

cube(X,Y) :- Y is X*X*X.

?

Есть какие-то причины размещать ответ в первой позиции?

> Как пишут предикаты поясню на примере: p1(a,b) :- a=b. Здесь возможны варианты 1) a неопределенно, b - определено, тогда a примет значение b, предикат p1 примет значение истина. 2) a и b определены, тогда результатом p1 будет сравнение a и b. 3) a определено, b - неопределено или a и b неопределены, тогда будет fail и откат.

Вот спасибо, стало чуть понятнее.

>Есть какие-то причины размещать ответ в первой позиции?

На этот вопрос я отвечу за деньги. :)

> Я писал на только TurboProlog, там формы is не было, там я бы написал просто:

cube(X,Y) :- X*X*X = Y.

Фигасе, как это работает??? Операция присваивания всегда присваивает левой части значение правой. Что означает «X*X*X = Y» ?

>> Есть какие-то причины размещать ответ в первой позиции?

На этот вопрос я отвечу за деньги. :)

Вон из треда! :))

>если разумеется x2 будет равно x1*x1*x1

Ну это, собственно, понятно.

Я писал на только TurboProlog, там формы is не было

Эта форма уже прописана в стандарте ISO Prolog, ЕМНИП.

>А как реально можно написать функцию нахождения квадратного корня?

sqrt(X).

При всём уважении, я считаю что на начальных этапах изучения Пролога так делать не нужно. Нужно наоборот повелосипедить, прочувствовать, так сказать, как на этом языке записываются привычные выражения. Поэтому, тов. xintrea, от нашего стола - вашему:

%% Sqrt, Newton method

absolute(X, Result) :-
	X >= 0, Result is X.
absolute(X, Result) :-
	X < 0, Result is -X.

squared(X, Result) :-
	Result is X * X.

good_enough(X, Guess) :-
	squared(Guess, Y),
	absolute(Y - X, Abs),
 	Abs < 0.001.

average(A, B, Result) :-
	Result is (A + B) / 2.

improve(X, Guess, Result) :-
 	average(Guess, (X / Guess), Result).

newton_sqrt(X, Guess, Result) :-
	good_enough(X, Guess), Result is Guess,!.
newton_sqrt(X, Guess, Result) :-
	improve(X, Guess, Improved),
	newton_sqrt(X, Improved, Result).

%% Hypotenuse
hypotenuse(A, B, C) :-
	squared(A, As),
	squared(B, Bs),
	newton_sqrt(As + Bs, 1, C).

Для нахождения квадратного корня тут использован численный метод Ньютона (см. SICP, к примеру).
На здоровье :)

?- newton_sqrt(4,1,X).
X = 2.0.

?- newton_sqrt(9,1,X). 
X = 3.00009.

?- hypotenuse(3, 4, X).
X = 5.00002.

Ну я могу ошибаться, давно все таки писал, но вроде бы такая форма корректна. Знак «=» это не присваивание, это спец. оператор со спец. семантикой и семантика его зависит от аргументов, т.е. если оба аргумента определены, то сравнивает, если хотя бы один определен, то перебрасывает значение, иначе откат, как-то так.

Да, так я денег не заработаю. :)

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

Но что-то ТС много вопросов простых задает, когда ответ на них лежит в секунде от него. Возьми в swipl и попробуй поменять X и Y местами. Нет, надо спросить. Хотел вот деньжат по-легкому срубить. :)

По вашему примеру есть вопросы.

1. Я правильно понимаю, что good_enough(X, Guess) возвращает булево значение?

2. Что возвращает предложение

improve(X, Guess, Result) :- 
    average(Guess, (X / Guess), Result).

?

Я подозреваю, что среднее арифметическое между Guess и (X / Guess). Но как Result возвращается? Ведь конструкция вида «Variable=» или «Variable is» не используется.

> Но что-то ТС много вопросов простых задает

Потому что про пролог я два часа назад читать стал.

И до сих пор не нашел внятного и достаточно описания синтаксиса на русском.

Упс :)

1. Я правильно понимаю, что good_enough(X, Guess) возвращает булево значение?

Пролог - язык логического программирования, и тут всё возвращает булевые значения. Либо тру, либо фолс. Передача всего остального идёт через переменные, как например тут:

squared(X, Result) :- Result is X * X. 

Емнип, запись может отличаться в разных диалектах.

Что возвращает предложение

improve(X, Guess, Result) :-  
    average(Guess, (X / Guess), Result).

Булевое значение. Если вы обратитесь к improve с явными аргументами, например improve(1, 2, 3), то получите false, ибо 3 не есть результат усреднения чисел 2 и 0.5. Но используется improve именно для получения среднего арифметического между Guess и (X / Guess), передача этого значения осуществляется через переменную Result. Это такая фишка Пролога - можно использовать «функции» как для тестирования утверждений, так и для вычислений, смотря как вызывать.

>И до сих пор не нашел внятного и достаточно описания синтаксиса на русском.

Так Братко же. По сути, «K&R» для Пролога.

Начинание хорошее. Только первым делом выброси свой интуит.ру и найди нормальную книжку. Нормальными являются клоксин/меллиш, стерлинг/шапиро (вот уж точно где «к&р от пролога») и уже упомянутый братко. Есть еще, но это основные и они есть на русском.

Через те же два часа погружения отпадут все вопросы по поводу синтаксиса, порядка агрументов, «спец. оператора со спец. семантикой» (man унификация) и «возвращаемых значений».

>всё возвращает булевые значения

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

Булевое значение.

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

Это такая фишка Пролога - можно использовать «функции» как для тестирования утверждений, так и для вычислений, смотря как вызывать.

И такая интерпретация только усложняет дело и отдаляет понимание сути. Нет никаких «вычислений» и «тестирований», зачем все искусственно усложнять? Есть два алгоритма: унификации и поиска в глубину с откатом, и два типа данных: «логическая переменная» и структуры (ну ладно, есть еще числа и атомы (структуры нулевой арности)). Всё. На этом и построен весь пролог. Если выбросить на время из головы всю эту дребедень про привычные «функции», «возвращаемые значения» и прочее, то окажется, что пролог на самом деле один из самых простых языков.

Пользуясь случаем, поинтересуюсь, есть ли тут люди, пишущие на Mercury ? Есть ли смысл его изучать/использовать ?

>А как реально можно написать функцию нахождения квадратного корня?

Дихотомия по ответу?

вот всегда удивляло, что в реальных программах на прологе, собственно на прологе написано очень мало :), здесь так только наверное abs() реализована...

когда то говорили, что на любом языке можно писать как на фортране... после чтения sicp наверное надо говорить что на любом языке (на некоторых легче :) можно писать как на лиспе :)

Вообще, признаюсь, да, я тупо перевел пример со Схемы на Пролог.

А как бы выглядел метод Ньютона в Ъ-прологовом стиле? Было бы очень интересно посмотреть :)

Я не смогу пока :( В том же SICP 4.4 дольше рассказано про замечательные грабли пролога

1) просто зацикливание

2) наборы взаимосвязанных правил - зацикливание

3) порядок правил - зацикливание или просто отсутствие вывода

Любой учебный пример при малейшем сотрясении норовит стать нерабочим примером :)