help links subscribe changes refresh edit

	FriCAS Problems
Manipulating Expressions ←	↑	→ Nature of expressions

Mutual Recursion

Edit detail for Mutual Recursion revision 1 of 3

	1 2 3
Editor: 127.0.0.1 Time: 2007/11/15 20:16:40 GMT-8
Note: transferred from axiom-developer

changed:
-
Here we give two examples of defining functions by mutual recursion in Axiom

Recursion between Separate Domains

  First we show how to define two separate domains **EVEN** and **ODD**
both of which have an attribute represented by the polymorthic function
**parity**.

We must start with a "bootstrap" definition of 'parity(n)\$even'. All that
is really needed here is a package that exports a function named 'parity'
with the right signature. This particular function will never be called
and will be re-defined later. It's only purpose is as a placeholder to
allow the later definition of **ODD**.

\begin{spad}
)abbrev domain EVEN even
even(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n) == true
\end{spad}

Now we can define 'parity(n)\$odd'. It depends on **EVEN**.

\begin{spad}
)abbrev domain ODD odd
odd(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n:Integer) ==
--    output("ODD",n::OutputForm)$OutputPackage
      (n>0) => parity(n-1)$even
      (n<0) => parity(n+1)$even
      false
\end{spad}

But the bootstrap definition of **EVEN** is incomplete. It really
depends (recusively) on **ODD**. So finally we need the full
(re-)definition of 'parity(n)\$even'

\begin{spad}
)abbrev domain EVEN even
even(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n) ==
--    output("EVEN",n::OutputForm)$OutputPackage
      n>0 => parity(n-1)$odd
      n<0 => parity(n+1)$odd
      true
\end{spad}

Now we can test the new function:
\begin{axiom}
parity(10)$even
parity(8)$odd
parity(-1111)$odd
\end{axiom}

Recursion within a Single Domain

  It is possible to write this same recursion as a domain that
exports two functions **Even** and **Odd**. In this case we do not
need to supply any initial *bootstrap* code because the compiler is
able to resolve both functions simultaneously.

\begin{spad}
)abbrev domain PARITY Parity
Parity(): Exports == Implements where
  Exports == with
    Even: Integer -> Boolean
    Odd: Integer -> Boolean
  Implements == add
    Odd(n: Integer) ==
      n>0 => Even(n-1)
      n<0 => Even(n+1)
      false
    Even(n: Integer) ==
      n>0 => Odd(n-1)
      n<0 => Odd(n+1)
      true
\end{spad}

Test
\begin{axiom}
Even(10)$Parity
Odd(8)$Parity
Odd(-1111)$Parity
\end{axiom}

Here we give two examples of defining functions by mutual recursion in Axiom

Recursion between Separate Domains

First we show how to define two separate domains EVEN and ODD both of which have an attribute represented by the polymorthic function parity.

We must start with a "bootstrap" definition of parity(n)$even. All that is really needed here is a package that exports a function named parity with the right signature. This particular function will never be called and will be re-defined later. It's only purpose is as a placeholder to allow the later definition of ODD.

spad

)abbrev domain EVEN even
even(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n) == true

spad

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3342984326569348053-25px001.spad
      using old system compiler.
   EVEN abbreviates domain even 
------------------------------------------------------------------------
   initializing NRLIB EVEN for even 
   compiling into NRLIB EVEN 
   compiling exported parity : Integer -> Boolean
      EVEN;parity;IB;1 is replaced by QUOTET 
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |even| REDEFINED

;;;     ***       |even| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor even
      Time: 0 seconds

   finalizing NRLIB EVEN 
   Processing even for Browser database:
--->-->even(constructor): Not documented!!!!
--->-->even((parity ((Boolean) (Integer)))): Not documented!!!!
--->-->even(): Missing Description
; compiling file "/var/aw/var/LatexWiki/EVEN.NRLIB/EVEN.lsp" (written 14 JUL 2013 10:16:08 AM):

; /var/aw/var/LatexWiki/EVEN.NRLIB/EVEN.fasl written
; compilation finished in 0:00:00.012
------------------------------------------------------------------------
   even is now explicitly exposed in frame initial 
   even will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/EVEN.NRLIB/EVEN

Now we can define parity(n)$odd. It depends on EVEN.

spad

)abbrev domain ODD odd
odd(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n:Integer) ==
--    output("ODD",n::OutputForm)$OutputPackage
      (n>0) => parity(n-1)$even
      (n<0) => parity(n+1)$even
      false

spad

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/7392352806104595030-25px002.spad
      using old system compiler.
   ODD abbreviates domain odd 
------------------------------------------------------------------------
   initializing NRLIB ODD for odd 
   compiling into NRLIB ODD 
   compiling exported parity : Integer -> Boolean
Time: 0.01 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |odd| REDEFINED

;;;     ***       |odd| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor odd
      Time: 0.01 seconds

   finalizing NRLIB ODD 
   Processing odd for Browser database:
--->-->odd(constructor): Not documented!!!!
--->-->odd((parity ((Boolean) (Integer)))): Not documented!!!!
--->-->odd(): Missing Description
; compiling file "/var/aw/var/LatexWiki/ODD.NRLIB/ODD.lsp" (written 14 JUL 2013 10:16:08 AM):

; /var/aw/var/LatexWiki/ODD.NRLIB/ODD.fasl written
; compilation finished in 0:00:00.012
------------------------------------------------------------------------
   odd is now explicitly exposed in frame initial 
   odd will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/ODD.NRLIB/ODD

But the bootstrap definition of EVEN is incomplete. It really depends (recusively) on ODD. So finally we need the full (re-)definition of parity(n)$even

spad

)abbrev domain EVEN even
even(): E == I where
  E == with
    parity: Integer -> Boolean
  I == add
    parity(n) ==
--    output("EVEN",n::OutputForm)$OutputPackage
      n>0 => parity(n-1)$odd
      n<0 => parity(n+1)$odd
      true

spad

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8584362905457126194-25px003.spad
      using old system compiler.
   Illegal NRLIB 
   EVEN.NRLIB claims that its constructor name is the domain even but 
      even is already known to be the for package EVEN .
   EVEN abbreviates domain even 
------------------------------------------------------------------------
   initializing NRLIB EVEN for even 
   compiling into NRLIB EVEN 
   compiling exported parity : Integer -> Boolean
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |even| REDEFINED

;;;     ***       |even| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor even
      Time: 0 seconds

   finalizing NRLIB EVEN 
   Processing even for Browser database:
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3342984326569348053-25px001.spad-->even(constructor): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3342984326569348053-25px001.spad-->even((parity ((Boolean) (Integer)))): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/3342984326569348053-25px001.spad-->even(): Missing Description
; compiling file "/var/aw/var/LatexWiki/EVEN.NRLIB/EVEN.lsp" (written 14 JUL 2013 10:16:08 AM):

; /var/aw/var/LatexWiki/EVEN.NRLIB/EVEN.fasl written
; compilation finished in 0:00:00.010
------------------------------------------------------------------------
   even is already explicitly exposed in frame initial 
   even will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/EVEN.NRLIB/EVEN

Now we can test the new function:

fricas

parity(10)$even

$\label{eq1} \mbox{\rm true}$

(1)

Type: Boolean

fricas

parity(8)$odd

$\label{eq2} \mbox{\rm false}$

(2)

Type: Boolean

fricas

parity(-1111)$odd

$\label{eq3} \mbox{\rm true}$

(3)

Type: Boolean

Recursion within a Single Domain

It is possible to write this same recursion as a domain that exports two functions Even and Odd. In this case we do not need to supply any initial bootstrap code because the compiler is able to resolve both functions simultaneously.

spad

)abbrev domain PARITY Parity
Parity(): Exports == Implements where
  Exports == with
    Even: Integer -> Boolean
    Odd: Integer -> Boolean
  Implements == add
    Odd(n: Integer) ==
      n>0 => Even(n-1)
      n<0 => Even(n+1)
      false
    Even(n: Integer) ==
      n>0 => Odd(n-1)
      n<0 => Odd(n+1)
      true

spad

   Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/2188084076688500475-25px005.spad
      using old system compiler.
   PARITY abbreviates domain Parity 
------------------------------------------------------------------------
   initializing NRLIB PARITY for Parity 
   compiling into NRLIB PARITY 
   compiling exported Odd : Integer -> Boolean
Time: 0 SEC.

   compiling exported Even : Integer -> Boolean
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |Parity| REDEFINED

;;;     ***       |Parity| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor Parity
      Time: 0 seconds

   finalizing NRLIB PARITY 
   Processing Parity for Browser database:
--->-->Parity(constructor): Not documented!!!!
--->-->Parity((Even ((Boolean) (Integer)))): Not documented!!!!
--->-->Parity((Odd ((Boolean) (Integer)))): Not documented!!!!
--->-->Parity(): Missing Description
; compiling file "/var/aw/var/LatexWiki/PARITY.NRLIB/PARITY.lsp" (written 14 JUL 2013 10:16:08 AM):

; /var/aw/var/LatexWiki/PARITY.NRLIB/PARITY.fasl written
; compilation finished in 0:00:00.016
------------------------------------------------------------------------
   Parity is now explicitly exposed in frame initial 
   Parity will be automatically loaded when needed from 
      /var/aw/var/LatexWiki/PARITY.NRLIB/PARITY

Test

fricas

Even(10)$Parity

$\label{eq4} \mbox{\rm true}$

(4)

Type: Boolean

fricas

Odd(8)$Parity

$\label{eq5} \mbox{\rm false}$

(5)

Type: Boolean

fricas

Odd(-1111)$Parity

$\label{eq6} \mbox{\rm true}$

(6)

Type: Boolean