Space-efficient writing of functional notation

Question

Writing functional notation is often quite costly in terms of auxiliary space consumption. This is particularly critical for canonical writing of lists.

First consider the size of the output: Whereas the usual ignore_ops(false) writing requires at least 2n+1 characters for a list of length n as in [1,2,3], canonical writing requires at least 7n+2 as in '.'(1,'.'(2,'.'(3,[]))). (Added:) There is no way to change the output, as it is defined like that. However, there is ample room for improvement during writing:

And now consider the auxiliary space required to write the output: Writing lists with square brackets does not require any auxiliary space proportional to the length of the list. A naive canonical writing requires space proportional to the length of the list to represent the stack of indentations.

How to write a list canonically without that overhead?

---

Here is a simple test to check what happens in your system.

First, reduce the maximal virtual memory size to reduce your waiting time, some 180M-ish works for me.

$ ulimit -v -180000

With

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 and SWI alike now abort within write_canonical(Null, SX). It would be expected that they rather abort at some point in nat_sx/2. A direct comparison for lists is not possible, as SWI's write_canonical/1 always uses square brackets.

Answer 1

Just treat '.'( as the opening bracket, ,'.'( as the comma, and increment the integer count of closing parens to be output in the end as the closing bracket.

Thus O(1) auxiliary space.