LINQ Recipe No. 2-9: Recursive Series and Patterns - How to Generate a Recursive Structure via L-System Grammar

Contents

1. Introduction
2. Keywords
3. Problem
4. Solution
5. Discussion
5.1 L-System
6. Practice: L-System Grammar with LINQ
7. Conclusions
8. Literature & Links

1. Introduction

This is the second part of Chapter 2 of LINQ recipes. This part is focused on Recursive Series and Patterns; and now we are going to learn how to use recursive structures to explore a some interesting system: L-System Grammar -a recurrence relation technically known as recursive pattern-. With an L-System, a cellular biologist can understand how plant cells growth and describe their behavior. Taking that into account, the programmer will learn how to implement such pattern using LINQ functional programming approach.

2. Keywords

• Biology
• Cell
• L-System
• LINQ
• Model

3. Problem

Implement the algae's growth via L-System using LINQ.

4. Solution

By defining recursive relations in LINQ, we will be able to generate a pattern like the algae's growth.

5. Discussion

5.1 L-System

An L-System (also known as Lindenmayer system) is defined as a formal grammar for generating well formed string formulas ("L-system", 2016). The axiom (~starting) string is A, and subsequent strings are formed according to this recursive pattern:

• A is replaced by AB, and 
• B is replaced by A.

Those steps are repeated recursively up to determined number of iterations.

This recursive pattern was discovered by Aristid Lindenmayer (an Hungarian biologist) to describe the behavior of plant cells ("L-System", 2016). It also serves to model the growth processes of plant development.

Additionally, L-systems are generally known as parametric L systems, and formally defined as a tuple:

where 

• V: is the set of available symbols -the alphabet.
• ω: initiator or axiom.
• P: is the set of production rules -recursive pattern.

6. Problem: L-System Grammar with LINQ

With this example, we are going to implement a L-System to model/simulate the growth of algae by using the LINQ functional programming approach.

The formal system is defined as follows:

• Variables: A, B
• Constants:
• Axiom (initiator): A
• Rules: (A -> AB), (B -> A)

The LINQ code: 

// The axiom - initial string:
string algae = "A";

// Replace functions:
Func<string, string> transformA = x => x.Replace("A", "AB");
Func<string, string> markBs = x => x.Replace("B", "[B]");
Func<string, string> transformB = x => x.Replace("[B]", "A");

// Number of iterations:
int length = 7;
Enumerable.Range(1, length).ToList()
.ForEach( iteration => algae = transformB(transformA(markBs(algae))));

The algae string variable represents the axiom. The functions transformA and transformB represent the production rules. We also recognize a third function -markBs-. That function can be seen as an auxiliary replacement to apply the (B -> A) rule.

After executing the LINQ in LINQPad code, we get 

Illustration 1. Algae growth at its seventh iteration.

I have made a trace with pencil and paper to follow the recursive steps which generate the given result in LINQPad: 

Illustration 2. Trace for algae growth simulation in LINQ.

7. Conclusions

We have learned how a recursive pattern is implemented with the LINQ functional programming approach: the algae growth behavior with an L-System. Techniques like this, give us more power to implement such mathematical productions which follow some interesting pattern in biology.

In the next LINQ recipe we are going to invest more time and resources to understand the step-by-step growth of an algae using recursive series and patterns.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
L-system (2016, June 18). Retrieved from: https://en.wikipedia.org/wiki/L-system

V