32:Ted0,md` ## Alphabet, strings, languages and grammars In *Formal Language Theory*, an alphabet is a finite set of elements we call symbols. For example: ${tex`\{a, b, c\}`} is the alphabet containing the symbols ${tex`a`}, ${tex`b`} and ${tex`c`}. A string over a given alphabet ${tex`V`} is a finite sequence, possibly empty, of symbols in ${tex`V`}. For example: ${tex`a`}, ${tex`aab`} and ${tex`bcacc`} are all strings over the alphabet ${tex`\{a, b, c\}`}. ${tex`\epsilon`} denotes the empty string, that is, a string with no symbols. A language ${tex`L`} over an alphabet ${tex`V`} is a, possibly infinite, set of strings over ${tex`V`}. ${tex`V^*`} denotes the language of all possible strings over ${tex`V`}. Any language ${tex`L`} over ${tex`V`} is a subset of ${tex`V^*`}. Grammars are formal mechanisms to generate strings over an alphabet. A grammar ${tex`G`} is defined as follows: ${tex`G = `} where: - ${tex`V_N`} is an alphabet of *non-terminal symbols* - ${tex`V_T`} is an alphabet of *terminal symbols*, ${tex`V_N \cap V_T =\empty`} - ${tex`P`} is a finite subset of ${tex`(V_N \cup V_T)^*V_N(V_N \cup V_T)^* \times (V_N \cup V_T)^*`} named *production rules* or *productions*. This means that all rules are tuples whose first element (left part) is a string of terminal and non-terminal symbols with at least one non-terminal symbol and the second element (right part) is a string or terminal and non-terminal symbols. - ${tex`S`} a non-terminal symbol (${tex`S \in V_N`}) named *starting* or *distinguished* symbol. A grammar generates a language over ${tex`V_T`}. From the starting symbol, a grammar generates new strings by replacing occurrences of the left part of the rules by their right parts. The general procedure is as follows: - Initially, the *current string* is a string containing only the starting symbol. - On each iteration the grammar picks a random production rule whose left part is a substring of the current string. Then the left part is replaced for the right part of the rule. This is a *substitution* or a *direct derivation*. - The procedure continues until no rule can be applied. - If the resulting string contains only terminal symbols, then it is a string generated by the grammar. Otherwise nothing has been generated. For example: ${tex.block`<\{S\}, \{a,b\}, \{(S, aS), (S, bS), (S, \epsilon)\}, S>`} is a grammar that generates all strings over ${tex`\{a,b\}`}. Usually and for the sake of simplicity, the production rules are represented with a ${tex`\to`} and all rules sharing the same left part are grouped together: ${tex.block`S \to aS | bS | \epsilon`} To generate the string ${tex`abb`} the grammar would perform the following sequence of substitutions: ${tex.block`S \Rightarrow_{S \to aS} aS \Rightarrow_{S \rightarrow aS} aaS \Rightarrow_{S \rightarrow bS} aabS \Rightarrow_{S \rightarrow \epsilon} aab `} The following grammar generates ${tex`\{(ab)^n | n \gt 0\}`} ${tex.block` \begin{matrix} <\{S\} , \{a,b\}, P,S> \\ P: S \rightarrow abS | ab \\ \end{matrix} `} As another example, the following grammar generates ${tex`\{a^rb^sc^t | r,s,t \ge 0\}`}: ${tex.block` \begin{matrix} <\{S,A,B,C\} , \{a,b,c\}, P,S> \\ \begin{aligned} P: & \\ & S \rightarrow ABC \\ & A \rightarrow aA | \epsilon \\ & B \rightarrow bB | \epsilon \\ & C \rightarrow cC | \epsilon \\ \end{aligned} \end{matrix} `} When the left part of all the productions in a grammar are a single non-terminal symbol, the grammar is said to be *context-free*. [*The Theory of Parsing Translation and Compiling*, by Aho and Ullman](https://www.amazon.com/Theory-Parsing-Translation-Compiling/dp/0139145567) is a great book to explore more about Formal Language Theory. `33:Tab1,md` ### Array grammars As there is a strong theory about strings, languages and grammars, there is also an extended definition and theory about bi-dimensional strings or bi-dimensional arrays. The counterpart of traditional grammars are *array grammars*. These grammars encode in the productions the positions of the symbols in the bi-dimensional array. For example, the following production: ${tex.block` \begin{array}{l} a \\ b \\ \end{array} \Rightarrow \begin{array}{l} a \\ c \\ \end{array} `} means that if we find an ${tex`a`} above a ${tex`b`} in the array, we can replace ${tex`b`} by ${tex`c`}. Here is an example of a full array grammar definition: ${tex.block`< \{S,b\}, \{0,1\}, P, S>`} ${tex`S`} and ${tex`b`} are non-terminal symbols. ${tex`b`} is a special symbol denoting a *blank* space in the array. ${tex`0`} and ${tex`1`} are the terminal symbols. The elements of ${tex`P`} are: ${tex.block` \begin{array}{cccc} S \rightarrow 1 & S \rightarrow 0 & & \\ \begin{array}{l} 0 \\ b \\ \end{array} \rightarrow \begin{array}{l} 0 \\ 1 \\ \end{array} & \begin{array}{l} b \\ 0 \\ \end{array} \rightarrow \begin{array}{l} 1 \\ 0 \\ \end{array} & 0 b \rightarrow 0 1 & b 0 \rightarrow 1 0 \\ \begin{array}{l} 1 \\ b \\ \end{array} \rightarrow \begin{array}{l} 1 \\ 0 \\ \end{array} & \begin{array}{l} b \\ 1 \\ \end{array} \rightarrow \begin{array}{l} 0 \\ 1 \\ \end{array} & 1 b \rightarrow 1 0 & b 1 \rightarrow 0 1 \\ \end{array} `} The following could be a sequence of productions generating an array: ${tex` \begin{array}{ccccc} b & b & b & b & b \\ b & b & b & b & b \\ b & b & S & b & b \\ b & b & b & b & b \\ b & b & b & b & b \\ \end{array} \Rightarrow \begin{array}{ccccc} b & b & b & b & b \\ b & b & b & b & b \\ b & b & 1 & b & b \\ b & b & b & b & b \\ b & b & b & b & b \\ \end{array} \Rightarrow \begin{array}{ccccc} b & b & b & b & b \\ b & b & b & b & b \\ b & b & 1 & 0 & b \\ b & b & b & b & b \\ b & b & b & b & b \\ \end{array} \Rightarrow \dots \Rightarrow \begin{array}{ccccc} b & b & b & b & b \\ b & b & b & b & b \\ b & b & 1 & 0 & b \\ b & b & 0 & 1 & b \\ b & b & b & b & b \\ \end{array} \Rightarrow \dots \Rightarrow \begin{array}{ccccc} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ \end{array} `} If we interpret ${tex`1`} as a black square or pixel and ${tex`0`} as a white pixel we obtain a checkerboard pattern like the one below. `34:T55c,{ const array = "\\begin{array}{ccc} a & a & a \\\\ a & a & a \\\\ a & a & a \\\\ \\end{array}"; const pattern = "\\begin{array}{cccc} 0 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 1 \\\\ 1 & 0 & 0 & 0 \\\\ \\end{array}"; return md` Array grammar primitives are too low level. It is common to combine more than one array grammar to generate different levels of details. In the following example ${tex`G_1`} and ${tex`G_2`} are combined to create a new pattern. ${tex.block` \begin{matrix} G_1 = <\{S,b\}, \{a\}, P_1, S> \\ \begin{array}{ccc} P_1: & S \rightarrow a & \\ & \begin{array}{l} a \\ b \\ \end{array} \rightarrow \begin{array}{l} a \\ a \\ \end{array} & \begin{array}{l} b \\ a \\ \end{array} \rightarrow \begin{array}{l} a \\ a \\ \end{array} \\ & ab \rightarrow aa & ba \rightarrow aa \\ \end{array} \end{matrix} `} ${tex.block` \begin{matrix} G_2 = <\{S,b\}, \{a\}, P_2, S> \\ P_2: \begin{array}{cccc} a & b & b & b \\ b & b & b & b \\ b & b & b & b \\ \end{array} \rightarrow ${pattern} \end{matrix} `} Starting with the following array: ${tex.block` \begin{array}{ccc} b & b & b \\ b & S & b \\ b & b & b \\ \end{array} `} using first ${tex`G_1`} we obtain: ${tex.block`${array}`} and using now ${tex`G_2`} we obtain the following pattern: ${tex.block`${array.replace(/\sa\s/g, ` ${pattern} `)}`} which corresponds to the following figure: `; }35:Tc0b,md` ### Context Free Art [Context Free](https://www.contextfreeart.org/) is an open-source application that leverages context free grammars to generate images. In fact, it allows to implement attributed grammars. Attributed grammars augment formal grammars by associating attributes to the symbols and declaring semantic rules for each production. Semantic rules control how the information stored in the attributes is passed from one symbol to the other. In Context Free, one must specify a starting non-terminal symbol or *shape*. Shapes can be defined by means of terminal symbols represing circles, squares and alike. One can use attributes to modify the position, size and color of the shapes being generated, as in the example below. \`\`\` startshape fig shape fig { SQUARE[] CIRCLE[x 1 s 0.5 h 200 sat 1 b 1] } \`\`\`

${Object.assign(await FileAttachment("primitives.png").image(), { width: 400 })} It is also possible to define custom primitives or shapes as in the following example: \`\`\` startshape LEAF[h 100 sat 1 b 0.5] path LEAF { MOVETO(0, -0.5) LINETO(-0.4 , -0.2) LINETO(-0.15, -0.25) LINETO(-0.3 , 0.1) LINETO(-0.1 , 0) LINETO(0 , 0.5) LINETO(0.1 , 0) LINETO(0.3 , 0.1) LINETO(0.15, -0.25) LINETO(0.4 , -0.2) CLOSEPOLY() } \`\`\`

${Object.assign(await FileAttachment("custom_path.png").image(), { width: 200 })} The program provides its own *Domain Specific Language* that includes controls structures like conditional and loops. It also has a set of predefined functions to manipulate the attributes and users can even define their own functions and variables. The next example shows how to use loops and the predefined function *rand* to generate an image. \`\`\` startshape collage import "Example 2 - Custom primitives.cfdg" hues = 0, 30, 60, 90 shape collage { loop 100 [x (0.5 + rand()) y rand() r (100*rand())] LEAF [h hues[randint(4)] sat (rand(0.5, 1)) b 0.5] } \`\`\`

${Object.assign(await FileAttachment("collage.png").image(), { width: 400 })} As in a traditional context free grammar, productions may share the same left part. These are defined by means of *rules*. As an additional feature, rules can be weighted. These weights control the frequency with which each rule is selected. This is an application of stochastic grammars. The next example generates trees by using weighted rules: \`\`\` startshape tree shape tree { SQUARE[] branch[r randint(20, 30) s rand(0.1, 0.8)] branch[r randint(-20, -30) s rand(0.1, 0.8)] tree[y 0.7 s 0.99] } shape branch rule 10 {} rule { tree[s 0.8] } \`\`\`

${Object.assign(await FileAttachment("tree.png").image(), { width: 400 })} The code of Context Free is available from [Github](https://github.com/MtnViewJohn/context-free) as well as its [documentation](https://github.com/MtnViewJohn/context-free/wiki). There is also a [gallery](https://www.contextfreeart.org/gallery ) full of true masterpieces. `36:T515,class Path { constructor() { this.position = { x: 0, y: 0 }; this.bounds = { left: 0, top: 0, right: 0, bottom: 0 }; this.code = "M0,0 "; } updateBounds() { this.bounds.left = Math.min(this.bounds.left, this.position.x); this.bounds.right = Math.max(this.bounds.right, this.position.x); this.bounds.top = Math.min(this.bounds.top, this.position.y); this.bounds.bottom = Math.max(this.bounds.bottom, this.position.y); } vertical(length) { this.code += ` v${length}`; this.position.y += length; this.updateBounds(); } horizontal(length) { this.code += ` h${length}`; this.position.x += length; this.updateBounds(); } moveTo(x, y) { this.position.x = x; this.position.y = y; this.code += ` M${x},${y}`; this.updateBounds(); } _move(cmd, dx, dy) { this.code += ` ${cmd}${dx},${dy}`; this.position.x += dx; this.position.y += dy; this.updateBounds(); } move(dx, dy) { this._move('m', dx, dy); } line(dx, dy) { this._move('l', dx, dy); } get width() { return this.bounds.right - this.bounds.left; } get height() { return this.bounds.bottom - this.bounds.top; } get top() { return this.bounds.top; } get left() { return this.bounds.left; } }37:Tce3,class ContextFreeGrammar { constructor(start, productions, shortcuts) { this.start = start; //TODO: Shortcuts are computable from the grammar, as the shortest string each production can generate //TODO: Clean the grammar this.shortcuts = shortcuts; this.productions = this._normalizeProductions(productions); this.nonterminals = this._keysOf(this.productions); this._validateNonterminals(); } _keysOf(object) { let result = new Set(); for (let key in object) { result.add(key); } return result; } _normalizeProductions(productions) { let result = {}; for (let key in productions) { result[key] = this._normalizeOptions(productions[key]); } return result; } _validateNonterminals() { if (!this.nonterminals.has(this.start)) throw new Error('Starting symbol must be a non-terminal'); for (let symbol of this.nonterminals) { if (symbol.length > 1) { throw new Error( `Only strings of length 1 can be used as non-terminals, got ${symbol}` ); } } } _normalizeOptions(options) { if (!options) { return [""]; } if (Array.prototype.isPrototypeOf(options)) { return options.map(x => '' + x); } if (typeof options === 'string') { return options; } return '' + options; } _getNonterminalPositions(sentenceForm) { let result = []; for (let i = 0; i < sentenceForm.length; i++) { if (this.nonterminals.has(sentenceForm[i])) { result.push(i); } } return result; } _pick(options) { return options[Math.floor(Math.random() * options.length)]; } _terminate(str) { let result = ""; for (let i = 0; i < str.length; i++) { if (str[i] in this.shortcuts) { result += this.shortcuts[str[i]]; } else { result += str[i]; } } return result; } generate(max) { let current = this.start; for (let iteration = 0; iteration < max; iteration++) { let options = this._getNonterminalPositions(current); if (options.length === 0) { return current; } let choice = this._pick(options); let potentialReplacements = this.productions[current[choice]]; let replacement = this._pick(potentialReplacements); current = current.slice(0, choice) + replacement + current.slice(choice + 1, current.length); } return this._terminate(current); } get terminals() { let result = new Set(); for (let left in this.productions) { let options = this.productions[left]; for (let body of options) { for (let symbol of body) { if (!this.nonterminals.has(symbol)) { result.add(symbol); } } } } return result; } toTex() { const set2tex = s => `\\{ ${Array.from(s).join(',')} \\}`; let result = `\\begin{matrix} <${set2tex(this.nonterminals)}, ${set2tex( this.terminals )}, P,${this.start}> \\\\ \\begin{array}{cc} P: & \\\\`; for (let left in this.productions) { result += ` & ${left} \\to ${this.productions[left] .map(x => x || '\\epsilon') .join('|')} \\\\`; } return tex`${result} \end{array} \end{matrix}`; } }38:Te00,LSystem = { const EPSILON = 0.00001; return class { constructor(axiom, rules) { this._assertType(axiom, 'string', 'Axiom must be a string'); this.axiom = axiom; this.rules = this._preprocessRules(rules); } _assertType(object, type, message) { const actualType = typeof object; if (actualType !== type) { throw new Error(`${message}, got ${object} of type ${typeof object}`); } } _toOption(rule) { const type = typeof rule; if (type === 'string') { return { weight: 0, body: rule }; } else if (type === 'object') { if (!('weight' in rule && 'body' in rule)) { throw new Error( `Rule definition should have a weight and the actual body. Got ${rule}` ); } this._assertType( rule.weight, 'number', "Rule's weight must be a number" ); this._assertType(rule.body, 'string', "Rule's body must be a string"); return { weight: rule.weight, body: rule.body }; } throw new Error( `Rule definition should be a string or an object, got an instance of ${type}` ); } _normalizeWeights(rules) { const sum = () => rules.reduce((acc, rule) => acc + rule.weight, 0); let total = sum(); if (total < EPSILON) { // All weights are 0 total = rules.length; for (let option of rules) { option.weight = 1; } } else { // Filling 0 weights for (let option of rules) { if (option.weight <= EPSILON) { option.weight = total; } } total = sum(); } for (let option of rules) { option.weight = option.weight / total; } } _preprocessRules(rules) { let result = {}; for (let left in rules) { this._assertType(left, 'string', 'Left part of rules must be a string'); if (left.length !== 1) { throw new Error( `Left part of rules must me a string of length 1, got ${left}` ); } let givenOptions = typeof rules[left] === 'string' ? [rules[left]] : rules[left]; if (!Array.prototype.isPrototypeOf(givenOptions)) { throw new Error( `Options can only be a string or an array, got ${rules[left]}` ); } let options = givenOptions.map(this._toOption); this._normalizeWeights(options); result[left] = options; } return result; } pickOptions() { let result = {}; for (let left in this.rules) { let prob = Math.random(); let op = prob; for (let option of this.rules[left]) { prob -= option.weight; if (prob < EPSILON) { result[left] = option.body; break; } } } return result; } generate(iterations) { let current = this.axiom; for (let i = 0; i < iterations; i++) { let options = this.pickOptions(); let next = ''; for (let symbol of current) { next += symbol in options ? options[symbol] : symbol; } current = next; } return current; } toTex() { let result = `\\begin{matrix} ${this.axiom} \\\\`; for (let left in this.rules) { let options = this.rules[left]; for (let opt of options) { result += ` ${left} \\to ${opt.body} \\\\`; } } return tex`${result} \end{matrix}`; } }; }39:[{"id":"4e1ae4e8d1b51bd7055cdc401cd246ec5d1e86a52309405fd427b5e7be8bb664909bb9cee2d3ff5c8a1bbc9e3e6b4321a34aff425a5d335cc5f36bc33184ef2e","href":"https://static.observableusercontent.com/files/4e1ae4e8d1b51bd7055cdc401cd246ec5d1e86a52309405fd427b5e7be8bb664909bb9cee2d3ff5c8a1bbc9e3e6b4321a34aff425a5d335cc5f36bc33184ef2e","name":"primitives.png","type":"image/png","lastModified":1590176011548.143,"size":22284},{"id":"d1a9b24383d3f9f4e790afcd1b2b8b933c9feea0c4ef7c7f7e5bdc2ea4637fe9986d52b015cf0618f293a85ea80c903174101c41aa4f0abade4d01de1474d22b","href":"https://static.observableusercontent.com/files/d1a9b24383d3f9f4e790afcd1b2b8b933c9feea0c4ef7c7f7e5bdc2ea4637fe9986d52b015cf0618f293a85ea80c903174101c41aa4f0abade4d01de1474d22b","name":"tree.png","type":"image/png","lastModified":1590176012273.086,"size":193484},{"id":"1278be6103a18917fdcca6c80fe38aff7f3f9d9c1a36b2988569f681c64ddc746bf4e4b0b4a899d4d12e82c8a8ff2333bd94379ade65b9256e793a49288f4898","href":"https://static.observableusercontent.com/files/1278be6103a18917fdcca6c80fe38aff7f3f9d9c1a36b2988569f681c64ddc746bf4e4b0b4a899d4d12e82c8a8ff2333bd94379ade65b9256e793a49288f4898","name":"collage.png","type":"image/png","lastModified":1590176012065.144,"size":273564},{"id":"bf3200978954b2a10050a170ac7306be2c3120356703c81c77367f68759a7dddeb061d0b05e17e98e7c4df8d424c36a7fca38bd66609bc3f41edcc937161a469","href":"https://static.observableusercontent.com/files/bf3200978954b2a10050a170ac7306be2c3120356703c81c77367f68759a7dddeb061d0b05e17e98e7c4df8d424c36a7fca38bd66609bc3f41edcc937161a469","name":"custom_path.png","type":"image/png","lastModified":1590176011589.268,"size":55332}] 30:{"title":"Grammatical Picture Generation: Introductory examples","cells":[{"id":0,"value":"md`\n# Grammatical Picture Generation: Introductory examples\n\nThis notebook gathers a set of introductory examples on Grammatical Picture Generation from the related bibliography. It first discusses the concept of formal grammars, then introduces the examples and finally provides some pointers to valuable books to dig deeper in this topic.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"md`\n## Generating pictures with grammars\n\nGrammars can be leveraged to generate more than strings, and, of course, they can be used to generate pictures. But, strings generated by grammars are unidimensional sequences of symbols. Also, symbols have no specific meaning. \n\nSo, to generate pictures from grammars, we should either:\n\n- Change our definition of a string: For example, instead of one-dimensional strings we could generate a two-dimensional string.\n- Change the nature of our symbols: Instead of abstract symbols we can use, for example, notions of figures like squares or circles and take advantage of their properties.\n- Interpret the generated string to produce an image: For example, consider symbols as drawing commands.\n\nIn the following sections we briefly show some examples of how to generate pictures with the help of grammars.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":559,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":590,"value":"{\n const side = 30;\n return svg``;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":53,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":621,"value":"{\n const side = 30;\n const pattern = (x, y) => svg`\n \n \n \n \n \n \n `;\n\n return svg`\n \n `;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":74,"value":"md`\n### Shape grammars\n\nShape grammars replace symbols by shape primitives and strings by combinations of shapes. A shape grammar contains a finite set of *terminal shapes*, a disjoint finite set of *marker* shapes, which are a parallel of non-terminal symbols, and a combination of terminals and markers which is the starting shape. \n\nProductions are ordered pairs where both elements are combinations of terminals and markers and the left part must contain at least a marker.\n\nNew shapes are generated from the starting shape, by locating the left part of a production. Then we apply the corresponding geometrical transformations such as rotation, translation and scaling to the left part to exactly match the combination in the current shape. The same transformations are applied to the right part of the production which is used to replace the left part in the current figure.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":509,"value":"md`For our example, the set of terminal shapes will contain only an hexagon:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":516,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":534,"value":"md`as a marker we will use a single dot:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":519,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":537,"value":"md`the following figure will be the starting shape:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":521,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":538,"value":"md`With the following productions:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":89,"value":"svg`\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":544,"value":"md`The grammar is able to generate a honeycomb-like pattern. The following sequence shows the shapes that are being form by subsequent substitutions. `","pinned":false,"hidden":false,"mode":"ojs"},{"id":470,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":468,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":465,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":301,"value":"svg`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":551,"value":"md`\n### Interpreting strings\n\nIt is possible to generate pictures by associating symbols to a specific action, for example, drawing commands. In this way, a string generated by a grammar can produce a picture by interpreting in order the sequence of symbols.\n\nA simple approach is to consider the following four symbols with an associated meaning:\n\n- ${tex`u`}: Draw a vertical up line of a fixed length .\n- ${tex`d`}: Draw a vertial down line of a fixed length.\n- ${tex`l`}: Draw a horizontal line of a fixed length to the left.\n- ${tex`r`}: Draw a horizontal line of a fixed length to the right.\n\nA picture can be generated from a string by starting at a given position, for example, the origin of the coordinate system ${tex`(0,0)`}. The execution of the drawing commands are contatenated, so that the last position becomes the initial position of the next command.\n\nAs such, interpreting ${tex`urdl`} would result in a picture of a square.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":743,"value":"svg`\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":757,"value":"md`\nTry your own drawing, any symbols other than ${tex`u`}, ${tex`d`}, ${tex`l`} or ${tex`r`} will be ignored:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":760,"value":"viewof drawing_example_input = text({\n value: 'ururur',\n title: 'Drawing input'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":777,"value":"resizableCanvas(drawPath(drawing_example_input, 30), 5)","pinned":false,"hidden":false,"mode":"ojs"},{"id":811,"value":"md`\nWith these simple commands, the following grammar generates drawings known as *Manhattan Skylines* given their ressemblance to the landscape of that city:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":883,"value":"manhattan_grammar.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":829,"value":"viewof manhattan_generate = button({ value: 'Generate' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":832,"value":"{\n manhattan_generate;\n return resizableCanvas(drawPath(manhattan_grammar.generate(200), 30), 5);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":844,"value":"md`On its side, the following grammar generates simplified trees:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":885,"value":"tree_grammar.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":850,"value":"viewof tree_generate = button({ value: 'Generate' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":846,"value":"{\n tree_generate;\n return resizableCanvas(drawPath(tree_grammar.generate(200), 30), 5);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":553,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":555,"value":"md`\n### L-Systems\n\n*L-Systems* were proposed by the biologist Aristid Lindermayer in 1968. They are generator mechanisms similar to formal grammars. L-Systems are defined by:\n- a set of constant symbols, \n- a set of variable symbols which will be substituted, \n- a set of production rules, whose left side is a string containing at least one variable symbols \n- and an axiom which is a string of variable and constant symbols.\n\nThe generation process starts by the axiom, and variable symbols are substituted according to the production rules. The difference between L-Systems and traditional grammars is that in one iteration of the generation process all variable symbols are substituted and all occurrences of the same symbol are substituted in parallel with the same rule.\n\nThe following L-System has ${tex`b`} as axiom, then substitutes ${tex`b`} by ${tex`a`} and ${tex`a`} by ${tex`ab`}.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":881,"value":"algae.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":871,"value":"md`The table below shows the first six generation iterations using the example above. Iteration 0 corresponds to the axiom. Notice how, from iteration 3 to iteration 4 both ${tex`a`}'s are substituted at the same time.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":863,"value":"html`\n\n \n ${range(7).map(i => ``)}\n

Iteration	Result
${i}	${algae.generate(i)}

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":874,"value":"md`\nThe length of the string produced in the ${tex`i^{th}`} iteration coincides with the ${tex`i^{th}`} number in the Fibonacci sequence. This example was the first used by Lindermayer.\nWhen combined with turtle graphics, L-Systems can generate instersting pictures.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":890,"value":"md`\n#### Turtle graphics\n\nTurtle graphics consist in a reduced set of rawing commands which were used for the Logo educational programming languague. These commands modify the state of a cursor or a *turtle*. \n\n- ${tex`F`}: Moves the turtle forward a number of steps while drawing a line\n- ${tex`f`}: Moves the turtle forward a number of steps whitout drawing a line\n- ${tex`-`}: Rotates the direction of the turtle to the right with a given angle \n- ${tex`+`}: Rotates the direction of the turtle to the left with a given angle \n- ${tex`[`}: Pushes the current state of the turtle: position, direction into a global stack\n- ${tex`]`}: Pops the state on top of the global stack and it becomes the current state\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":905,"value":"viewof input_turtle_example = text({\n title: 'Input',\n desciption: 'Other symbols will be ignored',\n value: 'F[+F][-F]fF'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":893,"value":"viewof step_turtle_example = number({\n title: 'Step length',\n min: 10,\n max: 30,\n value: 30\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":900,"value":"viewof angle_turtle_example = slider({\n min: 0,\n max: 90,\n step: 1,\n title: \"Angle\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":909,"value":"resizableCanvas(\n drawTurtlePath(\n input_turtle_example,\n step_turtle_example,\n (Math.PI * angle_turtle_example) / 180\n ),\n 5\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":939,"value":"md`\n#### Examples\nThe following are typical examples on how to use L-Systems in combination with turtle graphics:\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1016,"value":"md`##### The Koch Island`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1180,"value":"koch.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1183,"value":"tex`\\delta = \\frac{\\pi}{2}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":942,"value":"viewof koch_iteration = slider({ value: 0, min: 0, max: 3, step: 1 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":945,"value":"{\n let path = drawTurtlePath(\n koch.generate(koch_iteration),\n 320 / Math.pow(4, koch_iteration),\n Math.PI / 2\n );\n return fixedSizeCanvas(path, 550, 550, 110, 440);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1168,"value":"md`The dragon curve`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1170,"value":"dragon.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1173,"value":"tex`\\delta = \\frac{\\pi}{2}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1018,"value":"viewof dragon_iterations = slider({ min: 0, max: 10, step: 1, value: 5 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1020,"value":"fixedSizeCanvas(\n drawTurtlePath(dragon.generate(dragon_iterations), 10, Math.PI / 2),\n 500,\n 350,\n 380,\n 220\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1153,"value":"md`##### A tree`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1146,"value":"tree.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1156,"value":"tex`\\delta = \\frac{\\pi}{9}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1064,"value":"viewof tree_iterations = slider({ min: 1, max: 6, value: 6, step: 1 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1068,"value":"fixedSizeCanvas(\n drawTurtlePath(tree.generate(tree_iterations), 5, Math.PI / 9),\n 360,\n 650,\n 180,\n 650\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1159,"value":"md`##### Another tree`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1162,"value":"tree2.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1164,"value":"tex`\\delta = \\frac{\\pi}{9}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1088,"value":"viewof tree2_iterations = slider({ min: 1, max: 6, value: 6, step: 1 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1091,"value":"fixedSizeCanvas(\n drawTurtlePath(tree2.generate(tree2_iterations), 5, Math.PI / 9),\n 360,\n 650,\n 180,\n 650\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1209,"value":"md`##### Other examples`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1211,"value":"koch2.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1225,"value":"tex`\\delta = \\frac{\\pi}{2}, n = 3`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1219,"value":"resizableCanvas(drawTurtlePath(koch2.generate(2), 10, Math.PI / 2), 3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1236,"value":"triangle.toTex()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1238,"value":"resizableCanvas(drawTurtlePath(triangle.generate(7), 5, Math.PI / 3), 3)","pinned":false,"hidden":false,"mode":"ojs"},{"id":937,"value":"md`## Bibliography\n\nMost examples above are extracted from the following books:\n- [Grammatical picture generation: A tree-based approach](https://www.springer.com/gp/book/9783540213048)\n- [Handbook of Formal Languages: Volume 3 Beyond Words. \n](https://www.springer.com/gp/book/9783642638596)\n- [The algorithmic beauty of plants](http://algorithmicbotany.org/papers/abop/abop.pdf)\n\nThey are also invaluable resources to further learn about grammatical picture generation.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":150,"value":"md`## Supporting cells`","pinned":false,"hidden":false,"mode":"ojs"},{"id":151,"value":"common_shape_style = \"stroke:#000000;stroke-width:3;stroke-linejoin:round\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":155,"value":"hexagon = (x, y) =>\n svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"arrow = (x, y) =>\n svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"circle = (x, y) =>\n svg``","pinned":false,"hidden":false,"mode":"ojs"},{"id":241,"value":"shape_rule = (y, mx, my) => svg`${hexagon(0, y)} ${circle(18, y)} \n${arrow(50, y)} \n${hexagon(110, y)} ${hexagon(162, y)} ${circle(162 + mx, y + my)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":567,"value":"range = function(count) {\n let result = [];\n for (let i = 0; i < count; i++) result[i] = i;\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":658,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":663,"value":"class Vector {\n constructor(x, y) {\n this.x = x || 0;\n this.y = y || 0;\n }\n\n setArgMag(arg, mag) {\n this.x = mag * Math.cos(arg);\n this.y = mag * Math.sin(arg);\n }\n\n set magnitude(value) {\n this.setArgMag(this.argument, value);\n }\n\n get magnitude() {\n return Math.sqrt(this.x * this.x + this.y * this.y);\n }\n\n set argument(value) {\n this.setArgMag(value, this.magnitude);\n }\n\n get argument() {\n return Math.atan2(this.y, this.x);\n }\n\n add(other) {\n this.x += other.x;\n this.y += other.y;\n }\n\n clone() {\n return new Vector(this.x, this.y);\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":666,"value":"drawPath = function(commands, step) {\n let path = new Path();\n\n const actions = new Map([\n [\n 'u',\n () => {\n path.vertical(-step);\n }\n ],\n [\n 'd',\n () => {\n path.vertical(step);\n }\n ],\n [\n 'r',\n () => {\n path.horizontal(step);\n }\n ],\n [\n 'l',\n () => {\n path.horizontal(-step);\n }\n ]\n ]);\n\n for (let cmd of commands) {\n if(!actions.has(cmd)) continue;\n actions.get(cmd).apply();\n }\n\n return path;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":699,"value":"drawTurtlePath = function(commands, step, angle) {\n let variation = new Vector(0, -step);\n const path = new Path();\n const memory = [];\n const forward = () => {\n path.line(variation.x, variation.y);\n };\n const actions = new Map([\n ['F', forward],\n ['M', forward],\n ['f', () => path.move(variation.x, variation.y)],\n ['+', () => (variation.argument -= angle)],\n ['-', () => (variation.argument += angle)],\n [\n '[',\n () =>\n memory.push({\n x: path.position.x,\n y: path.position.y,\n variation: variation.clone()\n })\n ],\n [\n ']',\n () => {\n let state = memory.pop();\n variation = state.variation;\n path.moveTo(state.x, state.y);\n }\n ]\n ]);\n\n for (let cmd of commands) {\n if (!actions.has(cmd)) continue;\n actions.get(cmd).apply();\n }\n return path;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":732,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":736,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":778,"value":"resizableCanvas = function(path, padding) {\n return svg`\n \n`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":964,"value":"fixedSizeCanvas = function(path, width, height, dx, dy) {\n return svg`\n `;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":822,"value":"manhattan_grammar = new ContextFreeGrammar(\n 'S',\n { S: ['B', 'SrS'], B: ['r', 'rB', 'uBd'] },\n { S: 'r', B: 'r' }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":841,"value":"tree_grammar = new ContextFreeGrammar(\n 'T',\n {\n T: ['uLuRT', 'u'],\n L: ['luLdr', ''],\n R: ['ruRdl', '']\n },\n { T: 'uludrurudlu', L: 'ludr', R: 'rudl' }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":859,"value":"algae = new LSystem('b', { a: 'ab', b: 'a' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":922,"value":"koch = new LSystem('F-F-F-F', { F: 'F-F+F+FF-F-F+F' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":924,"value":"snowflake = new LSystem('-F', { F: 'F+F-F-F+F' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":926,"value":"koch2 = new LSystem('F+F+F+F', {\n F: 'F+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF',\n f: 'ffffff'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":928,"value":"dragon = new LSystem('FX', { X: 'X+YF+', Y: '-FX-Y' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":930,"value":"triangle = new LSystem('F', { M: 'F+M+F', F: 'M-F-M' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":932,"value":"tree = new LSystem('X', { X: 'F[+X][-X]FX', F: 'FF' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":934,"value":"tree2 = new LSystem('X', { X: 'F[+X]F[-X]+X', F: 'FF' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":764,"value":"import { text, button, number, slider } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W39","stdlib":"1","titling":"auto"}