Shrubbery Designer is a tool and LISP like language for experimenting with token based editing, code analysis, and visualisation.
It can be used as a utility for on the fly parsing to generate SVG diagrams, or as an interactive text based (ncurses) REPL and editor. It uses SVG graphics and LISP symbolic representation to parse, filter and manipulate code and represent it graphically and in text form.
Shrubbery Designer is a text based tool that runs in a terminal, but it also has a socket interface that enables a separate graphical GUI client to interact with it. Primarily such a GUI client would run in a web browser, but it could also be a standalone graphics program written in GTK+, QT etc.
The idea is that the core program is lightweight enought to run on a small embedded Linux board in a terminal window using the serial port. But when running on a regular pc with graphics capabilities, you connect to the socket and run the GUI client in the browser. Since the program is scriptable it is possible to keep it small when it needs to be, and extend it with more features when running it on a more powerful machine.
Central to the design of Shrubbery Designer is the concept of token based representation, a unified format for storing code that can be interactively presented both as text and graphics.
Token based representation means that code is not stored as individual ascii characters. Instead, the smallest unit of storage is the lexical unit defined by the underlying language, i.e. the lexical token. The term token is borrowed from parser and lexer terminology. In other contexts it might be called a structured editor, or in the LISP tradition, symbolic computing.
These concepts are similar with some overlap and some differences. To avoid confusion; in the context of this project, token based representation will be defined like this:
This format makes text editing a little more awkward than with text based editors, but it makes parsing and manipulating the lexical elements of the code easier.
By also merging in SVG macros and graphics primitives with the lexical token format, the syntax tree can be used to create graphs and diagrams of various kinds. The graphical views are functions that take the syntax tree as input, but they do not alter or translate the syntax tree or create parallel representations that need to be synchronised and updated as the syntax tree is edited. Changes in the text view will immediately show up in the graphics views, and vice versa, because the same underlying data is being edited.
Removing white space from the representation is essential to make parsing regular and simpler. Since most languages allow any number of white space characters to be inserted between tokens you can not easily traverse the code representation if you need to account for an unknown number of white space. Or if you want to compare two snippets of code and see if they are the same it gets even trickier. They may be the same syntactically, but they do not look the same because the spaces and newlines are not the same.
Recursive descent parsers typically have to insert eat white functions everywhere where white space may occur. In Shrubbery Designer this is done once when the file is and parsed into the internal format, which is then free from white space irregularities.
However, the white space information has to be kept with the token format so that newlines and space can be restored when the code is saved or displayed as text. You dont necessarily want to lose the newlines and indentations of the original file when you print it or save it to a text file.
But if you choose, the placement information can be used to change the white space, e.g. to implement a white space rule to reformat and neatify the text according your favorite coding standard.
Shrubbery Designer is implemented in plain c++ as far as possible. It should be easy to compile on different operating systems and even (maybe) on embedded systems. The only libraries required, apart from c++ STL, is ncurses and support for sockets, if the socket service is used.
To build on Ubuntu:
First install build essential sudo apt-get install build-essential Install ncurses sudo apt-get install libncurses5-dev Go to the source directory and type make shrubbery
The documentation is made with Shrubbery Designer in combination with Doxygen. In an earlier version of the program, the documentation and the tests were written in Shrubbery Designer. Perhaps due to all SW developers great love of recursion and metacircularity, or maybe it was just the authors instinct for laziness, this seemed like an elegant concept. In reality, it proved to be a bit tricky and messy when trying to find bugs.
As it turns out, it is probably not a good idea to try to test with the same code that you are testing. Instead, separate documentation and testing frameworks are used, but extended with Shrubbery Designer visualisation and scripting.
So, the documentation uses Doxygen , to create html from plain text.
Tests are written using Crpcut, the Compartmented Robust Posix C++ Unit Test system. This unit testing framework is easy to use and has some great and powerfl features. You can read more about Crpcut here: http://crpcut.sourceforge.net/
To build the documentation and run the tests you need Doxygen and Crpcut:
sudo apt-get install Doxygen Installing crpcut unit test framework For Ubuntu 14.04 the version crpcut 1.9.2 seems to work (best). Download and unpack the tar file from the source forge site and follow the instructions at http://crpcut.sourceforge.net/1.9.2/install-guide.html Use this line for cmake, installing libraries in /usr/local/lib cmake -DLIB_SUFFIX= -DCMAKE_BUILD_TYPE=debug Install make install Run ldconfig and then you can make and run the tests sudo ldconfig cd source make This will make the code, run the tests and create the documentation in a directortory named xdox. A directory named puplic_html will also be created with the subset of the documentation used for the home page.
Shrubbery Designer is still in an early stage of development.
Parts and concepts have been developed and explored in earlier versions of the program and they have hopefully come together now in a design that is good enough to keep.
It may be a little difficult to see at first the idea and utility of having a unified format for storing code that can be interactively presented both as text and graphics, and executed. And, as is often the case with graphical tools, they are probably best explained by demonstration.
So the first step will be to put enough parts together to be able to demonstrate the idea and create more documentation and tutorials. The documentation is also obviously incomplete at this point, so more work is needed there.
After that, the next step will be to arrive at an implementation of the internal parts so that tinkering and tweaking of the the langauge elements can stop. Then further development of features can continue using the scripting language and the basic elements.
Evolution of the project:
- Graphics primitives - svgx. - Lexical heterogenous type based on strings, streams and xml. - LISP like interpreter. - Example and standard diagrams. - Web server based GUI - Graphical Editing. - Garbage Collection.
The part of the software responsible to encoding and manipulating graphics objects is called svgx. It was initially called gx, as in graphics utilities and were developed for an earlier version of the program. Then the idea occured to create SVG graphics directly without using a graphics framework with a canvas concept, like Cairo, wxWidgets etc. So additional functionality was added to support working with SVG strings, which is basically xml encoding, and the name was changed to svgx to reflect the usage of SVG.
The Shrubbery Designer language is a LISP like interpreted language. It is designed as a special purpose language that tries to be as small as it can get away with. It will never be a complete Scheme or LISP, and certainly not be compatible with CLISP or any other standard.
It provides a basic set of LISP functions, conditionals, arithmetic, and foreach and map type looping and a few special purpose functions and types for dealing with the SVG and token editing. The aim is to implement most functionality needed in the language rather than extending it, althugh some features implemented in c++ are provided to make it more comfortable to do editing and visualisation tasks.
Code, list, vector, and graph...
The name Shrubbery Designer was inspired by Monty Python and the knights who say ni!, in the Holy Grail. It seemed a suitable name for a tool that encodes and works on the tree structure of a program, which often more resembles an unwieldy shrubbery at first before the designer gets it pruned, orderly and beautiful.
There were many sources of inspiration and information for the implementing of LISP like scripting.
The Paul Grahams paper / article The Roots of LISP was the first, which made me rediscover LISP and realise how a powerful and surpricingly complete interpreted language can be implemented with just a handful of commands.
The Paul Graham article doesnt give you exactly all the details on how to implement a LISP interpreter though. More detailed information and insight was gained from Gary D Knotts book about implementing LISP. Also some other open source projects were studied to learn about how to implement a simple LISP.
The power of c++ operators, STL, SVG/XML and a dash of OOP were enlisted and combined with the design techniques of c based interpreters, but the basic structure is essentially the same. Especially how LISP goes about implementing heterogenous lists, typed pointers and memory management is somewhat different from how things are usually done in c/c++, and turned out to be key to the power and versatility of LISP style lists and interpreting.
Interpreting LISP by Gary D.Knott
1.8.6 
