Coding things

## Category: Questions of a Beginner

### Writing a Compiler for Verilog – part 2

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.

### 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.

### 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.

### 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.

### 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 $N=1000$, $P=42$. 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).

### A Puzzle and a Solution

Let’s say we have a number $N$ of children placed in a circle and playing the following simple game: proceeding around the circle they kick out every $P$th of them (of course, $P < N$).

Of course, what we will obtain is a permutation of the first $N$ natural numbers. The puzzle asks for the order of this permutation (that is the number of times it must be applied to itself to get back to an ordered list.

### Verilog and VHDL on Linux (Ubuntu)

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.

### Uniformity

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?