Sign in to follow this  

Unity Algorithm for transforming equations

This topic is 4196 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 want to be able to transform equations so that they are as computationally cheap as possible. So given a set of rules (a*n + a = a*(n+1), a*n + a*m = a*(n+m), etc.), a set of operators and their computational cost, and an equation. The algorithm should be able to transform the equation using the rules to the cheapest possible equation with the same semantics (assuming all rules are correct). For a simple example imagine the following
R = { a*b=b*a,  a*b + a*c = a*(b+c) }
C = {a+b = 3,  a*b = 7}
E = a*3 + 2*b
Of course R is the set of rules, C is the set of costs and E is the equation. Here the algorithm would somehow find out that the best representation would be:
E = a * (3+2)
Because the cost would be: 7+3 = 10, where the cost of the original equation would be: 7+3+7 = 17. So does anyone know of an algorithm capable of doing this? Brute force is not an option, and I would like the algorithm to stay at O(n²) or lower, but if there exist no such thing I can do with algorithms with worse complexity. If I can reduce the complexity by using an algorithm which didn’t always produced perfect results that would also be good. I don’t need the data to be in any kind of data structure, so I don’t care if the algorithm wants the rules in a black-red tree with the costs being the keys, or if the algorithm wanted a circular linked list. EDIT: I can see this might seem like school work, but it's not. In a recent thread I saw some quite surprising assembly from a modern compiler, and as Jan Wassenberg points out, the assembly is actually quite bad. Therefore I chose to do some research in this kind of stuff, just to see where the problems really are.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sharlin
Dynamic programming will probably help keeping the time complexity acceptable. Basically, the idea is to cache (or memoize) intermediate results, so that overlapping subproblems will only get calculated once.


Thanks, I believe that can cut down the processing time quite a lot. I doubt it will change the actual complexity though.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This is not a simple problem. Depending on your rewrite rules and initial expression, in this case:

R = { a*b=b*a, a*b + a*c = a*(b+c) }
E = a*3 + 2*b

it is entirely possible that the set of expressions that can be generated using the rewrite rules and are equivalent to your initial expression is infinite. That is, an algorithm enumerating them would not halt, so no optimum algorithm exists to solve the general case.

This means you'd have to use heuristics to search some finite subset for the best solutions.

Symbolic algebra systems like Macsyma and Maple do the same stuff, only they have heuristics to find the most convenient representation (for example, 3*x is more convenient than x + x + x).

Are you familiar with the concept of syntactic unification?

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Depending on your rewrite rules and initial expression, in this case:

R = { a*b=b*a, a*b + a*c = a*(b+c) }
E = a*3 + 2*b

it is entirely possible that the set of expressions that can be generated using the rewrite rules and are equivalent to your initial expression is infinite. That is, an algorithm enumerating them would not halt, so no optimum algorithm exists to solve the general case.

I thought the set of costs could help to construct a finite number of combinations of rules, where these combinations would be the only way to decrease the cost. Well honestly I don't have enough understanding of the problem, so I'll just choose to believe that the general case is impossible to solve for now.

Quote:
This means you'd have to use heuristics to search some finite subset for the best solutions.

Symbolic algebra systems like Macsyma and Maple do the same stuff, only they have heuristics to find the most convenient representation (for example, 3*x is more convenient than x + x + x).

I though it might be necessary to do something like this.

Quote:
Are you familiar with the concept of syntactic unification?

No, but I'm willing to read about it. To be honest I wouldn't mind reading 10 books to get a better understanding of the problem, it would just mean I had learned more in the end. So, I'll go read about syntactic unification now. I would really appreciate links to some articles or books which might give me some additional information about the problem (even if they assume knowledge of syntactic unification).

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
it is entirely possible that the set of expressions that can be generated using the rewrite rules and are equivalent to your initial expression is infinite. That is, an algorithm enumerating them would not halt, so no optimum algorithm exists to solve the general case.


Indeed. This is an interesting problem. You can't straightforwardly prune branches that yield expressions more costly than the original, because they might *eventually* lead to cheaper solutions. But you *must* somehow cap the cost, otherwise the search will happily generate expressions such as original + 0 + 0 + 0 + 0 + 0 + 0 + 0, ad infinitum.

It also occurred to me that because the search space is an arbitrary graph, you *have* to keep track of opened nodes, lest you end up with an infinite loop. So memoization is pretty much a requirement, not just an optimization.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:

I thought the set of costs could help to construct a finite number of combinations of rules, where these combinations would be the only way to decrease the cost.
Heh, that's a standard optimization called hill-climbing, only it requires that you can always go in the direction of decreasing cost. In other words, your cost function must be monotonic, without local minima.

Unfortunately, this problem is too complicated: you can't devise an algorithm that can guarantee to find the best expression in this way.

Quote:

No, but I'm willing to read about it. To be honest I wouldn't mind reading 10 books to get a better understanding of the problem, it would just mean I had learned more in the end.


An excellent (and hands-on!) introduction is found in SICP:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_sec_4.4

Unification is a generalisation of pattern matching. It's hard to explain simply without getting into details, but it's what you intuitively do when noticing that, given these two equations:

x + y = z
x + 2 = z

you can deduce (by looking at the syntax only!) that y = 2 is consistent with both equations.

If you don't know scheme, it might be worth it to learn it for tackling this problem, because scheme is:

1) Laughably easy syntax; you can pick it up in a day.

2) Very well suited for representing and manipulating symbolic expressions.

You are likely to be scared off if you just go link-hunting: unification can get exceedingly technical in a rigorous mathematical formalization.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Here's the way you might start attacking the problem:

1) Write a unification algorithm for your expression syntax. This is pretty simple if you've got a convenient data representation for your expressions; I'd use scheme or Common Lisp, because I've written unifiers in them and know it is simple from experience. Symbolic manipulation is one of lisps' strengths.

2) Your rewrite rules are transitions from one expression to another. That is, a rule looks like:

E0 -> E1

for example

x*y + 2 -> y*x + 1 + 1

or

0*x -> 0

where E0 is an expression containing variables and constants and E1 is another expression containing the same variables (or not, but certainly no NEW variables) that is equivalent to E0. Let's call E0 the head of the rule, and E1 the result.

So given an expression E, if E can be unified with a rule's head, it is equivalent to that rule's tail with the variables adequately substituted. (There may be more than one way to unify two expressions).

So you get a set of expressions that are reachable in one step from your original E expression and your set R of rewrite rules.

Of course, you can apply your rewrite rules to this new set of expressions too, yielding more equivalent expressions.

This yields a (potentially infinite) directed graph of the expressions that are syntactically derivable using your rewrite rules.

Now comes the hard part: how to search that potentially infinite expression graph for good expressions? You can apply genetic algorithms or simulated annealing as the poster above mentioned, A* with a heuristic of your own, simple breadth first search, symmetry pruning...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Thanks a lot, if I could I would rate you up.
I'm glad I could help.

Be advised, these concepts are not simple, and understanding them takes sweat and hard work.

I'd be happy to walk you through writing the expression representation and the unification algorithm at least: it's fun and doing this sort of thing keeps me on my mental toes. So if you want to see how this sort of thing is done and don't mind using lisp or scheme, I'll post a step-by-step description of how to do this in lisp or scheme.

Just say the word.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
I'd be happy to walk you through writing the expression representation and the unification algorithm at least: it's fun and doing this sort of thing keeps me on my mental toes. So if you want to see how this sort of thing is done and don't mind using lisp or scheme, I'll post a step-by-step description of how to do this in lisp or scheme.

Just say the word.


If you want to help with a step-by-step description, I would really appreciate it. I don't mind you using lisp or scheme, or any other language for that matter, learning the syntax of a language doesn't take long and the Lisp variants are often easy to learn.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Okay. :)

There are a few things we should be clear about before diving in:

1) That two mathematical expressions are theoretically equivalent doesn't mean they'll give the same answer when a computer calculates them, unfortunately. The whole field of numerical analysis is dedicated to finding ways to write an expression so that numerical error propagation is not catastrophic.

So this is a nice exercise, but to make this practically useful, error propagation must be taken into account, and good programmers usually write mathematical expressions with error propagation in mind, so rearranging them might not always be what the programmer wants.

2) If I tried to explain every concept we'd be here forever, so I'll provide links to concepts I think are explained better elsewhere.

3) I'll probably make mistakes, so try to find them. Give me as much feedback as possible for every post, and ask about what you don't understand; writing a monologue is not fun.

4) If real life intervenes, I might disappear for a few days at a time, depending on how busy I am. I'll try to get the first post with actual content done today before I head for the bars.

---------------------------------------------------------

The first part of the problem is: given an expression and some rewrite rules, figure out how to generate equivalent expressions using the rewrite rules, and be sure you're actually doing this correctly and not screwing up.

1) First we have to choose a representation for our mathematical expressions. Choosing a convenient representation is not as easy as one may think, and it must be done carefully and rigorously.

2) Next we have to choose a representation for our rewrite rules.

3) We have to think about what applying a rewrite rule to an expression *means*. We have to find an algorithm that applies a given rewrite rule to an expression in every possible way that makes sense. I've been thinking about this, and fortunately I think we can get away with a simple pattern matching algorithm: the full generality of unification is not needed, because expressions cannot contain pattern variables. But I'll leave this for much later.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Choosing a representation for our expressions part 1:

First we have to decide WHAT we're actually trying to represent. We are talking about the expressions to the left of an assignment, like*:

3 + 6*y

in

x := 3 + 6*y

What do we need to bear in mind? Not the colon-equal sign, because it doesn't really mean equality here but assignment, and is not part of the actual expression which we want to rewrite.

We DO have to bear in mind the algebraic operators. Let's limit ourselves to *, +, /, and -. We can always add more later.

We have to have parentheses, like (4 + 5)*z.

We also have to bear in mind what those operators act upon: constants like 6 and variable identifiers like y.

So we know intuitively that the expressions we want to represent are like 4 + 5 or (x + y) / 5 . We have to formalize this intuition so that we can write code that manipulates these expressions as data structures.

---------------------------------------------------------------------------------------

So we have to first clarify and formalize our syntactic representation: only then can we start to code it.

We already know of one possible syntactic representation: the typical math notation we learn in school**. Indeed,

(x + y) / 5

or

4 - 9

are written in that form. We know that these expressions:

+3++/

or

)(-7**(6()

are nonsense, even though they use the symbols that are used in math notation. So we need a formal way to specify the rules in a given syntax, rules that tell us what the valid expressions are and what expressions are nonsense.

How do we formally specify and reason about syntax rules? Thank god that Backus and Naur already solved that problem for us, because it is thorny. We turn to Backus and Naur and ask them for help:

http://www.cs.man.ac.uk/~pjj/bnf/bnf.html

http://en.wikipedia.org/wiki/Backus-Naur_form

It is important that you understand this before we move on. Don't be ashamed to ask questions: again, these are difficult concepts. Invent a few BNF grammars and see how they work using pen and paper to get a feel for them.




* I'm using := to represent assignment instead of = to distinguish assignment from actual equality.

**We will use another representation, because traditional infix algebra notation is (relatively) complicated to formalize as BNF rules. We'll use a BNF representation that is so simple you won't believe it at first.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
How do we formally specify and reason about syntax rules?

Ok, this doesn't seem so hard. You mention we won't be using the infix notation, but I tried to create a set of rules for it anyway

digit ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"
char ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"

number ::= <digit> | <number> <digit>
string ::= <char> | <string> <char>

operator ::= "+" | "-" | "/" | "*"
constant ::= <number>
variable ::= <string>
operand ::= <constant> | <variable>

expression ::= <operand> |
"(" <expression> ")" |
<expression> <operator> <expression>
assignment ::= <variable> ":=" <expression>





I also tried to create a simple grammar for a Lisp like system (prefix), most is still the same only assignment and expression is changed and operand_expression_list is added.

digit ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"
char ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"

number ::= <digit> | <number> <digit>
string ::= <char> | <string> <char>

operator ::= "+" | "-" | "/" | "*"
constant ::= <number>
variable ::= <string>
operand ::= <constant> | <variable>

operand_expression_list ::=
<operand> |
<expression> |
<operand_expression_list> " " <operand> |
<operand_expression_list> " " <expression>

expression ::= operand | "(" <operator> " " <operand_expression_list> ")"
assignment ::= "(" "define" <variable> <expression> ")"





I believe both representations are about correct, I haven't verified it in any way though.

I have ignored whitespace since I can't see it doing anything but complicating the algorithm.

[Edited by - CTar on June 16, 2006 3:21:12 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Excellent. I see you are a very quick learner. Quicker than me at least. I'll pick up the pace.

The disadvantage I see with infix notation is threefold:

1) Operator precedence rules must be codified into the BNF grammar if one wants a unique parse tree for every expression (a unique meaning). This is a pain because one is forced to mix syntax with semantics, and it makes the BNF more complicated.

Of course, if one is forced to use parentheses to mark operation precedence in infix notation, the readability advantage of prefix notation is negated.

2) The left-recursiveness of math notation must be worked around if one wants to implement a recursive descent parser. This is also a pain.

3) If we're using lisp and represent expressions in prefix notation, we get an evaluator for our expression representation for free!

Quote:

I believe both representations are about correct, I haven't verified it in any way though.
I'll take your word for it. :)

I see you are already familiar with lisp or scheme. That's great.

I realize that you wrote the BNF lisp forms there for a quick examples' sake. But for anyone else reading this, you should be aware that define in scheme is a binding construct, not an assignment operator. For the language lawyers, this means that define binds a name to a value cell while set! (the assignment operator) mutates the value in a bound name's value cell. That's why you can get unboundname errors using set!.

Also, this means that define's binding only extends within its enclosing lexical scope while set! actually modifies the value in the value cell bound to the name, which does have important consequences. For example:


(define *x* 5)

(define (test-binding)
(define *x* 3)
*x*)

(define (test-assignment)
(begin
(set! *x* 3)
*x*))

;here's the difference:

> *global-var*
5
> (test-binding)
3
> *global-var*
5
> (test-assignment)
3
> *global-var*
3



So if any scheme newbie is reading this, remember that define is a binding construct and not an assignment operator!

Anyway, have a fun friday night! I'll proceed tomorrow or sunday, depending. :)

Share this post


Link to post
Share on other sites
This is really interesting. I didn't know anything about lisp/scheme but they look useful.

But I'm not completely sure what you're working towards - Basically, a computer algebra system, right? But in this case you're taking into account the "cost" of each computation?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oh the irony. I posted to unconfuse possible scheme newbies and probably confused them all the more.

I changed the global variable name in my example from *x* to *global-var* for clarity, but forgot to change it in the function definitions.

I am terribly sorry, the example should read:


(define *global-var* 5)

(define (test-binding)
(define *global-var* 3)
*global-var*)

(define (test-assignment)
(begin
(set! *global-var* 3)
*global-var*))

;here's the difference:

> *global-var*
5
> (test-binding)
3
> *global-var*
5
> (test-assignment)
3
> *global-var*
3



Quote:

But I'm not completely sure what you're working towards - Basically, a computer algebra system, right? But in this case you're taking into account the "cost" of each computation?
Well, it's basically a computer algebra system where each expression has an associated cost, so that the computer can automatically transform expressions into equivalent, lower cost ones.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
So, one way to formalize our syntax is to write down the typical math syntax in BNF, but this is complicated: we'd have to introduce artificial terms in the BNF syntax to make each expression have one unique parse tree (one unique meaning). This is a headache, and conflates two issues: we'd be mixing the syntax specification with the semantics. And we would have to find a BNF syntax that is not left recursive.

So, why don't we follow the example of Lisp and use parenthesised prefix notation? We lose no generality (any expression that can be written in typical math syntax can be written in prefix syntax) and the BNF specification becomes laughably simple, letting us concentrate on the problem at hand. We can always write a prefix -> infix and infix -> prefix parser later if we need it.

We have the added advantage of writing our expression representations in a language that lisp already understands, so if we use lisp as an implementation language we wouldn't have to implement our own evaluator for our expression representation: we can just use lisp to do it for us!

So here's a simple BNF grammar for expressions using *, +, -, / in prefix notation :



<E> ::= <V> | <K> | <mul-expr> | <sum-expr> | <div-expr> | <sub-expr>

<mul-expr> ::= (* <E> <E>)

<sum-expr> ::= (+ <E> <E>)

<div-expr> ::= (/ <E> <E>)

<sub-expr> ::= (- <E> <E>)

<V> ::= x | y | z | t | s ....... (variable names)

<K> ::= 0 | 1 | 2 | 3 ...... (constants)




This says that the terminals in our grammar are either variables or constants, and that an expression is either a terminal or a multiplication, addition, division or subtraction of two expressions. It's also consistent with scheme syntax for the aforementioned operations.

I will use pattern matching in function definitions next, so read up on it if you're not familiar with it. I've decided to use Dr. Scheme (PLT mzscheme) as the implementation language.

http://en.wikipedia.org/wiki/Pattern_matching

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-29.html#%_idx_5176

http://download.plt-scheme.org/doc/103p1/pdf/match.pdf

http://www.codecomments.com/archive282-2004-8-252517.html

Unlike unification, it is a very straightforward concept. If you've ever used Haskell you know about it already.

For now we'll use it only for convenience to avoid tiresome nested if statements; later it will be an integral part of our expression rewriting algorithm, and we'll maybe write a pattern matcher ourselves to clarify the concept. It's simple.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Now, to code! The first thing we have to do is translate the BNF terms into Scheme data types, so we can actually manipulate them in scheme. We'll choose a Scheme representation for each BNF term, and we'll make a predicate function for each term that tells us whether a given scheme data object is an instance of that term type.

You will notice that the code used in each predicate is basically the BNF syntax. A direct translation.

We will include the pattern matching module in PLT mzscheme because it makes writing the operator predicates very straightforward:


(require (lib "match.ss"))



We will represent terminals of type K (numerical constants) using Scheme's number types: so any number Scheme recognizes is a valid K terminal. So the built-in predicate number? is all we need to tell if a term is a constant in our grammar:


(define constant? number?)



We will represent terminals of type V (variable identifiers) as symbols belonging to a set of predefined variable symbols. We'll store this set in the global variable *variable-names*:


(define *variable-names*
'(x y z s t q r))

(define (variable? var)
(if (member var *variable-names*)
#t
#f))



Now, the meat of the issue are the nonterminals of type mul-expr, sum-expr, etc. Just as the BNF definition of a given operator expression is recursive (operator expressions are defined in terms of expressions) the predicate for identifying them will be recursive. Let's make predicates for the *, /, + and - cases.

We represent these cases as lists of the form

( )

This common structure for these binary operators means we can abstract a function that makes predicates for a given binary operator. The function make-binary-operator-pred is a function that returns functions. We use that predicate-generating function to make predicates for the operators we'll use. This is the only nontrivial code written so far; the third link in my previous post is the documentation for the mzscheme pattern matcher, but check the fourth link for a simpler explanation:


(define (make-binary-operator-pred op-symbol)
(lambda (expr)
(match expr
((operator subexpr1 subexpr2)
(and (eq? operator op-symbol) (expression? subexpr1) (expression? subexpr2)))
(anything-else #f))))

(define mul-expr? (make-binary-operator-pred '*))
(define div-expr? (make-binary-operator-pred '/))
(define sum-expr? (make-binary-operator-pred '+))
(define sub-expr? (make-binary-operator-pred '-))



The predicate returned by make-binary-operator-pred is a function that tries to match its argument expr to the (operator subexpr1 subexpr2) pattern. If it matches, it ensures that operator is indeed the symbol that represents the operator the predicate recognizes (stored in op-symbol), and also ensures that subexpr1 and subexpr2 are valid subexpressions, by executing

(and (eq? operator op-symbol) (expression? subexpr1) (expression? subexpr2)).


anything-else is guaranteed to match anything at all. It works kind of like the else clause in a cond; in this case, I use it to mean that any pattern that is not matched by (operator subexpr1 subexpr2) is not a binary operation so the predicate should return false.

Now we can trivially define the expression? predicate, which looks exactly like the BNF definition for :


(define (expression? expr)
(or (constant? expr)
(variable? expr)
(mul-expr? expr)
(div-expr? expr)
(sum-expr? expr)
(sub-expr? expr)))



Notice that, given the BNF definition, we directly translated each nonterminal into scheme code.

These predicates allow us to validate an expressions' syntactical correctness. They also will allow us to dispatch control on expression type, which is what we need in order to manipulate symbolic expressions.

Let's test it:


> (expression? '(+ 3 (- 4 5)))
#t
> (expression? 5)
#t
> (expression? '(y))
#f
> (expression? '(+ y (- 4 5)))
#t
> (expression? '(+ e (- 4 5)))
#f
> (expression? '(b y (- 4 5)))
#f


Share this post


Link to post
Share on other sites
Ok, thanks for the replies. I think I have an idea of how make-binary-operator-pred works, could you please tell me if my following understanding is correct:

(match (operator subexpr1 subexpr2)

This gives the possible parameters inside the match.


(and (eq? operator op-symbol) (expression? subexpr1) (expression? subexpr2)))

This is the expression which has to be true for the match to be succesfull,if it isn't anything-else is called. It uses all of the parameters defined previosly. operator is passed to eq? (equal) together with op-symbol, so eq? checks if the first x chars match op-symbol, if it doesn't the match is unsuccessfull. Then the parser starts parsing data into subexpr1, as soon as the expression stops the parser moves on to subexpr2, which does the same as subexpr1. I'm wondering though, will we be able to use operator, subexpr1 and subexpr2 at a later time? If anything fails (anything because it's inside an and-expression) anything-else is called. Will these functions only be used for checking if the expressions are valid or will they also be used to create the actual representation of the expression?

One last question, is there a reason why you didn't just defined variable? like this?

(define (variable? var)
(member var *variable-names*) )

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hmm, introducing pattern matching for such a simple task was a bad idea. It is not parsing. I'll explain it later in detail anyway. It's only distracting you from the real issues at this point.

So forget pattern matching for now: we'll rewrite our mult-expr?, sum-expr?, etc. predicates using standard scheme, and look at pattern matching in depth later. Just forget everything you wrote down in the previous post. Forget I ever mentioned pattern matching.

According to our BNF formalism, operator expressions are of the form:

(operator subexpression1 subexpression2)

So, they are lists, and they are three elements long. So how would we write, say, mul-expr?

We have to check that the expression is a list, and that is three elements long. So any element must have this structure to be a mul-expr.

Furthermore, to be a mult-expr, the first element of this list, the car, must be a * symbol.
The second element of the list, the cadr, must be a valid expression.
The third element of the list, the caddr, must also be a valid expression.

If these conditions are met, then we have a valid mult-expr:


(define (mul-expr? expr)
(and (list? expr) (= 3 (length expr))
(eq? '* (car expr)) (expression? (cadr expr)) (expression? (caddr expr))))



Scheme's 'and' sequences comparisons from left to right and shortcuts evaluation: this is fortunate. If it didn't shortcut evaluation and we called mul-expr? like this, for example:

(mul-expr? 5)

the length function would throw an error because it can only be applied to lists. So would the car, cadr and caddr functions. In this case, the ordering of expressions inside the 'and' is very important!

Now, we know that all operator predicates are the same except for their operator symbol. So instead of duplicating a lot of code for each operator, we will write a function that makes operator predicates for the symbols one gives it, like we did before:


(define (make-binary-operator-pred op-symbol)
(lambda (expr)
(and (list? expr) (= 3 (length expr))
(eq? op-symbol (car expr)) (expression? (cadr expr)) (expression? (caddr expr)))))



Now we can make each operator predicate by calling the make-binary-operator-pred function with the appropriate symbol.

Down here is ALL THE CODE we have so far, so you don't have to hunt around for different code snippets and can cut and paste it all at once. Notice that it's surprisingly little code for a lot of functionality.

Instead of using match for the operator expressions we use this new approach I just described.


(define constant? number?)

(define *variable-names*
'(x y z s t q r))

(define (variable? var)
(if (member var *variable-names*)
#t
#f))

(define (make-binary-operator-pred op-symbol)
(lambda (expr)
(and (list? expr) (= 3 (length expr))
(eq? op-symbol (car expr)) (expression? (cadr expr)) (expression? (caddr expr)))))

(define mul-expr? (make-binary-operator-pred '*))
(define div-expr? (make-binary-operator-pred '/))
(define sum-expr? (make-binary-operator-pred '+))
(define sub-expr? (make-binary-operator-pred '-))

(define (expression? expr)
(or (constant? expr)
(variable? expr)
(mul-expr? expr)
(div-expr? expr)
(sum-expr? expr)
(sub-expr? expr)))



Oh, and how do you get monospaced font and preserve whitespace without using source tags? I tried using code tags once, but they didn't seem to work.

The rest of your questions will be answered in the next post.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Will these functions only be used for checking if the expressions are valid or will they also be used to create the actual representation of the expression?
The quickest way to create the actual representation of the expressions is to write them down directly, for example:

(* x (+ 4 y))

That is the actual representation of an expression in our expression language. :) Just try out our expression predicate in Dr. Scheme!:

(expression? '(* x (+ 4 y)))

So I'm not sure I understand your question. The predicates will allow us to carry out manipulations on expressions.

For example, imagine we want to change all multiplication operations to addition operations inside a given expression, but leave all other operations the same. This is simple (but a little cumbersome) once our predicates are defined:


(define (mul->sum expr)
(cond ((mul-expr? expr)
(list '+ (mul->sum (cadr expr)) (mul->sum (caddr expr))))
((div-expr? expr)
(list '/ (mul->sum (cadr expr)) (mul->sum (caddr expr))))
((sum-expr? expr)
(list '+ (mul->sum (cadr expr)) (mul->sum (caddr expr))))
((sub-expr? expr)
(list '- (mul->sum (cadr expr)) (mul->sum (caddr expr))))
((variable? expr) expr)
((constant? expr) expr)
(else (error "mul->sum was given an invalid expression:" expr))))

; an example interaction with the interpreter:

> (mul->sum 7)
7
> (mul->sum '(* 2 3))
(+ 2 3)
> (mul->sum '(* (* 1 2) (- x (/ y 4))))
(+ (+ 1 2) (- x (/ y 4)))
> (mul->sum '(f 1 2))
. mul->sum was given an invalid expression: (f 1 2)



This is nothing less than a rewrite rule! But it's pretty cumbersome and repetitive to write down. We might write it informally as:

(* a b) is rewritten as (+ a b)

Fortunately we can do something about that, but let's leave that for later.

Oh, and I hope you're cutting and pasting all this into Dr. Scheme and playing with it and writing your own experimental code snippets as we go along. :) The best way to learn is by experimenting yourself.

Homework: try writing a rewrite rule that flips expressions around in each op:

(op a b) is rewritten as (op b a)

Use the code above as a starting point.


Quote:

One last question, is there a reason why you didn't just defined variable? like this?
Yes. Functions ending with a question mark are predicates by convention in scheme, that is, functions that return either #t or #f. 'member' is not a predicate; it returns the sublist from the element onwards if the element is found in the list.

So someone reading my code might be disagreeably surprised if the variable? function, which convention says is supposed to be a predicate because of the question mark, starts spitting out lists instead of #t. It might break his code, because he didn't expect variable? to behave like that.

To avoid unexpected behavior, I make variable? behave as a predicate. Write code for the poor guy who will read it in mind, not for the compiler. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
The quickest way to create the actual representation of the expressions is to write them down directly, for example:

(* x (+ 4 y))

That is the actual representation of an expression in our expression language. :) Just try out our expression predicate in Dr. Scheme!:

(expression? '(* x (+ 4 y)))

So I'm not sure I understand your question. The predicates will allow us to carry out manipulations on expressions.

Sorry, bad habit from languages like C++. Didn't thought of an expression like something you actually can manipulate. I think I understand why you choose Scheme as your language. I can't imagine how much more work something like this would be in C.

Quote:
Oh, and I hope you're cutting and pasting all this into Dr. Scheme and playing with it and writing your own experimental code snippets as we go along. :) The best way to learn is by experimenting yourself.

Of course, actually I read your post and code, then I try to code it myself. This often catches a couple of things I didn't see in the code.

Quote:
Homework: try writing a rewrite rule that flips expressions around in each op:

(op a b) is rewritten as (op b a)

Use the code above as a starting point.


Homework? It starts feeling like school :) Well fun homework aren't bad anyway.
(define (compound-expr? expr)
(or (mul-expr? expr)
(div-expr? expr)
(sum-expr? expr)
(sub-expr? expr)))

(define (swap-operands expr)
(cond
(( compound-expr? expr)
(list (car expr) (swap-operands (caddr expr)) (swap-operands (cadr expr)) ) )
( (or (constant? expr) (variable? expr) )
expr)
(else (error "Illegal expr") )
)
)


And a simple test:

> (swap-operands '(+ 2 1) )
(+ 1 2)
> (swap-operands '(+ (* 2 (+ 5 1) ) 3) )
(+ 3 (* (+ 1 5) 2))


I assume you wanted the procudure to also flip all sub-expressions.

Share this post


Link to post
Share on other sites
This should really be written up in a paper/tutorial or something.

On a side note: Using scheme you seem to be able to construct the "classical" binary tree structure implicitly! (without nodes, links, etc). And to think I spent so much time doing the same thing........

Share this post


Link to post
Share on other sites

This topic is 4196 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Forum Statistics

    • Total Topics
      628738
    • Total Posts
      2984464
  • Similar Content

    • By INTwindwolf
      THE PROJECT

      INT is a 3D Sci-fi RPG with a strong emphasis on story, role playing, and innovative RPG features such as randomized companions. The focus is on the journey through a war-torn world with fast-paced combat against hordes of enemies. The player must accomplish quests like a traditional RPG, complete objectives, and meet lively crew members who will aid in the player's survival. Throughout the game you can side and complete missions through criminal cartels, and the two major combatants, the UCE and ACP, of the Interstellar Civil War.
      Please note that all of our current positions are remote work. You will not be required to travel.
      Talent Needed
       
      Unity Engine Programmer
      Website Administrator
      3D Animator
      We have made great strides in the year 2017! INT has received a comprehensive face-lift compared to the start of the year. We look forward to a productive, fruitful year 2018!
      Revenue-Share
      This is the perfect opportunity to get into the game development industry. Being an Indie team we do not have the creative restrictions often imposed by publishers or other third parties. We are extremely conscientious of our work and continuously uphold a high level of quality throughout our project.
      We are unable to offer wages or per-item payments at this time. However revenue-sharing from crowd-funding is offered to team members who contribute 15-20 hours per week to company projects, as well as maintain constant communication and adhere to deadlines. Currently the crowd-funding campaign is scheduled for the year 2018. Your understanding is dearly appreciated.
       
      Thank you for your time! We look forward to hearing from you!
       
      John Shen
      HR Lead
      Starboard Games LLC
    • By Apollo Cabrera
      Energy particles being harnessed by collection multi-hedron energy matrix. Whuuuttt?
      Love it :)
    • By AndySv
        Total Music Collection (http://u3d.as/Pxo)   THE COLLECTION CONTAINS:   Mega Game Music Collection   Universal Music Collection   Huge library of high quality music for any project! All at an incredibly low price!   - 2,5GB of high quality audio - 100+ different music tracks - Loop and short versions   Action, fantasy, casual, horror, puzzle, epic, dramatic, romantic, positive, inspiring, motivational and more!
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064

      View full story
    • By Dafu
      FES Retro Game Framework is now available on the Unity Asset Store for your kind consideration!
      FES was born when I set out to start a retro pixel game project. I was looking around for an engine to try next. I tried a number of things, from GameMaker, to Fantasy Consoles, to MonoGame and Godot and then ended up back at Unity. Unity is just unbeatable in it's cross-platform support, and ease of deployment, but it sure as heck gets in the way of proper retro pixel games!
      So I poured over the Unity pipeline and found the lowest levels I could tie into and bring up a new retro game engine inside of Unity, but with a completely different source-code-only, classic game-loop retro blitting and bleeping API. Months of polishing and tweaking later I ended up with FES.
      Some FES features:
      Pixel perfect rendering RGB and Indexed color mode, with palette swapping support Primitive shape rendering, lines, rectangles, ellipses, pixels Multi-layered tilemaps with TMX file support Offscreen rendering Text rendering, with text alignment, overflow settings, and custom pixel font support Clipping Sound and Music APIs Simplified Input handling Wide pixel support (think Atari 2600) Post processing and transition effects, such as scanlines, screen wipes, screen shake, fade, pixelate and more Deploy to all Unity supported platforms I've put in lots of hours into a very detail documentation, you can flip through it here to get an better glimpse at the features and general overview: http://www.pixeltrollgames.com/fes/docs/index.html
      FES is carefully designed and well optimized (see live stress test demo below). Internally it uses batching, it chunks tilemaps, is careful about memory allocations, and tries to be smart about any heavy operations.
      Please have a quick look at the screenshots and live demos below and let me know what you think! I'd love to hear some opinions, feedback and questions!
      I hope I've tickled your retro feels!



      More images at: https://imgur.com/a/LFMAc
      Live demo feature reel: https://simmer.io/@Dafu/fes
      Live blitting stress test: https://simmer.io/@Dafu/fes-drawstress
      Unity Asset Store: https://www.assetstore.unity3d.com/#!/content/102064
  • Popular Now