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. These three styles of
programming are:
-
Imperative/Object-Oriented Programming with languages like Java, C++, Python, and other languages you may have used before.
-
Functional Programming with languages like Standard ML, Haskell, Lisp, Scheme, and others.
-
Logic Programming with Prolog.
The book provides an in-depth look at
programming in assembly language, Java, 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.
To begin you should know something
about the history of computing, particularly as it applies to the
models of computation that have been used in implementing many of
the programming languages we use today. All of what we know in
Computer Science is built on the shoulders of those who came before
us. To understand where we are, we really should know something
about where we came from in terms of Computer Science. Many great
people have been involved in the development of programming
languages and to learn even a little about who these people are is
really fascinating and worthy of an entire book in itself.
Fig.
1.1
Sophus Lie [21]
1.1 Historical Perspective
Much of what we attribute to Computer
Science actually came from Mathematics. Many mathematicians are
programmers that have written their programs, or proofs in the
words of Mathematics, using mathematical notation. In the mid 1800s
abstract algebra and geometry were hot topics of research among
mathematicians. In the early 1800s Niels Henrik Abel, a Norwegian
mathematician, was interested in solving a problem called the
quintic equation. Eventually he developed a new branch of
mathematics called Group Theory with which he was able to prove
there was no general algebraic solution to the quintic equation.
Considering the proof of this required a new branch of mathematics,
much of Abel’s work involved developing the mathematical notation
or language to describe his work. Unfortunately, Abel died of
tuberculosis at twenty six years old.
Sophus Lie (pronounced Lee), pictured in
Fig. 1.1,
was another Norwegian mathematician who lived from 1842–1899 [20].
He began where Abel’s research ended and explored the connection of
Abstract Algebra and Group Theory with Geometry. From this work he
developed a set of group theories, eventually named Lie Groups.
From this discovery he found ways of solving Ordinary Differential
Equations by exploiting properties of symmetry within the equations
[8]. One Lie group, the 
group was too complicated to map in Lie’s time. In
fact, it wasn’t until 2007 that the structure of the 
group could
be mapped because the solution produced sixty times more data than
the human genome project [1].
group was too complicated to map in Lie’s time. In
fact, it wasn’t until 2007 that the structure of the group could
be mapped because the solution produced sixty times more data than
the human genome project [1].While the techniques Lie and Abel
discovered were hard for people to learn and use at the time, today
computer programs capable of symbolic manipulation use Lie’s
techniques to solve these and other equally complicated problems.
And, the solutions of these problems are very relevant in the world
today. For example, the work of Sophus Lie is used in the design of
aircraft.
As mathematicians’ problem solving
techniques became more sophisticated and the problems they were
solving became more complex, they were interested in finding
automated ways of solving these problems. Charles Babbage
(1791–1871) saw the need for a computer to do calculations that
were too error-prone for humans to perform. He designed a
difference engine to
compute mathematical tables when he found that human computers weren’t very accurate [27].
However, his computer was mechanical and couldn’t be built using
engineering techniques known at that time. In fact it wasn’t
completed until 1990, but it worked just as he said it would over a
hundred years earlier.
Charles Babbage’s
difference engine was an early attempt at automating a solution to
a problem, but others would follow of course. Alan Turing was a
British mathematician and one of the first computer scientists. He
lived from 1912–1954. In 1936 he wrote a paper entitled, “On
Computable Numbers, with an Application to the
Entscheidungsproblem” [23]. The Entscheidungsproblem, or decision
problem, had been proposed a decade earlier by a German
mathematician named David Hilbert. This problem asks: Can an
algorithm be defined that decides if a statement given in first
order logic can be proved from a set of axioms and known truth
values? The problem was later generalized to the following
question: Can we come up with a general set of steps that given any
algorithm and its data, will decide if it terminates? In Alan
Turing’s paper, he devised an abstract machine called the Turing
Machine. This Turing Machine was very general and simple. It
consisted of a set of states and a tape. The set of states were
decided on by a programmer. The machine starts in the start state
as decided by the programmer. From that state it could read a
symbol from a tape. Based on the symbol it could write a symbol to
the tape and move to the left or right, while transitioning to
another state. As the Turing machine ran, the action that it took
was dictated by the current state and the symbol on the tape. The
programmer got to decide how many states were a part of the
machine, what each state should do, and how to move from one state
to another. In Turing’s paper he proved that such a machine could
be used to solve any computable function and that the decision
problem was not solvable by this machine. The more general
statement of this problem was named the Halting Problem. This was a very
important result in the field of theoretical Computer
Science.
In 1939 John
Atanasoff, at Iowa State University, designed what is arguably the
first computer, the ABC or Atanasoff-Berry Computer [28]. Clifford
Berry was one of his graduate students. The computer had no central
processing unit, but it did perform logical and other mathematical
operations. Eckert and Mauchly, at the University of Pennsylvania,
were interested in building a computer during the second world war.
They were funded by the Department of Defense to build a machine to
calculate trajectory tables for launching shells from ships. The
computer, called ENIAC for Electronic Numerical Integrator and
Computer, was unveiled in 1946, just after the war had ended. ENIAC
was difficult to program since the program was written by plugging cables into a
switch, similar to an old telephone switchboard.
Around that same time a new computer,
called EDVAC, was being designed. In 1945 John von Neumann proposed
storing the computer programs on EDVAC in memory along with the
program data [26]. Alan Turing closely followed John von Neumann’s
paper by publishing a paper of his own in 1946 describing a more
complete design for stored-program computers [24]. To this day the
computers we build and use are stored-program computers. The
architecture is called the von Neumann architecture because of John
von Neumann’s and Alan Turing’s contributions. While Turing didn’t
get the architecture named after him, he is famous in Computer
Science for other reasons like the Turing machine and the Halting
problem.
Fig.
1.2
John Backus [3]
In the early days of Computer Science,
many programmers were interested in writing tools that made it
easier to program computers. Much of the programming was based on
the concept of a stored-program computer and many early programming
languages were extensions of this model of computation. In the
stored-program model the program and data are stored in memory. The
program manipulates data based on some input. It then produces
output.
Around 1958, Algol was created and the
second revision of this language, called Algol 60, was the first
modern, structured, imperative programming language. While the
language was designed by a committee, a large part of the success
of the project was due to the contributions of John Backus pictured
in Fig. 1.2. He described the structure of the Algol
language using a mathematical notation that would later be called
Backus-Naur Format or BNF. Very little has changed with the
underlying computer architecture over the years. Of course, there
have been many changes in the size, speed, and cost of computers!
In addition, the languages we use have become even more structured
over the years. But, the principles that Algol 60 introduced are
still in use today.
Fig.
1.3
John McCarthy [14]
Recalling that most early computer
scientists were mathematicians, it shouldn’t be too surprising to
learn that there were others that approached the problem of
programming differently. Much of the initial interest in computers
was spurred by the invention of the stored-program computer and
many of the early languages reflected this excitement. The
imperative style was closely tied to the architecture of a stored
program computer. Data was read from an input device and the
program acted on that data by updating memory as the program
executed. There was another approach developing at the same time.
Back in 1936, Alonzo Church, a U.S. mathematician who lived from
1903–1995, was also interested in the decision problem proposed by
David Hilbert. To try to solve the problem he devised a language
called the lambda calculus, usually written as the 
-calculus. Using his very simple language he
was able to describe computation as symbol manipulation. Alan
Turing was a doctoral student of Church and while they
independently came up with two ways to prove that the decision
problem was not solvable, they later proved their two models of
computation, Turing machines and the 
-calculus, were equivalent. Their work
eventually led to a very important result called the Church-Turing
Thesis. Informally, the thesis states that all computable problems
can be solved by a Turing Machine or the 
-calculus. The two models are equivalent in
power.
-calculus. Using his very simple language he
was able to describe computation as symbol manipulation. Alan
Turing was a doctoral student of Church and while they
independently came up with two ways to prove that the decision
problem was not solvable, they later proved their two models of
computation, Turing machines and the -calculus, were equivalent. Their work
eventually led to a very important result called the Church-Turing
Thesis. Informally, the thesis states that all computable problems
can be solved by a Turing Machine or the -calculus. The two models are equivalent in
power.Ideas from the 
-calculus led to the development of Lisp by
John McCarthy, pictured in Fig. 1.3. The 
-calculus and Lisp were not designed based on
the principle of the stored-program computer. In contrast to Algol
60, the focus of these languages was on functions and what could be
computed using functions. Lisp was developed around 1958, the same
time that Algol 60 was being developed.
-calculus led to the development of Lisp by
John McCarthy, pictured in Fig. 1.3. The -calculus and Lisp were not designed based on
the principle of the stored-program computer. In contrast to Algol
60, the focus of these languages was on functions and what could be
computed using functions. Lisp was developed around 1958, the same
time that Algol 60 was being developed.Logic is important both in Computer
Science and Mathematics. Logicians were also interested in solving
problems in the early days of Computer Science. Many problems in
logic are expressed in the languages of propositional or predicate
logic. Of course, the development of logic goes all the way back to
ancient Greece. Some logicians of the 20th century were interested
in understanding natural language and they were looking for a way
to use computers to solve at least some of the problems related to
processing natural language statements. The desire to use computers
in solving problems from logic led to the development of Prolog, a
powerful programming language based on predicate logic.
Practice 1.1
Find the answers to the following
questions.
- 1.
What are the origins of the three major computational models that early computer scientists developed?
- 2.
Who were Alan Turing and Alonzo Church and what were some of their contributions to Computer Science?
- 3.
What idea did both John von Neumann and Alan Turing contribute to?
- 4.
What notation did John Backus develop and what was one of its first uses?
- 5.
What year did Alan Turing first propose the Turing machine and why?
- 6.
What year did Alonzo Church first propose the
-calculus and why? - 7.
Why are Eckert and Mauchly famous?
- 8.
Why are the history of Mathematics and Computer Science so closely tied together?
1.2 Models of Computation
While there is some controversy about
who originally came up with the concept of a stored program
computer, John von Neumann is generally given credit for the idea
of storing a program as a string of 0’s and 1’s in memory along
with the data used by the program. Von Neumann’s architecture had
very little structure to it. It consisted of several registers and
memory. The Program Counter (PC) register kept track of the next
instruction to execute. There were other registers that could hold
a value or point to other values stored in memory. This model of
computation was useful when programs were small. However, without
additional structure, anything but a small program would quickly
get hard to manage. This was what was driving the need for better
and newer programming languages. Programmers needed tools that let
them organize their code so they could focus on problem solving
instead of the details of the hardware.
1.2.1 The Imperative Model
As programs grew in size it was
necessary to provide the means for applying additional structure to
them. In the early days a function was often called a sub-routine.
Functions, procedures, and sub-routines were introduced by
languages like Algol 60 so that programs could be decomposed into
simpler sub-programs, providing a way for programmers to organize
their code. Terms like top-down or bottom-up design were used to
describe this process of subdividing programs into simpler
sub-programs. This process of subdividing programs was often called
structured programming,
referring to the decomposition of programs into simpler, more
manageable pieces. Most modern languages provide the means to
decompose problems into simpler subproblems. We often refer to this
structured approach as the imperative model of programming.
Fig.
1.4
Imperative model
To implement functions and function
calls in the von Neumann architecture, it was necessary to apply
some organization to the data of a program. In the imperative
model, memory is divided into regions which hold the program and
the data. The data area is further subdivided into the static or
global data area, the run-time stack, and the heap as pictured in
Fig. 1.4.
In the late 1970s and 1980s people
like Niklaus Wirth and Bjarne Stroustrup were interested in
developing languages that supported an additional level of
organization called Object-Oriented Programming, often abbreviated
OOP. Object-oriented programming still uses the imperative model of
programming. The addition of a means to describe classes of objects
gives programmers another way of organizing their code into
functions that are related to a particular type of object.
When a program executes it uses a
special register called the stack pointer (SP) to point to the top
activation record on the run-time stack. The run-time stack
contains one activation record for each function or procedure
invocation that is currently unfinished in the program. The top
activation record corresponds to the current function invocation.
When a function call is made an activation record is pushed onto
the run-time stack. When a function returns, the activation record
is popped by decrementing the stack pointer to point to the
previous activation record.
An activation record contains
information about its associated function. The local variables of
the function are stored there. The program counter’s value before
the function call was made is stored there. This is often called
the return address. Other state information may also be stored
there depending on the language and the details of the underlying
von Neumann architecture. For instance, parameters passed to the
function may also be stored there.
Static or global data refers to data
and functions that are accessible globally in the program. Global
data and functions are visible throughout the program. Where global
data is stored depends on the implementation of the compiler or
interpreter. It might be part of the program code in some
instances. In any case, this area is where constants, global
variables, and possibly built-in globally accessible functions are
stored.
The heap is an area for dynamic memory
allocation. The word dynamic means that it happens while the
program is running. All data that is created at run-time is located
in the heap. The data in the heap has no names associated with the
values stored there. Instead, named variables called pointers or
references point to the data in the heap. In addition, data in the
heap may contain pointers that point to other data, which is also
usually in the heap.
Like the original von Neumann
architecture, the primary goal of the imperative model is to get
data as input, transform it via updates to memory, and then produce
output based on this imperatively changed data. The imperative
model of computation parallels the underlying von Neumann
architecture and is used by many modern languages. Some variation
of this model is used by languages like Algol 60, C++, C, Java,
VB.net, Python, and many other languages.
Practice 1.2
Find the answers to the following
questions.
- 1.
What are the three divisions of data memory called?
- 2.
When does an item in the heap get created?
- 3.
What goes in an activation record?
- 4.
When is an activation record created?
- 5.
When is an activation record deleted?
- 6.
What is the primary goal of imperative, object-oriented programming?
1.2.2 The Functional Model
In the functional model the goal of a
program is slightly different. This slight change in the way the
model works has a big influence on how you program. In the
functional model of computation the focus is on function calls.
Functions and parameter passing are the primary means of
accomplishing data transformation.
Data is generally not changed in the
functional model. Instead, new values are constructed from old
values. A pure functional model wouldn’t allow any updates to
existing values. However, most functional languages allow limited
updates to memory in the imperative style.
The conceptual view presented in
Fig. 1.4
is similar to the view in the functional world. However, the
difference between program and data is eliminated. A function is
data like any other data element. Integers and functions are both
first-class citizens of the functional world.
The static data area is still present,
but takes on a minor role in the functional model. The run-time
stack becomes more important because most work is accomplished by
calling functions. Functional languages are much more careful about
how they allow programmers to access the heap and as a result, you
really aren’t aware of the heap when programming in a functional
language. Data is certainly dynamically allocated, but once data is
created on the heap it is not modified in a pure functional model.
Impure models might allow some modification of storage but this is
the influence of imperative languages creeping into the functional
model as a way to deal with performance issues. The result is that
you spend less time thinking about the underlying architecture when
programming in a functional language.
Lisp, Scheme, Scala, Clojure, Elixir,
Haskell, Caml, and Standard ML, which is covered in this text, are
all examples of functional languages. Functional languages may be
pure, which means they do not support variable updates like the
imperative model. Scheme is a pure functional language. Most
functional languages are not pure. Standard ML and Lisp are
examples of impure functional languages. Scala is a recent
functional language that also supports object-oriented
programming.
Practice 1.3
Answer the following questions.
- 1.
What are some examples of functional languages?
- 2.
What is the primary difference between the functional and imperative models?
- 3.
Immutable data is data that cannot be changed once created. The presence of immutable data simplifies the conceptual model of programming. Does the imperative or functional model emphasize immutable data?
1.2.3 The Logic Model
The logic model of computation,
pictured in Fig. 1.5, is quite different from either the
imperative or functional model. In the logic model the programmer
doesn’t actually write a program at all. Instead, the programmer
provides a database of facts or rules. From this database, a single
program tries to answer questions with a yes or no answer. In the
case of Prolog, the program acts in a predictable manner allowing
the programmer to provide the facts in an order that determines how
the program will work. The actual implementation of this conceptual
view is accomplished by a virtual machine, a technique for
implementing languages that is covered later in this text.
Fig.
1.5
Logic model of computation
There is still the concept of a heap
in Prolog. One can assert new rules and retract rules as the
program executes. To dynamically add rules or retract them there
must be an underlying heap. In fact, the run-time stack is there
too. However, the run-time stack and heap are so hidden in this
view of the world that it is debatable whether they should appear
in the conceptual model at all.
Practice 1.4
Answer these questions on what you
just read.
- 1.
How many programs can you write in a logic programming language like Prolog?
- 2.
What does the programmer do when writing in Prolog?
1.3 The Origins of a Few Programming Languages
This book explores language
implementation using several small languages and exercises that
illustrate each of these models of computation. In addition,
exercises within the text will require implementation in four
different languages: assembly language, Java (or alternatively
C++), Standard ML, and Prolog. But where did these languages come
from and why are we interested in learning how to use them?
Fig.
1.6
Bjarne Stroustrup [18]
1.3.1 A Brief History of C and C++
The Unix operating system was
conceived of, designed, and written around 1972. Ken Thompson was
working on the design of Unix with Dennis Ritchie. It was their
project that encouraged Ritchie to create the C language. C was
more structured than the assembly language most operating systems
were written in at the time and it was portable and could be
compiled to efficient machine code. Thompson and Ritchie wanted an
operating system that was portable, small, and well
organized.
While C was efficient, there were
other languages that had either been developed or were being
developed that encouraged a more structured approach to
programming. For several years there had been ideas floating around
about how to write code in object-oriented form. Simula, created by
Ole-Johan Dahl and Kristen Nygaard around 1967, was an early
example of a language that supported Object-Oriented design.
Modula-2, created by Niklaus Wirth around 1978, was also taking
advantage of these ideas. Smalltalk, an interpreted language, was
object-oriented and was also developed in the mid 1970s and
released in 1980.
In 1980 Bjarne Stroustrup, pictured in
Fig. 1.6,
began working on the design of C++ while working at Bell Labs. He
envisioned C++ as a language that would allow C programmers to keep
their old code while new code could be written using these
Object-Oriented concepts. In 1983 he named this new language C++,
as in the next increment of C, and with much anticipation, in 1985
the language was released. About the same time Dr. Stroustrup
released a book called The C++
Programming Language [19], which described the language. The
language is still evolving. For instance, templates, an important
part of C++ were first described by Stroustrup in 1988 [17] and it
wasn’t until 1998 that it was standardized as ANSI C++. Today an
ANSI committee oversees the continued development of C++. The
latest C++ standard was released in 2014 as of this writing. The
previous standard was released in 2011. C++ is a mature language,
but is still growing and evolving. The 2017 standard is currently
in the works with comments presently being solicited by the
standards committee.
1.3.2 A Brief History of Java
C++ is a very powerful language, but
also demands that programmers be very careful when writing code.
The biggest problem with C++ programs are memory leaks. When
objects are created on the heap in C++, they remain on the heap
until they are freed. If a programmer forgets to free an object,
then that space cannot be re-used while the program is running.
That space is gone until the program is stopped, even if no code
has a pointer to that object anymore. This is a memory leak. And,
for long-running C++ programs it is the number one problem.
Destructors are a feature of C++ that help programmers prevent
memory leaks. Depending on the structure of a class in your
program, it may need a destructor to take care of cleaning up
instances of itself (i.e. objects of the class) when they are
freed.
C++ programs can create objects in the
run-time stack, on the heap, or within other objects. This is
another powerful feature of C++. But, with this power over the
creation of objects comes more responsibility for the programmer.
This control over object creation leads to the need for extra code
to decide how copies of objects are made. In C++ every class may
contain a copy constructor so the programmer can control how copies
of objects are made.
In 1991 a team called the Green Team, was working for a company
named Sun Microsystems.
This group of software engineers wanted to design a programming
language and run-time system that could be used in the next
generation of personal devices. The group was led by a man named
James Gosling. To support their vision, they designed the Java
Virtual Machine (i.e. JVM), a program that would interpret byte
code files. The JVM was designed as the run-time system for the
Java programming language. Java programs, when compiled, are
translated into bytecode files that run on the JVM.
The year 1995 brought the birth of the
world wide web and with it one of the first web browsers, Netscape
Navigator, which later became Mozilla Firefox. In 1995 it was
announced that Netscape would include Java technology within the
browser. This led to some of the initial interest in the language,
but the language has grown way beyond web browsers. In fact, Java
is not really a web browser technology anymore. It is used in many
web backends, where Java programs wait for connections from web
browsers, but it doesn’t run programs within web browsers much
these days. Another language, Javascript, is now the primary
language of web browsers. Javascript is similar to Java in name,
but not its technology. Javascript was licensed as a name from Sun
Microsystems in its early days because of the popularity of
Java [22].
The original intention of Java was to
serve as a means for running software for personal devices. Java
has become very important in that respect. It now is the basis for
the Android operating system that runs on many phones and other
personal devices like tablets. So, in a sense, the original goal of
the Green Team has been realized, just fifteen or so years
later.
When the original Green Team was
designing Java they wanted to take the best of C++ while leaving
behind some of its complexity. In Java objects can only be created
in one location, on the heap. Sticking to one and only one memory
model for objects simplifies many aspects of Java. Objects are
never copied by the language. So, copy constructors are unnecessary
in Java. When an object is passed to a function, a reference to an
object is passed without making a copy of the object. When one
object wants to contain another object, it keeps a reference to
that object. Java objects are never stored inside other objects.
Simplifying the memory model for objects means that in Java
programs we don’t have to worry about copying objects.
Objects can still
be copied in Java, but making copies of objects is the
responsibility of the programmer. The Java language does not make
copies. Programmers make copies by calling a special method called
clone.
Java also includes garbage collection.
This means that the Java Virtual Machine takes care of deciding
when the space that an object resides in can be reclaimed. It can
be reclaimed when no other objects or code have a reference to it
anymore. This means that programmers don’t have to write
destructors. The JVM manages this for them.
So, while C++ and Java share a lot of
syntax, there are many differences as well. Java has a simpler
memory model. Garbage collection removes the fear of memory leaks
in Java programs. The Java Virtual Machine also provides other
advantages to writing Java programs. This does not make C++ a bad
language by any means. It’s just that Java and C++ have different
goals. The JVM and Java manage a lot of the complexity of writing
object-oriented programs, freeing the programmer from these duties.
C++ on the other hand, gives you the power to manage all the
details of a program, right down to the hardware interface. Neither
is better than the other, they just serve different purposes while
the two languages also share a lot of the same syntax.
Fig.
1.7
Guido van Rossum [25]
1.3.3 A Brief History of Python
Python was designed and implemented by
Guido van Rossum, pictured in Fig. 1.7. He started Python as
a hobby project during the winter months of 1989. A more complete
history of this language is available on the web at http://python-history.blogspot.com.
Python is another object-oriented language like C++ and Java.
Unlike C++, Python is an interpreted language. Mr. van Rossum
designed Python’s interpreter as a virtual machine, like the Java
Virtual Machine (i.e. JVM). But Python’s virtual machine is not
accessible separately, unlike the JVM. The Python virtual machine
is an internal implementation detail of the Python interpreter.
Virtual machines have been around for some time including an
operating system for IBM mainframe computers, called VM. Using a
virtual machine when implementing a programming language can make
the language and its programs more portable across platforms.
Python runs on many different platforms like Apple’s Mac OS X,
Linux, and Microsoft Windows. Virtual machines can also provide
services that make language implementation easier.
Programmers world-wide have embraced
Python and have developed many libraries for Python and written
many programs. Python has gained popularity among developers
because of its portability and the ability to provide libraries to
others. Guido van Rossum states in his history of Python, “A large
complex system should have multiple levels of extensibility. This
maximizes the opportunities for users, sophisticated or not, to
help themselves.” Extensibility refers to the ability to define
libraries of classes to solve problems from many different
application areas. Python is used in internet programming, server
scripting, computer graphics, visualization, Mathematics, Computer
Science education, and many, many other application areas.
Mr. van Rossum continues, saying “In
many ways, the design philosophy I used when creating Python is
probably one of the main reasons for its ultimate success. Rather
than striving for perfection, early adopters found that Python
worked “well enough” for their purposes. As the user-base grew,
suggestions for improvement were gradually incorporated into the
language.” Growing the user-base has been key to the success of
Python. As the number of programmers that know Python has increased
so has interest in improving the language. Python now has two major
versions, Python 2 and Python 3. Python 3 is not backward
compatible with Python 2. This break in compatibility gave the
Python developers an opportunity to make improvements in the
language. Chapters 3 and 4 cover some of the implementation
details of the Python programming language.
1.3.4 A Brief History of Standard ML
Standard ML originated in 1986, but
was the follow-on of ML which originated in 1973 [16]. Like many
other languages, ML was implemented for a specific purpose. The ML
stands for Meta Language. Meta means above or about. So a
metalanguage is a language about language. In other words, a
language used to describe a language. ML was originally designed
for a theorem proving system. The theorem prover was called LCF,
which stands for Logic for Computable Functions. The LCF theorem
prover was developed to check proofs constructed in a particular
type of logic first proposed by Dana Scott in 1969 and now called
Scott Logic. Robin Milner, pictured in Fig. 1.8, was the principal
designer of the LCF system. Milner designed the first version of
LCF while at Stanford University. In 1973, Milner moved to
Edinburgh University and hired Lockwood Morris and Malcolm Newey,
followed by Michael Gordon and Christopher Wadsworth, as research
associates to help him build a new and better version called
Edinburgh LCF [9].
Fig.
1.8
Robin Milner [15]
For the Edinburgh version of LCF, Dr.
Milner and his associates created the ML programming language to
allow proof commands in the new LCF system to be extended and
customized. ML was just one part of the LCF system. However, it
quickly became clear that ML could be useful as a general purpose
programming language. In 1990 Milner, together with Mads Tofte and
Robert Harper, published the first complete formal definition of
the language; joined by David MacQueen, they revised this standard
to produce the Standard ML that exists today [16].
ML was influenced by Lisp, Algol, and
the Pascal programming languages. In fact, ML was originally
implemented in Lisp. There are now two main versions of ML: Moscow
ML and Standard ML. Today, ML’s main use is in academia in the
research of programming languages. But, it has been used
successfully in several other types of applications including the
implementation of the TCP/IP protocol stack [4] and a web server as
part of the Fox Project. A goal of the Fox Project was the
development of system software using advanced programming languages
[10].
ML is a very good language to use in
learning to implement other languages. It includes tools for
automatically generating parts of a language implementation
including components called a scanner and a parser which are
introduced in Chap. 6. These tools, along with the
polymorphic strong type checking provided by Standard ML, make
implementing a compiler or interpreter a much easier task. Much of
the work of implementing a program in Standard ML is spent in
making sure all the types in the program are correct. This strong
type checking often means that once a program is properly typed it
will run the first time. This is quite a statement to make, but
nonetheless it is often true.
Important Standard ML features
include:
-
ML is higher-order supporting functions as first-class values. This means functions may be passed as parameters to functions and returned as values from functions.
-
Strong type checking (discussed later in this chapter) means it is pretty infrequent that you need to debug your code. What a great thing!
-
Pattern-matching is used in the specification of functions in ML. Pattern-matching is convenient for writing recursive functions.
-
The exception handling system implemented by Standard ML has been proven type safe, meaning that the type system encompasses all possible paths of execution in an ML program.
1.3.5 A Brief History of Prolog
Prolog was developed in 1972 by Alain
Colmerauer, pictured in Fig. 1.9, with Philippe
Roussel. Colmerauer and Roussel and their research group had been
working on natural language processing for the French language and
were studying logic and automated theorem proving [7] to answer
simple questions in French. Their research led them to invite
Robert Kowalski, pictured in Fig. 1.10, who was working in
the area of logic programming and had devised an algorithm called
SL-Resolution, to work with them in the summer of 1971 [11, 29].
Colmerauer and Kowalski, while working together in 1971, discovered
a way formal grammars could be written as clauses in predicate
logic. Colmerauer soon devised a way that logic predicates could be
used to express grammars that would allow automated theorem provers
to parse natural language sentences efficiently. This is covered in
some detail in Chap. 7.
Fig.
1.9
Alain Colmerauer [6]
Fig.
1.10
Robert Kowalski [12]
In the summer of 1972, Kowalski and
Colmerauer worked together again and Kowalski was able to describe
the procedural interpretation of what are known as Horn Clauses.
Much of the debate at the time revolved around whether logic
programming should focus on procedural representations or
declarative representations. The work of Kowalski showed how logic
programs could have a dual meaning, both procedural and
declarative.
Colmerauer and Roussel used this idea
of logic programs being both declarative and procedural to devise
Prolog in the summer and fall of 1972. The first large Prolog
program, which implemented a question and answering system in the
French language, was written in 1972 as well.
Later, the Prolog language interpreter
was rewritten at Edinburgh to compile programs into DEC-10 machine
code. This led to an abstract intermediate form that is now known
as the Warren Abstract Machine or WAM. WAM is a low-level
intermediate representation that is well-suited for representing
Prolog programs. The WAM virtual machine can be (and has been)
implemented on a wide variety of hardware. This means that Prolog
implementations exist for most computing platforms.
Practice 1.5
Answer the following questions.
- 1.
Who invented C++? C? Standard ML? Prolog? Python? Java?
- 2.
What do Standard ML and Prolog’s histories have in common?
- 3.
What do Prolog and Python have in common?
- 4.
What language or languages is Standard ML based on?
1.4 Language Implementation
There are three ways that languages
can be implemented.
-
A language can be interpreted.
-
A language can be compiled to a machine language.
-
A language can be implemented by some combination of the first two methods.
Fig.
1.11
Language implementation
Computers are only capable of
executing machine language. Machine language is the language of the
Central Processing Unit (CPU) and is very simple. For instance,
typical instructions are fetch
this value into the CPU, store this value into memory from the
CPU, add these two values
together, and compare these
two values and if they are equal, jump here next. The goal
of any programming language implementation is to translate a source
program into this simpler machine language so it can be executed by
the CPU. The overall process is pictured in Fig. 1.11.
All language implementations
translate a source program to some intermediate representation
before translating the intermediate representation to machine
language. Exactly how these two translations are packaged varies
significantly from one programming language to the next, but
luckily most language implementations follow one of a few
methodologies. The following sections will present some case
studies of different languages so you can see how this translation
is accomplished and packaged.
1.4.1 Compilation
The most direct method of translating
a program to machine language is called compilation. The process is
shown in Fig. 1.12. A compiler is a program that internally
is composed of several parts. The parser reads a source program and
translates it into an intermediate form called an abstract syntax
tree (AST). An AST is a tree-like data structure that
internally represents the source program. We’ll read about abstract
syntax trees in later chapters. The code generator then traverses the AST
and produces another intermediate form called an assembly language
program. This program is not machine language, but it is much
closer. Finally, an assembler and linker translate an assembly language
program to machine language making the program ready to execute.
Fig.
1.12
The compilation process
This whole
process is encapsulated by a tool called a compiler. In most instances, the
assembler and linker are separate from the compiler, but normally
the compiler runs the assembler and linker automatically when a
program is compiled so as programmers we tend to think of a
compiler compiling our programs and don’t necessarily think about
the assembly and link phases.
Programming in a compiled language is
a three-step process.
-
First, you write a source program.
-
Then you compile the source program, producing an executable program.
-
Then you run the executable program.
When you are done, you have a source
program and an executable program that represent the same
computation, one in the source language, the other in machine
language. If you make further changes to the source program, the
source program and the machine language program are not in sync.
After making changes to the source program you must remember to
recompile before running the executable program again.
Machine language is specific to a CPU
architecture and operating system. Compiling a source program on
Linux means it will run on most Linux machines with a similar CPU.
However, you cannot take a Linux executable and put it on a
Microsoft Windows machine and expect it to run, even if the two
computers have the same CPU. The Linux and Windows operating
systems each have their own format for executable machine language
programs. In addition, compiled programs use operating system
services for printing, reading input, and doing other Input/Output
(I/O) operations. These services are invoked differently between
operating systems. Languages like C++ hide these implementation
details from you in the code generator, but the end result is that
a program compiled for one operating system will not work on
another operating system without being recompiled.
C, C++, Pascal, Fortran, COBOL and
many others are typically compiled languages. On the Linux
operating system the C compiler is called gcc and the C++ compiler is called
g++. The g in both names reflects the fact that
both compilers come out of the GNU project and the Free Software
Foundation. Linux, gcc, and g++ are freely available to anyone who
wants to download them. The best way to get these tools is to
download a Linux distribution and install it on a computer. The
gcc and g++ compilers come standard with
Linux.
There are implementations of C and
C++ for many other platforms. The web site http://gcc.gnu.org contains links
to source code and to prebuilt binaries for the g++ compiler. You
can also download C++ compilers from Apple and Microsoft. For Mac
OS X computers you can get C++ by downloading the XCode Developer
Tools. You can also install g++ and gcc for Mac OS X computers
using a tool called brew.
If you run Microsoft Windows you can install Visual C++ Express
from Microsoft. It is free for educational use.
1.4.2 Interpretation
An interpreter is a program that is
written in some other language and compiled into machine language.
The interpreter itself is the machine language program. The
interpreter itself is written to read source programs from the
interpreted language and interpret them. For instance, Python is an
interpreted language. The Python interpreter is written in C and is
compiled for a particular platform like Linux, Mac OS X, or
Microsoft Windows. To run a Python program, you must download and
install the Python interpreter that goes with your operating system
and CPU.
When you run an interpreted source
program, as depicted in Fig. 1.13, you are actually
running the interpreter. Your program is not running because your
program is never translated to machine language. The interpreter is
the machine language program that executes all the programs you
write in the interpreted language. The source program you write
controls the behavior of the interpreter program.
Fig.
1.13
The interpretation process
Programming in an interpreted
language is a two step process.
-
First you write a source program.
-
Then you execute the source program by running the interpreter.
Each time your program is executed it
is translated into an AST by a part of the interpreter called the
parser. There may be an additional step that translates the AST to
some lower-level representation, often called bytecode. In an
interpreter, this lower-level representation is still internal to
the interpreter program. Then a part of the interpreter, often
called a virtual machine, executes the byte code
instructions.
Not every interpreter translates the
AST to bytecode. Sometimes the interpreter directly interprets the
AST but it is often convenient to translate the source program’s
AST to some simpler representation before executing it.
Eliminating the compile step has a
few implications.
-
Since you have one less step in development you may be encouraged to run your code more frequently during development. This is a generally a good thing and can shorten the development cycle.
-
Secondly, because you don’t have an executable version of your code, you don’t have to manage the two versions. You only have a source code program to keep track of.
-
Finally, because the source code is not platform dependent, you can usually easily move your program between platforms. The interpreter insulates your program from platform dependencies.
Of course, source programs for
compiled languages are generally platform independent too. But,
they must be recompiled to move the executable program from one
platform to another. The interpreter itself isn’t platform
independent. There must be a version of an interpreter for each
platform/language combination. So there is a Python interpreter for
Linux, another for Microsoft Windows, and yet another for Mac OS X.
Thankfully, because the Python interpreter is written in C the same
Python interpreter program can be compiled (with some small
differences) for each platform.
There are many interpreted languages
available including Python, Ruby, Standard ML, Unix scripting
languages like Bash and Csh, Prolog, and Lisp. The portability of
interpreted languages has made them very popular among programmers,
especially when writing code that needs to run across multiple
platforms.
One huge problem that has driven
research into interpreted languages is that of heap memory
management. Recall that the heap is the place where memory is
dynamically allocated. As mentioned earlier in the chapter, C and
C++ programs are notorious for having memory leaks. Every time a
C++ programmer reserves some space on the heap he/she must remember
to free that space. If they don’t free the space when they are done
with it the space will never be available again while the program
continues to execute. The heap is a big space, but if a program
runs long enough and continues to allocate and not free space,
eventually the heap will fill up and the program will terminate
abnormally. In addition, even if the program doesn’t terminate
abnormally, the performance of the system will degrade as more and
more time is spent managing the large heap space.
Most, if not
all, interpreted languages don’t require programmers to free space
on the heap. Instead, there is a special task or thread that runs
periodically as part of the interpreter to check the heap for space
that can be freed. This task is called the garbage collector. Programmers can
allocate space on the heap but don’t have to be worried about
freeing that space. For a garbage collector to work correctly,
space on the heap has to be allocated and accessed in the right
way. Many interpreted languages are designed to insure that a
garbage collector will work correctly.
The disadvantage of an interpreted
language is in speed of execution. Interpreted programs typically
run slower than compiled programs. In a compiled program, parsing
and code generation happen once when the program is compiled. When
running an interpreted program, parsing and code generation happen
each time the program is executed. In addition, if an application
has real-time dependencies then having the garbage collector
running at more or less random intervals may not be desirable. As
you’ll read in the next section some steps have been taken to
reduce the difference in execution time between compiled and
interpreted languages.
1.4.3 Virtual Machines
The advantages of interpretation over
compilation are pretty significant. It turns out that one of the
biggest advantages is the portability of programs. It’s nice to
know when you invest the time in writing a program that it will run
the same on Linux, Microsoft Windows, Mac OS X, or some other
operating system. This portability issue has driven a lot of
research into making interpreted programs run as fast as compiled
languages.
Fig.
1.14
Virtual machine implementation
As discussed earlier in this chapter,
the concept of a virtual machine has been around quite a while. A
virtual machine is a program that provides insulation from the
actual hardware and operating system of a machine while supplying a
consistent implementation of a set of low-level instructions, often
called bytecode. Figure 1.14 shows how a virtual machine sits on top of
the operating system/CPU to act as this insulator.
There is no one specification for
bytecode instructions. They are specific to the virtual machine
being defined. Python has a virtual machine buried within the
interpreter. Prolog is another interpreter that uses a virtual
machine as part of its implementation. Some languages, like Java
have taken this idea a step further. Java has a virtual machine
that executes bytecode instructions as does Python. The creators of
Java separated the virtual machine from the compiler. Instead of
storing the bytecode instructions internally as in an interpreter,
the Java compiler, called javac, compiles a Java source code
program to a bytecode file. This file is not machine language so it
cannot be executed directly on the hardware. It is a Java bytecode
file which is interpreted by the Java virtual machine, called
java in the Java set of
tools. Java bytecode files all end with a .class extension. You may have noticed
these files at some point after compiling a Java program.
Programs written using a hybrid
language like Java are compiled. However, the compiled bytecode
program is interpreted. Source programs in the language are not
interpreted directly. By adding this intermediate step the
interpreter can be smaller and faster than traditional
interpreters. Very little parsing needs to happen to read the
program and executing the program is straightforward because each
bytecode instruction usually has a simple implementation.
Languages that fall into this virtual
machine category include Java, ML, Python, C#, Visual Basic .NET,
JScript, and other .NET platform languages. You might notice that
Standard ML and Python were included as examples of interpreted
languages. Both ML and Python include interactive interpreters as
well as the ability to compile and run low-level bytecode programs.
Python bytecode files are named with a .pyc extension. Standard ML compiled
files are named with a -platform as the last part of the
compiled file name. In the case of Python and Standard ML the
virtual machine is not a separate program. Both interpreters are
written to recognize a bytecode file and execute it just like a
source program.
Java and the .NET programming
environments do not include interactive interpreters. The only way
to execute programs with these platforms is to compile the program
and then run the compiled program using the virtual machine.
Programs written for the .NET platform run under Microsoft Windows
and in some cases Linux. Microsoft submitted some of the .NET
specifications to the ISO to allow third party software companies
to develop support for .NET on other platforms. In theory all .NET
programs are portable like Java, but so far implementations of the
.NET framework are not as generally available as Java. The Java
platform has been implemented and released on all major platforms.
In fact, in November 2006 Sun, the company that created Java,
announced they were releasing the Java Virtual Machine and related
software under the GNU Public License to encourage further
development of the language and related tools. Since then the
rights to Java have now been purchased by Oracle where it continues
to be supported.
Java and .NET
language implementations maintain backwards compatibility of their
virtual machines. This means that a program compiled for an earlier
version of Java or .NET will continue to run on newer
implementations of the language’s virtual machine. In contrast,
Python’s virtual machine is regarded as an internal design issue
and does not maintain backwards compatibility. A .pyc file compiled for one version of
Python will not run on a newer version of Python. This distinction
makes Python more of an interpreted language, while Java and .NET
languages are truly virtual machine implementations.
Maintaining backwards compatibility
of the virtual machine means that programmers can distribute
application for Java and .NET implementations without releasing
their source code. .NET and Java applications can be distributed
while maintaining privacy of the source code. Since intellectual
property is an important asset of companies, the ability to
distribute programs in binary form is important. The development of
virtual machines made memory management and program portability
much easier in languages like Java, Standard ML, and the various
.NET languages while also providing a means for programmers to
distribute programs in binary format so source code could be kept
private.
1.5 Types and Type Checking
Every
programming language defines operations that can be used to
transform data. Data transformation is the fundamental operation
that is performed by all programming languages. Some programming
languages mutate data to new values. Other languages transform data
by building new values from old values. However the transformation
takes place, these data transformation operations are defined for
certain types of data. Not
every transformation operation makes sense for every type of value.
For instance, addition is an operation that makes sense for
numbers, but does not make any sense for customers. How would you
add two customers together and what would that mean?
Since
programming languages define data transformation operations, they
similarly define types to
specify which operations make sense on which types of data. Types
in programming languages include integers, booleans, real numbers
(i.e. sometimes called floating point numbers), strings, lists,
tuples, and user-defined types like customers. Transformation
operations are defined operators on these values. The plus sign
(e.g. +) often defines addition. String concatenation might also be
denoted by the plus sign. Or it might be some other symbol.
One of the jobs of a programming
language implementation is to determine which operation is meant
when, for instance, the plus sign is written in a program. Does it
mean the addition of two numbers, string concatenation, or is it an
error because you can’t add two customers together? Determining if
the plus sign makes sense in the context of its operands (i.e. the
two things being added together) is the job of a programming
language implementation. More generally, the programming language
implementation is responsible for checking that the operations
performed on its data types are defined and the programming
language is responsible for invoking the correct operation.
There are two
different times that this type checking might occur. Some
programming languages defer all type checking until the last
possible second when the program is actually executing. When the
next operation occurs, a programming language implementation may
terminate a program and report that the next operation to be
executed is not defined. This is called a dynamically typed programming
language.
Python is a dynamically typed
programming language. You don’t find out that an operation is
undefined until the operation is about to be executed. No earlier
warning is given. When the code is executed, if you try to add two
customers together, you find out that this has not been
defined.
Other
programming languages report any operation that is not defined
before the program begins execution. In this case the programming
language is statically typed. A statically typed language goes through
a step during before execution where type checking is performed to
see if the operations are defined for the given types of operands.
This type checking step is performed in languages like Java and
C++. These languages are statically typed.
An important facet of Standard ML is
the strong type checking provided by the language. The type
inference system, commonly called Hindley-Milner type inference,
statically checks the types of all expressions and operations in
the language. In addition, the type checking system is polymorphic,
meaning that it handles types that may contain type variables. The
polymorphic type checker is sound. It will never say a program is
typed correctly when it is not. Interestingly, the type checker has
also been proven complete, which means that all correctly typed
programs will indeed pass the type checker. No correctly typed
program will be rejected by the type checker. We expect soundness
out of type checkers but completeness is much harder to prove and
it has been proven for Standard ML.
There are trade-offs between
statically and dynamically typed languages. Typically there is more
overhead to programming with a statically typed language. Types in
C++ and Java must be declared so that static type checking can be
performed. But this is not always the case. Standard ML infers the
types of most values in the language without requiring the types of
its values to be declared.
Dynamically typed languages typically
require less overhead in declaring values. In Python you don’t
declare the value of any object, except through the creation of
that object. Writing
results in x referring to an integer
value. Then printing 
will result in 12 being printed because
is
determined to be a valid operation on integers at run-time, as
is
computed.
will result in 12 being printed because
is
determined to be a valid operation on integers at run-time, as
is
computed.The problem with dynamically typed
languages comes from the lateness of determining if the operation
is defined on the objects. If the operation is only determined to
be valid right before it is executed, then every single line of a
program must be tested to determine if the program is correct or
not. While static typing tells you whether operations are defined
or not before the program executes, dynamically typed languages
don’t help you with that. They only tell you that an operation is
not defined if you actually try to execute that line of code.
So, which is better, dynamically or
statically typed languages? It depends on the complexity of the
program you are writing and its size. Static typing is certainly
desirable if all other things are equal. But static typing
typically does increase the work of a programmer up front. On the
other hand, static typing is likely to decrease the amount of time
you spend testing as evidenced by the Fox Project [10] at Carnegie
Mellon.
1.6 Chapter Summary
The history of languages is
fascinating and a lot more detail is available than was covered in
this chapter. There are many great resources on the web where you
can get more information. Use Google or Wikipedia and search for
“History of your_favorite_language” as a place to begin. However,
be careful. You can’t believe everything you read on the web and
that includes Wikipedia. While the web is a great source, you
should always research your topic enough to independently verify
the information you find there.
While learning new languages and
studying programming language implementation it becomes important
to understand models of computation. A compiler translates a
high-level programming language into a lower level computation.
These low-level computations are usually expressed in terms of
machine language but not always. More important than the actual
low-level language is the model of computation. Some models are
based on register machines. Some models are based on stack
machines. Still other models may be based on something entirely
different. Chapters 3 and 4 explore stack-based virtual
machines in much more detail.
The next chapter provides the
foundations for understanding how the syntax of a language is
formally defined by a grammar. Then chapter three introduces a
Python Virtual Machine implementation called JCoCo. JCoCo is an
interpreter of Python bytecode instructions. Chapter three
introduces assembly language programming using JCoCo, providing
some insight into how programming languages are implemented.
Subsequent
chapters in the book will again look at language implementation to
better understand the languages you are learning, their strengths
and weaknesses. While learning these languages you will also be
implementing a compiler for a high level functional language called
Small which is a robust
subset of Standard ML. This will give you even more insight into
language implementation and knowledge of how to use these languages
to solve problems.
Finally, in the last two chapters of
this text, you will learn about type checking and type inference
using Prolog, a language that is well-suited to logic problems like
type inference. Learning how to use Prolog and implement a type
checker is a great way to cap off a text on programming languages
and language implementation.
A great way to summarize the rest of
this text is to see it moving from very prescriptive approaches to
programming to very descriptive approaches to programming. The word
prescriptive means that you
dwell on details, thinking very carefully about the details of what
you are writing. For instance, in a prescriptive approach you might
ask yourself, how do you set things up to invoke a particular
type of instruction? In contrast, descriptive programming relies on
programmers describing relationships between things. Functional
programming languages, to some extent, and logic programming
languages employ this descriptive approach to programming. Read on
to begin the journey from prescriptive to descriptive
programming!
1.7 Review Questions
- 1.
What are the three ways of thinking about programming, often called programming paradigms?
- 2.
Name at least one language for each of the three methods of programming described in the previous question.
- 3.
Name one person who had a great deal to do with the development of the imperative programming model. Name another who contributed to the functional model. Finally, name a person who was responsible for the development of the logic model of programming.
- 4.
What are the primary characteristics of each of the imperative, functional, and logic models?
- 5.
Who are recognized as the founders of each of the languages this text covers: Java, C++, Python, Standard ML, and Prolog?
- 6.
Name a language, other than Python, C++, or Java, that is imperative object-oriented in nature.
- 7.
Name a language besides Standard ML, that is a functional programming language.
- 8.
What other logic programming languages are there other than Prolog? You might have to get creative on this one.
- 9.
Why is compiling a program preferred over interpreting a program?
- 10.
Why is interpreting a program preferred over compiling a program?
- 11.
What benefits do virtual machine languages have over interpreted languages?
- 12.
What is a bytecode program? Name two languages that use bytecode in their implementation.
- 13.
Why are types important in a programming language?
- 14.
What does it mean for a programming language to be dynamically typed?
- 15.
What does it mean for a programming language to be statically typed?
1.8 Solutions to Practice Problems
These are solutions to the practice
problems. You should only consult these answers after you have
tried each of them for yourself first. Practice problems are meant
to help reinforce the material you have just read so make use of
them.
1.8.1 Solution to Practice Problem 1.1
- 1.
The origins of the three models are the Turing Machine, the
-calculus, and propositional and predicate
logic. - 2.
Alan Turing as a PhD student of Alonzo Church. Alan Turing developed the Turing Machine and Alonzo Church developed the
-calculus to answer prove there were
somethings that are not computable. They later proved the two
approaches were equivalent in their power to express
computation. - 3.
Both von Neumann and Turing contributed to the idea of a stored-program computer.
- 4.
Backus developed BNF notation which was used in the development of Algol 60.
- 5.
1936 was a big year for Computer Science.
- 6.
So was 1946. That was the year ENIAC was unveiled. Eckert and Mauchly designed and built ENIAC.
- 7.
The problems in Mathematics were growing complex enough that many mathematicians were developing models and languages for expressing their algorithms. This was one of the driving factors in the development of computers and Computer Science as a discipline.
1.8.2 Solution to Practice Problem 1.2
- 1.
The run-time stack, global memory, and the heap are the three divisions of data memory.
- 2.
Data on the heap is created at run-time.
- 3.
An activation record holds information like local variables, the program counter, the stack pointer, and other state information necessary for a function invocation.
- 4.
An activation record is created each time a function is called.
- 5.
An activation record is deleted when a function returns.
- 6.
The primary goal of imperative, object-oriented programming is to update memory by updating variables and/or objects as the program executes. The primary operation is memory updates.
1.8.3 Solution to Practice Problem 1.3
- 1.
Functional languages include Standard ML, Lisp, Haskell, and Scheme.
- 2.
In the imperative model the primary operation revolves around updating memory (the assignment statement). In the functional model the primary operation is function application.
- 3.
The functional model emphasizes immutable data. However, some imperative languages have some immutable data as well. For instance, Java strings are immutable.
1.8.4 Solution to Practice Problem 1.4
- 1.
You never write a program in Prolog. You write a database of rules in Prolog that tell the single Prolog program (depth first search) how to proceed.
- 2.
The programmer provides a database of facts and predicates that tell Prolog about a problem. In Prolog the programmer describes the problem instead of programming the solution.
1.8.5 Solution to Practice Problem 1.5
- 1.
C++ was invented by Bjourne Stroustrup. C was created by Dennis Ritchie. Standard ML was primarily designed by Robin Milner. Prolog was designed by Alain Colmerauer and Philippe Roussel with the assistance of Robert Kowalski. Python was created by Guido van Rossum. Java was the work of the Green team and James Gosling.
- 2.
Standard ML and Prolog were both designed as languages for automated theorem proving first. Then they became general purpose programming languages later.
- 3.
Both Python and Prolog run on virtual machine implementations. Python’s virtual machine is internal to the interpreter. Prolog’s virtual machine is called WAM (Warren Abstract Machine).
- 4.
Standard ML is influenced by Lisp, Pascal, and Algol.