From 8bc09f04ca12db4a2bf1fcd853e22ab989d250c8 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 11:01:47 -0800 Subject: Chapter 18: Functions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: RobertObkircher --- docs/chapter18/README.md | 238 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 238 insertions(+) create mode 100644 docs/chapter18/README.md (limited to 'docs/chapter18/README.md') diff --git a/docs/chapter18/README.md b/docs/chapter18/README.md new file mode 100644 index 00000000..0fa07818 --- /dev/null +++ b/docs/chapter18/README.md @@ -0,0 +1,238 @@ +# 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