Prof. Dr. Thom Frühwirth
Ulm University
Institute of Software Engineering and Programming Languages
Faculty of Engineering, Computer Science and Psychology 89069 Ulm, Germany
http://www.constraint-handling-rules.org
ISBN 9783752890471
Herstellung und Verlag: Books on Demand GmbH, Norderstedt, Germany
© Thom Fruehwirth 2018
The frontispiece shows a coloring of a mason’s mark done by our tool VanDeGraphGenerator
1.1 Mason’s Mark from Ulm Minster
2.1 Constraint Handling Rules Logo
3.1 Graph [2,90,1,90,2]
3.2 Rule for Merging Shared Lines with Identical Identifier
3.3 Rule to Transform Line and All Connected Lines
3.4 Two Different Graphs from the Same Two Nodes
3.5 Four Given Node Constraints for Exhaustive Generation
3.6 Exhaustive Generation of Marks from Given Node Constraints
A.1 Gothic Mason’s Marks of Ulm Minster
A.2 Gothic Mason’s Marks of Ulm Minster, contd.
A.3 Gothic Mason’s Marks of Ulm Minster with Arcs
A.4 Gothic Mason’s Marks of Ulm Minster with Arcs, contd.
A.5 Gothic Mason’s Marks of Strasbourg Cathedral
A.6 Gothic Mason’s Marks of Strasbourg Cathedral, contd.
A.7 Mason’s Marks of Iglesia Arciprestal de Santiago Villena
B.1 Mason’s Mark from Ulm Minster
B.2 Node Constraints from Mark for Exhaustive Generation
B.3 Another Mason’s Mark from Ulm Minster
B.4 Mason’s Mark from Ulm Minster
B.5 Mason’s Mark from Strasbourg Cathedral
B.6 Random Node Constraints for Exhaustive Generation
B.7 Random Node Constraints for Exhaustive Generation
The stonecutter’s yard on the right.
Ulysses, James Joyce, 1922.
The quaint German city of Ulm is dominated by its minster. It boasts the highest Christian church steeple in the world. When my wife prepared for her exam to become certified city guide, I put together a book of Ulm’s attractions. Later, browsing through her books on the history of the city, I became aware of the mason’s marks of the Ulm Minster. For thousands of years, stonecutters have been carving these symbolic signs in dressed stone. I saw the elegance of those marks, but also that these marks exhibit certain regularities. They have been constructed by compass and ruler in many cases.
A couple of years later, as divertissement I started to encode mason’s marks using the programming language Constraint Handling Rules. I dabbled with Computational Geometry. Exploiting their inherent structural regularities, I was not only able to represent them concisely, but also to generate new ones. The idea was simple: Find the hidden logical substructures of mason’s marks. Then use these to assemble new designs automatically using simple methods from Artificial Intelligence research. I was surprised what could be done - and this is what this book is about. It is about the beauty of mason’s marks and their handling and generation by means of computers.
In this book, I shortly introduce mason’s marks and the Constraint Handling Rules programming language. Geometrically, mason’s marks consist of a pattern of straight lines, arcs and sometimes circles. I will introduce the graph tool VanDeGraphGenerator to draw, analyse, and generate graphs. Then, I will present a node-centric representation of mason’s marks as connected planar graphs. This encoding consists of simple subgraphs that can be connected by shared lines.
Next, I describe how to exhaustively or randomly generate graphs from given small constrained subgraphs. The appendix of the book is comprised more than thousand mason’s marks, ones from Ulm Minster, Strasbourg Cathedral, and Iglesia Arciprestal de Santiago in Villena, as well as random ones generated from them. This application shows the power of declarative modeling, storage, analysis, and generation of diagrammatic information using a logic-based programming language.
Thom Frühwirth, Ulm, August 2018
Mason’s marks are symbols often found on dressed stone in historic buildings. These signs go back about 4500 years, to the tombs of the advanced ancient civilization of Egypt. In Europe, they were common from the 12th century on [Friedrich, 1932, Davis, 1954, Champion, 2015]. There, one can mainly find mason’s marks from the medieval ages, mostly in churches, cathedrals and monasteries. In one such building, there may be a thousand mason’s marks of hundred different designs. Over time, mason’s marks got smaller and more complex (from 25cm down to 2cm).
Mason’s marks were carved on the stones by stonemasons during construction of a building to identify their work, presumably for quality control and probably to receive payment. This was important for masons who were free of servitude and therefore allowed to travel the country for work (see [Follett, 2010] for popular fiction on the subject).
Only stonemason masters were allowed to inscribe their mark in a blazon. Their mason’s marks can also be found on medieval documents and masons tombstones. The master would give a personal mason’s mark to his apprentices, provided they had enough skill to construct and interpret the mason’s mark symbol. A challenging design and interpretation would make it harder to appropriate or misuse a mason’s mark.
Beyond that, uncertainty prevails in what we know about mason’s marks: Sometimes, the master’s mark was passed on the the master’s son. Sometimes, the mark of the mason changed. Sometimes, the same mark was used by different quarrymen. Sometimes, a stone has several different marks.
Architecture historians and archaeologists think that marks were also used by the craftsmen to give the stone’s origin, as signs to indicate if they belong to a specific part of the building, or how the stones should be assembled [Van Belle, 2001, Pitte et al., 2007]. They could be instructions between the designer, quarriers and other workers.
Stonecutter’s marks are an important source of information for art and architecture historians, in particular to reconstruct the construction process of buildings in time and space.
Mason’s marks tend to be simple geometric symbols, usually constructed using rulers and compasses and precisely cut with a chisel. In this way, a distinctive sign consisting of straight lines and curves could be produced with little effort. The geometric construction of mason’s marks implies that they exhibit a structural regularity. This was first discussed and formalized by Franz von Ržiha [Ržiha, 1881]. He claimed that mason’s marks are small subfigures of regular grids (called Schlüssel), which consist either of squares or equilateral triangles together with circles inscribed in each other.
Ržiha’s theory is obsolete, because there is no historical evidence that grids were explicitly used. Not all marks fit these grid patterns. It is, however, clear that the construction of the mason’s marks with compasses and rulers lends itself to the prevalence of certain angles (such as multiples of 30 and 45 degrees) between lines and certain multiples of line lengths due to the use of diagonals in squares and altitudes in triangles [Álvaro Rendón Gómez, 2013].
Figure 1.1 shows a mason’s mark from the Ulm Minster.
Figure 1.1: Mason’s Mark from Ulm Minster
This chapter is concerned with the technical description of our tool VanDe-GraphGenerator. Our graph analysis and generation tool is implemented using the Constraint Handling Rules (CHR) library in SWI Prolog programming language [Wielemaker et al., 2014]. We assume basic familiarity with Prolog and CHR [Frühwirth, 2009, Frühwirth, 2015, Frühwirth and Raiser, 2018].
Starting at http://www.constraint-handling-rules.org, information on CHR can be found online, including news, tutorials, research papers, bibliography, online demos and free downloads of the programming language.
The logo of CHR is shown in Figure 2.1. This Chinese character symbol is written as "CHR" in the Yale transcription of Mandarin. It is derived from the character for horse, and depending on context, it means to speed, to propagate, to be famous.
Constraints are relations, distinguished predicates of first order logic. The arguments of constraints are expressions called terms, these can be numbers, lists or other (data) structures. Constraints are rewritten by CHR rules, consisting of a left-hand side pattern to match constraints, a guard to check their arguments, and a right-hand side to be executed. A CHR program is a set of rules. A (generalized) simpagation rule is of the form
Figure 2.1: Constraint Handling Rules Logo
Head1 \ Head2 <=> Guard | Body.
In the rule head (left-hand side), Head1 and Head2 are conjunctions of constraints, the optional guard Guard is a conjunction of tests (system predicates), and the body (right-hand side) Body is a goal. A goal is a conjunction of constraints and auxiliary system predicates. Conjunctions are understood as multisets of their conjuncts.
In the rule, Head1 are called the kept constraints, while Head2 are called the removed constraints. At least one of Head1 and Head2 must be nonempty. If Head1 is empty, the rule corresponds to a simplification rule, also written
Head2 <=> Guard | Body.
If Head2 is empty, the rule corresponds to a propagation rule, also written
Head1 ==> Guard | Body.
We will not need propagation rules in our exposition of the tool.
Given a problem stated as a multiset of constraints, the rules of the program are applied to exhaustion. A rule is applicable, if its left-hand side (head) constraints are matched by constraints in the current goal one-by-one and if, under this matching, the guard test of the rule succeeds. Any of the applicable rules can be applied, and the application cannot be undone (in contrast to backtracking in Prolog). The execution of the right-hand side (body) of a rule may compute and add new constraints.
When a simplification rule is applied, the matched constraints in the current goal are replaced by the body of the rule. When a propagation rule is applied, the body of the rule is added to the goal without removing any constraints. When a simpagation rule is applied, only the head constraints right to the backslash symbol are removed, the head constraints before are kept.
Assume we would like to compute the minimum of some numbers, given as multiset num(N1), num(N2),..., num(Nk). We make use of the following CHR rule that filters these numbers until only the minimum value remains.
num(N) \ num(M) <=> N=<M | true.
In the rule, the parameter arguments are the variables N and M. The rule consists of a left-hand side, on which a pair of num constraints has to be matched, a guard test N=<M that has to hold, and an empty right-hand side denoted by true. In effect, the rule takes two numbers and removes the one with the larger value.
The rule corresponds to the intuitive algorithm that if we are to find the minimum from a given list of numbers, we just cross out larger numbers until one, the minimum, remains. Consider the following computation, where in each line, the rule is always applied to the first two constraints:
num(2), num(4), num(1), num(3)
num(2), num(1), num(3)
num(1), num(3)
num(1)
In effect, the rule is applied until only one, thus the smallest value, remains as single num constraint.
Our tool VanDeGraphGenerator can analyse, generate and draw straight- and curved line graphs based on a novel node-centric representation of graphs [Frühwirth, 2018a, Frühwirth, 2018b]. It features
VanDeGraphGenerator can be applied to any problem domain that admits a modeling as graphs. Currently we use the tool to classify and to invent mason’s marks. This application is described in this book.
The VanDeGraphGenerator tool comes with several modules. Each module provides a certain functionality and is a collection of CHR rules that are prefixed by a common auxiliary constraint encoding the name of the module. In this way, rules of a particular module can only fire if the module name constraint is present.
We first discuss the representation of graphs and then the essential modules for encoding and generation of mason’s marks. Graph analysis to produce statistics about graph properties, and recognition of subgraphs using pattern matching rules is described in the companion paper [Frühwirth, 2018b]. For readability, the code we show is slightly edited and simplified.
We in essence represent mason’s marks by connected planar straight-line graphs, a drawing of planar graphs in the plane such that its edges are straight line segments [Tamassia, 2013]. A line has two nodes, or two endpoints, given by Cartesian coordinates. Each point is defined by a pair of numbers written (X,Y). For convenience of manipulation, we redundantly represent lines by polar coordinates, which consist of a reference point (pole), which is the first endpoint of the line, a line length and an angle (azimuth) in degrees. Each line also has an identifier. This representation leads to the constraint line with five arguments:
line(EndPoint1, EndPoint2, LineLength, Angle, Identifier)
With polar coordinations, translation, rotation and scaling of lines is straightforward. With Cartesian coordinates, visualization by translation into scalable vector graphics (svg) is easy. Only when the lines are drawn, missing point coordinates are computed.
Extension to Arcs. For the purpose of representing mason’s marks, we extend the representation to allow for arcs. Arcs are curves that are circle segments. As for straight lines, we represent the two end points of the segment and their distance (length). We will use the same line constraint for the representation, but replace the numeric argument LineLength by a term structure than contains additional information about the circle segment.
This information is of the form arc(Distance,Radius,SweepFlag), where Radius denotes the radius of the circle from which we take the segment (arc). The numeric SweepFlag tells us if the arc is drawn in clockwise (0) or counter-clockwise (1) direction or in both directions (2). For simplicity, we assume arcs are at most 180 degrees. Larger or symmetric arcs and full circles can be drawn using both directions (2).
Through exhaustive initial experiments, we found that for the encoding and generation of mason’s marks a node-centric (vertex-centric) representation of their underlying graph is helpful. The constraint representing a graph node is defined by the following EBNF grammar (where we use Prolog’s list notation syntax):
GraphNode ::= node(NodePoint, NodeList)
NodePoint ::= (Number,Number)