A week’s exploration of declarative programming through Prolog

Prolog (1972) is a dinosaur of the programming cannon, forgotten and nearly childless (overlooking SQL). Arguably victim of its own genius and unfortunate historical associations. On these grounds, I’ve decided to commit a week’s worth of free time towards playing with Prolog, seeing through the difficulties of the learning curve to understand its merits. It seems reasonable to assume that some useful applications of the logic paradigm might present themselves.

I started with this inviting post.

Advertisements
A week’s exploration of declarative programming through Prolog

Graph Theory: Shortest Path Algorithm

“The mind is a wonderful thing. You start off on one journey but it decides to take you somewhere completely different. The path of least resistance is the way to go. Don’t fight it – enjoy the ride.”
David Alejandro Fearnhead

Following an introduction by my colleague Ben Cohen, I’ve continued studying Steven Wolfman’s presentation on graph theory with the aid of some other resources.

Here, we’ll consider the shortest path problem:

Given: A graph G with (positively) weighted edges

Find: the least costly path from nodes X to Y

For this problem, we’ll explore Dijkstra’s algorithmic solution. Note that an unweighed graph shortest path can be solved using a simple breadth first search. A more general, but less efficient Bellman-Ford algorithm offers a solution for graphs with negatively weighted edges. Also consider that the algorithm being presented is not suitable for graphs with negative cost cycles, which make cost of transversal arbitrarily small.

Our implementation of Dijkstra’s shortest path algorithm should execute with O(n^2) (more precisely, O(|v|log|v|+|e|))time complexity. However, a simpler topological sort provides an answer for directed acyclic graphs in linear time.

An implementation of this algorithm using Python’s NetworkX package is in the works.

reference: Algorithm Design Manual, Skiena (2010)

 

 

 

Graph Theory: Shortest Path Algorithm

C++ Stack Implementation

Continuing with the theme of implementing elementary data structures, I pumped out a quick stack implementation in C++.

#include <stdio.h>
#include <iostream>

class stack{
int stack[100]; // allocate a maximum of 101 information slots
int t= 0; //top of stack
void push(int x){
stack[t]=x;
t++; // add error exception for full stack
};
int pop(){
return stack[t];
t--; // add error exception for empty stack
}
int length(){
return t;
}
int peek(){ //make sure this is what peek actually is supposed to do
return stack[t-1]; //add out of bounds except
}
bool isEmpty(){ //better way to do this? backed myself into a corner?
return t==-1 ; //fix
}

As the comments indicate, I haven’t finished yet.

C++ Stack Implementation

Exploring Julia

https://camo.githubusercontent.com/e1ae5c7f6fe275a50134d5889a68f0acdd09ada8/687474703a2f2f6a756c69616c616e672e6f72672f696d616765732f6c6f676f5f68697265732e706e67

I decided to take a few hours today to learn some Julia. Julia is a fairly new language (2012) that has received a good deal of attention for its appeal to the scientific/data-science communities. A statement of motivation here.

Since my first two posts on C and Python implementations of linked lists, I’ve quickly taken note of the enormous time cost of thorough documentation of progress. For now, I’ll readjust to write less of all I learn/do and more on what’s notable. Also, I’ll keep a focus on the facts rather than introspection.

Spending some minutes reading about the language revealed some desirable properties:

  • strong and transparent type system appeals to tastes developed while journeying through Haskell
  • fairly clear syntax
  • f!() notation for those functions which mutate their arguments
  • type classification is a property of values, rather than variables
  • the existence of BioJulia, which might be something cool to contribute to in the future

I’ll add more notes here as I continue reading about the language.

Exploring Julia

Implementing a Singly Linked List in C++

 

Implementing a Python linked list left me a bit unsatisfied. Does this data structure really qualify as a linked list, or is it some sort of analogue? In searching for an answer, I came across this definition of Linked Lists from Wikipedia:

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

While pointers don’t seem to be an explicit requirement, studying a proper linked list in C/C++ seems like a good learning exercise.

Here’s a C++ linked list I came across surfing the web for a simple implementation, annotated piecewise:


#include <iostream>;
using namespace std;

class LinkedList{
struct Node {
int x;
Node *next;</pre>
};

Within the template for a linked list, a structure called node is defined first. Node, representing a single entry in the list, contains two bins, a value and a pointer referencing the next entry.

The Linked List class continues:

public:
LinkedList(){
head = NULL;
}

A value constructor sets the head value to NULL. Any instance of our linked list class starts its life an empty, with the head space set to NULL.

void addValue(int val){
Node *n = new Node();
n->x = val;
n->next = head;
head = n;
}

To this empty list we use a method called addValue to chain items. This method evokes a new instance of the node structure, to which the argument value is passed as the node’s value. Next of this node points to the current head, which for a new linked list function is simply NULL. This new node then is designated as the new head.


int popValue(){
Node *n = head;
int ret = n->x;

head = head->next;
delete n;
return ret;
}

This next method allows us to reverse the effect of the previous prepending addValue function. ret is assigned the value of the current head node’s x. Then, head is reassigned as the current next value. Now that the old next cell is set to the head of the list, it is now safe to delete the previous head node and return its x value.

private:
Node *head;
};

_

Implementing a Singly Linked List in C++