How to automatically generate a stack diagram for a PostScript expression?

The following figure shows a PostScript expression and its stack diagrams step by step. Is there any package to generate it out of the box? If there is no such a package, how to generate it automatically for any PostScript expression? I don't want to write my own interpreter for sure.

Any methods are welcome.

-
Do you need it just for debugging? Or do you want to write a PS manual? For the first task I use pstack PS command. –  AlexG Feb 13 at 13:12
@AlexG: I want to write a tutorial about PostScript so it must be typeset by (La)TeX. –  The Last Error Feb 13 at 13:13
I've got a postscript procedure to print the stack on one line. This might be useful in generating the values for arbitrary code. –  luser droog Feb 14 at 1:42
Yes, it was useful. –  luser droog Feb 14 at 19:58

Using bash or a similar command line, executing

s="";for i in 4  2  1 add 1 sub add ; do  s="$s$i"; echo " $s pstack" | gs -q -sDEVICE=pbm | sed -e "s/GS>/\\\\foo{$i}{/" -e "s/GS<[0-9]*>/}/" ; done


produces

\foo{4}{4
}\foo{2}{2
4
}\foo{1}{1
2
4
4
}\foo{1}{1
3
4
}\foo{sub}{2
4
}


and then if you wrap that in some latex:

\documentclass{article}

\def\foo#1#2{%
\parbox[t]{3em}{\centering
\textbf{#1}%
\xfoo#2\$}} \def\xfoo#1 {\ifx\$#1\else\\#1 \expandafter\xfoo\fi}

\begin{document}

% s="";for i in 4  2  1 add 1 sub add ; do  s="$s$i"; echo " $s pstack" | gs -q -sDEVICE=pbm | sed -e "s/GS>/\\\\foo{$i}{/" -e "s/GS<[0-9]*>/}/" ; done

\foo{4}{4
}\foo{2}{2
4
}\foo{1}{1
2
4
4
}\foo{1}{1
3
4
}\foo{sub}{2
4
}

\end{document}


You get

-

Just for fun (or typing exercise or whatever) with TikZ.

It's not complete, but should be trivial to implement the remaining postscript stack commands.

\documentclass[border=0.125cm]{standalone}
\usepackage{tikz}

\makeatletter
\newcount\stacktop
\def\stackclear{\global\stacktop=0\relax}

\def\stackpush#1{%
\expandafter\xdef\csname stack@item@\the\stacktop\endcsname{#1}%
}
\def\stackpeek#1#2{%
\pgfmathparse{int(#1)}%
\edef#2{\csname stack@item@\pgfmathresult\endcsname}%
}
\def\stackpop#1{%
\ifnum\stacktop>0\relax
\edef#1{\csname stack@item@\the\stacktop\endcsname}%
\fi%
}

\def\stackswap#1#2{%
\pgfmathparse{int(#1)}\let\a=\pgfmathresult
\pgfmathparse{int(#2)}\let\b=\pgfmathresult
\edef\tmp{\csname stack@item@\a\endcsname}%
\expandafter\xdef\csname stack@item@\a\endcsname{\csname stack@item@\b\endcsname}%
\expandafter\xdef\csname stack@item@\b\endcsname{\tmp}%
}

\def\stackroll{%
\stackpop\R%
\stackpop\r%
\pgfmathparse{int(\R < 0 ? -\R : \R)}\let\RR=\pgfmathresult
\pgfmathloop%
\ifnum\pgfmathcounter>\RR\relax
\else%
\ifnum\R<0\relax%
\stackrollneg%
\else%
\stackrollpos%
\fi%
\repeatpgfmathloop%
}

\def\stackrollpos{%
\begingroup%
\pgfmathloop%
\ifnum\pgfmathcounter=\r
\else%
\stackswap{\stacktop-\pgfmathcounter+1}{\stacktop-\pgfmathcounter}%
\repeatpgfmathloop%
\endgroup%
}

\def\stackrollneg{%
\begingroup%
\pgfmathloop%
\ifnum\pgfmathcounter=\r
\else%
\stackswap{\stacktop-\r+\pgfmathcounter+1}{\stacktop-\r+\pgfmathcounter}%
\repeatpgfmathloop%
\endgroup%
}

\def\at{@}

\def\stackmathparse#1{%
\pgfmathparse{(#1) == int(#1) ? int(#1) : (#1)}%
}
\tikzset{%
postscript parse/.code={%
\stackclear%
\tikzset{ps/parse={#1 @}}%
},
ps/.cd,
parse/.code args={#1 #2}{%
\def\rest{#2}%
\def\current{#1}%
\tikzset{ps/commands/#1={#2}}%
\tikzset{xshift=1cm}
\node at (0,.75) {#1};
\foreach \i [evaluate={\j=int(\stacktop-\i);}] in {0,...,5}
\node [draw, minimum width=.75cm, minimum height=0.5cm] at (0,-\i/2) {\stackpeek{\j}{\x}\x};
\ifx\rest\at%
\else
\tikzset{ps/parse={#2}}%
\fi%
},
commands/.cd,
.unknown/.code={\stackpush{\current}},
exch/.code={\stackswap{\stacktop}{\stacktop-1}},
roll/.code={\stackroll},
dup/.code={\stackpeek{\stacktop}{\x}\stackpush{\x}},
mul/.code={\stackpop{\x}\stackpop{\y}\stackmathparse{\y*\x}\stackpush{\pgfmathresult}},
sub/.code={\stackpop{\x}\stackpop{\y}\stackmathparse{\y-\x}\stackpush{\pgfmathresult}},
div/.code={\stackpop{\x}\stackpop{\y}\stackmathparse{\y/\x}\stackpush{\pgfmathresult}}
}

\begin{document}
\begin{tabular}{l}
\begin{tikzpicture}
\end{tikzpicture}
\\[0.25in]
\begin{tikzpicture}
\tikzset{postscript parse={4 3 2 1 3 1 roll 3 -1 roll}}
\end{tikzpicture}
\\[0.25in]
\begin{tikzpicture}
\tikzset{postscript parse={3 2 dup mul 5 add exch div}}
\end{tikzpicture}
\end{tabular}
\end{document}


-

For rendering such a stack, I provide the below solution. But as Jake points out, it does not digest a raw postscript expression. However, see the end of this answer to see how I can digest David's bash output.

Here, I use a bunch of nested stacks. The \psdepth (depth of stack tube), \pswidth (width of stack tube), and \psrule (stack rule thickness) may all be tuned.

REEDITED to make the input syntax easier. There is no limit to the stack depth, as there was in an earlier EDIT.

\documentclass{article}
\usepackage[usestackEOL]{stackengine}
\usepackage{ifthen}
\def\psdepth{2cm}
\def\pswidth{.5cm}
\def\psrule{.15ex}
\def\psbar{\rule[-\psdepth]{\psrule}{\psdepth}}
\def\pspipe{\psbar\kern\pswidth\psbar}
\def\pscell#1{\stackunder{\footnotesize#1}{\rule{\pswidth}{\psrule}}}
\newcounter{index}
\makeatletter
\newcommand\psstack[2]{%
\getargsC{#2}%
\setcounter{index}{0}%
\def\psstackdata{}%
\whiledo{\theindex<\narg}{%
\stepcounter{index}%
\protected@edef\thisarg{\csname arg\romannumeral\theindex\endcsname}%
\protected@edef\psstackdata{%
\psstackdata\protect\pscell{\thisarg}}%
\ifthenelse{\theindex<\narg}{\protected@edef\psstackdata{%
\psstackdata \\}}{}%
}%
\sffamily\def\stacktype{L}%
\stackunder{%
\def\stacktype{S}\stackunder{#1}{\pspipe}%
}{%
\def\stacktype{S}\setstackgap{S}{3pt}\expandafter%
\Shortunderstack\expandafter{\psstackdata}%
}%
\hspace{1ex}%
}
\makeatother
\begin{document}
\psstack{4}{4}
\psstack{2}{2 4}
\psstack{1}{1 2 4}
\psstack{exch}{2 1 4}
\psstack{1}{1 3 4}
\psstack{sub}{2 4}
\end{document}


Defining \foo as

\newcommand\foo[2]{%
\getargsC{#2}%
\setcounter{index}{0}%
\def\psstackdata{}%
\whiledo{\theindex<\numexpr\narg-1}{%
\stepcounter{index}%
\protected@edef\thisarg{\csname arg\romannumeral\theindex\endcsname}%
\protected@edef\psstackdata{%
\psstackdata\protect\pscell{\thisarg}}%
\ifthenelse{\theindex<\narg}{\protected@edef\psstackdata{%
\psstackdata \\}}{}%
}%
\sffamily\def\stacktype{L}%
\stackunder{%
\def\stacktype{S}\stackunder{#1}{\pspipe}%
}{%
\def\stacktype{S}\setstackgap{S}{3pt}\expandafter%
\Shortunderstack\expandafter{\psstackdata}%
}%
\hspace{1.85ex}%
}


in my syntax allows one to digest David's bash output and present it with my rendering.

-
I think the OP wants to generate the diagram automatically from a PS expression. –  Jake Feb 13 at 13:22
@Jake I see what you mean. But I don't know enough about "postscript" expressions" to do the conversion. But perhaps a front end to this code could be adapted to feed it the data. –  Steven B. Segletes Feb 13 at 13:30

The automatic generation is easy to realize with LuaTeX, which I leave to the reader ...

\documentclass{article}
\usepackage{array,multido}
\newcount\stackNo  \def\maxStackNo{6}
\makeatletter
\newtoks\ps@stack

\newcommand*\psstack[2]{%
\sffamily\stackNo=0
\ps@stack={\,\tabular[t]{ |c| }
\multicolumn{1}{c}{\makebox[0pt]{\Large#1}}}
\expandafter\psstack@i#2,,\@nil}
\ifx\relax#2\relax\def\next{\psstack@ii}%
\else\def\next{\psstack@i#2,#3\@nil}%
\fi\next}
\def\psstack@ii{%
\loop
\expandafter\ifnum\the\stackNo<\maxStackNo
\repeat
\the\ps@stack \ps@stack={}%
}
\makeatother
\begin{document}
\psstack{4}   {4}
\psstack{2}   {2,4}
\psstack{1}   {1,2,4}
\psstack{exch}{2,1,4}
\psstack{1}   {1,3,4}
\psstack{sub} {2,4}
\end{document}


-
Really nice solution, Herbert! –  Svend Tveskæg Feb 13 at 16:06
@SvendTveskæg see Jake's comment on the first answer, I believe the question wants the stack to be determined not supplied –  David Carlisle Feb 13 at 16:09
@DavidCarlisle I missed that. Then I guess it isn't that nice after all. :) –  Svend Tveskæg Feb 13 at 16:13
Is it possible to use PSTricks to automatically construct the diagram? (because in my opinion, PSTricks has a direct access to PostScript then it should be possible) –  The Last Error Feb 14 at 1:00

As for generating the content for the stack pictures, I've been inspired by this thread to clean up some old code and now we can generate nice traces for arbitrary code.

The code is posted to comp.lang.postscript, as it's more directly pertinent there, as this is also a step-wise debugger. The code is mostly level-1 postscript with the exception of << and >> and could potentially be down-ported to run on level-1 interpreters, but it is quite wasteful of memory and might not be practical to use in memory-constrained environments without a garbage collector.

For these code fragments:

1 2 3 add add
6 eq { 8 9 add = } { 9 10 add = } ifelse


And:

 1 2 3 add add
6 eq { 7 } if

9 {
5
count 4 gt {
exit
} if
} repeat

{ 55 exit } loop

(continuation) =

0 1 10 {
dup 5 eq {exit} if
} for


I get the following stack trace output:

GPL Ghostscript 9.06 (2012-08-08)
This software comes with NO WARRANTY: see the file PUBLIC for details.
%|-
1  %|- 1
2  %|- 1 2
3  %|- 1 2 3
6  %|- 6 6
eq  %|- true
ifelse  %|-
8  %|- 8
9  %|- 8 9
= 17

%|-
1  %|- 1
2  %|- 1 2
3  %|- 1 2 3
6  %|- 6 6
eq  %|- true
{7}  %|- true {7}
if  %|-
7  %|- 7
9  %|- 7 9
{5 count 4 gt {exit} if}  %|- 7 9 {5 count 4 gt {exit} if}
repeat  %|- 7
5  %|- 7 5
count  %|- 7 5 2
4  %|- 7 5 2 4
gt  %|- 7 5 false
{exit}  %|- 7 5 false {exit}
if  %|- 7 5
8  %|- 7 5 8
{5 count 4 gt {exit} if}  %|- 7 5 8 {5 count 4 gt {exit} if}
repeat  %|- 7 5
5  %|- 7 5 5
count  %|- 7 5 5 3
4  %|- 7 5 5 3 4
gt  %|- 7 5 5 false
{exit}  %|- 7 5 5 false {exit}
if  %|- 7 5 5
7  %|- 7 5 5 7
{5 count 4 gt {exit} if}  %|- 7 5 5 7 {5 count 4 gt {exit} if}
repeat  %|- 7 5 5
5  %|- 7 5 5 5
count  %|- 7 5 5 5 4
4  %|- 7 5 5 5 4 4
gt  %|- 7 5 5 5 false
{exit}  %|- 7 5 5 5 false {exit}
if  %|- 7 5 5 5
6  %|- 7 5 5 5 6
{5 count 4 gt {exit} if}  %|- 7 5 5 5 6 {5 count 4 gt {exit} if}
repeat  %|- 7 5 5 5
5  %|- 7 5 5 5 5
count  %|- 7 5 5 5 5 5
4  %|- 7 5 5 5 5 5 4
gt  %|- 7 5 5 5 5 true
{exit}  %|- 7 5 5 5 5 true {exit}
if  %|- 7 5 5 5 5
exit  %|- 7 5 5 5 5
{55 exit}  %|- 7 5 5 5 5 {55 exit}
loop  %|- 7 5 5 5 5
55  %|- 7 5 5 5 5 55
exit  %|- 7 5 5 5 5 55
(continuation)  %|- 7 5 5 5 5 55 (continuation)
= continuation
%|- 7 5 5 5 5 55
0  %|- 7 5 5 5 5 55 0
1  %|- 7 5 5 5 5 55 0 1
10  %|- 7 5 5 5 5 55 0 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0
dup  %|- 7 5 5 5 5 55 0 0
5  %|- 7 5 5 5 5 55 0 0 5
eq  %|- 7 5 5 5 5 55 0 false
{exit}  %|- 7 5 5 5 5 55 0 false {exit}
if  %|- 7 5 5 5 5 55 0
1  %|- 7 5 5 5 5 55 0 1
1  %|- 7 5 5 5 5 55 0 1 1
10  %|- 7 5 5 5 5 55 0 1 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0 1
dup  %|- 7 5 5 5 5 55 0 1 1
5  %|- 7 5 5 5 5 55 0 1 1 5
eq  %|- 7 5 5 5 5 55 0 1 false
{exit}  %|- 7 5 5 5 5 55 0 1 false {exit}
if  %|- 7 5 5 5 5 55 0 1
2  %|- 7 5 5 5 5 55 0 1 2
1  %|- 7 5 5 5 5 55 0 1 2 1
10  %|- 7 5 5 5 5 55 0 1 2 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 2 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0 1 2
dup  %|- 7 5 5 5 5 55 0 1 2 2
5  %|- 7 5 5 5 5 55 0 1 2 2 5
eq  %|- 7 5 5 5 5 55 0 1 2 false
{exit}  %|- 7 5 5 5 5 55 0 1 2 false {exit}
if  %|- 7 5 5 5 5 55 0 1 2
3  %|- 7 5 5 5 5 55 0 1 2 3
1  %|- 7 5 5 5 5 55 0 1 2 3 1
10  %|- 7 5 5 5 5 55 0 1 2 3 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 2 3 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0 1 2 3
dup  %|- 7 5 5 5 5 55 0 1 2 3 3
5  %|- 7 5 5 5 5 55 0 1 2 3 3 5
eq  %|- 7 5 5 5 5 55 0 1 2 3 false
{exit}  %|- 7 5 5 5 5 55 0 1 2 3 false {exit}
if  %|- 7 5 5 5 5 55 0 1 2 3
4  %|- 7 5 5 5 5 55 0 1 2 3 4
1  %|- 7 5 5 5 5 55 0 1 2 3 4 1
10  %|- 7 5 5 5 5 55 0 1 2 3 4 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 2 3 4 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0 1 2 3 4
dup  %|- 7 5 5 5 5 55 0 1 2 3 4 4
5  %|- 7 5 5 5 5 55 0 1 2 3 4 4 5
eq  %|- 7 5 5 5 5 55 0 1 2 3 4 false
{exit}  %|- 7 5 5 5 5 55 0 1 2 3 4 false {exit}
if  %|- 7 5 5 5 5 55 0 1 2 3 4
5  %|- 7 5 5 5 5 55 0 1 2 3 4 5
1  %|- 7 5 5 5 5 55 0 1 2 3 4 5 1
10  %|- 7 5 5 5 5 55 0 1 2 3 4 5 1 10
{dup 5 eq {exit} if}  %|- 7 5 5 5 5 55 0 1 2 3 4 5 1 10 {dup 5 eq {exit} if}
for  %|- 7 5 5 5 5 55 0 1 2 3 4 5
dup  %|- 7 5 5 5 5 55 0 1 2 3 4 5 5
5  %|- 7 5 5 5 5 55 0 1 2 3 4 5 5 5
eq  %|- 7 5 5 5 5 55 0 1 2 3 4 5 true
{exit}  %|- 7 5 5 5 5 55 0 1 2 3 4 5 true {exit}
if  %|- 7 5 5 5 5 55 0 1 2 3 4 5
exit GS<12>

-