Transitive closure

I figured out how to write the code for Transitive Closure. Here it is in Andl.

// define recursive function
XYT := {{X:='',Y:=''}}
TRANCLO:XYT(XY:XYT) => do {
  TTT := XY[{*Z := Y}] compose XY[{*Z := X}] union XY if(TTT = XY, TTT, TRANCLO(TTT))
}
// call it
TRANCLO(MM[ {X:=MAJOR_P#, Y:= MINOR_P# } ]) [{MAJOR_P#:=X, MINOR_P#:=Y }]

Note

  1. XYT is an expression which provides the type information for what amounts to a function call. This is structural typing, there are no type names.
  2. The symbol ‘=>’ means deferred evaluation, in this case with arguments. A function call by any other name.
  3. The do {} block allows an arbitrary number of statements, and returns the value of the last expression.

I have to confess I’m quite pleased with the outcome.  Here is the equivalent code in Tutorial-D.

/* the function */
OPERATOR TRANCLO ( XY RELATION { X P#, Y P# } ) RETURNS RELATION { X P#, Y P# } ;
    RETURN 
  ( WITH ( XY UNION ( ( XY RENAME ( Y AS Z ) ) 
              COMPOSE ( XY RENAME ( X AS Z ) ) ) ) AS TTT :
    IF TTT = XY THEN TTT /* unwind recursion */
      ELSE TRANCLO ( TTT ) /* recursive invocation */
    END IF 
  ) ;
END OPERATOR ;
/* the call */
( TRANCLO ( MM RENAME ( MAJOR_P# AS X , MINOR_P# AS Y ) ) ) RENAME ( X AS MAJOR_P# , Y AS MINOR_P# )

The similarities are reasonably obvious.

Leave a Comment

Filed under Code sample

Leave a Reply

Your email address will not be published. Required fields are marked *