Cogs and Levers A blog full of technical stuff

Mutable State with IORef

01 Feb 2013

Introduction

Haskell goes to great lengths to control state but one way you can achieve mutable state in Haskell is by use of IORef. IORef gives you the ability to assign a reference to a variable in the IO monad. This at least decorates your code in such a way that it’s obvious to you, the developer and Haskell that there will be side effects. Today’s post, I’ll create a very simple example usage of IORef. We’ll construct a counter that we can increment and decrement.

Declaring our type

import Data.IORef                        
                                         
data Counter = Counter { x :: IORef Int }

First of all, we import Data.IORef to give us access to IORef. We declare our counter data type using record style, the only member of which is the value that counts. It’s an IORef Int to mean it references a variable in the IO monad that will be of type Int. So, it’s not so blatant that you’re dragging the integer value around with you, rather you’re dragging something closer to a pointer to the value or reference. To build one of our types, we need to use newIORef which references our actual value and we wrap it up in our Counter data type.

makeCounter :: Int -> IO Counter        
makeCounter i = do iref <- newIORef i   
                   return (Counter iref)

makeCounter takes in an initial integer that will seed our counter and returns a Counter in the IO monad. Getting our hands on the reference and doing something with it is pretty simple with the use of modifyIORef. Using this information, we can increment our counter with the following function.

incCounter :: Int -> Counter -> IO ()            
incCounter i (Counter c) = do modifyIORef c (+ i)

modifyIORef actually gives us the ability to pass a function to modify the referenced value. Be careful with modifyIORef though. As with a lot of things in Haskell, this is lazy. We’re operating on IO actions here so it’s all “promises to do something” or “will do it later when I need to” type operations, so repeatedly calling this without emitting the value will make these promises pile up. There is a strict and non-lazy evaluated version called modifyIORef'. Finally, when we want to get our hands on the referenced value and do something with it (in our example here, we’ll just present it to screen) we use readIORef. readIORef will take our IORef and just made it a value in the IO monad meaning we can simply use <- to emit the value.

showCounter :: Counter -> IO ()               
showCounter (Counter c) = do c' <- readIORef c
                             print(c')

This all pretty straight forward. Seeing this Counter run from GHCI is pretty straight forward.

λ> c <- makeCounter 1
λ> showCounter c
1
λ> incCounter 1 c
λ> showCounter c
2

There you have it - mutable state with IORef.

Write yourself a Scheme in 48 Hours

29 Jan 2013

A small bookmark to myself, wikibooks has an import of Johnathan Tang’s Write Yourself a Scheme in 48 Hours that I’ve come across.

http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours

Looks quite good if you’ve already gone through the language cruft that all of the other tutorials put you through first.

Making a Big Math Library (Part 2)

29 Jan 2013

Introduction

In the previous post, we had setup a basic array data type to act as a very big number. We implemented an initialise, increment and decrement function. Today we’ll extend on this library by adding some zero testing. It is of interest to us when our numbers are zero and when they aren’t.

Scanning our number

The plan of attack is to use a scan string quad-word scasq. We’re going to enumerate our array, testing each block for zero. If we make it to the end of the array, we have a zero number. If our scanning got interrupted by a non-zero number, our overall number couldn’t possibly be zero.

Here’s the code.

; --------------------------------------------
; bignum_is_zero                              
; determines if a big number is zero          
;                                             
; input                                       
; rsi - address of the number                 
; --------------------------------------------
                                              
_bignum_is_zero:                              
  push  rcx                   ; save off any registers that                                   
  push  rbx                   ; we'll use in this function
  push  rdi                                  
                                              
  mov   rdi, rsi              ; setup the destination pointer
                              ; for the scan operation
  mov   rcx, bignum_size      ; the number of blocks that we'll scan
  xor   rax, rax              ; the value that we'll be scanning for                   
  repe  scasq                 ; while we're still finding the value in
                              ; rax at [rdi], keep scanning
                                              
  cmp   rcx, 0                ; if we exhausted our counter at the end
                              ; of the scan, we have a zero number

  je    _bignum_is_zero_yes   ; jump to a true state               
                                              
  xor   rax, rax              ; rax = 0 = false, non-zero               
  jmp   _bignum_is_zero_done                 
                                              
_bignum_is_zero_yes:                          
  mov   rax, 1                ; rax = 1 = true, zero               
                                              
_bignum_is_zero_done:                         
                                              
  pop   rdi                   ; restore our saved registers               
  pop   rbx                                  
  pop   rcx                                  
                                              
  ret

Now that we’ve got this function, we can wrap it up with a print so we can visually see if a number is zero or not. This will also give you basic usage of the function above.

print_zeroness:                                 
  ; define the strings that we'll show to screen
  defsz zero_msg, "The number was zero"        
  defsz non_zero_msg, "The number was not zero"
  
  ; test the number that's at [esi]
  call  _bignum_is_zero            

  ; check if it "is zero", 
  cmp   rax, 1             

  ; jump over if it wasn't
  jne   print_zeroness_not_zero                
  
  ; print the "was zero" message
  print zero_msg                               
  jmp   print_zeroness_done                    
                                                
print_zeroness_not_zero:                        
  
  ; print the "wasn't zero" message
  print non_zero_msg                           
                                                
print_zeroness_done:                            
  ret

In action

Now that we’ve got a little helper function to wrap up our is-zeroness and reporting on this to the console, we’re free to test it out as follows.

mov   rdi, num_a      ; zero out our number     
call  _bignum_zero   
                        
mov   rsi, num_a      ; test if it is zero
call  print_zeroness 
                        
mov   rdi, num_a      ; increment our number
call  _bignum_inc    
                        
mov   rsi, num_a      ; re-test if it's zero
call  print_zeroness

To which we end up with a result looking like this.

$  bigmath  ./bigmath
The number was zeroThe number was not zero

As expected. Initially the number was zero, after incrementation is was not.

There’s some basic logic testing for your big number.

Monads

28 Jan 2013

Introduction

Following on from my previous posts about functors, applicative functors and applying applicative it would only be natural for me to post a follow up on the topic of Monads. Monads take shape very similarly to applicative functors so for this post to make sense, I suggest you read the previous articles so that you have a chance to follow along.

What is a Monad?

At a code level, a Monad is a type that is an instance of the Monad type class. At a concept level a Monad allows you to provide a function that is context-unaware to operate over values that are wrapped in a context. Immediately, you’d think that this is weaker functionality that what was defined for applicative functors - and you’d be right in thinking so, but Monads do provide a very natural way to write code against our types. Here is the type definition for a Monad.

class Monad m where
  return :: a -> m a

  (>>=) :: m a -> (a -> m b) -> m b

  (>>) :: m a -> m b -> m b
  x >> y = x >>= \_ -> y

  fail :: String -> m a
  fail msg = error msg

Moving through all of the defined functions, you first see return. return is the same as pure which we defined when making an applicative functor. return’s role in this type is to lift a value into a context. The next function you see is >>= which is pronounced “bind”. This is the major difference right here. >>= is what takes a value wrapped in a context m a and takes a function with a parameter of a returning a wrapped b as m b, with the function returning a b in a context m b. The remaining two operations are rarely delved into as their default implementations suffice majority of scenarios.

Laws

There are some laws that need to be abided by when implementing Monads. Left Identity suggests that

x >>= f is the same thing as f x

Right Identity suggests that

m >>= return is the same as m

Associativity suggests that

(m >>= f) >>= g is the same as m >>= (\x -> f x >>= g)

Such that it shouldn’t matter how these calls are nested together.

Custom context

Applying this knowledge to our rather useless example “CustomContext” discussed here, we can make this type a monad with the following definition.

instance Monad CustomContext where
  return = CustomContext         
  CustomContext x >>= f = f x

Ok, so - as prophesied return is doing the same thing as pure did for us - it’s just lifting a plain value into our context. >>= or “bind” on the other hand is taking the value out of its context and applying a function to it. We can check out our bind implementation in action with the following simple examples.

λ> CustomContext 3 >>= \x -> return (x + 1)
CustomContext 4
λ> CustomContext "Hello" >>= \x -> return (x ++ " World!")
CustomContext "Hello World!"

Our value is having a function applied to it. Values are getting de-contexted, worked-on than re-contexted. Pretty straight forward. To show you how >>= can work for us, I’ve created a function that will accumulate even numbers as they are received into it. If an odd number is encountered, the accumulated total get wiped back to zero until conditions are met to have another two consecutive calls with even numbers. Here’s how the function looks.

accumEven :: Int -> Int -> CustomContext Int 
accumEven y x                                
  | even x    = CustomContext (y + x)       
  | otherwise = CustomContext 0

Using guards, we filter out odd numbers sending the result back to zero otherwise we continue to accumulate. Note how the inputs are just plain integers but the output is an integer wrapped in one of our CustomContext types. With the use of >>= the following calls are possible.

λ> accumEven 0 2
CustomContext 2
λ> accumEven 0 2 >>= accumEven 4
CustomContext 6
λ> accumEven 0 2 >>= accumEven 4 >>= accumEven 7
CustomContext 13

First of all, we’re freely using wrapped and un-wrapped contexts thanks to that bind operator. More interestingly (and demonstrative to our purposes here), the last example appears to be in error, but it’s really not. Think about it this way.

accumEven 0 2 = 2
accumEven 4 2 = 6
accumEven 6 7 = 13

So you can see here that the next sub-sequent call to accumEven would finish with a 0 (zero) value as the 13 would be carried onto the next call and would be tested for evenness. Even if this isn’t the best example, it still demonstrates how bind is sending information between the calls.

do Notation

Another nicety when working with Monads is do notation. do notation allows you to clean up a lot of the boilerplate that builds up around the functionality you write when working with monadic values. Here’s a very simple function that builds a CustomContext from two other CustomContexts by adding them.

CustomContext 6 >>= (\x -> CustomContext 7 >>= (\y -> CustomContext(x + y)))

You can see how things start to get a bit gnarly once you chain more calls together. Using do notation, this gets cleaned up pretty well. The above can be re-written like so.

makeContext = do        
  x <- CustomContext 6 
  y <- CustomContext 7 
  CustomContext (x + y)

That’s so much easier to read! There’s do notation at work for you, anyway. Well, that’s all there is for Monads right now. As soon as I try something useful with them, I’ll post a follow-up article of Monads in Application.

Making a Big Math Library

28 Jan 2013

Introduction

In most of your day to day applications, numbers that fit within 8, 16, 32 and 64 bits are enough. Sometimes you may need to stretch out into your floating point processor to include some more precision and start looking at 80 bit numbers. Today’s post, I want to start on a library in assembly language that works on even bigger numbers. There are going to be some caveats or conditions that we’ll establish up front, but they will be big numbers! The design considerations for this library will be as follows:

  • Unsigned integers
  • Fixed size

With this information, we can now start to build our library.

The big number data type

Well, it’s not really that special at all. We just need to define an array of quad-words to the length that we want. So, an example would look like this.

bignum_size EQU 10        ; bignums will be 640bits in size
                                            
num_a resq bignum_size    ; make our bignum variable

That’s all pretty simple. A number is just an array of a pre-defined length. With a length to 10, at 64 bits per array index we’ve got ourselves a 640 bit number. Quite large. In fact, we’re talking numbers up to 4.562441e+192. Now that’s impressive.

Lets operate!

We’ve got a very impressive data type that we can declare where ever we want, but how do we use it? We need to define all of the management, arithmetic, logic and printing ourselves. First of all though, we’ll want to be able to zero out our number, which is just continually writing zeros over our memory buffer (much like a memset).

; --------------------------------------------
; bignum_zero                                 
; initialize a bignum to zero                 
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_zero:                                 
  push  rax               ; save any registers                                  
  push  rcx               ; that we'll mow over                   
  push  rdi                                  
                                              
  xor   rax, rax          ; the value we want to set to                   
  mov   ecx, bignum_size  ; the number of quads to write                   
  rep   stosq             ; clear out our number                   
                                              
  pop   rdi               ; restore any registers that                   
  pop   rcx               ; we saved                   
  pop   rax                                  
                                              
  ret

Excellent. We can initialize our big number now to zero so that we have a starting point. Next, we’ll want to be able to debug any problems that we may have while building this library, so its going to be of great benefit to be able to see what the value is of our number. The following code leans on some assembly I had written in a previous article which displays the value in RAX. Here’s how we’ll print our big number to screen.

; --------------------------------------------
; bignum_print                                
; prints a bignum to the console             
;                                             
; input                                       
; rsi - address of the number                 
; --------------------------------------------
                                              
_bignum_print:                                
  push  rax                 ; save off any values                         
  push  rbx                                  
  push  rcx                                  
                                              
  mov   rcx, bignum_size    ; we'll print all blocks

next_block:                                   

  mov   rbx, rcx            ; setup our base pointer                             
  dec   rbx                 ; to point to the block corresponding                 
  shl   rbx, 3              ; to our counter rcx

  mov   rax, [rsi + rbx]    ; get the value in rax                 
                                              
  call  _print_rax          ; print it                 
                                              
  dec   rcx                 ; move onto the next block                 
  jnz   next_block          ; keep printing                 
                                              
  pop   rcx                 ; restore any saved registers                 
  pop   rbx                                  
  pop   rax                                  
  ret

Most obvious thing to note here is that we’re moving through the bignumber back-to-front so that it’s presented on screen in a human manner. We can test what we have so far is working by writing a small piece of test code.

; zero out our number
mov   rdi, num_a   
call  _bignum_zero  

; print it to screen
mov   rsi, num_a   
call  _bignum_print

Which, rather uninterestingly will just spit out a massive list of zeros.

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

So, lets do something a little more interesting. The smallest pieces of arithmetic that I think we can implement for these numbers is increment and decrement.

Increment

This is straight forward. Add 1 to the lowest part of the number. If that part of the number just “clocked”, or reset to zero - we must carry our value onto a higher block.

; --------------------------------------------
; bignum_inc                                  
; increments a big number by 1                
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_inc:                                  
  push  rcx                       ; save off any registers                                  
  push  rbx                                  
  push  rax                                  
                                              
  mov   rcx, bignum_size          ; worst case, we'll have to
                                  ; go through all blocks

  xor   rbx, rbx                  ; reset our base to be zero                             
                                              
_bignum_inc_carry:                            
  mov   rax, qword [rdi + rbx]    ; get this block into rax           
  inc   rax                       ; increment it
  mov   qword [rdi + rbx], rax    ; store it back           
  cmp   rax, 0                    ; check if we "clocked"           
  jne   _bignum_inc_done          ; if we didn't, we're finished           
                                              
  add   rbx, 8                    ; move the base onto the next block           
  dec   rcx                       ; 1 less block to process           
  jnz   _bignum_inc_carry         ; continue until we're finished           
                                              
_bignum_inc_done:                             

  pop   rax                       ; restore any of the saved values           
  pop   rbx                                  
  pop   rcx                                  
  ret

Alright, we’ve got incrementation going on here. The most interesting case for us to test is when a block is sitting on the carry boundary or sitting at 0xffffffffffffffff. After we increment that, we should see that clear out to zero and the next block to get a 1.

mov   rdi, num_a                     
call  _bignum_zero                   
mov   qword [rdi], 0xffffffffffffffff   ; setup out number on the boundary
                                     
mov   rsi, num_a                     
call  _bignum_print                     ; print it out
                                     
mov   rdi, num_a                        ; push it over the boundary with
call  _bignum_inc                       ; an increment 
                                     
mov   rsi, num_a                        ; print out the new number
call  _bignum_print

Which results in the following.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000

Those massive trails of zeros are getting annoying. We can clean them up later by making our print routine a little smarter. But you can see that we’ve successfully incremented over a boundary so that our next higher block gets a one.

Decrement

This is pretty much as straight forward as incrementing, on this time we’re not going to carry to a higher quad-word, we’re going to borrow from it if we do cross a boundary. Here’s the code for a decrement.

; --------------------------------------------
; bignum_dec                                  
; decrements a big number by 1                
;                                             
; input                                       
; rdi - address of the number                 
; --------------------------------------------
                                              
_bignum_dec:                                  
  push  rcx                       ; save off any registers                                  
  push  rbx                                  
  push  rax                                  
                                              
  mov   rcx, bignum_size          ; worst case, we'll need
                                  ; to go through all blocks

  xor   rbx, rbx                  ; clear out the base                             
                                              
_bignum_dec_borrow:                           
  mov   rax, qword [rdi + rbx]    ; get the current quad           
  dec   rax                       ; decrement it           
  mov   qword [rdi + rbx], rax    ; store it back in the number           
  cmp   rax, 0xffffffffffffffff   ; check if we went across a boundary           
  jne   _bignum_dec_done          ; if not, get out now           
                                              
  add   rbx, 8                    ; move onto the next block           
  dec   rcx                       ; not done yet?           
  jnz   _bignum_dec_borrow        ; keep processing borrows           
                                              
_bignum_dec_done:                             
  pop   rax                       ; restore the saved registers           
  pop   rbx                                  
  pop   rcx                                  
  ret

This really is the increment routine just with the numeric direction reversed. Making sure that we are on the right track, we can test out the decrement across a boundary again.

mov   rdi, num_a                        ; setup our number right                     
call  _bignum_zero                      ; on the boundary
mov   qword [rdi], 0xffffffffffffffff
                                     
mov   rsi, num_a                        ; print its current state
call  _bignum_print                  
                                     
mov   rdi, num_a                        ; increment over the boundary
call  _bignum_inc                    
                                     
mov   rsi, num_a                        ; print its state
call  _bignum_print                  
                                     
mov   rdi, num_a                        ; decrement it over the boundary
call  _bignum_dec                    
                                     
mov   rsi, num_a                        ; print its state
call  _bignum_print

The output of which looks like this.

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FFFFFFFFFFFFFFFF

Again, it’s pretty hideous with the trailing zeros, but you can see this in action now. Back and forth, across boundaries - no sweat.

Conclusion

Well, this is just the tip of the iceberg for this particular library. I’d hope to demonstrate logical testing, addition, subtraction, multiplication and division as well shortly. The best part about these routines is that if you wanted to operate on 6400 bit numbers, all you have to do is change the constant bignum_size that I’d set earlier to 100.