/prog/ challenge redux

Create a LISP program that generates random LISP programs.

No two runs of the program should generate the same code.

Generated code must be VALID LISP and should (given random input) return a value without throwing errors in such a way that the same input always returns the same output.

I make one in C OMG OPTIMIZED


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

#define MAX_LEN 9000

int main()
{
  int num_brackets;
  int i;

  srand(time(0));
  num_brackets = rand() % MAX_LEN;

  for (i=0; i<num_brackets; i++) {
    putchar((rand() & 1) == 1 ? '(' : ')');
  }
  putchar('\n');
  return 0;
}

No two runs of the program should generate the same code.
That seems difficult if not impossible because seeds are of fixed length (unless you want to use some bignum, for example keyed on time) and thus there is a finite amount of possible programs to generate. If you relax the requirement as a program being seeded by a bigint returning a deterministic program output.
You also need to define better what 'random input' represents (depends on Lisp dialect and how input is given and its type/format).
Leaving that aside, it seems rather trivial to make a random code generator, however there's a simpler solution: define a VM which cannot access anything external (and thus no source of randomness), interpret bignum input as a binary/compiled program written for that VM, throw some error handler (or just make VM incapable of crashing) around it.

>>3
It's impossible because generating an infinite stream of unique random numbers is impossible.  I'm sure OP meant to say that each unique seed should generate a unique program.

(define (random-program) `(display (+ (read) ,(random))))

I almost want to sketch out a program of the halting solver. I always wondered, the answer for a FINITE problem solver which is feed infinite code is that no, it can't determine an infinite input, but by definition, since a finite problem solver will eventually find in random code an infinite problem solver, doesn't this mean that the finite problem solver does find a solution to all programs in finite time?

>>4
generating an infinite stream of unique random numbers is impossible.
because "infinity" doesnt exist?

>>7
Yes

>>6
Definitions don't do well with notions such as infinity