 Arc Forum new | comments | leaders | submit login A new arc challenge 1 point by akkartik 2705 days ago | 9 comments I've been going through SICP again (this time I'm going to go all the way through it), and I got distracted after solving exercise 1.19.http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.19Spoiler alert: If you haven't encountered this exercise yet, it's very fun to try solving by yourself first.I initially tried it using sweet expressions atop guile (http://readable.sourceforge.net), but I wasn't happy with how it looked:`````` ;; T: ;; a = a + b ;; b = a ;; ;; T_pq: ;; a' = ap + (b+a)q ;; b' = bp + aq ;; ;; T_pq^2: ;; a'' = b'q + a'q + a'p ;; = (bp + aq)q + (bq + aq + ap)(p + q) ;; = bpq + aqq + bpq + apq + app + bqq + aqq + apq ;; = (a+b)2pq + (a+b)qq + a(pp + qq) ;; = a(pp+qq) + (b+a)(2pq+qq) ;; ;; b'' = b'p + a'q ;; = (bp + aq)p + (bq + aq + ap)q ;; = bpp + apq + bqq + aqq + apq ;; = b(pp+qq) + a(2pq+qq) ;; ;; Therefore, T_pq^2 = T_(pp+qq)(2pq+qq) define fib2(n) fib-iter(1 0 0 1 n) define fib-iter(a b p q n) cond {n = 0} b even?(n) fib-iter(a b {square(p) + square(q)} {{2 * p * q} + square(q)} {n / 2}) else fib-iter({{b * q} + {a * q} + {a * p}} {{b * p} + {a * q}} p q {n - 1}) `````` The curlies were too visually heavy, and the ability to use infix was counterbalanced by requiring spaces around operators.In wart:`````` def fib-iter(a b p q n) (if (iso n 0) b even?.n (fib-iter a b (+ square.p square.q) (+ square.q (* 2 p q)) (/ n 2)) :else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- n 1))) `````` Mildly better, but it still suffered from the lisp problem that arithmetic becomes hard to read.I find the right macro helps group sums and products separately far better than infix:`````` mac perform(op1 op2 . list-of-args/over) `(,op1 ,@(map (fn(args) `(,op2 ,@args)) list-of-args)) `````` Now:`````` def fib-iter(a b p q n) (if (iso n 0) b even?.n (fib-iter a b (perform + * :over p.p q.q) (perform + * :over q.q (2 p q)) (/ n 2)) :else (fib-iter (perform + * :over b.q a.q a.p) (perform + * :over b.p a.q) p q (- n 1))) `````` What do y'all think? Too clever? Is there a nicer way to write it in Shen or Nulan?  1 point by akkartik 2702 days ago | link I just realized I can make the second call to perform look even nicer, with dot mimicking the syntax for multiplication in math:`````` (perform + * :over q.q 2.p.q) `````` The new perform just has an extra word:`````` mac perform(op1 op2 . list-of-args/over) `(,op1 ,@(map (fn(args) `(,op2 ,@flatten.args)) list-of-args))``````-----  3 points by fallintothis 2691 days ago | link Mildly better, but it still suffered from the lisp problem that arithmetic becomes hard to read.Meh. The prefix version reads fine, to me. I think infix notation is too much of a sacred cow ("but math!"). People bend over backwards to try to selectively write infix notation in both prefix & postfix languages, but not much ever seems to get saved in the process. Elegant parsing algorithms are typically general, so why not stick with them? Prefix math isn't that bad.At the same time, I'm not sure that perform is general enough beyond this problem. Wouldn't it be more general to have syntax for infix expressions (prefix be damned)? You could use a macro for rudimentary infix parsing, e.g.,`````` (= priority* (obj + 1 - 1 * 2 / 2 expt 3)) (def operand (tok) (~priority* tok)) (def priority>= (a b) (>= (priority* a) (priority* b))) (mac infix toks (let (ops prefix) nil (each tok toks (if (operand tok) (push tok prefix) (do (while (and ops (priority>= (car ops) tok)) (push (list (pop ops) (pop (cdr prefix)) (pop prefix)) prefix)) (push tok ops)))) (while ops (push (list (pop ops) (pop (cdr prefix)) (pop prefix)) prefix)) (pop prefix))) (def zero (n) (is n 0)) (def sq (n) (* n n)) (def fib-iter (a b p q n) (if (zero n) b (even n) (fib-iter a b (infix sq.p + sq.q) (infix sq.q + 2 * p * q) (/ n 2)) (fib-iter (infix b * q + a * q + a * p) (infix b * p + a * q) p q (- n 1)))) `````` But in the limit, you'd still want/need something built into the parser to deal with things like parens, whitespace, infix/prefix operator mixing, etc.What does leap out at me, though, is the if where each clause is a function repeatedly applied to the same argument. I know I've seen versions around on the forum before with different names, but it's essentially just a variant of case:`````` (mac where (expr . args) (withs (var (uniq) ex (afn (args) (if (no (cdr args)) (car args) `(if (,(car args) ,var) ,(cadr args) ,(self (cddr args)))))) `(let ,var ,expr ,(ex args)))) (def fib-iter (a b p q n) (where n zero b even (fib-iter a b (infix sq.p + sq.q) (infix sq.q + 2 * p * q) (/ n 2)) (fib-iter (infix b * q + a * q + a * p) (infix b * p + a * q) p q (- n 1)))) `````` Beyond that, I'm not sure there's much more to simplify. I mean, the function already takes 5 variables---there's only so much you can do.-----  3 points by akkartik 2690 days ago | link :) Yeah, that's a nice example where infix-with-precedence looks nicer than curly infix (without precedence). http://sourceforge.net/p/readable/wiki/Rationale points out that precedence breaks homoiconicity. And without precedence you end up with a lot more redundant whitespace and tokens to do nested infix. Hmm, perhaps if the infix tokens are limited (Nulan's idea http://arclanguage.org/item?id=16487), violating homoiconicity for just them may be more reasonable. What if user code can extend and locally override the infix ops, but not change their relative precedence? I'm going to look for more examples from numerical methods and graphics.Also, I think you underestimate how generally useful perform can be :) What if I called it poly for polynomial? I'll keep an eye out for more examples. Adding precedence doesn't change how uniform complex expressions have to look if you can't group them. It isn't as big a deal here, but I think more complex expressions with the infix macro would get less readable. What I really want is to use juxtaposition to indicate higher precedence:`````` (+ b.p a.q a.p) `````` ---Whoa, whacky idea alert. What if we use whitespace to indicate operator precedence?`````` (fib-iter {b * q + a * q + a * p} {b * p + a * q} p q {n - 1}) `````` Here the + operators have three spaces rather than one around them, so are at a lower precedence and get translated into (+ (* b q) (+ (* a q) (* a p))). Assume that operators at the same precedence are always applied right-associatively.-----  3 points by fallintothis 2690 days ago | link Whoa, whacky idea alert. What if we use whitespace to indicate operator precedence?Ha! File that under "never would've thought of it". Still think prefix does just fine, but I like that idea for its quirkiness.Also, I think you underestimate how generally useful perform can be :)Superficially contemplating perform (namely the fact that it's a macro) made me think of one thing I wish I had while writing infix. pop is a macro, so I couldn't pass it to map, proper. What I needed was a macro to map macros:`````` ; Goofy-looking name, but bear with me (mac macmap (m . exprs) `(list ,@(map [list m _] exprs))) `````` Thus`````` (push (list (pop ops) (pop (cdr prefix)) (pop prefix)) prefix) `````` becomes`````` (push (macmap pop ops (cdr prefix) prefix) prefix) `````` Which got me thinking: why did perform need to be a macro again? Well, obviously`````` (sum [apply * _] (list (q q) (2 p q))) `````` tries to eval (q q) and (2 p q), and writing (list q q) defeats the purpose of brevity. (Side note: in vanilla Arc, you couldn't use q.q, because ssyntax isn't expanded before macros.)Then I actually double-checked your original definition of perform and realized (macmap pop ...) = (perform list pop ...). So I've found my own example! But I think we might could do one better.What if I called it poly for polynomial?poly is too specific, if this operator hopes to be general. The operation itself smacks more of distributivity---almost like distributing an operator over cons. Emphasis on "an" operator, not a pair of them (lest it read like "distribute addition over multiplication"). But because (macmap ...) = (perform list ...), maybe it's just a better name for macmap:`````` (mac distribute (op . exprs) `(list ,@(map [list op _] exprs))) ; Thus (distribute pop ops (cdr prefix) prefix) `````` If we were to make perform a single-operator macro, a similarity I should've noticed earlier appears: it's almost the same as macmap, except`````` (mac distribute (op . exprs) `(list ,@(map [cons op _] exprs))) ; cons vs list! ; Thus (apply + (distribute * (q q) (2 p q))) `````` Not that the above is the best rewrite of the original, but if it were...is there a way to reconcile the cons vs list difference, whether by different names or by merging it into a super-distribute?-----  1 point by akkartik 2690 days ago | link This is a super neat rewrite of the original. I don't have have much to contribute in response except tangents.1. I didn't pay attention to your implementation earlier, but this is insane:`````` (list (pop ops) (pop (cdr prefix)) (pop prefix)) `````` How the heck does this work? I replace cdr.prefix with just prefix and it works fine except that it reverses the order of the operands.. Ooh, I see:`````` arc> (= x '(1 2 3)) (1 2 3) arc> (pop cdr.x) 2 arc> x (1 3) `````` Mind.. blown. Of course, it makes sense with hindsight.Still, way too clever for my taste to rely on arg eval order. I'd rather make the ordering of mutations explicit:`````` (withs (b pop.prefix a pop.prefix) (push (list pop.ops a b) prefix)) `````` (with would still rely on arg eval order, I think.)2. "Still think prefix does just fine.."Absolutely. I'm not sure infix is worthwhile, just mildly dissatisfied by how arithmetic expressions in lisp turn out.3. It turns out David Wheeler has thoroughly thought through the various scenarios for infix precedence: http://sourceforge.net/p/readable/wiki/Precedence. I haven't digested it yet.4. "poly is too specific."Yes, I was being lazy. I imagined poly without operator parameters:`````` (poly q.q 2.p.q) `````` 5. "Emphasis on _an_ operator, not a pair of them (lest it read like 'distribute addition over multiplication')."That was incredibly useful in following your comment.6. Can I prevail on you to switch from zero to zero?? :)-----  2 points by fallintothis 2690 days ago | link I don't have have much to contribute in response except tangents.Well, birds of a feather...1. Still, way too clever for my tasteOh, certainly. It was a result of me golfing an earlier version. :)6. Can I prevail on you to switch from zero to zero??In a heartbeat. I wish Arc used question marks (judiciously, mind you; don't need names like Scheme's char  2 points by rocketnia 2683 days ago | link "What I really want is to use juxtaposition to indicate higher precedence"I think I first heard of that idea from the Gel syntax: http://www.cs.utexas.edu/~wcook/Drafts/2008/gel.pdfThe discussion at http://c2.com/cgi/wiki?SyntacticallySignificantWhitespaceCon... leads to the stillborn Merd language project from 2001-2003, which calls this "horizontal layout": http://merd.sourceforge.net/#features---"Whoa, whacky idea alert. What if we use whitespace to indicate operator precedence?"The Merd site mentions that case, too: "experimentation is needed to know if [horizontal layout] could work for more than one space" http://merd.sourceforge.net/choices_syntax.html#6I've doodled this idea independently a couple of times, but I see a few issues:1. Line breaks throw a monkey wrench in the works (though it might be reasonable to prohibit line breaks within { ... }).2. In many contexts, it can be tough to count spaces. :)3. Sometimes it's nice to tabulate similar lines of code using extra spaces, and in those cases this feature would be a minor annoyance, since it would force some subexpressions to bail out to parentheses.`````` // Horizontal layout interferes: var wargle = 2 * x + 0.03 * y + 200; var tricennarious = 13 * x + 0.4 * y + 50; // Fix: var wargle = 2 * x + (0.03 * y) + 200; var tricennarious = 13 * x + (0.4 * y) + 50;``````-----  1 point by akkartik 2683 days ago | link Alternatively:`````` var wargle = 2 * x + 0.03 * y + 200; var tricennarious = 13 * x + 0.4 * y + 50; `````` Adding tabulation in addition to whitespace precedence would end up making expressions even more loose and baggy than otherwise. The writer would have to count spaces, but it's fairly clean when reading.---Thanks for the pointers! I'm going to go look at those now.-----  1 point by akkartik 2681 days ago | link I've also been reading about J (http://www.jsoftware.com/help/primer/contents.htm; via the recent http://arclanguage.org/item?id=16728), which might provide some interesting ideas.----- 