Path Notations for Lists: ~ ^~ and ~n

To make the use of lists more convenient, three special notations have been defined in FUF: ~, ^~ and ~n. The macro-character ~ is used to define lists of FDs as an FD with features car and cdr. It performs the following transformation:

          
~(fd1 fd2 ... fdn)  <==> ((car fd1)
                          (cdr ((car fd2)
                                (cdr ...
                                          ((car fdn)
                                           (cdr none))))))
          
          

The two other notations are used within path expressions (within curly braces). ~n is used to access the nth element within a list. It is expanded to the appropriate sequence of cdrs and car. The notation ^~ is used to go back up to the beginning of a list from within an element of a list. This is expanded at unification-time since it depends on the level of embedding of the element. Therefore ^~ actually increases the expressive power of path expressions. If ^~ is used within a feature which is not a list element (which means that it does not occur under car), then it is equivalent to the simple ^ (which means that it does go up one level anyway). The shorthand notation ^n~ is used for ^n ^~ that is, go up first n levels and then to the beginning of the embedding list. These notations are shown for example in the input example above.