Semantics And Syntax Of High Level Languages

Author

Ken Pu

1 Data Abstraction

1.1 Symbol names

User can define symbol names based on the semantic meaning of the variables.

total = 0
...
total += counter

1.2 Type annotation

User can annotate values by type information so to make verification (type checking) possible.

int total = 0;
...
total += counter;

1.3 Rich data structures

The JVM runtime memory layout (stack, local vars, and heap space) is for performance reasons. Programming languages offer rich data structures to express memory layouts that are natural to the needs of the application.

1.4 Arrays:

names = [
    'Albert Einstein',
    'Alan Turing',
    'David Hilbert',
]

1.5 Dictionaries:

course = {
    'title': "Compilers",
    'schedule': {
        "Wednesday": {
            "start": "8am",
            "end": "9:30am"
        }
    }
}

1.6 Strongly typed data structure

We can give semantically significant names to types.

type StudentID = String
type Name = String
type Street = String
type City = String
type Province = String

We can define more complex data types.

data Address = Address {
  street :: Street,
  city :: City,
  province :: Province
}

data Student = Student {
  studentID :: StudentID,
  name :: Name,
  address :: Address
}

Ultimately we can model arrays more precisely.

type Class = [Student]

This allows us to create instances safely:

sampleClass :: Class
sampleClass = [
    Student {
        studentID = "001",
        name = "Alice Smith",
        address = Address {
            street = "123 Maple Street",
            city = "Springfield",
            province = "StateA"
        }
    },
    Student {
        studentID = "002",
        name = "Bob Johnson",
        address = Address {
            street = "456 Oak Avenue",
            city = "Riverdale",
            province = "StateB"
        }
    }
]

1.6.1 Advanced typing

How do we ensure that studentID is a string that only contains numerical digits?

Haskell offeres the advanced feature known as dependent type:

import Data.Char (isDigit)

mkStudent :: String -> Name -> Address -> Maybe Student
mkStudent sid name addr
  | all isDigit sid = Just $ Student sid name addr
  | otherwise       = Nothing

It allows code that is even more safe:

sampleClass :: Maybe Class
sampleClass = sequence [
    mkStudent "001" "Alice Smith" (
        Address "123 Maple Street" "Springfield" "StateA"
    ),
    mkStudent "002" "Bob Johnson" (
        Address "456 Oak Avenue" "Riverdale" "StateB"
    ),
]

The code sampleClass is safer in the sense that it forces the programming to write code to deal with situations where sampleClass is not a valid class, and instead is Nothing.

2 Runtime Abstraction

2.1 Binding and scopes

Variables are assigned to values.

var x = 10
fmt.Println(x)

2.1.1 Nested scoping rule

However, there is the notion of scopes, and scopes can be nested.

var x int = 10
{
    var y int = 20
}
fmt.Println(x) // ✅
fmt.Println(y) // ❌

2.1.2 More structured scope functions

// Kotlin
var student = Student(
    "002",
    "Bob Johnson",
    Address("456 Oak Avenue", "Riverdale", ...)
).also(
    val student = this.name
    println("${student} address is ${this.address}")
)

There are two scopes:

  • the main scope has a binding between variable student to the object.
  • the subscope has a binding between value student to the student name, and this to the object.

2.2 Threads

2.2.1 Multicore architecture

2.2.2 Structured threaded execution

import kotlin.concurrent.thread

thread(start=true) {
    ... // code to run in a new thread.
}

thread(start=true) {
    ... // code to run in another new thread.
}

2.2.3 Interleaving threads via communication

2.2.4 Inter-thread communication

var count = 0
var total = 0.0
var lock = Any()
fun increment(amount:Double) {
    synchronized(lock) {
        count ++
        total += amount
    }
}

fun decrement(amount:Double) {
    synchronized(lock) {
        count --
        total -= amount
    }
}

The two functions increment and decrement will never overlap.

val t1 = Thread {
    for(i in 1..5) {
        increment(Random.nextDouble())
    }
}
val t2 = Thread {
    for(i in 1..5) {
        decrement(Random.nextDouble())
    }
}

We can management threads with manual control.

t1.start()
t2.start()

t1.join()
t2.join()

// counter should be zero

2.3 Coroutines and channels

  • Coroutines are blocks of code that are allowed to be executed interleaved.

    • a relaxed version of threads
    • each thread can execute multiple coroutines
    • coroutines can be interleaved using co-operative multiplexing
    • highly scalable (> 1,000,000 coroutines)

2.3.1 Golang coroutines

go func() {
    ... // runs concurrently with multiplexing
}()

The general syntax is:

go f(...)

where the function f(...) is executed in a coroutine.

Here we are creating an anonymous function, and invoking it immediately.

func() {
  // code to be executed
}()

Go has a highly efficient dispatcher that can support millions of coroutines on modern CPUs, making it so ideal for server development.

2.3.2 Golang channels

Channels are communicating objects that can be shared among coroutines.

var ch chan int = make(chan int)
ch <- 42
var number = <-ch

2.3.3 An example of producer / consumer pattern

func producer(ch chan<- int, group *sync.WaitGroup) {
    for i := 1; i <= N; i++ {
        var value int = makeValue()
        ch <- value
    }
    group.Done()
}

The producer function makes \(N\) integer values, and sends them to the channel ch. At the end, it also indicates that it is done.

func consumer(ch <-chan int) {
    for value := range ch {
        saveValue(value)
    }
}

The consumer function reads all the data from the channel until it is closed (remotely).

Let’s put it all together:

var NUM_PRODUCERS = 1000000
var ch = make(chan int)

This is a shared channel.

var group sync.WaitGroup

This is a shared count-down synchronization data structure.

  • group.Wait() blocks until the lock value reaches zero.
  • group.Done() decrements the lock value by one.
go consumer(ch)

We can safely start consuming even before the producers have started.

  • It will momentarily block at reading from the channel.
  • It will also terminate after the channel is closed.
group.Add(NUM_PRODUCERS)
for i := 0; i < NUM_PRODUCERS; i++ {
    go producer(ch, &group)
}
  • Initially, we set the count-down value to NUM_PRODUCERS.
  • Start NUM_PRODUCERS coroutines.
group.Wait()
close(ch)
  • Wait for all producers to finish
  • When all the producers are done, we can safely close the channel.
  • When the channel is closed, then the consumer will also terminate.

3 Summary

3.1 Design of runtime environment

  • Scopes, modules, and functions
  • Data types
  • Concurrency: thread / coroutine / channels

3.2 Syntax

  • Nested code blocks, anonymous function
  • Type system and type annotations
  • Structured concurrency and synchronization

3.3 What’s the point?

  • Innovative runtime environment
  • requires innovative syntax to boost productivity and improves reliability.