news

2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 FOSS documentation emacs fedora foss freedom gnome haskell install laptop photo ruby travel verilog vhdl vlsi xmonad


[Published in Open Source For You (OSFY) magazine, August 2014 edition.]

This second article in the series on Haskell explores a few functions.

Consider the function sumInt to compute the sum of two integers. It is defined as:

sumInt :: Int -> Int -> Int
sumInt x y = x + y

The first line is the type signature where the function name, arguments and return types are separated using a double colon (::). The arguments and the return types are separated by the symbol (->). Thus, the above type signature tells us that the sum function takes two arguments of type Int and returns an Int. Note that the function names must always begin with the letters of the alphabet in lower case. The names are usually written in CamelCase style.

You can create a Sum.hs Haskell source file using your favourite text editor, and load the file on to the Glasgow Haskell Compiler interpreter (GHCi) using the following code:

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.

Prelude> :l Sum.hs
[1 of 1] Compiling Main             ( Sum.hs, interpreted )
Ok, modules loaded: Main.

*Main> :t sumInt
sumInt :: Int -> Int -> Int

*Main> sumInt 2 3
5

If we check the type of sumInt with arguments, we get:

*Main> :t sumInt 2 3
sumInt 2 3 :: Int

*Main> :t sumInt 2
sumInt 2 :: Int -> Int

The value of sumInt 2 3 is an Int as defined in the type signature. We can also partially apply the function sumInt with one argument and its return type will be Int -> Int. In other words, sumInt 2 takes an integer and will return an integer with 2 added to it.

Every function in Haskell takes only one argument. So, we can think of the sumInt function as one that takes an argument and returns a function that takes another argument and computes their sum. This return function can be defined as a sumTwoInt function that adds a 2 to an Int using the sumInt function, as shown below:

sumTwoInt :: Int -> Int
sumTwoInt x = sumInt 2 x

The ‘=’ sign in Haskell signifies a definition and not a variable assignment as seen in imperative programming languages. We can thus omit the ‘x’ on either side and the code becomes even more concise:

sumTwoInt :: Int -> Int
sumTwoInt = sumInt 2

By loading Sum.hs again in the GHCi prompt, we get the following:

*Main> :l Sum.hs
[1 of 1] Compiling Main             ( Sum.hs, interpreted )
Ok, modules loaded: Main.

*Main> :t sumTwoInt
sumTwoInt :: Int -> Int

*Main> sumTwoInt 3
5

Let us look at some examples of functions that operate on lists. Consider list ‘a’ which is defined as [1, 2, 3, 4, 5] (a list of integers) in the Sum.hs file (re-load the file in GHCi before trying the list functions).

a :: [Int]
a = [1, 2, 3, 4, 5]

The head function returns the first element of a list:

*Main> head a
1

*Main> :t head
head :: [a] -> a

The tail function returns everything except the first element from a list:

*Main> tail a
[2,3,4,5]

*Main> :t tail
tail :: [a] -> [a]

The last function returns the last element of a list:

*Main> last a
5

*Main> :t last
last :: [a] -> a

The init function returns everything except the last element of a list:

*Main> init a
[1,2,3,4]

*Main> :t init
init :: [a] -> [a]

The length function returns the length of a list:

*Main> length a
5

*Main> :t length
length :: [a] -> Int

The take function picks the first ‘n’ elements from a list:

*Main> take 3 a
[1,2,3]

*Main> :t take
take :: Int -> [a] -> [a]

The drop function drops ‘n’ elements from the beginning of a list, and returns the rest:

*Main> drop 3 a
[4,5]

*Main> :t drop
drop :: Int -> [a] -> [a]

The zip function takes two lists and creates a new list of tuples with the respective pairs from each list. For example:

*Main> let b = ["one", "two", "three", "four", "five"]

*Main> zip a b
[(1,"one"),(2,"two"),(3,"three"),(4,"four"),(5,"five")]

*Main> :t zip
zip :: [a] -> [b] -> [(a, b)]

The let expression defines the value of ‘b’ in the GHCi prompt. You can also define it in a way that’s similar to the definition of the list ‘a’ in the source file.

The lines function takes input text and splits it at newlines:

*Main> let sentence = "First\nSecond\nThird\nFourth\nFifth"

*Main> lines sentence
["First","Second","Third","Fourth","Fifth"]

*Main> :t lines
lines :: String -> [String]

The words function takes input text and splits it on white space:

*Main> words "hello world"
["hello","world"]

*Main> :t words
words :: String -> [String]

The map function takes a function and a list and applies the function to every element in the list:

*Main> map sumTwoInt a
[3,4,5,6,7]

*Main> :t map
map :: (a -> b) -> [a] -> [b]

The first argument to map is a function which is enclosed within parenthesis in the type signature (a -> b). This function takes an input of type ‘a’ and returns an element of type ‘b’. Thus, when operating over a list [a], it returns a list of type [b].

Recursion provides a means of looping in functional programming languages. The factorial of a number, for example, can be computed in Haskell, using the following code:

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

The definition of factorial with different input use cases is called as pattern matching on the function. On running the above example with GHCi, you get:

*Main> factorial 0
1
*Main> factorial 1
1
*Main> factorial 2
2
*Main> factorial 3
6
*Main> factorial 4
24
*Main> factorial 5
120

Functions operating on lists can also be called recursively. To compute the sum of a list of integers, you can write the sumList function as:

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

The notation *(x:xs) represents a list, where ‘x’ is the first element in the list, and ‘xs’ is the rest of the list. On running sumList with GHCi, you get the following:

*Main> sumList []
0
*Main> sumList [1,2,3]
6

Sometimes, you will need a temporary function for a computation, which you will not need to use elsewhere. You can then write an anonymous function. A function to increment an input value can be defined as:

*Main> (\x -> x + 1) 3
4

Such functions are called as Lambda functions, and the ‘\’ represents the notation for the symbol Lambda. Another example is given below:

*Main> map (\x -> x * x) [1, 2, 3, 4, 5]
[1,4,9,16,25]

It is a good practice to write the type signature of the function first when composing programs, and then write the body of the function. Haskell is a functional programming language, and understanding the use of functions is very important.

[Published in Open Source For You (OSFY) magazine, July 2014 edition.]

Haskell, a free and open source programming language, is the outcome of 20 years of research. It has all the advantages of functional programming and an intuitive syntax based on mathematical notation. This article flags off a series in which we will explore Haskell at length.

Haskell is a statically typed, general purpose programming language. Code written in Haskell can be compiled and also used with an interpreter. The static typing helps detect plenty of compile time bugs. The type system in Haskell is very powerful and can automatically infer types. Functions are treated as first-class citizens and you can pass them around as arguments. It is a pure functional language and employs lazy evaluation. It also supports procedural and strict evaluation similar to other programming paradigms.

Haskell code is known for its brevity and is very concise. The latest language standard is Haskell 2010. The language supports many extensions, and has been gaining wide-spread interest in the industry due to its capability to run algorithms on multi-core systems. It has support for concurrency because of the use of software transactional memory. Haskell allows you to quickly create prototypes with its platform and tools. Hoogle and Hayoo API search engines are available to query and browse the list of Haskell packages and libraries. The entire set of Haskell packages are available in Hackage.

The Haskell Platform contains all the software required to get you started on it. On GNU/Linux, you can use your distribution package manager to install the same. On Fedora, for example, you can use the following command:

# yum install haskell-platform

On Ubuntu, you can use the following:

# apt-get install haskell-platform

On Windows, you can download and run HaskellPlatform-2013.2.0.0-setup.exe from the Haskell platform web site and follow the instructions for installation.

For Mac OS X, download either the 32-bit or 64-bit .pkg file, and click on either to proceed with the installation.

The most popular Haskell interpreter is the Glasgow Haskell Compiler (GHC). To use its interpreter, you can run ghci from the command prompt on your system:

$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 

The Prelude prompt indicates that the basic Haskell library modules have been imported for your use.

To exit from GHCi, type :quit in the Prelude prompt:

Prelude> :quit
Leaving GHCi.

The basic data types used in Haskell are discussed below.

A Char data type is for a Unicode character. You can view the type using the command :type at the GHCi prompt:

Prelude> :type 's'
's' :: Char

The ’::’ symbol is used to separate the expression on the left with the data type on the right.

A Bool data type represents a logical value of either True or False.

Prelude> :type True
True :: Bool

Signed numbers with a fixed width are represented by the Int data type. The Integer type is used for signed numbers that do not have a fixed width.

Prelude> 5
5

The Double and Float types are used to represent decimal values. The Double type has better precision for floating point numbers:

Prelude> 3.0
3.0

The basic data types can be combined to form composite types. There are two widely used composite types in Haskell, namely, lists and tuples. A list is a collection of elements of the same data type enclosed within square parenthesis. A list of characters is shown below:

Prelude> :type ['a', 'b', 'c']
['a', 'b', 'c'] :: [Char]

The static typing in Haskell produces errors during compile or load time (in GHCi) when you mix data types inside a list. For example:

Prelude> ['a', 1, 2]

<interactive>:7:7:
    No instance for (Num Char) arising from the literal `1'
    Possible fix: add an instance declaration for (Num Char)
    In the expression: 1
    In the expression: ['a', 1, 2]
    In an equation for `it': it = ['a', 1, 2]

You can have a list of lists as long as they contain the same data type:

Prelude> :type [['a'], ['b', 'c']]
[['a'], ['b', 'c']] :: [[Char]]

A tuple is an ordered list of elements with a fixed size, enclosed within parenthesis, where each element can be of a different data type. For example:

Prelude> :type ('t', True)
('t', True) :: (Char, Bool)

Note that the tuple with type (Char, Bool) is different from the tuple with type (Bool, Char).

Prelude> :t (False, 'f')
(False, 'f') :: (Bool, Char)

Haskell originates from the theory of Lambda calculus, which was developed by Alonzo Church to formally study mathematics. In 1958, John McCarthy created Lisp, that relates programming with Lambda calculus. Robin Milner created a functional programming language called ML (meta language) for automated proofs of mathematical theorems in 1970. During the 1980s, there were a number of lazy functional programming languages scattered across the research community. Miranda was a very popular proprietary programming language released by Research Software Ltd in 1985.

A need arose to unify the different research developments, for which a committee was formed and the first version of the standard was released in 1990. It was called Haskell 1.0, after the mathematician and logician, Haskell Brooks Curry. Subsequently, there were four revisions made - 1.1, 1.2, 1.3 and 1.4. In 1997, the Haskell 98 report was released. In 2009, the Haskell 2010 standard was published and is the latest standard as on date. It has Foreign Function Interface (FFI) bindings to interface with other programming languages. The Hugs interpreter is useful for teaching, while the Glasgow Haskell Compiler (GHC) is very popular. The paper by John Hughes on “Why Functional Programming matters?” in as excellent paper to read. A number of software companies in the industry have begun to use Haskell in production systems.

We shall be exploring more features, constructs and use of the language in future articles.

References

[1] Haskell. http://haskell.org/

[2] Haskell 2010. http://www.haskell.org/haskellwiki/Haskell_2010

[3] Hoogle. http://www.haskell.org/hoogle/

[4] Hayoo. http://holumbus.fh-wedel.de/hayoo/hayoo.html

[5] Hackage. http://hackage.haskell.org/

[6] Haskell Platform. http://www.haskell.org/platform/

[7] Glasgow Haskell Compiler. http://www.haskell.org/ghc/

[8] Alonzo Church. http://www-groups.dcs.st-and.ac.uk/history/Mathematicians/Church.html

[9] John McCarthy. http://www-formal.stanford.edu/jmc/

[10] Lisp. http://en.wikipedia.org/wiki/Lisp_%28programming_language%29

[11] Robin Milner. http://www.cl.cam.ac.uk/archive/rm135/

[12] Miranda. http://miranda.org.uk/

[13] Haskell 1.0. http://www.haskell.org/definition/haskell-report-1.0.ps.gz

[14] Haskell Brooks Curry. http://www-history.mcs.st-andrews.ac.uk/Biographies/Curry.html

[15] Hugs. http://www.haskell.org/hugs/

[16] “Why Functional Programming matters?” http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html

[17] Why functional programming? Why Haskell?. http://book.realworldhaskell.org/read/why-functional-programming-why-haskell.html

Command Functionality
$ sudo /etc/init.d/postgresql start Start server (Ubuntu)
$ psql -U postgres Connect
postgres=# \l Show databases
postgres=# \h Help
postgres=# CREATE DATABASE jerry; Create database
postgres=# DROP DATABASE jerry; Delete database
postgres=# SET search_path TO schema; Use schema
$ psql -U postgres -d Use database
postgres=# \c test Change database
postgres=# \du List users
postgres=# \d List tables
postgres=# CREATE SCHEMA sausalito; Create schema
postgres=# \dn List schema
postgres=# DROP SCHEMA sausalito; Drop schema
postgres=# SELECT * FROM sausalito.employees; Select rows
postgres=# CREATE TABLE sausalito.employees (id INT); Create table
postgres=# INSERT INTO sausalito.employees VALUES (1); Insert record
postgres=# UPDATE sausalito.employees SET id = 4 WHERE id = 2; Update table record
postgres=# DELETE FROM sausalito.employees WHERE id = 3; Delete record
postgres=# DROP TABLE sausalito.employees; Drop table
postgres=# \q Quit from session

Boot from LiveCD ( nixos-graphical-14.12.140.0dbc415-x86_64-linux.iso ), with 40 GB virtual disk, and login as root (no password required).

nixos login: root

[root@nixos:~]#

Start the KDE environment using the following command:

[root@nixos:~]# start display-manager

You can then add the English Dvorak layout (optional) by selecting ‘System Settings’ -> ‘Input Devices’ -> ‘Keyboard settings’ -> ‘Layouts’ -> ‘Configure layouts’ -> ‘Add’ and use the label (dvo) for the new layout. Check that networking works as shown below:

[root@nixos:~]# ifconfig

[root@nixos:~]# ping -c3 www.google.com

You can now partition the disk using ‘fdisk /dev/sda’ and create two partitions (39 GB /dev/sda1 and swap on /dev/sda2). Create the filesystems, and turn on swap using the following commands:

# mkfs.ext4 -L nixos /dev/sda1

# mkswap -L swap /dev/sda2
# swapon /dev/sda2

Generate a basic system configuration file with nixos-generate-config:

# mount /dev/disk/by-label/nixos /mnt

# nixos-generate-config --root /mnt

Update /mnt/etc/nixos/configuration.nix with new packages that you need as illustrated below:

# Edit this configuration file to define what should be installed on
# your system.  Help is available in the configuration.nix(5) man page
# and in the NixOS manual (accessible by running ‘nixos-help’).

{ config, pkgs, ... }:

{
  imports =
    [ # Include the results of the hardware scan.
      ./hardware-configuration.nix
    ];

  # Use the GRUB 2 boot loader.
  boot.loader.grub.enable = true;
  boot.loader.grub.version = 2;
  # Define on which hard drive you want to install Grub.
  boot.loader.grub.device = "/dev/sda";

  # networking.hostName = "nixos"; # Define your hostname.
  networking.hostId = "56db3cd3";
  # networking.wireless.enable = true;  # Enables wireless.

  # Select internationalisation properties.
  # i18n = {
  #   consoleFont = "lat9w-16";
  #   consoleKeyMap = "us";
  #   defaultLocale = "en_US.UTF-8";
  # };

  # List packages installed in system profile. To search by name, run:
  # $ nix-env -qaP | grep wget
  environment.systemPackages = with pkgs; [
    wget emacs24 git python gnuplot notmuch
    haskellPackages.pandoc

    # Installing texlive is slow and incomplete on NixOS
    # (pkgs.texLiveAggregationFun { paths = [ pkgs.texLive pkgs.texLiveExtra pkgs.texLiveBeamer ]; })    
  ];
  # texLive tetex lmodern
  
  # List services that you want to enable:

  # Enable the OpenSSH daemon.
  services.openssh.enable = true;

  # Enable CUPS to print documents.
  # services.printing.enable = true;

  # Enable the X11 windowing system.
  services.xserver.enable = true;
  services.xserver.layout = "us";
  # services.xserver.xkbOptions = "eurosign:e";

  # Enable the KDE Desktop Environment.
  services.xserver.displayManager.kdm.enable = true;
  services.xserver.desktopManager.kde4.enable = true;


  # Define a user account. Don't forget to set a password with ‘passwd’.
  users.extraUsers.apollo = {
    home = "/home/apollo";
    extraGroups = [ "wheel" ];
    useDefaultShell = true;
    isNormalUser = true;
    uid = 1000;
  };

}

Install NixOS to hard disk:

# nixos-install

setting root password...
Enter new UNIX password: ***
Retype new UNIX password: ***

passwd: password updated successfully
installation finished!

You can now reboot into the system:

# reboot

After you login to the console, set a password for the ‘apollo’ user. A screenshot of the desktop is shown below:

[Published in Electronics For You (EFY) magazine, June 2014 edition.]

HCT stands for HDL Complexity Tool, where HDL stands for Hardware Description Language. HCT provides scores that represent the complexity of modules present in integrated circuit (IC) designs. It is written in Perl and released under the GPLv3 and LGPLv3 license. It employs McCabe Cyclomatic Complexity that uses the control flow graph of the program source code to determine the complexity.

There are various factors for measuring the complexity of HDL models such as size, nesting, modularity, and timing. The measured metrics can help designers in refactoring their code, and also help managers to plan project schedules, and allocate resources, accordingly. You can run the tool from the GNU/Linux terminal for Verilog, VHDL, and CDL (Computer Design Language) files or directory sources. HCT can be installed on Fedora using the command:

$ sudo yum install hct

After installation, consider the example project of uart2spi written in Verilog, which is included in this month’s EFY DVD. It implements a simple core for a UART interface, and an internal SPI bus. The uart2spi folder contains rtl/spi under the file directory in your PC: /home/guest/uart2spi/trunk/rtl/spi. Run the HCT tool on the rtl/spi Verilog sources as follows:

$ hct rtl/spi

We get the output:

Directory: /home/guest/uart2spi/trunk/rtl/spi

verilog, 4 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| spi_ctl.v                           20     1       1          0.1724 |
|                      spi_ctl        20     1       1                 |
+----------------------------------------------------------------------+
| spi_core.v                          0      0       1          0.0076 |
|                      spi_core       0      0       1                 |
+----------------------------------------------------------------------+
| spi_cfg.v                           0      0       1          0.0076 |
|                      spi_cfg        0      0       1                 |
+----------------------------------------------------------------------+
| spi_if.v                            15     3       1          0.0994 |
|                      spi_if         15     3       1                 |
+----------------------------------------------------------------------+

The output includes various attributes that are described below:

  • FILENAME is the file that is being parsed. The parser uses the file name extension to recognize the programming language.

  • MODULE refers to the specific module present in the file. A file can contain many modules.

  • IO refers to the input/output registers used in the module.

  • NET includes the network entities declared in the given module. For Verilog, it can be ‘wire’, ‘tri’, ‘supply0’ etc.

  • MCCABE provides the McCabe Cyclomatic Complexity of the module or file.

  • TIME refers to the time taken to process the file.

A specific metric can be excluded from the output using the “–output-exclude=LIST” option. For example, type the following command on a GNU/Linux terminal:

$ hct --output-exclude=TIME rtl/spi 

The output will be;

Directory: /home/guest/uart2spi/trunk/rtl/spi

verilog, 4 file(s)
+----------------------+----------------+--------+---------+-----------+
| FILENAME             | MODULE         | IO     | NET     | MCCABE    |
+----------------------+----------------+--------+---------+-----------+
| spi_ctl.v                               20       1         1         |
|                        spi_ctl          20       1         1         |
+----------------------------------------------------------------------+
| spi_core.v                              0        0         1         |
|                        spi_core         0        0         1         |
+----------------------------------------------------------------------+
| spi_cfg.v                               0        0         1         |
|                        spi_cfg          0        0         1         |
+----------------------------------------------------------------------+
| spi_if.v                                15       3         1         |
|                        spi_if           15       3         1         |
+----------------------------------------------------------------------+

If you want only the score to be listed, you can remove the MODULE listing with the “–output-no-modules” option:

$ hct --output-no-modules rtl/spi

Directory: /home/guest/uart2spi/trunk/rtl/spi

verilog, 4 file(s)
+-----------------------+---------+----------+-------------+-----------+
| FILENAME              | IO      | NET      | MCCABE      | TIME      |
+-----------------------+---------+----------+-------------+-----------+
| spi_ctl.v               20        1          1             0.16803   |
+----------------------------------------------------------------------+
| spi_core.v              0         0          1             0.007434  |
+----------------------------------------------------------------------+
| spi_cfg.v               0         0          1             0.00755   |
+----------------------------------------------------------------------+
| spi_if.v                15        3          1             0.097721  |
+----------------------------------------------------------------------+

The tool can be run on individual files, or recursively on subdirectories with the “-R” option. The output the entire uart2spi project sources is given below:

$ hct -R rtl

Directory: /home/guest/uart2spi/trunk/rtl/uart_core

verilog, 4 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| uart_rxfsm.v                        10     0       1          0.1379 |
|                      uart_rxfsm     10     0       1                 |
+----------------------------------------------------------------------+
| clk_ctl.v                           0      0       1          0.0146 |
|                      clk_ctl        0      0       1                 |
+----------------------------------------------------------------------+
| uart_core.v                         18     1       1          0.1291 |
|                      uart_core      18     1       1                 |
+----------------------------------------------------------------------+
| uart_txfsm.v                        9      0       1          0.1129 |
|                      uart_txfsm     9      0       1                 |
+----------------------------------------------------------------------+

Directory: /home/guest/uart2spi/trunk/rtl/top

verilog, 1 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| top.v                               16     0       1          0.0827 |
|                      top            16     0       1                 |
+----------------------------------------------------------------------+

Directory: /home/guest/uart2spi/trunk/rtl/spi

verilog, 4 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| spi_ctl.v                           20     1       1          0.1645 |
|                      spi_ctl        20     1       1                 |
+----------------------------------------------------------------------+
| spi_core.v                          0      0       1          0.0074 |
|                      spi_core       0      0       1                 |
+----------------------------------------------------------------------+
| spi_cfg.v                           0      0       1          0.0073 |
|                      spi_cfg        0      0       1                 |
+----------------------------------------------------------------------+
| spi_if.v                            15     3       1          0.0983 |
|                      spi_if         15     3       1                 |
+----------------------------------------------------------------------+

Directory: /home/guest/uart2spi/trunk/rtl/lib

verilog, 1 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| registers.v                         5      0       1          0.0382 |
|                      bit_register   5      0       1                 |
+----------------------------------------------------------------------+

Directory: /home/guest/uart2spi/trunk/rtl/msg_hand

verilog, 1 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| uart_msg_handler.v                  0      0       1          0.0192 |
|                      uart_m~ndler   0      0       1                 |
+----------------------------------------------------------------------+

The default behaviour is to dump the output to the terminal. It can be redirected to a file with the “–output-file=FILE” option. You can also specify an output file format, such as “csv” with the “–output-format=FORMAT” option:

$ hct --output-file=/home/guest/project-metrics.csv --output-format=csv rtl/spi 

$ cat /home/guest/project-metrics.csv

Directory: /home/guest/uart2spi/trunk/rtl/spi

verilog, 4 file(s)

 FILENAME    , MODULE    , IO   , NET  , MCCABE  , SLOC  , COMMENT_LINES  , TIME
 spi_ctl.v   ,           , 20   , 1    , 1       , 110   , 48             , 0.1644
             , spi_ctl   , 20   , 1    , 1       , 68    , 6              ,
 spi_core.v  ,           , 0    , 0    , 1       , 46    , 43             , 0.0073
             , spi_core  , 0    , 0    , 1       , 4     , 1              ,
 spi_cfg.v   ,           , 0    , 0    , 1       , 46    , 43             , 0.0075
             , spi_cfg   , 0    , 0    , 1       , 4     , 1              ,
 spi_if.v    ,           , 15   , 3    , 1       , 80    , 44             , 0.0948
             , spi_if    , 15   , 3    , 1       , 38    , 2              ,

There are various yyparse options that are helpful to understand the lexical parsing of the source code. They can be invoked using the following command:

$ hct --yydebug=NN sources

The NN options and their meaning is listed below:

0x01 Lexical tokens
0x02 Information on States
0x04 Shift, reduce, accept driver actions
0x08 Dump of the parse stack
0x16 Tracing for error recovery
0x31 Complete output for debugging

HCT can also be used with VHDL, and Cyclicity CDL (Cycle Description Language) programs. For VHDL, the filenames must end with a .vhdl extension. You can rename .vhd files recursively in a directory (in Bash, for example) using the following script:

for file in `find $1 -name "*.vhd"`
do
  mv $file ${file/.vhd/.vhdl}
done

The “$1” refers to the project source directory that is passed as an argument to the script. Let us take the example of sha256 core written in VHDL, which is also included in this month’s EFY DVD. The execution of HCT on the sha256core project is as follows:

 $  hct rtl

Directory: /home/guest/sha256core/trunk/rtl

vhdl, 6 file(s)
+--------------------+--------------+------+-------+----------+--------+
| FILENAME           | MODULE       | IO   | NET   | MCCABE   | TIME   |
+--------------------+--------------+------+-------+----------+--------+
| sha_256.vhdl                        29     0       1          0.9847 |
|                      sha_256        29     0       1                 |
+----------------------------------------------------------------------+
| sha_fun.vhdl                        1      1       1          0.3422 |
|                                     1      1       1                 |
+----------------------------------------------------------------------+
| msg_comp.vhdl                       20     0       1          0.4169 |
|                      msg_comp       20     0       1                 |
+----------------------------------------------------------------------+
| dual_mem.vhdl                       7      0       3          0.0832 |
|                      dual_mem       7      0       3                 |
+----------------------------------------------------------------------+
| ff_bank.vhdl                        3      0       2          0.0260 |
|                      ff_bank        3      0       2                 |
+----------------------------------------------------------------------+
| sh_reg.vhdl                         19     0       1          0.6189 |
|                      sh_reg         19     0       1                 |
+----------------------------------------------------------------------+

The “-T” option enables the use of threads to speed up computation. The LZRW1 (Lempel–Ziv Ross Williams) compressor core project implements a lossless data compression algorithm. The output of HCT on this project, without threading and with threads enabled, is shown below:

$ time hct HDL

Directory: /home/guest/lzrw1-compressor-core/trunk/hw/HDL

vhdl, 8 file(s)
...
real	0m3.725s
user	0m3.612s
sys     0m0.013s

$ time hct HDL -T

Directory: /home/guest/lzrw1-compressor-core/trunk/hw/HDL

vhdl, 8 file(s)
...
real	0m2.301s
user	0m7.029s
sys     0m0.051s

The supported input options for HCT can be viewed with the “-h” option.

The invocation of HCT can be automated, rechecked for each code check-in that happens to a project repository. The complexity measure is thus recorded periodically. The project team will then be able to monitor, analyse the complexity of each module and decide on any code refactoring strategies.

[Published in Open Source For You (OSFY) magazine, May 2014 edition.]

This article guides readers through the installation of GNU Unified Parallel C, which is designed for high performance computing on large scale parallel machines.

GNU Unified Parallel C is an extension to the GNU C compiler (GCC), which supports execution of Unified Parallel C (UPC) programs. UPC uses the Partitioned Global Address Space (PGAS) model for its implementation. The current version of UPC is 1.2, and a 1.3 draft specification is available. GNU UPC is released under the GPL license, while, the UPC specification is released under the new BSD license. To install it on Fedora, you need to first install the gupc repository:

$ sudo yum install http://www.gccupc.org/pub/pkg/rpms/gupc-fedora-18-1.noarch.rpm

You can then install the gupc RPM using the following command:

$ sudo yum install gupc-gcc-upc

The installation directory is /usr/local/gupc. You will also require the numactl (library for tuning Non-Uniform Memory Access machines) development packages:

$ sudo yum install numactl-devel numactl-libs

To add the installation directory to your environment, install the environment-modules package:

$ sudo yum install environment-modules

You can then load the gupc module with:

# module load gupc-x86_64

Consider the following simple ‘hello world’ example:

#include <stdio.h>

int main()
{
   printf("Hello World\n");
   return 0;
}

You can compile it using:

# gupc hello.c -o hello

Then run it with:

# ./hello -fupc-threads-5

Hello World
Hello World
Hello World
Hello World
Hello World

The argument -fupc-threads-N specifies the number of threads to be run. The program can also be executed using:

# ./hello -n 5

The gupc compiler provides a number of compile and run-time options. The ’-v’ option produces a verbose output of the compilation steps. It also gives information on GNU UPC. An example of such an output is shown below:

# gupc hello.c -o hello -v

Driving: gupc -x upc hello.c -o hello -v -fupc-link
Using built-in specs.
COLLECT_GCC=gupc
COLLECT_LTO_WRAPPER=/usr/local/gupc/libexec/gcc/x86_64-redhat-linux/4.8.0/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ...
Thread model: posix
gcc version 4.8.0 20130311 (GNU UPC 4.8.0-3) (GCC) 
COLLECT_GCC_OPTIONS='-o' 'hello' '-v' '-fupc-link' '-mtune=generic' '-march=x86-64'
...
GNU UPC (GCC) version 4.8.0 20130311 (GNU UPC 4.8.0-3) (x86_64-redhat-linux)
	compiled by GNU C version 4.8.0 20130311 (GNU UPC 4.8.0-3),
        GMP version 5.0.5, MPFR version 3.1.1, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
...
#include "..." search starts here:
#include <...> search starts here:
 /usr/local/gupc/lib/gcc/x86_64-redhat-linux/4.8.0/include
 /usr/local/include
 /usr/local/gupc/include
 /usr/include
End of search list.
GNU UPC (GCC) version 4.8.0 20130311 (GNU UPC 4.8.0-3) (x86_64-redhat-linux)
	compiled by GNU C version 4.8.0 20130311 (GNU UPC 4.8.0-3), 
        GMP version 5.0.5, MPFR version 3.1.1, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 9db6d080c84dee663b5eb4965bf5012f
COLLECT_GCC_OPTIONS='-o' 'hello' '-v' '-fupc-link' '-mtune=generic' '-march=x86-64'
 as -v --64 -o /tmp/cccSYlmb.o /tmp/ccTdo4Ku.s
...
COLLECT_GCC_OPTIONS='-o' 'hello' '-v' '-fupc-link' '-mtune=generic' '-march=x86-64'
...

The -g option will generate debug information. To output debugging symbol information in DWARF-2 (Debugging With Attributed Record Formats), use the -dwarf-2-upc option. This can be used with GDB-UPC, a GNU debugger that supports UPC.

The -fupc-debug option will also generate filename and the line numbers in the output.

The optimization levels are similar to the ones supported by GCC: ’-O0’, ’-O1’, ’-O2’, and ’-O3’.

Variables that are shared among threads are declared using the ‘shared’ keyword. Examples include:

shared int i;
shared int a[THREADS];
shared char *p;

‘THREADS’ is a reserved keyword that represents the number of threads that will get executed run-time. Consider a simple vector addition example:

#include <upc_relaxed.h>
#include <stdio.h>

shared int a[THREADS];
shared int b[THREADS];
shared int vsum[THREADS];

int
main()
{
  int i;

  /* Initialization */
  for (i=0; i<THREADS; i++) {
    a[i] = i + 1;               /* a[] = {1, 2, 3, 4, 5}; */
    b[i] = THREADS - i;         /* b[] = {5, 4, 3, 2, 1}; */
  }

  /* Computation */
  for (i=0; i<THREADS; i++)
    if (MYTHREAD == i % THREADS)
      vsum[i] = a[i] + b[i];

  upc_barrier;

  /* Output */
  if (MYTHREAD == 0) {
    for (i=0; i<THREADS; i++)
      printf("%d ", vsum[i]);
  }

  return 0;
}

‘MYTHREAD’ indicates the thread that is currently running. upc_barrier is a blocking synchronization primitive that ensures that all threads complete before proceeding further. Only one thread is required to print the output, and THREAD 0 is used for the same. The program can be compiled, and executed using:

# gupc vector_addition.c -o vector_addition
# ./vector_addition -n 5

6 6 6 6 6

The computation loop in the above code can be simplified with the upc_forall statement:

#include <upc_relaxed.h>
#include <stdio.h>

shared int a[THREADS];
shared int b[THREADS];
shared int vsum[THREADS];

int
main()
{
  int i;

  /* Initialization */
  for (i=0; i<THREADS; i++) {
    a[i] = i + 1;               /* a[] = {1, 2, 3, 4, 5}; */
    b[i] = THREADS - i;         /* b[] = {5, 4, 3, 2, 1}; */
  }

  /* Computation */
  upc_forall(i=0; i<THREADS; i++; i)
      vsum[i] = a[i] + b[i];

  upc_barrier;

  if (MYTHREAD == 0) {
    for (i=0; i<THREADS; i++)
      printf("%d ", vsum[i]);
  }

  return 0;
}

The upc_forall construct is similar to a for loop, except, that it accepts a fourth parameter, the affinity field. It indicates the thread on which the computation runs. It can be an integer that is internally represented as integer % THREADS, or it can be an address corresponding to a thread. The program can be compiled and tested with:

# gupc upc_vector_addition.c -o upc_vector_addition
# ./upc_vector_addition -n 5

6 6 6 6 6

The same example can also be implemented using shared pointers:

#include <upc_relaxed.h>
#include <stdio.h>

shared int a[THREADS];
shared int b[THREADS];
shared int vsum[THREADS];

int
main()
{
  int i;
  shared int *p1, *p2;

  p1 = a;
  p2 = b;

  /* Initialization */
  for (i=0; i<THREADS; i++) {
    *(p1 + i) = i + 1;          /* a[] = {1, 2, 3, 4, 5}; */
    *(p2 + i) = THREADS - i;    /* b[] = {5, 4, 3, 2, 1}; */
  }

  /* Computation */
  upc_forall(i=0; i<THREADS; i++, p1++, p2++; i)
      vsum[i] = *p1 + *p2;

  upc_barrier;

  if (MYTHREAD == 0)
	for (i = 0; i < THREADS; i++)
		printf("%d ", vsum[i]);

  return 0;
}
# gupc pointer_vector_addition.c -o pointer_vector_addition
# ./pointer_vector_addition -n 5

6 6 6 6 6

Memory can also be allocated dynamically. The upc_all_alloc function will allocate collective global memory that is shared among threads. A collective function will be invoked by every thread. The upc_global_alloc function will allocate non-collective global memory which will be different for all threads in the shared address space. The upc_alloc function will allocate local memory for a thread. Their respective declarations are as follows:

shared void *upc_all_alloc (size_t nblocks, size_t nbytes);
shared void *upc_global_alloc (size_t nblocks, size_t nbytes);
shared void *upc_alloc (size_t nbytes);

To protect access to shared data, you can use the following synchronization locks:

void upc_lock (upc_lock_t *l)
int upc_lock_attempt (upc_lock_t *l)
void upc_unlock(upc_lock_t *l)

There are two types of barriers for synchronizing code. The upc_barrier construct is blocking. The non-blocking barrier uses upc_notify (non-blocking), and upc_wait (blocking) constructs. For example:

#include <upc_relaxed.h>
#include <stdio.h>

int
main()
{
  int i;

  for (i=0; i<THREADS; i++) {
    upc_notify;

    if (i == MYTHREAD)
      printf("Thread: %d\n", MYTHREAD);

    upc_wait;
  }

  return 0;
}

The corresponding output is shown below:

# gupc count.c -o count
# ./count -n 5

Thread:  0
Thread:  1
Thread:  2
Thread:  3
Thread:  4

You can refer the GUPC user guide for more information.

[Published in Electronics For You (EFY) magazine, January 2014 edition.]

Drawtiming is a free/open source software tool that can be used to generate digital circuit timing diagrams. It is released under the GNU General Public License (GPL). The tool accepts text file as an input from the user and generates image output in different file formats such as PNG, JPEG, PostScript, and PDF. The input needs to adhere to a specific syntax to describe the different signals, their inter-relationships, and transitions as described in the next section with examples.

Before you can try the examples, you need to install the drawtiming tool in your GNU/Linux system. Installation steps may be different from system to system. To install this software in Ubuntu 12.10, just click on Ubuntu Software Centre option from desktop and search for Drawtiming to install it.

For a basic input command example to generate a clock for three periods, the syntax is written as:

CLOCK=0.
CLOCK=1.
CLOCK=0.

A period (.) is used to mark the end of each clock cycle. The first clock period lists and sets the inital states of the signals. Save the above three-line syntax as a .txt file. Here, we name the file as ‘basic.txt’ and save it in a folder named as, say, EFYdraw. Note that the syntax is case sensitive. To generate the timing diagram, open EFYdraw from the terminal window using ‘cd’ command and enter the following command against the prompt, and you will get the output diagram as shown in Fig. 1.

$ drawtiming -o basic.jpg basic.txt
Figure 1.

Figure 1.

The tick keyword can also indicate a clock cycle. The following syntax creates a single period clock as shown below:

CLOCK=tick.

The output diagram is shown in Fig. 2.

Figure 2.

Figure 2.

The order in which the signal commands are listed determines the order in which they appear in the output. Multiple signals are separated by commas as shown below:

CLOCK=tick, FLAG=0.

The output diagram is shown in Fig. 3.

Figure 3.

Figure 3.

A change in one signal that triggers a change in another can be expressed using arrow notation (=>). In the following example (Fig. 4), when the address latch enable (ALE) signal changes state, the read signal (RD) changes its state in the subsequent cycle. The syntax is given below:

ALE=tick,    RD=0.
ALE => RD=1, ALE=0.
Figure 4.

Figure 4.

If the transition is in the same clock cycle, it can be indicated in the same clock period. For instance, both CLK and CLK2 change in the second clock period:

CLK=0,    CLK2=0.
CLK=tick, CLK2=1.

The output is shown in Fig. 5.

Figure 5.

Figure 5.

If there are multiple signal changes, you can separate them with a comma. For example, LED is turned on when both the chip select (CS) and output enable (OE) signals change state; then the syntax is written as:

CS=0, OE=0, LED=Z.
CS=1, OE=1.
CS, OE => LED=ON.

The output is as shown in Fig. 6.

Figure 6.

Figure 6.

A semicolon can be used to separate a list of dependency signal changes for the same clock period, which is illustrated in the third clock period (refer Fig. 7) in the following example. The syntax is as given below:

CS=0, OE=0, LED=Z, DATA=Z.
CS=1, OE=1.
CS, OE => LED=ON;
DATA=DATA.
Figure 7.

Figure 7.

Drawtiming has numerous command line options which can be seen by using the -h option. The supported output image formats are listed in ImageMagick website. A PDF output of the basic.txt example can be created by specifying the .pdf filename extension as shown below:

$ drawtiming -o basic.pdf basic.txt

Here, the output will be the same as shown in Fig. 1, only file format is changed to .pdf.

The output image can be scaled with the -x option. To generate an image that is twice the default size, you can use the command as given below:

$ drawtiming -x 2 -o basic-twice.jpg basic.txt

The output is as shown in Fig. 8.

Figure 1.

Figure 1.

Figure 8.

Figure 8.

If you want to be explicit about the pixel width and height, the -p option followed by width ‘x’ height can be specified as given below:

$ drawtiming -p 250x75 -o basic-p.jpg basic.txt

The output is as shown in Fig. 9.

Figure 1.

Figure 1.

Figure 9.

Figure 9.

The default cell width and height are 64 and 48 pixels, respectively. The -w and -c options are used to modify them:

$ drawtiming -c 100 -o basic-c.jpg basic.txt

The output is as shown in Fig. 10.

Figure 1.

Figure 1.

Figure 10.

Figure 10.

The line width can be changed using the -l option. For example:

$ drawtiming -l 3 -o basic-l.jpg basic.txt

The output is as shown in Fig. 11.

Figure 1.

Figure 1.

Figure 11.

Figure 11.

The default font size is 25 points. You can change it with the -f option. You can also specify a different font using the –font option.

$ drawtiming -f 10 -o basic-f.jpg basic.txt

The output is as shown in Fig. 12.

Figure 1.

Figure 1.

Figure 12.

Figure 12.

Timing delays can be displayed in the output using -tD> construct between any two signals. In a simple I/O write cycle, the minimum time between a valid address and the I/O write (IOW) strobe is shown as 92 units (minimum) as follows:

ADDRESS="VALID ADDRESS", DATA="", IOW=1.
DATA="", IOW=0.
ADDRESS -92min> IOW;
DATA="VALID DATA".
IOW=1.
IOW -516min> DATA;
ADDRESS="", DATA="".

The output is as shown in Fig. 13.

Figure 13.

Figure 13.

For a real-world example, let us consider the write cycle of a 68008 microprocessor. During the write cycle, the CPU first asserts the read/write (RW) signal for write operation, followed by the address and data signals. The data strobe (DS) signal is then asserted, and the CPU waits for the receiver to acknowledge the same, as indicated by the data transfer acknowledge (DTACK) signal. The syntax for this ‘write’ cycle is as given below:

CLK=0, ADDRESS=Z, AS=1, RW=X, DS=1, DATA=X, DTACK=1.
CLK=1, RW=1, DATA=Z.
CLK=0, ADDRESS="VALID ADDR".
CLK=1, AS=0, RW=0.
CLK=0, DATA="VALID DATA".
CLK=1, DS=0.
CLK=0, DTACK=0.
CLK=1.
CLK=0, AS=1, DS=1, DTACK=1.
CLK=1, ADDRESS="", RW=1, DATA="".
.

The output is as shown in Fig. 14.

Figure 14.

Figure 14.

The 68008 read cycle is similar to the write cycle, except that the read signal in RW is asserted, and the DS signal is asserted one clock period earlier as shown below:

CLK=0, ADDRESS=Z, AS=1, RW=X, DS=1, DATA=X, DTACK=1.
CLK=1, RW=1, DATA=Z.
CLK=0, ADDRESS="VALID ADDR".
CLK=1, AS=0, DS=0.
CLK=0.
CLK=1.
CLK=0, DTACK=0.
CLK=1.
CLK=0, AS=1, DS=1, DATA="DATA", DTACK=1.
CLK=1, ADDRESS="", DATA=Z.
.

The output is as shown in Fig. 15.

Figure 15.

Figure 15.

[Published in Open Source For You (OSFY) magazine, October 2013 edition.]

GNU Parallel is a tool for running jobs in parallel in a Bash environment. The job can be a single command or a script, with variable arguments. The simultaneous execution can occur on remote machines as well. Released under the GPLv3+ license, you can install it on Fedora using the following command:

$ sudo yum install parallel

After installation, you need to remove ’–tollef’ from the /etc/parallel/config file, if it is present. This option will be permanently removed in future releases.

GNU Parallel takes a command and a list of arguments for processing. The arguments are provided in the command line after the notation ’:::’, and the command is executed for each argument. For example:

$ parallel echo ::: alpha beta gamma
alpha
beta
gamma

You can pass multiple arguments to GNU parallel, and it will run the command for every combination of the input, as shown below:

$ parallel echo ::: 0 1 ::: 0 1
0 0
0 1
1 0
1 1

The order in the output may be different. The tool provides a number of replacement string options. The default string ‘{}’ represents the input:

$ parallel echo {} ::: /tmp
/tmp

The replacement string ‘{/}’ removes everything up to and including the last forward slash:

$ parallel echo {/} ::: /tmp/stdio.h
stdio.h

If you want to return the path only, use the ‘{//}’ string:

$ parallel echo {//} ::: /tmp/stdio.h
/tmp

The string ‘{.}’ removes any filename extension:

$ parallel echo {.} ::: /tmp/stdio.h
/tmp/stdio

The output of a GNU Parallel command may not necessarily be in the order in which the input arguments are listed. For example:

$ parallel sleep {}\; echo {} ::: 5 2 1 4 3
1
2
4
3
5

If you wish to enforce the order of execution, use the ’-k’ option, as shown below:

$ parallel -k sleep {}\; echo {} ::: 5 2 1 4 3
5
2
1
4
3

A test script, for example, may need to be run ‘N’ times for the same argument. This can be accomplished with the following code:

$ seq 10 | parallel -n0 echo "Hello, World"
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World
Hello, World

The ’-n’ option represents the maximum number of arguments in the command line.

The commands that will get executed by GNU Parallel can be observed with the ’–dry-run’ option, as illustrated below:

$ parallel --dry-run -k sleep {}\; echo {} ::: 5 2 1 4 3
sleep 5; echo 5
sleep 2; echo 2
sleep 1; echo 1
sleep 4; echo 4
sleep 3; echo 3

The ’–eta’ option will give an estimate on the time it will take to complete a job:

$ parallel --eta -k sleep {}\; echo {} ::: 5 2 1 4 3

Computers / CPU cores / Max jobs to run
1:local / 4 / 4

Computer:jobs running/jobs completed/%of started jobs/Average seconds to complete
ETA: 5s 1left 1500avg  local:1/4/100%/1.0s 
2
1
4
3
ETA: 1s 0left 1.00avg  local:0/5/100%/1.0s 

Suppose you have a large number of log files that you wish to zip and archive, you can run the gzip command in Parallel, as shown below:

$ parallel gzip ::: *.log

To unzip them all, you can use the following command:

$ parallel gunzip ::: *.gz

The ‘convert’ command is useful to transform image files. High resolution images can be scaled to a lower resolution using the following command:

$ convert -resize 512x384 file.jpg file_web.jpg

If you have a large number of files that you wish to resize, you can parallelize the task, as shown below:

$ find . -name '*.jpg' | parallel convert -resize 512x384 {} {}_web.jpg

GNU Parallel with wget can help in parallel downloads of large Linux kernel releases, as shown below:

$ parallel wget ::: www.kernel.org/pub/linux/kernel/v3.x/linux-3.11.tar.xz \
                    www.kernel.org/pub/linux/kernel/v3.x/linux-3.10.10.tar.xz

The URLs can also be stored in a text file (“input.txt”), and passed as an argument to Parallel:

$ parallel -a input.txt wget

The file “input.txt” contains:

https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.11.tar.xz
https://www.kernel.org/pub/linux/kernel/v3.x/linux-3.10.10.tar.xz

The downloaded kernel images can also be extracted in Parallel:

$ find . -name \*.tar.xz | parallel tar xvf

A ‘for’ loop in a Bash script can be parallelised. In the following script, the file sizes of all the text files are printed:

#!/bin/sh

for file in `ls *.txt`; do
  ls -lh "$file"
done | cut -d' ' -f 5

The parallelized version is as follows:

$ ls *.txt | parallel "ls -lh {}" | cut -d' ' -f 5

The number of CPUs and cores in your system can be listed with GNU Parallel:

$ parallel --number-of-cpus
1
$ parallel --number-of-cores
4

The ’-j’ option specifies the number of jobs to be run in parallel. If the value 0 is given, GNU Parallel will try to start as many jobs as possible. The ‘+ N’ option with ’-j’ adds N jobs to the CPU cores. For example:

$ find . -type f -print | parallel -j+2 ls -l {}

The input to GNU parallel can also be provided in a tabular format. Suppose you want to run ping tests for different machines, you can have a text file with the first column indicating the ping count, and the second column listing the hostname or the IP address. For example:

$ cat hosts.txt 
1 127.0.0.1
2 localhost

You can run the tests in parallel using the following code:

$ parallel -a hosts.txt --colsep ' ' ping -c {1} {2}

PING 127.0.0.1 (127.0.0.1) 56(84) bytes of data.
64 bytes from 127.0.0.1: icmp_seq=1 ttl=64 time=0.074 ms

--- 127.0.0.1 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 0.074/0.074/0.074/0.000 ms

PING localhost.localdomain (127.0.0.1) 56(84) bytes of data.
64 bytes from localhost.localdomain (127.0.0.1): icmp_seq=1 ttl=64 time=0.035 ms
64 bytes from localhost.localdomain (127.0.0.1): icmp_seq=2 ttl=64 time=0.065 ms

--- localhost.localdomain ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1000ms
rtt min/avg/max/mdev = 0.035/0.050/0.065/0.015 ms

GNU Parallel can also execute jobs on remote machines, for which you need to first test that ssh works:

$ SERVER1=localhost
$ ssh $SERVER1 echo "Eureka"
guest@localhost's password: 
Eureka

You can then invoke commands or scripts to be run on SERVER1, as shown below:

$  parallel -S $SERVER1 echo "Eureka from " ::: $SERVER1
guest@localhost's password: 
Eureka from localhost

Files can also be transferred to remote machines using the ’–transfer’ option. Rsync is used internally for the transfer. An example is shown below:

$  parallel -S $SERVER1 --transfer cat ::: /tmp/host.txt 
guest@localhost's password: 
1 127.0.0.1
2 localhost

Refer to the GNU Parallel tutorial and manual page for more options and examples.

[Published in Open Source For You (OSFY) magazine, October 2013 edition.]

Sparse is a semantic parser written for static analysis of the Linux kernel code. Here’s how you can use it to analyse Linux kernel code.

Sparse implements a compiler front-end for the C programming language, and is released under the Open Software License (version 1.1). You can obtain the latest sources via git:

$ git clone git://git.kernel.org/pub/scm/devel/sparse/sparse.git 

You can also install it on Fedora using the following command:

$ sudo yum install sparse

The inclusion of ‘C=1’ to the make command in the Linux kernel will invoke Sparse on the C files to be compiled. Using ‘make C=2’ will execute Sparse on all the source files. There are a number of options supported by Sparse that provide useful warning and error messages. To disable any warning, use the ’-Wno-option’ syntax. Consider the following example:

void
foo (void)
{
}

int
main (void)
{
  foo();

  return 0;
}

Running sparse on the above decl.c file gives the following output:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include decl.c

decl.c:2:1: warning: symbol 'foo' was not declared. Should it be static?

The ’-Wdecl’ option is enabled by default, and detects any non-static variables or functions. You can disable it with the ’-Wno-decl’ option. To fix the warning, the function foo() should be declared static. A similar output was observed when Sparse was run on Linux 3.10.9 kernel sources:

arch/x86/crypto/fpu.c:153:12: warning: symbol 'crypto_fpu_init' was not declared. 
Should it be static?

While the C99 standard allows declarations after a statement, the C89 standard does not permit it. The following decl-after.c example includes a declaration after an assignment statement:

int
main (void)
{
  int x;

  x = 3;

  int y;

  return 0;
}

When using C89 standard with the ’-ansi’ or ’-std=c89’ option, Sparse emits a warning, as shown below:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include -ansi decl-after.c

decl-after.c:8:3: warning: mixing declarations and code

This Sparse command line step can be automated with a Makefile:

TARGET = decl-after

SPARSE_INCLUDE = -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
                 -I/usr/include

SPARSE_OPTIONS = -ansi

all:
	sparse $(SPARSE_INCLUDE) $(SPARSE_OPTIONS) $(TARGET).c

clean:
	rm -f $(TARGET) *~ a.out

If a void expression is returned by a function whose return type is void, Sparse issues a warning. This option needs to be explicitly specified with a ’-Wreturn-void’. For example:

static void
foo (int y)
{
  int x = 1;

  x = x + y;
}

static void
fd (void)
{
  return foo(3);
}

int
main (void)
{
  fd();

  return 0;
}

Executing the above code with Sparse results in the following output:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include -Wreturn-void void.c

void.c:12:3: warning: returning void-valued expression

The ’-Wcast-truncate’ option warns about truncation of bits during casting of constants. This is enabled by default. An 8-bit character is assigned more than it can hold in the following:

int
main (void)
{
  char i = 0xFFFF;
  
  return 0;
}

Sparse warns of truncation for the above code:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include trun.c 

trun.c:4:12: warning: cast truncates bits from constant value (ffff becomes ff)

A truncation warning from Sparse for Linux 3.10.9 kernel is shown below:

arch/x86/kvm/svm.c:613:17: warning: cast truncates bits from 
constant value (100000000 becomes 0)

Any incorrect assignment between enums is checked with the ’-Wenum-mismatch’ option. To disable this check, use ’-Wno-enum-mismatch’. Consider the following enum.c code:

enum e1 {a};
enum e2 {b};

int
main (void)
{
  enum e1 x;
  enum e2 y;

  x = y;

  return 0;
}

Testing with Sparse, you get the following output:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include enum.c

enum.c:10:7: warning: mixing different enum types
enum.c:10:7:     int enum e2  versus
enum.c:10:7:     int enum e1     

Similar Sparse warnings can also be seen for Linux 3.10.9:

drivers/leds/leds-lp3944.c:292:23: warning: mixing different enum types
drivers/leds/leds-lp3944.c:292:23:     int enum led_brightness  versus
drivers/leds/leds-lp3944.c:292:23:     int enum lp3944_status 

NULL is of pointer type, while, the number 0 is of integer type. Any assignment of a pointer to 0 is flagged by the ’-Wnon-pointer-null’ option. This warning is enabled by default. An integer pointer ‘p’ is set to zero in the following example:

int
main (void)
{
  int *p = 0;

  return 0;
}

Sparse notifies the assignment of 0 as a NULL pointer:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include nullp.c 

nullp.c:4:12: warning: Using plain integer as NULL pointer

Given below is another example of this warning in Linux 3.10.9:

arch/x86/kvm/vmx.c:8057:48: warning: Using plain integer as NULL pointer

The corresponding source code on line number 8057 contains:

vmx->nested.apic_access_page = 0;

The GNU Compiler Collection (GCC) has an old, non-standard syntax for initialisation of fields in structures or unions:

static struct
{
  int x;
} local = { x: 0 };

int
main (void)
{
  return 0;
}

Sparse issues a warning when it encounters this syntax, and recommends the use of the C99 syntax:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include old.c 

old.c:4:13: warning: obsolete struct initializer, use C99 syntax

This option is also enabled by default. The ’-Wdo-while’ option checks if there are any missing parentheses in a do-while loop:

int
main (void)
{
  int x = 0;

  do
    x = 3;
  while (0); 

  return 0;
}

On running while.c with Sparse, you get:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include -Wdo-while while.c

while.c:7:5: warning: do-while statement is not a compound statement

This option is not enabled by default. The correct use of the the do-while construct is as follows:

int
main (void)
{
  int x = 0;

  do {
    x = 3;
  } while (0); 

  return 0;
}

A preprocessor conditional that is undefined can be detected with the ’-Wundef’ option. This must be specified explicitly. The preprocessor FOO is not defined in the following undef.c code:

#if FOO
#endif

int
main (void)
{
  return 0;
}

Executing undef.c with Sparse, the following warning is shown:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include -Wundef undef.c

undef.c:1:5: warning: undefined preprocessor identifier 'FOO

The use of parenthesised strings in array initialisation is detected with the ’-Wparen-string’ option:

int
main (void)
{
  char x1[] = { ("hello") };

  return 0;
}

Sparse warns of parenthesised string initialization for the above code:

$ sparse -I/usr/include/linux -I/usr/lib/gcc/x86_64-redhat-linux/4.7.2/include \
         -I/usr/include -Wparen-string paren.c

paren.c:4:18: warning: array initialized from parenthesized string constant
paren.c:4:18: warning: too long initializer-string for array of char

The ’-Wsparse-all’ option enables all warnings, except those specified with ’-Wno-option’. The width of a tab can be specified with the ’-ftabstop=WIDTH’ option. It is set to 8 by default. This is useful to match the right column numbers in the errors or warnings.

You can refer to the following manual page for more available options:

$ man sparse

I attended Functional Conf 2014 between October 9-11, 2014 at Hotel Chancery Pavilion, Bengaluru.

Day I

Stage

The first day began with the keynote by Dr. Venkat Subramaniam on the “The Joy of Functional Programming”. The talk was centered around what is ‘mainstream’, and why something that is mainstream is not necessarily the ideal approach. He gave examples on writing functional programs in Java, and how these code expressions are easy to read and test.

I then attended the talk on “Functional Reactive UIs with Elm” by Shashi Gowda. He gave an introduction to the Elm functional programming language with UI reactive examples. The syntax of Elm is similar to that of Haskell. The idea is to write less code for creating interactive applications, and Elm generates HTML, CSS and Javascript. There are also d3.js bindings for Elm.

The talk on “Applying functional programming principles to large scale data processing” by Kishore Nallan from Indix introduced the “Lambda Architecture”. They scrap product details from web pages worldwide, and receive 4 TB of data every day. The architecture uses an append-only database, and has multiple readers and views for the data. You can check their engineering.indix.com/blog for more information on their attempts to process large data. Scalding, Cascading, Apache Spark, and Storm are tools that they are experimenting with.

Thomas Gazagnaire talk on “Compile your own cloud with Mirage OS v2.0” was very interesting on how they stripped down the entire OS and applications, and re-wrote them in OCaml for use in production environments. The Mirage OS is a unikernel and targets the Xen hypervisor. It is type safe, and faster to deploy and use. It uses light-weight threads. OPAM is the OCaml Package Manager. IRMIN is an example of a distributed database implemented in OCaml. The TLS protocol was implemented in pure OCaml and deployed as a service. The demo server is available at tls.openmirage.org.

“Property based testing for functional domain models” by Debasish Ghosh introduced the concept of generative data for tests in Scala. The idea is from the QuickCheck library and property-based testing in Haskell. This allows you to focus on executable domain rules. We can get some properties for free in statically typed languages. He mentioned shapeless, a type class and dependent type generic programming library for Scala, and also Algebird, which provides Abstract Algebra for Scala.

Vagmi Mudumbai wrote a simple TODO MVC web application using ClojureScript and Om in his “ClojureScript and Om - Pragmatic functional programming in the Javascript Land” talk. Clojure and ClojureScript can help you write concise code for the problem you want to solve. The immutability of Clojure and the DOM manipulation mutability of React.js complement each other well in implementing performance-savvy web sites.

“Learning (from) Haskell - An experience report” by Aditya Godbole was an attempt to teach functional problem solving using Gofer in an organization, and the lessons learnt.

At the end of the day, a Fish Bowl was organized where people discussed the choice of functional programming language for development, and the also shared their experiences on how they solved problems in the industry using functional programming.

After dinner, there was a BoF session on Clojure, but, it ended with mostly discussions on different programming paradigms, and functional programming languages.

Day II

The first keynote on the second day was by Bruce Tate on “Fear: The Role of Fear in Language Adoption”. He classified the challenges in moving to functional programming into two categories - paralyzing fears and motivational fears. The paralyzing fears are on adoption, cost and getting developers. These can be overcome by building communities, having object-oriented languages implement functional programming features, better deployment options, and with cleaner interfaces. The motivating fears can be overcome by the need for handling code complexity, software to run for multi-core and large distributed systems, and for solving complex problems. He also mentioned that he sees three large programming language communities today - a hybrid, only functional programming, and the JavaScript land.

Morten

Morten Kromberg introduced APL (A Programming Language) and Dyalog in his “Pragmatic Functional Programming using Dyalog” talk. APL was invented by Kenneth E. Iverson, an ACM Turing award recipient. Conventions Governing Order of Evaluation by Kenneth explains the context and need for APL. You can try the language using the online REPL at tryapl.org. There are no reserved keywords in this language. Morten also gave a demo of MiServer which is a free and open source web server written in APL. A number of libraries are also available at tools.dyalog.com/library/.

Tejas Dinkar talked on “Monads you already use (without knowing it)” where he tried to mimic the functionality of Haskell Monads in Ruby, but, there are differences in their actual implementation.

“Purely functional data structures demystified” by Mohit Thatte was an excellent talk that illustrates the thesis on Purely Functional Data Structures by Chris Okasaki. Mohit explained how data structures can be built on existing lists, and structural decomposition is an effective way to model complex data. An abstract data type (ADT) can thus be structurally decomposed using list data structures. Every abstract data type can be defined by its operations and invariants. For example, the stack has both push and pop operations, and the invariant is the property of a stack to follow Last In First Out (LIFO). Most programming languages don’t have an expressive power to specify the invariants. He explained functional data structures built with Clojure in simple words, and gave plenty of examples to illustrate the concepts.

I had a chance to meet Ramakrishnan Muthukrishnan, who has been a Debian contributor since 2001. Ramakrishnan’s talk was “An introduction to Continuation Passing Style (CPS)” using the Scheme programming language. A continuation is what is needed to complete the rest of the computation. It provides an alternative model for the use of stacks between function calls. He gave plenty of examples on how to convert an existing piece of code into CPS. Will Byrd’s Google Hangout talk on Introduction to Continuations, call/cc, and CPS was recommended.

“Elixir Today: a round-up on state of Elixir and it’s ecosystem” talk by Akash Manohar gave an introduction to the Elixir programming language. The language is built on the Erlang VM, and the community has taken lot of goodies from the Ruby world. Mix is the tool used to create, build and test Elixir projects, and Hex is the package manager used for Erlang. Elixir code can be deployed to Heroku using a buildpack. A number of useful software are already available - Poison is a JSON parser, Hound for browser automation and integration tests, Ecto is a DSL for communicating with databases, Phoenix is a web frawework for real-time, fault-tolerant applications, and Calliope is an Elixir HAML parser.

The final keynote of the conference was a brilliant talk by Daniel Steinberg on “Methodologies, Mathematics, and the Metalinguistic Implications of Swift”. He began on how people learn mathematics, and why we should reconsider the way we teach geometry. He emphasized that we always try to learn from someone in school (games, for example). Instead of presenting a programming language grammar, the rules can be presented in a playful way. Individuals and interactions are very important in problem solving. Math has a soul and it is beautiful. After providing proofs in geometry with beautiful illustrations, he goes on to say that there are things in mathematics that we can prove, and things that we cannot prove, and we have to accept that, giving examples from the Swift programming language. This was the best talk in the conference.

Day III

Banner

I attended the “Clojure Deep-dive” workshop by Baishampayan Ghose (BG). He started with the basics of Clojure and an introduction to functional style of programming. Clojure is opinionated, and the emphasis is on simplicity and fast problem solving. It involves programming at the speed of thought, and aims to make you more productive.

We used the Clojure REPL to practice writing simple functions. You need to determine the data structures that you want to use first, and then work on writing functions. In Clojure, data is of greater importance than code. The Emacs Clojure Starter Kit can be used to get the required environment to work with the REPL. Clojuredocs is a useful quick reference.

We then worked on solving a real problem of counting the most frequently used words from the ‘Alice in Wonderland’ book from Project Gutenberg. BG then explained the use and power of macros, multimethods, and concurrency capabilities in Clojure. Macros allow DSLs to be represented in the Clojure language itself. There is a core.typed library for static typing. core.async can be used for asynchronous programming. Enlive is a selector based (CSS) templating library, and Ring is a Clojure web applications library. You can find more goodies from the The Clojure Toolbox.

A couple of online resources to get started with Clojure are Clojure for the Brave and True and Clojure from the Ground Up.

The video recordings of the talks should be made available in YouTube.

I would like to thank Manufacturing System Insights for sponsoring my trip to the conference.

« OLDER POSTS