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/18-grammar.md | 132 +++ docs/chapter18/Makefile | 12 + docs/chapter18/README.md | 238 ++++ docs/chapter18/d3-graphviz.js | 2014 +++++++++++++++++++++++++++++++++ docs/chapter18/d3.v7.min.js | 2 + docs/chapter18/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter18/graphviz.umd.js | 7 + docs/chapter18/index.html | 218 ++++ docs/chapter18/lattice.gv | 203 ++++ docs/chapter18/lattice.svg | 691 +++++++++++ docs/chapter18/lattice2.gv | 85 ++ docs/chapter18/lattice2.svg | 260 +++++ docs/chapter18/webtcp.min.js | 65 ++ 13 files changed, 3927 insertions(+) create mode 100644 docs/chapter18/18-grammar.md create mode 100644 docs/chapter18/Makefile create mode 100644 docs/chapter18/README.md create mode 100644 docs/chapter18/d3-graphviz.js create mode 100644 docs/chapter18/d3.v7.min.js create mode 100644 docs/chapter18/font-awesome-4.7.0.zip create mode 100644 docs/chapter18/graphviz.umd.js create mode 100644 docs/chapter18/index.html create mode 100644 docs/chapter18/lattice.gv create mode 100644 docs/chapter18/lattice.svg create mode 100644 docs/chapter18/lattice2.gv create mode 100644 docs/chapter18/lattice2.svg create mode 100644 docs/chapter18/webtcp.min.js (limited to 'docs/chapter18') diff --git a/docs/chapter18/18-grammar.md b/docs/chapter18/18-grammar.md new file mode 100644 index 00000000..7b611fbf --- /dev/null +++ b/docs/chapter18/18-grammar.md @@ -0,0 +1,132 @@ +# Grammar for Chapter 16 + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | metaStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + +metaStatement : '#showGraph' ';' ; + +structDeclaration : 'struct' IDENTIFIER '{' block '}' ; + +expressionStatement + : type IDENTIFIER ';' + | type IDENTIFIER '=' expression ';' + | IDENTIFIER '=' expression ';' + | expression + ; + +PRIMTYPE + : 'int' + | 'i8' + | 'i16' + | 'i32' + | 'i64' + | 'u8' + | 'u16' + | 'u32' + | 'flt' + | 'f32' + | 'f64' + | 'bool' + ; + +type + : PRIMTYPE + | typeName '?'? + | typeName nestedArray+ + ; + +nestedArray : '?'? '[]'* ; + +typeName : IDENTIFIER ; + + +expression : bitWiseExpression ; + +bitWiseExpression + : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)* + ; + +shiftExpression + : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression postAssign + ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | '(' expression ')' + | 'true' + | 'false' + | 'null' + | newExpression + | IDENTIFIER + ; + +newExpression + : 'new' IDENTIFIER [ '{' block '}' ] + | 'new' IDENTIFIER '[' expression ']' + ; + +postAssign : postFix [ '=' expression ] | [ '#' ]; + +postFix + : '.' IDENTIFIER postFix + | '[' expression ']' postFix + ; + + +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; + +INTEGER_LITERAL + : [1-9]DIGIT* + | [0] + ; + +NON_DIGIT: [a-zA-Z_]; +DIGIT: [0-9]; +``` diff --git a/docs/chapter18/Makefile b/docs/chapter18/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter18/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) 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