Jump to content
  • Advertisement
Sign in to follow this  
Andrew Russell

Tree Manipulation Language

This topic is 4441 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently designing a program that needs to manipulate tree structures according to a set of rules. Basically it needs to recognise certain patterns within a tree and use the associated mutation to generate other valid trees. At the moment I'm just considering simple arithmetic trees, but I plan to make it more complicated later. Here is an example of a "language" that I have essentially made up to express this behaviour: 1: (a*b)/c -> a*b*(1/c) 2: (a*b)/c -> (a/c)*(b/c) 3: (a+b)/c -> (a/c)+(b/c) (etc...) As you can see - a number of patterns to recognise, and a number of things they can be converted into. Now, the question is - is there an existing good way to do this? Obviously I could write my own fancy parser for this made-up language. One of the problems with this is that I'll probably want to do more complicated operations eventually - for example (please excuse the fact that I'm essentially making up this "language" as I go): 4: (a*b)/n -> a*b*{evaluate "1/n"} 5: [*a]/b -> {each a, @/b} (Where 4 does the same thing as 1, but evaluates when c is a number "n", and 5 is the same as 2, but for multiplication nodes with more than two children.) Because of the need for arbitrary operations in there, it makes a custom parser solution reasonably annoying. I have heard vaguely that Lisp might be suitable for implementing something like this. I don't know Lisp or what it's capable of (at least in enough detail to know how suitable it is for this). If I used Lisp, it seems that L# is probably a good way to go (seeing as this is the sort of thing that I'd use C# for the GUI and support code). Would you agree? Basically I need a light-weight way of encoding rules (consisting of a pattern and its modified form) for converting tree structures. Is there a good way to do this in Lisp? Or should I go with a custom parser? Is there an even better way that I haven't thought of?

Share this post


Link to post
Share on other sites
Advertisement
Any language with pattern matching would work in this case, including LISP and ML variants. Illustrating with Objective Caml (or F#) syntax:


(* An arithmetic expression tree *)
type tree =
Mul of tree list
| Sum of tree list
| Div of tree * tree
| Sub of tree * tree
| Val of float

(* Transform a tree by a function: apply to the
* subtrees, then to the tree itself. *)
let rec map f = function
| Mul l -> f (Mul (List.map (map f) l))
| Sum l -> f (Sum (List.map (map f) l))
| Div (n,d) -> f (Div (map f n),(map f d))
| Sub (a,b) -> f (Sub (map f a),(map f b))
| Val _ as x -> f x

(* a/c -> a*(1/c) *)
let ex1 =
map (function
| Div (Mul l,d) -> Mul ((Div (Val 1,d))::l)
| Div (n,d) -> Mul [n; Div(Val 1,d)]
| x -> x)

(* [*a]/b -> *{each a: a/b} *)
let ex2 =
map (function
| Div (Mul l,b) -> Mul (List.map (fun a -> Div (a,b)) l)
| x -> x)

(* (a*b)/n -> (a*b)*("1/n") *)
let ex3 =
map (function
| Div (Mul l,Val n) -> Mul ((Val (1./.n))::l)
| x -> x)

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Any language with pattern matching would work in this case, including LISP and ML variants. Illustrating with Objective Caml (or F#) syntax:


code

Did you type that off the top of your head? Thats really impressive! I ask this because of the minor mistakes you made in the code which imply you didnt test the code and did it all off the top of your head.
(* An arithmetic expression tree *)
type tree =
Mul of tree list
| Sum of tree list
| Div of tree * tree
| Sub of tree * tree
| Val of float

(* Transform a tree by a function: apply to the
* subtrees, then to the tree itself. *)
let rec map f = function
| Mul l -> f (Mul (List.map (map f) l))
| Sum l -> f (Sum (List.map (map f) l))
| Div (n,d) -> f ( Div ((map f n),(map f d)) ) (* missing parentheses make it so no tuples *)
| Sub (a,b) -> f ( Sub ((map f a),(map f b)) )

| Val _ as x -> f x

(* a/c -> a*(1/c) *)
let ex1 =
map (function
| Div (Mul l,d) -> Mul ((Div (Val 1.0,d))::l) (* incorrect type*)
| Div (n,d) -> Mul [n; Div(Val 1.0,d)]

| x -> x)

(* [*a]/b -> *{each a: a/b} *)
let ex2 =
map (function
| Div (Mul l,b) -> Mul (List.map (fun a -> Div (a,b)) l)
| x -> x)

(* (a*b)/n -> (a*b)*("1/n") *)
let ex3 =
map (function
| Div (Mul l,Val n) -> Mul ((Val (1./.n))::l)
| x -> x)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It's also very straightforward in lisp. I remember demonstrating this in scheme in this forum, but I don't remember the thread. I'll use Common Lisp this time.

The drawback is that you have to roll your own pattern matcher (or leverage destructuring-bind), and that it is most convenient to use prefix notation for your trees. But writing the pattern matcher is trivial.

The advantage is that lisp is itself directly represented as a parse tree (that's what all the parentheses are for!) so you can just use the lisp evaluator to evaluate your expressions if they're written in terms of operators lisp understands (ie, built-in or defined by you).

First, we write the pattern matcher:


(defun var-p (pattern)
"This is to check whether something in a pattern is a pattern variable
or something else (the + - * / symbols you want to treat as constant)."
(and (symbolp pattern) (not (member pattern '(nil + - * /)))))

(defun quoted-p (pattern)
"This we won't use yet, but it will allow us to use symbols as constants in
a pattern. "
(and (consp pattern) (eq 'quote (car pattern))))

(defun match-var (var expr bindings)
"If a pattern variable is already bound, the match succeeds if the bindings
coincide. If not, the match succeeds and the new bnding is established."
(let ((binding (assoc var bindings)))
(cond ((and binding (equalp (cdr binding) expr))
bindings)
((not binding)
(acons var expr bindings))
(t 'match-fail))))

(defun pattern-match (pattern expr bindings)
"A vanilla pattern matcher."
(cond ((eq bindings 'match-fail)
'match-fail)
((var-p pattern)
(match-var pattern expr bindings))
((and (consp pattern) (consp expr))
(pattern-match (cdr pattern) (cdr expr)
(pattern-match (car pattern) (car expr) bindings)))
((equalp pattern expr)
bindings)
(t 'match-fail)))



Now, we write a function that takes a set of bindings and an expression and replaces the bound variables in the expression with their bindings. We also write a macro that automates the housekeeping of building a tree transformer.


(defun apply-bindings (expr bindings)
(if (consp expr)
(cons (apply-bindings (car expr) bindings)
(apply-bindings (cdr expr) bindings))
(let ((binding (assoc expr bindings)))
(if binding
(cdr binding)
expr))))

(defmacro make-transformer (in-pattern out-pattern expr)
(let ((bindings (gensym)))
`(let ((,bindings (pattern-match (quote ,in-pattern) ,expr ,(list))))
(if (not (eq ,bindings 'match-fail))
(apply-bindings (quote ,out-pattern) ,bindings)
'match-fail))))



Now we can conveniently use our make-transformer macro to define your example transformations:


(defun example1 (expr)
"(a*b)/c -> a*b*(1/c) "
(make-transformer (/ (* a b) c)
(* a b (/ 1 c))
expr))


(defun example2 (expr)
"(a*b)/c -> (a/c)*(b/c)"
(make-transformer (/ (* a b) c)
(* (/ a c) (/ b c))
expr))

(defun example3 (expr)
"(a+b)/c -> (a/c)+(b/c)"
(make-transformer (/ (+ a b) c)
(+ (/ a c) (/ b c))
expr))



Let's test it:


[100]> (example1 '(/ (* 1 2) 3))
(* 1 2 (/ 1 3))

[101]> (example2 '(/ (* 1 2) 3))
(* (/ 1 3) (/ 2 3))

[102]> (example3 '(/ (+ 1 2) 3))
(+ (/ 1 3) (/ 2 3))

[103]> (example3 '(/ (* 1 2) 3))
MATCH-FAIL

Share this post


Link to post
Share on other sites
Wow. That looks pretty cool. Except I don't understand OCaml. [wink]

Can you give me a quick rundown of what that code is doing?

Also - I see that F# is a Microsoft thing, which is most likely a good thing.

A related question. Can I use F# (or L#) in combination with the Express Edition of Visual C#?


(edit: I wrote the above before reading the AP who just posted. I'll read that now.)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Andrew, if you're interested in F# you might want to take a look at two channel9 videos where the ms researcher Don Syme talks about and demonstrates F# which targets the CLR:
http://channel9.msdn.com/Showpost.aspx?postid=234889
This is part 2 where F# is demoed inside visual studio 2005.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
AP: That Lisp-magic looks pretty damn awesome. Would it handle cases 4 and 5, though? (I'm not Lispy enough to work it out )


Sure, if you tell it to. I'm a bit busy now, but here's case 4 as an appetizer (I rushed this so it's probably not the best way to do it. Using eval directly is usually unwise).

We need to make these two changes:


(defun eval-marked (expr)
"This walks the code and evaluates the chunks that are prefixed with the
:eval keyword we use to mark the chunks we want to evaluate. "
(cond ((and (consp expr) (eq :eval (car expr)))
(eval (cadr expr)))
((consp expr)
(cons (eval-marked (car expr)) (eval-marked (cdr expr))))
(t expr)))

(defmacro make-transformer (in-pattern out-pattern expr)
"A modified make-transformer macro: now it understands the :eval command
in the output pattern."
(let ((bindings (gensym)))
`(let ((,bindings (pattern-match (quote ,in-pattern) ,expr ,(list))))
(if (not (eq ,bindings 'match-fail))
(eval-marked (apply-bindings (quote ,out-pattern) ,bindings))
'match-fail))))




Now, let's attack your example 4 and another one for example's sake:


(defun example4 (expr)
"(a*b)/n -> a*b*{evaluate 1/n}"
(make-transformer (/ (* a b) n)
(* a b (:eval (/ 1 n)))
expr))

(defun example6 (expr)
"(a*b) + c -> ( (evaluate a*b) + c)"
(make-transformer (+ (* a b) c)
(+ (:eval (* a b)) c)
expr))




Let's check:


[27]> (example4 '(/ (* 2 3) 4))
(* 2 3 1/4)
[28]> (example6 '(+ (* 2 3) 4))
(+ 6 4)
[29]>



Perfectly fine (* in lisp takes any number of arguments).

Share this post


Link to post
Share on other sites
AP #1: Well, I'm reasonably keen on Lisp now. Those examples were great, thanks [smile].

AP #2: I just watched my first Channel 9 video about 24h ago and it was pretty awesome. I'll have to leave those until tomorrow to view - hopefully they'll be just as great.

On the subject of .NET versions, does anyone have any experience with L#?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!