tampe is currently certified at Journeyer level.

Name: Stefan Israelsson Tampe
Member since: 2007-10-09 20:16:39
Last Login: 2015-05-23 17:52:30

FOAF RDF Share This

No personal information is available.

Projects

Recent blog entries by tampe

Syndication: RSS 2.0
22 May 2015 (updated 22 May 2015 at 22:40 UTC) »

again forward chaining

Hi people!

I was playing with guile log and the prolog theirin to introduce forward chaining building up databases and lookup tables. So let's go on to a nice examples in graph theory.

Consider the problem with a huge graph, but the graph consists of clusters and don't have
much arrows going between the clusters. Also the number of clusters are not that large and the individual clusters are not that large. The task is to setup an effective system that calculates a maping from one node to the next globally if there is a chain linking them. So what you can do is to calculate a lookup table for the individual cluster and also a relational mapping of the cluster themslf. We also need to map the individual interface nodes.

The inteface of library(forward_chaining) is as follows. There is a directive set_trigger/1 that defines the name of the trigger function that will be calculated. Then this atom will be used in consequent rules defining a forwars chaining indicated with =f> as an operator that is similart to :- , --> etc in prolog. Also the mappings will be effectively stored in lookup tables in dynamic predicates, so one need to declare those as well, the prelude is therefore,


:- use_module(library(forward_chaining)).

:- set_trigger(t).

:- dynamic(arrow/2).
:- dynamic(parent/2).
:- dynamic(parrow/2).
:- dynamic(interface/4).

Now for the rules,


arrow(X,Y),parent(X,XX),parent(Y,YY) =f>
{XX==YY} -> parrow(X,Y) ;
(parrow(XX,YY),interface(X,Y,XX,YY)).

This rule will maintain databases arrow/2 of arrows introduced, parent/2 a database
of cluster relations and as a conequence if the clusters are the same make a parrow/2 relation
or parraw/2 and interface/4 relation. The parrow is goverend by the transitive law


parrow(X,Y),parrow(Y,X) =f> parrow(X,Z).

parrow(X,Y) will tell if Y can be gotten from X inside
the same cluster and
parrow(XX,YY) will tell if YY cluster can be gotten from the XX but not nessesary. (This is
used to cut off branches later)

That''s the forward chaining part, we make some custom functions to add data to the database e.g.


set_arrow(X,Y) :- fire(t,arrow(X,Y)).
set_parent(X,Y) :- fire(t,parent(X,Y)).

You issue these functions for each arrow relation and cluster relation in the system. And the databases will be setuped just fine through the triggering system inherent in forward chaining.

The meat


'x->y?'(X,Y) :-
parent(X,XX),parent(Y,YY),
XX== YY -> parrow(X,Y) ; i(X,Y,XX,YY).

this is plain backward chaining, not defining any databases. We just dispatch depending if the clusters are the same or not. If they are the same, it's a microsecond away in the lookup table of
parrow/2, else we dispatch to i. i is interesting, here it is:


i(X,Y,XX,YY) :-
parrow(XX,YY),
(
(interface(Z,W,XX,YY),parrow(X,Z),parrow(W,Y)) ;
interface(Z,W,XX,ZZ),parrow(X,Z),i(W,Y,ZZ,YY)
).

Well XX must relate to YY aka parrow/2. But that is just a rough estimate, a hash value, if they are the same we must do more work. we first try to go to an interface node directly from XX to YY via interface Z,W. for all of those we try to match a parrow/2 lookup as it is defined whithin the same cluster but that may fail and then we try to jump to via an intermediate cluster.

An lookup table for the whole global system is expensive memory wize and you easy blow
guile-log's limit of 10000 elements in the database. But the lookup tables for these systems are very hardly optimized for fast lookup. Now just doing the lookup tables for the individual clusters
will make it scalable for larger system then if these tricks where not used. I find this system is
a nice middle ground between creating gigantic lookup tables and do eveythng in searches that
can take quite some time.

have fun!!!

25 Apr 2015 (updated 25 Apr 2015 at 15:14 UTC) »

The escape of the batch curse

Consider the following problem, assume that we can generate two random sequences l1,l2 of numbers between 0 and 9, take a transform that to each number map it to the length of when it appears again modulo 10, call this map M. Max be the transform of a sequence by taking the max of the current value and the next. Let Plus be the summation of two such sequences modulo 10. we also assume that we now that the second sequence, l2 has the property that elementwize,


Max(M(l1)) .leq. Max(M(l2)),

how do we go about to generate


M(Plus(Max(M(l1)),Max(M(l2)))).

The idea of the solution I would like to play with is to generate a special variable, that when you create it, the value is not known, but you can place it in the right order and then when it's all it's dependants are available the result will be executed. I've played with these ideas a long time a ago here on this blog, but now there is the addition of backtracking that come into play and that we use guile-log and prolog. So what is the main trick that enables this.

Define two predicates, delay and force that is used as follows


plusz(Z,X,Y) :- delay(plusz(Z,X,Y),X,Y) ;
(ZZ is X + Y, force(Z,ZZ)

we want to take the addition of X and Y, if X and Y both have been forced dealy will fail, else it will delay the evaluation of plusz(Z,X,Y) and execute that function at the time when both have been forced, to put the value in Z we need to execute special code to force the value if Z as well have been blessed as a delayed value. That's it, its defined in about 50 rows of guile-log code, nothing huge.

The setup to generate sequence is to maintain state and define transforms that initiate the state and update the state, given such transforms one have enough to generate the sequence, so one need to make sense of the following ideoms


next(S,SS) :- ..
start(S) :- ..

Lets see how it can look for our example in prolog,


next_all2([Z1,Z2,Id,S1,S2,Z],[ZZ1,ZZ2,IId,SS1,SS2,ZZ]) :-
next_M(Z1,[R1,P1,C1|_],ZZ1),
next_M(Z2,[R2,P2,C2|_],ZZ2),
moving_op(2,maxz,0,U1,C1,S1,SS1),
moving_op(2,maxz,0,U2,C2,S2,SS2),
fail_if(P2,(U1 .leq. U2)),
plus10z(C, U1 ,U2),
next_M(Z,[_,_,CZ|_],ZZ),
plusz(IId,Id ,C),
writez(_,IId,C,R1,R2).



next_M(Z,X,ZZ)

next_M(Z,X,ZZ), will be the seuence M(l), e.g. it's a construct that generate state information Z->ZZ with the current value X=[l_i,M(l)_i,Redo ...], with l_i the i'th generated random value, M(l)_i the number of times it takes befor l_i appear again in the sequence modulo 10, and Redo will be the backtracking object so that everything restarts from the generation of random value l_i.


moving_op(N,Op,InitSeed,MaxRes,ValIn,S,SS)

N is the length of the window, Op is the reducing operator op(Z,X,Y), InitSeed is the initial value of the reduction. MaxRes is the current result of e.g. the max operation on the window perhaps delayed, ValIn is the value in the sequence S state in and SS is the state out.


fail_if(P,(U1 .leq. U2),U1,U2)

when U1 and U2 have been forced and U1


plus10z(C, U1 ,U2),


plus modulo 10 of Max(M(l1) and Max(M(l2))


plusz(IId,Id ,C),

This is a convolution of the generation of solutions C, the result IId_i will be non delayed if and only if when all C_k k


writez(_,IId,C,R1,R2).

Write out the result C and the R1 and R2 generated random valued for l1 and l2.

As you see this approach make sure the combination of values are in the right synchronization and that the solution allow to destruct the problem in reusable more abstract components that one quite easy sew together, that's the power of this idea, you want to change the algorithm, easy to do, the number of buggs will be smaller due to the composability of the approach, neat! Also this approach will be memory safe due to the neat gc that guile-log has regarding logical variables so everything would work on as long sequences that you are prepared to wait for.

Cheers!

26 Jan 2015 (updated 26 Jan 2015 at 18:24 UTC) »

Swipify of guile-log and theory

Most of my continuation of working with guile-log has payed itself off. I can now compile and run quite many modules from the open source swi prolog engine. Atm I'm working with getting clpfd integer solver over finite domains module working. It is not easy the compilation takes 5 minutes and you need to recompile to find bugs. But a solution will come in the end. The most difficult part was to get prolog macros e.g. expansion of prolog code using prolog hooks. The system was not designed for these, it was designed to use the scheme macro expansion. So the solution is a bit clumsy.

I think I managed to fix the negation issue with tablating and a ton of technology semantics is copied from the swi prolog engine. This means that in the next release you will get quite good possiblities to try out guile-log's features on your own prolog code. Oh the compilation is slow, but the actual execution of code is just 10x slower then swi prolog. This can be noticable, on the other hand the fetures you have can enable you to escape from exponential complexity issues so it might be a win still, especially if you can make use of guile-log's internal data structures.

I am following black light powers work to make use of Mills theory of everything concept, called GUTCP. He has a freely downloadable book, from his web page and I recommend anybody knowledgeable in math to sip through it. He does explain how everything works and deduces 100's of constants for atom and particle physics just out of the classical maxwell equation and the condition that there is a source field that hinders radiation to remove energy from particles. To see all this for yourself my general reading suggestion to verify the power of his theory is to start with the conclusion of the derivation of the g-factor, see wikipedia and work yourself towards the basic assumptions. The conclusion states that an amazing number of digits are correctly calculated just from assuming that the hydrogen atom consist of a photon in a resonant cavity together with a source terms at a spherical shell of a specific radius so that all balances and nothing is radiated to the outside. You may have physical objection originating from what you know about QM and the fundamentals of physics, but the truth is that there is no mathematical choice points or fudge factors and the math for this conclusion is quite ok to follow. Quite neat. What amazes me is how physicists seams to not being able to understand that for all this to be untrue one need to point out where the fudge factors are located and or any choice points. There is actually no need for physics, just mathematics to verify this. I could not find any traces of such tweaks and I expect that any objections should be submitted with a page number and equation number and the objection showing clearly that there is a choice point or fudge factor. Experts is so stuck with their theory that they backpedal and claim some abstract concept is violated originating from another theory, that they totally misses the obvious. You just can't fake that precision, there must be something buried in all this.

Oh so what is the origination of charge and mass. Well I've asked around and the best explanation is that there is something like a continental shifty in space at the source terms that hinders information to flow through the surface. If you think of a higgs like field, not interacting with itself, equal intensity in all direction, one could think that this higgs field is interacting at this surface in such a way that you get source terms in maxwells equation, it feels ok, also it is not unthinkable that this interaction maintains the continental drift and stable setup and nonradiation. The seamingly fine balance of Mills theory of the atom and particles is probably much more robust than the impression you get by reading it. So there is still bit's of theory to be developed to actually show this and this is probably what will happen if Mills manage to create energy by producing dark matter e.g. hydrinos. Else we will be stuck with false physics for decades and probably a great hindering of the only progress that can stop (at least temporarily) humanity to kill itself of the planet (if the environmentalists are right, and there is a big enough chance they are to take this seriously). So this is why i'm writing this, a true concern and also to share the joy of understanding the basics of the universe - it isn't that difficult after all.

28 Nov 2014 (updated 28 Nov 2014 at 23:10 UTC) »


If I'm going to do this an infinite number of times, I can just as well say I did success in doing so and get a good night sleep

I just released a new version of guile-log e.g. logic programming in guile scheme. This release has a few major improvement. The most noteworthy of them are

Support for tablating, e.g. prolog versions of memoisations. There are a few important facts to note First of all the memoisation means that many infinite recursions will success and you can get meaning full answer out of


f(X) :- f(X).

The meaning with memoisation is of cause if f is continued ad infinite and never binds X then f will succeed and X is not bound. This is a nice feature together with good support of recursive datastructures that is now included in guile-log. The other pecularity is that for a given input the code can yield many outputs via backtracking. So it is not a easy peasy thing to churn out. I am not by any means first in producing such a tablating system. The most interesting thing though is that the machinery to implement this was (almost) already there. And the solution is simply just a meta programming on those tools.

The system works by for each templated function have a functional hash from any input to a list of outputs that may not be a unique list. As new solutions are produced, the new solutions is consed on the list, in evaluating the function it will lookup the list of solutions and the produce them as answers backtrackingly. when all solutions have been produced, it will then lookup the functional datastructure again and see if there is any new solutions, if not it will store a continuation and then fail. There will be a base e.g. the first time the function is called that if all continuation points have failed restart all continuations, each of them will reevaluate if there is any new solutions to produce and if they all fail the next round a fixpoint is found an no new solutions is produced. Neat. Be careful with negation (do you know why). Let's show some prolog ...


memo.scm:
------------------------------------
(compile-prolog-string
"
-functorize(tabling).
ff(X) :- (X=[Y,A,B]),ff(A),ff(B),(Y=1;Y=2).
"
------------------------------------
scheme@(guile-user)> (use-modules (logic guile-log iso-prolog))
scheme@(guile-user)> (load "memo.scm")
scheme@(guile-user)> ,L prolog
Happy hacking with Prolog! To switch back, type `,L scheme'.
prolog@(guile-user)> .rec ff(X).

X = {0}[1, ref[0], ref[0]]
more (y/n/a/s) > s
prolog@(guile-user)> .10 .c

X = {0}[2, ref[0], ref[0]]

X = {0}[1, ref[0], {1}[1, ref[1], ref[1]]]

X = {0}[2, ref[0], {1}[1, ref[1], ref[1]]]

X = {0}[1, ref[0], {1}[2, ref[1], ref[1]]]

X = {0}[2, ref[0], {1}[2, ref[1], ref[1]]]

X = [1, {0}[1, ref[0], ref[0]], {1}[1, ref[1], ref[1]]]

X = [2, {0}[1, ref[0], ref[0]], {1}[1, ref[1], ref[1]]]

X = [1, {0}[1, ref[0], ref[0]], {1}[2, ref[1], ref[1]]]

X = [2, {0}[1, ref[0], ref[0]], {1}[2, ref[1], ref[1]]]

X = [1, {0}[1, ref[0], ref[0]], {1}[1, ref[1], {2}[1, ref[2], ref[2]]]]
$1 = stalled
prolog@(guile-user)>

Not the same solution can show up many times in this infinite list. It is possible to use tools that make sure the list is unique but that is expensive and is not shown here. Also note how one can issue an 's' and return to the guile prompt from where state management can be done as well as taking 10 values as shown above.

As shown above recursive aware unification as well as many other recursive aware operations can now be enabled via a prolog goal or the .rec switch at command line

A modified bdw-gc has been made (see the guile-log doc's) and code inside guile's C layer have enabled fully garbage collected prolog variables. Now most normal prolog code will be safe to use even in a server setup where you basically tail call forever and temporary bound variables will not blow the stack. This was a pretty difficult thing to get fully working. A really nice hack indeed.

swi prologs attributed variables and coroutines have been implemented at least partly and with some extra bells and whistles. This feature mean that you can hook in code that will be executed when functions are bounded to specific values or well just bounded, lookup these features in the swi-prolog manual if you are interested, pretty cool.

operator bindings are now name spaced, meaning that by importing a module operators can get a new meaning, this can be used to take advantage of guiles number tower and not adhere strictly to iso-prolog.

Ok there is a few more points in the release, download it and have a play. I'm basically the only user and implementor so it is only a cool alpha software. I'm now heading towards being able to compile at least parts of the swi prolog system, to get more testing and because it is a nice bite to chew on, getting good prolog compability regarding the module system and a few more points is the goal.


Happy hacking and have fun!

guile-log 0.4.1 released

I'm really proud of this release. It sports an implementation of a logic programming environment that's previously had a interface designed by myself and the famous kanren interface that you grok if you read the reasoned schemer. In this release a fairly complete implementation of an iso-prolog have been churn out. That was a huge effort, but the ride was interesting and gave me a lot of new insights in computer programming. This also sports proper namespace handling, proper closures, proper delimited continuation goals. the kanren interleaving constructs, a framework that is enabled by functional data-structures and state handling, vhashes, vlists, and the coolest thing of all you can save state and restore state quite cheaply and seamlessly and with great power if you learn the system. by seamlessly I mean that we do not have proper functional data structures everywhere due to semantic needs in especially accumulators and delimited continuations goals, and the logical variables may also be used in a mutative fashion for two reasons 1. to enable GC of prolog variables. 2 it is maybe 3-4 times faster compared to a vhash based version that is also possible. The vhash version is thread safe (I'm not using guile's internal vhash, but a modded version in C)
Anyhow to seamlessly handle state in all this is really a delicate affair. Cheaply refers to the fact that I tried hard to enable state storage and state retrieval in algorithms meaning that a save is much more intelligent than saving the whole state of the prolog engine. In all I strongly recommend anybody interesting in logic programming to study the features more deeply. I believe there is some good lessons to learn there. And finally by power I mean that the system has designed an internal tool that makes difficult algorithm possible.

Let's play with it


scheme@(guile-user)> ,L prolog
Happy hacking with Prolog! To switch back, type `,L scheme'.
prolog@(guile-user)> .[use-modules (logic guile-log iso-prolog)]
prolog@(guile-user)> .[use-modules (logic guile-log guile-prolog interpreter)]
prolog@(guile-user)> user_set(1,1),stall,user_set(1,2),stall.
stalled
/* We are at the first stall */
prolog@(guile-user)> .h

HELP FOR PROLOG COMMANDS
---------------------------------------------------------------------
(.n ) try to find n solutions
(.all | .* ) try to find all solutions
(.once | .1 ) try to find one solution
(.mute | .m ) no value output is written.
---------------------------------------------------------------------
(.save | .s ) associate current state with name ref
(.load | .l ) restore associate state with name ref
(.cont | .c ) continue the execution from last stall point
(.lold | .lo) restore the last state at a stall
(.clear ) clear the prolog stack and state
---------------------------------------------------------------------
(.ref ) get value of reference user variable ref
(.set ) set user variable ref to value val
---------------------------------------------------------------------
prolog@(guile-user)> .ref 1
$1 = 1
prolog@(guile-user)> .s 1
prolog@(guile-user)> .c
$2 = stalled
/* we are at the second stall */
prolog@(guile-user)> .ref 1
$3 = 2
prolog@(guile-user)> .s 2
prolog@(guile-user)> .c
yesmore (y/n/a) > n
$4 = ()
prolog@(guile-user)> .l 1
prolog@(guile-user)> .ref 1
$5 = 1
prolog@(guile-user)> .l 2
prolog@(guile-user)> .ref 1
$6 = 2
prolog@(guile-user)> .c
yesmore (y/n/a) > n
$7 = ()
prolog@(guile-user)>

To play with it checkout the v0.4.1 tag at guile-log and read the manual at manual

Have fun

120 older entries...

 

Others have certified tampe as follows:

  • Akira certified tampe as Apprentice
  • zanee certified tampe as Apprentice
  • fzort certified tampe as Apprentice
  • mutek certified tampe as Master
  • ittner certified tampe as Journeyer
  • dangermaus certified tampe as Master

[ Certification disabled because you're not logged in. ]

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

X
Share this page