Elementary Computer Science: From Bits and Bytes to the Big Picture
@computation @computer-science @book
notes on ckirsch book
https://github.com/ckirsch/book
Think of this book as an introduction to elementary computer science similar to elementary arithmetic taught in primary and secondary school.
While a book about elementary computer science may sound appealing it actually requires commitment to understand the material even though we tried very hard to simplify everything as much as possible. The reason is that computers and software are so expressive that it is unlikely that any other computational machine in the future will be more expressive. Anything that can be computed can be computed now, provided you have enough time, space (as in memory), and energy. That power comes with a level of complexity that is unavoidable but a lot of fun to explore. Computer science is challenging like other natural sciences. In order to study and understand it you cannot just look at software or hardware and get it. No, its true nature is too complex for that. You need tools to see what is going on, like a microscope, except that here the microscope is a particular way to think!
Language
Formal languages have formal semantics.
- The meaning of programming languages are precisely defined, as opposed to an English sentence.
- Goes through recursion and tail recursion.
RISC-U
- Translation is optional, interpretation is not. Interpretation refers to executing the source code according to instructions on the machine .
-
0x15C(~2): 0x006282B3: add t0,t0,t1
- The above will use registers t0 and t1, add the two values and store the result in t0. The same as assigning t0 = t0+t1. The preamble is the memory where the instruction is stored and the encoded instruction.
-
0x006282B3 is the same as 0000 0000 0110 0010 1000 0010 1011 0011
- In binary. So this binary statement is what the machine reads to perform the instruction above.
Why Hexadecimal
-
each hexadecimal number corresponds to 4 bits (a nibble).
-
Hexadecimal is also more compact than binary, 4 times more compact. 1 character of hexadecimal can express 4 bits.
-
Compatibility and compactness.
-
A computer is in exactly one machine state at any given time. It executes and then proceeds across all instructions.
EBNF
- To describe the syntactic structure of formal languages.
-
Specifying the syntax of a formal language and efficiently checking whether some sequence of characters is a sentence according to that syntax are prerequisites of constructing semantics.
- So syntax is completely concerned with form, having no relation to meaning.
- The notion of a context free grammar, that allows recursion. Related to the difference between fsm and psa?
- By starting to define the syntax, we can do an interesting thing of nesting an arbitrary amount of structures (defined by the grammar).
- This makes the language context-free (?) because we can’t just create one big long chain that defines a unit of syntax in our language.
- A pushdown automata is finite state machine with a stack, so it can handle context free grammar.
Need to get familiar with the notion of abstractions and the role they play.