Programming Paradigms

In COMP 3007 we learnt about different programming paradigms. Assignments mainly focused on functional programming using Scheme and logic programming with Prolog. Discussed along the way were concepts relating to applicative and normal order evaluation.

A few questions from the assignments which stand out to me are explained below. The first few questions were done using Scheme. They included a semi-complicated mathematical problem which we had to solve using both iterative and recursive processes, and a function which generated all permutations of an input list.

The first Prolog question I remember working on asked to create a binary tree relation along with several helper functions. These functions included a depth generation function along with Post-Order, Pre-Order, and In-Order traversal procedures similar to the ones from the text The Art of Prolog: Advanced Programming Techniques.

The second Prolog question related to graph theory, and asked to create rules to solve the single source shortest path problem to answer whether two specified nodes were connected. After spending some time trying to figure out how to implement Dijkstra’s or the Bellman-Ford algorithm in Prolog I decided to simply generate all paths between the two specified nodes and select the shortest path. This is not very efficient, although that’s not what the class was about (which the Professor mentioned several times). The code worked by simply using the built-in findall statement to generate unique paths until no more could be created. The path uniqueness was enforced by the called procedure being limited to only following an edge once in the same path, thus limiting the use of cycles. After the paths were generated the weights of all paths were calculated and the path with least weight was selected and returned.

The third and last Prolog question asked to create a procedure to take as input two lists; one representing teams, and another representing tables. The general scenario was that the teams are invited to a banquet, and the players must be sat at the tables such that there is at most one player from each team at a table. The procedure created was meant to seat the players at the tables, and return either the proper seating configuration or an indication that a configuration cannot be found.