modal.md

Modal

The execution in this Modal interpreter revolves around the application of substitution rules to transform the initial program into its final state. This process is iterative, applying rules as long as possible until no more substitutions can be made. The core of the execution process is handled by the rewrite function. Let's break down how execution works, focusing on the rewrite function and related components:

The Rewrite Function

The rewrite function is the heart of the execution process. It iterates over the program, attempting to apply each rule to the program text. If a rule matches and is applied, the program is updated with the substitution, and the process repeats. Here's a simplified overview of how rewrite operates:

static int
rewrite(void)
{
	char c, *p = prog;
	while((c = *p)) {
		int i;
		if(p[0] == '<' && p[1] == '>')
			p = addrule(p) + 1, c = *p;
		for(i = 0; i < rules_len; i++) {
			Rule *r = &rules[i];
			char *res = match(p, r);
			if(res != NULL) {
				char cc, *b = r->b;
				while((cc = *b++)) {
					if(cc == '?')
						writereg(*b++);
					else
						*outp_++ = cc;
				}
				while((*outp_++ = *res++))
					;
				*outp_++ = 0;
				save(i);
				return 1;
			}
		}
		*outp_++ = c;
		p++;
	}
	*outp_++ = 0;
	return 0;
}

1. Initialization: The function starts with the beginning of the program text, pointed to by p.

2. Rule Application: It iterates through each character of the program, attempting to apply substitution rules. For each position in the program:

   • It checks if the current segment matches any of the rules using the match function.
   • If a match is found (match returns a non-NULL pointer), it constructs the substitution in the output buffer (outp) by:
     • Writing the substitution pattern (b of the rule), handling placeholders (?) by calling writereg to insert the matched segments.
     • Appending the remainder of the program text after the matched segment.
   • The state of the program is saved with the save function, which also prints the applied rule and the new program state for debugging or visualization purposes.
   • It returns 1 to indicate that a rule was applied, prompting another iteration of the rewrite process.

3. No Match: If no rules match at the current position, the character is copied to the output buffer, and the function proceeds to the next character.

4. Termination: If the function iterates through the entire program without applying any rules, it returns 0. This indicates that the program has reached its final state, and no further substitutions can be made.

Supporting Functions

• match: This function attempts to match a rule against a segment of the program starting at a given position. It handles placeholders in rules, allowing for flexible pattern matching.

• writereg: This function writes the content of a "register" (a placeholder match from a rule) to the output buffer. It's used to construct the substitution result by inserting matched segments into the substitution pattern.

• save: This function saves the current state of the output buffer as the new program state. It's used to update the program after a successful substitution and to print the rule number and the new program state.

Execution Flow

1. Start: The initial program is loaded, and rules are parsed from the input file.

2. Iterative Rewriting: The rewrite function is called in a loop, transforming the program iteratively by applying rules.

3. Final State: Once rewrite returns 0, indicating no more rules can be applied, the final state of the program is reached. This final state is the output of the Modal interpreter.

This execution process allows the Modal interpreter to transform the initial program step by step, applying rules to achieve complex behaviors and transformations based on simple substitution principles.

Rule precedence

In this Modal interpreter, rule precedence is determined by the order in which rules are defined in the input file. The interpreter attempts to apply rules in the same sequence they are listed, starting from the top. When processing the program, it checks each rule in order until it finds a match. Once a match is found and the substitution is made, the process restarts from the beginning of the updated program, again considering rules in their defined order. This means the first rule that matches at any given point is the one that gets applied, making the order of rule definition crucial to the behavior of the program.

Example Substitution Visualization

Let's consider a simple example to visualize how substitution works. Suppose we have the following rules and initial program:

Rules:

1. <> (a) (apple)
2. <> (b) (banana)
3. <> (apple banana) (fruit salad)

Initial Program:

a b

Execution Steps:

1. Start with the initial program:

   a b
   

2. Apply the first rule (a -> apple):

   • The program becomes:

     apple b
     

   • Since a substitution was made, we start over from the beginning of the updated program.

3. Apply the second rule (b -> banana):

   • The program becomes:

     apple banana
     

   • Again, we start over from the beginning of the updated program.

4. Apply the third rule (apple banana -> fruit salad):

   • The program becomes:

     fruit salad
     

   • We attempt to apply rules again, but no more matches are found.

5. Final State:

   fruit salad
   

   • The program has reached its final state, as no more substitutions can be applied.

Visualization

Here's a visual representation of the substitution process:

Initial Program:      a b
                      |
Rule 1 Applied:       |
                      v
                      apple b
                            |
Rule 2 Applied:             |
                            v
                      apple banana
                      |
Rule 3 Applied:       |
                      v
                      fruit salad

Each arrow (| and v) represents the application of a rule, transforming the program step by step until it reaches its final state.

This example illustrates how the Modal interpreter applies rules in the order they are defined, transforming the initial program through a series of substitutions. The process is iterative, with the interpreter continuously attempting to apply rules until no more matches are found, resulting in the final program state.