Principles of Programming Languages

References

• Principles of Programming Languages, Version 1.0.3, Mike Grant, Zachary Palmer, Scott Smith

Operational Semantics

The syntax of a programming language is the set of rules governing the formation of expressions in the language. The semantics of a programming language is the meaning of those expressions.

There are several forms of language semantics:

• Axiomatic semantics is a set of axiomatic truths in a programming language
• Denotational semantics involves modeling programs as static mathematical objects, namely as set-theoretic functions with specific properties

An operational semantics is a mathematical model of a programming language execution. It is an interpreter defined mathematically.

An operational semantics for a programming language is a mathematical definition of its computation relation, , where is a program in the language.

= expression of the language. = values of the language. and are metavariables, meaning they denote an arbitrary expression or value. An operational semantics for a programming language is a means for understanding in precise detail the meaning of an expression in the language.

Backus-Naur Form (BNF) is a standard grammar formalism for defining language syntax. All BNF grammars comprise terminals, nonterminals (aka semantic categories), and production rules. Terminals are traditionally identified using lower-case letters; non-terminals are identified using upper-case letters. Production rules describe how nonterminals are defined:

where each form above describes a particular language form - that is, a string of terminals and non-terminals. A term in the language is a string of terminals which matches the description of one of these rules.

Another way of expressing grammar is by the use of a syntax diagram. Syntax diagrams describe the grammar visually rather than in textual form.

Operational semantics are written in the form of logic rules, which are written as a series of preconditions above a horizontal line and the conclusion below it:

The above indicates that if a thing is red and shiny, then that thing is an apple. Operational semantics rules discuss how pieces of code evaluate. If there are no preconditions above the line in expressions like above, it means that no conditions must be met. Rules with nothing above the line are termed axioms since they have no preconditions and so the conclusion always holds. Using metavariables can help us generalize operational semantics:

The value rule above is an axiom declaring that any value always evaluates to itself. A proof amounts to constructing a sequence of rule applications such that, for any given application of a rule, the items above the line appeared earlier in the sequence and such that the final rule application is . All leaves of a proof tree must be axioms.

Our operational semantics rules have expressed the evaluation relation in terms of concrete syntax using metavariables. The abstract syntax of a language is a representation which more accurately (than operational semantics) describes how we think about the program. A term in an abstract syntax is represented as a syntax tree in which each operation to be performed is a node and each operand to that operation is a child of that node. The abstract syntax is a form which more directly represents the operations being performed whereas the concrete syntax is the form in which the operations are actually expressed. Part of the process of compiling or interpreting a program is to translate the concrete syntax term (source file) into an abstract syntax term (AST) in order to manipulate it. The relation to map concrete syntax form to abstract syntax form .

The only difference between the operational semantics and the interpreter is that the interpreter is a function.

A metacircular interpreter is an interpreter for (possibly a subset of) a language x that is written in language x.

A computation model is Turing-complete if every partial recursive function can be expressed within it.

A function is a partial recursive function if an algorithm exists to calculate it which has the following properties:

• The algorithm must have as its input a finite number of arguments.
• The algorithm must consist of a finite number of steps.
• If the algorithm is given arguments for which the function is defined, it must produce the correct answer within a finite amount of time.
• If the algorithm is given arguments for which the function is not defined, it must either produce a clear error or otherwise not terminate. (That is, it must not appear to have produced an incorrect value for the function if no such value is defined).

Note that BNF uses the metavariables , , and to represent expressions, values, and variables respectively. Operational semantics is about describing clearly and unambiguously how programs are to compute.

A variable use occurs in if appears somewhere in . Note we refer only to variable uses, not definitions.

(Bound Occurrence) Any occurrences of variable in the expression.

(Free Occurrence) A variable occurs free in if it has an occurrence in which is not a bound occurrence.

(Closed Expression) An expression is closed if it contains no free variable occurrences. All programs we execute are closed (no link-time errors) - non-closed programs don't diverge, we can't contemplate executing them because they are not in the domain of the evaluation relation.

(Variable Substitution) Given a closed expression , the variable substitution of for in , denoted , is the expression resulting from the operation of replacing all free occurrences of in with .

An encoding is a way of representing a behavior in a system that does not directly support it.

Tuples, Records, and Variants

One of the most fundamental forms of data aggregation in programming is the notion of pairing. With pairs, or 2-tuples, almost any data structure can be represented. With pairs, or 2-tuples, almost any data structure can be represented. Records are a variation on tuples in which the fields have names. The main advantage of a record over a tuple is the named field.

Side Effects: State and Exceptions

There are many types of side-effects, including the following:

• Goto-statements or loop-breaks, which are similar to exceptions. Note that loop-breaks require loops, which require state
• Input and output
• Distributed message passing

In an explicit environment interpreter, instead of doing direct variable substitution, we keep track of each variable's value in runtime environment. The runtime environment is simply a mapping of variables to values. A closure is a function along with an environment, such that all free values in the function body are bound to values in the environment.

Object-Oriented Language Features

Object-oriented programming has become an industry standard. Yet, object-oriented features do not fundamentally add much to a language. They certainly do not lead to shorter programs. The success of object-oriented programming is due mainly to the fact that it is a style that is appropriate for the human psychology. Humans, as part of their basic function, are highly adept at recognizing and interacting with everyday objects.

Most object-oriented languages allow information hiding which is used to protect methods and instance variables from direct outside use. Inheritance allows related objects to be defined that share some common code. The term dynamic dispatch refers to how the method invoked by a message send is not fixed at compile time.

Type Systems

A type is simply a property with which a program is implicitly or explicitly annotated before runtime. In static type systems, types are checked by the compiler and type-unsafe programs fail to compile. Dynamic type systems on the other hand check type information at runtime.

Concurrency

• Wikipedia Article on Parallel Computing
• Threads Wikipedia Article
• Actor Model Wikipedia Entry

Concurrent execution can be loosely grouped into three implementation categories, in order of loosest to tightest coupling.

1. Distributed Computation is computation on multiple computers which share no memory and are sending messages between each other to communicate data
2. Grid Computing is distributed computing where the internet is the communication medium
3. Cluster computing is over a fast LAN network
4. 1. Massive Parallel Processing (MPP) involves specialized communication hardware for very high communication bandwidth
4. Distributed shared memory is the case where different processes are running on different processors but sharing some special memory via a memory bus.
5. Multithreaded computation is the case where multiple threads of execution share a single memory which is local
6. 1. Multithreaded computations may run on a single (core) CPU, meaning the concurrent execution is an illusion achieved by interleaving the execution steps of two threads, or if the computer has multiple cores there can be true concurrent execution of a multithreaded program

Vector processors are computers that can do an operation on a whole array in one step. These architectures used to be called SIMD (Single Instruction Multiple Data). Stream processors are the modern version of vector processors which can work on more than just arrays in parallel, for example sparse arrays. The GPGPU (General Purpose Graphics Processing Units) is a recent version of a stream processor which arose as a generalization of specialized graphics processors. FPGA's are Field Programmable Circuits: you can create your own (parallel) logic on the fly.

A race condition is when two operations are interleaved and leave the data in an inconsistent state. Deadlock is when threads may need to wait for resources to free up, and can get into a cycle of waiting.