mfl

subset of C implemented in OCaml, compiled to LLVM IR

features

types

• int, bool, void
• char, short, long, long long, unsigned variants
• float, double, long double
• pointer types: int *p
• array types: int a[10]
• multidimensional arrays: int a[3][4]
• variable-length arrays: int a[n]
• flexible array members: struct { int n; int data[]; }
• struct (named, anonymous, typedef-ed)
• bit fields: struct { unsigned int x : 4; }
• union
• enum
• typedef
• function pointer types

operators

• arithmetic: +, -, *, /, %
• bitwise: &, |, ^, ~, <<, >>
• comparison: ==, !=, <, <=, >, >=
• logical: &&, ||, !
• unary negation: -
• operator precedence and associativity
• ternary: ?:
• compound assignment: +=, -=, *=, /=, &=, |=, ^=, <<=, >>=
• increment/decrement: ++, -- (pre and post)
• sizeof
• comma operator

expressions

• integer and boolean literals
• variable references
• assignment as expression (int z = (x = 3))
• function calls
• cast expressions: (int)x
• address-of &x and dereference *p
• subscript a[i]
• member access s.x, s->x
• char literals: 'a'
• string literals: "hello"
• adjacent string literal concatenation: "foo" "bar"
• string escape sequences: \n, \t, \0, \\, \", \xNN
• hex/octal literals: 0xFF, 0777
• integer suffixes: 42UL, 1LL
• simple float literals: 3.14
• exponent float literals: 1e-9
• floating point suffixes: 3.14f, 2.71828L
• compound literals: (int[]){1, 2, 3}, (struct Point){1, 2}

statements

• variable declarations with initializer: int x = 0
• aggregate initializers: int a[] = {1, 2}, struct Point p = {1, 2}
• string-to-array initialization: char s[] = "hello"
• designated initializers: struct Point p = {.x = 1, .y = 2}, int a[5] = {[2] = 7}
• if/else
• while, for
• return
• blocks / compound statements
• break, continue
• do/while
• switch/case/default
• goto and labels
• for with optional init/cond/incr (e.g. for (;;))
• uninitialized declarations: int x;
• multiple declarators: int x = 0, y = 1;

functions

• definitions and calls with parameters
• int, bool, void return types
• implicit return 0 for main, implicit ret void for void functions
• forward declarations: int foo(int x);
• extern declarations
• variadic functions declarations: extern int printf(char* fmt, ...);
• variadic function definitions: va_list, va_start, va_arg, va_end
• (void) parameter list: void foo(void) vs void foo()
• inline functions: inline int square(int x)

scoping

• function scope
• block scoping
• global variables
• static qualifier
• const qualifier
• extern qualifier for variables
• extern qualifier for functions
• volatile qualifier
• restrict qualifier

types

• array-to-pointer decay: int a[10]; int *p = a
• integer promotion and implicit conversion rules
• <stddef.h> types: size_t, ptrdiff_t, offsetof
• <stdint.h> types: int32_t, uint64_t, etc.

comments

• // line comments
• /* */ block comments

preprocessor

• #include
• #define / #undef — object-like and function-like macros
• # stringification and ## token pasting
• variadic macros: #define log(...) __VA_ARGS__
• #ifdef / #ifndef / #if / #elif / #else / #endif
• defined() operator
• #pragma
• #error, #line
• predefined macros: __FILE__, __LINE__, __func__, __DATE__, __TIME__
• multiline macros with \ continuation

other

• NULL
• main function with args: int main(int argc, char *argv[])

usage

# compile and run
dune exec mfl -- run program.mfl

# emit LLVM IR
dune exec mfl -- ir program.mfl

# pretty-print source
dune exec mfl -- format program.mfl

# compile and produce a binary
dune exec mfl -- ir program.mfl | clang -w -x ir - -o program

# run a binary
./program

examples

located under examples/

• factorial.mfl: prints the factorial of 10
• fibonacci.mfl: prints the first 10 Fibonacci numbers
• primes.mfl: prints the primes under 100
• quicksort.mfl: sorts an array of 10 integers using quicksort
• pointers.mfl: pointer arithmetic and dereferencing
• tree.mfl: binary search tree using structs, typedefs, and malloc
• typedefs.mfl: typedef usage examples
• raytracer.mfl: renders a lit scene of colored spheres to a PPM image

testing

# run tests
dune test

# run test with coverage
dune test --instrument-with bisect_ppx --force

sources

initial code is based off of, but written in ocaml instead of haskell: Daniel J. Harvey's blog

resources:

• https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/index.html
• https://blog.josephmorag.com/posts/mcc1/
• https://mapping-high-level-constructs-to-llvm-ir.readthedocs.io/en/latest/
• https://github.com/DoctorWkt/acwj
• a lot of cppreference
• c preprocessor: https://gcc.gnu.org/onlinedocs/cpp/

gadt:

• https://ocaml.org/manual/5.4/gadts-tutorial.html

possible code resources:

• https://github.com/arbipher/llvm-ocaml-tutorial/
• https://github.com/adamrk/llvm-ocaml-tutorial