Writing a Compiler for Verilog – part 1

This year, I took a class named Numerical Computers II (I had Numerical Computers I last year). The course was about Computer Architecture and things like this. However, I ended up with a very fascinating homework: to write a compiler for Verilog in a team of 2 to 4 people. The deadline is coming soon (I have to finish it by Friday) but I need a break so I’ll post here my story.

Segmented Sieve Of Eratosthenes

Today’s Programming Praxis problem describes an algorithm which may be used to find the prime numbers in a large interval, so large that it cannot be kept in memory at once. See their description there, I’ll only give the code in Haskell.

First, some utility functions:

firstQ :: Int -> Int -> Int
firstQ l pk = (-(1+l+pk) `div` 2) `mod` pk
 
nextQ :: Int -> Int -> Int -> Int
nextQ b pk qk = (qk - b) `mod` pk


Then we sieve one block and convert the values to the primes:

sieveBlock :: [Int] -> [Int] -> [Int] -> [Int]
sieveBlock [] [] blk = blk
sieveBlock (p:ps) (o:ofs) blk = filter f (sieveBlock ps ofs blk)
  where
    f x = (x < o) || ((x - o) `mod` p /= 0)
 
getValsfromBlock :: Int -> [Int] -> [Int]
getValsfromBlock l bl = map (\x->l+1+2*x) bl


Now, it’s time to obtain all the numbers. This post will make use of the until function which is very similar to what some will use for the `for` construct in C.

sieve :: Int -> Int -> Int -> [Int] -> [Int]
sieve l r b primes = middle $ until stop incr start
  where
    middle (_, v, _) = v
    stop (sb, _, _) = sb == r
    start = (l, [], map (firstQ l) primes)
    incr (startblock, primessofar, q) = (nextblock, nextprimes, nextq)
      where
        array = [0 .. b-1]
        nextblock = startblock + 2 * b
        nextprimes = primessofar ++ (getValsfromBlock startblock bl)
        nextq = zipWith (nextQ b) primes q
        bl = sieveBlock primes q array


The main is very simple after we know about the print function and that it is a monadic one

main = print $ sieve 100 20000 10 [3, 5, 7, 11, 13]


That’s all for now.

Formal Languages and Books

I’ve read two books in the last days. Both are related to Formal Languages, Automata Theory and Compilers. This will be another review article.

A Strange Machine

Another Haskell puzzle. This time, we have a 2D square matrix. Each cell can contain a number. We have a cursor which always resides in one cell of the matrix. Let s be the sum of values contained in the 8 neighbouring cells and the cursor’s cell. At each update step, we will modify the cell under cursor by using a bijective function of s. After this, we change the cursor location by moving it to a neighbouring cell or leaving it as it is, depending on the value of its cell.

We have to simulate such a machine, assuming that the matrix wraps at the boundary.

Learn the Tools of Open Trade

Today, we (members from ROSEdu) started accepting applications for the second edition of CDL. I’ll be back soon with another Haskell puzzle.

The Monad Reader – Issue 15

Today, Brent Yorgey announced a new issue of «The Monad Reader». The waiting of 10 days since submission deadline and today was worth it: a project from Google Summer of Code (Gergely Patai – a new profiler for Haskell), 3 useful monads (Edward Z. Yang – Logic, Prompt and Failure) – of which the Prompt Monad will be used in a personal project, hopefully before April -, a new way to write monads (Heinrich Apfelmus – an operational view of monads) and a nice implementation of STM in pure Haskell (Andrew Coppin).

I’ll be back shortly.

A General Network Module

Let’s say we need to solve a problem involving a graph-like structure, possibly containing cycles. We want to do this in a functional way (Haskell) but we are stuck when we deal with the cycles.

Numbers, exponents and cycles

Suppose we have a number . We apply the following procedure to in order to obtain a new number : we take ’s digits and raise them alternatively to 2 and 4, summing the results. Thus, will become . We don’t stop here. Instead, we apply the same procedure to obtaining .

Of course, and someone can prove it, this procedure will quickly lead either to a number already seen or to 1. For now, we are only interested in the number of iterations required for this.

A New Kind of Science

I’ve managed to read Stephen Wolfram’s book (pdf version, 20 to 30 pages in a week due to a busy schedule). I can say that it was a new kind of experience.

A Puzzle and a Solution (2)

Last post was ended with a problem: our solution exhausted the memory before it could give an answer to , . There were three comments trying to solve them and the last two of them are working. However, the solution involving the lcm of cycles is faster and I will post it here (the other one is posted as a comment there).