Representing Tree Structures

Ground expressions are especially convenient for representing symbolic (i.e. not purely numeric) data, organized in a "linear" or "tree" fashion.

For example, suppose we want to deal with algebraic formulae represented by ground expressions. In this case, we have to devise a way of representing constants, variables, and formulae formed by applying a binary operator to two smaller formulae. We may choose, for example, the following representation.

Let [p] denote the ground expression that represents the formula p . Then, numbers may be represented by the corresponding numeric symbols, variables by the corresponding word symbols, and formulae formed by applying binary operators according to the following rules:

[p+q] = ("plus" [p] [q] )

[p-q] = ("minus" [p] [q] )

[p*q] = ("mult" [p] [q] )

[p/q] = ("div" [p] [q] )

[p^q] = ("power" [p] [q] )

Thus the formula

(X+Y²)-512

is to be represented by the ground expression

    ("plus" ("minus" X ("power" Y 2)) 512)

The next example is the problem of representing chess positions by ground expressions.

First of all we have to denote the name and color of each piece. For example, ("white" "King"), ("black" "Pawn"). Then we have to specify the square occupied by each piece. For example, ("e" 2), ("h" 7). Now a position may be represented as a sequence of ground terms, each term specifying the name, color, and square of a piece. For example

    (("white" "King")        ("g" 5))
    (("black" "King")        ("a" 7))
    (("white" "Pawn")        ("c" 6))
    (("white" "Knight")      ("g" 1))
    (("black" "Knight")      ("a" 8))

[p+q]	=	`("plus"` [p] [q] `)`
[p-q]	=	`("minus"` [p] [q] `)`
*[pq]**	=	`("mult"` [p] [q] `)`
[p/q]	=	`("div"` [p] [q] `)`
[p^q]	=	`("power"` [p] [q] `)`