The Learning OS · Lego Code Blocks

Program 01

Hello World

Print the string Hello, world! to standard output. The smallest complete program. Establishes how each language enters, exits, and talks to the screen.

▌Haskell

.hs

-- Hello.hs
main :: IO ()
main = putStrLn "Hello, world!"

main :: IO () declares an action that touches the world and yields nothing. putStrLn prints a string and a newline.

▌x86-64 Assembly

.asm

; hello.asm  (nasm -felf64)
section .data
msg db "Hello, world!", 10
len equ $ - msg

section .text
global _start
_start:
    mov rax, 1      ; sys_write
    mov rdi, 1      ; stdout
    mov rsi, msg    ; ptr
    mov rdx, len    ; bytes
    syscall
    mov rax, 60     ; sys_exit
    xor rdi, rdi    ; status 0
    syscall

No runtime library. We talk to the Linux kernel directly through syscall: write the bytes, then exit cleanly.

▌C

.c

/* hello.c */
#include <stdio.h>

int main(void) {
    printf("Hello, world!\n");
    return 0;
}

printf writes to stdout via the C runtime; return 0; tells the OS the program succeeded.

Program 02

Add Two Numbers

Take two integers and print their sum. The arithmetic atom — variables go in, a number comes out.

▌Haskell

.hs

-- Add.hs
main :: IO ()
main = do
  a <- readLn :: IO Int
  b <- readLn :: IO Int
  print (a + b)

Each <- binds the parsed integer to a name. print renders the sum as text and writes it.

▌x86-64 Assembly

.asm

; add.asm  (links with C runtime)
section .data
a   dq 7
b   dq 35
fmt db "%ld", 10, 0

section .text
extern printf
global  main
main:
    mov   rax, [a]
    add   rax, [b]     ; the math
    mov   rsi, rax
    lea   rdi, [rel fmt]
    xor   eax, eax
    call  printf
    xor   eax, eax
    ret

Load a into rax; add places the sum back in rax. The rest is plumbing to print it.

▌C

.c

/* add.c */
#include <stdio.h>

int main(void) {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

scanf parses two integers from stdin into the addresses of a and b. The + happens in a register before printf.

Program 03

Factorial

Compute n! recursively. Introduces the base case and the recursive case — the two halves of every recursive function.

▌Haskell

.hs · function

-- Factorial.hs
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)

.hs · main

main :: IO ()
main = print (factorial 5)

Two equations. Pattern 0 is the base; n binds anything else. The compiler picks the right one by shape, not by branch.

▌x86-64 Assembly

.asm

; factorial.asm  rdi=n -> rax=n!
section .text
global factorial
factorial:
    cmp  rdi, 0
    je   .base
    push rdi            ; save n
    dec  rdi
    call factorial      ; rax = (n-1)!
    pop  rdi            ; restore n
    imul rax, rdi       ; n * (n-1)!
    ret
.base:
    mov  rax, 1
    ret

The stack remembers n across the recursive call. imul multiplies on the way back up.

▌C

.c · function

/* factorial.c */
#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

.c · main

int main(void) {
    printf("%d\n", factorial(5));
    return 0;
}

An if guards the base case. The recursion winds n calls deep and unwinds multiplying.

Program 04

Fibonacci

Compute the nth Fibonacci number recursively: fib n = fib (n-1) + fib (n-2), with fib 0 = 0 and fib 1 = 1.

▌Haskell

.hs · function

-- Fib.hs
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

.hs · main

main :: IO ()
main = print (fib 10)

Three equations, in order. The compiler tries patterns top-down and picks the first that fits.

▌x86-64 Assembly

.asm

; fib.asm  rdi=n -> rax=fib(n)
section .text
global fib
fib:
    cmp  rdi, 2
    jl   .base          ; n < 2 returns n
    push rdi
    dec  rdi
    call fib            ; rax = fib(n-1)
    pop  rdi            ; restore n
    push rax            ; save fib(n-1)
    sub  rdi, 2
    call fib            ; rax = fib(n-2)
    pop  rdx            ; rdx = fib(n-1)
    add  rax, rdx
    ret
.base:
    mov  rax, rdi
    ret

Two recursive calls means two stack saves: first n, then the result of fib(n-1) while we compute fib(n-2).

▌C

.c · function

/* fib.c */
#include <stdio.h>

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

.c · main

int main(void) {
    printf("%d\n", fib(10));
    return 0;
}

A single guard handles both base cases (0 and 1). The compiler turns the recursion into stack frames just like the asm.

Program 05

List Sum

Add up all the integers in a list (or array). The fold pattern in its smallest form.

▌Haskell

.hs · function

-- Sum.hs
sumList :: [Int] -> Int
sumList = foldr (+) 0

.hs · main

main :: IO ()
main = print (sumList [1, 2, 3, 4, 5])

foldr threads (+) from right to left through the list, with 0 as the seed. Point-free style: no argument needed.

▌x86-64 Assembly

.asm

; sum.asm  rdi=ptr, rsi=count -> rax=sum
section .text
global sum_list
sum_list:
    xor  eax, eax       ; total = 0
    xor  rcx, rcx       ; i     = 0
.loop:
    cmp  rcx, rsi
    jge  .done
    add  eax, [rdi + rcx*4]
    inc  rcx
    jmp  .loop
.done:
    ret

rax holds the running total; rcx is the index. Each iteration adds xs[i] (4 bytes per int) to the total.

▌C

.c · function

/* sum.c */
#include <stdio.h>

int sum_list(int *xs, int n) {
    int total = 0;
    for (int i = 0; i < n; i++)
        total += xs[i];
    return total;
}

.c · main

int main(void) {
    int xs[] = {1, 2, 3, 4, 5};
    printf("%d\n", sum_list(xs, 5));
    return 0;
}

A pointer plus a length is C's pragmatic answer to "what is a list?" The accumulator total is the explicit fold seed.

Program 06

String Length

Count the characters in a string. Sounds trivial — but the three languages disagree about what a string IS, and that disagreement IS the lesson.

▌Haskell

.hs · function

-- StrLen.hs
strLength :: String -> Int
strLength = length

.hs · main

main :: IO ()
main = print (strLength "Hello!")

Because String = [Char], the built-in length :: [a] -> Int already does the job. Type-driven reuse.

▌x86-64 Assembly

.asm

; strlen.asm  rdi=ptr -> rax=length
section .text
global my_strlen
my_strlen:
    xor  rax, rax       ; n = 0
.loop:
    cmp  byte [rdi + rax], 0
    je   .done
    inc  rax
    jmp  .loop
.done:
    ret

Walk byte-by-byte. The terminator is the byte 0x00; when we see it, we stop.

▌C

.c · function

/* strlen.c */
#include <stdio.h>

int my_strlen(const char *s) {
    int n = 0;
    while (*s++) n++;
    return n;
}

.c · main

int main(void) {
    printf("%d\n", my_strlen("Hello!"));
    return 0;
}

*s++ reads the byte at s, then advances s by one. The loop ends when the byte is 0 (which is falsy in C).

Program 07

Find Maximum

Return the largest value from a list or array. The accumulator pattern in its purest form.

▌Haskell

.hs · function

-- Max.hs
maxList :: [Int] -> Int
maxList = foldr1 max

.hs · main

main :: IO ()
main = print (maxList [3, 7, 2, 9, 4])

foldr1 uses the FIRST list element as the seed (no zero needed). It crashes on an empty list — the type doesn't protect us from that.

▌x86-64 Assembly

.asm

; max.asm  rdi=ptr, rsi=count -> rax=max
section .text
global max_list
max_list:
    mov  eax, [rdi]     ; best = xs[0]
    mov  rcx, 1
.loop:
    cmp  rcx, rsi
    jge  .done
    mov  edx, [rdi + rcx*4]
    cmp  edx, eax
    jle  .skip
    mov  eax, edx       ; new best
.skip:
    inc  rcx
    jmp  .loop
.done:
    ret

eax is "best so far"; we replace it whenever the next element is greater.

▌C

.c · function

/* max.c */
#include <stdio.h>

int max_list(int *xs, int n) {
    int best = xs[0];
    for (int i = 1; i < n; i++)
        if (xs[i] > best) best = xs[i];
    return best;
}

.c · main

int main(void) {
    int xs[] = {3, 7, 2, 9, 4};
    printf("%d\n", max_list(xs, 5));
    return 0;
}

Seed best with element zero, then sweep forward updating it. Mirrors the asm one-for-one.

Program 08

Reverse a List

Return the list with its elements in reverse order. The functional / imperative split shows up most cleanly here.

▌Haskell

.hs · function

-- Reverse.hs
reverseList :: [a] -> [a]
reverseList = foldl (flip (:)) []

.hs · main

main :: IO ()
main = print (reverseList [1, 2, 3, 4, 5])

Cons each element onto the front of an accumulator list. Walking left builds a list in opposite order — that IS the reverse.

▌x86-64 Assembly

.asm

; reverse.asm  rdi=ptr, rsi=count
;   in-place; no return value
section .text
global reverse
reverse:
    xor  rcx, rcx       ; i = 0
    mov  rdx, rsi
    dec  rdx            ; j = n-1
.loop:
    cmp  rcx, rdx
    jge  .done
    mov  eax, [rdi + rcx*4]
    mov  r8d, [rdi + rdx*4]
    mov  [rdi + rcx*4], r8d
    mov  [rdi + rdx*4], eax
    inc  rcx
    dec  rdx
    jmp  .loop
.done:
    ret

Two pointers, i from the left and j from the right, swap and march toward each other.

▌C

.c · function

/* reverse.c */
#include <stdio.h>

void reverse(int *xs, int n) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int t = xs[i];
        xs[i] = xs[j];
        xs[j] = t;
    }
}

.c · main

int main(void) {
    int xs[] = {1, 2, 3, 4, 5};
    reverse(xs, 5);
    for (int i = 0; i < 5; i++) printf("%d ", xs[i]);
    printf("\n");
    return 0;
}

Same two-pointer dance, with a temporary t holding one value during each swap. The original array is gone.

Program 09

Linear Search

Find the index of the first occurrence of a value in a list. Return either the index or "not found."

▌Haskell

.hs · function

-- Search.hs
import Data.List (findIndex)

findIdx :: Int -> [Int] -> Maybe Int
findIdx target = findIndex (== target)

.hs · main

main :: IO ()
main = print (findIdx 7 [3, 7, 2, 9, 4])
-- prints: Just 1

findIndex returns a Maybe Int. There is no "magic number" for failure — failure is its own value, Nothing.

▌x86-64 Assembly

.asm

; search.asm
;   rdi=ptr, rsi=count, rdx=target
;   rax = index, or -1 on miss
section .text
global find_idx
find_idx:
    xor  rcx, rcx
.loop:
    cmp  rcx, rsi
    jge  .miss
    mov  eax, [rdi + rcx*4]
    cmp  eax, edx
    je   .hit
    inc  rcx
    jmp  .loop
.hit:
    mov  rax, rcx
    ret
.miss:
    mov  rax, -1
    ret

Two exits: .hit returns the index, .miss returns -1. The caller has to know what -1 means.

▌C

.c · function

/* search.c */
#include <stdio.h>

int find_idx(int *xs, int n, int target) {
    for (int i = 0; i < n; i++)
        if (xs[i] == target) return i;
    return -1;
}

.c · main

int main(void) {
    int xs[] = {3, 7, 2, 9, 4};
    printf("%d\n", find_idx(xs, 5, 7));
    return 0;
}

Walk forward, return the index on first match, fall through to the sentinel -1 otherwise.

Program 10

Traffic Light State Machine

Cycle through three states: Red → Green → Yellow → Red. The smallest finite state machine.

▌Haskell

.hs · type + function

-- Light.hs
data Light = Red | Green | Yellow
  deriving Show

next :: Light -> Light
next Red    = Green
next Green  = Yellow
next Yellow = Red

.hs · main

main :: IO ()
main = mapM_ print
       (take 4 (iterate next Red))

data Light = ... creates a brand-new type with three legal values. iterate next Red is the infinite stream Red, Green, Yellow, Red, ...; we take 4.

▌x86-64 Assembly

.asm

; light.asm
;   rdi = current  (0=R, 1=G, 2=Y)
;   rax = next
section .text
global next_light
next_light:
    cmp  rdi, 0
    je   .toGreen
    cmp  rdi, 1
    je   .toYellow
    xor  rax, rax       ; Yellow -> Red (0)
    ret
.toGreen:
    mov  rax, 1
    ret
.toYellow:
    mov  rax, 2
    ret

"States" are just numbers. The CPU has no opinion about whether 1 means GREEN — that's a contract between us and our future self.

▌C

.c · type + function

/* light.c */
#include <stdio.h>

typedef enum {
    RED, GREEN, YELLOW
} Light;

Light next(Light l) {
    switch (l) {
        case RED:    return GREEN;
        case GREEN:  return YELLOW;
        case YELLOW: return RED;
    }
    return RED;  /* unreachable */
}

.c · main

int main(void) {
    Light l = RED;
    for (int i = 0; i < 4; i++) {
        printf("%d\n", l);
        l = next(l);
    }
    return 0;
}

enum gives names to the integers 0, 1, 2. The return RED; at the bottom is a polite lie the compiler demands — the switch already covers every case.