Arc Forum | CL's psetf

Arc Forum

CL's psetf

6 points by mapper 5213 days ago | 14 comments

This macro sets variables in parallel.

  (def interleave lists
    (apply mappend list lists))

  (mac pset  vars-and-vals
    (withs (pairs (pair vars-and-vals)
            vars (map car pairs)
            vals (map cadr pairs)
            uniqs (n-of (len vals) (uniq)))
      `(with ,(interleave uniqs vals)
          (assign ,@(interleave vars uniqs)))))

It got my attention when I saw it used in a fibonacci function. Here's an Arc version:

  (def fib (n)
    (with (a 0 b 1)
      (repeat (1- n)
        (pset  a b  b (+ a b)))
      b))

Testing in Jarc:

  Jarc> (map fib (range 1 9))
  (1 1 2 3 5 8 13 21 34)

4 points by waterhouse 5213 days ago | link

Nice and elegant.

More about computing Fibonacci numbers: If F_n is the nth Fibonacci number, and if you know the rules for matrix multiplication, you can see:

  [1 1] x [F_n  ] = [F_n + F_n-1] = [F_n+1]
  [1 0]   [F_n-1]   [F_n        ]   [F_n  ]

This is equivalent to applying the "pset" algorithm once; it's simply expressed in the notation of matrices. And, further:

  [1 1]^n x [F_1] = [F_n+1]
  [1 0]     [F_0]   [F_n  ]

This is particularly useful, because one can calculate the nth power of a matrix (or of anything) in O(log n) steps with exponentiation by squaring.[0] If we represent a matrix as a list of lists, then the following definitions will work[1][2]...

  (def mat-trans (x) ;transpose; this is incredibly terse
    (apply map list x))

  (def mat-mul (a b)
    (let u mat-trans.b
      (map (fn (xa)
             (map (fn (xb)
                    (reduce + (map * xa xb)))
                  u))
           a)))

  (def mat-id (n) ;n x n identity matrix
    (mapn (fn (x)
            (mapn (fn (y)
                    (if (is x y) 1 0))
                  1 n))
          1 n))

  (def mat-expt (x n)
    (xloop (x x n n total (mat-id (len x)))
       (if (is n 0)
           total
           (even n)
           (next (mat-mul x x) (/ n 2) total)
           (next x (- n 1) (mat-mul x total)))))

  (def fib (n)
    (let u (mat-mul (mat-expt '((1 1) (1 0)) n)
                    '((1) (0)))
      u.1.0))

This strategy has the advantage that, once you get it, you can use it for any linear recurrence. For example, if we had

  f(n) = n if n≤2, else f(n-1) + 2f(n-2) + 3f(n-3)

then this could be calculated as

  (def f (n)
    (car:last:mat-mul (mat-expt '((1 2 3) (1 0 0) (0 1 0)) n)
                      '((2) (1) (0))))

. Also, if one wants, say, these sequences mod m, then it's a fairly simple matter to come up with a "mod"ified version of mat-mul and use that instead--and then the calculation is actually O(log n), because the numbers stay small.

[0] Of course this can be done without the language of matrices. Saying that [1 1; 1 0]^3 = [3 2; 2 1] is the same as saying that the transformation "b -> a+b, a -> b" applied three times is the transformation "b -> 3b+2a, a -> 2b+a". Matrices, and matrix multiplication, are simply a convenient way to represent and compose these transformations.

In fact, as far as I'm concerned, that is the single thing they're good for; and in high school, when I was taught about matrices but not about this stuff, I found it a strange and unmotivated exercise, and so I retained basically none of it, even after it was covered in three consecutive math classes. And I am not known for forgetting or failing to understand things; I've been one of the top students in all of my math classes (except those at an extremely hardcore math camp). I can only imagine how it was for the other students. </rant>

[1] Library functions (with these, the above should work in standard Arc):

  (def mapn (f a b)
    (if (> a b)
        nil
        (cons (f a) (mapn f (+ a 1) b))))

  (mac xloop (binds . body)
    `((rfn next ,(map car pair.binds)
        ,@body)
      ,@(map cadr pair.binds)))

[2] It's possible to be slightly more clever than this. E.g. the powers of the [1 1; 1 0] will always look like this:

  [F_n+2 F_n+1]
  [F_n+1 F_n  ]

In theory, you could represent the whole matrix using just two variables (say, F_n+1 and F_n), and the entire computation could be done with four variables.

-----

2 points by akkartik 5209 days ago | link

With spectacular timing:

http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-i... http://news.ycombinator.com/item?id=2537811

-----

1 point by akkartik 5212 days ago | link

I can't believe arc's = isn't parallel. Shouldn't it be?

Somehow I never noticed, I suppose because I've been writing such beautiful functional code (sic).

Update: turns out enq relies on serial assignment.

-----

3 points by waterhouse 5212 days ago | link

Some cases off the top of my head in which I use serial assignment with =. Basically I use it frequently when I'm setting stuff up.

  (= home-dir ($.path->string ($.find-system-path 'home-dir))
     home (fn args (string home-dir args))
     orders-file (home "ORDERS")
     orders-input (home "ARC_INPUT"))

  (= the-grid '(2 0 1 0 0 4 0 1 1 0 0 0 4 4 0 0 0 1 2 0 3 2 0 1 0 4 3 2 0 
                4 0 4 0 4 0 4 0 3 3 6 6 B 3 5 0 2 0 3 5 0 3 3 0 2 0 0 4 3
                0 4 0 3 3 6 0 2 3 0 0 5 0 4 0 5 1 4 0 0 2 0 0 3 2 4 3 0 0
                0 1 0 0 4 0 4 2 0 0 4 0 0 3 0 0 0 0 4 0 0 3 4 3 0 2 0 4 4
                1 3 0 1 2 0 0 1 0 4 2 3 0 0 4 4 1 0 2 0 2 0 2 0 0 3 2 3 0)
     the-grid (map [case _
                     B (cons 0 'b)
                     (cons _ (list 'b 'w))] the-grid)
     the-grid (tuples (/ len.the-grid 5) the-grid)
     ggrid deepcopy.the-grid)

And then this is a case where my code doesn't actually use multiple arguments to = for accidental reasons, but this is what it would look like:

  (def nrev (xs)
    (let u nil
      (whilet head xs
        (= xs       cdr.xs
           cdr.head u      ;I actually use scdr here
           u        head))
      u))

Hmm... come to think of it, I guess it could be done, perhaps better, with parallel assignment. You have to be careful, though. The "cdr.xs" that is set to "u" should be the cdr of the original xs.

  (def nrev (xs)
    (let u nil
      (while xs  ;no whilet
        (p= xs     cdr.xs
            cdr.xs u
            u      xs))
      u))

And then there are about 20 cases in which I assign multiple things with = and it wouldn't matter whether it was parallel or not. And there's a case in which I had to be a bit careful about the ordering to make sequential = work.

I almost never think about using parallel assignment, at least not explicitly. (But, hmm, it seems it would be useful for destructive operations on AVL trees, or any data structure. But it must be defined carefully.) I frequently use it in a loop, but it appears as a tail-recursive call; in fact, the example that is the subject of this thread could be done in that style:

  (def fib (n)
    (xloop (n n a 0 b 1)
      (if (is n 0)
          a
          (next (- n 1) b (+ a b)))))

I do believe that the language should provide both a parallel = and a sequential =. I'm not entirely sure which one should be afforded "official =" status. For the moment, portable code could use "=*" or maybe "=s" for sequential and "p=" or something for parallel assignment (it definitely has to be no more than two characters).

-----

1 point by Pauan 5212 days ago | link

"I do believe that the language should provide both a parallel = and a sequential =. I'm not entirely sure which one should be afforded "official =" status. For the moment, portable code could use "=" or maybe "=s" for sequential and "p=" or something for parallel assignment (it definitely has to be no more than two characters)."

That sounds reasonable. In fact, then = could just be an alias... something like this:

  (assign = =p)

And then if you would prefer = to be sequential, you could do this:

  (assign = =s)

This would of course clobber other code that expects = to be parallel, but that should be handled by a module/namespace system, so I'm not worried about that.

Side note: maybe we should avoid giving them names that look like emoticons...

-----

2 points by aw 5212 days ago | link

Reminds me of the recursive let discussion (http://arclanguage.org/item?id=13748): when we're defining or setting a variable, and we have an expression which calculates the (new) value for the variable, which scope do we want the variables in the expression to come from?

Sometimes we'll want the variables to come from one scope and sometimes from another. But, I think you're right that a parallel = would be a useful default. It would be easy for me to write (= a x b y) as (= a x) (= b y) if I didn't want the variables to be set in parallel, but harder for me to get them to be evaluated in parallel when I wanted them to be without a facility to do it for me.

-----

1 point by akkartik 5212 days ago | link

In wart I'm now trying out = for parallel assignment and =* for serial assignment.

https://github.com/akkartik/wart/commit/cc53b7941b0fc492ed5f...

(analogous to let and let*)

---

The definition is still a little 'lumpy' for my taste. But it'll smooth out with time. Besides, maybe it'll turn out to be a bad idea. No point prematurely optimizing for aesthetics.

-----

1 point by Pauan 5212 days ago | link

"Update: turns out enq relies on serial assignment."

That seems silly. If you want sequentialness, you can replace (= a b c d) with (do (= a b) (= c d)) So why would making = parallel prevent enq from working?

-----

1 point by akkartik 5212 days ago | link

If I wanted to just write code that 'works' I'd use assembler. I care about making elegant ways to express things we say often. That's what this forum's about, right? enq is evidence that even serial assignment needs (some) love.

-----

1 point by Pauan 5212 days ago | link

Then why do we have to write this?

  (if a
    (do b c)
    (do d e))

My point is that languages can't read our minds. Making a change that makes one thing easier often makes things harder in a different area.

So the question is: which is more preferable? Making sequential assignment the default, or parallel?

Enq is a single data point. A single function that would not benefit much either way. Using it as evidence that a very common operator (assignment) should be one way or the other seems like a weak argument to me.

Consider this: if making = parallel would not affect 99% of code, and would make certain types of code shorter, then whether enq relies on sequential access or not is pretty much irrelevant, right? It can just use `do`, and in exchange for that the other code would get nice benefits.

So yes, enq is evidence for sequential assignment... but this thread (psetf) is evidence for parallel... so we're right back where we started, at a point where the evidence doesn't say much one way or the other.

But, let's suppose that we decided to make = sequential... like it is right now. Now you need to make a new macro (like pset) to describe parallelness. On the other hand, if = were parallel, it's trivial to use `do` to make it sequential: no need to write a new macro. This also makes it obvious that the assignments are indeed happening one after the other, which may be important to you (or may not be).

Thus the evidence that we have right now suggests making = parallel by default, and that is why I said it seems silly to use enq as evidence that = should be sequential.

P.S. I'll note that I was agreeing with you about making parallel the default; I was noting that we shouldn't make it sequential just because of it breaking enq, especially since there is such an easy work-around (using `do`) Apparently I was misunderstood, I'm sorry.

-----

3 points by waterhouse 5212 days ago | link

> But, let's suppose that we decided to make = sequential... like it is right now. Now you need to make a new macro (like pset) to describe parallelness. On the other hand, if = were parallel, it's trivial to use `do` to make it sequential: no need to write a new macro.

Minor objection here: No. I could call it trivial to do the work of describing parallel assignments:

  (with (new-a b new-b (+ b a))
    (= a new-a b new-b))

And, in fact, I would feel the need to write a new macro to express sequential =. "Gar dammit I hate writing "do" and "=" a bunch of times." To me, both things are trivial, and I just might be more annoyed by the latter.

-----

1 point by Pauan 5212 days ago | link

Alright, fair enough. But what if there was a built-in macro like =* that could be defined like so:

  (mac =* args
    `(do ,@(map (fn ((n v))
                  `(= ,n ,v))
                (pair args))))

  (macex1 '(=* a b c d e f)) -> (do (= a b) (= c d) (= e f))

Voila, now both cases are handled in a nice and easy fashion.

-----

1 point by akkartik 5212 days ago | link

Yeah my inclination too is that = should mean parallel assignment; I was just thinking aloud about reasons against.

As it happens I found a way to cleanly remove serial assignment in enq.

https://github.com/akkartik/wart/commit/f44e0d77be58e946c79d...

-----

2 points by mapper 5213 days ago | link

'fib should have been simpler.

  (def fib (n)
    (with (a 0 b 1)
      (repeat n
        (pset  a b  b (+ a b)))
      a))

-----