[Tex/LaTex] Drawing a LISP expression as a tree

tikz-trees

Somewhat inspired by How to automatically draw tree diagram of prime factorization with LaTeX? and mostly motivated by laziness, I'd like to be able to draw a tree defined by LISP syntax for a class I'll be TA'ing next semester.

For those who don't know, LISP is a programming language (the second oldest, in fact) that specifies programs directly as trees:

(defun count (a l &optional c)
  (if l                                      ;; if l is not empty [()===nil]
      (count a                               ;; return the number of a's in the cdr
             (cdr l)
             (+ (if c c 0)                   ;; add c (if it wasn't given, start with 0)
                (if (equal a (car l)) 1 0))) ;; and 1 or 0, if a==l[0]
    c))                                      ;; otherwise, return the count

Given the (if ...) sequence, I'd like it to come up with something like this:

\documentclass{article}
\usepackage{tikz}
\usepackage[active,tightpage]{preview}
\PreviewEnvironment{tikzpicture}
\setlength{\PreviewBorder}{10pt}%
\usetikzlibrary{arrows}

\begin{document}
\begin{tikzpicture}[->,>=stealth',level/.style={sibling distance = 10cm/#1,
  level distance = 1.5cm}] 
\node  {if}
    child{ node {l} }
    child{ node {count}
            child{ node {a} }
            child{ node {cdr}
                    child{node {l}}}
            child{ node {+}
                            child{ node {if}
                                child { node {c} }
                                child { node {c} }
                                child { node {0} }}
                            child{ node {if}
                                child { node {equal}
                                    child {node {a}}
                                    child {node {car}
                                        child { node {l}}}}
                                child { node {1}}
                                child { node {0}}}}}
; 
\end{tikzpicture}
\end{document}

Obviously the style is whatever looks best, but I'd like the macro to avoid the crossings that my example is a victim of.

enter image description here

My best guesses are to make ( and ) active somehow, but I don't have the TeXnical experience to define such macros off-hand.

Best Answer

Both the following solutions can work with a literal & and

\catcode`\&=12

forest + xstring

A proof of concept that uses xstring to split things at spaces. Unfortunately, setting the opening bracket and the closing bracket didn’t work for me so a quick Search’n’Replace will be needed.

The afterthough key is redefined so that everything after a child and the next closing ] is forwarded to the splitter* key.

Code

\documentclass[tikz]{standalone}
\usepackage{forest,xstring}
\forestset{
  splitter/.code={%
    \fullexpandarg
    \IfSubStr{\forestov{content}}{ }{%
      \StrCount{\forestove{content}}{ }[\cnt]%
      \def\forestPrepend{}%
      \foreach \Cnt[evaluate={\CNT=int(\Cnt+1)}] in {\cnt,...,1} {%
        \StrBetween[\Cnt,\CNT]{\forestov{content} }{ }{ }[\tmp]%
        \xappto\forestPrepend{,prepend={[\expandonce\tmp]}}%
      }%
      \expandafter\forestset\expandafter{\forestPrepend}%
      \StrBefore{\forestov{content}}{ }[\forestContent]%
      \forestolet{content}\forestContent%
    }{}},
  splitter*/.code={%
    \noexpandarg
    \IfSubStr{ #1}{ }{%
      \StrCount{ #1}{ }[\cnt]%
      \def\forestAppend{}%
      \foreach \Cnt[evaluate={\CNT=int(\Cnt+1)}] in {1,...,\cnt} {%
        \StrBetween[\Cnt,\CNT]{ #1 }{ }{ }[\tmp]%
        \xappto\forestAppend{,append={[\expandonce\tmp]}}%
      }%
      \expandafter\forestset\expandafter{\forestAppend}
    }{}}}
\makeatother
\begin{document}
\ttfamily
\begin{forest}  for tree={delay=splitter, afterthought/.style={for parent={splitter*={#1}}}}
[defun count [a l \&optional c]
  [if l
      [count a
             [cdr l]
             [+ [if c c 0]
                [if [equal a [car l] ] 1 0]]]
    c]]
\end{forest}
\end{document}

Output

enter image description here

forest-qtree

With the excellent setup of the forest-qtree.sty file from the author of forest himself and a small change (that may be needed again at other places), it is even easier. Unfortunately, setting the brackets to ( and ) hasn’t worked out for me so far.

For some reason, standalone outputs one big empty page before and one page the size of the tree after the actual tree …

Code

\documentclass[tikz]{standalone}
\usepackage{forest-qtree}
\makeatletter
\forestset{
  qtree without dots/.style={% so no empty parent
    qtree,
    /utils/exec=%
      \def\forest@qtree@parse@opening{%
        \@ifnextchar.{\forest@qtree@parse@label}{\forest@qtree@parse@label.}%
      }}}
\makeatother
\begin{document}
\begin{forest} qtree without dots
[defun count [a l \&optional c]
  [if l
      [count a
             [cdr l]
             [+ [if c c 0]
                [if [equal a [car l] ] 1 0]]]
    c]]
\end{forest}
\end{document}

Output

enter image description here

Related Question