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.

!

Declaration

int i;
int[10] j;

Read / Write

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

Types

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.

Functions

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)
    return
}

! 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.

Branching

var discount = 0;
if(age < 10)
  discount = 0.4;
else if(age >= 65)
  discount = 0.2;
else
  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.

Iteration

!

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

Scope

!

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.

!

Abstraction


$\lambda x.e$

!

(fn [x] e)

Application


$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]

Summary

!

back
© KEN PU, 2016