Randomization

[darcey]

It would be nice if Dyna had some kind of randomization, so students could play around with generating random ngram sentences.

[jeisner]

Grepping the examples directory for rand, I see that Tim used something in force.dyna, like this:

% randomly initialize node positions.
x("a",0) += uniform(0,1).  y("a",0) += uniform(0,1).
x("b",0) += uniform(0,1).  y("b",0) += uniform(0,1).
x("c",0) += uniform(0,1).  y("c",0) += uniform(0,1).

However, I don't understand how that is compatible with the semantics of Dyna: if uniform(0,1) is a term, then it should only have a single value in a given fixpoint of the program.

I also don't understand how it is implemented. For example, if it were backward chained and memoized, then it would have the same value every time. Perhaps it's currently like a special literal, similar to 0.6 or "hello world" but with a value that is chosen randomly when the literal is read in by the Dyna parser? But then we wouldn't get

:- query uniform(0,1)
    0.18774785536950045 is uniform(0,1)

[timvieira]

uniform is a complete disregard of dyna's randomization semanitcs. It's just an foreign function. From what I recall dyna's random semantics sets edge's randomseed to a gensim-type value for that edge is that right?

@nwf what do I need to do to get gensyms up and running? We can already "name hyperedges". What else?

Does Dyna's FFI semanics treat foreign functions like it treats random functions? I'm not totally sure what I mean with this question... ugh... do we memoize FFI calls, e.g. a += ff(0,1). stores the invocation to ff as and entry in a memo table: ffi(hyperedgename, function name, arguments..)?

On Fri, Jun 28, 2013 at 11:22 AM, Jason Eisner notifications@github.comwrote:

Grepping the examples directory for rand, I see that Tim used something in force.dyna, like this:

% randomly initialize node positions. x("a",0) += uniform(0,1). y("a",0) += uniform(0,1). x("b",0) += uniform(0,1). y("b",0) += uniform(0,1). x("c",0) += uniform(0,1). y("c",0) += uniform(0,1).

However, I don't understand how that is compatible with the semantics of Dyna: if uniform(0,1) is a term, then it should only have a single value in a given fixpoint of the program.

I also don't understand how it is implemented. For example, if it were backward chained and memoized, then it would have the same value every time. Perhaps it's currently like a special literal, similar to 0.6 or "hello world" but with a value that is chosen randomly when the literal is read in by the Dyna parser? But then we wouldn't get

:- query uniform(0,1) 0.18774785536950045 is uniform(0,1)

— Reply to this email directly or view it on GitHubhttps://github.com/nwf/dyna/issues/26#issuecomment-20194729 .

[jeisner]

My view is that a foreign function is under contract to always return the same value for the same inputs, because it's just telling you the value of an item like cos(3.14159) -- in fact an item that doesn't depend on other items (hence is const).

So a random foreign function can choose a random number, but it is up to the foreign random function to memoize that number and return it again if called with the same arguments, because that is what the contract requires.

An alternative to memoization is to use an appropriate hash of the arguments where the hash function is random. This only requires enough storage to save the parameters of the hash function (analogous to a random seed).

If the same .dyna file is loaded and queried by two different processes, it should possibly get the same random numbers, but we could look the other way on that for now.

Anyway, to get different random numbers, we have used constructs like uniform(*,0,1) where * denotes a gensym. This means that different call sites that say uniform(*,0,1) do have different arguments and therefore can have different values.

We think that once we have dynabases, we can probably use new uniform(0,1) rather than uniform(*,0,1) since each dynabase is a unique little snowflake just like a gensym -- we do need to work out some details.

[timvieira]

Very cool. Thanks for the explanation!

On Fri, Jun 28, 2013 at 4:38 PM, Jason Eisner notifications@github.comwrote:

My view is that a foreign function is under contract to always return the same value for the same inputs, because it's just telling you the value of an item -- in fact an item that doesn't depend on other items (hence is const).

We have used constructs like uniform(,0,1) where * denotes a gensym. This means that different call sites that say uniform(,0,1) do have different arguments and therefore can have different values.

To adhere to the contract, a random function can choose a random number, but it is up to the random function to memoize that number and return it again if called with the same arguments.

An alternative to memoization is to use an appropriate hash of the arguments where the hash function is random. This only requires enough storage to save the parameters of the hash function (analogous to a random seed).

If the same .dyna file is loaded and queried by two different processes, it should possibly get the same random numbers, but we could look the other way on that for now.

We think that once we have dynabases, we can probably use new uniform(0,1)rather than uniform(*,0,1) since each dynabase is a unique little snowflake just like a gensym -- we do need to work out some details.

— Reply to this email directly or view it on GitHubhttps://github.com/nwf/dyna/issues/26#issuecomment-20212909 .

[timvieira]

@nwf What do we need to do to get this flying?

[jeisner]

First thing we'd need is gensyms, I think, so I posted that as #43.