# Assembly

([home](https://github.com/alexhkurz/introduction-to-programming/blob/master/README.md) ... [previous](https://hackmd.io/@alexhkurz/Sks4Jxekw) ... [next](https://hackmd.io/@alexhkurz/Hkc7HoSC8))

## Introduction

[Assembly](https://en.wikipedia.org/wiki/Assembly_language) is a generic word for the programming languages that are close enough to the architecture so that they do force the programmer to know about details of memory management and other aspects of the hardware.

## Computer Architecture

For this session we only need to know the very basics of computer architecture.

For us, computers have three components, which today fit all on the same chip.

RAM, Bus, CPU.

The RAM (Random Access Memory) stores the programs and the data. it is measured in GB (Giga Byte). The CPU (Central Processing Unit) has only a small working memory and is responsible for exectuting the program on the data. For this purpose the CPU keeps repeating the [instruction cycle](https://en.wikipedia.org/wiki/Instruction_cycle):
- fetch the next instruction of the program from the memory
- fetch the relevant data from the program
- execute the instruction on the data
- write the result to memory

The Bus is the connection between RAM and CPU. The instruction cycle above needs a lot of data going forth and back on the bus. Communication over the bus is what slows down a lot of computations and is knows as the von Neumann bottleneck.

## Webassembly

In this session we look at an example of an assembly language, called Webassembly, that is still on a high enough level of abstraction that it does not depend on the particular hardware your machine is running on, but already shows many of the particular features of assembly languages.

**Activity:** Read the first two paragraphs of [Webassembly](https://en.wikipedia.org/wiki/WebAssembly) and report back something interesting.

Webassembly is hardware independent. It should run on any machine in any webbrowser. Before Webassembly, code that was to run in a browser was written in JavaScript, see this example at [Khanacademy](https://www.khanacademy.org/computer-programming/spin-off-of-project-shooting-star/4559547334737920) for an example. Webassembly has two advantages: It is a faster, more low-level language and any higher language such as C, Python, etc can be compiled (=translated) into Webassembly. So one gains performance and platform indpendence.

I took the following C-program of the Fibonacci sequence from the article [Understand WebAssembly Text Format](https://dev.to/sendilkumarn/understand-webassembly-text-format-from-wtf-to-wat-43bi), but I have a shorter more concise translation into Webassembly, produced with the C++ to Webassembly compiler written by Samuel Balco.

## A C Program

Let us first look at the following version of Fibonacci written in C.

int fib(int n) {
if (n <= 1)
return 1;
else
return fib(n-1) + fib(n-2);
}

**Activity:** Read this program. Can you spot some differences between C and Python? Write out the beginning of the sequence produced by this program. Does it produce a different sequence? To compile the program download [fib.c](https://raw.githubusercontent.com/alexhkurz/introduction-to-programming/master/src/fib.c). Compile it with

gcc fib.c

which produces a machine readable file called `a.out` which you can run with

./a.out

## Webassembly, again

Webassembly is a more low-level language than C and Python. For example, ...

Webassembly is more high-level than other assembly languages in that it abstracts from ...

It is helpful to think of Webassembly not as running directly on hardware but running on an "abstract machine" (which in turn is implemented on the hardware). This abstract machine comprises the following features.

- ...
- ...

## Example

Now let us look at how this plays out in a concrete example. The C program above can be written in Webassembly as follows.

(func $fib (export "fib") (param $n i32) (result i32)
(local.get $n)
(i32.const 1)
i32.le_s
(if
(result i32)
(then (i32.const 1) return)
(else
(local.get $n)
(i32.const 1)
i32.sub
(call $fib)
(local.get $n)
(i32.const 2)
i32.sub
(call $fib)
i32.add
return
)
)
)

**Activity:** To experiment with the code paste the code above in the upper right window of [wat2wasm demo](https://webassembly.github.io/wabt/demo/wat2wasm/) and paste

const wasmInstance =
new WebAssembly.Instance(wasmModule, {});
const { fib } = wasmInstance.exports;
console.log(fib(10));

in the lower left window. Call `fib` with different values.

**Activity:** Execute the code above line by line on the `fib(3)`.

**Optional Activity:** Read [Understand WebAssembly Text Format : From WTF to WAT](https://dev.to/sendilkumarn/understand-webassembly-text-format-from-wtf-to-wat-43bi) which has the same C-program compiles it differently to Webassembly. Can you compare the two?

**Optional Activity:** Can you modify the code in order to print the values of a different sequence such as the triangle numbers?

## References

[Understand WebAssembly Text Format](https://dev.to/sendilkumarn/understand-webassembly-text-format-from-wtf-to-wat-43bi)

[webassembly.org](https://webassembly.org/)

## Appendix

In the version above the C program and the Webassembly program are still quite similar. For example we do not see how loops are implemented using jumps (or gotos). So let us look at the following iterative version of Fibonacci.

but a bit longer. If you are interested in looking a bit more at Webassembly this may be a good exercise.

At the start

(module
(func $fibonacci (export "fibonacci") (param $n i32) (result i32)

one declares a function `fibonacci` (in Webassembly all variable names begin with `$`) that takes an argument (parameter) called `n` of type `i32` (a 32 bit integer) and returns a result of type `i32`.

Then the local variables are declared:

(local $fib_one i32)
(local $fib_two i32)
(local $fib i32)
(local $i i32)

In the lines above, we do not see all details of the memory management. For example, we do not see the addresses of the variables `fib_one`, etc. Only their types are declared. The type is important because it tells the machine that it needs to reserve 32 bits in memory for it.

We have seen that both in a Turing machine and in the von Neumann architecture a finite control works on potentially infinte memory. The finite control maintains its own internal memory in form of a stack.

(i32.const 0)

Puts `0` on top of the stack.

(local.set $fib_one)

Writes the value on top of the stack into memory location `fib_one`. Deletes the value from the stack.

Can you annotate the next 4 lines?

(i32.const 1)
(local.set $fib_two)
(i32.const 0)
(local.set $i)

Now we enter the loop:

(block
(loop
(local.get $i)
(local.get $n)

The last two lines get the values of `i` and `n` from the RAM and put them on the stack.

(i32.const 1)
i32.add

Now `n+1` is on the top of the stack.

i32.lt_s

Remove `i,n` from the stack. If `not (i < n+1)` put `0` on top of the stack, otherwise put `1`.

i32.eqz

Negates the top of the stack.

(br_if 1)

If `1` on top of the stack jump out of the block, otherwise continue.

Can you continue annotating from here?

(local.get $i)
(i32.const 0)
i32.eq
(if
(then (local.get $fib_one) (local.set $fib))
(else
(local.get $i)
(i32.const 1)
i32.eq
(if
(then (local.get $fib_two) (local.set $fib))
(else
(local.get $fib_one)
(local.get $fib_two)
i32.add
(local.set $fib)
(local.get $fib_two)
(local.set $fib_one)
(local.get $fib)
(local.set $fib_two)
)
)
)
)
(local.get $i)
(i32.const 1)
i32.add
(local.set $i)
(br 0)
)
)
(local.get $fib)
return
)
(export "fibonacci" (func $fibonacci))
)

**Activity:** To experiment with the Webassembly program above, first paste the code below

const wasmInstance =
new WebAssembly.Instance(wasmModule, {});
const { fibonacci } = wasmInstance.exports;
console.log(fibonacci(8));

in the lower left window of [wat2wasm demo](https://webassembly.github.io/wabt/demo/wat2wasm/) and the code below in the upper left window.

(module
(func $fibonacci (export "fibonacci") (param $n i32) (result i32)
(local $fib_one i32)
(local $fib_two i32)
(local $fib i32)
(local $i i32)
(i32.const 0)
(local.set $fib_one)
(i32.const 1)
(local.set $fib_two)
(i32.const 0)
(local.set $i)
(block
(loop
(local.get $i)
(local.get $n)
(i32.const 1)
i32.add
i32.lt_s
i32.eqz
(br_if 1)
(local.get $i)
(i32.const 0)
i32.eq
(if
(then (local.get $fib_one) (local.set $fib))
(else
(local.get $i)
(i32.const 1)
i32.eq
(if
(then (local.get $fib_two) (local.set $fib))
(else
(local.get $fib_one)
(local.get $fib_two)
i32.add
(local.set $fib)
(local.get $fib_two)
(local.set $fib_one)
(local.get $fib)
(local.set $fib_two)
)
)
)
)
(local.get $i)
(i32.const 1)
i32.add
(local.set $i)
(br 0)
)
)
(local.get $fib)
return
)
)

In the upper right window, you see the code in binary format. In the lower right window you see the result of the computation.

**Optional Activity:** Can you modify the code in order to print the values of a different sequence such as the triangle numbers?