/* pidgin.c - Copyright (c) 1999 by Gary William Flake.  All rights
   reserved.  Permission is granted to use this code for any purpose
   provided that the author's comments are left intact. */

/* This program demonstrates the most ridiculous method for computing
   primes.  It uses only unsigned recursive functions, increment (++),
   decrement (--), if, return, and 0.  Also, a single printf() is used
   for output, but that's it.

   The interesting thing is that this subset of C is Turing complete.
   So whatever can be done on a general purpose computer can also be
   done in this primitive C.  In fact, it wouldn't be too difficult to
   show that this subset of C is trivially identical to the general
   recursive functions; but that's left as an exercise for the reader
   ;-).  */

/* Compile with: cc -O2 -o pidgin pidgin.c */

#include <stdlib.h>
#include <stdio.h>

/* GCC under linux reserves 'div' so I am using the define below to
   shut it up. */

#define div xdiv

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Increment an unsigned integer */

unsigned inc(unsigned x)
{
  return ++x;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Decrement an unsigned integer if it is nonzero; otherwise, return
   zero. */

unsigned dec(unsigned x)
{
  if (x) return --x;
  return 0;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Boolean AND:  Nonzero means TRUE and zero means FALSE. */

unsigned and(unsigned x, unsigned y)
{
  if (x)
    if (y)
      return inc(0);
  return 0;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Boolean OR:  Nonzero means TRUE and zero means FALSE. */

unsigned or(unsigned x, unsigned y)
{
  if (x)
    return inc(0);    
  if (y)
    return inc(0);
  return 0;
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Boolean NOT:  Nonzero means TRUE and zero means FALSE. */

unsigned not(unsigned x)
{
  if (x) return 0;
  return inc(0);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Equality test for unsigned number: return value is nonzero for TRUE
   and zero for FALSE. */

unsigned equal(unsigned x, unsigned y)
{
  /* Exactly one parameter being nonzero implies they are not equal. */
  if (or(and(not(x), y), and(x, not(y)))) return 0;

  /* If both are zero, then they are equal. */
  if (and(not(x), not(y))) return inc(0);

  /* Recursively try equal(x-1, y-1). */
  return equal(dec(x), dec(y));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Positive integer addition. */

unsigned add(unsigned x, unsigned y)
{
  /* Use additive identity rule: (x + 0) = x. */
  if (not(y)) return x;

  /* Recursively use x + y = x + (y + 1 - 1) = 1 + (x + (y - 1)) */
  return inc(add(x, dec(y)));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Positive integer subtraction that is only defined for positive 
   results. */

unsigned sub(unsigned x, unsigned y)
{
  /* Use subtractive identity rule: (x - 0) = x. */
  if (not(y)) return x;

  /* Recursively use x - y = (x + 1 - 1) - (y + 1 - 1) = (x - 1) - (y - 1) */
  return sub(dec(x), dec(y));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Positive multiplication. */

unsigned mul(unsigned x, unsigned y)
{
  /* Catch x * 0 case. */ 
  if (not(y)) return 0;

  /* Recursively use x * y = x * (y - 1 + 1) = x * (y - 1) + x */
  return add(x, mul(x, dec(y)));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Positive integer division. */

unsigned div(unsigned x, unsigned y)
{
  /* Only allow positive divisor. */
  if (sub(y, x)) return 0;

  /* Recursively  use x / y = (y + x - y) / y = 1 + (x - y) / y */
  return inc(div(sub(x, y), y));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Modulus operator. */

unsigned mod(unsigned x, unsigned y)
{  
  /* If y is zero or one, return 0. */
  if (or(not(y), not(dec(y)))) return 0;
  /* Handle the simple case of x < y with x % y = x. */
  if (sub(y, x)) return x;
  /* Recursively use x % y = (x - y) % y. */
  return mod(sub(x, y), y);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Positive integer exponentiation. */

unsigned pow(unsigned x, unsigned y)
{
  /* Handle case for x^0 = 1. */
  if (not(y)) return inc(0);
  /* handle case for x^1 = x. */
  if (not(dec(y))) return x;
  /* Recursively use x^y = x * x^(y-1). */
  return mul(x, pow(x, dec(y)));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Everything below is specific to the task of enumerating prime 
   numbers. */

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Loops over all integer divisors needed to test the candidate
   number.  If any one divisor evenly divides the candidate, then
   we know the number is not prime.  But if the candidate passes
   for the supplied divisor, we may need to check the next smallest. */

unsigned prime_tester(unsigned candidate, unsigned divisor)
{

  /* Return with TRUE if divisor is 1 because this means that we have
   * passed all tests from 2 ... candidate / 2.
   */
  if (not(dec(divisor))) return inc(0);

  /* If candidate % divisor = 0, then this number is not prime. */
  if (not(mod(candidate, divisor))) return 0;

  /* Recursively check divisor - 1. */
  return prime_tester(candidate, dec(divisor));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Return nonzero if x is a prime number. */

unsigned prime(unsigned x)
{
  /* The call below has a second argument of x / 2.  The second
   * argument is the number of tests yet to be performed in order to
   * guarantee that the first argument is prime.
   */
  return prime_tester(x, div(x, inc(inc(0))));
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Loop over a bunch of primes, printing them out. */

unsigned prime_lister(unsigned candidate, unsigned remaining)
{
  /* All done, yeah! */
  if (not(remaining)) return 0;

  /* This number is prime, so print it out. */
  if (prime(candidate)) {
    printf("%d\n", candidate);
    /* Loop again, with the next candidate being incremented, and
     * the number remaining to display being decremented.
     */
    return prime_lister(inc(candidate), dec(remaining));
  }

  /* This candidate failed, so try the next one. */
  return prime_lister(inc(candidate), remaining);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* List the first count primes. */

unsigned list_primes(unsigned count)
{
  /* The first argument is where we start test for primality. */
  return prime_lister(inc(inc(0)), count);
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

/* Our main function lists the first 100 prime numbers. */

int main(int argc, char **argv)
{
  return list_primes(pow(inc( /* 1 + 3 * 3 = 10 */
			     mul( /* 3 * 3 = 9 */
				 inc(inc(inc(0))),   /* 3 */
				 inc(inc(inc(0))))), /* 3 */
			 inc(inc(0)) /* 2 */
			 )); /* (1 + 3 * 3) ^ 2 = 10 ^ 2 = 100 */
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */