AI Zone Admin Forum Add your forum

NEWS: Chatbots.org survey on 3000 US and UK consumers shows it is time for chatbot integration in customer service!read more..

RSS AI Zone  Forum Home  >  Development  >  AIML & other standards  >  Thread
Primitive Recursive Functions in AIML
  
 
Posted: Jan 11, 2010

Primitive Recursive Functions are a way to define elementary math functions using only a few simple operations.

Because AIML has no built-in math functions, writing simple addition and subtraction functions is a minor challenge.  Generally, for things like math functions, we would recommend breaking out of AIML and using another language through the <system> tag.  But as an exercise, you can define addition and subtraction in AIML using primitive recursive functions.

First you need to be able to count.  The function SUCCESSOR(X) returns X+1.  In AIML we can define the SUCCESSOR function with a group of categories:

<category><pattern>SUCCESSOR 0</pattern><template>1</template></category>
<category><pattern>SUCCESSOR 1</pattern><template>2</template></category>
<category><pattern>SUCCESSOR 2</pattern><template>3</template></category>
<category><pattern>SUCCESSOR 3</pattern><template>4</template></category>
<category><pattern>SUCCESSOR 4</pattern><template>5</template></category>
<category><pattern>SUCCESSOR 5</pattern><template>6</template></category>
<category><pattern>SUCCESSOR 6</pattern><template>7</template></category>
<category><pattern>SUCCESSOR 7</pattern><template>8</template></category>
<category><pattern>SUCCESSOR 8</pattern><template>9</template></category>
<category><pattern>SUCCESSOR 9</pattern><template>1 0</template></category> 

Notice that when we got to 10, we had to write the number as “1 0” rather than “10”, due to the pattern matching style of AIML.

For two digit numbers we need a special case when the last digit is 9.  We can build the SUCCESSOR function for two digits from the one-digit version:

<category><pattern>SUCCESSOR * 9</pattern>
<template><srai>SUCCESSOR <star/></srai> 0</template>
</category>

<category><pattern>SUCCESSOR * *</pattern>
<template><star/> <srai>SUCCESSOR <star index="2"/></srai>
</template>
</category> 

For three digits, we can write:

<category><pattern>SUCCESSOR * 9 9</pattern>
<template><srai>SUCCESSOR <star/></srai> 0 0</template>
</category>

<category><pattern>SUCCESSOR * * *</pattern>
<template><star/> <srai>SUCCESSOR <star index="2"/> <star index="3"/></srai>
</template>
</category> 

Now we have the ability to count from 0 to 999. 

Adding 0 to a number is the same as the number itself:

<category>
<pattern>ADD 0 PLUS *</pattern>

<template><star/></template>
</category> 

The function ADD(1, X) is the same as the function SUCCESSOR(X):

 

<category>
<pattern>ADD 1 PLUS *</pattern>

<template><srai>SUCCESSOR <star/></srai></template>
</category> 

The ADD(X,Y) function breaks down the operation of adding into a series of ADD(X, 1), repeated recursively Y times:

<category>
<pattern>ADD * PLUS *</pattern>
<template><srai>ADD 1 PLUS <srai>ADD <srai>PREDECESSOR <star/></srai> PLUS <star index="2"/></srai></srai>
</template>
</category> 
 

 
Posted: Jan 11, 2010
   [ # 1 ]

(continued from previous post due to length)

The function PREDECESSOR(X) works much like SUCCESSOR(X):

<category><pattern>PREDECESSOR 1</pattern><template>0</template></category>
<category><pattern>PREDECESSOR 2</pattern><template>1</template></category>
<category><pattern>PREDECESSOR 3</pattern><template>2</template></category>
<category><pattern>PREDECESSOR 4</pattern><template>3</template></category>
<category><pattern>PREDECESSOR 5</pattern><template>4</template></category>
<category><pattern>PREDECESSOR 6</pattern><template>5</template></category>
<category><pattern>PREDECESSOR 7</pattern><template>6</template></category>
<category><pattern>PREDECESSOR 8</pattern><template>7</template></category>
<category><pattern>PREDECESSOR 9</pattern><template>8</template></category>
<category><pattern>PREDECESSOR 1 0</pattern><template>9</template></category>
<category><pattern>PREDECESSOR * 0</pattern><template><srai>PREDECESSOR <star/></srai> 9</template></category>
<category><pattern>PREDECESSOR * *</pattern><template><star/> <srai>PREDECESSOR <star index="2"/></srai></template></category>
<category><pattern>PREDECESSOR 1 0 0</pattern><template>9 9</template></category> 

However there are some special cases when the second digit is 0:

<category><pattern>PREDECESSOR * 0 0</pattern><template><srai>PREDECESSOR <star/></srai> 9 9</template></category>
<category><pattern>PREDECESSOR * 1 0</pattern><template><star/> 0 9</template></category>
<category><pattern>PREDECESSOR * 0 9</pattern><template><star/> 0 8</template></category>
<category><pattern>PREDECESSOR * 0 8</pattern><template><star/> 0 7</template></category>
<category><pattern>PREDECESSOR * 0 7</pattern><template><star/> 0 6</template></category>
<category><pattern>PREDECESSOR * 0 6</pattern><template><star/> 0 5</template></category>
<category><pattern>PREDECESSOR * 0 5</pattern><template><star/> 0 4</template></category>
<category><pattern>PREDECESSOR * 0 4</pattern><template><star/> 0 3</template></category>
<category><pattern>PREDECESSOR * 0 3</pattern><template><star/> 0 2</template></category>
<category><pattern>PREDECESSOR * 0 2</pattern><template><star/> 0 1</template></category>
<category><pattern>PREDECESSOR * 0 1</pattern><template><star/> 0 0</template></category> 

Finally by adding the PREDECESSOR function for 3-digit numbers:

<category><pattern>PREDECESSOR * * *</pattern>
<template><star/> <srai>PREDECESSOR <star index="2"/> <star index="3"/></srai></template></category> 

we can count down from 999 to 0, and now we can define the primitive recursive subtraction function:

<category>
<pattern>SUBTRACT * MINUS 0</pattern>
<template><star/></template>
</category>

<category>
<pattern>SUBTRACT * MINUS 1</pattern>
<template><srai>PREDECESSOR <star/></srai></template>
</category>

<category>
<pattern>SUBTRACT * MINUS *</pattern>
<template>
<srai>SUBTRACT 
  <srai>SUBTRACT <star/> MINUS 
      <srai>PREDECESSOR <star index="2"/></srai>
  </srai>
      MINUS 1
</srai>
</template> 
 

 
Posted: Jan 11, 2010
   [ # 2 ]

off topic: just doubled the max length of postings to 12.000 characters.
 

 
Posted: Jan 18, 2010
   [ # 3 ]

Humans have 10d (decimal ten) fingers to count on.  In semi-conductor physics, robots have 10b (binary two)  fingers to count on.  This makes binary more efficient than decimal for robots to process.  This is why I disagree with the notion that A.I. has not progressed.  Humans are not making a fair comparison when they lack the native machine language of A.I.  so that much of its power is uptapped.

The function BINARY_REGISTER(X) returns X+1.  In AIML we can define the BINARY_REGISTER function with a group of categories:

<category><pattern>BINARY_REGISTER * 1</pattern>
<template><srai>BINARY_REGISTER <star/></srai> 0</template>
</category>

<category><pattern>BINARY_REGISTER * *</pattern>
<template><star/> <srai>BINARY_REGISTER <star index="2"/></srai>
</template>
</category>

<category><pattern>BINARY_REGISTER * 1 1</pattern>
<template><srai>BINARY_REGISTER <star/></srai> 0 0</template>
</category>

<category><pattern>BINARY_REGISTER * * *</pattern>
<template><star/> <srai>BINARY_REGISTER <star index="2"/> <star index="3"/></srai>
</template>
</category>

<category><pattern>BINARY_REGISTER 0 </pattern><template>1</template></category>
<category><pattern>BINARY_REGISTER 1</pattern><template>1 0 </template></category>
<category><pattern>BINARY_REGISTER 1 1</pattern><template>1 0 0 </template></category> 

Now we have the ability to count in binary from 0 to 111. 

Adding 0 to a binary number is the same as the binary number itself:

<category>
<pattern>ADD_BINARY 0 PLUS *</pattern>

<template><star/></template>
</category> 

The function ADD_BINARY(1, X) is the same as the function BINARY_REGISTER(X):

<category>
<pattern>ADD_BINARY 1 PLUS *</pattern>

<template><srai>REGISTER <star/></srai></template>
</category> 

The ADD_BINARY(X,Y) function breaks down the binary operation of adding into a series of ADD_BINARY(X, 1), repeated recursively Y times:

<category>
<pattern>ADD_BINARY * PLUS *</pattern>
<template><srai>ADD_BINARY 1 PLUS <srai>ADD_BINARY <srai>ADD_REGISTER <star/></srai> PLUS <star index="2"/></srai></srai>
</template>
</category> 

Note: The star indices remain in decimal for the humans.
 

 
  login or register to react
     Tracing Matches in AIML ››