CS 480 Notes

CS 480 Notes

November 9, 2006

Alan R. Crouch

LISP and Trees

Its good to have comments and tests to see that it works

Comments are made like this:

; This is a comment

Some Ideas on solving Build List

Function	Arguments
Append	2 lists
Cons	Atom & list OR 2 lists
Car / Cdr	All

New Function

(Trace functionName) - Traces a function

Types of Trees

() ß Empty Tree

((5)) ß Tree with one element and no children

((2)(3)(4)) ß Tree with one parent and 2 children

(((2)(3)(4))(5)((6)(7)(8))) ß Tree with one parent and 2 children with 2 children each

3 Depth first Traversals (these are traversals)

-Pre Order

-Post Order

-In Order

Breadth first (level by level)

(((4)(C)(3)(A)((1)(B)(2)))

~~ABC432~~1

We don’t generally put duplicate items in the tree

(((2)(4)(5))(6)((7)(8)(9)))

Traversal

Visit the node if it exists:

Go left

Go right

Visit 6 Go Left

Visit 4 Go Left

Visit 2 Go Left

Go Right

Visit 5 Go Left

Go Right

Visit 8 Go Left

Visit 7 Go Left

Go Right

Visit 9 Go Left

Go Right

à Pre-Order Traversal 6 4 2 13 5 3 72 14 (Visit go Left go Right)

à In-Order Traversal 2 4 13 6 72 3 5 (Go Left Visit Go Right)

à Post-Order 2 13 4 72 3 4 5 6 (Go Left Go Right Visit)

Assignment:

Part 1: Program to either build a binary search tree as a list similar to the ones on the blackboard or to traverse a tree expressed as a list is due Monday night at Midnight. It should have the standard heading, comments, descriptions. It should be named yourname7.lsp and should NOT be zipped.

Part 2: Download Alice to your computer from CMU site www.alice.org - be sure to get it from here as there is another Alice programming language that we are not going to use. If you have time, start the tutorial as you will have an Alice program due on Thursday.

Below is a copy of the code Mike Ware wrote for BuildList which he has been kind enough to share (in the two boxes)

; Programmer: Mike Ware

; Course: CS 530 T/TH 2:00

; Date Due: 11-9 zero-hundred hours

; Language: LISP

; Compiler: xlispsml.exe

; Source Filename: WareBuildList.lst

; Executable Filename: WareBuildList.lst

; Professor: Dr. Adams

; PURPOSE: A lisp function to build a list of atoms ordered in descending order.

;           The atoms are actually integers.

; INPUT: The function takes two parameters. The first parameter is an

;           atom to be inserted. The second parameter is a list.

; OUTPUT: The function returns a list with the new atom inserted into

;           its proper location in the list.

;           > (buildList 3 '())

;           (3)

;           > (buildList 3 '(5 1))

;            (5 3 1)

;           > (buildList 3 '(5 4))

;           (5 4 3)

;           > (buildList 3 '(5 4 2 1))

;           (5 4 3 2 1)

;           > (buildList 6 '(5 4 2 1))

;           (6 5 4 2 1)

;           > (buildList 0 '(5 4 2 1))

;           (5 4 2 1 0)

;           > (buildList 3 '(5 4 2 1))

;           (5 4 3 2 1)

;           > (buildList 100 '(5 4 3 2 1))

;           (100 5 4 3 2 1)

; MODIFICATIONS:

;    error: EOF reached before expression end

;    error: can't load file

;            C:\\mystuff\\jmu\\classes\\530\\lisp\\WAREBU~1.LST"

;           - was missing a parentheses

;    error: too few arguments

;           - improper use of parentheses

;           - had (atom) and only needed atom

; GENERAL COMMENTS ABOUT THE PROGRAM OR THE LANGUAGE:

;    The function assumes that the list is already sorted into descending

;    order. If the list (the second parameter) is not sorted into

;    descending order, then it will not return a sorted list.

; Schematically, a LISP function definition looks like this:

;        (defun <name> <parameter-list> <body>)

;    defun is a keyword allowing you to define your own functions

;    <name> is a name for the function

;    <parameter-list> is the parameters for the function (and is optional)

;    <body> is the statements executed inside the function

;    Below,

;           cond stands for condition and allows for multiple

;           expressions to be evaluated; if the first expression returns false,

;           then the following expression is evaluated, and so on; if an

;           expression returns true, then the function returns at that point

;    EQ is an equality operator

;    cons is used to build a new list

;    >= is an greater-than or equal to operator

;    car is used to return the first atom in a list

;    cdr is used to return the tail end of a list as a list

;    t stands for true and is a default statement to be executed when all else are false

(defun buildList (atom list)

     (cond

            ((EQ list NIL) (cons atom '()))

            ((>= atom (car list)) (cons atom list))

            (t (cons (car list) (buildList atom (cdr list))))

Possibly new information

You can trace Lisp functions, both user-defined and built-in using (trace functionName)

You can turn the trace off using (untrace functionName).

You can have output from your program go to a file using (dribble “filename.txt”)

Sample representations of binary trees as lists: I may test your programs with a more complex tree.

( ((5) (10) (15)) (25) ( (30) (40) (50)))

( ( nil (10) (23)) (25) ( (30) (40) nil ))