Older blog entries for tampe (starting at number 107)

functionasm

Alex Shinn, has written a library for scheme that does formatting tasks in a functional style, the fmt library. In this library there is a package for outputting c code. Let's play with that.

A next step might be to be able schemify c code. e.g. introduce <define>, <let*>, <begin>, <if> and <recur> + the operators. The innovation needed to do this is to make sure that everything return values and are able to be composed together with some kind of "sewing" mechanism.

The idea of attacking this is to try keep everything functional as far as possible and then at the final step add syntactic sugars in the form of macros. When trying to do this one realizes that we need two phases of evaluation. The reason are this, consider a function application:


int f(int),
----------------
f((<let*> ((a (+ b c))) (<if> q a b)) + b)?
Now the idea of modelling is to let the statments evaluate to a lambda that takes as an argument #f or a symbol. The lambda applied to a symbol will mean that the result of that expression will generate c-code where the tail expressions will set the symbol to the return result. so we do stuff like,

(define (f-if p x y)
    (lambda (ret)
       (let ((pred (gensym "pred"))
         (c-block
           (c-var 'int pred)   ; define pred integer
           (p pred)            ; execute p expression
                               ; pred is the result
           (c-if pred (x ret) (y ret))))))
This will illustrate the technique (we are using autoquoting features in the macro package). Over to the function application. Here we conclude that in order to be general we need to use

   (int arg)
   ((((<let*> ((a (+ b c))) (<if> q a b)) + b)
    arg)
   (c= ret `(f ,arg))
E.g. we introduce an arg symbol to be able to set it. Doing this we need to know about the function signature. Designing the <define> as a function means that we are not able to register the function signature before the body is evaluated and the function signature needed in case of recursion. So one need one extra lambda dereference. I thught that was too complicated though and used macros in stead to accomplish correct registration order.

The function example lack some wow factor. But for the loop construct in clambda, the <recur> statement, it's a must. Here is how the idea of this works


(<recur> loop ((int n 100) (int s 0)
    (<if> (< n 0)
          s
          (<next> loop (+ s 314))))
====================================
Aproximate translation
====================================
 int n = 100;
 int s = 0
loop:
 if (n < 0)
    ret = s;
 else
 {
    s = s + 314;
    goto loop;
  }

This is kind of handy loop construct and again one need to register the loop symbols this time in order to be able to expand the <next> statement later on.

This is about 300 lines of code. For 600 I guess you would be able to introduce a good enough c to produce workable code with syntax line numbers introduced as well to be able to debug after gcc has found your bugs.

Now this is not that complicated and everything is just a quite simple idea of syntactic sugars. But this will enable scheme macro facilities to your c-code (for one thing you will be able to track source code line numbers to be able to debug your macros correctly. Also going between clambda and pure scheme is a smaller step then between c and scheme this means that you can keep a large part of say guile c-code both in c and scheme at the same time.

Have fun

o.o

Can strange things happen, that matters. I don't know, but strange indeed are the day's I live in. To keep sane is a big struggle and without ears plugged with music. I would not know where I would be.

Anyhow here is a spooky story.

I met an old woman a couple a weeks back and she talked about many things, fools and queens, high and low. But what I previously did not remember was how she spoke about a book, her exact words I don't know, but she talked about an o and a dot.

Then I forget about her, and a week later I sat down and thought a poem on a piece of math would be so perfect. Thinking about my old ford and the day's back when I was young I got into the right mood of writing the poem. And the dance went on. At the end I saw that it was not perfect. I wanted to move the text to the right and wrote "o." at the beginning without knowing why, I just did it cause writing a poem is to express feelings and then I just relax and let the hand walk across the keyboard. So, focus! It struck me, just struck me, don't ask me why,..., why don't write "o.o" instead of "o." and so I did. And so I did.

And so I did, I need to keep that python syntax correct, don't I.

And time passes, life went boring and I took a walk to the library. I stood there just feeling empty and pointed the finger at a shelf of books, letting the finger wander from book to book, reading the titles without thinking, and then I picked, as it felt, randomly, the Illusionist by Fowler.

This is a kind of cool book and in the beginning the character of importance move to a lonely place, becomes depressed and decide to shoot himself with a shotgun. And at the moment the trigger is supposed to go off, Fowler writes the characters o and dot. Probably, to make an illusion of end of life.

The effect of this happening to me is tremendous. I had a brother you know, and his life did not end with an illusion. I took a long walk and did not calm down until I met a family of deers that just stood there about 10m in front of me, relaxing, and reminded me about how life goes on.

o.o

8 Apr 2011 (updated 8 Apr 2011 at 15:24 UTC) »
When thoughts flow too fast

Fasten your seat-belts, earplugs in and here we go. The city flows silently and the leaves dance together with plastic bags in an urban eddy. Music in the blood and so much feelings pressing when you take in everything. Silent shadows with faces that pass by and I think, oh well I need to freeze this moment and carve it into a stone cake, the ones you find in the book: uncle tungsten.

I'm planning to be much more moveable in the future and are preparing a smaller laptop with linux for guile-unify development. I had a stress breakthrough and need to take a brake from work. And of cause the most relaxing thing for me to do is to code like an artist and not like a monkey. Probably the resulting code will be too poetic, but I don't care. I hunt for pieces of ideas. Not running them through the fingers like the end is near. In the end I will return to normal productivity but that's for later. Most important thing for universe minus me in the near future is to shelve out a release of this stuff. Then people who would like to play a tune of two of that weird poetry can do that with some guidance. Or at least not need to read the mind of a sole on the other side of the Atlantic see.

Oh, I'm also trying to push out a physics paper, but that have to take the time it takes. What's cool here is that I will try to make it as a combination of poetry and science - if they dare.

So, for me life can be stated with the one liner:

Play it again Sam!

Dream on folks!

6 Jan 2011 (updated 20 Jan 2011 at 05:53 UTC) »
A flow of thoughts

So, I start as usually with my bad prefix.

I haven't had so much fun for ages. The Yang Mill theory is a really great work of illusion. My bet is that people who analyze the equations will not realize the true nature and continue with their hopeless task. You really have to think out of the box in order to solve this.

The world may look straight. But in reality looks queer. (freely translated from Copernicus with help of Einstein)

A huge hug to you all

4 Jan 2011 (updated 15 Jan 2011 at 17:00 UTC) »
New year's mini search.

So, it's Christmas, and the New year went by. as usually at this time of the year. The family have been relaxing and the my mind have been floating around fishing ideas on the pond of imagination.

So, as usual I spend some time trying to solve a very interesting puzzle. What the are nature made up by. One thing I just can't understand is why we make such a fuzz out of the number dimension of space. It's the numbers of freedoms in the model. But for god sake a pencil have 6 freedoms. Three rotational degrees of freedom and three translational degrees of freedom. My point is that it is likely that there are a local structure that we cannot see that have a gazillion of freedoms (well this is a free source blog aren't it :-).

It looks to me that it is pretty premature to twist peoples mind about talking about high dimensional space in the way we do. On the other hand the number of freedoms are important mathematically no doubt about that.

The next things that just forces me to try to think by my own is how we argue about the fundamental parameters in space. In some science shows I seen on the tube they only explain this by saying that we would not be here to analyze it and simply that's why. And this is why they are feasible and not a small distance away from it leading to an unfeasible solution.

Here is where the engineer in me just go into rocket mode. What!!!, this is not the only argument. It is just as likely that the reason is that the laws are simpler and demand less parameters. To visualize, We have a higher dimension model that works really well. A simpler model with fewer parameters will then be embedded very much like a surface in space e.g. move a little in the wrong direction and you are out of the surface. And the setup will be unphysical.

Have fun!

9 Sep 2010 (updated 15 Jan 2011 at 18:38 UTC) »
Gardening

After a couple of weeks hacking fixing bugs etc in the guile-unify module the example in my previous post runs effectively according to the discussion in my last post - not the hackish slow method I used previously. So it seams to work - cool. The next step is to understand another problem one have when trying breath first like algorithms. It can have to much of computational complexity.

I've been wondering what example to use. And I think that it would be interesting to go after automatic proof generation. I decided to play with the leanCop prolog solver for this application in order to understand needs. A first approach will be to make proof searches that postpone against stack usage. E.g. try to search for a simple proof before a more complex one. </b>

Now, there is this piece left that is needed in order to dive into this problem. That is one probably need a way to cut out branches and trim the reasoning trees. How can this algorithm be constructed? Well, assume a certain level L. One will hit at some point a memory barrier K. Then one need to decide about Cutting out a fraction F from the tree because of the high complexity of typical algorithms. This can be done randomly or e.g. according to an importance index. So the tactic here is to bring out all the importance numbers, sort them and search for the level separating the whole tree in correct fractions. Notice that it can be smart to add a small random variable to the index in case there are many similar importance numbers - and one get a random sample. After finding the threshold the c-code can make sure to trim the tree according to the threshold in a adaptive and globally sound way.

And of cause there are some holes remaining like making sure scheme variables sit in the redo tree get garbage collected. but this is boring though important technical stuff.

There is another idea I later would like to follow. The redo tree can be seen as a storage of a set of permutations of a few symbols or numbers. Therefore, later on, some kind of compression of the redo tree will be used. So typically you have a sequence of (type pointer val type pointer val ...) where the pointer points to a scheme variable or immediate. That will be reset to the new value. now currently we waste space by storing (type pointer val) as three 64 bit elements on a 64 bit platform. Type can be just one byte and we could device a control byte describing the the size of pointer and val around stored base points. e.g. choose between 1,2,4 or 8 byte representations around 4 stored values. many application will then just need 4-5 bytes to be able to restore a state for a variable which is maybe a 6 fold saving of memory (this is the benefits of C). Of cause one can let a control bit decide if there need to be a resetting of a stored base value and use some kind of adaptive learning to compress but I leave that out for now. actually any technique found in gzip can of cause be used if one likes. We will do it in the order of one extra scan of the tree not doing an actual redo and therefore loss of addresses due to variable sized atoms may not have such a great impact. On the other hand it is possible to store pointers to speed up plain tree searches in the redo tree.

I hoped I'm not bored you here. But one of the reasons I do write this is to help me think about what to do next. Ergo it help OSS ;-)

Have fun

27 Aug 2010 (updated 27 Aug 2010 at 10:29 UTC) »

Compress that for me, please

So, if you are in a habit of analyze lists and tree structures like code, and like pattern matching, you may end up writing ton's of code like.


(def sum-of-leaves
   ((X . L)      (+ (sum-of-leaves X) (sum-of-leaves L)))
   (()           0)
   ( X           X))

e.g. if you have a list sum the first and the sum of rest the empty list yields 0 and all non list elements -the leaves, assumed numbers - end up being just counted as the value they represent.

So how should we code this destruction into a primitive lang? One idea I used is to work with the guile VM directly and use a few extra primitives there.

So consider destructuring


(define (f A)  (match A ((X 'a (X . L) . U) (list X L U) ...)

we could do this with a stack machine like,


(push A)         ;; Stack -> (A)
(explode-cons)   ;; Stack -> ((car A) (cdr A))
(set X)          ;; Stack -> ((cdr A))
(explode-cons)   ;; Stack -> ((cadr A) (cddr A))
(match-eq? 'a)   ;; Stack -> ((cddr A))   
(explode-cons)   ;; Stack -> ((caddr A)  (cdddr  A))
(explode-cons)   ;; Stack -> ((caaddr A) (cdaddr A)
(cdddr A)))
(match-eq? X)    ;; Stack -> ((cdaddr A) (cdddr A))
(set L)          ;; Stack -> ((cddr A))
(set U)          ;; Stack -> ()
(list X L U)
;;; note if an explode-cons or eq? fails it will 
;;; reset and the next pattern will be tried.

And what you note is that this is a more compact reduction of pattern matching then doing it with the standard VM of guile. So the end results is that code executed on this VM is both faster and more compact then using the standard setup. But of cause if we would like to compile this to the native platform then the standard compilation to pure scheme probably has an edge.

Interestingly though (I'm implementing a prolog on top of guile), this pattern can be generalized to the case where A - the input is a unifying variable. The destruction will look almost the same, but we need to tell the VM that we are in a mode of destructing a unifying variable. Meaning that if X is not bound we will set that variable to a cons and push two new unbound variables (car A) and (cdr A) onto the stack.

Cheers!

24 Aug 2010 (updated 16 Jan 2011 at 06:54 UTC) »
What's growing on your head old moose

So a couple of weeks of working and this was the result,


prun() :- L = [1,[3,[7,[15],8,[16]],
               4,[9,[17],10,[18]]],
               2,[5,[11,[19],12,[20]]],
               6,[13,[21],14,[22]]],
          postpone_frame(30,0.8),
          f(L).


f([H|L]) :- !, sub-tree-max([H|L],X), postpone(X), g(H,L).

f(H) :- postpone(H),pk(H), fail.

g(H,L) :- f(H). g(_,[H|L]) :- g(H,L). g(_,[]) :- fail.

where sub-tree-max represents the maximum value in a specific subtree. We get the result:

 
(18) (19) (20) (21)
(22) (15) (16) (17)
(14) (11) (12) (13)
(8)  (9)  (10) (7)
(6)  (4)  (5)  (3)
(2)  (1)

Note, the intention is to make an addition to a prolog engine to accomplish the above.

postpone_frame(Level,Fraction) will start executing all postpones above Level*Fraction. Then it will execute all postpones above Level*Fraction*Fraction and so on. You may want to change the algorithm at your taste but the main idea is not to use a full sort but tasty chunks of code which basically flows from most interesting to least interesting. I will add a lower level as well for which a direct Cut is taken.

Actually the current working implementation is very costly, e.g. every postpone is visited and if criteria is not met (the state is still recalculated!!!) it will again postpone (stupid, yea I know, but I wanted a working simple starting point)

Have fun

And so we unify the universes and continues just as before

How cool it is to have fun and do something useful. Well at least on the paper. My main focus for some time is to learn scheme and help out for that community. It's a really nice experience - thanks for that.

Anyhow I just entered a new project on Advogato - guile unify - which is may latest contribution. I've been hacking on it for some months, and feel that it got some interesting twists. so what is it?. Well it's exploring the combination of scheme and prolog.

One of the unique features of scheme that have etched its pattern in my brain is continuations - mainly because it was so hard to grok that call/cc stuff when I first encountered it. And this is a really interesting combination to breed in this marriage between a schemer and a prologur.

prolog is a combination of a variable stack, tree search, and unifying matches. To introduce continuations one probably end up with needing redo trees. A path from the root of the tree out to a leaf is passing variable "set commands" in such a way that the state of variable stack is restored from a blank base setup at the leaf, where a closure is found ready to take a continuation action. By making a tree one can save some on memory and perhaps also on time. Got this working and prompted me give the project some light.

Now, actually I'm lying. Pure continuation will come, but I'm targeted the method for a limited kind of continuation. e.g. a postpone command.

Consider writing a chess solver. Now you build up state information in various structures as you go and would like to use that information to draw strategic conclusions for a certain move. You may want to cut unstrategic moves, right! Well actually this may be prompting the developer to do a lot of tuning to get correct. So an interesting idea is to store the state of the game, save that continuation on a list and continue with that list if resources are available. This approach is more adaptive and probably lead to less tuning for the developer. To note is that storing this state for millions of continuations can put a severe strain on memory and also raise the complexity of the continuation. So that's why compress all the information in a redo tree very much like saving a word lexicon effectively may be interesting - actually, i don't now about this, I just made it work!! and it was great fun and a challenge to do it.

Consider trying to logically prove a statement. Could be cool to try to search for a small and elegant solution before trying those infinite paths. So just monitor stack usage and postpone at the points where stack reaches above a level, and continue to the next level if needed then on. Just write the usual prolog stuff and insert a few commands and you will have it. Nah not implemented but hey look at.

An example in prolog comes here,


prun() :- L = [[[5],2],1,[3,4]],
          postpone_frame,
          X is 0,
          pk(X),
          f(L,X).


f([H|L],N) :- !, postpone, N is N + 1, g(H,L,N). f(H,N) :- pk([H,N]), fail. g(H,L,N) :- f(H,N). g(_,[H|L],N) :- g(H,L,N). g(_,[],_) :- fail.

And entering prun leads to the sequence


(1 1),(2 2),(3 2),(4,2),(5,3)
Yea, trivial, but it shows how simple to code it. Now it's actually trivial to make a stack size criteria that will be a nice hack to try just to see if it improves.

Oh, The speed is not to bad and it is taking advantage of tail calls, prompt logic and CPS. Turns out CPS is not bad for speed - but do affect it.

Now, entering true continuation is just a matter of hard work. I will need to write a special GC for this structure because, the data-structure is tuned to be good at the scenario above and true continuation will be a cool creature, but a second citizen in my view that need some caring.

I will try to find time to talk a little more about the internals of all this. Maybe it's all a nice sand castle, maybe it is severely cool. Time will tell. I will continue to hack on it. If you have any questions or would like to learn or help, join the guile devel community and ask about guile unify.

Cheers

Stefan

2 Jan 2010 (updated 16 Jan 2011 at 07:04 UTC) »
Types

I ended the last sequence of blogs about exploring looping, then basically stopped and started to learn about type theory and prolog using Qi.

right now I working with this engine to write a type system that works pretty much like lisp type system e.g. if we can deduce type, then use it! This type-engine will be used to compile Qi to lisp/clojure/scheme/go? or whatever lisp like environment you got.

Cheers!

98 older entries...

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!