Examples for FlatCurry and its XML representation

Example 1

The first example program defines a data type for natural numbers (built by the constructors Zero and Succ) and a predicate (Boolean function) leq defining the less-or-equal relation on naturals. This example program can be written in Curry as follows (note that the evaluation annotation "leq eval flex" specifies in Curry that the function leq can be evaluated with narrowing in order to solve equations involving leq):

  data Nat = Zero | Succ Nat

  leq eval flex
  leq Zero     x        = True
  leq (Succ x) Zero     = False
  leq (Succ x) (Succ y) = leq x y

Using an informal notation for case expressions (like in the abstract syntax for FlatCurry), we could translate the rules for leq into a single rule as follows (in order to make the pattern matching explicit):

  leq x y = fcase x of
               { Zero      -> True ;
                 (Succ x1) -> fcase y of
                                 { Zero      -> False ;
                                   (Succ y1) -> leq x1 y1 } }

This definition is the basis of the corresponding FlatCurry program which is represented in XML as follows. In this example, we assume that "nat" is the name of this program (used to prefix all internal names) and "/home/curry/lib/prelude" is the name of the standard prelude for Curry programs (e.g., containing the definition of Booleans).

<prog>
  <module>nat</module>
  <import>
    <module>/home/curry/lib/prelude</module>
  </import>
  <types>
    <type name="nat_Nat">
      <params />
      <cons name="nat_Zero" arity="0" />
      <cons name="nat_Succ" arity="1">
        <tcons name="nat_Nat" />
      </cons>
    </type>
  </types>
  <functions>
    <func name="nat_leq" arity="2">
      <functype>
        <tcons name="nat_Nat" />
        <functype>
          <tcons name="nat_Nat" />
          <tcons name="Bool" />
        </functype>
      </functype>
      <rule>
        <lhs>
          <var>0</var>
          <var>1</var>
        </lhs>
        <rhs>
          <case type="Flex">
            <var>0</var>
            <branch>
              <pattern name="nat_Zero" />
              <comb type="ConsCall" name="True" />
            </branch>
            <branch>
              <pattern name="nat_Succ">
                <var>2</var>
              </pattern>
              <case type="Flex">
                <var>1</var>
                <branch>
                  <pattern name="nat_Zero" />
                  <comb type="ConsCall" name="False" />
                </branch>
                <branch>
                  <pattern name="nat_Succ">
                    <var>3</var>
                  </pattern>
                  <comb type="FuncCall" name="nat_leq">
                    <var>2</var>
                    <var>3</var>
                  </comb>
                </branch>
              </case>
            </branch>
          </case>
        </rhs>
      </rule>
    </func>
  </functions>
  <operators />
  <translation>
    <trans>
      <name>Nat</name>
      <intname>nat_Nat</intname>
    </trans>
    <trans>
      <name>Zero</name>
      <intname>nat_Zero</intname>
    </trans>
    <trans>
      <name>Succ</name>
      <intname>nat_Succ</intname>
    </trans>
    <trans>
      <name>leq</name>
      <intname>nat_leq</intname>
    </trans>
  </translation>
</prog>

Example 2

The second example shows the use of disjunctions, constraints and guarded rules for the translation of a function not defined by disjoint patterns. Consider the following definition written in Curry syntax:

   fs xs | xs =:= [x]                 = x  where x free
   fs xs | let y free in xs =:= [y,x] = x  where x free

Using the notation used in the abstract syntax for FlatCurry (for the sake of readability, without indexing of variables and infix notation of operators), we could translate the definition of fs into the following FlatCurry rule:

  fs xs = or(guarded([x],xs=:=[x],x)
             guarded([z],constr([y],xs=:=[y,z]),z))

Thus, the corresponding XML representation of this program is as follows (where we assume that "prog" is the name of this program):

<prog>
  <module>prog</module>
  <import>
    <module>/home/curry/lib/prelude</module>
  </import>
  <types />
  <functions>
    <func name="prog_fs" arity="1">
      <functype>
        <tcons name="[]">
          <tvar>0</tvar>
        </tcons>
        <tvar>0</tvar>
      </functype>
      <rule>
        <lhs>
          <var>0</var>
        </lhs>
        <rhs>
          <or>
            <guardedexpr>
              <freevars>
                <var>1</var>
              </freevars>
              <comb type="FuncCall" name="=:=">
                <var>0</var>
                <comb type="ConsCall" name=":">
                  <var>1</var>
                  <comb type="ConsCall" name="[]" />
                </comb>
              </comb>
              <var>1</var>
            </guardedexpr>
            <guardedexpr>
              <freevars>
                <var>2</var>
              </freevars>
              <constr>
                <freevars>
                  <var>3</var>
                </freevars>
                <comb type="FuncCall" name="=:=">
                  <var>0</var>
                  <comb type="ConsCall" name=":">
                    <var>3</var>
                    <comb type="ConsCall" name=":">
                      <var>2</var>
                      <comb type="ConsCall" name="[]" />
                    </comb>
                  </comb>
                </comb>
              </constr>
              <var>2</var>
            </guardedexpr>
          </or>
        </rhs>
      </rule>
    </func>
  </functions>
  <operators />
  <translation>
    <trans>
      <name>fs</name>
      <intname>prog_fs</intname>
    </trans>
  </translation>
</prog>

Example 3

The third example shows the translation of programs using the committed choice. In Curry, a committed choice is used in functions with the evaluation annotation choice, like in the following simplified example definition:

   m eval choice
   m [] y = y
   m x [] = x

An indeterministic function evaluated by committed choice is represented by a rule whose right-hand side is a "choice" expression and the different alternatives are represented as disjunctions. Furthermore, all rules of the original definition must be represented by a "guarded" expression after pattern matching. Operationally, a choice is evaluated by creating independent evaluation spaces for all disjunctions inside this choice until one space has satisfied its constraint of the corresponding guarded expression. Using the notation used in the abstract syntax for FlatCurry (for the sake of readability, without indexing of variables and infix notation of operators), we could translate the definition of indeterministic function m into the following FlatCurry rule:

  m x y = choice(or(case x of { [] -> guarded([],success,y) }
                    case y of { [] -> guarded([],success,x) }))

Thus, the corresponding XML representation of this program is as follows (where we assume that "prog" is the name of this program and "success" is the always satisfiable constraint):

<prog>
  <module>prog</module>
  <import>
    <module>/home/curry/lib/prelude</module>
  </import>
  <types />
  <functions>
    <func name="prog_m" arity="2">
      <functype>
        <tcons name="[]">
          <tvar>0</tvar>
        </tcons>
        <functype>
          <tcons name="[]">
            <tvar>0</tvar>
          </tcons>
          <tcons name="[]">
            <tvar>0</tvar>
          </tcons>
        </functype>
      </functype>
      <rule>
        <lhs>
          <var>0</var>
          <var>1</var>
        </lhs>
        <rhs>
          <choice>
            <or>
              <case type="Rigid">
                <var>0</var>
                <branch>
                  <pattern name="[]" />
                  <guardedexpr>
                    <freevars />
                    <comb type="FuncCall" name="success" />
                    <var>1</var>
                  </guardedexpr>
                </branch>
              </case>
              <case type="Rigid">
                <var>1</var>
                <branch>
                  <pattern name="[]" />
                  <guardedexpr>
                    <freevars />
                    <comb type="FuncCall" name="success" />
                    <var>0</var>
                  </guardedexpr>
                </branch>
              </case>
            </or>
          </choice>
        </rhs>
      </rule>
    </func>
  </functions>
  <operators />
  <translation>
    <trans>
      <name>m</name>
      <intname>prog_m</intname>
    </trans>
  </translation>
</prog>

Michael Hanus