Computer Science 456: Artificial Intelligence and Expert Systems

Unit 2: AI Programming Languages – Prolog and Lisp

This unit covers the programming language component. It focuses on the exploration of the programming paradigms in Prolog and Lisp, which are considered to be the main programming languages used by the AI community. The founding concepts, syntax, and data structures in these two languages are presented using supporting examples for a fast and lucid learning experience.

Note: You can choose to learn either Prolog or Lisp, or both. However you are required to learn only one of these languages for use in practicing the learned concepts and completing the programming part of the assignments.

Activities

Download the PDF file “AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java”: http://wps.pearsoned.com/wps/media/objects/5771/5909832/PDF/Luger_0136070477_1.pdf/

Assignment 1

Complete Assignment 1, and submit it to your tutor for evaluation and feedback.

Compilers for Prolog and Lisp

The course is based on the standard specifications for Prolog and Lisp that are implemented by most of the compilers. You are free to use any compiler that you are familiar with as long as you will be able to submit your source code for marking.

Examples of compilers that you can use:

GNU Prolog: http://www.gprolog.org/

SWI Prolog: http://www.swi-prolog.org/

GNU Common Lisp: http://www.clisp.org/

LispWorks: http://www.lispworks.com/

Section 2.1: Introduction to Programming in Prolog

In this section, you will learn how to program using Prolog, the language for programming in logic. The concept of declarative programing will also be introduced. This section will explain the concepts of facts and rules, and give an overview of the syntax of Prolog predicates. It also discusses the list representation as the main data structure used in Prolog and presents recursion as the main process used in Prolog programs.

Learning Objectives

  • Explain the concepts of facts, rules, and predicates.
  • Write logic predicates using Prolog syntax.
  • Apply the list representation to your data structures in Prolog.
  • Use the recursion process and backtracking to control your Prolog predicate execution.

Key Terms

fact, rule, predicate, backtracking, variable binding, built-in predicate, list, recursion

Readings

Read Chapter 2 from the textbook companion resource, AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.

Tasks

Practice the following exercises from Chapter 2 of the textbook companion resource AI algorithms, data structures, and idioms in Prolog, Lisp, and Java:

  •  Exercises 2, 3, and 4. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.

Section 2.2: Abstract Data Types and Backtracking Control in Prolog

In this section, you will learn some advanced Prolog programming mechanisms. The cut predicate and control of the Prolog backtracking mechanism is explained. Abstract data types and procedural abstractions are also discussed.

Learning Objectives

  • Outline some of the built-in predicates such as path(), not(), and member().
  • Apply cut to control backtracking.
  • Use abstract data types to enhance Prolog programs.

Key Terms

built-in predicate, cut, abstract data type, set, stack, queue, priority queue

Readings

Read Chapter 3 from the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.

Tasks

Practice the following exercises from Chapter 3 of the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java:

  •  Exercises 2 and 3. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.

Section 2.3: Introduction to Programming in Lisp

In this section, you will learn how to program using Lisp as a language for symbolic computing. The concept of functional programing will also be introduced. This section will explain the preliminary tools and techniques for Lisp as well as the critical data structures. We will explore the recursive definition of symbolic expressions and introduce concepts for assembly instructions. Using examples, we will also demonstrate the creation and evaluation of symbol expression.

Learning Objectives

  • Explain the concepts of symbol expressions and Lisp predicates.
  • Write functions using Prolog syntax.
  • Practice Lisp program control.
  • Apply lists as recursive data structures in Lisp.

Key Terms

s-expression, atom, list, function, Lisp evaluation, conditionals, predicates, symbolic computing

Readings

Read Chapter 11 and Chapter 12 from the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.

Tasks

Practice the following exercises from Chapter 11 of the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java:

  •  Exercises 1 and 4.

Practice the following exercises from Chapter 12 of the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.

  • Exercises 1 and 2.

You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.

Section 2.4: Variables and Data Types in Lisp

In this section, you will learn some advanced programming mechanisms in Lisp. This section explains the creation of variables using set and let as well as their bindings. It also presents commonly used data types including the built-in ones such as arrays, hash tables, and sets.

Learning Objectives

  • Outline the definition of local variables.
  • Outline the binding of variables.
  • Use data types to enhance Lisp programs.

Key Terms

variable creation, variable binding, data types

Readings

Read Chapter 13 from the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java.

Tasks

Practice the following exercises from Chapter 13 of the textbook companion resource AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java:

  • Exercises 1 and 3. You may want to use the Personal Workspace wiki on the course home page and/or share your observations with classmates in the COMP 456 General Discussion forum.

TOP