Maude system
Encyclopedia
The Maude system is an implementation of rewriting logic developed at SRI International
. It is similar in its general approach to Joseph Goguen
's OBJ3
implementation of equational logic
, but based on rewriting logic rather than order-sorted equational logic, and with a heavy emphasis on powerful metaprogramming
based on reflection
.
NOTE: If you want to test these examples on your own, you should start Maude with the option -no-prelude which lets Maude know that none of its basic modules are included (like Maude's own NAT module which will cause a conflict).
This rewrite theory specifies all the natural numbers. First we introduce the sort, saying that there exists a sort called Nat (short for natural numbers), and below is the specification of how these terms are constructed. The operator s in Example 1 is the successor function representing the next natural number in the sequence of natural numbers i.e. s(N) := N + 1. s(0) is meant to represent the natural number 1 and so on. 0 is a constant, it takes no input parameter(s) but returns a Nat.
sort Nat .
op 0 : -> Nat [ctor] .
op s : Nat -> Nat [ctor] .
op _+_ : Nat Nat -> Nat .
vars N M : Nat .
eq 0 + N = N .
eq s(N) + M = s (N + M) .
endfm
In Example 2 we introduce the + sign meant to represent addition of natural numbers. Its definition is almost identical to the previous one, with input and output sorts but there is a difference, its operator has underscores on each side. Maude lets the user specify whether or not operators are infix, postfix or prefix (default), this is done using underscores as place fillers for the input terms. So the + operator takes its input on each side making it an infix operator. Unlike our previous operator s which takes its input terms after the operator (prefix).
op + : Nat Nat -> Nat .
*** is the same as
op +__ : Nat Nat -> Nat . *** two underscores
The three stars are Maude's rest-of-line-comments and lets the parser know that it can ignore the rest of the line (not part of the program), with parenthesis we get section comments:
*** rest of line is ignored by Maude
*** (
section
is
ignored by Maude
)
The extended Nat module also holds two variables and two sets of equations.
vars N M : Nat .
eq 0 + N = N .
eq s(N) + M = s (N + M) .
When Maude "executes", it rewrites terms according to our specifications. And this is done with the statement
reduce in : .
or the shorter form
red .
For this last statement to be used it is important that nothing is ambiguous. A small example from our rewrite theory representing the natural numbers:
reduce in NAT : s(0) + s(0) .
rewrites: 2 in 0ms cpu (0ms real) (~ rewrites/second)
result Nat: s(s(0))
Using the two equations in the rewrite theory NAT Maude was able to reduce our term into the desired term, the representation of the number two i.e. the second successor of 0. At that point no other application of the two equations were possible, so Maude halts. Maude rewrites terms according to the equations whenever there is a match between the closed terms that we try to rewrite (or reduce) and the left hand side of an equation in our equation-set. A match in this context is a substitution
of the variables in the left hand side of an equation which leaves it identical to the term we try to rewrite/reduce.
To illustrate it further we can look at the left hand side of the equations as Maude executes, reducing/rewriting the term.
eq s(N) + M = s (N + M) .
can be applied to the term:
s(0) + s(0)
since the substitution:
N => 0
M => s(0)
s(N) + M N => 0, M => s(0) s(0) + s(0)
makes them identical, and therefore it can be reduced/rewritten using this equation. After this equation has been applied to the term, we are left with the term:
s (0 + s(0))
If we take a close look at that term we will see that it has a fitting substitution with matches the first equation, at least parts of the term matches the first equation:
eq 0 + N = N .
substitution:
N => s(0)
s (0 + N) N => s(0) s (0 + s(0))
0 + s(0) - matches first equation and is rewritten
As we can see the second substitution and rewrite step rewrites the an inner-term (the whole term does not match any of the equations but the inner term does). Then we end up with our resulting term s(s(0)), and it can seem like a lot of hassle to add 1 + 1, but hopefully you will soon see the strength of this approach.
Another thing worth mentioning is that reduction/rewriting up to this point has taken something very important for granted, which is:
This cannot be taken for granted, and for a rewrite theory to be sane, we have to ensure that equational application is confluent and terminating. To prove that term-rewriting terminates is not possible in any instance, as we know from the halting problem
. To be able to prove that term-rewriting (with regards to the equations) terminates, one can usually create some mapping between terms and the natural numbers, and show that application of the equations reduces the associated value of the term. Induction then proves that it is a halting process since the event of finding smaller natural numbers is a halting process. Naturally equation sets that can cause a term-rewrite to contain cycles will not be terminating. To prove confluence is another important aspect since a rewrite theory lacking this ability will be rather flawed. To prove that the equation set is confluent one has to prove that any application of the equations to any belonging term will lead to the same resulting term (termination is a prerequisite). Details for how to prove termination or confluence will not be given here, it just had to be mentioned, since this is where equations and rewrite-rules differ, which is the next topic of this short overview.
The module presented so far NAT which represented the natural numbers and addition on its elements, is considered a functional module/rewrite theory, since it contains no rewrite rules. Such modules are often encapsuled with a fmod and endfm (instead of mod endm) to illustrate this fact. A functional module and its set of equations must be confluent and terminating since they build up the part of a rewrite theory that always should compute the same result, this will be clear once the rewrite rules come into play.
This module introduces two new sorts, and a set of rewrite rules. We also include our previous module, to illustrate how equations and rewrite rules differ. The rewrite rules is thought of as a set of legal state changes, so while equations hold the same meaning on both sides of the equality sign, rewrite rules do not (rewrite rules use a => token instead of an equality sign). You are still the same person after your married (this is open for debate), but something has changed, your marital status at least. So this is illustrated by a rewrite rule, not an equation. Rewrite rules do not have to be confluent and terminating so it does matter a great deal what rules are chosen to rewrite the term. The rules are applied at "random" by the Maude system, meaning that you can not be sure that one rule is applied before another rule and so on. If an equation can be applied to the term, it will always be applied before any rewrite rule.
A small example is in order:
Here we tell the Maude system to rewrite our input term according to the rewrite theory, and we tell it to stop after 3 rewrite steps (remember that rewrite rules do not have to be terminating or confluent so an upper bound is not a bad idea), we just want see what sort of state we end up in after randomly choosing 3 matching rules. And as you can see the state this person ends up in might look a bit strange. (When you're married at the age of one you kind of stick out a bit in kindergarten I guess). It also says 4 rewrite steps, although we specifically stated an upper limit of 3 rewrite steps, this is because rewrite steps that are the result of applying equations does not count (they do not change the term, at least if the equations are sane). In this example one of the equations of the NAT module has been used to reduce the term 0 + s(0) to s(0), which accounts for the 4'th rewrite step.
To make this rewrite theory a bit less morbid, we can alter some of our rewrite rules a bit, and make them conditional rewrite rules, which basically means they have to fulfill some criteria to be applied to the term (other than just matching the left hand side of the rewrite rule).
It seems reasonable that you cannot die once you're dead, and you cannot marry as long as you are married. The leaning toothpicks (/\) are supposed to resemble a logical AND which means that both criteria have to be fulfilled to be able to apply the rule (apart from term matching). Equations can also be made conditional in a similar manner.
We can use Maude's built-in search to look for unwanted states, or it can be used to show that no such states can be reached.
A small example from our PERSON module once again.
Here the Natural numbers have a more familiar look (the basic Maude modules prelude.maude has been loaded, that can be done with the command "in prelude", or 1 can be replaced by s(0) and 2 by s(s(0)) if you don't want to load the default Maude-modules), naturally Maude has built-in support for ordinary structures like integers and floats and so on. The natural numbers are still members of the built-in sort Nat. We state that we want to search for a transition using one rewrite rule (=>1), which rewrites the first term into the other. The result of the investigation is not shocking but still, sometimes proving the obvious is all we can do. If we let Maude use more than one step we should see a different result:
To see what led us in that direction we can use the built in command show path which lets us know what rule applications led us to the resulting term. The token (=>+) means one or more rule application.
As we can see the rule application "birthday" followed by "las-vegas" got us where we wanted. Since all rewrite theories or modules with many possible rule applications will generate a huge tree of possible states to search for with the search command, this approach is not always the solution. We also have the ability to control what rule applications should be attempted at each step using meta-programming, due to the reflective property or rewriting logic. This subject of meta-programming and reflection requires a great deal of explanation for it to be simple, so that will be left for another section.
Maude is free software with great performance, and well written tutorials are available online (don't let this short howto scare you away).
SRI International
SRI International , founded as Stanford Research Institute, is one of the world's largest contract research institutes. Based in Menlo Park, California, the trustees of Stanford University established it in 1946 as a center of innovation to support economic development in the region. It was later...
. It is similar in its general approach to Joseph Goguen
Joseph Goguen
Joseph Amadee Goguen was a computer science professor in the Department of Computer Science and Engineering at the University of California, San Diego, USA, who helped develop the OBJ family of programming languages. He was author of A Categorical Manifesto and founder and Editor-in-Chief of the...
's OBJ3
OBJ3
OBJ3 is a version of OBJ based on order-sorted rewriting. OBJ3 is agent-oriented and runs on Kyoto Common Lisp AKCL. It is now of historical interest since newer versions of the OBJ family are available.-References:...
implementation of equational logic
Equational logic
First-order equational logic consists of quantifier-free terms of ordinary first-order logic, with equality as the only predicate symbol. The model theory of this logic was developed into Universal algebra by Birkhoff et al. [Birkhoff, Gratzer, Cohn]...
, but based on rewriting logic rather than order-sorted equational logic, and with a heavy emphasis on powerful metaprogramming
Metaprogramming
Metaprogramming is the writing of computer programs that write or manipulate other programs as their data, or that do part of the work at compile time that would otherwise be done at runtime...
based on reflection
Reflection (computer science)
In computer science, reflection is the process by which a computer program can observe and modify its own structure and behavior at runtime....
.
Maude - the basics
Maude modules (rewrite theories) consists of a term-language plus sets of equations and rewrite-rules. Terms in a rewrite theory are constructed using operators (functions taking 0 or more arguments of some sort, which return a term of a specific sort). Operators taking 0 arguments are considered constants, and we construct our term-language by these simple constructs.NOTE: If you want to test these examples on your own, you should start Maude with the option -no-prelude which lets Maude know that none of its basic modules are included (like Maude's own NAT module which will cause a conflict).
Example 1
fmod NAT is
sort Nat .
op 0 : -> Nat [ctor] .
op s : Nat -> Nat [ctor] .
endfm
This rewrite theory specifies all the natural numbers. First we introduce the sort, saying that there exists a sort called Nat (short for natural numbers), and below is the specification of how these terms are constructed. The operator s in Example 1 is the successor function representing the next natural number in the sequence of natural numbers i.e. s(N) := N + 1. s(0) is meant to represent the natural number 1 and so on. 0 is a constant, it takes no input parameter(s) but returns a Nat.
Example 2
fmod NAT issort Nat .
op 0 : -> Nat [ctor] .
op s : Nat -> Nat [ctor] .
op _+_ : Nat Nat -> Nat .
vars N M : Nat .
eq 0 + N = N .
eq s(N) + M = s (N + M) .
endfm
In Example 2 we introduce the + sign meant to represent addition of natural numbers. Its definition is almost identical to the previous one, with input and output sorts but there is a difference, its operator has underscores on each side. Maude lets the user specify whether or not operators are infix, postfix or prefix (default), this is done using underscores as place fillers for the input terms. So the + operator takes its input on each side making it an infix operator. Unlike our previous operator s which takes its input terms after the operator (prefix).
op + : Nat Nat -> Nat .
*** is the same as
op +__ : Nat Nat -> Nat . *** two underscores
The three stars are Maude's rest-of-line-comments and lets the parser know that it can ignore the rest of the line (not part of the program), with parenthesis we get section comments:
*** rest of line is ignored by Maude
*** (
section
is
ignored by Maude
)
The extended Nat module also holds two variables and two sets of equations.
vars N M : Nat .
eq 0 + N = N .
eq s(N) + M = s (N + M) .
When Maude "executes", it rewrites terms according to our specifications. And this is done with the statement
reduce in
or the shorter form
red
For this last statement to be used it is important that nothing is ambiguous. A small example from our rewrite theory representing the natural numbers:
reduce in NAT : s(0) + s(0) .
rewrites: 2 in 0ms cpu (0ms real) (~ rewrites/second)
result Nat: s(s(0))
Using the two equations in the rewrite theory NAT Maude was able to reduce our term into the desired term, the representation of the number two i.e. the second successor of 0. At that point no other application of the two equations were possible, so Maude halts. Maude rewrites terms according to the equations whenever there is a match between the closed terms that we try to rewrite (or reduce) and the left hand side of an equation in our equation-set. A match in this context is a substitution
Substitution
Substitution may refer to:- Sciences :* Substitution , a syntactic transformation on strings of symbols of a formal language* Substitution of variables* Substitution cipher, a method of encryption...
of the variables in the left hand side of an equation which leaves it identical to the term we try to rewrite/reduce.
To illustrate it further we can look at the left hand side of the equations as Maude executes, reducing/rewriting the term.
eq s(N) + M = s (N + M) .
can be applied to the term:
s(0) + s(0)
since the substitution:
N => 0
M => s(0)
s(N) + M N => 0, M => s(0) s(0) + s(0)
makes them identical, and therefore it can be reduced/rewritten using this equation. After this equation has been applied to the term, we are left with the term:
s (0 + s(0))
If we take a close look at that term we will see that it has a fitting substitution with matches the first equation, at least parts of the term matches the first equation:
eq 0 + N = N .
substitution:
N => s(0)
s (0 + N) N => s(0) s (0 + s(0))
0 + s(0) - matches first equation and is rewritten
As we can see the second substitution and rewrite step rewrites the an inner-term (the whole term does not match any of the equations but the inner term does). Then we end up with our resulting term s(s(0)), and it can seem like a lot of hassle to add 1 + 1, but hopefully you will soon see the strength of this approach.
Another thing worth mentioning is that reduction/rewriting up to this point has taken something very important for granted, which is:
- Reduction/Rewriting terminates
- Reduction/Rewriting is confluent (applying the equations in any order will eventually lead to the same resulting term)
This cannot be taken for granted, and for a rewrite theory to be sane, we have to ensure that equational application is confluent and terminating. To prove that term-rewriting terminates is not possible in any instance, as we know from the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
. To be able to prove that term-rewriting (with regards to the equations) terminates, one can usually create some mapping between terms and the natural numbers, and show that application of the equations reduces the associated value of the term. Induction then proves that it is a halting process since the event of finding smaller natural numbers is a halting process. Naturally equation sets that can cause a term-rewrite to contain cycles will not be terminating. To prove confluence is another important aspect since a rewrite theory lacking this ability will be rather flawed. To prove that the equation set is confluent one has to prove that any application of the equations to any belonging term will lead to the same resulting term (termination is a prerequisite). Details for how to prove termination or confluence will not be given here, it just had to be mentioned, since this is where equations and rewrite-rules differ, which is the next topic of this short overview.
Rewrite Rules
Up to this point we have been talking about rewriting and reduction as more or less the same thing, our first rewrite theory had no rewrite rules, still we rewrote terms, so it is time to illustrate what rewrite rules are, and how they differ from the equations we have seen so far (they do not differ much from equations naturally since we talk about the two concepts almost interchangeably).The module presented so far NAT which represented the natural numbers and addition on its elements, is considered a functional module/rewrite theory, since it contains no rewrite rules. Such modules are often encapsuled with a fmod and endfm (instead of mod endm) to illustrate this fact. A functional module and its set of equations must be confluent and terminating since they build up the part of a rewrite theory that always should compute the same result, this will be clear once the rewrite rules come into play.
Example 3
mod PERSON is
including NAT . *** our previous module
sort Person .
sort State .
op married : -> State [ctor] .
op divorced : -> State [ctor] .
op single : -> State [ctor] .
op engaged : -> State [ctor] .
op dead : -> State [ctor] .
op person : State Nat -> Person [ctor] .
var N : Nat .
var S : State .
rl [birthday] :
person (S, N) => person (S, N + s(0)) .
rl [get-engaged] :
person (single, N) => person (engaged, N) .
rl [get-married] :
person (engaged, N) => person (married, N) .
rl [get-divorced] :
person (married, N) => person (divorced, N) .
rl [las-vegas] :
person (S, N) => person (married, N) .
rl [die] :
person (S, N) => person (dead, N) .
endm
This module introduces two new sorts, and a set of rewrite rules. We also include our previous module, to illustrate how equations and rewrite rules differ. The rewrite rules is thought of as a set of legal state changes, so while equations hold the same meaning on both sides of the equality sign, rewrite rules do not (rewrite rules use a => token instead of an equality sign). You are still the same person after your married (this is open for debate), but something has changed, your marital status at least. So this is illustrated by a rewrite rule, not an equation. Rewrite rules do not have to be confluent and terminating so it does matter a great deal what rules are chosen to rewrite the term. The rules are applied at "random" by the Maude system, meaning that you can not be sure that one rule is applied before another rule and so on. If an equation can be applied to the term, it will always be applied before any rewrite rule.
A small example is in order:
Example 4
rewrite [3] in PERSON : person (single, 0) .
rewrites: 4 in 0ms cpu (0ms real) (~ rewrites/second)
result Person: person (married, s(0))
Here we tell the Maude system to rewrite our input term according to the rewrite theory, and we tell it to stop after 3 rewrite steps (remember that rewrite rules do not have to be terminating or confluent so an upper bound is not a bad idea), we just want see what sort of state we end up in after randomly choosing 3 matching rules. And as you can see the state this person ends up in might look a bit strange. (When you're married at the age of one you kind of stick out a bit in kindergarten I guess). It also says 4 rewrite steps, although we specifically stated an upper limit of 3 rewrite steps, this is because rewrite steps that are the result of applying equations does not count (they do not change the term, at least if the equations are sane). In this example one of the equations of the NAT module has been used to reduce the term 0 + s(0) to s(0), which accounts for the 4'th rewrite step.
To make this rewrite theory a bit less morbid, we can alter some of our rewrite rules a bit, and make them conditional rewrite rules, which basically means they have to fulfill some criteria to be applied to the term (other than just matching the left hand side of the rewrite rule).
crl [las-vegas] :
person (S, N) => person (married, N) if (S =/= married) /\ (S =/= dead) .
crl [die] :
person (S, N) => person (dead, N) if (S =/= dead) .
It seems reasonable that you cannot die once you're dead, and you cannot marry as long as you are married. The leaning toothpicks (/\) are supposed to resemble a logical AND which means that both criteria have to be fulfilled to be able to apply the rule (apart from term matching). Equations can also be made conditional in a similar manner.
Why Rewriting Logic? Why Maude?
As you probably can tell Maude sets out to solve a different set of problems than ordinary imperative languages like C, Java or Perl. It is a formal reasoning tool, which can help us verify that things are "as they should", and show us why they are not if this is the case. In other words Maude lets us define formally what we mean by some concept in a very abstract manner (not concerning ourselves with how the structure is internally represented and so on), but we can describe what is thought to be the equal concerning our theory (equations) and what state changes it can go through (rewrite rules). This is extremely useful to validate security protocols and critical code. The Maude system has proved flaws in cryptography protocols by just specifying what the system can do (in a manner similar to the PERSON rewrite theory), and by looking for unwanted situations (states or terms that should not be possible to reach) the protocol can be showed to contain bugs, not programming bugs but situations happen that are hard to predict just by walking down the "happy path" as most developers do.We can use Maude's built-in search to look for unwanted states, or it can be used to show that no such states can be reached.
A small example from our PERSON module once again.
search [1] in PERSON : person (single, 1) =>1 person (married, 2) .
No solution.
Here the Natural numbers have a more familiar look (the basic Maude modules prelude.maude has been loaded, that can be done with the command "in prelude", or 1 can be replaced by s(0) and 2 by s(s(0)) if you don't want to load the default Maude-modules), naturally Maude has built-in support for ordinary structures like integers and floats and so on. The natural numbers are still members of the built-in sort Nat. We state that we want to search for a transition using one rewrite rule (=>1), which rewrites the first term into the other. The result of the investigation is not shocking but still, sometimes proving the obvious is all we can do. If we let Maude use more than one step we should see a different result:
search [1] in PERSON : person (single, 1) =>+ person (married, 2) .
Solution 1 (state 7)
states: 8 rewrites: 14 in 0ms cpu (0ms real) (~ rewrites/second)
To see what led us in that direction we can use the built in command show path which lets us know what rule applications led us to the resulting term. The token (=>+) means one or more rule application.
show path 7 .
state 0, Person: person (single, 1)
crl person(S, N) => person(married, N) if S =/= married = true /\ S =/= dead = true [label las-vegas .]
>
state 7, Person: person (married, 2)
As we can see the rule application "birthday" followed by "las-vegas" got us where we wanted. Since all rewrite theories or modules with many possible rule applications will generate a huge tree of possible states to search for with the search command, this approach is not always the solution. We also have the ability to control what rule applications should be attempted at each step using meta-programming, due to the reflective property or rewriting logic. This subject of meta-programming and reflection requires a great deal of explanation for it to be simple, so that will be left for another section.
Maude is free software with great performance, and well written tutorials are available online (don't let this short howto scare you away).
External links
- Maude homepage at University of Illinois at Urbana-Champaign;
- The Real-Time Maude Tool homepage developed by Peter Csaba Ölveczky;
- An introduction to Maude by Neal Harman, Swansea UniversitySwansea UniversitySwansea University is a university located in Swansea, Wales, United Kingdom. Swansea University was chartered as University College of Swansea in 1920, as the fourth college of the University of Wales. In 1996, it changed its name to the University of Wales Swansea following structural changes...
(errata) - The Policy And GOal based Distributed Architecture written in Maude by SRI International.
- Maude for Windows, the Maude installer for Windows, and Maude Development Tools, the Maude Eclipse plugin developed by the MOMENT project at Technical University of Valencia (Spain).