As previously stated, I am working on a Verilog Compiler in Python using PLY. The last article talked in a generic way about the project, from now on we will talk about specific parts of the compiler.
Today, we begain with the first part of any compiler: the lexing part.
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.
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.
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.
Today, we (members from ROSEdu) started accepting applications for the second edition of CDL. I’ll be back soon with another Haskell puzzle.
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.
Last post was ended with a problem: our solution exhausted the memory before it could give an answer to 
Let’s say we have a number 
Of course, what we will obtain is a permutation of the first
For those interested in programming electronic components there is always the possibility to use Xilinx if you are on Windows. Of course, there is a Xilinx port for Linux but it is buggy application and a very large download. This article aims to give an alternative to this application. One that will need only a few KB of download from an apt-get source.
Suppose we have to make a quiz. The questions have different degrees of difficulty and come from several different chapters. We have the following problem:How can we ensure that we select the questions uniformly from both domains?
