节省空间的功能符号书写

Question

就辅助空间消耗而言，编写功能符号通常非常昂贵。这对于列表的规范编写尤其重要。

首先考虑输出的大小：对于长度为n的列表，通常的ignore_ops(false)书写需要至少2n+1 个字符，如 in ，规范书写至少需要7n+2 个字符，如。（添加：）无法更改输出，因为它是这样定义的，但是，在编写过程中还有很大的改进空间：[1,2,3]'.'(1,'.'(2,'.'(3,[])))

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

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

---

这是一个简单的测试，用于检查系统中发生的情况。

首先，减少最大虚拟内存大小以减少您的等待时间，一些 180M-ish 适合我。

$ 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. 列表的直接比较是不可能的，因为 SWIwrite_canonical/1总是使用方括号。

Answer 1

只需将'.'(左括号,'.'(视为逗号，并将最后要输出的右括号的整数计数增加为右括号。

因此O(1)辅助空间。