PLI Tutorial 1
Introduction to PLI (and required tools)

(Lm.n refers to Louden, Exercise m.n.)

Make sure you have a working account on the ICT student server dwarf (dwarf.ict.griffith.edu.au).  Use PuttySSH to access dwarf.

Part A.  C programming.

1. Review C.

2. Modify the mergesort program linked from the Resources page to sort an array of structs and not just an array of integers.

3. Write a C library for managing binary search trees of distinct integers.  The library should contain functions for creating a BST, for adding an integer to a BST, for searching a BST for an integer, and, optionally, for deleting an integer from a BST.

Test your solutions using gcc on dwarf.

Part B.  Scheme programming.

1. Download PLT Scheme (DrScheme) onto your PC or onto your H: drive on the University network.  Read the Scheme tutorial "Teach Yourself Scheme in Fixnum Days".  Study the provided examples.  Experiment.

2. Define a function (leaves tree) that, given a binary tree such as 'a or '(a . b) or '((a . b) . (c . (d . e))), returns a list of the leaves in the tree, e.g., (a) or (a b) or (a b c d e).

3. Define a function (equal-leaves? tree1 tree2) that returns true (#t) or false (#f) depending on whether or not the two trees have equal lists of leaves.  E.g., (equal-leaves? '(a . b) '(a . c)) ==> #f but (equal-leaves? '(a . (b . c)) '((a . b) . c)) ==> #t.  Rewrite your definition so that it is more efficient when the trees differ on one of the first of their leaves.

Part C.  Compilers.

(Some of these problems will carry over to week 2.)

1. A compiler is a program which takes a program text as input.  List as many other programs as you can that take program texts as input.

2. Discuss what is involved in (a) retargeting a compiler to produce target code for a new machine and (b) rehosting a compiler to run on a new machine.  Illustrate these two operations with T-diagrams (Louden, 1.6).

3. Translate the following Tiny program (Louden, Figure 1.4) into an equivalent sequence of TM instructions.  (Tiny and TM are described in the Resources page.)

	{ Sample Tiny program - computes factorial }
	read x; { input an integer x }
	if x > 0 then 
	   fact := 1;
	   repeat
	      fact := fact * x;
	      x := x - 1
	   until x = 0;
	   write fact { output factorial of x }
        end