|
Generativity Thought Experiment |
|
|
|
Suppose I want to generate something, maybe: |
|
- a number |
|
- a string |
|
- a list of numbers |
|
- a set of parameters that define a 3d model |
|
- a game level |
|
- a poem |
|
- a story |
|
- a 3d-model of a creature |
|
- a recipe for a tasty meal |
|
- an attractive painting |
|
|
|
If any of the later examples are meant to be represented by a computer, |
|
then they ought to be enumerable, i.e. mappable onto the set of natural |
|
numbers. Then generating a good one just becomes a question of generating |
|
the "right" number. :) Of course, representation is everything. |
|
|
|
So let's talk first about how to generate that number. Of course I don't |
|
want just *any* number: I want it to be an integer, and it must be at least |
|
1 and at most 6. |
|
|
|
At a constraint logic programming or other prolog-ish REPL i could do: |
|
|
|
Input: X : X >= 1, X <= 6, integer(X) |
|
Output: 4 |
|
|
|
Or maybe I want to be more explicit about the generator's choices: |
|
Input: {1, 2, 3, 4, 5, 6} |
|
Output: 4 |
|
|
|
Or maybe the generator can be more explicit about its expressive range: |
|
Input: X : X >= 1, X <= 6, integer(X) |
|
Output: {1, 2, 3, 4, 5, 6} |
|
|
|
We could even potentially handle uncountable sets... |
|
Input: X : X >= 1, X <=6, real(X) |
|
...as long as we sample from a countable subset: |
|
Ouput: ?x1 : <RANGE 1..6> |
|
Input: ?x1.sample(1, dist=uniform, precision=.01); |
|
Ouput: 2.57 |
|
|
|
Strings can work similarly. We're humans, so instead of Goedel-numbering |
|
our strings let's describe them with grammars. |
|
|
|
And of course I want not just *any* string, but specifically strings of As |
|
and Bs that are palindromes. |
|
|
|
Input: X : X = "" | A | B | A <X> A | B <X> B |
|
Output: |
|
AABBBAA |
|
Or, output: |
|
?x1 : <GRAMMAR X = "" | A | B | A <X> A | B <X> B> |
|
Query: ?x1.sample(3, dist=uniform_by_level) |
|
Output: {B, AAA, BABBAB} |
|
Query: ?x1.enumerate(4, breadth_first, fn x => length x >= 2) |
|
Output: {AA, BB, AAA, BAB} |
|
|
|
And, hey, I can describe poems as grammars over strings, right? Or at least |
|
an interesting subset of strings. |
|
|
|
set POEM(a,b) = AB(a,b,N)* | N=1..6 |
|
set AB(a,b,n) |
|
= (p1:PHRASE) RHYME(A) "\n" (p2:PHRASE) RHYME(B) |
|
: syllables(p1) = syllables(p2) = N |
|
set RHYME(X) = {x | rhyme(x, X)} |
|
rhyme("foo", "moo"), rhyme("hair", "there"), ... |
|
rhyme(X,Y) <- rhyme(Y,X). |
|
syllables(butter) = 2. |
|
syllables(scotch) = 1. |
|
syllables(dog) = 1. |
|
syllables(word::phrase) = W + P |
|
<- syllables(word) = W |
|
<- syllables(phrase) = P. |
|
|
|
Query: POEM(dire,knowing) |
|
Output: butter scotch fire |
|
nothing all going |
|
call dog for liar |
|
turning cell snowing |
|
Query: POEM(X,Y) : X:word, Y:word |
|
Output: X=log, Y=pants |
|
off nog |
|
no ants |
|
your dog |
|
a glance |
|
sure sog |
|
doze ants |
|
|
|
As for a pretty painting or a cute monster, maybe I don't want to literally |
|
describe the output (e.g. 2d or 3d image) that I want to see, but generate |
|
an intermediate representation (e.g. array of floats). |
|
|
|
I could describe that intermediate representation in this way and also |
|
provide a mapping between it and my final ouput (i.e. a rendering |
|
function). If this rendering fn is written in the same setting, then I can |
|
describe constraints to my generator in terms of properties of the rendered |
|
output. This activity is not dissimilar from relating a piece of source |
|
code to its compiled machine instructions, something that users of proof |
|
assistants like Agda or Coq do regularly. |