Tag Archive : programming

/ programming

Introduction to JavaScript

December 9, 2015 | Article | No Comments

JavaScript, standardized as ECMAScript, is a popular language especially when you want to build a web-based application. JavaScript is (not only) the programming language of the web, though we will discuss it why we say not only. In modern day, all modern web browsers – on desktop, game consoles, tablets, and smart phones – ship JavaScript interpreters. This makes JavaScript the most ubiquitos programming language in history.

While HTML (and HTML5) acts just as a skeleton and CSS3 act as decorator, JavaScript do the logic in client side. It is used to specify the behavior of a web page.

If you are already familiar with other programming language, you should be able to learn JavaScript quickly. However, we should note something about JavaScript: JavaScript use unique programming model. JavaScript also has nothing to do with Java programming language. They are different in concept and design.

JavaScript is a Script

JavaScript is a scripting language. That means, JavaScript cannot run without an interpreter. Here we know what the interpreters are: browsers.

A scripting language is a lightweight programming language. In client-side scripting, JavaScript is code inserted into HTML pages or load by page.

What Can JavaScript Do?

In a browser, JavaScript can construct a behavior for a web page. It can manipulate a web page in some manners defined by a programmer. It can add, delete, and change a HTML object (also known as DOM or Document Object Model). It can also change the style of element (button, etc).

JavaScript can also used as a callback. This way, when a specific event occurred, such as a button clicked, a JavaScript code can be executed. For example: when user filling a form and then click a ‘Register’ button, javascript then check the validity all the data.

In some page, a page can communicate asynchronously to server to update specific content without refreshing the page. This is called AJAX, a more advance use of JavaScript. Using this, we can create an interactive web-app.

JavaScript on Other Platform

JavaScript still a script and need an interpreter. However, this day we can see more interpreter aside of browsers. On a desktop, we have NodeJS which is another implementation of JavaScript. NodeJS allows us to write and execute JavaScript like other scripting language (i.e. Python, Ruby, Perl). On some level, JavaScript (subset) is also used to create a interactive application.

All possibility open for JavaScript.

This article will explains some of the more important syntactic and semantic differences between two different assembler style: Intel and AT&T. The AT&T style is used by GNU Assembler (GAS) and the Intel style used by Netwide Assembler (NASM).

Although the goal of this article would be specifically show the differences between syntax, the source codes provided here has been tested on Linux machine using corresponding assembler. This article is written in purpose to help you more easily convert from one flavor of assembler to another.

Building the Program

When there is a source code involved, you can use following command to build the example. Do assembling and linking, depend on your compiler.

Assembling

ELF (Executable and Linkable Format) is executable format used by Linux.

nasm -f elf -o program.o program.asm
as -o program.o program.s
Linking
ld -o program program.o
Linking when an external C library used
ld --dynamic-linker /lib/ld-linux.so.2 -lc -o program program.o

Basic Structure

The structure of a program is at least consists of a section for code, heap, and stack.

; Intel format

; Text segment begins
section .text

   global _start

; Program entry point
   _start:

; codes are written here
# AT&T format

# Text segment begins
.section .text

   .globl _start

# Program entry point
   _start:

# codes are written here

1. Operands Order

One of the noticeable difference between the AT&T and Intel formats is the way they refer to source and destination operands within an instruction. The order of source and destination operand are swapped each other.

Under Intel format, after the instruction come destination followed by a comma and the source operand (the first operand is the destination). Under the AT&T these roles are reversed: the source comes before the comma and the destination (the first operand is source).

; Intel format

PUSH EBP
MOV EBP, ESP
SUB ESP, 48
CMP [EBP+4], 10
# AT&T format

pushl %ebp
movl %esp, %ebp
subl $0X48, %esp

At first glance, AT&T is likely more natural as we read and write from left to right. However, this lead to some flaw and inconsistencies (won’t be discussed here).

The primary reason of AT&T source-operand order is due to the VAX assembly format for which the AT&T was originally invented. The Motorola 68000 and its descendents were heavily influenced by the VAX. Likewise, their assembly language format moves in this direction as well.

2. Naming

2.1 Value & Register Naming

AT&T is quite famous for it’s heavy use of prefixes. In AT&T, registers are prefixed with a ‘%’ and immediate value are prefixed with a ‘$’. Intel in other hand, use plain naming for registers and immediate value.

Intel syntax sure doesn’t use prefix for writing register. However it uses a suffix to distinguish hexadecimal and binary number from decimal. The ‘h’ suffix used for hexadecimal number and the ‘b’ suffix used for binary number. Also, Intel use 0 in front of the hexadecimal number, while AT&T use 0x.

; Intel format

MOV EAX, 1
MOV EBX, 0FFh
INT 80h
# AT&T format

movl $1, %eax
movl $0xFF, %ebx
int $0x80

2.2 Instruction Naming

AT&T format use slightly different names than the Intel format. They differ in keeping with VAX and Motorola traditions where instruction names include a suffix which describes the size of the data they modify. Under Intel format, these data size directives are normally described using the ‘BYTE PTR’, ‘WORD PTR’, ‘DWORD PTR’, prefix phrases.

; Intel format

MOVZX EAX, BYTE PTR [ESI+5]
SUB EAX, 30
DEC WORD PTR [EBX]
INC CX
CMP AL,5
# AT&T format

movzbl 0x5(%esi), %eax
subl $0x30, %eax
decw (%ebx)
incw %cx
cmpb $0x5, %al

Under AT&T format, instruction suffixes are “b” for byte size operations (8-bits), “w” for word size operations (16-bits), “l” for double-word operations (32-bits), and “q” for quad-word operations (64-bits). As you may notice in the ‘movzbl’ (Move with zero-extend) instruction, more than one suffix letter is used when an instruction’s source and destination operand differ in size. The first suffix letter describes the source operand while the second letter describes the destination.

3. Memory Addressing

Under Intel format, memory addressing is simple calculation of address enclosed by ‘[‘ and ‘]’. The AT&T format in other hand use ‘(‘ and ‘)’ to enclose it.

3.1 Indirect Addressing Mode

Recall to x86 assembly language, there are five indirect addressing modes when writing an instruction:

  1. immediate indirect
  2. register indirect
  3. base register + offset indirect
  4. index register * width + offset indirect
  5. and base register + index register * width + offset indirect.
; Intel format

; Immediate
MOV EAX, [0100]

; Register
MOV EAX, [ESI]

; Register + Offset
MOV EAX, [EBP-8]

; Register * Width + Offset
MOV EAX, [EBX*4 + 0100]

; Base + Register*Width + Offset
MOV EAX, [EDX + EBX*4 + 8]
# Intel format

# Immediate
movl 0x0100, %eax

# Register
movl (%esi), %eax

# Register + Offset
movl -8(%ebp), %eax

# Register * Width + Offset
movl 0x100(,%ebx,4), %eax

# Base + Register*Width + Offset
movl 0x8(%edx, %ebx,4), %eax

Under AT&T format, indirect addressing mode are written to the general form of “OFFSET(BASE, INDEX, WIDTH)”. OFFSET, if present, must be a constant integer. BASE and INDEX, if either is present, must be registers. WIDTH, if present, applies to the register named in Index, and must be the constant 1,2, 4, 8. If width is not specified, the default constant 1 is taken.

Under Intel, indirect addressing is as simple as math formula “[BASE + INDEX*WIDTH + OFFSET] using the same terminology as used by AT&T format.

Under AT&T, all immediate addresses are written simply as an OFFSET with a missing BASE, INDEX, and WIDTH parameter. The immediate indirect address is written by itself with no special prefix or suffix characters.

Programming Problem Set: 99 Problems Chapter 5

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Multiway Trees. Multiway tree is composed of a root element and a (possibly) empty set of successors which are multiway trees themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

63. Check whether a given object / term is a multiway tree

The predicate is succeeds if and only if its argument is a representing a multiway tree.

example:
is_tree_mp(t(a,[t(f,[t(g,[])]),t(c,[]),t(b,[t(d,[]),t(e,[])])])) -> true

64. Count the nodes of a multiway tree

Example: nnodes_m_p( t(a,[t(f,[])]),N )
 ->
2
Write another version which allows for a flow pattern

65. Tree construction from a node string

We suppose that the nodes of a multiway tree contain single characters. In the
depth-first order sequence of its nodes, a special character ^ has been inserted
whenever, during the tree traversal, the move is a backtrack to the previous level.

By this rule, the tree in the figure opposite is represented as: <tt>afg^^c^bd^e^^^</tt>

Define the syntax of the string and write a predicate tree(String,Tree) to construct
the Tree when the String is given. Work with atoms (instead of strings). Make your
predicate work in both directions.

66. Determine the internal path length of a tree

We define the internal path length of a multiway tree as the total sum of the path
lengths from the root to all nodes of the tree. By this definition, the tree in the
figure of problem 5.03 has an internal path length of 9

Write a predicate ipl(Tree,IPL) for the flow pattern (+,-).

67. Construct the bottom-up order sequence of the tree nodes

Write a predicate bottom_up(Tree,Seq) which constructs the bottom-up sequence of the
nodes of the multiway tree Tree. Seq should be a Prolog list.

What happens if you run your predicate back words?

68. Lisp-like tree representation

There is a particular notation for multiway trees in Lisp. Lisp is a prominent
functional programming language, which is used primarily for artificial intelligence
problems. As such it is one of the main competitors of Prolog. In Lisp almost
everything is a list, just as in Prolog everything is a term.

The following pictures show how multiway tree structures are represented in Lisp.

Note that in the "lispy" notation a node with successors (children) in the tree is
always the first element in a list, followed by its children. The "lispy"
representation of a multiway tree is a sequence of atoms and parentheses '(' and ')',
which we shall collectively call "tokens". We can represent this sequence of tokens as
a Prolog list; e.g. the lispy expression (a (b c)) could be represented as the Prolog
list ['(', a, '(', b, c, ')', ')']. Write a predicate tree_ltl(T,LTL) which constructs
the "lispy token list" LTL if the tree is given as term T in the usual Prolog notation.

Example:
tree_ltl_p (t(a,[t(b,[]),t(c,[])]),LTL).
-->
['(', a, '(', b, c, ')', ')']

As a second, even more interesting exercise try to rewrite tree_ltl/2 in a way that
the inverse conversion is also possible: Given the list LTL, construct the Prolog
tree T. Use difference lists.

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 4

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Binary Trees. Binary is either empty or it is composed of a root element and two successors, which are binary tree themselves.

The problems in this chapter is a continuation of previous chapter, therefore the numbering will start from the last problem.

For the sake of writing, we will denote tree node as t (value, left, right).

45. Check whether a given object / term is a binary tree

The predicate is succeeds if and only if its argument is a representing a binary tree.

example:
is_tree_p( t(a, t(b, null, null), null) -> true

46. Construct a completely balanced binary trees

In a completely balanced binary tree, the following property holds for every node: The number
of nodes in its left subtree and the number of nodes in its right subtree are almost equal,
which means their difference is not greater than one.

Write cbal_tree/2 to construct completely balanced binary trees for a given number of nodes.
The predicate should generate all solutions via backtracking. Put the letter 'x' as information
into all nodes of the tree.

Example: cbal_tree_p( 4 )
 ->
t(x, t(x, null, null), t(x, null, t(x, null, null)))
t(x, t(x, null, null), t(x, t(x, null, null), null))
...etc

47. Symmetric binary trees

Let us call a binary tree symmetric if you can draw a vertical line through the root node
and then the right subtree is the mirror image of the left subtree. Write symmetric/1 to check
whether a given binary tree is symmetric.

Hint: Write mirror/2 first to check whether one tree is the mirror image of another.
We are only interested in the structure, not in the contents of the nodes. 48. Binary search trees (dictionaries)
Write a predicate to construct a binary search tree from a list of integer numbers.

Example:
construct_p( [3,2,5,7,1] ).
-> t(3, t(2, t(1, nil, nil), nil), t(5, nil, t(7, nil, nil)))

49. Generate and test paradigm

Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees
with a given number of nodes.

Example: sym_cbal_trees_p( 5 )
 ->
[t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil),
 t(x, nil, t(x, nil, nil)))]

How many such trees are there with 57 nodes? Investigate about how many solutions there are for a
given number of nodes. What if the number is even? Write the appropriate solution.

50. Construct height-balanced binary trees

In a height-balanced binary tree, the following property holds for every node:
The height of its left subtree and the height of its right subtree are almost equal, which means their
difference is not greater than one.

Write a predicate hbal_tree/2 to construct height-balanced binary trees for a given height.
The predicate should generate all solutions via backtracking. Put the letter 'x' as information into
all nodes of the tree.

Example: hbal_p( 3 )
 ->
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), t(x, nil, nil)))
t(x, t(x, t(x, nil, nil), t(x, nil, nil)), t(x, t(x, nil, nil), nil))
...etc

51. Construct height-balanced binary trees with a given number of nodes

Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain?
Clearly, MaxN = 2^H - 1. However, what is the minimum number MinN? This question is more difficult.
Try to find a recursive statement and turn it into a predicate minNodes/2 defined as follwos:

minNodes_p( H ) -> the minimum number of nodes in a height -balanced binary tree of height H.

On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes
can have?

maxHeight_p( N ) -> the maximum height of a height balanced binary tree with N nodes

Now, we can attack the main problem: construct all the height-balanced binary trees with a given number
of nodes.

hbal_tree_nodes_p( N ) -> height-balanced binary tree with N nodes.

Find out how many height-balanced trees exist for N = 15

52. Count the leaves of a binary tree

A leaf is a node with no successors.

Example: count_leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
 -> 3

The leaf are [ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

53. Collect the leaves of a binary tree in a list

A leaf is a node with no successors.

Example:
leaves_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
 ->
[ t(c, null, null), t(d, null, null)), t(e, null, null)) ]

54. Collect the internal nodes of a binary tree in a list

An internal node of a binary tree has either one or two non-empty successors.
Example: internals_p( t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
->
[ t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)),
  t(b, t(c, null, null), t(c, null, null)) ]

55. Collect the nodes at a given level in a list

A node of a binary tree is at level N if the path from the root to the node has length N-1.
The root node is at level 1.

Example: atlevel_p( 2, t(a, t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) )
->
[ t(b, t(c, null, null), t(d, null, null)), t(e, null, null)) ]

56. Construct a complete binary tree

A complete binary tree with height H is defined as follows:
The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i,
note that we start counting the levels from 1 at the root). In level H, which may contain less
than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a
levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors
(the nil's which are not really nodes!) come last.

Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.

We can assign an address number to each node in a complete binary tree by enumerating the nodes in
levelorder, starting at the root with number 1. In doing so, we realize that for every node X with
address A the following property holds: The address of X's left and right successors are 2*A and 2*A+1,
respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete
binary tree structure. Write a predicate complete_binary_tree/2 with the following specification:

Example: complete_binary_tree_p( 3 ) -> The complete binary tre with N nodes

57. Layout a binary tree

Given a binary tree as the usual Prolog term t(X,L,R) (or nil). As a preparation for drawing the tree,
a layout algorithm is required to determine the position of each node in a rectangular grid.
Several layout methods are conceivable, one of them is shown in the illustration above.
In this layout strategy, the position of a node v is obtained by the following two rules:
(1) x(v) is equal to the position of the node v in the inorder
(2) y(v) is equal to the depth of the node v in the tree sequence

58. Layout a binary tree (2)

Figure located above

An alternative layout method is depicted in the above illustration. Find out the rules and write
the corresponding solution.
Hint: On a given level, the horizontal distance between neighboring nodes is constant.

Use the same conventions as in problem 57.

59. Layout a binary tree (3)

Figure located above

Yet another layout strategy is shown in the above illustration. The method yields a very compact
layout while maintaining a certain symmetry in every node. Find out the rules and write the
solution.
Hint: Consider the horizontal distance between a node and its successor nodes.
How tight can you pack together two subtrees to construct the combined binary tree?

Use the same conventions as in problem 57 and 58 and test your predicate in an appropriate way.
Note: This is a difficult problem. Don't give up too early!

Which layout do you like most?

60. A string representation of binary trees

Somebody represents binary trees as strings of the following type (see example):

a(b(d,e),c(,f(g,)))

(a) Write a solution which generates this string representation, if the tree is given as
usual (as nil or t(X,L,R) term). Then write a predicate which does this inverse;
i.e. given the string representation, construct the tree in the usual form.
Finally, combine the two predicates in a single predicate tree_string/2 which can be used in
both directions.

(b) Write the same predicate tree_string/2 using difference lists and a single predicate
tree_dlist/2 which does the conversion between a tree and a difference list in both directions.

For simplicity, suppose the information in the nodes is a single letter and there are no
spaces in the string.

61. Preorder and inorder sequence of binary trees

We consider binary trees with nodes that are identified by single lower-case letters, as in the
example of problem 60.

(a) Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a
given binary tree, respectively. The results should be atoms, e.g. 'abdecfg' for the preorder sequence
of the example in problem 4.16.

(b) Can you use preorder/2 from problem part a) in the reverse direction;
i.e. given a preorder sequence, construct a corresponding tree? If not, make the necessary arrangements.

(c) If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given,
then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.

(d) Solve problems (a) to (c) using difference lists.

What happens if the same character appears in more than one node. Try for instance pre_in_tree(aba,baa,T).

62. Dotstring representation of binary trees

We consider again binary trees with nodes that are identified by single lower-case letters, as in
the example of problem 60. Such a tree can be represented by the preorder sequence of its nodes in
which dots (.) are inserted where an empty subtree (null) is encountered during the tree traversal.
For example, the tree shown in problem 60 is represented as <tt>'abd..e..c.fg...'</tt>.
First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2
which does the conversion in both directions. Use difference lists.

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 3

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Logic and Codes. The problems in this chapter served as continuation of previous problems, therefore the numbering will start from the last problem.

40. Truth tables for logical expression

Define and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which
succeed or fail according to the result of their respective operations;
e.g. and(A,B) will succeed, if and only if both A and B succeed.

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

Example: table_p( A, B, xor(A,B) )
->
true true false
true false true
false true true
false false false

41. Truth tables for logical expressions (2)

Continue problem 40 by defining and/2, or/2, etc as being operators. This allows to write the
logical expression in the more natural way, as in the example: A and (A or not B).
Define operator precedence as usual; i.e. as in C.

Example: table2_p( A, B, A and (A or not B) )
 ->
true true true
true false true
false true false
false false false

41. Truth tables for logical expressions (2)

Generalize problem 41 in such a way that the logical expression may contain any number
of logical variables. Define table/2 in a way that table(List,Expr) prints the truth table
for the expression Expr, which contains the logical variables enumerated in List.

The index is started from 1.

Example: table3_p( [A,B,C], A and (B or C) equ A and B or A and C)
 ->
<tt>true true true true
true true false true
true false true true
true fail false true
false true true true
false true false true
false false true true
false false false true

43. Gray code

An n-bit Gray code is a sequence of n-bit strings constructed according to
certain rules. For example,

n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010','110','111','101','100'].

Find out the construction rules and write a predicate with the following specification:

% gray(N,C) :- C is the N-bit Gray code

Can you apply the method of "result caching" in order to make the predicate more
efficient, when it is to be used repeatedly?

44. Huffman code

First of all, study a good book on discrete mathematics or algorithms for a detailed
description of Huffman codes, or consult wikipedia

We suppose a set of symbols with their frequencies, given as a list of fr(S,F) terms.
Example: [fr(a,45),fr(b,13),fr(c,12),fr(d,16),fr(e,9),fr(f,5)]. Our objective is to
construct a list hc(S,C) terms, where C is the Huffman code word for the symbol S.
In our example, the result could be Hs = [hc(a,'0'), hc(b,'101'), hc(c,'100'), hc(d,'111'),
hc(e,'1101'), hc(f,'1100')] [hc(a,'01'),...etc.].

Example: huffman_p(Fs,Hs)
-> Hs is the Huffman code table for the frequency table Fs

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 2

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Arithmetic. A list is either empty or it is composed of a first element (head) and a tail, which is a list itself. As a continuation from previous chapter, the problem will be started from last previous number.

29. Determine whether a given integer number is prime.

Example: is_prime_p( 7 ) -> Yes

30. Determine the prime factors of a given positive integer.

Construct a list containing the prime factors in ascending order

Example: prime_factor_p( 315 ) -> [ 3, 3, 5, 7 ]

31. DetermineĀ  the prime factors of a given positive integer (2)

Construct a list containing the prime factors and their multiplicity.

Example: prime_factor2_p( 315 ) -> [ [3,2], [5,1], [7,1] ]

Hint: The solution of problem 10 may be helpful.

32. A list of prime number

Given a range of integers by its lower and upper limit, construct
a list of all prime numbers in that range.

Example: prime_list_p( 3, 15 ) -> [3, 5, 7, 11, 13 ]

33. Goldbach’s conjecture

Goldbach's conjecture says that every positive even number greater
than 2 is the sum of two prime numbers. Example: 28 = 5 + 23.
It is one of the most famous facts in number theory that has not
been proved to be correct in the general case. It has been numerically
confirmed up to very large numbers.
Find the two prime numbers that sum up to a given even integer

Example: goldbach_p( 28 ) -> [ 5, 23]

34. A list of Goldbach compositions

Given a range of integers by its lower and upper limit, print a
list of all even numbers and their Goldbach composition

Example: goldbach_list_p( 9, 20 )
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17

In most case, if an even number is written as the sum of two prime
numbers, one of them is very small. Very rarely, the primes are
both bigger than say 50. Try to find out how many such cases
there are in the range 2..3000.

35. Determine the greatest common divisor of two positive integer number

Use Euclid's algorithm

Example: gcd_p( 36, 63 ) -> 9

36. Determine whether two positive integer numbers are coprime

Two numbers are coprime if their greates common divisor equals 1

Example: coprime_p( 35, 64 ) -> Yes

37. Calculate Euler’s totient function phi(m)

Euler's so-called totient phi(m) is defined as the number of pisitive
integers r (1 <= r < m) that are coprime to m.
If m = 10 then r = 1, 3, 7, 9; thus phi(m) = 4. Note the special case
phi(1) = 1

Example: phi_p( 10 ) -> 4

38. Calculate Euler’s totient function phi(m) (2)

See the previous problem for definition of Euler's totient function.
If the list of the prime factors of a number m is known in the form
of problem 32 then the function phi(m) can be efficiently calculated
as follows:

Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors
(and their multiplicities) of a given number m. Then phi(m) can be
calculated with following formula:

phi(m) = (p1-1)* p1^(m1-1) *(p2-1)* p2^(m2-1)*(p3-1)* p3^(m3-1)

Note that a^b stands for the b'th power of a.

39. Compare the two methods of calculating Euler’s totient function.

Use the solution of problem 37 and 38 to compare algorithm. Take
the number of logical inferences as a measure for efficiency. Try to
calculate phi(10090) as an example

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

Programming Problem Set: 99 Problems Chapter 1

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about Lists. A list is either empty or it is composed of a first element (head) and a tail, which is a list itself.

01. Find the last element of a list

Example: last_p( [a, b, c, d] ) -> d

02. Find the last but one element of a list

Example: last_one_p( [a, b, c, d] ) -> c

03. Find the n’th element of a list

The index is started from 1.

Example: at_p( [a, b, c, d], 3) -> c

04. Find the number of elements of a list

Example: length_p( [a, b, c, d] ) -> 4

05. Reverse a list

Example: reverse_p( [a, b, c, d] ) -> [d, c, b, a]

06. Find out whether a list is a palindrome

A palindrome ca be read forward of backward.

Example: palindrom_p( [a, b, c, b, a] ) -> true

07. Flatten a nested list structure

Transform a lists as elements into a 'flat'
list by replacing each list with its element (recursively)

Example: flatten_p( [a, [b, [c, d], e]] ) -> [a, b, c, d, e]

08. Eliminate consecutive duplicates of list elements

If a list contains repeated elements they should be replaced
with a single copy of the element. The order of elements
should not be changed.

Example: compress_p( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ) -> [a, b, c, a, d, e]

09. Pack consecutive duplicates of list elements into sublists

If a list contains repeated elements, they should be placed
in separate sublist.

Example: pack_p( [a, a, a, a, b, c, c, a, a, d, e, e, e, e])
 -> [ [a, a, a, a], [b], [c, c], [a, a], [d], [e, e, e, e,] ]

10. Run-length encoding of a list

Consecutive duplicates of elements are encoded as terms [N, E]
where N is the number of duplicates of the element E.

Example: encode_p1( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] )
 -> [ [4,a], [1,b], [2,c], [2,a], [1,d], [4,e]]

11. Modified run-length encoding

Consecutive duplicates of elements are encoded as terms [N, E]
where N is the number of duplicates of the element E. If an
element has no duplicates, it is simply copied into the result
list Only duplicates are transferred as [N, E] terms.

Example: encode_p2( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] )
 -> [ [4,a], b, [2,c], [2,a], d, [4,e] ]

12. Decode a run-length encoding list

Given a run-length code list generated, construct its uncompressed
version.

Example: encode_p3( [4,a], [1,b], [2,c], [2,a], [1,d], [4,e])
 -> [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ]

13. Run-length encoding of a list (direct solution)

Implement the so-called run-length encoding data compression method
directly. Don't explicitly create the sublists containing the
duplicates but only count them. Simplify the result list by
replacing the singleton terms [1,X] by X.

Example: encode_p4([a, a, a, a, b, c, c, a, a, d, e, e, e, e])
 -> [ [4,a], b, [2,c], [2,a], d, [4,e]]

14. Duplicate the elements of a list

Example: duplicate_p([a, b, c, d, e]) -> [a, a, b, b, c, c, d, d, e, e]

15. Duplicate the elements of a list a given number of times.

Example: duplicate_px([a, b, c, d, e], 3)
 -> [a, a, a, b, b, b], c, c, c, d, d, d, e, e, e]

16. Drop everh N’th element from a list

Example: drop_p([a, b, c, d, e, f, g, h, i, k], 3)
 -> [a, b, d, e, g, h, k]

17. Split a list into two parts; the length of the first part is given

Do not use any predefined predicates / function.

Example: split_p([a, b, c, d, e, f, g, h, i, k], 3, L1, L2)
 -> L1 = [a, b, c] ; L2 = [d, e, f, g, h, i, k]

18. Extract a slice from a list

Given two indices, I and K, the slice is the list containing the
elements between the I'th and K'th element of the original list
(both limits included). Start counting the element with 1.

Example: slice_p([a, b, c, d, e, f, g, h, i, k], 3, 7) -> [c, d, e, f, g]

19. Rotate a list N places to the left

Example:
rotate_p([a, b, c, d, e, f, g, h], 3) -> [d, e, f, g, h, a, b, c]
rotate_p([a, b, c, d, e, f, g, h],-2) -> [g, h, a, b, c, d, e, f]

20. Remove the K’th element from a list

Example: remove_p([a, b, c, d], 2) -> [a, c, d]

21. Insert an element at a given position into a list

Example: insert_p(x, [a, b, c, d], 2) -> [a, x, b, c, d]

22. Create a list containing all integers withing a given range.

Example: range_p(4, 9) -> [4, 5, 6, 7, 8, 9]

23. Extract a given number of randomly selected elements from a list.

The selected items shall be put into a result list.

Example: rnd_select_p1([a, b, c, d, e, f, g, h], 3) -> [g, a, c]

24. Draw N different random numbers from the set 1..M.

The selected numbers shall be put into a result list.

Example: rnd_select_p2(6, 49) -> [23, 1, 33, 21, 37, 17]

25. Generate a random permutation of the elemnts of a list.

Example: rnd_permut_p([a, b, c, d, e]) -> [b, a, d, c, e, f]

26. Generate the combinations of K distinct objects chosen from the N elements of a list.

In how many ways can a committee of 3 be chosen from a group of
12 people? There are C(12,3) = 220 possibilities denotes the
well-known binomial coefficients.

Example: combination_p([a, b, c, d, e, f])
[a, b, c]
[a, b, d]
[a, b, e]
...

27. Group the elements of a set into disjoint subsets.

(a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3, and 4 persons?
Example: group3_p([aldo,beat, carla, david, evi, flip, gary, hugo, ida])

G1 = [aldo, beat], G2 = [carla, david, evi], G3 = [flip, gary, hugo, ida]


(b) Generalize the above function in a way that we can specify a list of group sizes and the 
predicate will return a list of groups

Example: group_p([aldo, beat, arla, david, evi, flip, gary, hugo, ida],[2, 2, 5])
 -> [[aldo,beat],[carla,david],[evi,flip,gary,hugo, ida]]
[/sourcecode]

28. Sorting a list of lists according to length of sublists

(a) Suppose that a list (InList) contains elements that are lists themselves.
 The objective is to sort the elements of InList according to their length.
 E.g. short lists first, longer lists later, or vice versa.


Example: lsort_p([[a, b, c], [d,e],[f,g,h], [d,e], [i,j,k,l], [m,n],[o]])
 -> [[o],[d, e],[d, e],[m, n],[a, b, c],[f, g, h],[i, j, k, l]]




(b) Suppose a list (InList) contains elements that are list themselves.
 But this time the objective is to sort the elements of InList according to
 their length frequency. i.e. in the default, where sorting is done ascendingly,
 lists with rare lengths are placed first, others with a more frequent length
 come later.

Example: lfsort_p([[a, b, c], [d,e],[f,g,h], [d,e], [i,j,k,l], [m,n],[o]])
 -> [[i, j, k, l],[o],[a, b, c],[f, g, h],[d, e],[d, e],[m, n]]

Note that in the above example, the first two list in the result have length
4 and 1, both lengths appear just one. The third and forth list have length
3, there are two list of this length. And finally the last three lists have
length 2. This is the most frequent length
[/sourcecode]

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

In more complex situation, there is a need for application to run a certain codes in regards of situation. Thus we need to analyze what condition to execute what codes. It is called condition analysis, but widely known as branching. Condition analysis or branching is no more than selecting statement which will be executed. The selection is based on some conditions – represented by one or more boolean expression – applied.

C++ has two type structure to implement branching: if structure and switch structure.

Statements inside of branching block will be executed only if the condition is satisfied / fulfilled. Which in turn, if condition is not achieved, then the statements / codes won’t be executed.

Let’s see a case in real world. Note this sentence:

If Andy passed the exam then Andy will get a prize

This simple sentence tells us what will happen to Andy. As demonstrated here we know that Andy will get prize if he pass the exam. Otherwise, he won’t. The action defined here is Andy will get a prize. But to do the action, there is a condition, which is Andy must pass the exam.

In programming world, similar case applied, of course in some notion. Programming world use a formalized form in which we will discuss in this article.

If Structure

The first structure we will discuss is IF. This structure is the simplest of all things. Let’s see following snippet:

// If there are more than 1 statement
if (condition) {
   statement1;
   statement2;
}

// If there is only 1 statement
if (condition) statement;

There is the simplest structure we have, if with only one condition analysis. Yes, the statement(s) will be execute if the condition is satisfied. Let’s see how we can use in the actual program.

#include <iostream>
using namespace std;

int main() {
   int number;

   // Input an integer number from user
   cout << "Please input number: " ;
   cin >> number;

   if (number > 10)
      cout << "You give me " << number << ", it's more than 10 :D" << endl;

   return 0;
}

As you can see, the condition is consist of comparison operations. In general, condition can be formed by one or more comparison expression merged by logical operation such as: && (and), || (or). This we call as complex condition structure. Let’s see this example:

#include <iostream>
using namespace std;

int main() {
char c;

// Input a character from user
cout << "Please input a character: " ;
cin >> c;

if ( (c == 'A') || (c == 'a') ||
(c == 'I') || (c == 'i') ||
(c == 'U') || (c == 'u') ||
(c == 'E') || (c == 'e') ||
(c == 'O') || (c == 'o'))
cout << "You give me a vowel" << endl;

return 0;
}

With a simple analysis, we can see that the statement cout << “You give me a vowel” << endl can be can be executed if one of those multiple condition is satisfied (you can see why).

One or more condition can be made to this structure. In fact, it is easy to write. For a starter, let see how we can analyze two condition:

if (condition) {
   statement_if_condition_is_satisfied
} else {
   statement_if_condition_is_not_satisfied
}

There we have two situation: a situation if condition is satisfied, and situation where condition is not satisfied. If the application failed to satisfied the condition, the execution will fall to block following else word. In here we will see how we the usage in the real world programming:

#include <iostream>
using namespace std;

int main() {
   int number;

// Input an integer number from user
   cout << "Please input a number: " ;
   cin >> number;

   if ( number % 2 == 0 ) {
      cout << "You give me an even number" << endl;
   } else {
      cout << "You give me an odd number" << endl;
   }

   return 0;
}

There we analyze whether the given number is an even or an odd number. Wee that a number which is not an even number must be an odd number, so we just applied one condition to check and if the condition is not satisfied it will fall to the else block of statement.

Now how if we want to inspect more than that? Simple, we could write something like this:

if (condition-1) {
   statement_if_condition_1_satisfied
} else if (condition-2) {
   statement_if_condition_2_satisfied
} else if (condition-3) {
   statement_if_condition_3_satisfied
} ...

} else {
   statement_if_no_condition_is_satisfied
}

Yes, we can use else if to analyze other condition that might happen.

Switch Structure

Aside from if structure, C++ offer us another condition analysis structure, switch.

Switch is like an actual switch. Imagine there is an electronic switch which connecting two endpoint. There are two condition for this switch at a time: on or off. On an observation, we could see that if the switch is on, the two endpoint will be connected. Otherwise the two endpoint is disconnected. Therefore we can see there are two different action: connected and disconnect, which is drived by two different condition: on or off.

Similar to that, switch need a variable in which will be observed. Switch then compare the value to the list of value might equal to it.

If we transform the analogy to a C++ snippet, we will get something like this:

switch ( electronic_switch) {
case on:
   connected;
   break;

case off:
   disconnected;
   break;

default:
}

As we can see, the variable electronic_switch is being inspected and then it will be compared to two value: on and off. Once it is matched, it will begin to execute whatever code later. Therefore, we must set a stop / break point. This break statement then stop the execution and then finishing the switch statement.

Oh, and don’t forget that the value compared using case keyword must be a constant. You can’t compare the value which is being inspected to a variable.

What if we forgot to give break there? Switch will continue executing codes until it found break or until it reach end of switch statement. Be careful!

Now let see the actual use:

#include <iostream>
using namespace std;

int main() {
   int number;

   cout << "Input a number (1..7): ";
   cin >> number;

   switch(number) {
      case 1: cout << "You give me one" << endl; break;
      case 2: cout << "You give me two" << endl; break;
      case 3: cout << "You give me three" << endl; break;
      case 4: cout << "You give me four" << endl; break;
      case 5: cout << "You give me five" << endl; break;
      case 6: cout << "You give me six" << endl; break;
      case 7: cout << "You give me seven" << endl; break;
   }

   return 0;
}

Nested Condition Analysis

Now suppose we want to analyze something after some condition is satisfied. This common situation is called as nested branching / nested condition analysis. You can use if of switch inside of another if or switch structure.

How to do it? Well, I will let you figure it out šŸ˜›

Perfect Forwarding in C++11

December 5, 2015 | Article | No Comments

C++11 offers a great new features called Perfect Forwarding, which is enabled via the use of rvalue references.

Perfect forwarding allows a function template to pass its arguments through to another function while retaining the original lvalue / rvalue nature of the function arguments. It avoids unnecessary copying and avoids the programmer having to write multiple overloads for different combinations of lvalue and rvalue references. A class can use perfect forwarding with variadic templates to “export” all possible constructors of a member object at the parent’s level.

class Blob
{
  std::vector<std::string> _v;
public:
  template<typename... Args>
  Blob(Args&&... args)
   : _v(std::forward<Args>(args)...)
  {  }
};
int main(void)
{
  const char * shapes[3] = { "Circle", "Triangle", "Square" };
  Blob b1(5, "C++ Truths");
  Blob b2(shapes, shapes+3);
}

The Blob class above contains a std::vector, which has many different constructors. Using a perfect forwarding constructor, the Blob class allows its clients to pass variable number of parameters that different constructors of std::vector would use. For example, object b1 uses std::vector’s constructor that takes a count and an initial value where as object b2 uses the constructor that takes an iterator pair. Also note that std::forward allows us to perfect-forward the parameters.

If you look carefully, actually this example does not require perfect forwarding as Blob constructor could take a std::vector by value and move it into the member vector object. Well, suppose we don’t know.

In practice, however, we would encounter classes that would have several members. Naturally, we may want to “export” their different constructors at its parent’s level. This is particularly true if object construction is heavy and does not support efficient move. The motivation behind this is no different than that of the emplace operations on containers. Just like the standard emplace operations, our perfect forwarding constructor allows us to construct an object in-place. We don’t even pay the cost of a move (which is often negligible for types such as std::vector). An interesting problem arises when we want to perfect forward arguments to more than one constructor. How do we decide which parameters are for which object?

Let see example below. The following Blob class has a vector of strings and a list of doubles. How do we group the parameters to the respective constructors? How do we know the programmer’s intent?

class Blob
{
  std::vector<std::string> _v;
  std::list<double> _l;
public:
  template<typename... Args>
  Blob(Args&&... args)
   : _v(???)
     _l(???)
  {  }
};
int main(void)
{
   Blob b3(5, 10, 10.0); // Three parameters and two constructors. How do we group?
}

Fortunately there is a way out and a very interesting one.

First of all, we’ve to group the parameters. An obvious candidate comes to mind: std::tuple! We could ask programmers to group the parameters in a sequence of tuples and each parameter grouped in the tuples are passed to the respective constructors.

Blob b3(std::make_tuple(5), std::make_tuple(10, 99.99));
The intent of the programmer is pretty clear in the above groupings. The vector will have 5 empty strings and the list will have 10 doubles each initialized to value = 99.99. However, we’ve a new problem now. std::vector and std::list do not accept std::tuple as parameters. We’ve to ungroup them before calling their constructors. This is far from trivial but it also makes the whole thing very interesting.

Note that retrieving values from a std::tuple requires calling std::get<i> where i is a compile-time constant that varies from 0 to the tuple_length-1. Somehow, we’ve to call std::get on each tuple with increasing values of i. To do that, we’ve to create a compile-time list of tuple indices. Here is a way to do it.

template<unsigned...> struct index_tuple{};
template<unsigned I, typename IndexTuple, typename... Types>
struct make_indices_impl;
template<unsigned I, unsigned... Indices, typename T, typename... Types>
struct make_indices_impl<I, index_tuple<Indices...>, T, Types...>
{
  typedef typename
    make_indices_impl<I + 1,
                      index_tuple<Indices..., I>,
                      Types...>::type type;
};
template<unsigned I, unsigned... Indices>
struct make_indices_impl<I, index_tuple<Indices...> >
{
  typedef index_tuple<Indices...> type;
};
template<typename... Types>
struct make_indices
  : make_indices_impl<0, index_tuple<>, Types...>
{};

make_indices is a collection of recursive meta-fuctions that compute a list of indices given a tuple type. For example, if you have (42, true, 1.2), which is tuple<int, bool, double>, make_indices<int,bool,double>::type gives index_tuple<0, 1, 2>. Here is how to use make_indices in a simple program.

template <unsigned... Indices, class... Args, class Ret>
Ret forward_impl(index_tuple<Indices...>,
                 std::tuple<Args...> tuple,
                 Ret (*fptr) (Args...))
{
  return fptr(std::get<Indices>(tuple)...);
}
template<class... Args, class Ret>
Ret forward(std::tuple<Args...> tuple, Ret (*fptr) (Args...))
{
   typedef typename make_indices<Args...>::type Indices;
   return forward_impl(Indices(), tuple, fptr);
}
int myfunc(int i, bool, double)
{
  return 5 + i;
}
int main()
{
  std::cout << forward(std::make_tuple(42, true, 1.2), myfunc) << std::endl;
}

Line #6 above is the place where the actual function is called where the list of indices and the tuple come together and two parameter packs are expanded in lockstep to yield the complete list of parameters. Note that we’re not using perfect forwarding in this case. Moreover, tuple is also copied by value. That’s fine for scalar builtin types like int, bool, and double. For large types, however, unnecessary copies may be created. The above program is simplified for the purpose of illustration.

Back to class Blob

The make_indices utility is pretty clever. But we’re not done yet. We’ve to achieve the same effect while calling the member constructors from the initialization list. We’ve to compute two lists of indices (one for vector and one for list) and expand them with the respective tuples. The question is how do we compute the list of indices before calling member constructors?

Delegated constructors come to rescue!

class Blob
{
  std::vector<std::string> _v;
  std::list<double> _l;
public:
  template <typename... Args1,
            typename... Args2>
  Blob(std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2)
  : Blob(tuple1,
         tuple2,
         typename make_indices<Args1...>::type(),
         typename make_indices<Args2...>::type())
  {}
private:
  template <typename... Args1,
            typename... Args2,
            unsigned... Indices1,
            unsigned... Indices2>
  Blob(std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2,
       index_tuple<Indices1...>,
       index_tuple<Indices2...>)
    : _v(std::forward<Args1>(std::get<Indices1>(tuple1))...),
      _l(std::forward<Args2>(std::get<Indices2>(tuple2))...)
  { }
};

The new Blob class has a public constructor that delegates to a private constructor that expects not only the tuples but also the list of indices. The private constructor is not only templatized on the tuple arguments but also on the list of indices. Once we’ve the tuples and lists of indices together, passing them to the member constructors is pretty straight forward. We simply expand the two variadic lists in unison.

Astute readers will likely notice that the Blob class is no longer using perfect forwarding because it accepts two tuples by value as opposed to an argument list in a perfect forwarding fashion shown at the beginning. That’s is on purpose. And it is not any less efficient either! Even for large types! How’s that possible?

Well, who says copying a tuple by value means copying its original parameters by value? C++ standard library provides a very convenient helper called forward_as_tuple, which perfect-forwards its parameters types as tuple members. It constructs a tuple object with rvalue references to the elements in arguments suitable to be forwarded as argument to a function. That is, the tuple member types are T&& and copying references is blazing fast. So we can afford to pass the tuples by value. Alternatively, we could use rvalue references to the tuples because in this case they are always (!) created by calling std::forward_as_tuple, which returns a temporary tuple. Here is how we use our final Blob class.

int main(void)
{
  Blob b3(std::forward_as_tuple(5, "C++ Truths"),
          std::forward_as_tuple(10, 99.99));
  // b3._v has 5 strings initialized to "C++ Truths" and
  // b3._l has 10 doubles initialized to 99.99
  Blob b4(std::forward_as_tuple(5),
          std::forward_as_tuple(10, 99.99));
  // b4._v has 5 empty strings and
  // b4._l has 10 doubles initialized to 99.99
  Blob b5(std::forward_as_tuple(),
          std::forward_as_tuple(10, 99.99));
  // b5._v is an empty vector
  // b5._l has 10 doubles initialized to 99.99
}

Using std::piecewise_construct

The Blob class looks fine and dandy so far. But the use of forward_as_tuple looks somewhat weird and does not say what it is for: in-place construction of a Blob object from its pieces. So in the final installment of the Blob class, we say what we mean. We just decorate the class with a standard (!) dummy class called std::piecewise_construct_t. The public constructor of the Blob is modified like below. We use std::piecewise_construct, a predefined object of std::piecewise_construct_t, at the call site where we create Blob objects.

#include <utility>
// ...
  template <typename... Args1,
            typename... Args2>
  Blob(std::piecewise_construct_t,
       std::tuple<Args1...> tuple1,
       std::tuple<Args2...> tuple2)
  : Blob(tuple1,
         tuple2,
         typename make_indices<Args1...>::type(),
         typename make_indices<Args2...>::type())
  {}
//...
Blob b3(std::piecewise_construct,
        std::forward_as_tuple(5, "C++ Truths"),
        std::forward_as_tuple(10, 99.99));

Obviously, the C++ library working group anticipated such situations. But are there use cases in the standard library that require the piecewise_construct idiom? As it turns out, the std::map and std::unordered_map face a very similar issue while using emplace operations. Note that std::map and std::underorder_map use a std::pair as their value_type. The pair’s .first and .second members must be constructed from a list of perfectly forwarded parameters. Obviously, the question arises what parameters go where. To solve this issue, the parameters of each member’s constructor must be wrapped as a tuple and indicate so using std::piecewise_construct so that the right pair constructor can be invoked.

C++11 New Feature: Variadic Template

December 5, 2015 | Article | 1 Comment

Before the possibilities of the new C++ language standard, C++11, the use of templates was quite limited when it campe to implementing for instance function objects (functors) & tuple facilities. Implementing these sort of things using earlier C++ standard often require similar codes to be repeated various times without forgetting preprocessor metaprogramming. However, using variadic templates, new features of C++11, make programming using templates easier, cleaner, & more memory-efficient.

In this article we will discuss about Variadic Template on C++11. I assume that you have understood what class & function templates are and how to declare, define, and use them.

What is Variadic Template?

Variadic template is a template, which can take an arbitrary number of template arguments of any type. Both the classes & funcitons can be variadic. Example can be seen below:

template<typename... Arguments>
class VariadicTemplate;

Any of the following ways to create an instance of this class template is valid:

VariadicTemplate<double, float> instance;
class VariadicTemplate;
VariadicTemplate<bool, unsigned short int, long> instance;
VariadicTemplate<char, std::vector<int>, std::string, std::string, std::vector<long long>> instance;

The number of variadic template arguments can also be zero, which mean that following also valid

VariadicTemplate<> instance;

However, a template like this:

template<typename T, typename... Argument>
class VariadicTemplate;

Must be supplied by at least one type as a template argument (which is for typename T), unless default type has been initialized, like in in the following declaration:

template<typename T = int, typename... Argument>
class VariadicTemplate;

Ellipsis Operator

Ellipsis operator (…) is an operator used in different context in C++. It;s name comes from an ellipsis mechanism in C. In this mechanism programmer can create a funciton taking variable number of parameters. Probably the most famous function in both C & C++ to take advantace of this mechanism is printf and scanf function from C standard library.

printf(const char* format, ...);
scanf(const char* format, ...);

Ellipsis mechanism can also be used with preprocessor in a form of a macro. A macro take a variable number of parameters is called a variadic macro.

#define VARIADIC_MACRO(...)

In C++, the ellipsis operator got a new meaning in different context called exception handling. The operator is used in catch blocks after try blocks which can be seen as following:

try {
   // try block
} catch (...) {
   // catch block
}

Which “catch” any exception thrown by try block and then executes the code on catch block. Thus any exception regardless of types will be taken as if parameter of function.

Later on C++11, variadic templates has brought yet another meaning for this operator. The operator works somewhat like in ellipsis mechanism with more complex. As seen at this snippet:

template<typename... Arguments>
void SampleFunction(Arguments... parameters);

The content of the variadic template arguments are called parameter packs. These packs will then be unpacked inside of function parameters. For example:Ā  If we create a function call to previous variadic template

SampleFunction<int, int>(16,24);

then an equivalent template would be:

template<typename T, typename U>
void SampleFunction(T param1, U param2);

“Sizeof…” Operator

Another operator used with variadic templates is the sizeof… operator (yes it is sizeof followed by three dot). Unlike sizeof operator which can determine the size of a type such as sizeof(int) or sizeof(double), sizeof… operator can be used to determine the amount of types given into a variadic template. A snippet below will demonstrate:

template<typename... Arguments>
class VariadicTemplate {
  static const unsigned short int size = sizeof...(Arguments);
}
void SampleFunction(T param1, U param2);

Two Ellipsis together? (……)

In some circumtances, there can be two ellipsis operators put together (……) and yes there are six dot there which also can be separated (written as … …) Probably the most clear way, however, is to separate those two operators witha comma (such as …,…) is still acceptable.

This kind of syntax can appear with variadic function templates using ellipsis mechanism:

template<typename... Arguments>
void SampleFunction(Arguments..., ...);

Inheritance and Initialization List

When it comes to classes, variadic templates can be used with inheritance & initialization lists. Inheritance taking advantage of variadic templates can be accomplished like this:

template<typename... BaseClasses>
class VariadicTemplate : public BaseClasses...

And if we want to create a constructor inside this class using initialization list to call the constructor of all the given base classes as template arguments, we would have to do it this way:

template<typename... BaseClasses>
class VariadicTemplate : public BaseClasses... {
  VariadicTemplate(BaseClasses&&... base_classes) : BaseClasses(base_classes)... {

  }
};

Variadic Class Template Specialization

Like class templates, variadic class templates can also be specialized. With template, the specialization happens like this:

template<typename T>
class Template {
public:
  void SampleFunction(T param) {

  }
};
template<>
class Template<int> {
public:
  void SampleFunction(int param) {

  }
};

But with variadic templates it become like this:

template<typename... Arguments>
  class VariadicTemplate {
public:
  void SampleFunction(Arguments... param) {

  }
};

template<>
  class VariadicTemplate<double, int, long> {
public:
  void SampleFunction(double param1, int param2, long param3) {

  }
};

Conclusion

Templates have been a powerful feature in C++. Now, after the introduction of variadic template, templates have proven themselves even more powerful. Variadic templates are a trusworthy solution to implement delegates and tuples. And, instead of C-style ellipsis mechanism, variadic templates can offer a typesafer solution to replace them.

Social media & sharing icons powered by UltimatelySocial