# Drawing a LISP expression as a tree

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.

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

-

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}


# 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

-

The forest package is your best friend here, since it allows you to specify the bracket that it uses for the tree! However, since it requires all terminals to be bracketed, I needed to adjust the Lisp code to fit that requirement. It's a long time since I've used Lisp, so I might have messed up some things. I also changed the comment characters and escaped the &. More complicated code might encounter other characters that would need to be escaped, but this is proof of concept. It seems that you could definitely use this method with minimal changes to your Lisp source to generate the appropriate trees.

\documentclass[png,border=4pt]{standalone}
\usepackage{forest}
\bracketset{
opening bracket=(,
closing bracket=)}
\begin{document}
\begin{forest}
(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
\end{forest}

\end{document}


-
@Qrrbrbirlbel Yes, I just realised that. forest requires terminals to be bracketed, which is the problem. Hmm. Back to the drawing board, I guess. –  Alan Munn Oct 26 '13 at 19:13
@Qrrbrbirlbel What's needed is a combination of this and Is it possible to emulate qtree with forest? –  Alan Munn Oct 26 '13 at 19:20
@Qrrbrbirlbel No forest-qtree doesn't solve the problem I think, since it also deals with the . in the label that qtree expects. –  Alan Munn Oct 26 '13 at 19:47
With a small redefinition, forest-qtree can be used when we include the . if it is not there. See my answer. –  Qrrbrbirlbel Oct 26 '13 at 20:16
@Qrrbrbirlbel Nice. I didn't have the patience to hunt throught the forest-qtree` code. :) –  Alan Munn Oct 26 '13 at 20:34