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:

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

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