XSG: Fair Language with Built-in Equality
Yuri Andreevich Klimov, Anton Yu · 2007
We describe the XSG programming language and define a formal semantics for it. XSG is a functional-logic untyped first-order language. Like a functional language it has functions which return results (not predicates only as classic logic languages). And like a logic language it allows implicit definition of variables’ values. XSG is developed as a model language for metacomputations. It is a successor of the TSG and NTSG languages used by S. M. Abramov and R. Glück for formal description of basic metacomputation tools such as driving, PPT and URA [1,2,3,4,5,6,7]. In XSG the concept of pattern matching is generalized by introducing equations. Both free and bound variables in equations can go both at the left and at the right sides. Also a variable can occur in an equation several times. Thus there is a notion of equality inherent in the language. Every variable in XSG is a logic variable: it designates a set of possible values. The equations are global constraints on the variables. Thus there is an embedded nondeterminism in the language as the program result is an unordered set of possible answers.