Space-函数式符号的高效书写

Question

写函数式记法，在辅助space消耗方面，往往成本相当高。这对于列表的规范编写尤为重要。

首先考虑输出的大小：而通常的ignore_ops(false)写作需要至少2n+1个字符的列表长度n 如[1,2,3]，规范写作至少需要7n+2如'.'(1,'.'(2,'.'(3,[])))。（补充：）无法更改输出，因为它是这样定义的。不过在写作中还有很大的提升空间：

现在考虑写入输出所需的辅助 space：用方括号编写列表不需要任何与列表长度成比例的辅助 space。天真的规范写作需要 space 与列表的长度成比例来表示缩进堆栈。

如何在没有开销的情况下规范地编写列表？

这是一个简单的测试，可以检查您的系统中发生了什么。

首先，减少最大虚拟内存大小以减少您的等待时间，大约 180M 左右适合我。

$ ulimit -v -180000

有

nat_sx(N0, s(X)) :-
   N0 > 0,
   N1 is N0-1, nat_sx(N1,X).
nat_sx(0, 0).

?- open('/dev/null',write,Null),
   length(_,I), N is 10^I, nat_sx(N,SX),
   ( Res=unwritten ; write_canonical(Null,SX) ).

SICStus 和 SWI 现在都在 write_canonical(Null, SX) 内中止。预计他们宁愿在 nat_sx/2 的某个时候中止。列表的直接比较是不可能的，因为 SWI 的 write_canonical/1 总是使用方括号。

Answer 1

就把'.'(当成左括号，,'.'(当成逗号，把最后输出的右括号的整数个数递增作为右括号。

因此O(1)辅助space.

Answer 2

有人可能认为在 Prolog 中实现 write_canonical/1 本身可以解决本机堆栈问题。但是有一点扭曲，如果我使用这段代码，那么 writec/1 不能使用最后调用优化，因为最后有一个 write(')'):

writec(X) :- 
    X =.. [F,Y|L], !,
    writeq(F),
    write('('),
    writec(Y),
    writec_list(L),
    write(')').              /* prevents LCO */
writec(X) :-
    writeq(X).

writec_list([]).
writec_list([X|L]) :-
    write(','),
    writec(X),
    writec_list(L).

对于 SWI-Prolog 中的列表，需要添加从 '[|]' 到 '.' 的翻译。但除此之外，代码按预期工作：

?- writec(f(h(- 1),g(2+3))).
f(h(-(1)),g(+(2,3)))
true.
?- writec([a,b,c]).
'[|]'(a,'[|]'(b,'[|]'(c,[])))
true.

但是按照Will Ness的思路我们可以将代码改造如下。我们按照建议使用右括号的整数计数，并在 writec:

的原子情况下处理右括号

writec2(X) :-
    writec2(0, X).

writec2(N, X) :- 
    X =.. [F,Y], !,
    writeq(F),
    write('('),
    M is N+1,
    writec2(M, Y).
writec2(N, X) :- 
    X =.. [F,Y,Z|L], !,
    writeq(F),
    write('('),
    writec2(Y),
    writec2_list([Z|L], N).
writec2(N, X) :- 
    writeq(X),
    writec2_closing(N).

writec2_closing(0) :- !.
writec2_closing(N) :-
    M is N-1,
    write(')'),
    writec2_closing(M).
    
writec2_list([X], N) :- !,
    write(','),
    M is N+1,
    writec2(M, X).
writec2_list([X,Y|L], N) :-
    write(','),
    writec2(X),
    writec2_list([Y|L], N).

以上代码现在完全可以进行最后调用优化。人们可能会尝试使用最后一个复合参数的循环将其移植回本机堆栈例程。最后的健全性检查，它确实做了正确的事情：

?- writec2(f(h(- 1),g(2+3))).
f(h(-(1)),g(+(2,3)))
true.
?- writec2([a,b,c]).
'[|]'(a,'[|]'(b,'[|]'(c,[])))
true.

Space-函数式符号的高效书写

Space-efficient writing of functional notation

list

prolog

iso-prolog