• Advertisement

# Tree Manipulation Language

This topic is 4174 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

##### 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

##### Share on other sites
Quote:
 Original post by ToohrVykAny 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

##### Share on other sites
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

##### 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

##### Share on other sites
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 [wink])

#### Share this post

##### Share on other sites
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

##### Share on other sites
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

##### 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

##### Share on other sites
wow.. so this is the legendary lisp programmer i have heard say about.

#### Share this post

##### Share on other sites
I had written a rudimentary recursive parser to build TeX linguistics trees out of simple bracketed trees, like (root (node) (node) (root (node))). I don't think I ever got much further than it, but I could've probably turned it into a language.

#### Share this post

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

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.

Last time I checked, this guy was still impressive. I don't know what he can't do on the top of his head (well... maybe moving real-life objects, although I'm not even sure about that).

#### Share this post

##### Share on other sites
Quote:
 Original post by DaeraxDid 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.

I'm a Caml Light teacher, so I find myself writing that kind of things on a white board every so often (as well as debugging my students' programs off the top of my head, too). I also write more O'Caml code than C/C++/C# code (and more PHP/LaTeX than O'Caml, but that's another matter).

#### Share this post

##### Share on other sites
You might want to look into buying "ANSI Common Lisp"(ISBN: 0133708756) as it includes as an example a pretty complex pattern matching system. It uses it to provide a relational logic language ("M is-mother-of C" implies "C is-child-of M" type of stuff), but the way it handles things (IIRC) should make it fairly easy to build up a formalization of mathematics on top (math formalization does start with basic logic, after all =-)

-Extrarius

#### Share this post

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

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.

Last time I checked, this guy was still impressive. I don't know what he can't do on the top of his head (well... maybe moving real-life objects, although I'm not even sure about that).

well im sure he could easily move objects on the top of his head hehe. [grin] but yeah him, that anonymous poster, zahlman and snk_kid ( <- used to) constantly write amazing bits of code on the forums on the go, that just made you go wow. for a lack of words.

Quote:
 Original post by Anonymous PosterYou might want to look into buying "ANSI Common Lisp"(ISBN: 0133708756) as it includes as an example a pretty complex pattern matching system. It uses it to provide a relational logic language ("M is-mother-of C" implies "C is-child-of M" type of stuff), but the way it handles things (IIRC) should make it fairly easy to build up a formalization of mathematics on top (math formalization does start with basic logic, after all =-)-Extrarius

There is a way that is many, many orders of magnitudes better than this. The method you are espousing would quickly get bogged down in semantics and become impossible to work with least of all verify, as it would become more and more specific and hardcoded. As well it would be exponentially difficult to extend. You know of metamath. that way is one way, another way is to do it constructively in a strongly typed lambda calculus whose termination assures that the proof is correct.

#### Share this post

##### Share on other sites
Quote:
 AP #1: Well, I'm reasonably keen on Lisp now. Those examples were great, thanks .
Here's another example of a cool thing that lisp is especially good at: molding itself to what you want to do. Maybe it'll make you keener. ;)

I've thought about this and I'm growing increasingly envious of the ML pattern matching syntax based on destructuring types by their type constructors. It's extremely convenient for manipulating tree structures.

Haskellers and ML'ers are rightly smug about it. So we lispers might either

a) sneer and say it isn't that cool anyway or

b) bow deeply to those guys and steal everything that isn't nailed down in ML.

I'm going with option b.

Of course, we don't have invertible type constructors for all types in lisp, and we don't necessarily want to go through the hassle of having them (sometimes dynamicity is good). So we'll go a slightly different route: we'll pattern match against a pattern and then filter the bindings through some (optional) predicates. These can be type predicates (providing the functionality of ML patterns) or arbitrary predicates.

We want to be able to write the famous haskell factorial or map:

fac :: Integer -> Integerfac 0 = 1fac n | n > 0 = n * fac (n-1)map                     :: (a->b) -> [a] -> map f  []               =  []map f (x:xs)            =  f x : map f xs

in a similar way. So we want syntax, let's call it defun-matcher, that takes a name and an arbitrary number of pattern-predicate-expression tuples and turns them into a common lisp function with the same name that has the desired behaviour. The fac and map functions above might look like this:

(defun-matcher  ((fact 0) (t) 1)  ((fact n) ((numberp n) (> n 0)) (* n (fact (- n 1)))))(defun-matcher   ((my-map f nil) (t) nil)  ((my-map f (x . xs)) (t) (cons (funcall f x) (my-map f xs))))

More parentheses, but it's equally beautiful once you look past them.

We need some medium macrology to accomplish this: we have to unfold a pattern into code that matches that pattern, and this is tougher than recursively matching bindings because we have to know whether a pattern variable has been bound or not 'previously'. 'Previously' means we have to impose an ordering on how we flatten the pattern into code that matches it; we didn't have to worry about that before.

We can use tyhe recursive approach we used for the previous pattern matcher as long as we remember to pass along the variables that have yet to be bound into each recursive branch (while knowing their relative ordering when the pattern is unfolded into code). Then the code will know whether to check a variable against a previous binding or whether to bind it directly and move on. I'm no Paul Graham, so we'll restrict ourselves to matching against lists only.

#### Share this post

##### Share on other sites
Here're a few functions we need first: the predicates to check whether something is a pattern variable or a quoted expression, a function that extracts a list of variables from patterns, and a function that returns the variables in the first pattern that are not in the second pattern. We'll need the last two functions to keep track of which variables have not been given bindings yet during the creation of the matcher code.

(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)  (and (consp pattern) (eq 'quote (car pattern))))(defun get-vars (tree)  "returns a list of all variables in a pattern (save those escaped by a quote)."  (cond ((and (consp tree) (eq 'quote (car tree)))	 (list))	((consp tree)	 (append (get-vars (car tree)) (get-vars (cdr tree))))	((var-p tree)	 (list tree))	(t (list))))(defun var-difference (pattern1 pattern2)  (set-difference (get-vars pattern1) (get-vars pattern2)))

Here's the matcher-code generator, which turns a pattern into code that matches it and binds the pattern variables in it. We also pass it an identifier for an expression (which it'll match against) an inner-form (which it will place inside the bindings so it can be evaluated within them). It must know which variables are as yet unbound, so as to bind them instead of comparing them to their (nonexistent!) binding.

It looks scarier than it actually is: for you non-lispers, the code that is preceded by a backquote is just a code template that is returned (this function generates code, after all), it isn't part of the logic in the function and isn't actually doing anything.

(defun make-matcher (pattern expr unbound-vars inner-form)  (let ((right-branch (gensym)))    (cond ((var-p pattern)	   (if (member pattern unbound-vars)	     (let ((,pattern ,expr))		,inner-form)	     (if (equalp ,pattern ,expr)		,inner-form)))	  ((and (consp pattern) (eq 'quote (car pattern)))	   (if (equalp ,pattern ,expr)	      ,inner-form))	  ((consp pattern)	   (destructuring-bind (pattern1 . pattern2) pattern	     (let ((inner-unbound (var-difference pattern2 pattern1)))	       (if (consp ,expr)		  (let ((,expr (car ,expr)) (,right-branch (cdr ,expr))) 		    ,(make-matcher pattern1 expr unbound-vars 				   (make-matcher pattern2 right-branch inner-unbound inner-form)))))))	  ((eq pattern '_)	   inner-form)	  (t 	    (if (equalp (quote ,pattern) ,expr)	       ,inner-form)))))

Now, this only destructures a pattern and fails if the pattern doesn't match. We also wanted to fail if the generated bindings didn't satisfy some arbitrary predicates, remember?

And we also want a function that puts this all together: one we can call with the symbol the expression to be matched will be initially bound to and with a list of pattern-guard-form tuples. This function will set things up so that the matcher works as expected: trying to satify the patterns and guards in order, and evaluating and returning the form in the first successful match.

(defun make-guarded-matcher (in-pattern guards form expr-symbol)  (let ((inner-form (if (and ,@guards) (return-from successful-match ,form))))     (make-matcher in-pattern expr-symbol (get-vars in-pattern) inner-form)))(defun single-matcher (expr-symbol pattern-guard-forms)  (let ((guarded-matchers (loop for p-g-f in pattern-guard-forms				collect (destructuring-bind (pattern guards form) p-g-f					      (make-guarded-matcher pattern guards form expr-symbol)))))    (block successful-match	    (progn ,@guarded-matchers))))

#### Share this post

##### Share on other sites
We now have a function that can turn lists of pattern-guard-form tuples into the code to match and execute the first successful match. But we wanted to be able to define functions, and these can take more than one argument (each argument can be a pattern). Fortunately, it is just a matter of transforming the pattern-function syntax into pattern-guard-form tuples , which we already know how to deal with.

None of this code is particularly pretty (I'm pressed for time) and this is the ugliest bt, but also the simplest: the hard work is behind us.

(defun check-fn-arity (fns-args)  (destructuring-bind (name-args . therest) fns-args    (let ((arity+1 (length name-args))	  (name (car name-args)))      (loop for function-args in therest do	    (if (or (not (eq name (car function-args))) 		    (not (= arity+1 (length function-args))))	      (error "name or arity mismatch in a pattern-match defined function")))      (cons name (- arity+1 1)))))(defmacro defun-matcher (&rest name-pattern-guard-forms)  (let* ((expr-symbol (gensym))	 (function-args (mapcar #'car name-pattern-guard-forms))	 (name-arity (check-fn-arity function-args))	 (pattern-guard-forms (mapcar (lambda (n-p-g-f) 					(destructuring-bind ((name . args) . g-f) n-p-g-f					  (cons args g-f))) 				      name-pattern-guard-forms)))      (let ((args (loop for x from 1 to (cdr name-arity) collect (gensym))))	(defun ,(car name-arity) ,args	   (let ((,expr-symbol (list ,@args)))	     ,(single-matcher expr-symbol pattern-guard-forms))))))

Whoopee! We're done.

Let's see what code is actually generated when we write down those beautiful, concise pattern function definitions:

[122]> (macroexpand-1 '(defun-matcher  ((fact 0) (t) 1)  ((fact n) ((numberp n) (> n 0)) (* n (fact (- n 1))))))(DEFUN FACT (#:G3372) (LET ((#:G3371 (LIST #:G3372)))  (BLOCK SUCCESSFUL-MATCH   (PROGN    (IF (CONSP #:G3371)     (LET ((#:G3371 (CAR #:G3371)) (#:G3373 (CDR #:G3371)))      (IF (EQUALP '0 #:G3371)       (IF (EQUALP 'NIL #:G3373)        (IF (AND T) (RETURN-FROM SUCCESSFUL-MATCH 1))))))    (IF (CONSP #:G3371)     (LET ((#:G3371 (CAR #:G3371)) (#:G3376 (CDR #:G3371)))      (LET ((N #:G3371))       (IF (EQUALP 'NIL #:G3376)        (IF (AND (NUMBERP N) (> N 0))         (RETURN-FROM SUCCESSFUL-MATCH (* N (FACT (- N 1))))))))))))) ;T

And for my-matcher:

[123]> (macroexpand-1 '(defun-matcher  ((my-map f nil) (t) nil)  ((my-map f (x . xs)) (t) (cons (funcall f x) (my-map f xs)))))(DEFUN MY-MAP (#:G3380 #:G3381) (LET ((#:G3379 (LIST #:G3380 #:G3381)))  (BLOCK SUCCESSFUL-MATCH   (PROGN    (IF (CONSP #:G3379)     (LET ((#:G3379 (CAR #:G3379)) (#:G3382 (CDR #:G3379)))      (LET ((F #:G3379))       (IF (CONSP #:G3382)        (LET ((#:G3382 (CAR #:G3382)) (#:G3383 (CDR #:G3382)))         (IF (EQUALP 'NIL #:G3382)          (IF (EQUALP 'NIL #:G3383)           (IF (AND T) (RETURN-FROM SUCCESSFUL-MATCH NIL)))))))))    (IF (CONSP #:G3379)     (LET ((#:G3379 (CAR #:G3379)) (#:G3387 (CDR #:G3379)))      (LET ((F #:G3379))       (IF (CONSP #:G3387)        (LET ((#:G3387 (CAR #:G3387)) (#:G3388 (CDR #:G3387)))         (IF (CONSP #:G3387)          (LET ((#:G3387 (CAR #:G3387)) (#:G3390 (CDR #:G3387)))           (LET ((X #:G3387))            (LET ((XS #:G3390))             (IF (EQUALP 'NIL #:G3388)              (IF (AND T)               (RETURN-FROM SUCCESSFUL-MATCH                (CONS (FUNCALL F X) (MY-MAP F XS)))))))))))))))))) ;T[124]>

Isn't it a relief we can get lisp to write that instead of having to do it ourselves? And it's bulky but pretty efficient: it stops looking as soon as it discovers it can't match the pattern.

#### Share this post

##### Share on other sites
Now, this code is almost certainly buggy and far from pretty. I only tested it on the fact and my-map examples (which surprisingly seem to work):

[124]> (fact 3)6[125]> (my-map (lambda (x) (* x x)) (list 1 2 3 4 5))(1 4 9 16 25)[126]>

But it's VERY little work for what it does (extend lisp syntax to comfortably express functions in terms of patterns and predicates they must match). Suddenly you have syntax that is almost as pretty as Haskell pattern-match function definitions, and it takes only a few hours to extend your language!

And I feel very flattered at being called legendary, but I'm actually a beginner at lisp (been writing it for a little over two years, on and off) and I've forgotten the languages I thought I 'knew' before (I'm starting to realize I didn't know them at all).

The point is that some things that are unthinkably hard in other languages are very easy in lisp; writing this requires no extraordinary ability, just the right language. Lisp is very well suited to this sort of thing, and I like the practice :)

#### Share this post

##### Share on other sites
Quote:
 Original post by Anonymous PosterAnd I feel very flattered at being called legendary, but I'm actually a beginner at lisp

Woah.

Well, it seems like I'm going to need to learn Lisp anyway - just to fully appreciate that code.

If no one can point me in an even better direction, I'm going to go for Lisp on this project. Cheers [smile]

#### Share this post

##### Share on other sites
Quote:
Original post by Andrew Russell
Quote:
 Original post by Anonymous PosterAnd I feel very flattered at being called legendary, but I'm actually a beginner at lisp

Woah.

Well, it seems like I'm going to need to learn Lisp anyway - just to fully appreciate that code.

If no one can point me in an even better direction, I'm going to go for Lisp on this project. Cheers [smile]

wtf, taking the meaning of the word beginner to another level.

Anyways as the L AP stated, the pattern matching syntax of the ML languages are far superior to Lisp's and will certainly make your task easier and more mentally palapable. However, the meta capabilities of Lisp will make it trivial to create a special syntax most suited for your problem domain. You might want to take a view at Nemerle which strikes a balance between the two and is also a member of the curly brace (or optionally, indentation) family of syntax.

#### Share this post

##### Share on other sites
Different non-Godlike ap here:

nemerle is dead sexy. Plus P. Grahams is free now:

http://www.paulgraham.com/onlisptext.html

#### Share this post

##### Share on other sites
Quote:
 Original post by Daerax[...]There is a way that is many, many orders of magnitudes better than this. The method you are espousing would quickly get bogged down in semantics and become impossible to work with least of all verify, as it would become more and more specific and hardcoded. As well it would be exponentially difficult to extend. You know of metamath. that way is one way, another way is to do it constructively in a strongly typed lambda calculus whose termination assures that the proof is correct.
MetaMath is not a tree manipulation language. It does nothing more replace identifiers with strings to build new strings. I'm 99% certain that it isn't turing complete, since it does not provide a method to replace strings (so strings can be expanded, but not contracted).

#### Share this post

##### Share on other sites
Quote:
Original post by Extrarius
Quote:
 Original post by Daerax[...]There is a way that is many, many orders of magnitudes better than this. The method you are espousing would quickly get bogged down in semantics and become impossible to work with least of all verify, as it would become more and more specific and hardcoded. As well it would be exponentially difficult to extend. You know of metamath. that way is one way, another way is to do it constructively in a strongly typed lambda calculus whose termination assures that the proof is correct.
MetaMath is not a tree manipulation language. It does nothing more replace identifiers with strings to build new strings. I'm 99% certain that it isn't turing complete, since it does not provide a method to replace strings (so strings can be expanded, but not contracted).

Oh right, I know that but your post was confusing since it didnt read, to me, like it had much to do with tree manipulation. You said:
Quote:
 You might want to look into buying "ANSI Common Lisp"(ISBN: 0133708756) as it includes as an example a pretty complex pattern matching system. It uses it to provide a relational logic language ("M is-mother-of C" implies "C is-child-of M" type of stuff), but the way it handles things (IIRC) should make it fairly easy to build up a formalization of mathematics on top (math formalization does start with basic logic, after all =-)

And I was simply noting that such a method is not that most fruitful of ways to approach the formailization of mathematics which has nothing to do with the original tree manipulation post. As well the pattern matching of MLs, orginally created for proof theoretic reasons is much more powerful (do not overestimate succintity).

Yeah, Metamath is not turing complete since it does no computations (that is its beauty) but can easily be extended so.

---

but to remain ontopic I will resuggest Nemerle which has the pattern matching capabilities of an ML but also the metabilities of a Lisp.

#### Share this post

##### Share on other sites
Quote:
 Original post by Daerax[...]And I was simply noting that such a method is not that most fruitful of ways to approach the formailization of mathematics which has nothing to do with the original tree manipulation post. As well the pattern matching of MLs, orginally created for proof theoretic reasons is much more powerful (do not overestimate succintity).Yeah, Metamath is not turing complete since it does no computations (that is its beauty) but can easily be extended so.---but to remain ontopic I will resuggest Nemerle which has the pattern matching capabilities of an ML but also the metabilities of a Lisp.
The part of importance was the pattern matching, which is exactly what is needed to tree manipulation. I just mentioned that it wasn't designed for the purpose of direct tree manipulation, but even without modification, it could be used as such in a contrived kind of way (inference engines are far stronger than 'metamath's language, and perform tree manipulation as a main function)

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement
• ### Popular Tags

• Advertisement
• ### Popular Now

• 45
• 11
• 17
• 11
• 13
• Advertisement