"""
在纯粹的、无依赖的 Python 环境中训练和运行 GPT 推理的最原子的（极简的）方法。
这个文件包含了完整的算法。
其他的优化都只是为了提高运行效率而已。

@karpathy
"""

import os       # 检查路径是否存在 (os.path.exists)
import math     # 对数 (math.log) 和指数 (math.exp) 运算
import random   # 随机数种子 (random.seed)，随机选择 (random.choices)，高斯分布 (random.gauss)，随机打乱 (random.shuffle)
random.seed(42) # 让混沌中诞生秩序（固定随机数种子保证可复现）

# 构建数据集 `docs`：包含多个文档（字符串）的列表 (list[str])（例如：一个人名列表）
if not os.path.exists('input.txt'):
    import urllib.request
    names_url = 'https://raw.githubusercontent.com/karpathy/makemore/988aa59/names.txt'
    urllib.request.urlretrieve(names_url, 'input.txt')
docs = [line.strip() for line in open('input.txt') if line.strip()]
random.shuffle(docs)
print(f"num docs: {len(docs)}")

# 构建分词器 (Tokenizer)，用于将字符串和整数序列（“tokens/词元”）相互转换
uchars = sorted(set(''.join(docs))) # 数据集中的唯一字符变成了 token id，范围从 0 到 n-1
BOS = len(uchars) # 序列起始标志 (BOS - Beginning of Sequence) 的特殊 token id
vocab_size = len(uchars) + 1 # 唯一 token 的总数，+1 是为了包含 BOS token
print(f"vocab size: {vocab_size}")

# 构建自动微分 (Autograd) 机制，通过计算图递归应用链式法则求导
class Value:
    __slots__ = ('data', 'grad', '_children', '_local_grads') # Python 优化机制，用于节省内存占用

    def __init__(self, data, children=(), local_grads=()):
        self.data = data                # 在前向传播期间计算的该节点的标量值
        self.grad = 0                   # 损失函数对该节点的导数（梯度），在反向传播期间计算
        self._children = children       # 计算图中该节点的子节点（依赖节点）
        self._local_grads = local_grads # 该节点对其子节点的局部导数

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        return Value(self.data + other.data, (self, other), (1, 1))

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        return Value(self.data * other.data, (self, other), (other.data, self.data))

    def __pow__(self, other): return Value(self.data**other, (self,), (other * self.data**(other-1),))
    def log(self): return Value(math.log(self.data), (self,), (1/self.data,))
    def exp(self): return Value(math.exp(self.data), (self,), (math.exp(self.data),))
    def relu(self): return Value(max(0, self.data), (self,), (float(self.data > 0),))
    def __neg__(self): return self * -1
    def __radd__(self, other): return self + other
    def __sub__(self, other): return self + (-other)
    def __rsub__(self, other): return other + (-self)
    def __rmul__(self, other): return self * other
    def __truediv__(self, other): return self * other**-1
    def __rtruediv__(self, other): return other * self**-1

    def backward(self):
        topo = []
        visited = set()
        def build_topo(v):
            if v not in visited:
                visited.add(v)
                for child in v._children:
                    build_topo(child)
                topo.append(v)
        build_topo(self)
        self.grad = 1
        for v in reversed(topo):
            for child, local_grad in zip(v._children, v._local_grads):
                child.grad += local_grad * v.grad

# 初始化参数，用于存储模型的“知识”
n_layer = 1     # Transformer 神经网络的深度（层数）
n_embd = 16     # 网络的宽度（嵌入维度）
block_size = 16 # 注意力窗口的最大上下文长度（注意：最长的名字是 15 个字符）
n_head = 4      # 注意力头的数量
head_dim = n_embd // n_head # 推导出的每个注意力头的维度
matrix = lambda nout, nin, std=0.08: [[Value(random.gauss(0, std)) for _ in range(nin)] for _ in range(nout)]
state_dict = {'wte': matrix(vocab_size, n_embd), 'wpe': matrix(block_size, n_embd), 'lm_head': matrix(vocab_size, n_embd)}
for i in range(n_layer):
    state_dict[f'layer{i}.attn_wq'] = matrix(n_embd, n_embd)
    state_dict[f'layer{i}.attn_wk'] = matrix(n_embd, n_embd)
    state_dict[f'layer{i}.attn_wv'] = matrix(n_embd, n_embd)
    state_dict[f'layer{i}.attn_wo'] = matrix(n_embd, n_embd)
    state_dict[f'layer{i}.mlp_fc1'] = matrix(4 * n_embd, n_embd)
    state_dict[f'layer{i}.mlp_fc2'] = matrix(n_embd, 4 * n_embd)
params = [p for mat in state_dict.values() for row in mat for p in row] # 将所有参数展平为一个一维列表 list[Value]
print(f"num params: {len(params)}")

# 定义模型架构：一个将 token 和参数映射为预测下一个 token 的 logits（未归一化概率）的函数
# 遵循 GPT 系列中备受推崇的经典 GPT-2 架构，但有一些微小的差异：LayerNorm 改为 RMSNorm，无偏置项，激活函数 GeLU 改为 ReLU
def linear(x, w):
    return [sum(wi * xi for wi, xi in zip(wo, x)) for wo in w]

def softmax(logits):
    max_val = max(val.data for val in logits)
    exps = [(val - max_val).exp() for val in logits]
    total = sum(exps)
    return [e / total for e in exps]

def rmsnorm(x):
    ms = sum(xi * xi for xi in x) / len(x)
    scale = (ms + 1e-5) ** -0.5
    return [xi * scale for xi in x]

def gpt(token_id, pos_id, keys, values):
    tok_emb = state_dict['wte'][token_id] # Token 嵌入 (Token Embedding)
    pos_emb = state_dict['wpe'][pos_id] # 位置嵌入 (Position Embedding)
    x = [t + p for t, p in zip(tok_emb, pos_emb)] # 将 Token 嵌入和位置嵌入相加组合
    x = rmsnorm(x) # 注意：这一步并非多余，因为它涉及到通过残差连接的反向传播

    for li in range(n_layer):
        # 1) 多头注意力机制模块 (Multi-head Attention block)
        x_residual = x
        x = rmsnorm(x)
        q = linear(x, state_dict[f'layer{li}.attn_wq'])
        k = linear(x, state_dict[f'layer{li}.attn_wk'])
        v = linear(x, state_dict[f'layer{li}.attn_wv'])
        keys[li].append(k)
        values[li].append(v)
        x_attn = []
        for h in range(n_head):
            hs = h * head_dim
            q_h = q[hs:hs+head_dim]
            k_h = [ki[hs:hs+head_dim] for ki in keys[li]]
            v_h = [vi[hs:hs+head_dim] for vi in values[li]]
            attn_logits = [sum(q_h[j] * k_h[t][j] for j in range(head_dim)) / head_dim**0.5 for t in range(len(k_h))]
            attn_weights = softmax(attn_logits)
            head_out = [sum(attn_weights[t] * v_h[t][j] for t in range(len(v_h))) for j in range(head_dim)]
            x_attn.extend(head_out)
        x = linear(x_attn, state_dict[f'layer{li}.attn_wo'])
        x = [a + b for a, b in zip(x, x_residual)]
        # 2) 多层感知机模块 (MLP block)
        x_residual = x
        x = rmsnorm(x)
        x = linear(x, state_dict[f'layer{li}.mlp_fc1'])
        x = [xi.relu() for xi in x]
        x = linear(x, state_dict[f'layer{li}.mlp_fc2'])
        x = [a + b for a, b in zip(x, x_residual)]

    logits = linear(x, state_dict['lm_head'])
    return logits

# 构建著名的 Adam 优化器及其相关的动量缓冲区
learning_rate, beta1, beta2, eps_adam = 0.01, 0.85, 0.99, 1e-8
m = [0.0] * len(params) # 一阶动量缓冲区 (平均梯度)
v = [0.0] * len(params) # 二阶动量缓冲区 (梯度平方的平均)

# 按顺序重复训练步骤
num_steps = 1000 # 训练步数
for step in range(num_steps):

    # 取出单个文档，对其进行分词，并在两端加上 BOS 特殊标志 token
    doc = docs[step % len(docs)]
    tokens = [BOS] + [uchars.index(ch) for ch in doc] + [BOS]
    n = min(block_size, len(tokens) - 1)

    # 将 token 序列前向传播通过模型，一直构建到计算出损失 (loss) 的完整计算图
    keys, values = [[] for _ in range(n_layer)], [[] for _ in range(n_layer)]
    losses = []
    for pos_id in range(n):
        token_id, target_id = tokens[pos_id], tokens[pos_id + 1]
        logits = gpt(token_id, pos_id, keys, values)
        probs = softmax(logits)
        loss_t = -probs[target_id].log()
        losses.append(loss_t)
    loss = (1 / n) * sum(losses) # 计算文档序列上的最终平均损失。愿你的 Loss 足够低。

    # 对损失进行反向传播，计算所有模型参数的梯度
    loss.backward()

    # Adam 优化器更新：基于对应的梯度更新模型参数
    lr_t = learning_rate * (1 - step / num_steps) # 线性学习率衰减 (Linear learning rate decay)
    for i, p in enumerate(params):
        m[i] = beta1 * m[i] + (1 - beta1) * p.grad
        v[i] = beta2 * v[i] + (1 - beta2) * p.grad ** 2
        m_hat = m[i] / (1 - beta1 ** (step + 1))
        v_hat = v[i] / (1 - beta2 ** (step + 1))
        p.data -= lr_t * m_hat / (v_hat ** 0.5 + eps_adam)
        p.grad = 0

    print(f"step {step+1:4d} / {num_steps:4d} | loss {loss.data:.4f}", end='\r')

# 推理阶段：愿模型能向我们牙牙学语（生成内容）
temperature = 0.5 # 范围 (0, 1]，控制生成文本的“创造性/随机性”，从低到高
print("\n--- inference (new, hallucinated names) ---")
for sample_idx in range(20):
    keys, values = [[] for _ in range(n_layer)], [[] for _ in range(n_layer)]
    token_id = BOS
    sample = []
    for pos_id in range(block_size):
        logits = gpt(token_id, pos_id, keys, values)
        probs = softmax([l / temperature for l in logits])
        token_id = random.choices(range(vocab_size), weights=[p.data for p in probs])[0]
        if token_id == BOS:
            break
        sample.append(uchars[token_id])
    print(f"sample {sample_idx+1:2d}: {''.join(sample)}")