Есть ли у Пролога псевдоним «оператор», такой как Haskell?

Question

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

tails a@(_:xs) = a : tails xs 
tails [] = [[]] 

The @ гарантирует, что у вас есть ссылки на оба полный аргумент, а также ссылку на некоторые части структуры параметра. Это интеллектуальная производительность (это скорее взлом производительности, так как восстановление массива (x:xs)) в теле первой строки, будет - если не оптимизировано компилятором - приведет к распределению нового объекта, изменению полей и т. Д. См. here для получения дополнительной информации.

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

tails([H|T],[[H|T]|TA]) :- 
    tails(T,TA). 
tails([],[[]]). 

Но это может быть более эффективным, если бы был " как "-оператор типа:

tails(L@[_|T],[L|TA]) :- %This does not compile 
    tails(T,TA). 
tails([],[[]]). 

Есть ли такая конструкция или языковое расширение?

Answer 1

TL; Полезная идея ! Ускорение, по-видимому, ограничено ~ 20% (для большинства размеров списка).

В этом ответе, мы сравним три различные предикатов, которые различаются в отношении повторного использования @ -кака данных:

 
list_tails([], [[]]).    % (1) like `tails/2` given by the OP ... 
list_tails([E|Es], [[E|Es]|Ess]) :- %  ....... but with a better name :-) 
    list_tails(Es, Ess). 

list_sfxs1(Es, [Es|Ess]) :-   % (2) "re-use, mutual recursion" 
    aux_list_sfxs1(Es, Ess).   %  "sfxs" is short for "suffixes" 

aux_list_sfxs1([], []). 
aux_list_sfxs1([_|Es], Ess) :- 
    list_sfxs1(Es, Ess). 

list_sfxs2([], [[]]).    % (3) "re-use, direct recursion" 
list_sfxs2(Es0, [Es0|Ess]) :- 
    Es0 = [_|Es], 
    list_sfxs2(Es, Ess). 

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

 
:-( dif (D, sicstus), current_prolog_flag (dialect ,D) 
    ; use_module (library(between)) 
). 

run_benchs(P_2s, P_2, L, N, T_ms) :- 
    between (1, 6, I), 
    L  is 10 ^ I, 
    N is 10^(8-I), 
    length (Xs, L), 
    member (P_2, P_2s), 
    garbage_collect , 
    call_walltime(run_bench_core(P_2,Xs,N), T_ms). 

run_bench_core(P_2, Xs, N) :- 
    between(1, N, _), 
    call (P_2, Xs, _), 
    false . 
run_bench_core(_, _, _). 

Для измерения wall-time , мы используем call_ walltime /2 -a изменение call_time/2:

 
call_walltime(G, T_ms) :- 
    statistics (walltime , [T0|_]), 
    G, 
    statistics(walltime, [T1|_]), 
    T_ms is T1 - T0. 

Давайте соберем выше варианты кода для теста ...

• ... используя другой список длин L ...
• ... и работает каждый тест несколько раз N (для лучшая точность).

Во-первых, мы используем swi-prolog версию 7.3.14 (64-битный):

 
?- run_benchs([list_sfxs1,list_sfxs2,list_tails], P_2, L, N, T_ms). 
    P_2 = list_sfxs1, L*N = 10*10000000, T_ms = 7925 
; P_2 = list_sfxs2, L*N = 10*10000000, T_ms = 7524 
; P_2 = list_tails, L*N = 10*10000000, T_ms = 6936 
; 
    P_2 = list_sfxs1, L*N = 100*1000000, T_ms = 6502 
; P_2 = list_sfxs2, L*N = 100*1000000, T_ms = 5861 
; P_2 = list_tails, L*N = 100*1000000, T_ms = 5618 
; 
    P_2 = list_sfxs1, L*N = 1000*100000, T_ms = 6434 
; P_2 = list_sfxs2, L*N = 1000*100000, T_ms = 5817 
; P_2 = list_tails, L*N = 1000*100000, T_ms = 9916 
; 
    P_2 = list_sfxs1, L*N = 10000*10000, T_ms = 6328 
; P_2 = list_sfxs2, L*N = 10000*10000, T_ms = 5688 
; P_2 = list_tails, L*N = 10000*10000, T_ms = 9442 
; 
    P_2 = list_sfxs1, L*N = 100000*1000, T_ms = 10255 
; P_2 = list_sfxs2, L*N = 100000*1000, T_ms = 10296 
; P_2 = list_tails, L*N = 100000*1000, T_ms = 14592 
; 
    P_2 = list_sfxs1, L*N = 1000000*100, T_ms = 6955 
; P_2 = list_sfxs2, L*N = 1000000*100, T_ms = 6534 
; P_2 = list_tails, L*N = 1000000*100, T_ms = 9738. 

Затем мы повторить предыдущий запрос с использованием sicstus-prolog версии 4.3.2 (64 бит):

 
?- run_benchs([list_sfxs1,list_sfxs2,list_tails], P_2, L, N, T_ms). 
    P_2 = list_sfxs1, L*N = 10*10000000, T_ms = 1580 
; P_2 = list_sfxs2, L*N = 10*10000000, T_ms = 1610 
; P_2 = list_tails, L*N = 10*10000000, T_ms = 1580 
; 
    P_2 = list_sfxs1, L*N = 100*1000000, T_ms = 710 
; P_2 = list_sfxs2, L*N = 100*1000000, T_ms = 750 
; P_2 = list_tails, L*N = 100*1000000, T_ms = 840 
; 
    P_2 = list_sfxs1, L*N = 1000*100000, T_ms = 650 
; P_2 = list_sfxs2, L*N = 1000*100000, T_ms = 660 
; P_2 = list_tails, L*N = 1000*100000, T_ms = 740 
; 
    P_2 = list_sfxs1, L*N = 10000*10000, T_ms = 620 
; P_2 = list_sfxs2, L*N = 10000*10000, T_ms = 650 
; P_2 = list_tails, L*N = 10000*10000, T_ms = 740 
; 
    P_2 = list_sfxs1, L*N = 100000*1000, T_ms = 670 
; P_2 = list_sfxs2, L*N = 100000*1000, T_ms = 650 
; P_2 = list_tails, L*N = 100000*1000, T_ms = 750 
; 
    P_2 = list_sfxs1, L*N = 1000000*100, T_ms = 12610 
; P_2 = list_sfxs2, L*N = 1000000*100, T_ms = 12560 
; P_2 = list_tails, L*N = 1000000*100, T_ms = 33460. 

Резюме:

• псевдоним штуковина может и ведет к улучшению производительности значительно.
• В этих тестах SICStus Пролог jit дает 10X ускорение, по сравнению с SWI-Prolog!

---

^{Сноска 1: Почему трюк сдачи (@)/2 в голове правила? В конечном итоге с кодом idiomatic Пролог?
Сноска 2: Мы заинтересованы в общей продолжительности работы. Зачем? Потому что затраты на сбор мусора показывают большие размеры данных!
Сноска 3: Последовательность ответов была обработана после обработки для удобства чтения.
Сноска 4: Имеются в наличии начиная с release 4.3.0. Текущие целевые архитектуры включают IA-32 и AMD64.}