unified field theory!

unified field theory!

[stefan]

Hi,

I)
I did introduce prompts to the example unify code, and the comparison 
resulted in
no-prompt     :  37ms
gp-prompt     :  35ms
guile-prompts :  49ms

I think using guile prompts are acceptable here. But they are on the expensive 
side, especially in the light that unwinding should not put a significan
mark on the timings.

II)
unify variables and fluid variables are close in nature. So it would be cool
to understand the difference better. i will dive in on that. 

III)
One cool thing is to abstract out matchers. As a result you get a little tool
to create top down parsers. here we go, consider

(udef <i> (((? integer? X) . L) (cons X  L)
	   (L                   (cons #f L))))

A matcher for an integer!

the output of a matcher has to be of the from (cons Val Rest). when Val 
equals #f it sends the signal of a failure. (perhaps use (values Val Rest) 
instead)

now we can use this as
(udef f ((<i> <i> 'a 'b) 'ok)) 

and 

(f '(1 2 a b)) will match to 'ok

But it's really nice to have arguments to the matcher so consider

(udef <...> ((F   (  (<> F)   (<...> F)  )  (cons (cons F.0 <...>.0) 
						  <...>...))
	     (F    L                        (cons '() L))))

F.0   is the value of the (<> F) match. F... is the rest of the same match and
so on. Now <...> is a gready matcher that has one argument F that itself is 
a matcher and now we can use it accordingly. if a symbol looks like <symb>
then it's a matcher abstraction. (<> F) is used when the matcher has a name
not of that form.

(udef f ((   (<...> <i>) . L)  L))

and

(f '(1 23 4 a b)) 

gives

'(a b)

Have fun,

Stefan

Re: unified field theory!

[Andy Wingo]

Hi Stefan,

On Sun 23 May 2010 16:52, stefan <stefan.tampe@spray.se> writes:

> I did introduce prompts to the example unify code, and the comparison 
> resulted in
> no-prompt     :  37ms
> gp-prompt     :  35ms
> guile-prompts :  49ms
>
> I think using guile prompts are acceptable here. But they are on the expensive 
> side, especially in the light that unwinding should not put a significan
> mark on the timings.

Good news that it's OK, and agreed that it's on the expensive side; but
this may be fixed in Guile.

(For example, we could (and probably should) maintain the dynamic
context as a proper stack rather than a consed list. This has the same
performance tradeoffs that heap frames versus stack frames have,
regarding continuations; but the advantages to the normal case are more
important. In addition some prompts and aborts may be reduced to normal
control flow at compile time. This is a parenthetical note, due to the
tangential relevance to your code.)

> II)
> unify variables and fluid variables are close in nature. So it would be cool
> to understand the difference better. i will dive in on that. 

Interesting question. Please let us know of your results.

> III)
> One cool thing is to abstract out matchers. As a result you get a little tool
> to create top down parsers. here we go, consider
>
> (udef <i> (((? integer? X) . L) (cons X  L)
> 	   (L                   (cons #f L))))
>
> A matcher for an integer!

All of this is very stimulating! Perhaps even more so for someone as
ignorant as myself, as I have more to learn.

It does seem that you are nearing a point where your code can be
generally useful. What do you think about starting a project on savannah
or gitorious, and tracking your code in git, together with these test
cases? If you are not familiar with the process, we can help you out. It
would be interesting to follow your hackings.

Cheers,

Andy
-- 
http://wingolog.org/

Re: unified field theory!

[stefan]

> It does seem that you are nearing a point where your code can be
> generally useful. What do you think about starting a project on savannah
> or gitorious, and tracking your code in git, together with these test
> cases? If you are not familiar with the process, we can help you out. It
> would be interesting to follow your hackings.
> 
> Cheers,
> 
> Andy
> 

I put a clone of guile up on gitorious, 
  
  http://gitorious.org/guile-unify/

Now, the code performs but and is fragile and hacky. I will put in my stuff 
there and then try to transform the hacks into somehting acceptable.

Have fun

Stefan

fluids and unification

[Stefan]

Hi,

I've gone through the code for fluids to understand it. And how it relates to unification variables.

Some facts for fluids:
*	Allocation is slow, can be made faster but still it seams to be slow
		-	Allocates on the heap
		-	uses a mutex
		-	scans a list of fluid numbers from the beginning to find the next free one

*	Fluid numbers are used to lookup the meaning of a fluid under a context meaning that
	each context keep a translation table.


So fluids can be used for unification variables but it will be unpractically slow because new
variables are very often created. 

The current unification variables
*	Allocation is stack-like, but the stack is separate.
*	local variables to a thread e.g. not meant to be shared between threads.
*	keep an undo array. of the form (id val1 id2 val2 ....) and having the frames point into this
        list and at unwinding walk the list backwards and revert the variables.
*      fast to do lookup, e.g. less indirections then fluids.


So, it would be cool to make fluids allocate faster and also make unify variables be able to 
be shared between threads. Comments?

Regards
Stefan

Re: fluids and unification

[Andy Wingo]

Hi,

On Wed 26 May 2010 13:16, Stefan <stefan.tampe@spray.se> writes:

> I've gone through the code for fluids to understand it. And how it relates to unification variables.
>
> Some facts for fluids:
> *	Allocation is slow, can be made faster but still it seams to be
> slow

Indeed; you don't want to be allocating new fluids during the course of
e.g. calling a function. You probably just want to use one fluid, and
have that fluid contain the set of already-seen patterns, or the current
unification state, or something...

> The current unification variables
> *	Allocation is stack-like, but the stack is separate.

For example, hold the stack pointer in the fluid.

> So, it would be cool to make fluids allocate faster

Tricky; I looked at this and it's hard, for various reasons. Better to
rearchitect and figure out how to use a small number of fluids instead.

> and also make unify variables be able to be shared between threads.

Really? Are you sure you want this? :)

Andy
-- 
http://wingolog.org/