Wednesday, December 12, 2012

Byte Packing with core.logic

My brain thinks of problems in odd ways. Often I think "well if an entire language exists that stresses a given style of programming, then what would problem X look like in that language". Recently I've begun that thought process with core.logic

Let's say we have two ints that want to output: 42 and 10755, but we only want to write 16bits of each number, and we want to write the low bytes first. So, for our program, the example output should be:

(42 0 3 42)

Now, for the core.logic part. Recently added to core.logic is a set of finite domain functions. This should allow us to express our packing routines in a relational manner:

(defn split-16 [i high low]                                                                                                                                                                                                                                            
        (fresh [h]                                                                                                                                                                                                                                                          
               (infd i (interval 0 65536))                                                                                                                                                                                                                                  
               (infd high low (interval 0 255))                                                                                                                                                                                                                              
               (*fd high 256 h)                                                                                                                                                                                                                                              
               (+fd h low i)))

What's amazing about this, is how clear the logic is presented. Given three vars: i, high, and low. We define the domains for each (16bit and 8bit). Next we say that "h" is "high", shifted by 8 bits. And finally, i is h + low. The cool thing here is that if we are packing or unpacking we will end up running half of this function "backwards". So...does it work?

user> (run* [i l h] (split-16 10755 l h))                                                                                                                                                                                                                                    
([_.0 42 3])                                                                                                                                                                                                                                                                
user> (run* [i l h] (split-16 i 42 3))                                                                                                                                                                                                                                      
([10755 _.0 _.1])

Awesome! So we can run it both forwards and backwards.

Now, for the actual "writing to the stream". A little work with appendo gives us what we need:

(defn append-16 [input i output]                                                                                                                                                                                                                                      
        (fresh [l h]                                                                                                                                                                                                                                                        
               (split-16 i h l)                                                                                                                                                                                                                                              
               (appendo input [l h] output)))

user> (run* [q]                                                                                                                                                                                                                                                              
            (fresh [z]                                                                                                                                                                                                                                                      
                   (append-16 '() 42 z)                                                                                                                                                                                                                                      
                   (append-16 z 10755 q)))



((42 0 3 42))

So we reached our goal. we can pack a few ints. But wait...what's the matra shouted by every logic programmer from here to China? "Run your program backwards!". Okay...let's try it.

user> (run* [i1 i2]                                                                                                                                                                                                                                                          
            (fresh [z q]                                                                                                                                                                                                                                                    
                   (emptyo q)                                                                                                                                                                                                                                                
                   (append-16 q i1 z)                                                                                                                                                                                                                                        
                   (append-16 z i2 '(42 0 3 42))))                                                                                                                                                                                                                          
                                                                                                                                                                                                                                                                             
([42 10755])  

The power shown here is just amazing. Using the same logic, we are able to run our code as both a packer and an unpacker. Two programs for the price of one.


2 comments:

  1. Souldn't be the upper limit to i 65535? Because for 65536 you need 17 bits.

    Juan Manuel

    ReplyDelete
  2. Quite right, that was a type-o on my part. Thanks!

    ReplyDelete