A tour of programming languages


We will examine the influence of TM and LC on the design of programming languages.

Stateful languages


Stateful languages

Principles of a TM

Stateful languages

! Describing computation based on the principles of a TM s called imperative programming.

Stateful languages

Elements of TM Programming construct Jargon
Memory Array, struct Builtin aggregate types
Multable Assignments lvalues
Flow control if-else, while, for Branche and loops

Stateful languages

Extensions to the TM

They are necessary for humans to author and reason about the program.

! Procedural programming languages

Variables (in procedural languages)

Ultimately, variables are names which are aliases for memory addresses.



int i;
int[10] j;

Read / Write

i = 10;
j[2] = i * j[0];


typedef Point2D struct {
    float x;
    float y;

! This declares a struct aggregate type in C

type Point2D struct {
    X float
    Y float

! Same structure in Go

class Point2D(val x:Float, val y:Float)

! Same structure in Scala

We can build arbitrarily complex data structures using user-defined types.


Point2D rotate(Point2D p, float a) {
    Point2D p2;
    p2.x = p.x * cos(a) - p.y * sin(a);
    p2.y = p.x * sin(a) + p.y * cos(a);
    return p2;

! A function in C

func rotate(p Point2D, a float) (p2 Point2D) {
    p2.X = p.X * math.Cos(a) - p.Y * math.Sin(a)
    p2.Y = p.X * math.Sin(a) + p.Y * math.Cos(a)

! A function in Go. Note the name binding in the return type.

def rotate(p: Point2D, a : Float) : Point2D {
    val x = p.x * cos(a) - p.y * sin(a);
    val y = p.x * sin(a) + p.y * cos(a);
    Point2D(x, y)

! A function in Scala. Note the val keyword, and the lack of explicit return

More on functions


In modern languages, functions can be values and can be constructed and passed around like values.


var log = function(message) {
    console.info("Message: " + message);

! Function as value in Javascript.

var log = func(msg string) {
    fmt.Println("Message:" + msg)

! Function as value in Go.

val log = {msg : String => println(msg)}

! Function as value in Scala.

Expression vs Statement

printf("hello world\n")

! This is a statement. It is invalid to ask the value of a statement. It’s meant to do something, not represent something.

get_age() > 65

! This is an expression. It doesn’t (necessarily) do anything, but it represents a value of some type. In this case, it’s a boolean expression.


var discount = 0;
if(age < 10)
  discount = 0.4;
else if(age >= 65)
  discount = 0.2;
  discount = 0;

! Javascript branching with if-else. C and Java have the same style of if-else. Here if-else is an statement. What it does is the assignment of some variable discount.

val discount = if(age < 10) 0.4
               else if(age >= 65) 0.2
               else 0

! In Scala, everything is an expression. It represents the value of discount.

val discount = age match {
    case _ if age < 10 => 0.4
    case _ if age >= 65 => 0.2
    case _ => 0

! Scala supports pattern matching.



Possibly the most used and thought-out feature of procedural programming.


for(int i=0; i < 100; i++)
  for(int j=0; j < 100; j++)
    if(i + j == 55) printf("%d, %d\n", i, j)

! for loop in C/Java/Javascript.

for i in range(100):
  for j in range(100):
    if i + j == 55:  print i,j

! for loop in Python

print [(i,j) for i in range(100) \
    for j in range(100) if i + j == 55]

! List comprehension in Python



The scope of a variable is context in which the variable exists. This will be discussed in depth later.

Scoping is not part of the syntax, but rules on variable life-time.


int i = 0;
if(i == 0) {
    int i = 10;
    printf("%d", i);
printf("%d\n", i)

! C will print out 10 0. Note that there are two variables, both with the name i.

function friendlyLogger() {
    var greeting = "Hi there, ";
    return function(message) {
        console.info(greeting + message);


var logger = friendlyLogger();
logger("my name is Einstein.");

! For Javascript, scopes are nested, and the parent scope (friendlyLogger) is preserved in the scope of function(message). This is called closure.

Functional languages


Functional languages

Principles of LC

Functional languages

LC influence on programming language design

Functional languages

Extensions to beyond LC

! We will illustrate these topics using Clojure.

Syntax: from LC to Lisp


LC is so syntactically clean that Lisp (and its dialets including Clojure) has borrowed the LC syntax almost verbatim.



$\lambda x.e$


(fn [x] e)


$f e$


(f e)

Functions as data

(defn log [message]
  (println message))

! Declaring a function with a name.

(fn [message] (println message))

! Creating a value which happens to be a function. This function has no name, so we call such functions anonymous functions.

#(println %1)

! A quicker way to create a function without a name.

Name binding

(def pi 3.1415)

! Global name binding

(def log (fn [message]
           (println message)))

! This is another way to create a named function.

(let [name "Einstein"]
  (println name))

! The let form helps to create name bindings with limited scopes.

Immutable data


Data can only be:


But never modified.


(def x [1 2 3 4])

! Create a list of numbers, and bind it a name x.

(conj x 5)

! This makes a copy of x and append 5. But since it’s not bound to any name, the result is lost.

(def y (concat x [10 20 30]))

! x is still [1,2,3,4] (forever), and y is [1,2,3,4,10,20,30]



© KEN PU, 2016