From eee5b806fabae0b480ff7d41159369c5a457d014 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 11:01:47 -0800 Subject: Chapter 18: Functions --- Makefile | 9 +- README.md | 2 +- docs/chapter18/18-grammar.md | 132 ++ docs/chapter18/Makefile | 12 + docs/chapter18/README.md | 231 +++ 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 + src/main/java/com/seaofnodes/simple/Ary.java | 36 +- src/main/java/com/seaofnodes/simple/CodeGen.java | 123 ++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 36 +- .../com/seaofnodes/simple/GraphVisualizer.java | 20 +- src/main/java/com/seaofnodes/simple/IRPrinter.java | 170 +- src/main/java/com/seaofnodes/simple/IterPeeps.java | 7 +- src/main/java/com/seaofnodes/simple/JSViewer.java | 394 ++++ .../java/com/seaofnodes/simple/ListScheduler.java | 110 ++ src/main/java/com/seaofnodes/simple/Parser.java | 648 +++++-- src/main/java/com/seaofnodes/simple/SB.java | 74 + .../com/seaofnodes/simple/SimpleWebSocket.java | 148 ++ src/main/java/com/seaofnodes/simple/Var.java | 55 + .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/AndNode.java | 20 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 17 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 34 +- .../java/com/seaofnodes/simple/node/CProjNode.java | 6 +- .../com/seaofnodes/simple/node/CallEndNode.java | 92 + .../java/com/seaofnodes/simple/node/CallNode.java | 142 ++ .../java/com/seaofnodes/simple/node/CastNode.java | 22 +- .../com/seaofnodes/simple/node/ConstantNode.java | 16 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 14 + .../java/com/seaofnodes/simple/node/DivNode.java | 1 - .../java/com/seaofnodes/simple/node/FRefNode.java | 35 + .../java/com/seaofnodes/simple/node/FunNode.java | 133 ++ .../java/com/seaofnodes/simple/node/IfNode.java | 18 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 35 +- .../com/seaofnodes/simple/node/LogicalNode.java | 29 + .../java/com/seaofnodes/simple/node/LoopNode.java | 48 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 156 ++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 18 +- .../com/seaofnodes/simple/node/MinusFNode.java | 2 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 10 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 11 +- .../java/com/seaofnodes/simple/node/MultiUse.java | 5 + .../java/com/seaofnodes/simple/node/NewNode.java | 8 +- src/main/java/com/seaofnodes/simple/node/Node.java | 60 +- .../java/com/seaofnodes/simple/node/NotNode.java | 24 +- .../java/com/seaofnodes/simple/node/OrNode.java | 20 +- .../java/com/seaofnodes/simple/node/OutNode.java | 7 - .../java/com/seaofnodes/simple/node/ParmNode.java | 47 + .../java/com/seaofnodes/simple/node/PhiNode.java | 66 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 16 +- .../com/seaofnodes/simple/node/RegionNode.java | 28 +- .../com/seaofnodes/simple/node/ReturnNode.java | 104 +- .../java/com/seaofnodes/simple/node/SarNode.java | 23 +- .../com/seaofnodes/simple/node/ScopeMinNode.java | 150 -- .../java/com/seaofnodes/simple/node/ScopeNode.java | 166 +- .../java/com/seaofnodes/simple/node/ShlNode.java | 25 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 18 +- .../java/com/seaofnodes/simple/node/StartNode.java | 16 +- .../java/com/seaofnodes/simple/node/StopNode.java | 40 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 27 +- .../com/seaofnodes/simple/node/StructNode.java | 3 +- .../java/com/seaofnodes/simple/node/SubNode.java | 7 +- .../com/seaofnodes/simple/node/ToFloatNode.java | 10 +- .../java/com/seaofnodes/simple/node/XCtrlNode.java | 4 +- .../java/com/seaofnodes/simple/node/XorNode.java | 21 +- .../java/com/seaofnodes/simple/type/Field.java | 17 +- src/main/java/com/seaofnodes/simple/type/Type.java | 105 +- .../java/com/seaofnodes/simple/type/TypeFloat.java | 99 +- .../com/seaofnodes/simple/type/TypeFunPtr.java | 140 ++ .../com/seaofnodes/simple/type/TypeInteger.java | 89 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 41 +- .../com/seaofnodes/simple/type/TypeMemPtr.java | 97 +- .../java/com/seaofnodes/simple/type/TypeNil.java | 62 + .../java/com/seaofnodes/simple/type/TypePtr.java | 53 + .../java/com/seaofnodes/simple/type/TypeRPC.java | 100 + .../com/seaofnodes/simple/type/TypeStruct.java | 36 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 72 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 21 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 34 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 44 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 37 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 97 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 73 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 116 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 100 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 87 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 135 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 135 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 103 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 34 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 136 +- .../java/com/seaofnodes/simple/Chapter14Test.java | 121 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 163 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 128 +- .../java/com/seaofnodes/simple/Chapter17Test.java | 359 ++-- .../java/com/seaofnodes/simple/Chapter18Test.java | 328 ++++ src/test/java/com/seaofnodes/simple/Eval2.java | 446 +++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 2 +- .../java/com/seaofnodes/simple/MergeSortTest.java | 65 + .../java/com/seaofnodes/simple/SchedulerTest.java | 18 +- src/test/java/com/seaofnodes/simple/TypeTest.java | 45 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 61 +- .../com/seaofnodes/simple/evaluator/Scheduler.java | 63 +- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 48 +- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 11 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 5 +- 114 files changed, 9264 insertions(+), 2170 deletions(-) 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 create mode 100644 src/main/java/com/seaofnodes/simple/CodeGen.java create mode 100644 src/main/java/com/seaofnodes/simple/JSViewer.java create mode 100644 src/main/java/com/seaofnodes/simple/ListScheduler.java create mode 100644 src/main/java/com/seaofnodes/simple/SB.java create mode 100644 src/main/java/com/seaofnodes/simple/SimpleWebSocket.java create mode 100644 src/main/java/com/seaofnodes/simple/Var.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CallEndNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CallNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/CtrlNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/FRefNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/FunNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/LogicalNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MemMergeNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MultiUse.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/OutNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ParmNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeNil.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypePtr.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeRPC.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter18Test.java create mode 100644 src/test/java/com/seaofnodes/simple/Eval2.java create mode 100644 src/test/java/com/seaofnodes/simple/MergeSortTest.java diff --git a/Makefile b/Makefile index c14ffa27..f42659de 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,7 @@ SHELL := /bin/bash .DELETE_ON_ERROR: + # for printing variable values # usage: make print-VARIABLE # > VARIABLE = value_of_variable @@ -67,13 +68,19 @@ JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" tests: $(default_targets) @echo "testing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap + @$(JVM) org.junit.runner.JUnitCore $(test_cp) + @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap fuzzer: $(default_targets) @echo "fuzzing " $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +# Launch viewer +view: $(main_classes) + @echo "viewing " + @$(JVM) com.seaofnodes.simple.JSViewer + .PHONY: clean clean: rm -rf build diff --git a/README.md b/README.md index 724480a3..4808b0ab 100644 --- a/README.md +++ b/README.md @@ -55,5 +55,5 @@ The Simple language will be styled after a subset of C or Java * [Chapter 15](docs/chapter15/README.md): One dimensional static length array type, with array loads and stores. * [Chapter 16](docs/chapter16/README.md): Constructors * [Chapter 17](docs/chapter17/README.md): Mutability & Syntax Sugar: `var`, `val`, `x+=y`, `for(init;test;next)body` -* Chapter 18: Functions and calls. +* [Chapter 18](docs/chapter18/README.md): Functions and calls. * Chapter 19: Code gen to X86-64. 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..031ce589 --- /dev/null +++ b/docs/chapter18/README.md @@ -0,0 +1,231 @@ +# Chapter 18: Functions + + +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: + +``` +{ int x, int y -> + sqrt(x*x+y*y); +} +``` + +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