Local mutation, global mutation, mutable datastructures

[Artella Coding]

I was flicking through TBoS and noticed on p.g. 109 code which showed how to write functions which mutate a vector :

Shen 2010, copyright (C) 2010 Mark Tarver
released under the Shen license
www.shenlanguage.org, version 13
running under Ruby, implementation: ruby 2.0.0
port 0.7.0 ported by Greg Spurrier

(0-) 
(define add1
  <> -> <>
  (@v N V) -> (@v (+ N 1) (add1 V)))

(define destructive-add1
  V -> (destructive-add1-loop V 1 (limit V)))

(define destructive-add1-loop
  V Limit Limit -> (vector-> V Limit (+ 1 (<-vector V Limit)))
  V Count Limit -> (destructive-add1-loop
                     (vector-> V Count (+ 1 (<-vector V Count)))
                     (+ Count 1) Limit))
add1

(1-) destructive-add1

(2-) destructive-add1-loop

(3-) (set *myvector* (@v 1 2 3 <>))
<1 2 3>

(4-) (add1 (value *myvector*))
<2 3 4>

(5-) (value *myvector*)
<1 2 3>

(6-) (destructive-add1 (value *myvector*))
<2 3 4>

(7-) (value *myvector*)
<2 3 4>

In https://groups.google.com/forum/#!msg/qilang/Qk-WruXatLY/Q_JE5_Hw25kJ you pointed out (in a response to deech) how to make shen "pure" in the sense that destructive operations are disallowed.

My question is whether it is possible (via macros or some other scheme) to 

a)disallow mutations when you cross function boundaries (i.e. when you feed a datastructure into a function you have a guarantee that the original datastructure will not be changed) 

b)but then to allow local mutations within a function. i.e. you can mutate the local copy of the datastructure within the function, without affecting the original datastructure from which the copy was made

I think Clojure has this feature, and it is nice because local mutations are useful for performance reasons, but disallowing mutations when crossing function boundaries means that I dont have to worry about tracking the chain of functions in order to see whether destructive operations are being performed in a way that unintentionally modifies the original datastructure. Thanks

[Artella Coding]

See also this interesting post by David Nolen where he talks about local mutations : http://swannodette.github.io/2013/06/10/porting-notchs-minecraft-demo-to-clojurescript/

[Mark Tarver]

The only way I could see that you could do this would be to copy the vector argument before passing it to the function.

(package vector [copy]

    (define copy

        {(vector A) --> (vector A)}

        Vector -> (let Limit (limit Vector) (copyh Vector (vector Limit) Limit)))

    (define copyh

        {(vector A) --> (vector A) --> number --> (vector A)}

        _ Copy 0 -> Copy

        Vector Copy N -> (copyh Vector (vector-> Copy N (<-vector Vector N)) (- N 1)))   ) 

This only works on dense standard vectors - that contain no gaps in them.  If you wanted to process all vectors, then you'd need <-address.   You need to build a type theory for immutable vectors to prevent the use of vector->/address-> outside of your barrier of abstraction.  

Mark

[Ramil Farkhshatov]

Artella Coding <artella...@googlemail.com> wrote:

> My question is whether it is possible (via macros or some other scheme) to
>

> a) disallow mutations when you cross function boundaries (i.e. when you

> feed a datastructure into a function you have a guarantee that the original
> datastructure will not be changed)
>

> b) but then to allow local mutations within a function. i.e. you can mutate

> the local copy of the datastructure within the function, without affecting
> the original datastructure from which the copy was made

You can pass a copy of the datastructure when you don't want the
original to be mutated.

[Mark Tarver]

Somewhat better

(package vector [copy]

    (define copy

        {(vector A) --> (vector A)}

        Vector -> (let Limit (limit Vector) (copyh Vector (vector Limit) Limit)))

    (define copyh

        {(vector A) --> (vector A) --> number --> (vector A)}

        Vector Copy 0 -> Copy

        Vector Copy N -> (copyh Vector 

                                              (trap-error (vector-> Copy N (<-vector Vector N)) (/. E Copy))

                                              (- N 1)))   ) 

This traps any erroneous attempt to extract information from a sparse vector and works for all standard vectors.

Mark

[Artella Coding]

@Mark @Ramil, I know I need to copy. But how do I get the system to do this transparently for me? In the below code the "test" function still modifies the datastructure. Thanks :

Shen 2010, copyright (C) 2010 Mark Tarver
released under the Shen license
www.shenlanguage.org, version 13
running under Ruby, implementation: ruby 2.0.0
port 0.7.0 ported by Greg Spurrier

(0

-) 
(package vector [copy]

    (define copy
        {(vector A) --> (vector A)}
        Vector -> (let Limit (limit Vector) (copyh Vector (vector Limit) Limit)))

    (define copyh
        {(vector A) --> (vector A) --> number --> (vector A)}
        Vector Copy 0 -> Copy
        Vector Copy N -> (copyh Vector 
                                              (trap-error (vector-> Copy N (<-vector Vector N)) (/. E Copy))
                                              (- N 1)))   ) 
copy
vector.copyh

(1-) 
(define destructive-add1
  V -> (destructive-add1-loop V 1 (limit V)))

(define destructive-add1-loop

  V Limit Limit -> (vector-> V Limit (+ 1 (<-vector V Limit)))
  V Count Limit -> (destructive-add1-loop
                     (vector-> V Count (+ 1 (<-vector V Count)))
                     (+ Count 1

) Limit))

(define test
  X -> (destructive-add1 X))destructive-add1

(2-) destructive-add1-loop

(3-) (set *myvector* (@v 1 2 3

 <>))
test
<1 2 3>

(4-) (test (value *myvector*))
<2 3 4>

(5-) (value *myvector*)
<2 3 4>

[Mark Tarver]

You create clojure immutable vectors as an abstract datatype. 

(package clojure [copy give immutable]

    (datatype immutable

      __________________

      <> : (immutable A);

     X : A; V : (immutable A);

     =========================

     (@v X V) : (immutable A);

     ______________________________________

     copy : ((immutable A) --> (vector A));

     ______________________________________

     give : ((vector A) --> (immutable A));)

    \\ fast copy with native vectors

    (define copy

       Vector -> (let Limit (limit Vector) 

                      EmptyCopy (absvector (+ Limit 1))

                      StandardV (address-> EmptyCopy 0 Limit)

                      (copyh Vector StandardV Limit)))

    (define copyh

        _ Copy 0 -> Copy

        Vector Copy N -> (copyh Vector (address-> Copy N (<-address Vector N)) (- N 1)))   

    \\ coerces to immutable status

    (define give

       Vector -> Vector) )

Here is destructive add.

(define destructive-add1

  {(vector number) --> (vector number)}

  V -> (destructive-add1-loop V 1 (limit V)))

(define destructive-add1-loop

  {(vector number) --> number --> number --> (vector number)}

  V Limit Limit -> (vector-> V Limit (+ 1 (<-vector V Limit)))

  V Count Limit -> (destructive-add1-loop

                     (vector-> V Count (+ 1 (<-vector V Count)))

                     (+ Count 1) Limit))

Here we declare a global as an immutable vector.

(datatype globals

  ______________________________________

  (value *immutable*) : (immutable number);)

____________________________________________________________________________

\\ This fails because immutable vectors cannot be built this way.

(41+) (set *immutable* (vector 7))

type error

\\This fails too.

(42+) (set *immutable* (@v 1 2 a <>))

type error

\\This works.

(43+) (set *immutable* (@v 1 2 3 <>))

<1 2 3> : (immutable number)

\\Cannot mutate an immutable vector

(44+) (vector-> (value *immutable*) 2 6)

type error

\\But you can if you copy it.

(45+) (vector-> (copy (value *immutable*)) 2 6)

<1 6 3> : (vector number)

\\ Still immutable!

(46+) (value *immutable*)

<1 2 3> : (immutable number)

\\ Return an immutable vector

(47+) (give (vector-> (copy (value *immutable*)) 2 6))

<1 6 3> : (immutable number)

\\ Cannot mutate it.

(48+) (destructive-add1 (value *immutable*))

type error

\\ So copy it.

(49+) (destructive-add1 (copy (value *immutable*)))

<2 3 4> : (vector number)

You create an abstract datatype and the type checker controls access to objects of that type and ensures they are immutable.

Mark

[Artella Coding]

Hi thanks. I tried this in Common Lisp port 13, and it didnt work as above. Have I done something wrong? 

Shen 2010, copyright (C) 2010 Mark Tarver
released under the Shen license
www.shenlanguage.org, version 13

running under Common Lisp, implementation: CLisp
port 1.6 ported by Mark Tarver


(0-) (package clojure [copy give immutable]

    (datatype immutable

      __________________
      <> : (immutable A);

     X : A; V : (immutable A);
     =========================
     (@v X V) : (immutable A);

     ______________________________________
     copy : ((immutable A) --> (vector A));

     ______________________________________
     give : ((vector A) --> (immutable A));)


    \\ fast copy with native vectors
    (define copy
       Vector -> (let Limit (limit Vector)
                      EmptyCopy (absvector (+ Limit 1))
                      StandardV (address-> EmptyCopy 0 Limit)
                      (copyh Vector StandardV Limit)))

    (define copyh
        _ Copy 0 -> Copy
        Vector Copy N -> (copyh Vector (address-> Copy N (<-address Vector N)) (
- N 1

)))

    \\ coerces to immutable status
    (define give
       Vector -> Vector) )
clojure.type#immutable
copy
clojure.copyh
give

(1-)
(datatype globals

________________________________________
(value *immutable*) : (immutable number);)
type#globals

(2-)
(set *immutable* (vector 7))
<... ... ... ... ... ... ...>

(3-)

[Artella Coding]

Sent a post earlier about not being able to get the code above to work, but just worked out that you have to call "(tc +)" before invoking "(set *immutable* (vector 7))". Thanks for the detailed response.

[Jacob]

This is one of the reasons I prefer the common lisp way to the clojure way.  Clojure is too opinionated about being functional(imo, and about macros). I would rather have a hacky, meta-programming language that allows one to attack a problem from multiple directions.  Honestly, it would be nice if the compiler could just do all the concurrency for us while we just mutate whatever the crap we want.

[deech]

Hi Mark,
First off, this is great.

My question is slightly tangential ...

In the sources and other code you've posted here you write a lot of recursive functions that could be abstracted away into a fold. Here `copyh` is an example. Since I'm pretty sure you are familiar with folds is there a style reason for this?

-deech

[Artella Coding]

@Jacob It is not just about concurrency. It is (for me) much easier to debug/reason (other people's code) when you dont have variables/data structures being mutated all over the place. Also I have lost count the number of times I have encountered bugs due to variables/data structures being unintentionally mutated in places where it is not expected.

p.s. John Carmack did an interesting talk about functional programming (& problems with changing global states in his current code base etc..) in Quakecon 2013 : http://www.youtube.com/watch?v=1PhArSujR_A

[Jacob]

 "It is (for me) much easier to debug/reason (other people's code) "

Yes, I am a loner programmer(hopefully not forever).  I might learn to appreciate immutability more when I start actually working with others.  However, the point stands about reader macros(or does it, considering that is also a loner preference?)

[Jacob]

Deech, I believe it is simply because Shen(as of right now) does not really rely on a large body of functions that are common among other languages(a standard library).  I probably should just let Mark tell you but posting makes me feel important(not really).

[Mark Tarver]

Glad you like it.  No particular reason; maybe because it is not a system function.

Mark

[Artella Coding]

Well you could always contribute to one of the ports, then you wont be a "lone programmer" anymore:) 

I have to admit I still like C++. 

I haven't got around to learning about macros (reached chapter 4 severals months back but never got beyond that) so I can't say how the "reader" macros compare to clojure (I know very little clojure too).

[Jacob]

Just finished has talk.  His thoughts on immutability are sound but his thoughts on LISP and dynamic typing were not impressive to me at all.  I get tired of hearing the same mantra repeated by programmers about it being a religious conversation.  If we can get 

empirical, objectively verifiable data to compare the paradigms then we can approach the topics with more validity.  Some times these objective points are brought to bare and people still scream religion.  I guess the same is true of religion; even if historical facts 

might verify certain aspects of a given religion, people will not attribute any validity to the personal testimony of writers of history(yes I said history, everything one writes is hard to verify; all of history is your willingness to believe another's eye witness account and 

their subsequent interpretation, regardless of how absurd or illogical it sounds).  To end my rambling... Sounds like scheme could use some Common Lisp error handling(my assumption, since Carmack kept qq about the heinous errors he was 

running into).  

On Saturday, August 10, 2013 4:34:40 PM UTC-4, Artella Coding wrote:

[Artella Coding]

@Jacob yes I agree with you. I think he probably didnt give scheme a shot (in the same way he did with haskell) probably because of time constraints.

[Jacob]

Haskell is also very nice, not going to lie =).  However, I do not think that anyone really gets LISP until they play with macros for a little while.  Macros will truly embed in your brain the power of homoiconic syntactic constructs.  If one claims to "get" LISP without having  

extensively used macros; I highly doubt that claim.  Also, I wish he had played around with CLOS and maybe wrote an ai program that changes the structure of the source code itself, at run-time!  Of course, it is all my opinion but, I did not comprehend what could be  

accomplished with "homoiconicism" until I started to use macros.  I have wielded macros, like a crazy "wiztard", who's limited mental capabilities do not make it self evident how much damage they are causing by casting their SPELs(I am sure I abuse them now).

[Jacob]

Also about Shen macros... they are amazing.  Once you write a Shen macro you will laugh at clojure's(or for that matter any other macro system) macro facility.  They are so clean in Shen; I really love macros, probably too much.  Shen allows you to do a sort of 

pattern matching reader macro thing.  The only thing about the macro's in Shen that bother me is how you can't just flippantly program them, if you screw up it pretty much nukes the reader and you have to restart the repl.  I think that could be fixed with a good ide 

though(one that allows you to backtrack to previous writes of the macro).  

@ Dr Tarver

Do you think it is a good idea to take a compiler course?  Would it make me better at macro writing and prepare me to create a decent(crappy) IDE?  I want to work on the Shen Java port(Invoke Dynamic), since oracle will now be trying to optimize dynamic 

languages, not to mention Dynalink!  Dynalink is very exciting to me since it would allow the sharing of code between any language targeted at the jvm(now that will be library bliss)

[Mark Tarver]

I never bothered with courses; if you had a good book and a computer you had the best teachers you could find - one of them infallible and infinitely patient.  However things have developed since then and the internet is full of information.  Have a look at OpenCourseWare from MIT to see what they have.  

Books - Gough - Syntax Analysis and Software Tools.  Get a good book and code the ideas in Shen.

Shen-YACC is great for building compilers (the Shen reader is entirely coded in it) but suffers right now from transitioning into Shen-YACC II, which is better than YACC I, but not documented in TBoS 1st edition (but is in TBoS 2nd).  When TBoS 2nd edition comes out, you may want to

grok it.

Macros in Shen are great fun; they are actually byproducts of the Shen construction and enabled Shen to be built on such a tiny Lisp as KLambda.  They are on the whole to be compared to powerful but friendly jinn who will do your bidding - but yes they can vapourise the REPL if invoked unwisely.

Mark

[Artella Coding]

Now going in the opposite direction, is it possible to write functions which locally a mutate list? For example : 

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Bubble_sort#Common_Lisp

gives an efficient bubblesort algorithm (in Common Lisp) where the list is mutated. However the bubblesort algorithm given on pg 92 of TBoS (also given here : http://www.lambdassociates.org/Book/page088.htm) does not mutate the list. I rewrote this version in Common Lisp, and found it to be about 3 times slower

that the mutable bubblesort version. Thanks

[Artella Coding]

(continuing with the post on bubble sort) : 

So if you have a list (in Common Lisp notation) '(1 2 3 4 5 ....) :

1)a copy of '(2 3 4 5 ....) is made at the line "[X Y | Z] -> [Y | (bubble [X|Z])] where (> Y X)",

2)a copy of '(3 4 5 ....) is made at the same point upon recursion

3)a copy of '(4 5 ....) is made at the same point upon the second recursion

etc.

So that if a copy operation of a list of size N is a*N, then the total cost for a monotonically increasing list will be a[1 + 2 + .. + N] ~ aN^2/2

[Artella Coding]

" I rewrote this version in Common Lisp, and found it to be about 3 times slower that the mutable bubblesort version" - just to be clear I was not comparing Shen to CL, but instead CL(immutable bubblesort) to CL (mutable bubblesort), in order to guage the slowdown incurred from copying the lists.

[Mark Tarver]

Mutable lists are part of CL as you've found and yes, there are speedups. There are quite a few destructive list processes in CL like NREVERSE etc. This style of programming has the disadvantage of making programs hard to debug and errors are easy.  Formal reasoning over these destructive programs is hard. 

Back in the day, this style of programming was needed because machines were slow.  These days I feel there is less need for these constructions.

In Shen, the vector-> operation is destructive.  I felt that since vectors were often used to store global information for lookups, it made sense to incorporate a fast destructive vector operation.  You could probably reprise this style using vector-> and address->.

Mark

[Artella Coding]

"This style of programming has the disadvantage of making programs hard to debug and errors are easy.  Formal reasoning over these destructive programs is hard."

Wouldn't allowing local mutations (as mentioned in http://swannodette.github.io/2013/06/10/porting-notchs-minecraft-demo-to-clojurescript/) allow one to enjoy the best of both worlds? So :

a)forcing functions to make their own copy of the variables passed to them make them

"pure", hence overcoming the problems you mentioned above.

b)Allowing mutations of variables within a function (i.e. local mutations) allow one to enjoy the speedup associated with mutations. One would also need some looping mechanism in order to make good use of this. Since the mutations are "localised" one does not face the problem traditionally associated with programs which allow mutations.

Cheers

[Raoul Duke]

p.s. that was worded poorly. i know clojurescript derives from
clojure. i was trying to say, "yes, that sounded good to me too, and
one could look at clojure itself since clojurescript is predicated on
it."

On Sat, Oct 12, 2013 at 12:41 PM, Raoul Duke <rao...@gmail.com> wrote:
>> Wouldn't allowing local mutations (as mentioned in
>> http://swannodette.github.io/2013/06/10/porting-notchs-minecraft-demo-to-clojurescript/)
>> allow one to enjoy the best of both worlds? So :
>
>

> please also consider Clojure's approaches, with
> persistent-but-not-slow structures, and with transients. from the
> perspective of getting things done w/out bugs I personally based on my
> experience heartily concur with Dr. Tarver's position that we should
> eshew mutation as much as possible. of course there will always be
> mutation under the covers: even map/filter/reduce are presumably
> usually implemented in such a performant fashion, but it is locked
> down so to speak. so having mutation done once in a library routine is
> nice. having mutation done a zillion times willy-nilly is not.

[Raoul Duke]

> Wouldn't allowing local mutations (as mentioned in
> http://swannodette.github.io/2013/06/10/porting-notchs-minecraft-demo-to-clojurescript/)
> allow one to enjoy the best of both worlds? So :

[Artella Coding]

"I personally based on my experience heartily concur with Dr. Tarver's position that we should eshew mutation as much as possible."

But if a function which performs mutation internally is pure (i.e. does not mutate its arguments, but merely internal copies), then why should one "eshew mutation as much as possible"? Surely your experience is based on programs where mutations take place in a non-local sense?

In CL when I have a list from 1 to 100,000 : (1 2 .... 99999 100000), then :

Immutable CL bubble sort takes 262 s

Mutable CL bubble sort takes 42s

[Artella Coding]

By "Immutable CL bubble" I meant common lisp translation of bubble sort in http://www.lambdassociates.org/Book/page088.htm

By "Mutable CL bubble" I meant http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Bubble_sort#Common_Lisp

[Matthew Lamari]

More knowledgeable people can speak to what this means to Shen
specifically; but local mutable variables + looping impacts ability to
statically analyze code greatly. The value of a variable A could impact
a branch that affects whether B is overwritten. Knowing what A or B
contains, and whether it meets some constraint, is now much harder as
bindings have a time/order dimension.

> --
> You received this message because you are subscribed to the Google
> Groups "Shen" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to qilang+un...@googlegroups.com.
> To post to this group, send an email to qil...@googlegroups.com.
> Visit this group at http://groups.google.com/group/qilang.
> For more options, visit https://groups.google.com/groups/opt_out.

[Artella Coding]

@Matthew Lamari : Do you mean something like this? 

if(b == 1){

  a = a + b

}

And are you referring to typechecking? Why would typechecking be harder here? Thanks

[Artella Coding]

Maybe I am thinking of mutations from too simple a perspective. In the beginning of the video on the K Framework :

http://www.kframework.org/index.php/K_Overview

http://www.kframework.org/images/e/eb/K-Overview.pdf

An example is given of ambiguity between compilers for the following piece of (mutating) code : 

int main(void) {

  int x = 0;

  return (x=1) + (x=2);

[Artella Coding]

I found a similar question which has been asked before : http://stackoverflow.com/questions/3697760/functions-that-look-pure-to-callers-but-internally-use-mutation

 and the general consensus seems to be that local mutability is OK.

On Saturday, October 12, 2013 6:25:09 PM UTC+1, Mark Tarver wrote:

[Artella Coding]

Maybe I am thinking things to be worse than they actually are : my calculation of aN^2/2 assumes a dumb implementation. If the implementation was a tad bit more efficient then we would have : 

1)(1,2,3,..) -> (2,1,3,4) : the element containing 2 is made to point to 1 which is made to point to the 3 and the rest are left as is

2)(2,1,3,4) -> (2,3,1,4,5,...) :the element containing 2 is made to point to 3, and 3 is made to point to 1, and 1 is made to point to 4 and the rest is left as is

3)(2,3,1,4,5,...) -> (2,3,4,1,5,...): the element containing 3 is made to point to 4, 4 is made to point to 1, and 1 is made to point to 5 and the rest is left as is.

So we require 2 operations for boundaries and 3 operations otherwise, which means the net copying scales as N and not N^2/2. Makes me wonder why the immutable common lisp version was so slow...

Interestingly it turns out that Haskell also allows pure functions to mutate local variables via the State Monad (http://www.haskell.org/haskellwiki/Monad/ST). For example : 

import Control.Monad.ST
import Data.STRef
import Control.Monad
 
 
sumST :: Num a => [a] -> a
sumST xs = runST $ do
    n <- newSTRef 0             
    forM_ xs $ \x -> do        
        modifySTRef n (+x)
    readSTRef n                 

[Jacob]

Clojure transient