{"id":6,"date":"2008-06-07T19:52:01","date_gmt":"2008-06-08T02:52:01","guid":{"rendered":"http:\/\/cogblog.mirandabanda.org\/?p=4"},"modified":"2017-03-09T13:16:46","modified_gmt":"2017-03-09T21:16:46","slug":"closures-part-i","status":"publish","type":"post","link":"http:\/\/www.mirandabanda.org\/cogblog\/2008\/06\/07\/closures-part-i\/","title":{"rendered":"Closures Part I"},"content":{"rendered":"

BlueBook BlockContexts<\/a> are nearly closures.\u00c2\u00a0 They close-over their enclosing environment, providing access to an enclosing method’s arguments and temporary variables.\u00c2\u00a0 But they lack their own local environment, hijacking their method activation’s (or home context’s) temps to store their own arguments and temporaries (let’s call these locals).\u00c2\u00a0 Worse still, they’re not reentrant. \u00c2\u00a0BTW, “the home context” is the terminology for the activation record of a method. \u00c2\u00a0All blocks get created within some method activation (or within a block activation nested within a method activation). \u00c2\u00a0The method activation in which a block is created is called the block’s home context.<\/p>\n

Try the following in Squeak<\/a> prior to Squeak 4.x, and in VisualWorks<\/a>:<\/p>\n

\t        | factorial |
\n\t        factorial := [:n| n = 1 ifTrue: [1] ifFalse: [(factorial value: n – 1) * n]].
\n\t        (1 to: 10) collect: factorial<\/font>
<\/body>
\nIn VisualWorks you get #(1 2 6 24 120 720 5040 40320 362880 3628800).\u00c2\u00a0 In Squeak you get a Notifier proclaiming “Error: Attempt to evaluate a block that is already being evaluated.”\u00c2\u00a0 The Squeak code fails because in a Blue Book VM an unevaluated block is an activation record, a BlockContext, that has a sender field used to refer to the block’s caller.\u00c2\u00a0 You can inspect or explore the block to see it.\u00c2\u00a0 Here’s an explorer on it:<\/p>\n

\"\"<\/p>\n

You can see the block is referrered to from the first temporary of the home context “| factorial |”.\u00c2\u00a0 You can see its sender field which is used to refer to the calling context, the context that sends value: to the block to evaluate it. The block can’t be reentered without overwriting the sender field, preventing return to the first caller.<\/p>\n

OK, let’s deal with the reentrancy problem.\u00c2\u00a0 Simply evaluating a copy of the block instead of the original produces a fresh activation record for each activation of the block.\u00c2\u00a0 This is what Allen Wirfs-Brock’s team did in the Tektronix implementation on the 4404 back in the ’80’s.\u00c2\u00a0 They modified the BlockContext>>value[:value:…] primitives to activate a copy of the receiver.\u00c2\u00a0 Let’s try modifying the example with explicit copies:<\/p>\n

\t        | factorial |
\n\t        factorial := [:n| n = 1 ifTrue: [1] ifFalse: [(factorial copy value: n – 1) * n]].
\n\t        (1 to: 10) collect: factorial copy #(1 1 1 1 1 1 1 1 1 1)<\/font>
<\/body>
\nwhich answers… #(1 1 1 1 1 1 1 1 1 1) ?!?!<\/strong><\/p>\n

That’s because the above is actually compiled to code equivalent to<\/p>\n

\t        | factorial n |
\n\t        factorial := [:factorialsArgument|
\n                 n := factorialsArgument.
\n                 n = 1 ifTrue: [1] ifFalse: [(factorial copy value: n – 1) * n]].
\n\t        (1 to: 10) collect: factorial copy<\/font>
<\/body>
\nbecause with BlueBook BlockContexts all temporaries are stored in the temporary frame of the home context.\u00c2\u00a0 In the explorer above the “2: nil” field in the home context is the slot used to store the block’s argument “:n|”.<\/p>\n

By the time we’ve recursed to the base case with n = 1 we’ve overwritten n with 1 in all the ” * n”‘s, and so end up evaluating 1 * 1 * 1 ….<\/p>\n

This way round works as intended:<\/p>\n

\t        | factorial n |
\n\t        factorial := [:factorialsArgument|
\n                 n := factorialsArgument.
\n                 n = 1 ifTrue: [1] ifFalse: [n * (factorial copy value: n – 1)]].
\n\t        (1 to: 10) collect: factorial copy<\/font>
<\/body>
\nanswers #(1 2 6 24 120 720 5040 40320 362880 3628800), because in “n * (factorial copy value: n – 1)” n is pushed on the stack before the recursion due to Smalltalk’s strict left-to-right evaluation rule.<\/p>\n

Whether you think this is a big deal or not its not ANSI-compliant so we’ve got to fix it right? \u00c2\u00a0I’m all for standards, and for me not having closures is an issue.\u00c2\u00a0 It gets in the way of self-expression. \u00c2\u00a0It is useful to have recursive blocks.\u00c2\u00a0 And with Smalltalk’s system building machinery it is easy to fix. \u00c2\u00a0But its not a huge issue; Squeak has done without closures for thirty years. \u00c2\u00a0However,\u00c2\u00a0there are also pragmatic reasons for fixing this. \u00c2\u00a0Closures are an enabler for efficient implementation of context-to-stack mapping, something to be explained in an upcoming post, which will speed-up the interpreter as well as the fast VM.\u00c2\u00a0 In fact so effective is the form of this optimization that I plan to implement that when I reimplemented VisualWorks’ closures using it execution of block-intensive code such as exception handling sped up by a factor of two. \u00c2\u00a0These specifics are why I chose to do my own closure implementation instead of reusing Anthony Hannan’s one<\/a>.<\/p>\n

Implementing Closures<\/strong><\/h3>\n

Implementing closures is straight-forward.\u00c2\u00a0 We need three things.\u00c2\u00a0 One is to defer creating the activation of the block until we send value:.\u00c2\u00a0 So creating the block results in creating something, a BlockClosure, from which we can create an activation later on.\u00c2\u00a0 Another is the ability for a block activation to hold local arguments and temporaries.\u00c2\u00a0 We already have something that can do this, its called MethodContext :).\u00c2\u00a0 Finally we need a way of accessing locals in enclosing block or method activations.\u00c2\u00a0 This has already been done for Squeak.\u00c2\u00a0 Anthony Hannan did a closure implementation which exists in a rump form in 3.8.\u00c2\u00a0 But I didn’t use it because for efficient context-to-stack mapping I want one key ingredient which is to implement access to locals in enclosing activations without access through those activations.<\/p>\n

To explain the scheme, which is used in some Lisp compilers, let’s look at the following:<\/p>\n

counterBlock<\/b>
\n\t        | count |
\n\t        count := 0.
\n\t        [ count := count + 1].<\/font>
<\/body>
\nIf counter is stored on the stack of the method activation of counterBlock then there’s a problem if activations are mapped to stack frames for the duration of their execution.\u00c2\u00a0 Up until the block is returned counter can live happily on some native stack frame created when counterBlock was sent.\u00c2\u00a0 But since the block [counter := counter + 1] outlives the execution of counterBlock we must preserve the value of counter for subsequent evaluations of the block.\u00c2\u00a0 Since we have contexts the thing to do is to create a context object and associate it with the frame when creating a block that accesses the frame, and to write back the contents of the stack frame into its context when a frame that has a context is returned from.\u00c2\u00a0 The sad thing is that this return-time processing is very slow.<\/p>\n

What we need to do is to break the dependency between the block activation and its enclosing contexts for accessing locals.\u00c2\u00a0 I’m going to use Collection>>inject:into: as an example.<\/p>\n

Collection methods for enumerating<\/i>
\ninject:<\/b> thisValue<\/font> into:<\/b> binaryBlock<\/font>
\n\t        <\/font>"Accumulate a running value associated with evaluating the argument,
\n\t        binaryBlock, with the current value of the argument, thisValue, and the
\n\t        receiver as block arguments. For instance, to sum the numeric elements of
\n\t        a collection, aCollection inject: 0 into: [:subTotal :next | subTotal + next]."<\/font><\/p>\n

\t        <\/font>|<\/font> <\/font>nextValue<\/font> <\/font>|<\/font>
\n\t        <\/font>nextValue<\/font> <\/font>:=<\/b> <\/font>thisValue<\/font>.
\n\t        <\/font>self<\/font> <\/font>do:<\/font> [:<\/font>each<\/font> <\/font>|<\/font> <\/font>nextValue<\/font> <\/font>:=<\/b> <\/font>binaryBlock<\/font> <\/font>value:<\/font> <\/font>nextValue<\/font> <\/font>value:<\/font> <\/font>each<\/font>].
\n\t        <\/font>^<\/font>nextValue<\/font><\/font>
<\/body>
\nThe block\u00c2\u00a0 [:each | nextValue := binaryBlock value: nextValue value: each] reads the method argument binaryBlock and reads and writes nextValue.\u00c2\u00a0 If we allocate an explicit array to hold nextValue indirectly (something I’m going to call an “indirect temp vector”) we can avoid writing the local in the method activation:<\/p>\n

inject:<\/b> thisValue<\/font> <\/font>into:<\/b><\/font> <\/font>binaryBlock<\/font>
\n\t        <\/font>|<\/font> <\/font>indirectTemps<\/font> <\/font>|<\/font>
\n\t        <\/font>indirectTemps<\/font> <\/font>:=<\/b> Array <\/font>new:<\/font> <\/font>1<\/font>.
\n\t        <\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>thisValue<\/font>. <\/font>" was nextValue := thisValue."<\/font>
\n\t        <\/font>self<\/font> <\/font>do:<\/font> [:<\/font>each<\/font> <\/font>|<\/font>
\n\t        \t        <\/font>indirectTemps<\/font>
\n\t        \t        \t        <\/font>at:<\/font> <\/font>1<\/font>
\n\t        \t        \t        <\/font>put:<\/font> <\/font>(<\/font>binaryBlock<\/font>
\n\t        \t        \t        \t        \t        <\/font>value:<\/font> <\/font>(<\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font>)<\/font>
\n\t        \t        \t        \t        \t        <\/font>value:<\/font> <\/font>each<\/font>)<\/font>].
\n\t        <\/font>^<\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font><\/font>
<\/body>
\nNow the block only reads the locals of the method activation, and none of the locals it reads changes value after the block is created.\u00c2\u00a0 So the block can keep a private copy of those values without affecting semantics.\u00c2\u00a0 The compiler does this behind the scenes but the code is somewhat equivalent to<\/p>\n

inject:<\/b> thisValue<\/font> <\/font>into:<\/b><\/font> <\/font>binaryBlock<\/font>
\n\t        <\/font>|<\/font> <\/font>indirectTemps<\/font> <\/font>|<\/font>
\n\t        <\/font>indirectTemps<\/font> <\/font>:=<\/b> Array <\/font>new:<\/font> <\/font>1<\/font>.
\n\t        <\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>thisValue<\/font>.
\n\t        <\/font>self<\/font> <\/font>do:<\/font> (<\/font>thisContext<\/font>
\n\t        \t        \t        \t        <\/font>closureCopy:<\/font>
\n\t        \t        \t        \t        \t        <\/font>[<\/font>:<\/font>each<\/font> <\/font>|<\/font> <\/font>|<\/font> <\/font>binaryBlockCopy<\/font> <\/font>indirectTempsCopy<\/font> <\/font>|<\/font>
\n\t        \t        \t        \t        \t        <\/font>indirectTempsCopy<\/font>
\n\t        \t        \t        \t        \t        \t        <\/font>at:<\/font> <\/font>1<\/font>
\n\t        \t        \t        \t        \t        \t        <\/font>put:<\/font> <\/font>(<\/font>binaryBlockCopy<\/font>
\n\t        \t        \t        \t        \t        \t        \t        \t        <\/font>value:<\/font> <\/font>(<\/font>indirectTempsCopy<\/font> <\/font>at:<\/font> <\/font>1)<\/font>
\n\t        \t        \t        \t        \t        \t        \t        \t        <\/font>value:<\/font> <\/font>each<\/font>)<\/font>]<\/font>
\n\t        \t        \t        \t        <\/font>copiedValues:<\/font> <\/font>(<\/font>Array <\/font>with:<\/font> <\/font>binaryBlock<\/font> <\/font>with:<\/font> <\/font>indirectTemps<\/font>)<\/font>).
\n\t        <\/font>^<\/font>indirectTemps<\/font> <\/font>at:<\/font> <\/font>1<\/font><\/font>
<\/body>
\nclosureCopy:copiedValues: answers a BlockClosure that holds the pc in the method to start executing the block’s code (just like BlockContext’s startpc) and the array of copiedValues.\u00c2\u00a0 When the block is activated the copiedValues are pushed onto the activation’s stack after any block arguments, becoming locals of the activation.\u00c2\u00a0 Now there is no dependency on the enclosing activation for local access.\u00c2\u00a0 Nothing needs to happen when returning from an activation that encloses some closure so returns are simple and hence fast.<\/p>\n

The compiler analysis to do this is extremely simple.\u00c2\u00a0 Any local that is accessed by an inner scope must either be copied or put in an indirect temp vector.\u00c2\u00a0 If a local is assigned to after it is closed over (after a block is created that accesses the local) then the local must be made indirect.\u00c2\u00a0 We can do slightly better than this, but its not worth the effort.\u00c2\u00a0 This simple analysis works fine.\u00c2\u00a0 I’ll detail the analysis in a post on the closure compiler and its resultant bytecodes.\u00c2\u00a0 Note that we only need one indirect temp vector per scope, it needs an element to each indirect local.<\/p>\n

Prototyping The Implementation<\/h3>\n

The above facilities, creating a closure, creating an indirect temp vector and reading and writing from it, and the evaluation primitives all make sense when implemented in the VM with specific bytecodes and primitives.\u00c2\u00a0 But one thing that’s very nice about Smalltalk is that one can prototype the above scheme _without_ any VM modifications.\u00c2\u00a0 We can’t prototype non-local return wthout trickery but blocks like factorial above work fine.\u00c2\u00a0 I did just this before I implemented the closure bytecodes.\u00c2\u00a0 For example here’s the implementations of closureCopy:copiedValues:, the message one can use to create Closures, and value:, one of the evaluation primitives that can be written in pure Smalltalk due to it having first-class activation records.\u00c2\u00a0 Neat!<\/p>\n

Object subclass:<\/font> <\/font>#BlockClosure<\/font>
\n\t        <\/font>instanceVariableNames:<\/font> <\/font>‘outerContext startpc numArgs copiedValues’<\/font>
\n\t        <\/font>classVariableNames:<\/font> <\/font>”<\/font>
\n\t        <\/font>poolDictionaries:<\/font> <\/font>”<\/font>
\n\t        <\/font>category:<\/font> <\/font>‘Kernel-Methods’<\/p>\n

<\/font>ContextPart methods for controlling<\/i>
\nclosureCopy:<\/b> <\/font>numArgs<\/font> <\/font>copiedValues:<\/b> <\/font>anArray<\/font>
\n\t        <\/font>"Distinguish a block of code from its enclosing method by
\n\t         creating a BlockClosure for that block. The compiler inserts into all
\n\t         methods that contain blocks the bytecodes to send the message
\n\t         closureCopy:copiedValues:. Do not use closureCopy:copiedValues: in code that you write! Only the
\n\t         compiler can decide to send the message closureCopy:copiedValues:."<\/font><\/p>\n

\t        <\/font>^<\/font>BlockClosure <\/font>new<\/font> <\/font>outerContext:<\/font> <\/font>self<\/font> <\/font>startpc:<\/font> pc <\/font>+<\/font> <\/font>2<\/font> <\/font>numArgs:<\/font> <\/font>numArgs<\/font> <\/font>copiedValues:<\/font> <\/font>anArray<\/font><\/p>\n

BlockClosure methods for evaluating<\/i>
\nvalue:<\/b> <\/font>anArg<\/font>
\n\t        <\/font>"Activate the receiver, creating a closure activation (MethodContext)
\n\t         whose closure is the receiver and whose caller is the sender of this message.
\n\t         Supply the argument and copied values to the activation as its arguments and copied temps."<\/font>
\n\t        <\/font>|<\/font> <\/font>newContext<\/font> <\/font>sz<\/font> <\/font>|<\/font>
\n\t        numArgs <\/font>~=<\/font> <\/font>1<\/font> <\/font>ifTrue:<\/font>
\n\t        \t        [<\/font>self<\/font> <\/font>numArgsError:<\/font> <\/font>1<\/font>].
\n\t        <\/font>newContext<\/font> <\/font>:=<\/b> <\/font>self<\/font> <\/font>asContextWithSender:<\/font> <\/font>thisContext<\/font> <\/font>sender<\/font>.
\n\t        <\/font>sz<\/font> <\/font>:=<\/b> copiedValues <\/font>basicSize<\/font>.
\n\t        <\/font>newContext<\/font> <\/font>stackp:<\/font> <\/font>sz<\/font> <\/font>+<\/font> <\/font>1<\/font>.
\n\t        <\/font>newContext<\/font> <\/font>at:<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>anArg<\/font>.
\n\t        <\/font>sz<\/font> <\/font>><\/font> <\/font>0<\/font> <\/font>ifTrue:<\/font> <\/font>"nil basicSize = 0"<\/font>
\n\t        \t        [<\/font>1<\/font> <\/font>to:<\/font> copiedValues <\/font>basicSize<\/font> <\/font>do:<\/font>
\n\t        \t        \t        <\/font>[<\/font>:<\/font>i<\/font>|<\/font> <\/font>newContext<\/font> <\/font>at:<\/font> <\/font>i<\/font> <\/font>+<\/font> <\/font>1<\/font> <\/font>put:<\/font> <\/font>(<\/font>copiedValues <\/font>at:<\/font> <\/font>i<\/font>)<\/font>]<\/font>].
\n\t        <\/font>thisContext<\/font> <\/font>privSender:<\/font> <\/font>newContext<\/p>\n

<\/font>BlockClosure methods for private<\/i>
\nasContextWithSender:<\/b> <\/font>aContext<\/font>
\n\t        <\/font>"Inner private support method for evauation. Do not use unless you know what you’re doing."<\/font><\/p>\n

\t        <\/font>^<\/font>(MethodContext <\/font>newForMethod:<\/font> outerContext <\/font>method<\/font>)
\n\t        \t        <\/font>setSender:<\/font> <\/font>aContext<\/font>
\n\t        \t        <\/font>receiver:<\/font> outerContext <\/font>receiver<\/font>
\n\t        \t        <\/font>method:<\/font> outerContext <\/font>method<\/font>
\n\t        \t        <\/font>closure:<\/font> <\/font>self<\/font>
\n\t        \t        <\/font>startpc:<\/font> startpc<\/font><\/font>
<\/body>
\n\u00c2\u00a0
\nand here’s the decompilation of factorial compiled using the prototype compiler:<\/p>\n

\t        | t1 |
\n\t        t1 := Array new: 1.
\n\t        t1
\n\t        \t        at: 1
\n\t        \t        put: [:t2 | t2 = 1
\n\t        \t        \t        \t        ifTrue: [1]
\n\t        \t        \t        \t        ifFalse: [t2
\n\t        \t        \t        \t        \t        \t        * ((t1 at: 1)
\n\t        \t        \t        \t        \t        \t        \t        \t        value: t2 – 1)]].
\n\t        (1 to: 10)
\n\t         \t        collect: (t1 at: 1)<\/font>
<\/body>
\nand its opcodes:<\/p>\n

                 pushLit: Array
\n                  pushConstant: 1
\n                  send: #new:
\n                  popIntoTemp: 0
\n                  pushTemp: 0
\n                  pushConstant: 1
\n                  pushThisContext
\n                  pushConstant: 1
\n                  pushLit: Array
\n                  pushTemp: 0
\n                  send: #braceWith:
\n                  send: #closureCopy:copiedValues:
\n                  jumpTo: L3
\n                           pushTemp: 0
\n                           pushConstant: 1
\n                           send: #=
\n                           jumpFalseTo: L1
\n                           pushConstant: 1
\n                           jumpTo: L2
\n         L1:
\n                           pushTemp: 0
\n                           pushTemp: 1
\n                           pushConstant: 1
\n                           send: #at:
\n                           pushTemp: 0
\n                           pushConstant: 1
\n                           send: #-
\n                           send: #value:
\n                           send: #*
\n         L2:
\n                           blockReturn
\n         L3:
\n                  send: #at:put:
\n                  pop
\n                  pushConstant: 1
\n                  pushConstant: 10
\n                  send: #to:
\n                  pushTemp: 0
\n                  pushConstant: 1
\n                  send: #at:
\n                  send: #collect:
\n                  pop
\n                  returnSelf
<\/body><\/font>
\n\u00c2\u00a0<\/p>\n

and it works \ud83d\ude42<\/p>\n

Next post, the closure bytecodes, costs, etc.<\/p>\n

\t
\t\t \t\t\"\"<\/a> \t\t  <\/span> \t\tSend article as PDF<\/span> \t\t  <\/span> \t\t \t\t \t<\/form> <\/div>","protected":false},"excerpt":{"rendered":"

BlueBook BlockContexts are nearly closures.\u00c2\u00a0 They close-over their enclosing environment, providing access to an enclosing method’s arguments and temporary variables.\u00c2\u00a0 But they lack their own local environment, hijacking their method activation’s (or home context’s) temps to store their own arguments and temporaries (let’s call these locals).\u00c2\u00a0 Worse still, they’re not reentrant. \u00c2\u00a0BTW, “the home context” […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[],"_links":{"self":[{"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/posts\/6"}],"collection":[{"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/comments?post=6"}],"version-history":[{"count":4,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/posts\/6\/revisions"}],"predecessor-version":[{"id":376,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/posts\/6\/revisions\/376"}],"wp:attachment":[{"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/media?parent=6"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/categories?post=6"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mirandabanda.org\/cogblog\/wp-json\/wp\/v2\/tags?post=6"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}