Skip to main content
Top

2017 | Book

Foundations of Programming Languages

insite
SEARCH

About this book

This clearly written textbook provides an accessible introduction to the three programming paradigms of object-oriented/imperative, functional, and logic programming. Highly interactive in style, the text encourages learning through practice, offering test exercises for each topic covered. Review questions and programming projects are also presented, to help reinforce the concepts outside of the classroom. This updated and revised new edition features new material on the Java implementation of the JCoCo virtual machine.

Topics and features: includes review questions and solved practice exercises, with supplementary code and support files available from an associated website; presents an historical perspective on the models of computation used in implementing the programming languages used today; provides the foundations for understanding how the syntax of a language is formally defined by a grammar; illustrates how programs execute at the level of assembly language, through the implementation of a stack-based Python virtual machine called JCoCo and a Python disassembler; introduces object-oriented languages through examples in Java, functional programming with Standard ML, and programming using the logic language Prolog; describes a case study involving the development of a compiler for the high level functional language Small, a robust subset of Standard ML.

Undergraduate students of computer science will find this engaging textbook to be an invaluable guide to the skills and tools needed to become a better programmer. While the text assumes some background in an imperative language, and prior coverage of the basics of data structures, the hands-on approach and easy to follow writing style will enable the reader to quickly grasp the essentials of programming languages, frameworks, and architectures.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
This text on Programming Languages is intended to introduce you to new ways of thinking about programming. Typically, computer science students start out learning to program in an imperative model of programming where variables are created and updated as a program executes. There are other ways to program. As you learn to program in these new paradigms you will begin to understand that there are different ways of thinking about problem solving. Each paradigm is useful in some contexts. 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.
Kent D. Lee
Chapter 2. Syntax
Abstract
Once you’ve learned to program in one language, learning a similar programming language isn’t all that hard. But, understanding just how to write in the new language takes looking at examples or reading documentation to learn its details. In other words, you need to know the mechanics of putting a program together in the new language. Are the semicolons in the right places? Do you use begin...end or do you use curly braces (i.e. { and })? Learning how a program is put together is called learning the syntax of the language. Syntax refers to the words and symbols of a language and how to write the symbols down in some meaningful order. 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.
Kent D. Lee
Chapter 3. Assembly Language
Abstract
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.
Kent D. Lee
Chapter 4. Object-Oriented Programming
Abstract
In this chapter you’ll learn about the implementation of the JCoCo virtual machine while at the same time you’ll be introduced to the Java and C++, two statically typed object-oriented programming languages. The primary focus of the chapter is on learning advanced object-oriented programming using Java and C++. Statically typed languages, like C++ and Java, differ from dynamically typed languages like Python in the way that type errors are caught. When running a Python program a type error can occur in any branch of code. One of the big problems with Python programming is that these errors may exist until every possible path in a Python program is executed. Testing Python code takes considerable effort to ensure every possible path is executed. While thorough testing is always a good idea, these type errors may not be discovered until much later in the development cycle.
Kent D. Lee
Chapter 5. Functional Programming
Abstract
Chapter 3 introduced assembly language which was a very prescriptive language. Certain operands had to be on the operand stack before an instruction could be executed. These details had to be dealt with even though the programmer was trying to solve a bigger problem than how to execute the next instruction.
Kent D. Lee
Chapter 6. Compiling Standard ML
Abstract
The ML in the name Standard ML stands for meta-language. SML was designed as a language for describing languages when it was used as part of the Logic for Computable Functions (LCF) system (Gordon, From LCF to HOL: a short history, pp. 169–185, 2000) [9]. Two tools were designed to work with Standard ML for language implementation, ML-lex and ML-yacc.
Kent D. Lee
Chapter 7. Logic Programming
Abstract
Imperative programming languages reflect the architecture of the underlying von Neumann stored program computer: Programs update memory locations under the control of instructions.Execution is (for the most part) sequential. Sequential execution is governed by a program counter. Imperative programs are prescriptive. They dictate precisely how a result is to be computed by means of a sequence of statements to be performed by the computer. Consider this program using the Small language developed in Chap. 6.
Kent D. Lee
Chapter 8. Standard ML Type Inference
Abstract
Many language implementations, like C++ and Java, check the types of values and operations to be sure each operation is supported for the types of its operands. An important feature of Standard ML is the type inference system which is somewhat like the type checkers of C++ and Java, but a bit more powerful. A type checker checks the types written by the programmer to be sure each type declaration is consistent with the operations being performed, values being passed to functions, and the values being returned. Compilers for Java and C++ even infer the types of some expressions when polymorphic operators are used. For instance, the addition operator has multiple result types depending on the types of its operands.
Kent D. Lee
Chapter 9. Appendix A: The JCoCo Virtual Machine Specification
Abstract
JCoCo is a virtual machine which includes a built-in assembler. JCoCo executes assembly language programs by first processing the assembly language program and then executing it. The processing of the assembly language program is called assembling.
Kent D. Lee
Chapter 10. Appendix B: The Standard ML Basis Library
Abstract
Following is a subset of the Standard ML Basis Library.
Kent D. Lee
Backmatter
Metadata
Title
Foundations of Programming Languages
Author
Prof. Kent D. Lee
Copyright Year
2017
Electronic ISBN
978-3-319-70790-7
Print ISBN
978-3-319-70789-1
DOI
https://doi.org/10.1007/978-3-319-70790-7

Premium Partner