Concepts & Implementation of PLs

http://perugini.cps.udayton.edu/teaching/courses/Spring2015/cps352/index.html#lecturenotes

Programming Languages: Chapter 1: Introduction

Programming languages

Some fundamental questions

what is a language? a medium of communication
what is a program? a set of instructions which a computer understands and follows
what is a programming language? a notational system for describing computation in human-readable and machine-readable form

is HTML a programming language?
`a programming language is Turing complete provided it has integer variables and arithmetic and sequentially executes statements, which include assignment, selection (if), and loop (while) statements' [PLPP] p. 13
or alternatively, `a programming language is Turing complete if it has integer values, arithmetic functions on those values, and if it has a mechanism for defining new functions using existing functions, selection, and recursion' [PLPP] p. 17

what is a programming language concept?
- parameter passing (by-value, by-reference)
- typing (static or dynamic)
- support for abstraction (procedural, data)
- scope (static or dynamic)
- implementation (interpreted or compiled)
- as you can see, often has options
on which criteria can we evaluate programming languages?
- four main criteria (desiderata for computer languages)
  - readability
  - writability
  - reliability (safety)
  - cost (efficiency) of execution or development or both?
- how are readability and writability related?
- others?

Binding times

a useful concept for studying language concepts
a mapping from representation → intended meaning

The times of our lives (and their bindings)

conception
- sex
- parents
- older siblings (if any)
- DNA
birth: dob, name, ssn
life
- height
- degree
death

Times in the study of programming languages

language definition time:
- keyword int bound to meaning of integer
- N. Wirth (designer of Pascal): program mypgm () begin end
language implementation time: int datatype bound to a size (e.g., 4 bytes)
compile time: identifer x bound to an integer variable
link time: printf is bound to the definition
load time:
- variable x bound to memory cell at address 7cd7
- could be at run-time as well (consider a variable local to a function)
run-time: x bound to value 10
some are static, some are dynamic
- static: before run-time, and unchangeable
- dynamic: at or during run-time, and modifiable
earlier times imply
- safety
- reliability
- predictability, no surprises
- efficiency
later times imply flexibility
interpreted languages (e.g., Scheme): most bindings are dynamic (i.e., happen at run-time)
compiled languages (e.g., C, C++, FORTRAN): most bindings are static (i.e., happen before run-time)

Early vs. late binding

humans analogy
- parents and sex are bound statically (at conception)
- birthday is bound statically (at birth)
- height is bound and re-bound dynamically (throughout life)
a programming language should be an algorithm for algorithm development, rather than just a tool to implement an algorithm (recall oil painting)
do not get too wedded to a design or you will be forced to use duck-tape to patch things later should the specifications change (which they always do!) (it's like a bad movie that never ends)
now even Microsoft trying to get a piece of the pie with F#

Static vs. dynamic bindings

a static binding happens prior to execution (usually during compile-time) (e.g., type of x)
a dynamic binding happens and is changable during run-time (i.e., execution) (e.g., the value of x)

Automobile analogs

make: Honda or Toyota
engine: gas or diesel; 4 cylinder, V6, or V8
transmission: manual or automatic
steering: manual or power
braking system: manual or power
options: A/C or no-A/C

Approach

study language concepts by implementing a series of interpreters in Scheme and assess the differences in the resulting languages
why Scheme (a functional language with imperative features)? for purposes of its elegance and power
- ideally situated between formal mathematics and natural language (preface to [TSS])
- ``If you give someone Fortran, he has Fortran. If you give someone LISP, he has any language he pleases'' (afterward to [TSS])
- it is the most powerful programming language
- it is a metalanguage: a language for creating languages [BITL]
- LISP is the second oldest programming language (which is the oldest?)

Programming language paradigms

What is a paradigm? a model or world view (contributed by historian of science Thomas Kuhn) [SICP]
What is a model? a simplified view of something in the real world
What is a programming language paradigm? a pattern for a programming language to follow [PLPP]
paradigms
analogy: C is to the imperative paradigm, as Spanish is to romance languages (essentially all have the same grammar, only differ in the terminals)
declarative languages are sometimes called very-high-level languages ([PLPP] p. 18 and [SICP] p. 22)
will implement languages using Scheme, a functional language
object-orientation evolved from the functional paradigm (see below)
we will also explore (and program in) the functional, logic, and object-oriented paradigms through the use of the languages Haskell and ML, PROLOG, and Smalltalk, respectively
where do functional and logic languages motivate from?
- LISP machine predecessor to modern single-user workstation as well as important modern technologies such as garbage collection, high-resolution graphics, and computer mice, among others
- Warren Abstract Machine (or WAM) is a target for PROLOG compilers
historically,
- imperative languages involve more static bindings and, thus, tend to be compiled
- functional and logic languages involve more dynamic bindings and, thus, tend to be interpreted
when to use which language in which paradigm? application-driven? other ideas?

Definitions of terms used above

syntax (form of language) vs. semantics (meaning of language)
first-class entity
side-effect

Why take variables and assignment away from the programmer?

seems stoic, but there must be an advantage
no assignment in mathematics
variable modification through assignment accounts for a large volume of bugs in programs
without such facilities we might be able to write less buggy code
other reasons? parallelization

First-class entity

notion due to British computer scientist Christopher Strachey (1916-1975) ([SICP] p. 76)
see [EOPL] p. 56 or [PLP] p. 143
a first-class entity is one that can be
- stored (e.g., in a variable or data structure),
- passed as an argument, and
- returned as a value
second-class: only passed as an argument
third-class: cannot even be passed as an argument
are objects first-class in C++? yes. Java? depends how you look at it
are closures first-class in Scheme? yes
alternate perspective ([PLPP] p. 337): the ability to create new values at run-time

Side effect

see [COPL6] p. 299
modification of a parameter or something in the external environment (e.g., a global variable or I/O)
assignment statement possible?
for instance, X = read(); print X + X; vs. print read() + read();
a + fun(a) [COPL6] p. 299

Referential transparency

expressions and languages are said to be referentially transparent (i.e., independent of evaluation order [PLP] p. 622) if the same arguments to a function yield the same output
see [COPL6] p. 583
alternate viewpoint (called substitution rule with mathematical expressions): ``any two expressions in a program that have the same value may be substituted for each other anywhere in the program -- in other words, their values always remain equal regardless of the context in which they are evaluated'' [PLPP] p. 268
related to side-effects, but different
are all functions without side-effects referentially transparent? no, consider a function which returns time()
are all referentially transparent functions without side-effects? no, consider a function which prints "hello world" or a function that always returns 1, but modifies a global variable

What influences language design?

why did programming languages evolve as they did?
computer architecture (e.g., von Neumann architecture gives rise to imperative languages ([PLPP] p. 13-14))
- memory stores both instructions and data
- fetch-decode-execute cycle
- I/O (between processor and memory) is the biggest bottleneck of any computer architecture
- von Neumann bottleneck: computation need not described as a sequence of instructions operating on a single piece of data. For instace, what about
  - parallel computation,
  - nondeterministic computation, or
  - recursion? [PLPP].
programming methodology: top-down design, more data-driven, less procedure-driven, object-oriented
surprisingly, not the abilities of programmers
read The Psychology of Computer Programming by Gerald M. Weinberg

Book/Course objectives

Establish an understanding of fundamental programming language concepts primarily through the implementation of interpreters.
Improve your ability to understand new languages and technologies, and expand your background for selecting appropriate languages.
Expose students to alternate styles/paradigms of programming and exotic ways of affecting computation so to paint a more holistic picture of computing.

Book/Course themes

relationship between languages and the capacity to express ideas about computation
static (rigid and fast) vs. dynamic (flexible and slow) properties
cost/speed of execution vs. cost/speed of development
simple, small, consistent, and powerful languages (LISP, Smalltalk) vs. complex, large, irregular, and weak languages (so called kitchen-sink languages [PLPP], e.g., C++)
languages evolve: the influence of language design and implementation options on current trends in programming practice and vice versa (iPod, GPS in car)
shift in modern times towards more functional, dynamic languages (speed of execution is less important as a design goal as it once was)

Advantages of this course of study

(or `why bother with this stuff anyway?')

see [COPL6] § 1.1 (pp. 2-5)
improve background for choosing appropriate languages
ability to easily learn new languages and technologies as they arrive (ability to focus on the big picture and not the details)
some things cannot be expressed as easily in certain languages (e.g., déjà vu in English, ref. Charlie Suer, Fall 2010)
increase capacity to express ideas about computation (thinking out of the box)
why these languages?
increase ability to design and implement new languages
to better appreciate the historical context
to become a well-rounded computer scientist
in summary, this course will make you a better programmer, in any language

What will you learn?

concepts of programming languages through the implementation of interpreters
language definition and description methods (e.g., grammars)
how to implement interpreters and implementation strategies (e.g., inductive data types, data abstraction and representation, design patterns)
programming paradigms and how to program using representative languages in each paradigm (e.g., Scheme, Haskell, ML, PROLOG, Smalltalk)
esoteric language concepts (e.g., continuations, currying, lazy evaluation)

References

[BITL]	G. J. Sussman, G.L. Steele, and R.P. Gabriel. A Brief Introduction to Lisp. ACM SIGPLAN Notices, 28(3), 361-362, 1993.
[COPL6]	R.W. Sebesta. Concepts of Programming Languages. Addison-Wesley, Boston, MA, Sixth edition, 2003.
[PLP]	M.L. Scott. Programming Language Pragmatics. Morgan Kaufmann, Amsterdam, Second edition, 2006.
[PLPP]	K.C. Louden. Programming Languages: Principles and Practice. Brooks/Cole, Pacific Grove, CA, Second edition, 2002.
[SICP]	H. Abelson and G.J. Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, MA, Second edition, 1996.
[TSS]	D.P. Friedman and M. Felleisen. The Seasoned Schemer. MIT Press, Cambridge, MA, 1996.