「ポーランド記法での四則演算」「関数定義とその実行」「関数の再帰呼び出し」を処理できる minimal な言語処理系の実装 https://www.youtube.com/watch?v=JAtN0TGrNE4

lang.c

#include <stdio.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>

static char *p;
static char func[26][100];

__attribute__((noreturn)) static void error(char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);
    vfprintf(stderr, fmt, ap);
    fprintf(stderr, "\n");
    exit(1);
}

static void read_until(char c, char *buf) {
    for(; *p != c; p++, buf++)
        *buf = *p;
    p++;
    *buf = '\0';
}

static void skip() {
    while (isspace(*p))
        p++;
}

static void expect(char c) {
    if (*p != c)
        error("%c expected: %s", c, p);
    p++;
}

static int eval(int *args);

static int eval_string(char *code, int *args) {
    char *orig = p;
    p = code;
    int val;
    while (*p)
        val = eval(args);
    p = orig;
    return val;
}

static int eval(int *args) {
    skip();

    // Function parameter
    if ('a' <= *p && *p <= 'z') {
        return args[*p++ - 'a'];
    }

    // Function definition
    if ('A' <= *p && *p <= 'Z' && p[1] == '[') {
        char name = *p;
        p += 2;
        read_until(']', func[name - 'A']);
        return eval(args);
    }

    // build-in function
    // "P" print primitive
    if (*p == 'P') {
        p++;
        expect('(');
        int val = eval(args);
        expect(')');
        printf("%d\n", val);
        return val;
    }

    // Function application
    if ('A' <= *p && *p <= 'Z' && p[1] == '(') {
        int newargs[26];
        char name = *p;
        p += 2;

        int i = 0;
        for (skip(); *p != ')'; skip())
            newargs[i++] = eval(args);
        expect(')');
        return eval_string(func[name - 'A'], newargs);
    }

    // Literal numbers
    if (isdigit(*p)) {
        int val = *p++ - '0';
        while (isdigit(*p))
            val = val * 10 + (*p++ - '0');
        return val;
    }

    // Arithmetic operators
    if (strchr("+-*/", *p)) {
        int op = *p++;
        int x = eval(args);
        int y = eval(args);
        switch (op) {
            case '+': return x + y;
            case '-': return x - y;
            case '*': return x * y;
            case '/': return x / y;
        }
    }

    error("invalid character: %c", *p);
}

int main(int argc, char**argv) {
    p = argv[1];
    while(*p)
        printf("%d\n", eval(0));
    return 0;
}

runtest.sh

#!/bin/bash
gcc -std=c11 -o lang lang.c

runtest() {
    output="$(./lang "$1")"
    if [ "$output" != "$2" ]; then
        echo "$1: $2 expected, but got $output"
        exit 1
    fi
    echo "$1 => $output"
}

echo "=== basic ==="
runtest 0 0
runtest 1 1
runtest 99 99

runtest '1 2 3' '1
2
3'

echo "=== arithmestic operators ==="
runtest '+ 1 2' 3
runtest '+ 100 5' 105
runtest '- 5 1' 4
runtest '- 1 5' -4
runtest '* 3 5' 15
runtest '/ 20 5' 4

echo "== nest ==="
runtest '+ + + 1 2 3 4' 10
runtest '+ 1 + 2 + 3 4' 10
runtest '+ 2 * 4 3' 14

echo "=== functions ==="
runtest 'F[+ a a] F(1)' 2
runtest 'F[* a 2] F(5)' 10
runtest 'F[* a a] F(F(2))' 16
runtest 'F[* a a] F(F(F(2)))' 256
runtest 'F[* a b] F(3 5)' 15
runtest 'F[- a 5] G[F(+ a 10)] G(0)' 5

echo "=== build-in function ==="
runtest 'P(5)' '5
5'

echo "=== fibonacci ==="
./lang 'F[P(a) F(b + a b)] F(0 1)' | head

echo OK