Hat Prolog einen Alias ​​"Operator" wie Haskell?

Question

In Haskell gibt es eine Sprachfunktion namens "as" -Operator (manchmal als Alias ​​bekannt). Die Idee ist folgende: Da Sie eine Funktion haben, dass zum Beispiel als Eingabe eine Liste und will alle Schwänze zurückkehren, können Sie dies als implementieren können:

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

Die @ sorgt dafür, dass Sie einen Verweis müssen sowohl die ganzes Argument sowie eine Referenz auf einige Teile der Struktur des Parameters. Dies ist intelligent performance-weise (es ist mehr ein Performance-Hack, weil ein Array (x:xs) rekonstruieren) im Körper der ersten Zeile, wird - wenn nicht vom Compiler optimiert - führen zu einem neuen Objekt zuweisen, Felder ändern usw. Siehe here für weitere Informationen.

Ich frage mich, ob Prolog etwas Gleichwertiges hat: zum Beispiel, wenn Sie Schwänze in Prolog implementieren möchten, kann es die folgende Art und Weise erfolgen:

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

Aber es könnte effizienter sein, wenn es eine " als "-Operator wie:

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

Gibt es ein solches Konstrukt oder eine Spracherweiterung?

Answer 1

TL; DR: Gute Idee ! Die Beschleunigung scheint auf ~ 20% begrenzt zu sein (für die meisten Listengrößen).

In dieser Antwort, vergleichen wir drei verschiedene Prädikate, die in Bezug auf unterschiedlich @ -ähnlichen Wiederverwendung von Daten:

 
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). 

Laufzeit zu messen, verwenden wir den folgenden Code:

 
:-( 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(_, _, _). 

Zur Messung wall-time verwenden wir call_ walltime /2-eine Variation von call_time/2:

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

den obigen Code Variationen auf die Probe stellen lassen ...

• ... andere Liste mit Längen L ...
• ... und läuft jeden Test mehrere Male N (für bessere Genauigkeit).

Erstens verwenden wir swi-prolog Version 7.3.14 (64-Bit):

 
?- 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. 

Dann wiederholen wir die vorherige Abfrage mit sicstus-prolog Version 4.3.2 (64-Bit):

 
?- 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. 

Zusammenfassung:

• Das alias-Dingen kann und nicht verbessert Leistung deutlich.
• In diesen Prüfungen der SICStus Prolog jit gibt 10X Speedup, im Vergleich zu SWI-Prolog!

---

^{Fußnote 1: Warum den Stunt (@)/2 in der Regel Kopf setzen? Am Ende mit nicht idiomatic Prolog Code?
Fußnote 2: Wir sind an der Gesamtlaufzeit interessiert. Warum? Denn Müllabfuhrkosten zeigen sich bei größeren Datenmengen!
Fußnote 3: Die Antwortsequenz wurde aus Gründen der Lesbarkeit nachbearbeitet.
Fußnote 4: Verfügbar seit release 4.3.0. Aktuelle Zielarchitekturen umfassen IA-32 und AMD64.}