Welcome!

This book has been replaced by the newer and much enhanced Foundations of Programming Languages. The webpage for this new text can be found here. This page is left here for reference to the old text only.

Welcome to the web page for Programming Languages: An Active Learning Approach written by Kent D. Lee and published by Springer Science. This book was written as an introductory undergraduate text in Programming Languages. The text is oriented towards students who have taken an introductory sequence of courses using an Object-Oriented imperative programming language. However, it can be used by students with programming skills in any language. The intent of the text is to teach students how to program in the three programming paradigms: Object-Oriented Imperative , Functional, and Logic. While teaching skills like pattern-matching, recursion, and the use of unification the three paradigms are contrasted to show the differences between languages of these types. In addition, important aspects of programming languages are discussed that affect software reliability and the ease of programming.

The text is very hands on with many examples, practice exercises (with solutions!), and programming projects. The best way to teach from this text is to make lectures interactive with students working through practice exercises during class. They may check their work against the solutions at the end of each chapter as they work through the text. The projects and exercises reinforce what was taught in the chapter. Many of the projects have source code provided to help the students in getting started. Downloads for each of the chapters are provided below.

Errata and Suggestions

I hope both professors and students enjoy using the text! I hope to get constructive feedback from folks so if you find an error or have a suggestion don't hesitate to email me. My email is kentdlee at luther.edu. The Errata page is for typos or other problems in the text. Please consult the Errata page if you are unsure whether or not you've discovered an unknown problem in the text. If you have suggestions you would like to make for future printings of the text, please email me.

Lecture Slides and Solutions to Exercises

If you are an instructor using or considering using the text to teach a course and would like lecture slides and solutions to exercises, I would be happy to provide them. Detailed lecture slides are available with all examples and practice problems from the text. Please email me and provide me with information about where you are teaching and a web site where I can verify that you are a teacher at your institution and I will email you a userid, password, and link where you can download the support materials.

News

• Website made available January of 2007.
• 3-11-2008. The book will be published by Springer Science and should be available for Fall 2008.
• 09-04-2008. Book is now available from Springer.

Support Files for Individual Chapters

The following sections contain support files for individual chapters. These support files may be downloaded by students or faculty to complete projects from each of the chapters below.

Chapter 2

Download: The EWE Interpreter
The EWE language is an extended version of Sethi's RAM (Random Access Machine) language. EWE was written to simulate a very simple machine with random access storage. The machine can store integers, one per memory location. There is also some language support for storing strings (as strings of integers representing ASCII characters). The BNF for the language is in chapter two of the book and several exercises require the students to write EWE programs. They can check their programs with the interpreter provided here. The interpreter may be compiled by downloading and installing the Standard ML of New Jersey implementation of ML. The interpreter is almost completely written in ML. While written in ML, one support file (the ewe script) assumes that the underlying implementation supports a scripting language to start the interpreter. A Makefile is also supplied to easily make the interpreter. If you are downloading this code to a Windows machine you may have to execute the commands in the Makefile by hand to make the project. A short batch program can be used to start the interpreter. See the ewe script supplied with the installation for details on what to put in the batch file.

Chapter 3

Download: The C++ Calculator Language Interpreter

This is the C++ Calculator Language Interpeter code. Enough code is provided to get students started on the project given at the end of the chapter. The Calculator Language is the language of expressions with a memory location that may be stored to and retrieved during expression evaluation. To complete the project a recursive-descent parser must be completed as well as code to evaluate the Abstract Syntax Tree (AST) associated with an expression to be evaluated. The code that is provided here will add and subtract integers with no modification.

Students learn about the structure of an interpreter. At the same time they learn about C++ programming including the organization of code within a C++ project, use of the C++ preprocessor for class declaration and separate compilation.

Chapter 4

Download: The Ruby Calculator Language Interpreter

This is the Ruby Calculator Language Interpeter code. This project is a repeat of the C++ Calculator Language Interpreter. Given that there may not be enough time in a semester to do both projects, one or the other may be chosen. Completing both projects will illustrate the difference between a statically typed, compiled language (C++) and a dynamically typed, interpreted language. Ruby implements polymorphism by delaying method and instance variable lookup until run-time through the use of a hash table lookup of instance variables and methods.

There is less overhead involved in learning and using Ruby so if C++ is new to students and time is limited, the Ruby project will be easier to introduce and bring students up to speed on.

Download: The Ruby Calculator Language Compiler

Exercise 7 at the end of the chapter requires you to implement a compiler instead of an interpreter for calculator expressions. The compiler targets the EWE language presented in chapter 2. The code provided in the download above will get you started implementing a compiler in Ruby.

Chapter 6

Download: The Standard ML Calculator Language Compiler

This is the Standard ML Calculator Language compiler. The compiler targets the EWE machine presented in chapter 2. The language is extended through a series of incremental projects. Extensions are somewhat independent of each other so not every project has to be completed to proceed to the next one. A register machine is simulated using the EWE target language. The compiler uses a register allocation framework to manage the allocation of registers in a stack machine like fashion.

Students learn the difference between compile-time and run-time issues. The learn about register management and how the functional design of a compiler using pattern-matching and strong type checking.

Chapter 7

Download: The Prolog Family Tree Example

This is the Prolog family tree database from the text. Several examples, practice problems, and exercises depend on this data. To avoid retyping all the information you may download it here.

Download: The Prolog Binary Search Tree Example

This is the Prolog binary search tree code. A few examples use this code. A couple of projects extend the code provided here.

Project: The Prolog Calculator Language Interpreter

There is no code download provided for the Prolog Calculator Language interpreter. However, the predicate for starting the interpreter should be something like this:

calc :- read a line, preprocess the line, parse the expression, evaluate the AST.

Each of the steps outlined above is described in the text. To invoke the calculator you query Prolog with the calc predicate. There are no parameters provided when querying with the calc predicate.

Chapter 8

Download: The Genesis Action Semantics Compiler Generator

Genesis is a compiler generator for Action Semantic Descriptions. It is based on the work of Peter Mosses and David Watt. While written from scratch, some of it was inspired by the Actress compiler generator of Hermano Moura and Deryck Brown (and others). To use Genesis you must download Genesis from here. You need to install Standard ML of New Jersey and the Jasmin Java assembler. You need to set your path to include the programs from both Standard ML and Jasmin. Then you should proceed to the installation instructions below.

The Genesis compiler generator is meant to be installed by each individual that will use it. It is not currently written to be installed site-wide. To install the compiler generator you must have already installed Standard ML and the Jasmin Java assembler. Genesis will generate compilers that either target the JVM or MIPS assembly language. A MIPS simulator is available if you want to target MIPS assembly language. Send email to me to get the MIPS simulator. To install Genesis, download the zipped file above and unzip it. In the genesis directory edit the genesis script so the GENPATH variable points to the current location of the genesis directory

GENPATH=/path/to/the/script/genesis

Then, link to the genesis script from your path. For instance,

cd ~/bin
ln -s ../genesis/genesis

Then you can change directory to your genesis folder and type "make" to make the compiler generator. Finally, you can go to the examples/small subdirectory and type

genesis small jvm

and it will generate a compiler from the Action Semantics Definition called small.asd. The generated compiler is called smallc and you can run it to compile a file

smallc test28.small

to run a test program you can run the java virtual machine

java test28

That should do it. You can modify the Action Semantic Definitions provided to suit your needs or write your own description from scratch. This is research code so use at your own risk. All code is mine and no portion of it should be used for commercial purposes without my written consent.