Foundations of Programming Languages

Foundations of Programming LanguagesReviews
Author: Kent D. Lee
Pub Date: 2014
ISBN: 978-3-319-13313-3
Pages: 354
Language: English
Format: PDF
Size: 17 Mb


This clearly written textbook introduces the reader to the three styles of programming, examining object-oriented/imperative, functional, and logic programming. The focus of the text moves from highly prescriptive languages to very descriptive languages, demonstrating the many and varied ways in which we can think about programming. Designed for interactive learning both inside and outside of the classroom, each programming paradigm is highlighted through the implementation of a non-trivial programming language, demonstrating when each language may be appropriate for a given problem. Features: includes review questions and solved practice exercises, with supplementary code and support files available from an associated website; provides the foundations for understanding how the syntax of a language is formally defined by a grammar; examines assembly language programming using CoCo; introduces C++, Standard ML, and Prolog; describes the development of a type inference system for the language Small.


This book is not meant to be a survey of lots of different languages. Rather, its purpose is to introduce you to the three styles of programming languages by using them to implement a non-trivial programming language. These three style of programming are:

  • Imperative/Object-Oriented Programming with languages like Java, C++, Python, and other languages you may have used before.
  • FunctionalProgrammingwithlanguageslikeStandardML,Haskell,Lisp,Scheme, and others.
  • Logic Programming with Prolog.

The book provides an introduction to programming in assembly language, C++, Standard ML, and Prolog. However, the programming language concepts covered in this text apply to all languages in use today. The goal of the text is to help you understand how to use the paradigms and models of computation these languages represent to solve problems. The text elaborates on when these languages may be appropriate for a problem by showing you how they can be used to implement a programming language. Many of the problems solved while implementing a programming language are similar to other problems in computer science. The text elaborates on techniques for problem solving that you may be able to apply in the future. You might be surprised by what you can do and how quickly a program can come together given the right choice of language.

Semantics is the word that is used when deriving meaning from what is written. The semantics of a program refers to what the program will do when it is executed. Informally it is much easier to say what a program does than to describe the syntactic structure of the program. However, syntax is a lot easier to formally describe than
semantics. In either case, if you are learning a new language, you need to learn something about both the syntax and semantics of the language.

Assembly Language

Python is an object-oriented, interpreted language. Internally to the Python interpreter, a Python program is converted to bytecode and interpreted using a virtual machine. Most modern programming languages have support for high-level abstractions while the instructions of a virtual machine are closer to the machine language
instructions supported by hardware architectures, making the interpretation of bytecode easier than interpretation of the original source program. The advantage of virtual machine implementations results from dividing the mapping from high-level abstractions to low-level machine instructions into two parts: high-level abstractions to bytecode and bytecode to machine instructions.

While bytecode is a higher level abstraction than machine language, it is not greatly so. As programmers, if we understand how the underlying machine executes our
programs, we better equip ourselves to make good choices about how we program. Just as importantly, having an understanding of how programs are executed can help us diagnose problems when things go wrong.

This chapter introduces assembly language programming in the bytecode language of the Python virtual machine. The Python virtual machine is an internal component of the Python interpreter and is not available to use directly. Instead, a bytecode interpreter called CoCo has been developed that mimics a subset of the behavior of the Python 3.2 virtual machine. Instead of writing bytecode files directly, CoCo supports a Python virtual machine assembly language.

While learning assembly language, we’ll limit ourselves to a subset of Python. CoCo supports boolean values, integers, strings, floats, tuples, and lists. It supports functions definitions and function calls. It also supports most of the instructions of the Python virtual machine including support for conditional execution, iteration, and exception handling. It does not support importing modules or module level code. CoCo differs from Python by requiring a main function where execution of a CoCo assembled program begins.


… It is also used in systems programming for operating systems development for IBM business computers, Linux, Mac OS X, and Microsoft Windows. C or C++ is used as the implementation language for many virtual machines including the Java Virtual Machine, Python, and as it turns out CoCo. C++ is used in massively parallel programs that solve problems by dividing work between many processors using libraries like Message Passing Interface (MPI).

Why is C++ so popular? C++ is an object-oriented, imperative programming language that supports static type checking, separate compilation, low-level programming that can get right down to the hardware level, high-level abstraction with classes, generics in the form of templates, inheritance, and polymorphism. C++ gives the programmer the ultimate control over his or her environment allowing the creation of objects in either the run-time stack or on the heap. C++ is a flexible language that can be used in many different ways.

With much power comes great responsibility as the saying goes. To use C++ correctly you need to understand how the code you write gets executed including the model that is used for executing C++ programs. It is said that if you learn to program in C++ you can program in any language. That statement should probably be amended just a bit: If you learn to program well in C++ then you can learn to program well in any language. Understanding the computational model used by C++ goes a long ways towards becoming a great C++ programmer. That’s probably the best place to start, with the model used by C++ programs as they execute.

Standard ML

This chapter introduces functional programming. Functional languages, like Standard ML, obviously concentrate more heavily on writing and calling functions. However, the term functional programming doesn’t say what functional programming languages lack. Specifically, pure functional languages lack assignment statements and iteration. Iteration relates to the ability to iterate or repeat code as in a loop of some sort. It is impossible in a pure functional language to declare a variable that gets updated as your program executes! If you think about it, if there are no variables, then there isn’t any reason for a looping construct in the language. Iteration and variables
go hand in hand. But, how do you get any work done without variables? The primary mode of programming in a functional language is through recursion.