%%
Title: The Architecture of Symbolic Computers
Created: 2022-03-10 02:26
Status: #Paused
Parent: [[Resources/Reading/Books/CompSci]]
Tags: #books
Source:
%%
# The Architecture of Symbolic Computers
# Introduction
- central idea: computations centred around processing symbols, often by substitution or matching
- two directions explored in this book
- functional: composition of functions
- logic/declarative: express relations between symbols
# Fundamentals of Computation
## Problems & Algorithms
- The normal reason for using a computer: we have a problem for which a solution is desired.
- Problems are often generic; they are parameterised.
- Solving a problem: provide input values to some parameters and finding matching values for the remainder of the parameters.
- Assignment specifies a particular instance; if there's a single solution, the problem is deterministic.
### Variables, substitutions, and computation
- Free variables: parameters not bound to a specific value.
- Binding: giving a free variable a value; a value can only be bound once in a given context.
- Substitution: replacing bound variables in the problem description with their values (input substitution); likewise, substituting some values in the remaining parameters $=>$ output substitution.
- Formal properties: what properties do the output parameters have in relation to the input parameters?
- Computation: determining an output substitution which, for a given specific input substitution, obeys the specified properties.
- Example: knapsack problem
- Formal problem statement
- Given
- a knapsack of capacity $C$
- $N$ objects of weight $W_k$ and value $V_k, k = 1, …, N$
- Find: a fraction $F_k$ of each object such that
- the knapsack isn't overloaded
- the value carried is maximised
- objects can be "sliced" into pieces
- Variables: $C, N, W_1, V_1, F_1, …, W_N, V_N, F_N$
- Instance (input substitution):
- C = 14kg
- N = 3
- W = {4, 6, 7}
- V = {30, 48, 50}
- Solution (output substitution):
- F = {1, 1, 4/7}
- total value: $106.57
### Algorithms
- Algorithm: step-by-step description of how to solve a problem
- Execution (of an algorithm): given a particular instance, substitute instance values for parameters in the algorithm
- Properties of an algorithm
- Finite number of steps
- Each step uses a finite number of simple operations
- Example: knapsack algorithm
1. Sort objects by ratio of value to weight.
2. Repeated until knapsack overflows: remove highest value-to-weight object and place entirely in the set.
3. Take out last item in knapsack and slice off just enough to fit in knapsack.
## Languages: syntax & semantics
- Language: notation for conveying meaning or information
- this book: restricted to notations comprised of linear left-to-right sequences of symbols.
- Syntax/grammar: rules describing valid forms of notation.
- Semantics: relationship between syntax and meaning.
- Program: syntactically complete description of one algorithm or problem statement.
- Statement (sentence): smallest piece of notation describing an individual step.
- Computer: some agent (usually electronic) that interprets a syntatically valid program according to the languages semantics, essentially executing the algorithm for a particular instance.
- Problem solving by substitution.
- Example: assignment statement $x := x + 42$
1. Get a copy of the contents of the memory location associated with the symbol '$x