About Programming

Introduction to Concepts of Programming Languages

The follows is an introduction to the concepts of Programming Languages. Some of these concepts are the style of language, the identification of typical error when programming, etc.Lets begin by identifying different styles of programming languages.

Programming languages normally are divided in two categories:

The first category are languages that behave in a declarative way which means we tell the  computer what it is going to do.

Declarative language example: In Prolog, we provide a group of facts and rules, its up to the programming language to figure out the answer:

is_mother_of(maria, pedro). /* Maria is_mother_of Pedro */
is_mother_of(maria, lucia)./* Maria is_mother_of Lucia */

is_father_of(diego, pedro). /* Diego is_father_of Pedro */
is_father_of(manuel, lucia). /* Manuel is_father_of Lucia */

/* Person is_parent_of Child if Person is_mother_of Child */
is_parent_of(Person, Child):- is_mother_of(Person, Child).
is_parent_of(Person, Child):- is_father_of(Person, Child).

In this case, we have that a mother, Maria, who is mother of two children, Pedro and Lucia; however, both children have different fathers. Diego is father of Pedro while Manuel is father of Lucia.

Prolog is going to search for the answer for us base on there facts and rules. If we wish for more answers, it will search for the next one. We can keep asking Prolog to keep searching until there are no more answers to be found.

/* Prolog give us an answer */
?- is_parent_of(Maria, Child).
Maria = maria,
Child = pedro.


/* After Prolog give us an answer, we can ask Prolog to search for another answer using ';' */
?- is_parent_of(Maria, Child).
Maria = maria,
Child = pedro ;
Maria = maria,
Child = lucia. 


In the declarative languages, there exist subcategories of programming  languages such as functional languages, dataflow languages, logic  languages (also known as constraint-based languages), and template based languages.


Functional languages examples: Haskell, Lisp (Scheme), MI.


This languages are based on the use of recursive definitions of functions.


Dataflow languages examples: Val, Id.


These languages are defined as tokens (known as nodes) that are used for the flow of information. This kind of language let the user to work on  an inherently parallel model.


Logic (constraint-based) languages examples: Prolog, spreadsheets (such as Excel).


This kind of languages are designed so the programmer provide relationships and rules in such a way that the computer try to find the values that will satisfy them.


Template based languages example: XSLT.


The second category are imperative languages in which we tell the computer how to find the answer.


Imperative language example: In C, we must tell the language how to solve the problem.


/* This code tell the computer how to do the power of a number */
int PowerI(int pow, int number){
    int accumulator, counter;
    for (accumulator = 1, counter = 0; counter < pow; ++counter){
        accumulator = accumulator * number;
    }
    return accumulator
}


In the imperative languages, there exist subcategories of programming  languages such as scripting languages, object oriented languages, and Von Neumann languages which are based on statements (in honor to the creator of this language  John Von Neumman – http://en.wikipedia.org/wiki/John_von_Neumann) .


Scripting languages examples: Bash, PHP, ASP, Python, Perl, Ruby.


This kind of languages let the programmer to create components and then combine them. The programmer can create a program and run it in real-time without compiling it, since each instruction is interpreted in real-time, letting the programmer to be able to change the program and witness the results instantaneously. However, there is a trade in speed.


Object Oriented languages examples: Java, C++, Small Talk, Eiffel.


This kind of languages work on the concepts of classes that are the blueprint to create objects. Later, the idea is to make these objects to interact between them.


Von Neumann languages examples: Fortran, Ada, C.


These languages are sequential in their process.
Share
Leave a comment
About Programming / Prolog

Prolog using Examples – Part 5

The follow is a continuation of the previous posting “Prolog using Examples – Part 4”

Example 1: Check the prefix of a list.

/* Base case */
/* When the list of prefix checked is empty means that we stop checking */
prefix([],_).

/* Recursive case */
/* Both head of the list must be the same */
prefix([Head|Tail_A], [Head|Tail_B]):-
    prefix(Tail_A, Tail_B).

?- prefix([1,b], [1,b,c,4]).
true.

?- prefix([1,b], [1,d,c,4]).
false.


/* prefix will search for each prefix everytime OR ';' is used */
?- prefix(Lst, [1,2,3,4]).
Lst = [] ;
Lst = [1] ;
Lst = [1, 2] ;
Lst = [1, 2, 3] ;
Lst = [1, 2, 3, 4] ;
false.

/* Generate a list where list [1,2,3,4] is the prefix and the tail is a dynamic variable */
?- prefix([1,2,3,4],Lst).
Lst = [1, 2, 3, 4|_G3713]. 

Example 2: Check the suffix of a list.

/* Base case */
/* When both list are the same, we found the suffix */
suffix(Lst_tail, Lst_tail).

/* Recursive case */
/* We want to check always the tail of the list, so the base case can check if they are the same */
suffix([_|Tail], Lst) :-
    suffix(Tail, Lst).

?- suffix([a,2,c,4],[c,4]).
true.

?- suffix([a,2,c,d],[c,4]).
false.

/* Obtain the next tail everytime OR ';' is used */
?- suffix([1,2,3,4], Lst).
Lst = [1, 2, 3, 4] ;
Lst = [2, 3, 4] ;
Lst = [3, 4] ;
Lst = [4] ;
Lst = [].

/* Be careful, in this kind of cases prolog keep generating dynamic variables in from of the list */
?- suffix(Lst, [1,2,3,4]).
Lst = [1, 2, 3, 4] ;
Lst = [_G3704, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, 1, 2, 3, 4] ;
Lst = [_G3704, _G3707, _G3710, _G3713, _G3716, _G3719, 1, 2, 3|...] ;
... /* Keep generating dynamic variables */

 

Example 3: In this example, we are introducing append. append is the unification of two lists, List_A, List_B, into one list that we are going to call list AB, List_AB.

The code of append is the follow:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

First append will move 1, 2,  and 3 atoms from List_A to List_AB using recursion:

/* Recursive case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-
    append(Tail_A, List_B, Tail_AB).

append([1,2,3], [4,5,6], []) → append([2,3], [4,5,6], [1])  → append([3], [4,5,6], [1,2])  → append([], [4,5,6], [1,2,3])

When List_A is empty, then it will append List_B to List_AB as a tail of List_AB using the base case:

/* Base case */
/* Will stop recursion when List_A is empty indicating that all the elements are in List_AB */
append([], Lst, Lst).


append([], [4,5,6], [1,2,3]) → append([], [], [1,2,3,4,5,6])  → List_AB = [1,2,3,4,5,6]

Example 4: Even do append seems to create a list by appending List_A with List_B, append can behave in a different ways depending of how it is used:

Let see the code for append:

append([], Lst, Lst). /* ← Base case */
append([Head|Tail_A], List_B, [Head|Tail_AB]):-  /* ← Recursive case */
    append(Tail_A, List_B, Tail_AB).

 

Lets say we do  append(List_A, [5,6], [1,2,3,4,5,6]). What would be the result?

As you can see List_AB have 1,2,3,4,5, and 6 while List_B have 5 and 6, Prolog will unify List_A with 1,2,3, and 4.

?- append(List_A, [5,6], [1,2,3,4,5,6]).
List_A = [1, 2, 3, 4] .

Share
Leave a comment
About Programming / Algorithms / Prolog

Prolog using examples – Part 4

In this part of this practical tutorial, we are going to do some coding involving facts, rules, recursion, and lists.

Example 1: Obtain the head of the list, obtain the tail of the list.

/* Get the head of the list */
get_head(Head, [Head|_]).

/* Get the tail of the list */
get_tail(Tail, [_|Tail]).

?- get_head(Head_is, [a,b,c,d]).
Head_is = a.

?- get_tail(Tail_is, [a,b,c,d]).
Tail_is = [b, c, d].

Example 2: Find out if an element is a member of a list.

/* Base case - We find the element inside the list */
/* The element is found if the head of the list can be unified with the element we are searching */
member(Element, [Element|_]).

/* Recursive function that call member with the tail without taking care of the head of the list */
/* The idea is that the base case will be called and check if the element is found */
member(Element, [_|Tail]) :-
    member(Element, Tail).    

?- member(a, [a,1,3,b,c]).
true .

/* Using OR ';', we ask Prolog to search for another element in the list */
?- member(a, [a,1,a,b,c]).
true ;
true ;
false.

/* Element is not found in the list */
?- member(a, [c,1,3,b,c]).
false.

Example 3: Find an specific element member inside a list in a determined position.

/* Base case */
/* The element was found in the list was found, set Position to 1 to stop recursion */
get_member_at(1, [Head|_], Head).

/* Recursive case */
/* Go thought the list until position is less than 1 indicating that member was found */
get_member_at(Position, [_|Tail], Element):-
    Position > 1,
    Temp_Position is Position - 1,
    get_member_at(Temp_Position, Tail,  Element).

/* Get the member at position 3 of the list */
?- get_member_at(3, [1,3,5,7], Lst).
Lst = 5. 

/* This fails when trying to get an element out or bounds of the list */
?- get_member_at(5, [1,3,5,7], Lst).
false. 

/* BE CAREFUL, Sometimes prolog can behave weird base on how you use your functors eg.*/

/* The follow is when prolog create dynamic variables because doesn't now the limit of the list */
?- get_member_at(5, Lst, Lst).
Lst = [_G455, _G458, _G461, _G464, **|_G468].

/* In this case, not only produce dynamic variables to be instanciated, but also add
the list [1,a,b] as the fifth head element of the list */
?- get_member_at(5, Lst, [1,a,b]).
Lst = [_G473, _G476, _G479, _G482, [1, a, b]|_G486] ;

Example 4: Lets obtain the numbers of elements that belong to a simple list.

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

In the recursive case, Prolog will call number_of_elements passing the tail of the list until the list is empty. Then, for every time number_of_elements was call it would return the counter + 1 to the previous call. At the end, we will obtain the total number of elements in the list.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 6.

/* In this case the sublist [1,2,3] inside the list is considerate an element as a whole */
?- number_of_elements([a,b,c,[1,2,3]], Counted).
Counted = 4.

?- number_of_elements([[a,b,c,1,2,3]], Counted).
Counted = 1.

If inside the code we would had the unification symbol instead of the word ‘is’, we would have a different result:

/* Base case - When the list is empty, unify with zero */
number_of_elements([], 0).

/* Recursive case */
number_of_elements([_|Tail], Number_counted) :-
    number_of_elements(Tail, counter),
    Number_counted is counter + 1.

?- number_of_elements([a,1,b,2,^, &], Counted).
Counted = 0+1+1+1+1+1+1.

Example 5: Lets sort a list of elements

/* Base case - Empty list */
sort_list([]).

/* Base case - [_] indicate we don't case about the element, there is only one, the list is sorted */
sort_list([_]).

/* Recursion case */
sort_list([First_element, Second_element|Tail]):-
    First_element =< Second_element,
    sorted([Second_element|Tail]).

?- is_list_sorted([1,2,3,4]).
true .

?- is_list_sorted([1,2,3,4]).
true ;
false.

?- is_list_sorted([1,3,3,4]).
true.

?- is_list_sorted([1,3,5,4]).
false.

This topic will continue in the next posting.

Share
Leave a comment
About Programming / Prolog

Prolog using Examples – Part 3

Prolog have a powerful way to work data by the use of lists. A list is normally a group of elements in each elements would have to pointers, one to the value and another to the next element or rest of the of the list. Just to clarify, we don’t see these pointers.

A list is represented in this way: T = [1, 2, 3, 4, 5] in which T is unified with this list and each number is an element of the list.

You can have also a list inside the list: T = [1, [a, b], 3, 4, 5].

The follows are some examples of how to work with list in Prolog:

Example 1: Lets have two variables, Head and Tail, we want the first element of the list to be unified with the Head variable and the rest of the list to be unified with the tail.

?- [Head|Tail] = [1,2,3,4,5].
H = 1,
T = [2, 3, 4, 5].

Example 2: Let say we wish to obtain the first two elements of the list, First_element and Second_element, and the rest of the list to the variable Tail.

?- [First_element, Second_element|Tail] = [1,2,3,4,5].
First_element = 1,
Second_element = 2,
Tail = [3, 4, 5].

If there are just two elements in the list, the Tail will be pointing to an empty list. An empty list is represented by []

?- [First_element, Second_element|Tail] = [1,2].
First_element = 1,
Second_element = 2,
Tail = [].

A list with less elements that needed, Prolog will indicate us cannot be done.

?- [First_element, Second_element|Tail] = [1].
False


/* Here [A] = [1] means that A is unified with 1, while B is unified with 2,3,4,5 */
?- [[A]|B] = [[1],2,3,4,5].
A = 1,
B = [2, 3, 4, 5].

/* [A|B] = [1,2], C = [3,4,5] → A = 1, B = [2], C = [3,4,5] */
?- [[A|B]|C] = [[1,2],3,4,5].
A = 1,
B = [2],
C = [3, 4, 5].

?- [[A|B]|C] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = [4, 5, 6].

?- [[A|B]|[C|D]] = [[1,2,3],4,5,6].
A = 1,
B = [2, 3],
C = 4,
D = [5, 6].


There are cases in which we can use the feature that Prolog provide of unification.


/* This case, we have the same Head. Notice we have two 3's,
one inside the sublist and one of the list */
?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],3,6,7].
Head = 3,
Tail_A = [4, 5],
Tail_B = [6, 7].


The following case would fails because the first list [Head|Tail_A] would unify with [3, 4, 5] and the second [Head|Tail_B] list would unify with [2,6,7], since the atom 3 is not the same as the atom 2 then it false.


?- [[Head|Tail_A]|[Head|Tail_B]] = [[3,4,5],2,6,7].
false.


The follow is the same example but using different atoms:


?- [[A|B]|[A|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[A|B]|[A|D]] = [[a,b,c],d,e,f].
false.

?- [[A|B]|[_|D]] = [[a,b,c],a,e,f].
A = a,
B = [b, c],
D = [e, f].

?- [[_|B]|[_|D]] = [[a,b,c],a,e,f].
B = [b, c],
D = [e, f].

?- [[A|T]|[B|T]] = [[a,b,c],d,b,c].
A = a,
T = [b, c],
B = d.


This proves that Prolog consider  numbers as atoms (constants) in the same way as lower case characters/names and strings such as ‘abc’.


Using an underscore inside the brackets indicate that we don’t care about that element or elements:


?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|Tail] = [1,2,3,4,5].
Tail = [2, 3, 4, 5].

?- [_|_] = [1,2,3,4,5].
True


In following posting, we will see how to work with lists using facts, rules, and recursion.
Share
Leave a comment
About Programming / Algorithms / Prolog

Prolog using Examples – Part 2

Lets begin with cases related with recursion:

In an imperative style,  you would use a loop to produce a result, while in an functional style, it is common to use recursion to produce the same result.

The most common example related with recursion is the factorial recursion, in which for example the factorial of 6 (6! = 5 * 4 * 3 * 2 * 1) would give us

/* Base case of the factorial, when N is 0 then return 1 */
factorial(0, 1).

factorial(N, M) :-
    N1 is N - 1,
    factorial(N1, M1),
    M is N * M1.
?- factorial(6, T).
T = 720;
ERROR: Out of local stack

Note: As you can see, when we added the OR ‘;’, prolog tried to find another  answer and went out of bound.
To prevent this we can do an small modification as follows:

/* Base case of the factorial, when N is 0 then return 1 */
factorial(0, 1).

factorial(N, M) :-
    N > 0
    N1 is N - 1,
    factorial(N1, M1),
    M is N * M1.
?- factorial(6, T).
T = 720;
False

In this case, when we tell Prolog that we wish to find another possible answer, Prolog would indicate false since it cannot find any other possible solution.

Lets go over some examples:

Example 1: We have a family and we wish to know the descendent of some individual.

/* Maria is_mother_of Pedro */
is_mother_of(Maria, Pedro).

/* Susana is_mother_of Maria */
is_mother_of(Susana, Maria).

/* Pepe is_father_of Pedro */
is_father_of(Pepe, Pedro).

/* Diego is_father_of Pepe */
is_father_of(Diego, Pepe).

/* Person is_parent_of Child if Person is_mother_of Child */
is_parent_of(Person, Child):- is_mother_of(Person, Child).

/* OR */

/* Person is_parent_of Child if Person is_father_of_Child */
is_parent_of(Person, Child):- is_father_of(Person, Child) */

/* Begin RECURSION */

/* Recursion Base */

/* Person is_decendent_of Adult if Adult is_parent_of Person */
is_decendent_of(Person, Adult) :- is_parent_of(Adult, Person).

/* Recursion */
/* Person is_decendent_of Adult if Older(person) is_parent_of Person AND Older is_decendent_of Adult */
 is_decendent_of(Person, Adult) :- is_parent_of(Older, Person), is_decendent_of(Older, Adult).


Example 2: Fibonacci (http://en.wikipedia.org/wiki/Fibonacci_number) is an integer sequence such as 0, 1, 1, 2, 3, 5, 8… As you may notice, the first two numbers are 0 and 1, an the subsequence is form by a number created from the sum of the two previous numbers: 0 + 1 = 1 (0,1,1) , 1 + 1 = 2 (1,1,2), 1 + 2 = 3 (1,2,3), 2 + 3 = 5 (2,3,5) …


/* Recursion base case */
fibonacci(0, 0).

/* Recursion base case */
fibonacci(1, 1).

/* Recursion */
fibonacci(N, F) :-
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    F is F1 + F2.


?- fibonacci(8, T).

T = 21;

ERROR: Out of local stack

Again in this case, when asking prolog to find another answer, it would go out of bounds because there is no case that stop it to keep calling itself. We need to modify this program:


/* Recursion base cases */
fibonacci(0, 0).
fibonacci(1, 1).

/* Recursion */
fibonacci(N, F) :-
    N > 0,
    N1 is N - 1,
    N2 is N - 2,
    fibonacci(N1, F1),
    fibonacci(N2, F2),
    F is F1 + F2. ?- fibonacci(8, T).
T = 21;
False


Again, Prolog couldn’t find a different answer when we ask it to search for it and let it know by returning false after the OR ‘;’.


Example 3: The following code is the Ackermann’s predicate (http://en.wikipedia.org/wiki/Ackermann_function).

One of the purposes to doing this kind of function could be to test the limits of the compiler.

The Ackermann’s functions is defined as follows:

ackermann( m,n ) =    n + 1                                                             if m = 0

ackermann( m,n ) =    ackermann(m – 1, 1)                                if n = 0 and m > 0

ackermann( m,n ) =    ack( m-1, ackermann( m, n-1 ) )          if n >0 and m > 0


/* ackermann(m, n) = n + 1 if m = 0 */
ackermann(Mi, Ni, No):- Mi = 0, No is Ni + 1.

/* ackermann(m, n) = ackermann(m - 1, ackermann(m, n - 1)) if n > 0 and m > 0 */
ackermann(Mi, Ni, No):-
    Mi > 0, Ni > 0,
    Mi2 is Mi - 1, Ni2 is Ni - 1,
    ackermann(Mi, Ni2, No2),
    ackermann(Mi2, No2, No).

/* ackermann(m, n) = ackermann(m - 1, 1) if n = 0 and m > 0 */
ackermann(Mi, Ni, No):-
    Mi > 0, Ni = 0,
    Mi2 is Mi - 1, Ni2 is 1,
    ackermann(Mi2, Ni2, No).


In the next blog posting, we are going to see Lists in Prolog.
Share
Leave a comment