Syntax and Grammar

Syntax Specification

Syntax in a programming language is specificied using a mathematical device called a Grammar.

Example: A really simple language’s syntax

Arithmetic Expression

AExp \to IntBit | AExp + AExp | ...

Boolean Expression

BExp \to BLit | BExp < BExp | ...

BLit: Boolean Literal

Statements:

\text{Stmnt} \to \text{Assgment} | \text{IFThen | \text{while}

et cetera…

Variables and Binding

Variables

Variable: Store data and associate it with a name.

Only makes sense in imperative languages (destructive updates, destroy previous value in memory location)

Variables have two values associated with them.

Memory location and value.

Example: A variable

int x = 42

Symbol table:

Symbol	L-Value	R-Value
x	i	42
…	…	…

Some systems programming languages let you access the L-value through pointers and dereferencing.
Symbol table can also store type information, so that we know how many bytes to read (e.g., 4 contiguous bytes for an integer)

Static type checking is an uncomputable problem. There is no algorithm that can, for all possible instances, solve that problem.

Example: A pointer

int x = 42;
int *p = &x;

Symbol table:

Symbol	L-Value	R-Value
x	i	42
p	j	i
…	…	…

Notice how *p and x become aliases for the same memory location, which can lead to potential problems.

Binding

Binding: Association of a name to a particular property.

e.g., memory, type, scope, and more.

\begin{matrix} &\text{Symbol} & & &\text{Property} \\ &x &\to& &p \end{matrix}

Types of Binding:
Memory Allocation: Memory binding
Typing: Type binding
Scoping: Scope binding

Binding Time: When the binding happens

Dynamic Binding: If the binding happens while the program is running.
Static Binding: If the binding happens outside program execution.

More on Static Binding: Two types
Compiler does it
Lexer does it.

Note: This has nothing to do with the static keyword in Java.

Memory Binding (Memory Allocation)

Static Allocation: Allocation happens before execution (typically the compiler)

Memory is allocated in data section.

Process Memory Heap:
TODO plantuml
stack (stack frames)
heap (dynamically allocated data)
data (statically allocated data).
text
Refresher: Frames store the local variables and parameters of a function call.

Dynamic Allocation: Allocation happens during execution.

Memory is allocated in heap section.

Example: Static and dynamic allocation in C.

// Statically allocate n=3
x = int[3];

// Dynamically allocate n=3
y = malloc(sizeof(int) * 3);

The dynamic array takes longer due to the overhead of malloc.
The static array has no such overhead, but requires you to know how much memory you need beforehand.

In dynamic languages (e.g., Python, Ruby, Perl), all arrays are dynamic, because there is no static allocation in an interpreted language.

Type Checking

Typing: Assigning a type to every symbol in a program, and checking the type assignment makes sense.

Static Typing

Static Typing: Happens before execution, typically during compilation

Explicit Typing: Type data explicitly stated in source code.
Implicit Typing: Type data is inferred by type checking engine.

Example: Explicit and implicit typing in Rust

// Explicit Typing
let x : f64 = 1.0;

// Implicit Typing (type inference)
let y = 1.0;

On Overhead:
Typing adds a lot of overhead, which is why there’s a gap in performance between compiled and dynamic languages.
In the modern day, with JIT and other optimizations, this gap is shortening.

Dynamic Typing

Dynamic Typing: Happens during execution

Strict Typing: When the type is allowed to change.

Example: Strict typing

Suppose:

x := 42
// ...
x := "Apple"

If this is disallowed, the typing is said to be strict.

Scope Binding

Scope: The region of a program where a symbol is visible.

Remember: This is about visibility, not permanence!

Globals: Symbols which ignore scoping rules and are visible everywhere.

Often used to create immutable consts.

Example: Scope

Typical example:

fn f() {
  let x = 42;
}

fn g() {
  let y = 42;
}

x and y are visible only in their respective functions, yada yada yada.

Wacky example:

// We can statically define variables in c
f() {
  static x = 0;
  x++;
}

The variable outlives the function, living in the data section rather than the heap.

Static Scoping (Lexical Scoping)

Scoping happens while writing the program.

Also called lexical scoping.

Dynamic Scoping

Scoping determined at runtime.

Whatever is in the stack exists everywhere.
Adds overhead, as you have to look in the stack to determine scope.

Example: Dynamic scoping and shadowing

z := 0
x := 0
call g
call f

function f() {
  // Shadows the x outside
  x := 42
  call g
}

function g() {
  // Uses the x in the function that called me 
  y := x \text{$+$} 7
}

This breaks local reasoning, your ability to look at a function and debug it by only looking at the contents of the function.
A pro is that is lets you have simpler function signatures.

For most dynamic languages, this is an optional thing you have to turn on.

Types

Data Type: Property of symbol that defines its nature (size, structure, etc.)

1. Primitive Types

Primitive: Types that are deined by language

More Accurate: Type that is not made from other types

Typical Primitive Types:

Boolean
Integers
Floating points
Characters

Example: Aside: Typical size of typical primitives.

Type	Bytes
bool	1
int	32
double	64
float	32
char	1—4

2. Non-Primitive Types

Typical Non-Primitive Types:

String literals

Now we’ll discuss some data types.

Strings

Most languages implement Strings as:
First-class citizens, and
Internally implements as arrays of characters.

Implementations:

Fixed Size Immutable: Easily implemented with arrays. (Java)
Bounded Dynamic Size: Can also be implemented with array, where the size of the array is the upper bound on the size of the string. (C/C++)
Fully Dynamic: Can be implemented with buffered arrays or linked lists (Ruby, Python)

Example: Implementation of string

In C, strings are just arrays of characters terminated by zero.
In Java, Strings are full-blown objects which has an array of characters

Arrays are very fast to read and easy to use, which is why they are behind most String implementations.

The disadvantage is that arrays are fixed-size.
Hence, array strings are great for read-heavy strings, and terrible for write-heavy strings.

Suppose you want to naively concatenate three Strings in Java: (A + B + C).

This’ll make Java create a whole new object just to do A+B, and another object to do B+C; which is very expensive.
If you need to do this a bunch of time, you should use StringBuffer instead, which allocates a large array to reduce allocations.

Arrays

Array: Indexed sequence of elements of the same type.

The simplest data structure in most imperative languages.

Why Elements of the Same Type?:
Every element must have the same size to achieve random-access.
e.g., we know to get arr[5], we just do \text{base address} + 5 \times \text{size of type}

Design Issues

Type of Subscript

Traditionally this is an integer, but some domains may want us to change it.

e.g., associative arrays (tables) map keys (usually strings) to the value.
- You can regain time with hash tables.
Does the index start at zero or one?

Range Checking

Is array index bounds checking provided?

Pros: Ensures safe memory access and memory integrity,
Cons: Adds overhead.

Not doing range checking will save some time.

Dynamic Range Checking: Range check at runtime

e.g., Java

Static Range Checking: Use a static analyzer that looks at each array access and determines if it’s safe.

This is an undecidable problem.
One solution is to use static range checking to mark certain accesses as safe, and mark the undecided ones for dynamic range checking.
- Static analysis is super expensive by itself, this will greatly complicate compilation.

Dynamic Size?

Recall — Arrays’ random access is made possible by the fact they are allocated contiguously.
Hence, to resize an array, we could allocate a whole new, bigger array and copy the data over.

In other words, dynamic array sizes are just abstractions on top of normal fixed-size arrays that simplify the operation for the programmer.

Implemention Methods:

Buffered Array: Allocate extra memory to lower amount of resizes.
- This is the preferred implementation.
Linked List: Totally forgoes speed.

Allocation: Static v. Dynamic

Does the array get allocated statically, dynamically, or in a mixed fashion?

Multidimensional Arrays

Multidimensional Arrays: Indexed by more than one index value.

e.g.,

int[][] arr := new int[3][3];
arr[0][2] := 42;

Implementation Methods:

Array of Arrays: 1D array with pointers to other array(s).
Sequential Allocation: All elements allocated on a single array.
- Pros: Everything is contiguously allocated.
- Cons: Cannot do jagged arrays.

Jagged Array: Multidimensional array in which one of the dimensions is variable.

Implemented with doing array of arrays.

Example: Implementation methods

Suppose this 2D array:

\begin{bmatrix} &0 &0 &0 \\ &1 &1 &1 \\ &2 &2 &2 \\ \end{bmatrix}

1. Array of Arrays

// Array of pointers
arr = [0x0, 0x1, 0x2]
// Arrays containing data
0x0 = [0, 0, 0]
0x1 = [1, 1, 1]
0x2 = [2, 2, 2]

2. Sequential Allocation

arr = [0,0,0,1,1,1,2,2,2]

// Jump 2 blocks, get element 1
arr[2][1]

Example: Jagged array

arr := new array[3][?]
arr[0] \rightarrow [0, 0, 0, 0]
arr[1] \rightarrow [1, 1]
arr[2] \rightarrow [2, 2, 2]

Associative Arrays

Map keys of any type to values.

Usually implemented as hash tables.

grades["John Romero"] = 3

Other Operations

Computing Length
Pretty Printing
Sorting
Reverse Lookup
Array Copying
- Computing subarrays
- Concatenation
- Computing subarrays that match predicate P
Vectorizing of functions

Next section:

Records and Tuples