#### 2018-09-01

term: 2A

Foundations of Sequential Programs, taken in Fall 2018.

# Course Overview

How to go from high-level languages (C++, Python, Racket…) to machine code. Understand the link between high-level languages and the underlying processor’s instruction set.

This info is complemented with an OS course, to understand how various resources (processor, main memory, secondary storage) are managed.

### major topics:

- Machine architecture
- Assembly language
- Assemblers
- Linkers & Loaders
- Regular languages and scanning
- Context-free languages and parsing
- Semantic Analysis
- Code generation
- Runtime organization
- Data layout

# 01 : representing data

**Decimals** for humans, aka base 10, radix 10: computers originally used base 10, but that led to complicated designs with vacuum tubes (good luck differentiating between 10 states)

**Binary** for computers, aka base 2, radix 2: Konrad Zuse’s mechanical computer Z1 was the first to use binary. Much simpler design, much more reliable to store information over time, or transmit over long distances.

**Hexadecimal** the compromise, base 16: represents more and is arguably readable

### unsigned ints

**Unsigned int addition**: issues with fixed width leading to overflowing, also negative numbers can’t be represented.

### signed ints

- most significant bit meaning the left-most bit with the highest value
- least significant bit meaning the right-most bit with the lowest value

**sign extension**: two ways to represent 0 (0000 and 1000, which is a problem)

**one’s complement**: invert bits, same problem

**two’s complement**: invert bits and add 1, easier to implement in hardware, and only one 0 (0000), NEED to specify word size

Why does 2’s complement work? Modular arithmetic that wraps around n-1 bits rather than n bits. The MSB of a negative number is always 1.

Interpretation is in the eye of the beholder.

Bit (1), Nibble (4), Byte (8)

Word, dependent of the processor/archtecture. (32/64)

# 02 : MIPS assembly language

# 03 : implementing an assembler

# 04 : regular languages

# 05 : deterministic finite automata

# 06 : finite automata

# 07 : regular expressions

# 08 : scanners

# 09 : regular languages

# 10 : context-free grammar I

# 11 : context-free grammar II

# 12 : top-down parsing

# 13 : bottom-up parsing

# 14 : context-sensitive analysis

# 15 : code generation big ideas

# 16 : code generation for pointers

# 17 : code generation for procedures

# 18 : optimization

# 19 : linkers and loaders

# 20 : heap management

# personal takeaways