#prolog #number-crunching
#пролог #обработка чисел
Вопрос:
Я нашел этот код в Интернете для умножения матриц в Prolog, может ли кто-нибудь, у кого есть опыт в Prolog, объяснить мне это?
% SWI-Prolog has transpose/2 in its clpfd library
:- use_module(library(clpfd)).
% N is the dot product of lists V1 and V2.
dot(V1, V2, N) :-
maplist(product, V1, V2, P),
sumlist(P, N).
product(N1,N2, N3) :-
N3 is N1 * N2.
% Matrix multiplication with matrices represented
% as lists of lists. M3 is the product of M1 and M2
mmult(M1, M2, M3) :-
transpose(M2, MT),
maplist(mm_helper(MT), M1, M3).
mm_helper(M2, I1, M3) :-
maplist(dot(I1), M2, M3).
Ответ №1:
Строки, начинающиеся с %
, являются комментариями
Большинство языков программирования имеют методы и функции. В прологе есть предикаты, которые завершаются успешно или завершаются неудачно, и они могут передавать значения в переменных.
Предикаты обозначаются их именем и арностью как таковыми, transpose/2
.
Большинство языков программирования используют присваивание, но Пролог использует унификацию. Для частного случая решения математических выражений Prolog имеет значение /2
:- use_module(library(clpfd)).
Это директива :- которая вводит библиотеку с именем clpfd. clpfd обычно используется для ограничений, но в этом случае используется для доступа к transpose/2
предикату.
dot(V1, V2, N) :-
maplist(product,V1,V2,P),
sumlist(P,N).
dot/3
это предикат, который принимает два вектора, я предполагаю, что в данном случае реализован как список Prolog, и связывает скалярное произведение как N
.
maplist/4 применяет предикат product /3 к значениям в V1
и V2
для создания списка P
.
sumlist/2 суммирует список значений в P
и связывает N
.
product(N1,N2,N3) :- N3 is N1*N2.
product/3
является вспомогательным предикатом для взятия двух чисел N1
N2
и их умножения.
N3 is N1*N2
можно рассматривать как N3 = (N1 * N2)
mmult(M1, M2, M3) :-
transpose(M2,MT),
maplist(mm_helper(MT), M1, M3).
transpose/2 — это типичное перемещение массива.
maplist/3
применяет вспомогательный предикат mm_helper/3
с использованием MT
и M1
для привязки M3
.
mm_helper(M2, I1, M3) :-
maplist(dot(I1), M2, M3).
maplist/3
применяется dot/3
к I1
и M2
к привязке M3
.
Я так понимаю, вы взяли код из RosettaCode или он пересекался с таким.
Пример запуска:
?- mmult([[1,2],[3,4]],[[5,6],[7,8]],R).
R = [[19, 22], [43, 50]] ;
true.
Проверка примера.
Из комментария.
Что представляет I1 в предикате mm_helper?
Подробности см. в трассировке ниже
Сигнатура mm_helper/3
— это mm_helper(M2, I1, M3)
то, что содержит второй параметр I1
. Из строк в трассировке
Exit: (11) mm_helper([[5, 7], [6, 8]], [3, 4], [43, 50])
вторым параметром является [3,4]
.
Call: (10) mm_helper([[5, 7], [6, 8]], [1, 2], _3596)
вторым параметром является [1,2]
.
То I2
же самое относится и к фрагменту строки первой матрицы.
Будьте осторожны с тем, что вы просите, вы можете получить больше, чем ожидалось? 🙂
Полная трассировка выполнения:
Это только здесь из-за вопроса в комментарии.
[trace] ?- mmult([[1,2],[3,4]],[[5,6],[7,8]],R).
Call: (8) mmult([[1, 2], [3, 4]], [[5, 6], [7, 8]], _3238)
Unify: (8) mmult([[1, 2], [3, 4]], [[5, 6], [7, 8]], _3238)
Call: (9) clpfd:transpose([[5, 6], [7, 8]], _3536)
Unify: (9) clpfd:transpose([[5, 6], [7, 8]], _3536)
Call: (10) error:must_be(list(list), [[5, 6], [7, 8]])
Unify: (10) error:must_be(list(list), [[5, 6], [7, 8]])
Exit: (10) error:must_be(list(list), [[5, 6], [7, 8]])
Call: (10) clpfd:lists_transpose([[5, 6], [7, 8]], _3540)
Unify: (10) clpfd:lists_transpose([[5, 6], [7, 8]], _3540)
Call: (11) clpfd:'__aux_maplist/2_same_length 1'([[7, 8]], [5, 6])
Unify: (11) clpfd:'__aux_maplist/2_same_length 1'([[7, 8]], [5, 6])
Call: (12) lists:same_length([5, 6], [7, 8])
Unify: (12) lists:same_length([5, 6], [7, 8])
Exit: (12) lists:same_length([5, 6], [7, 8])
Call: (12) clpfd:'__aux_maplist/2_same_length 1'([], [5, 6])
Unify: (12) clpfd:'__aux_maplist/2_same_length 1'([], [5, 6])
Exit: (12) clpfd:'__aux_maplist/2_same_length 1'([], [5, 6])
Exit: (11) clpfd:'__aux_maplist/2_same_length 1'([[7, 8]], [5, 6])
^ Call: (11) apply:foldl(transpose_, [5, 6], _3548, [[5, 6], [7, 8]], _3552)
^ Unify: (11) apply:foldl(clpfd:transpose_, [5, 6], _3554, [[5, 6], [7, 8]], _3558)
Call: (12) apply:foldl_([5, 6], _3552, clpfd:transpose_, [[5, 6], [7, 8]], _3558)
Unify: (12) apply:foldl_([5, 6], [_3536|_3538], clpfd:transpose_, [[5, 6], [7, 8]], _3564)
Call: (13) clpfd:transpose_(5, _3536, [[5, 6], [7, 8]], _3562)
Unify: (13) clpfd:transpose_(5, _3536, [[5, 6], [7, 8]], _3562)
Call: (14) clpfd:'__aux_maplist/4_list_first_rest 0'([[5, 6], [7, 8]], _3536, _3560)
Unify: (14) clpfd:'__aux_maplist/4_list_first_rest 0'([[5, 6], [7, 8]], [_3542|_3544], [_3548|_3550])
Call: (15) clpfd:list_first_rest([5, 6], _3542, _3548)
Unify: (15) clpfd:list_first_rest([5, 6], 5, [6])
Exit: (15) clpfd:list_first_rest([5, 6], 5, [6])
Call: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[7, 8]], _3544, _3550)
Unify: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[7, 8]], [_3554|_3556], [_3560|_3562])
Call: (16) clpfd:list_first_rest([7, 8], _3554, _3560)
Unify: (16) clpfd:list_first_rest([7, 8], 7, [8])
Exit: (16) clpfd:list_first_rest([7, 8], 7, [8])
Call: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([], _3556, _3562)
Unify: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([], [], [])
Exit: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([], [], [])
Exit: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[7, 8]], [7], [[8]])
Exit: (14) clpfd:'__aux_maplist/4_list_first_rest 0'([[5, 6], [7, 8]], [5, 7], [[6], [8]])
Exit: (13) clpfd:transpose_(5, [5, 7], [[5, 6], [7, 8]], [[6], [8]])
Call: (13) apply:foldl_([6], _3538, clpfd:transpose_, [[6], [8]], _3588)
Unify: (13) apply:foldl_([6], [_3566|_3568], clpfd:transpose_, [[6], [8]], _3594)
Call: (14) clpfd:transpose_(6, _3566, [[6], [8]], _3592)
Unify: (14) clpfd:transpose_(6, _3566, [[6], [8]], _3592)
Call: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[6], [8]], _3566, _3590)
Unify: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[6], [8]], [_3572|_3574], [_3578|_3580])
Call: (16) clpfd:list_first_rest([6], _3572, _3578)
Unify: (16) clpfd:list_first_rest([6], 6, [])
Exit: (16) clpfd:list_first_rest([6], 6, [])
Call: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([[8]], _3574, _3580)
Unify: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([[8]], [_3584|_3586], [_3590|_3592])
Call: (17) clpfd:list_first_rest([8], _3584, _3590)
Unify: (17) clpfd:list_first_rest([8], 8, [])
Exit: (17) clpfd:list_first_rest([8], 8, [])
Call: (17) clpfd:'__aux_maplist/4_list_first_rest 0'([], _3586, _3592)
Unify: (17) clpfd:'__aux_maplist/4_list_first_rest 0'([], [], [])
Exit: (17) clpfd:'__aux_maplist/4_list_first_rest 0'([], [], [])
Exit: (16) clpfd:'__aux_maplist/4_list_first_rest 0'([[8]], [8], [[]])
Exit: (15) clpfd:'__aux_maplist/4_list_first_rest 0'([[6], [8]], [6, 8], [[], []])
Exit: (14) clpfd:transpose_(6, [6, 8], [[6], [8]], [[], []])
Call: (14) apply:foldl_([], _3568, clpfd:transpose_, [[], []], _3618)
Unify: (14) apply:foldl_([], [], clpfd:transpose_, [[], []], [[], []])
Exit: (14) apply:foldl_([], [], clpfd:transpose_, [[], []], [[], []])
Exit: (13) apply:foldl_([6], [[6, 8]], clpfd:transpose_, [[6], [8]], [[], []])
Exit: (12) apply:foldl_([5, 6], [[5, 7], [6, 8]], clpfd:transpose_, [[5, 6], [7, 8]], [[], []])
^ Exit: (11) apply:foldl(clpfd:transpose_, [5, 6], [[5, 7], [6, 8]], [[5, 6], [7, 8]], [[], []])
Exit: (10) clpfd:lists_transpose([[5, 6], [7, 8]], [[5, 7], [6, 8]])
Exit: (9) clpfd:transpose([[5, 6], [7, 8]], [[5, 7], [6, 8]])
Call: (9) '__aux_maplist/3_mm_helper 1'([[1, 2], [3, 4]], _3238, [[5, 7], [6, 8]])
Unify: (9) '__aux_maplist/3_mm_helper 1'([[1, 2], [3, 4]], [_3596|_3598], [[5, 7], [6, 8]])
Call: (10) mm_helper([[5, 7], [6, 8]], [1, 2], _3596)
Unify: (10) mm_helper([[5, 7], [6, 8]], [1, 2], _3596)
Call: (11) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], _3596, [1, 2])
Unify: (11) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], [_3602|_3604], [1, 2])
Call: (12) dot([1, 2], [5, 7], _3602)
Unify: (12) dot([1, 2], [5, 7], _3602)
Call: (13) '__aux_maplist/4_product 0'([1, 2], [5, 7], _3626)
Unify: (13) '__aux_maplist/4_product 0'([1, 2], [5, 7], [_3608|_3610])
Call: (14) product(1, 5, _3608)
Unify: (14) product(1, 5, _3608)
Call: (15) _3608 is 1*5
Exit: (15) 5 is 1*5
Exit: (14) product(1, 5, 5)
Call: (14) '__aux_maplist/4_product 0'([2], [7], _3610)
Unify: (14) '__aux_maplist/4_product 0'([2], [7], [_3620|_3622])
Call: (15) product(2, 7, _3620)
Unify: (15) product(2, 7, _3620)
Call: (16) _3620 is 2*7
Exit: (16) 14 is 2*7
Exit: (15) product(2, 7, 14)
Call: (15) '__aux_maplist/4_product 0'([], [], _3622)
Unify: (15) '__aux_maplist/4_product 0'([], [], [])
Exit: (15) '__aux_maplist/4_product 0'([], [], [])
Exit: (14) '__aux_maplist/4_product 0'([2], [7], [14])
Exit: (13) '__aux_maplist/4_product 0'([1, 2], [5, 7], [5, 14])
Call: (13) backward_compatibility:sumlist([5, 14], _3602)
Unify: (13) backward_compatibility:sumlist([5, 14], _3602)
Call: (14) lists:sum_list([5, 14], _3602)
Unify: (14) lists:sum_list([5, 14], _3602)
Exit: (14) lists:sum_list([5, 14], 19)
Exit: (13) backward_compatibility:sumlist([5, 14], 19)
Exit: (12) dot([1, 2], [5, 7], 19)
Call: (12) '__aux_maplist/3_dot 1'([[6, 8]], _3604, [1, 2])
Unify: (12) '__aux_maplist/3_dot 1'([[6, 8]], [_3644|_3646], [1, 2])
Call: (13) dot([1, 2], [6, 8], _3644)
Unify: (13) dot([1, 2], [6, 8], _3644)
Call: (14) '__aux_maplist/4_product 0'([1, 2], [6, 8], _3668)
Unify: (14) '__aux_maplist/4_product 0'([1, 2], [6, 8], [_3650|_3652])
Call: (15) product(1, 6, _3650)
Unify: (15) product(1, 6, _3650)
Call: (16) _3650 is 1*6
Exit: (16) 6 is 1*6
Exit: (15) product(1, 6, 6)
Call: (15) '__aux_maplist/4_product 0'([2], [8], _3652)
Unify: (15) '__aux_maplist/4_product 0'([2], [8], [_3662|_3664])
Call: (16) product(2, 8, _3662)
Unify: (16) product(2, 8, _3662)
Call: (17) _3662 is 2*8
Exit: (17) 16 is 2*8
Exit: (16) product(2, 8, 16)
Call: (16) '__aux_maplist/4_product 0'([], [], _3664)
Unify: (16) '__aux_maplist/4_product 0'([], [], [])
Exit: (16) '__aux_maplist/4_product 0'([], [], [])
Exit: (15) '__aux_maplist/4_product 0'([2], [8], [16])
Exit: (14) '__aux_maplist/4_product 0'([1, 2], [6, 8], [6, 16])
Call: (14) backward_compatibility:sumlist([6, 16], _3644)
Unify: (14) backward_compatibility:sumlist([6, 16], _3644)
Call: (15) lists:sum_list([6, 16], _3644)
Unify: (15) lists:sum_list([6, 16], _3644)
Exit: (15) lists:sum_list([6, 16], 22)
Exit: (14) backward_compatibility:sumlist([6, 16], 22)
Exit: (13) dot([1, 2], [6, 8], 22)
Call: (13) '__aux_maplist/3_dot 1'([], _3646, [1, 2])
Unify: (13) '__aux_maplist/3_dot 1'([], [], [1, 2])
Exit: (13) '__aux_maplist/3_dot 1'([], [], [1, 2])
Exit: (12) '__aux_maplist/3_dot 1'([[6, 8]], [22], [1, 2])
Exit: (11) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], [19, 22], [1, 2])
Exit: (10) mm_helper([[5, 7], [6, 8]], [1, 2], [19, 22])
Call: (10) '__aux_maplist/3_mm_helper 1'([[3, 4]], _3598, [[5, 7], [6, 8]])
Unify: (10) '__aux_maplist/3_mm_helper 1'([[3, 4]], [_3686|_3688], [[5, 7], [6, 8]])
Call: (11) mm_helper([[5, 7], [6, 8]], [3, 4], _3686)
Unify: (11) mm_helper([[5, 7], [6, 8]], [3, 4], _3686)
Call: (12) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], _3686, [3, 4])
Unify: (12) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], [_3692|_3694], [3, 4])
Call: (13) dot([3, 4], [5, 7], _3692)
Unify: (13) dot([3, 4], [5, 7], _3692)
Call: (14) '__aux_maplist/4_product 0'([3, 4], [5, 7], _3716)
Unify: (14) '__aux_maplist/4_product 0'([3, 4], [5, 7], [_3698|_3700])
Call: (15) product(3, 5, _3698)
Unify: (15) product(3, 5, _3698)
Call: (16) _3698 is 3*5
Exit: (16) 15 is 3*5
Exit: (15) product(3, 5, 15)
Call: (15) '__aux_maplist/4_product 0'([4], [7], _3700)
Unify: (15) '__aux_maplist/4_product 0'([4], [7], [_3710|_3712])
Call: (16) product(4, 7, _3710)
Unify: (16) product(4, 7, _3710)
Call: (17) _3710 is 4*7
Exit: (17) 28 is 4*7
Exit: (16) product(4, 7, 28)
Call: (16) '__aux_maplist/4_product 0'([], [], _3712)
Unify: (16) '__aux_maplist/4_product 0'([], [], [])
Exit: (16) '__aux_maplist/4_product 0'([], [], [])
Exit: (15) '__aux_maplist/4_product 0'([4], [7], [28])
Exit: (14) '__aux_maplist/4_product 0'([3, 4], [5, 7], [15, 28])
Call: (14) backward_compatibility:sumlist([15, 28], _3692)
Unify: (14) backward_compatibility:sumlist([15, 28], _3692)
Call: (15) lists:sum_list([15, 28], _3692)
Unify: (15) lists:sum_list([15, 28], _3692)
Exit: (15) lists:sum_list([15, 28], 43)
Exit: (14) backward_compatibility:sumlist([15, 28], 43)
Exit: (13) dot([3, 4], [5, 7], 43)
Call: (13) '__aux_maplist/3_dot 1'([[6, 8]], _3694, [3, 4])
Unify: (13) '__aux_maplist/3_dot 1'([[6, 8]], [_3734|_3736], [3, 4])
Call: (14) dot([3, 4], [6, 8], _3734)
Unify: (14) dot([3, 4], [6, 8], _3734)
Call: (15) '__aux_maplist/4_product 0'([3, 4], [6, 8], _3758)
Unify: (15) '__aux_maplist/4_product 0'([3, 4], [6, 8], [_3740|_3742])
Call: (16) product(3, 6, _3740)
Unify: (16) product(3, 6, _3740)
Call: (17) _3740 is 3*6
Exit: (17) 18 is 3*6
Exit: (16) product(3, 6, 18)
Call: (16) '__aux_maplist/4_product 0'([4], [8], _3742)
Unify: (16) '__aux_maplist/4_product 0'([4], [8], [_3752|_3754])
Call: (17) product(4, 8, _3752)
Unify: (17) product(4, 8, _3752)
Call: (18) _3752 is 4*8
Exit: (18) 32 is 4*8
Exit: (17) product(4, 8, 32)
Call: (17) '__aux_maplist/4_product 0'([], [], _3754)
Unify: (17) '__aux_maplist/4_product 0'([], [], [])
Exit: (17) '__aux_maplist/4_product 0'([], [], [])
Exit: (16) '__aux_maplist/4_product 0'([4], [8], [32])
Exit: (15) '__aux_maplist/4_product 0'([3, 4], [6, 8], [18, 32])
Call: (15) backward_compatibility:sumlist([18, 32], _3734)
Unify: (15) backward_compatibility:sumlist([18, 32], _3734)
Call: (16) lists:sum_list([18, 32], _3734)
Unify: (16) lists:sum_list([18, 32], _3734)
Exit: (16) lists:sum_list([18, 32], 50)
Exit: (15) backward_compatibility:sumlist([18, 32], 50)
Exit: (14) dot([3, 4], [6, 8], 50)
Call: (14) '__aux_maplist/3_dot 1'([], _3736, [3, 4])
Unify: (14) '__aux_maplist/3_dot 1'([], [], [3, 4])
Exit: (14) '__aux_maplist/3_dot 1'([], [], [3, 4])
Exit: (13) '__aux_maplist/3_dot 1'([[6, 8]], [50], [3, 4])
Exit: (12) '__aux_maplist/3_dot 1'([[5, 7], [6, 8]], [43, 50], [3, 4])
Exit: (11) mm_helper([[5, 7], [6, 8]], [3, 4], [43, 50])
Call: (11) '__aux_maplist/3_mm_helper 1'([], _3688, [[5, 7], [6, 8]])
Unify: (11) '__aux_maplist/3_mm_helper 1'([], [], [[5, 7], [6, 8]])
Exit: (11) '__aux_maplist/3_mm_helper 1'([]
Комментарии:
1. Я думаю, что неверно говорить, что предикаты Prolog возвращают true или false . Они могут быть успешными или неудачными, но для true и false даже нет значений Prolog, вы не можете присвоить это возвращаемое значение переменной, и вы не можете поместить оценку предиката вместо значения true или false в вызове. Я знаю, что вы это знаете, я просто беспокоюсь, что эта формулировка может ввести в заблуждение.
2. @DanielLyons спасибо. Как всегда, не стесняйтесь редактировать мои вопросы или ответы. Это все creative commons.
3. Спасибо за объяснение, но выяснили ли вы, что представляет I1 в предикате mm_helper?
4. @Bettosama Смотрите Обновленный ответ. Теперь вы можете заглянуть и посмотреть, как он работает, используя вывод трассировки.
5. @Bettosama Если вы задаете какие-либо вопросы, связанные с выводом трассировки, вы должны опубликовать их как новый вопрос. StackOverflow не является дискуссионным сайтом.
Ответ №2:
Это выглядит ужасно! Но в этом есть смысл.
Очевидно, что % — это начало комментария (на всякий случай, если это непонятно)
: — определяет функцию
функция — это последовательность других функций, разделенных запятыми.
параметры передаются по ссылке (поэтому возвращаемых значений нет), в приведенном выше коде последний параметр — это место, где хранится результат каждой функции. Я бы предположил, что это какое-то соглашение в prolog, поскольку это также относится к библиотечным функциям.
maplist звучит так, как будто он применяет функцию к каждому элементу в переданном списке (т. Е. Сопоставляет список), Сохраняет значения в списке результатов (последний параметр). Вы можете погуглить эту функцию для подтверждения. Но это имело бы смысл с учетом того, как оно использовалось для определения функции точечного произведения.
транспонирование — это, по-видимому, просто обычная транспонирование матрицы (импортируется из библиотеки — согласно верхнему комментарию).
Это охватывает весь синтаксис, который я вижу. Таким образом, в конечном итоге он определяет функцию mmult (), которая принимает 3 входных сигнала, M1 amp; M2 — это списки списков чисел (т. Е. Матриц), а M3 — это выходные данные.