COMP348 Tutorial Notes
Principles of Programming Languages - Concordia University Fall 2017

Remember to fill out the TA/Lab instructor online evaluations
Programmer on Duty (One-on-one assistance) @ H854 --Tu--Th-- 16:00-17:30
Tutorial Leader @ H917 ------Th-- 14:45-15:35

List of tutorials
Tutorial 1 - Prolog An Introduction
Tutorial 2 - Prolog Recursion
Tutorial 3 - Prolog Advanced Recursion
Tutorial 4 - Lisp An Introduction
Tutorial 5 - Lisp Recursion
Tutorial 6 - Lisp Advanced Recursion
Tutorial 7 - Ruby An Introduction
A Retrospective on Prolog
Tutorial 8 - Ruby Classes and Objects + Introspection
Tutorial 9 - Ruby Code Blocks
Tutorial 10 - Basic Pointer Manipulation in C
Tutorial 11 - More Pointer Manipulation in C
Tutorial 12 - AspectJ

Tutorial 12 (30 November 2017)

Install AspectJ from this URL.

Tutorial 11 (23 November 2017)

More Pointers in C.

Basic manipulation of char pointers tutorial11_a.c

Basic use of string.h library tutorial11_b.c

Allocating memory on the heap (char array) tutorial11_c.c

Allocating memory on the heap (Person struct) and passing pointers to struct tutorial11_d.c
The order matters when reclaiming the memory from the heap free(...);

Tutorial 10 (16 November 2017)

Pointers in C. We covered the basic use of GCC
gcc -Wall tutorial10.c -o tutorial10.app

You can download the program we developed in tutorial 10 here: tutorial10_prog1.c

Tutorial 9 (9 November 2017)

Code blocks in Ruby.

Tutorial 8 (2 November 2017)

Classes with Ruby. Object introspection.

Tutorial 7 (26 October 2017)

Please revise and acquaint yourselves with the Learn X in Y minutes Ruby Tutorial.
We will cover classes with Ruby next tutorial. See you next week!

-Adrianna Prolog will come back for the final exam, so keep practicing. The code is here.

Midterm (25 October 2017)

Practice for Midterm:
COMP348 Midterm Sample 2009
COMP348 Midterm Sample 2013

Tutorial 6 (19 October 2017)

Recommended reading: Lisp Structures (continuation)

Double All Atoms - in a list

We are going to define a function that doubles every atom encountered in a (possibly nested) list.

Interleave list

Given two SORTED lists, merge them so that the whole resulting list is SORTED, in O(n) time...

MERGE sort of a list

Given a list of numbers, use the top-down list approach, to divide the list into two sublists, and recursively call this function, then, merge the resulting sublists.
  1. BASE CASE 0: Function is given a null list, functions takes nil as value.
  2. BASE CASE 1: A list with only one element is henceforth deemed to be sorted.
  3. RECURSIVE CASE: Split the list down the middle call the function recursively on the two halves, use the interleave function to merge the two resulting sorted sublists.
Here is the program we developed during the tutorial.

Tutorial 5 (12 October 2017)

Recommended reading:
Lisp Structures We are going to create binary trees and define several functions to handle them.
This is what our tree will look like conceptually. This is what the tree looks like inside Lisp.

Use of defstruct

Insert element in tree

(binary-tree-insert 'tree 'element)
  1. BASE CASE: Function is given a null subtree, then it makes a sub-tree and inserts element as value.
  2. Element we're inserting is less than the value at the root of the subtree, we recurse on the left subtree.
  3. Element we're inserting is greater than the value at the root of the subtree, we recurse on the right subtree.

Binary search in tree

(binary-tree-search 'tree 'element)
  1. BASE CASE 0: Function is given a null subtree, returns nil (FAILURE)
  2. BASE CASE 1: The value of the subtree is equal to the element being searched, returns element. (SUCCESS)
  3. Element we're inserting is less than the value at the root of the subtree, we recurse on the left subtree.
  4. Element we're inserting is greater than the value at the root of the subtree, we recurse on the right subtree.

Inorder traversal of tree

Will print the contents of the tree in natural order. (binary-tree-inorder 'tree)
  1. Stopping condition:Function is given a null subtree.
  2. Function recurses on the left subtree.
  3. Function prints the value of the root of the subtree.
  4. Function recurses on the right subtree.
Here is the program we developed during the tutorial.

Tutorial 4 (5 October 2017)

Suggested Reading:

Math with Lisp.

+, -, /, *, expt, mod, floor, ceiling, cos, sin, tan, incf, decf, pi, abs The Numbers Dictionary (Common LISP Hyperspec)

Manipulation of lists

car, cdr, cons, list, setcar, setcdr, nth, append, member, last

Variable assignment

global setf, local let

User-defined functions

defun, use of recursive constructs, output to console print, format

From algorithms to code

  1. Printing a list.
  2. Length of a list.
  3. Max of a list.
  4. Factorial of a number.
  5. GCD between two numbers.
  6. from the recommended reading...
Here is the program we developed during the tutorial.

Tutorial 3 (28 September 2017)

Delete all instances of E in a given list. mydelete([H|T],E,OutputList).
Solution:
mydelete([],_,[]).
Any element deleted from an empty list gives the empty list.
mydelete([H|T],E,[H|Output]):- H \== E, mydelete(T,E,Output).
If the Head is different from the Element, keep the Head in the Output, recurse on the Tail.
mydelete([E|T],E,Output):- mydelete(T,E,Output).
If the Head is identical to the Element, then you don't add it to the Output.
The nth element of a list. mynth([H|T],N,Elem).
You count backwards, recurse, instantiate the Element when you hit 0.
 0,1,2,3,4,5    Index starting
[a,b,c,d,e,f]    Initial list of elements
 4,3,2,1,0    We count backwards from the index we're looking for.
Solution:
my_nth([Elem|_],0,Elem):-!.
my_nth([H|Tail],Index,Elem):- Counter is Index - 1 , my_nth(Tail,Counter,Elem

Find the greatest number in a given list.
mymaxlist([H|Tail],Max):- mmax([H|Tail],Temp,Max).

mmax([],Max,Max).
mmax([H|Tail],TempValue,MaxOfList):- max(H,TempValue,TempMax), mmax(Tail,TempMax,MaxOfList).

max(N1,N2,Max):- N1 > N2, Max is N1.
max(N1,N2,Max):- N1 < N2, Max is N2.
max(SameNumber,SameNumber,SameNumber).
The greatest number is the same number, when you're given two identical numbers.

You can download the program we developed in tutorial 3 here: tutorial03_prog1_lists.pl

Tutorial 2 (21 September 2017)

Suggested Reading: Review examples from the Prolog handout 1

In this tutorial, we didn't attempt to review the slides from Professor Taleb (check Moodle for them...).

We went for a more practical approach.

NOTE: If you haven't yet gotten Prolog to run on your computer, I suggest you look at Tutorial 1 in this page.

If we had a list1 = [3,5,7,9] and we wanted to store it as a variable in the database:

In order to use it with a variable L we have to check for the possibility of the database to instantiate it.

The familiar idioms to iterate through lists are completely different in Prolog, due to the use of the Declarative Paradigm instead of the Imperative Paradigm in mainstream programming languages such as C, and Java.

So suppose you wanted to calculate and return the average of a list that has real numbers.

We would have to use the following expression (with Prolog builtin functions length/2 and sum_list/2 (see below for our own implementations):

average(List,Avg):- length(List,Len), Len > 0, sum_list(List, S), Avg is S / Len.

First we instantiate the list L by matching with an existing predicate list1, then we pass L to the function average, which succeeds if the second argument is the average of the first argument which is a list. This is by first calculating the length (builtin), checking for a length greater than zero to avoid the division by zero error, then calculating the sum with another builtin, and finally instantiating Average as the division of Sum by Length.

For the rest of the tutorial we came up with our own implementations of several of the Prolog builtins which are available in most flavours of Prolog.

In Prolog we can only see the first element of a list called the Head and the rest of the list is contained in a sublist called the Tail of the list.

[Head|Tail]

This is an important concept because it is at the heart of the use of recursion in Prolog,

list([]).%The empty list is a list.
list([_|Tail]):-list(Tail).%A list is a list if the tail of the list is a list itself.

The recursive definition of a list. The Art of Prolog, 2nd Edition, p. 57

Back to the problem at hand, to get the length of a list.

mylength([],0).%The length of the empty list is zero.
mylength([H|Tail],Sum):-mylength(Tail,SumTail), Sum is SumTail + 1 .The length of a non-empty list is one plus the sum of its Tail.

Also the sum of a list:

mysumlist([],0).The sum of the empty list is zero.
mysumlist([H|Tail],Sum):- mysumlist(Tail, SumTail), Sum is SumTail + H .The sum of a list is the sum of the Tail plus the Head element.

We also developed our own versions for membership check in a list, a function to retrieve the last element of a list, and the first element of a list.

You can download the program we developed in tutorial 2 here: tutorial02_prog1_lists.pl

Tutorial 1 (14 September 2017)

Suggested Reading: Familiarize yourself with pages 2,3 of Prolog handout 1

You can either use SWI-Prolog to edit and run your programs (pseudo-IDE) or use a text editor (Vim or SublimeText) + gProlog (The GNU Prolog interpreter)

Save the programs with .pl file extension

Useful commands in gprolog
[filename_lowercase_without_extension]. To load a file called file.pl
listing. Shows all the statements loaded
trace. To debug your program

We made a small database program. It is about a basic model of the Solar System, the Sun and the first four planets.

You can download the program we developed in tutorial 1 here: tutorial01_prog1_planets.pl