# Chapter 18: Functions # Table of Contents 1. [FunctionTypes](#function-and-rpc-types) 2. [Return Program Counters](#return-program-counters) 3. [Functions](#functions) 4. [CodeGen - The Compile Driver](#codegen---the-compile-driver) 5. [Graph Visualizer](#graph-visualizer) You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter17...linear-chapter18) it to the previous chapter. I hardly know where to begin! So many things changed here, mostly as indirect consequences of supporting functions. Highlights of the changes: - Function types, and a rework of the type lattice diagrams. - Return Program Counter types, or Return PC or RPC for short. - A distinguished `null` which can be used for functions, RPCs and struct pointers. - Functions themselves can be parsed and evaluated; recursive functions are supported. - Function calls work, call sites can link, and functions can be inlined. - The top-level is now a call to function `main`, and this changed most tests. - A top-level compile driver, which enforces optimization steps. - A local scheduler. - A new evaluator which relies on at code motion, both global and local. - A graphic animated viewer for peepholes. Functions are *not* closures in this chapter; that brings about far more changes and subtle complexities than sensible for such a large chapter. Functions can only refer to out of scope variables if they are some final constant. This generally includes e.g. recursive function pointers. ## Function and RPC Types ``` { argtype, argtype, ... -> rettype } ``` A leading `{` character denotes the start of a function or function type, then a list of argument types, and an arrow `->` and the return type. Functions variables are normal variables and assigned the same way: `functiontype fcn = function-typed-expr;` and function typed variables can be inferred, so `val` and `var` on the left hand side is fine: `val sq = { int x -> x*x; };` Internally, functions have a `TypeTuple` for the arguments, a return `Type`, and a *function index* spelled as a `fidx` in the code. Function indices are unique small dense integers, one per unique function. They are mapped 1-to-1 to the final code address of the generated function code. Function pointers can refer to more than one function with the same signature, and the `TypeFunPtr` tracks this as a bit set with the same tuple for signature and return. Function types can be `null` just like references. Functions cannot return `void`, but they can return `null` and have their return value ignored. A syntactic sugar for void returns may be added in the future. ### Return Program Counters Just like functions have a unique "function index" mapped one to one with function start addresses, call sites generate a unique "return program counter", one per unique call site. These are required for the evaluator to return from functions without itself relying on the implementing language's (e.g. Java) stack. This is the type for such values and `TypeRPC` is very similar to a `TypeFunPtr` except that the signature doesn't matter. In spirit, this is part of a `continuation` and would be required to do IR analysis of a hypothetical `call/cc` operation. That is outside our current scope, so for now these are only used in the evaluator. ## Functions Functions themselves using the same syntax with as function types, but filled in: ``` { flt x, flt y -> // Signature sqrt(x*x+y*y); // Body } ``` Used in a declaration statement: ``` // TYPE VAR = EXPR {flt,flt->flt} dist = { flt x, flt y -> sqrt(x*x+y*y); } ``` With `var`: ``` var dist = { flt x, flt y -> sqrt(x*x*,y*y); } ``` Functions are called in the usual way: `dist( 1.2, 2.3 ) // yields 2.59422435` Functions can have zero arguments, in which case the `->` argument seperator is optional. This allows any section of code to be "thunked" by wrapping it in `{}`. `just5 = { -> 5 } // With arrow` `just5 = { 5 } // Without arrow` Called: `just5() // Returns 5` Functions are always anonymous. When finally assigned to a variable, they will pick up the variable name for debugging and display purposes, but this has no semantics meaning. Here is a function variable referring to more than one anonymous function; the resulting function either doubles or squares: `val fcn = arg ? { int x -> x+x; } : { int x -> x*x; };` `fcn(3) // Prints either 6 or 9, depending on arg` Functions can be recursive: ``` val fact = { int n -> n <=1 ? n : n*fact(n-1); }; return fact(4); // Returns 4! or 24 ``` You can early return as normal out of functions: ``` val find = { int[] es, int e -> for( int i=0; i