treelispcommon-lispl-systems

OpenMusic: L-System tree generation using lisp


I am trying to work with a compositional tool called OpenMusic, which is a graphical development environment based on common lisp, and it uses something called "rhythm trees". I am trying to create rhythm trees using a set of rules and in OM this tree must have the following structure:

Given a tree depth n, an initial single node tree (1) and transformation rules:

It should give:

n = 1 -> (1 (1 2))


Solution

  • Recursive algorithms for trees/lists are typically written with COND. You figure out what the ending conditions are, and put those first. Then handle atoms, and finally iterate over a list by recursively calling the function on its CAR and CDR, and CONS the results to produce the output list. So the basic template is like:

    (defun algo (list)
      (cond
        ((end-condition) suitable-end-value)
        ((atom list) (do-something-with-atom list))
        (t (cons (algo (car list)
                 (algo (cdr list))))))
    

    In this case this would be something like:

    (defun rhythm-tree (n tree)
      (cond ((zerop n) tree)                 ; First end-condition.
            ((null tree) '())                ; Another end-condition.
            ((atom tree)                     ; An atom: transform into...
             (cons tree                      ; a list of the atom itself...
                   (list (rhythm-tree (1- n) ; and a list of children.
                                      (case tree
                                        (1 (list 1 2))
                                        (2 (list 1))
                                        (otherwise '()))))))
            ;; Iterate over elements of a list.
            (t (cons (rhythm-tree n (car tree))
                     (rhythm-tree n (cdr tree))))))
    
    (rhythm-tree 1 1)
    ;=> (1 (1 2))
    (rhythm-tree 2 1)
    ;=> (1 ((1 (1 2)) (2 (1))))