closure implementation: first steps

2 files changed, 71 insertions, 209 deletions

diff --git a/doc/gramcurl.txt b/doc/gramcurl.txt
deleted file mode 100755
index 3ac9294c8..000000000
--- a/doc/gramcurl.txt
+++ /dev/null
@@ -1,179 +0,0 @@
-module ::= stmt*
-
-comma ::= ',' [COMMENT] [IND]
-operator ::= OP0 | OR | XOR | AND | OP3 | OP4 | OP5 | OP6 | OP7
-           | 'is' | 'isnot' | 'in' | 'notin'
-           | 'div' | 'mod' | 'shl' | 'shr' | 'not'
-
-prefixOperator ::= OP0 | OP3 | OP4 | OP5 | OP6 | OP7 | 'not'
-
-optInd ::= [COMMENT] [IND]
-
-
-lowestExpr ::= orExpr (OP0 optInd orExpr)*
-orExpr ::= andExpr (OR | 'xor' optInd andExpr)*
-andExpr ::= cmpExpr ('and' optInd cmpExpr)*
-cmpExpr ::= ampExpr (OP3 | 'is' | 'isnot' | 'in' | 'notin' optInd ampExpr)*
-ampExpr ::= plusExpr (OP4 optInd plusExpr)*
-plusExpr ::= mulExpr (OP5 optInd mulExpr)*
-mulExpr ::= dollarExpr (OP6 | 'div' | 'mod' | 'shl' | 'shr' optInd dollarExpr)*
-dollarExpr ::= primary (OP7 optInd primary)*
-
-indexExpr ::= '..' [expr] | expr ['=' expr | '..' expr]
-
-castExpr ::= 'cast' '[' optInd typeDesc [SAD] ']' '(' optInd expr [SAD] ')'
-addrExpr ::= 'addr' '(' optInd expr ')'
-symbol ::= '`' (KEYWORD | IDENT | operator | '(' ')'
-               | '[' ']' | '=' | literal)+ '`'
-         | IDENT
-         
-primaryPrefix ::= (prefixOperator | 'bind') optInd
-primarySuffix ::= '.' optInd symbol
-                | '(' optInd namedExprList [SAD] ')'
-                | '[' optInd [indexExpr (comma indexExpr)* [comma]] [SAD] ']'
-                | '^'
-                | pragma
-
-primary ::= primaryPrefix* (symbol | constructor | castExpr | addrExpr)
-            primarySuffix*
-
-literal ::= INT_LIT | INT8_LIT | INT16_LIT | INT32_LIT | INT64_LIT
-          | FLOAT_LIT | FLOAT32_LIT | FLOAT64_LIT
-          | STR_LIT | RSTR_LIT | TRIPLESTR_LIT
-          | CHAR_LIT
-          | NIL
-
-constructor ::= literal
-          | '[' optInd colonExprList [SAD] ']'
-          | '{' optInd sliceExprList [SAD] '}'
-          | '(' optInd colonExprList [SAD] ')'
-
-colonExpr ::= expr [':' expr]
-colonExprList ::= [colonExpr (comma colonExpr)* [comma]]
-
-namedExpr ::= expr ['=' expr]
-namedExprList ::= [namedExpr (comma namedExpr)* [comma]]
-
-sliceExpr ::= expr ['..' expr]
-sliceExprList ::= [sliceExpr (comma sliceExpr)* [comma]]
-
-exprOrType ::= lowestExpr
-            | 'if' '(' expr ')' expr ('elif' '(' expr ')' expr)* 'else' expr
-            | 'var' exprOrType
-            | 'ref' exprOrType
-            | 'ptr' exprOrType
-            | 'type' exprOrType
-            | 'tuple' tupleDesc
-
-expr ::= exprOrType
-     | 'proc' paramList [pragma] ['=' stmt] 
-
-qualifiedIdent ::= symbol ['.' symbol]
-
-typeDesc ::= exprOrType
-         | 'proc' paramList [pragma]
-
-macroStmt ::= '{' [stmt] '}' ('of' [sliceExprList] stmt
-                         |'elif' '(' expr ')' stmt
-                         |'except' '(' exceptList ')' stmt )*
-                         ['else' stmt]
-
-simpleStmt ::= returnStmt
-             | yieldStmt
-             | discardStmt
-             | raiseStmt
-             | breakStmt
-             | continueStmt
-             | pragma
-             | importStmt
-             | fromStmt
-             | includeStmt
-             | exprStmt
-complexStmt ::= ifStmt | whileStmt | caseStmt | tryStmt | forStmt
-              | blockStmt | asmStmt
-              | procDecl | iteratorDecl | macroDecl | templateDecl | methodDecl
-              | constSection | typeSection | whenStmt | varSection
-
-stmt ::= simpleStmt
-       | indPush (complexStmt | simpleStmt) (';' (complexStmt | simpleStmt))*
-         DED indPop
-
-exprStmt ::= lowestExpr ['=' expr | [expr (comma expr)*] [macroStmt]]
-returnStmt ::= 'return' [expr]
-yieldStmt ::= 'yield' expr
-discardStmt ::= 'discard' expr
-raiseStmt ::= 'raise' [expr]
-breakStmt ::= 'break' [symbol]
-continueStmt ::= 'continue'
-ifStmt ::= 'if' '(' expr ')' stmt ('elif' '(' expr ')' stmt)* ['else' stmt]
-whenStmt ::= 'when' '(' expr ')' stmt ('elif' '(' expr ')' stmt)* ['else' stmt]
-caseStmt ::= 'case' '(' expr ')' ('of' sliceExprList ':' stmt)*
-                               ('elif' '(' expr ')' stmt)*
-                               ['else' stmt]
-whileStmt ::= 'while' '(' expr ')' stmt
-forStmt ::= 'for' '(' symbol (comma symbol)* 'in' expr ['..' expr] ')' stmt
-exceptList ::= [qualifiedIdent (comma qualifiedIdent)*]
-
-tryStmt ::= 'try' stmt
-           ('except' '(' exceptList ')' stmt)*
-           ['finally' stmt]
-asmStmt ::= 'asm' [pragma] (STR_LIT | RSTR_LIT | TRIPLESTR_LIT)
-blockStmt ::= 'block' [symbol] stmt
-filename ::= symbol | STR_LIT | RSTR_LIT | TRIPLESTR_LIT
-importStmt ::= 'import' filename (comma filename)*
-includeStmt ::= 'include' filename (comma filename)*
-fromStmt ::= 'from' filename 'import' symbol (comma symbol)*
-
-pragma ::= '{.' optInd (colonExpr [comma])* [SAD] ('.}' | '}')
-
-param ::= symbol (comma symbol)* (':' typeDesc ['=' expr] | '=' expr)
-paramList ::= ['(' [param (comma param)*] [SAD] ')'] [':' typeDesc]
-
-genericParam ::= symbol [':' typeDesc] ['=' expr]
-genericParams ::= '[' genericParam (comma genericParam)* [SAD] ']'
-
-
-routineDecl := symbol ['*'] [genericParams] paramList [pragma] ['=' stmt]
-procDecl ::= 'proc' routineDecl
-macroDecl ::= 'macro' routineDecl
-iteratorDecl ::= 'iterator' routineDecl
-templateDecl ::= 'template' routineDecl
-methodDecl ::= 'method' routineDecl
-
-colonAndEquals ::= [':' typeDesc] '=' expr
-
-constDecl ::= symbol ['*'] [pragma] colonAndEquals ';' [COMMENT]
-constSection ::= 'const' [COMMENT] (constDecl | '{' constDecl+ '}')
-
-typeDef ::= typeDesc | objectDef | enumDef | 'distinct' typeDesc
-
-objectField ::= symbol ['*'] [pragma]
-objectIdentPart ::= objectField (comma objectField)* ':' typeDesc
-                    [COMMENT|IND COMMENT]
-
-objectWhen ::= 'when' expr ':' [COMMENT] objectPart
-              ('elif' expr ':' [COMMENT] objectPart)*
-              ['else' ':' [COMMENT] objectPart]
-objectCase ::= 'case' expr ':' typeDesc [COMMENT]
-              ('of' sliceExprList ':' [COMMENT] objectPart)*
-              ['else' ':' [COMMENT] objectPart]
-
-objectPart ::= objectWhen | objectCase | objectIdentPart | 'nil'
-             | indPush objectPart (SAD objectPart)* DED indPop
-tupleDesc ::= '[' optInd [param (comma param)*] [SAD] ']'
-
-objectDef ::= 'object' [pragma] ['of' typeDesc] objectPart
-enumField ::= symbol ['=' expr]
-enumDef ::= 'enum' ['of' typeDesc] (enumField [comma] [COMMENT | IND COMMENT])+
-
-typeDecl ::= COMMENT
-           | symbol ['*'] [genericParams] ['=' typeDef] [COMMENT | IND COMMENT]
-
-typeSection ::= 'type' indPush typeDecl (SAD typeDecl)* DED indPop
-
-colonOrEquals ::= ':' typeDesc ['=' expr] | '=' expr
-varField ::= symbol ['*'] [pragma]
-varPart ::= symbol (comma symbol)* colonOrEquals [COMMENT | IND COMMENT]
-varSection ::= 'var' (varPart
-                   | indPush (COMMENT|varPart)
-                     (SAD (COMMENT|varPart))* DED indPop)
diff --git a/doc/intern.txt b/doc/intern.txt
index 86afbb7ba..550976d6f 100755
--- a/doc/intern.txt
+++ b/doc/intern.txt
@@ -218,7 +218,7 @@ Backend issues
 
 However the biggest problem is that dead code elimination breaks modularity! 
 To see why, consider this scenario: The module ``G`` (for example the huge
-Gtk2 module...) is compiled with dead code elimination turned on. So no
+Gtk2 module...) is compiled with dead code elimination turned on. So none
 of ``G``'s procs is generated at all.
 
 Then module ``B`` is compiled that requires ``G.P1``. Ok, no problem,
@@ -366,11 +366,27 @@ comparisons).
 Code generation for closures
 ============================
 
+Code generation for closures is implemented by `lambda lifting`:idx:.
+
+Design
+------
+
+A ``closure`` proc var can call ordinary procs of the default Nimrod calling
+convention. But not the other way round! A closure is implemented as a
+``tuple[prc, data]``. ``data`` can be nil implying a call without a closure.
+This means that a call through a closure generates an ``if`` but the 
+interoperability is worth the cost of the ``if``. Thunk generation would be
+possible too, but it's slightly more effort to implement.
+
+Tests with GCC on Amd64 showed that it's really beneficical if the
+'environment' pointer is passed as the last argument, not as the first argument.
+
+
 Example code:
 
 .. code-block:: nimrod
   proc add(x: int): proc (y: int): int {.closure.} = 
-    return lambda (y: int): int = 
+    return proc (y: int): int = 
       return x + y
 
   var add2 = add(2)
@@ -380,21 +396,21 @@ This should produce roughly this code:
 
 .. code-block:: nimrod
   type
-    PClosure = ref object 
-      fn: proc (x: int, c: PClosure): int
+    PEnv = ref object
       x: int # data
   
-  proc wasLambda(y: int, c: PClosure): int = 
+  proc anon(y: int, c: PClosure): int = 
     return y + c.x
   
-  proc add(x: int): PClosure = 
-    var c: PClosure
-    new(c)
-    c.x = x
-    c.fn = wasLambda
+  proc add(x: int): tuple[prc, data] =
+    var env: PEnv
+    new env
+    env.x = x
+    result = (anon, env)
   
   var add2 = add(2)
-  echo add2.fn(5, add2)
+  let tmp = if add2.data == nil: add2.prc(5) else: add2.prc(5, add2.data)
+  echo tmp
 
 
 Beware of nesting:
@@ -412,36 +428,46 @@ This should produce roughly this code:
 
 .. code-block:: nimrod
   type
-    PClosure1 = ref object 
-      fn: proc (x: int, c: PClosure1): int
+    PEnvX = ref object
       x: int # data
       
-    PClosure2 = ref object 
-      fn: proc (x: int, c: PClosure2): int
+    PEnvY = ref object
       y: int
-      c1: PClosure1
+      ex: PEnvX
       
+  proc lambdaZ(z: int, ey: PEnvY): int =
+    return ey.ex.x + ey.y + z
   
-  proc innerLambda(z: int, c2: PClosure2): int = 
-    return c2.c1.x + c2.y + z
-  
-  proc outerLambda1(y: int, c1: PClosure1): PClosure2 = 
-    new(result)
-    result.c1 = c1
-    result.y = y
-    result.fn = innerLambda
+  proc lambdaY(y: int, ex: PEnvX): tuple[prc, data: PEnvY] =
+    var ey: PEnvY
+    new ey
+    ey.y = y
+    ey.ex = ex
+    result = (lambdaZ, ey)
   
-  proc add(x: int): PClosure1 = 
-    new(result)
-    result.x = x
-    result.fn = outerLambda
+  proc add(x: int): tuple[prc, data: PEnvX] =
+    var ex: PEnvX
+    ex.x = x
+    result = (labmdaY, ex)
   
   var tmp = add(2)
-  var tmp2 = tmp.fn(4, tmp)
-  var add24 = tmp2.fn(4, tmp2)
+  var tmp2 = tmp.fn(4, tmp.data)
+  var add24 = tmp2.fn(4, tmp2.data)
   echo add24(5)
 
 
+We could get rid of nesting environments by always inlining inner anon procs.
+More useful is escape analysis and stack allocation of the environment, 
+however.
+
+
+Alternative
+-----------
+
+Process the closure of all inner procs in one pass and accumulate the 
+environments. This is however not always possible.
+
+
 Accumulator
 -----------
 
@@ -451,3 +477,18 @@ Accumulator
     return lambda: int = 
       inc i
       return i
+      
+  proc p =
+    var delta = 7
+    proc accumulator(start: int): proc(): int =
+      var x = start-1
+      result = proc (): int = 
+        x = x + delta
+        inc delta
+        return x
+    
+    var a = accumulator(3)
+    var b = accumulator(4)
+    echo a() + b()
+
+