读取记录列表，并使用Prolog对以前的记录执行正在进行的计算。

Question

这是一个操场的例子，灵感来自我曾经做过的一个真正的任务(更复杂)。基本流程是从顺序文件中读取记录。有些记录包含需要检查先前记录以计算值的命令。

这个解决方案的不可取之处在于它需要额外的列表，因此需要额外的重复存储。在下面的代码中，这个额外的列表被称为“记住”。这个例子有一个简单的记录结构，只包含一个数据值，所以复制记忆列表中的所有内容不是一个真正的问题。但是，请假定真正的任务涉及到一个更加复杂的记录结构，因此复制记忆列表中的所有内容是非常不可取的。

我倾向于使用双链接列表，但是在这个链接Prolog中的双链接列表的讨论中，似乎这不是Prolog做事情的方式。因此，我有兴趣看看Prolog的做事方式应该是什么。

/*
A file contains sequential records.
There are two types of record.
A data record provides a data value.
An average record provides a count and is a request for an average of the last count data values.
The parse dcg below parses a list from the data file.
The report dcg uses that list to generate a report.

After parse the list looks like this:

[value=5.9,value=4.7,value=7.5,average=3,value=9.0,value=1.1,value=8.3,average=5,value=7.1,value=1.3,value=6.7,value=9.9,value=0.5,value=0.3,value=1.5,value=0.2,average=7,value=2.2,value=7.8,value=2.5,value=4.5,value=2.4,value=9.7,average=4,value=5.2,value=8.5,value=2.2,value=8.0,value=0.7].

An example report looks like this:

[[count=3,total=18.1,average=6.033333333333333],[count=5,total=30.599999999999998,average=6.12],[count=7,total=20.400000000000002,average=2.9142857142857146],[count=4,total=19.1,average=4.775]].
*/

:- use_module(library(dcg/basics)).
:- use_module(library(readutil)).
:- use_module(library(clpfd)).
:- use_module(library(clpr)).

dospy
:-
spy(report),
spy(average),
leash(-all).

:- initialization main.

report(LIST)
-->
% the report starts with nothing to REMEMBER.
report(LIST,[]).

report([value=VALUE|LIST],REMEMBER)
-->
% value in the LIST goes into REMEMBER.
report(LIST,[value=VALUE|REMEMBER]).

report([average=COUNT|LIST],REMEMBER)
-->
% request for average in the LIST.
average(REMEMBER,COUNT),
report(LIST,REMEMBER).

report([],_REMEMBER)
% the LIST is empty so the report is done.
--> [].

average(REMEMBER,COUNT)
-->
% the average starts at 0 then accumulates for COUNT values from REMEMBER.
average(REMEMBER,COUNT,0,0.0).

average([value=VALUE|REMEMBER],COUNT,AT,TOTAL)
-->
% found needed value in the REMEMBER.
clpfd( AT #\= COUNT ),
clpfd( AT_NEXT #= AT + 1 ),
clpr( TOTAL_NEXT = TOTAL + VALUE ),
average(REMEMBER,COUNT,AT_NEXT,TOTAL_NEXT).

average(_REMEMBER,COUNT,COUNT,TOTAL)
-->
% all of the needed value have been seen so calculate and add to report. 
clpr( AVERAGE = TOTAL / COUNT ),
[[count=COUNT,total=TOTAL,average=AVERAGE]].

% now the part that does the parse of the data file.

parse(LIST) --> parse(data,LIST).
parse(LIST) --> parse(average,LIST).
parse(LIST) --> parse(end,LIST).

parse(data,[value=FLOAT|LIST])
-->
"data", whites, float(FLOAT), blanks, !,
parse(LIST).

parse(average,[average=COUNT|LIST])
-->
"average", whites, integer(COUNT), blanks, !,
parse(LIST).

parse(end,[])
-->
[].

clpr( CLPR )
-->
{ clpr:{ CLPR } }.

clpfd( CLPFD )
-->
{ CLPFD }.

main :-
system:( read_file_to_codes("doubly_motivation_data.txt",CODES,[]) ),
prolog:( phrase(parse(LIST),CODES) ),
system:( writeq(LIST),writeln(.) ),
prolog:( phrase(report(LIST),REPORT) ),
system:( writeq(REPORT),writeln(.) ).

/* doubly_motivation_data.txt
data 5.9
data 4.7
data 7.5
average 3
data 9.0
data 1.1
data 8.3
average 5
data 7.1
data 1.3
data 6.7
data 9.9
data 0.5
data 0.3
data 1.5
data 0.2
average 7
data 2.2
data 7.8
data 2.5
data 4.5
data 2.4
data 9.7
average 4
data 5.2
data 8.5
data 2.2
data 8.0
data 0.7
*/

Answer 1

所以，首先，我注意到你可以在任何一个方向上建立结果。换句话说，经典的"int list“语法是这样的：

intlist([]) --> [].
intlist([X|Xs]) --> integer(X), whites, intlist(Xs).

它的工作方式如下：

?- phrase(intlist(X), "1 23 45 9").
X = [1, 23, 45, 9] ;

但是你可以把它翻过来，这样它就可以像这样向后解析列表：

rintlist([]) --> [].
rintlist([X|Xs]) --> rintlist(Xs), whites, integer(X).

这是可行的，ish：

?- phrase(rintlist(X), "1 23 45 9").
X = [9, 45, 23, 1] 

这样做的问题是，将递归调用放在前面，然后是类似于可以匹配空列表的“空格”之类的东西，这是堆栈爆炸的秘诀。但是，您也可以通过通过DCG本身传递“先前”状态来向后解析事物：

rintlist(L) --> rintlist([], L).
rintlist(Prev, Prev) --> [].
rintlist(Prev, Last) --> integer(X), whites, rintlist([X|Prev], Last).

?- phrase(rintlist(X), "1 23 45 9").
X = [9, 45, 23, 1] .

现在，我认为我们可以很好地解决您的问题；我编写了我的解决方案，现在看到它非常类似于@PauloMoura的上面，但这里无论如何：

commands(Report) --> record(data(V)), blanks, commands([V], _, Report).

commands(Prev, Prev, []) --> [].
commands(Prev, Last, Report) -->
    record(data(V)),
    blanks,
    commands([V|Prev], Last, Report).
commands(Prev, Last, [report(Count, Total, Avg)|Report]) -->
    record(average(N)),
    blanks,
    { calculate_average(N, Prev, Count, Total, Avg) },
    commands(Prev, Last, Report).

calculate_average(N, Prev, Count, Total, Avg) :-
    length(L, N),
    append(L, _, Prev),
    sumlist(L, Total),
    Avg is Total / N,
    Count = N.

这似乎给出了与您的示例类似的输出：

?- phrase_from_file(commands(C), 'mdata.txt'), write_canonical(C).
[report(3,18.1,6.033333333333334),
 report(5,30.599999999999998,6.119999999999999),
 report(7,20.400000000000002,2.9142857142857146),
 report(4,19.1,4.775)]

现在，将其扩展到双链接列表，让我们首先看看我们需要做些什么才能以双链接的方式处理"int list“语法。与这个非常类似，我们必须将前面的链接向前传递到递归调用中，但是比这个更糟糕的是，我们需要用当前节点在前面的变量中填充"next“链接。但是因为这个链接第一次将是nil，所以我们必须有一些条件逻辑来忽略这个链接。我想不出一个合理的空的双链接列表，所以我将基本情况改为[X]而不是[]。所以它变得有点恶心。

% entry point (nil meaning there is no previous)
dlist(X) --> dlist(nil, X).

% base case: last integer
dlist(Prev, node(X, Prev, nil)) --> integer(X).
dlist(Prev, Last) -->
    integer(X), whites,
    {
     Prev = node(PV, PP, Cur)
     -> 
         Cur = node(X, node(PV, PP, Cur), _)
     ;
         Cur = node(X, Prev, _)
    },
    dlist(Cur, Last).

注意Cur = node(..., node(..., Cur), ...)中的自引用。这一统一就是“结结”的本质所在，在前一个环节和这个环节之间。我们试试看：

?- phrase(dlist(L), "1 23 45 9").
L = node(9, _S2, nil), % where
    _S1 = node(1, nil, node(23, _S1, _S2)),
    _S2 = node(45, node(23, _S1, _S2), _71658) 

有点难读，但基本上，从9分到45分，从23分到1分。我们把它从后面分析到前面，最后用指针指向两个方向。

现在还需要做的是更改解析器，用这些指针来发出记录，然后编写一个这样工作的普通人。我无法达到平均水平，所以我写了一个助手，从一个双链接列表中给我“最多N个以前的”：

take_upto(N, DL, Result) :- take_upto(N, 0, DL, [], Result).
take_upto(N, N, _, Result, Result).
take_upto(_, _, nil, Result, Result).
take_upto(N, I, node(V, Prev, _), Rest, Result) :-
    I < N,
    succ(I, I1),
    take_upto(N, I1, Prev, [V|Rest], Result).

它的工作方式如下：

?- phrase(dlist(X), "1 2 3 4 5 6 7 8 9 10"), take_upto(5, X, L).
X = node(10, _S2, nil), % where
   ... [trimmed]
L = [6, 7, 8, 9, 10] .


?- phrase(dlist(X), "1 2 3 4 5 6 7"), take_upto(15, X, L).
X = node(7, _S2, nil), % where
   ... [trimmed]
L = [1, 2, 3, 4, 5, 6, 7] .

有了这个实用程序，我们就可以完成以下操作：

commandsdl(Report) --> commandsdl(nil, _, Report).
commandsdl(Prev, Prev, []) --> [].
commandsdl(Prev, Last, Report) -->
    record(data(V)),
    blanks,
    {
     Prev = node(PV, PP, Cur)
     ->
         Cur = node(V, node(PV, PP, Cur), _)
     ;
         Cur = node(V, Prev, _)
    },
    commandsdl(Cur, Last, Report).
commandsdl(Prev, Last, [report(Count, Total, Avg)|Report]) -->
    record(average(N)),
    blanks,
    {
       calculate_average_dl(N, Prev, Count, Total, Avg)
    },
    commandsdl(Prev, Last, Report).

calculate_average_dl(N, Prev, Count, Total, Avg) :-
    take_upto(N, Prev, L),
    length(L, Count),
    sumlist(L, Total),
    Avg is Total / Count.

总的来说，我很高兴我能够做到这一点，但在这个公式中，您真的不需要双链接列表中的“下一个”指针，所以我倾向于只使用上面的列表实现(如果我查看Logtalk的话，可能是Paulo的实现)。希望这说明了如何使用双链接列表，如果您的实际问题需要它，尽管您的模型并不真正需要它。希望能帮上忙！

Answer 2

遵循Logtalk +SWI解决方案，它不需要任何双链接列表的物化。只需要使用列表实现的堆栈：

------------ reports.lgt ------------
% load the required modules
:- use_module(library(dcg/basics), []).

% ensure desired interpretation of double-quoted text
:- set_prolog_flag(double_quotes, codes).

% optimize the generated code
:- set_logtalk_flag(optimize, on). 


:- object(reports).

    :- public(process/2).

    :- uses(list, [take/3]).
    :- uses(numberlist, [sum/2]).
    :- uses(reader, [file_to_codes/2]).

    :- use_module(dcg_basics, [blanks//0, whites//0, integer//1, float//1]).

    process(File, Report) :-
        file_to_codes(File, Codes),
        phrase(report(Report), Codes).

    report(Report) -->
        data(Value),
        report(Report, [Value]).

    report([], _) -->
        eos.
    report([Record| Records], Stack) -->
        average(Count),
        {compute_record(Count, Stack, Record)},
        report(Records, Stack).
    report(Records, Stack) -->
        data(Value),
        report(Records, [Value| Stack]).

    average(Count) -->
        "average", whites, integer(Count), blanks.

    data(Value) -->
        "data", whites, float(Value), blanks.

    compute_record(Count, Stack, r(Count,Total,Average)) :-
        take(Count, Stack, Values),
        sum(Values, Total),
        Average is Total / Count.

:- end_object.
-------------------------------------

使用问题中的数据文件进行示例调用：

?- {library(types_loader), library(reader_loader), reports}.
...

?- reports::process('doubly_motivation_data.txt', Report).
Report = [r(3, 18.1, 6.033333333333334), r(5, 30.599999999999998, 6.119999999999999), r(7, 20.400000000000002, 2.9142857142857146), r(4, 19.1, 4.775)] .

正如您注意到的，我对报告使用了比列表更合理的表示形式。通过将take/3和sum/2调用组合到自定义谓词中，可以编写一些更有效的解决方案，方法是避免使用堆栈前缀(长度为Count )进行两次遍历，并创建一个临时的值列表。例如：

compute_record(Count, Stack, r(Count,Total,Average)) :-
    compute_record(0, Count, Stack, 0, Total),
    Average is Total / Count.

compute_record(Count, Count, _, Total, Total) :-
    !.
compute_record(Count0, Count, [Value| Stack], Total0, Total) :-
    Count1 is Count0 + 1,
    Total1 is Total0 + Value,
    compute_record(Count1, Count, Stack, Total1, Total).

从示例数据文件来看，该文件的结尾似乎是请求计算文件中所有值的平均值。因此，report//2非终端必须保持整个堆栈，直到所有数据文件被处理。

Answer 3

我会尝试利用DCG的半文本，正如在metalevel.at页面上解释的那样。我认为很容易理解的一个很难理解的例子是这个答案 (在DCG中解决斑马一样的难题)。

hint1 -->
  kind(brad, K), {dif(K, wheat)}, topping(brad, plain), size(walt, small).
hint2 -->
  size(P1, medium), size(P2, medium), {P1 \= P2},
  flavor(P1, hazelnut), topping(P2, peanut_butter).
...

提示访问上下文共享“通过魔术”：

kind(P, K) --> state([P, K, _, _, _]).
topping(P, T) --> state([P, _, T, _, _]).
...

必须以这种方式调用DCG，提供相关的初始状态：

bagels(Sol):- Sol =
    [[brad,_,_,_,_],
     [walt,_,_,_,_],
    ...],
  phrase((hint1, hint2, hint3, hint4, hint5, hint6), [state(Sol)], _).

现在，对于您的应用程序，这几乎是无用的(您已经解决了，只是冗长的方式)。首先，我不明白你为什么要执行2通算法。考虑一下代码是多么简洁，它产生的结果与您发布的结果完全相同(只是显示方式不同)，通过一次传递，使用库(聚合)来执行算术。顺便说一句，为什么clpfd，clpr也能算上.你真的对中电为这么简单的任务提供服务感兴趣吗？

cc_main :-
    %system:( read_file_to_codes("doubly_motivation_data.txt",CODES,[]) ),
    codes(CODES),
    tokenize_atom(CODES, Tks),
    phrase(cc_report([],Rep), Tks),
    maplist(writeln, Rep).

cc_report(_,[]) --> [].
cc_report(R,Re) -->
    [data,N],
    cc_report([N|R],Re).
cc_report(R,[ave(Ave)=sum(Sum)/C|Re]) -->
    [average,C],
    {aggregate_all((sum(V),count),(
         % no need for doubly linked lists, just peek from stack...
         nth1(I,R,V),I=<C
       ),(Sum,Count)),Ave is Sum/Count},
    cc_report(R,Re).

产量：

?- cc_main.
ave(6.033333333333334)=sum(18.1)/3
ave(6.119999999999999)=sum(30.599999999999998)/5
ave(2.9142857142857146)=sum(20.400000000000002)/7
ave(4.775)=sum(19.1)/4
true .

总之，swipl加载项提供了一些有用的材料。例如，参见edgc，它是一个扩展，用于处理多个累加器，同时对Acquarius Prolog编译器的具体语法树进行多次访问--可以追溯到90年代。