I love defmemo. It is amazingly convenient. I also like my math library. Here's the code I wrote. It is equivalent to your last solution.
(defmemo f (n d)
(if (is d 1)
1
(- (expt d n)
(sum (fn (i)
(* (choose d i)
(f n i)))
1 dec.d))))
arc> (time:f 12 5)
time: 1 gc: 0 mem: 27928
165528000
Note that you don't really need the "if d > n, return 0" part. An empty sum--or, in your code, (reduce + (map <something> <an empty range>))--will be 0 anyway.
It is a big fat Arc file on my computer. :-) In fact, the math stuff is just a subset of what's in that file. I suppose "library" probably isn't a good term for it. Should I perhaps put it in a form useful to the general public?
Well, here is a link to my arc3.1 folder (with some irrelevant things removed). The "a" file is the abovementioned big fat Arc file that has everything.
I've done some nonstandard things, like changing the order of expansion of ssyntax so a:b.c = (a:b c), and importing a bunch of Racket functions with $ (which at least is Anarki standard), so you probably can't paste in all my code and have it work, without, so to speak, pasting my version of ac.scm as well. I therefore supply this link, so you can run things directly. The code should probably be fairly understandable (if you know what the function's supposed to do) and it probably won't be very hard to port individual things you want to standard Arc.
By the way, my version of "sum" is simple: (sum f a b) = (reduce + (map f (range a b))), although it's implemented with a loop rather than map/reduce, which is more efficient. arc3.1 has a built-in function called "sum", which is different: (sum f xs) = (reduce + (map f xs)). Somewhere, akkartik had the idea of calling my "sum" function "sumn" (probably similar to "mapn", as in (mapn f a b) = (map f (range a b))), which is probably a reasonable compromise for standardization.
"changing the order of expansion of ssyntax so a:b.c = (a:b c)"
I've wondered about this myself. When wart started out I did what you do just because that was simplest (no precedence). Now I think I do as arc does. Do people have an opinion on what a:b.c should expand to?
I have a very strong opinion that it should expand to (a:b c), rather than (compose a b.c). I think I've once had a use for the latter, whereas I use the former all the time. Some examples (all of them were run with the former interpretation of a:b.c), found with this shell command:
Have you used ~f.g much? I ended up switching because arc.arc uses ~testify.f in a couple of places. And it seems inconsistent for that to work the other way..
Interesting case. No, I've never used that; actually, I never use the ~ operator, preferring "no:" (as you can see above). (I take it this is a different arc.arc than the one in arc3.1, as I don't find ~testify.f in there.)
Perhaps you could make ~ a function by itself: the "complement" function.[0] Then you could write ~:testify.f.
[0] Hmm, for some reason "complement" is defined as a macro in arc.arc. I don't think it needs to be that way. I think this would work fine:
I think it's that way so that 'complement can be used with macros. I don't think I ever use it that way, though. Either I use (~foo ...), where the metafn meaning takes control, or I use ~foo by itself with foo being a function. I don't give it much thought, 'cause there are good alternatives to ~, like the ones you're talking about.
I don't think this can be used with a macro. It applies f:
(mac complement (f)
(let g (uniq)
`(fn ,g
(no (apply (unquote f) (unquote g))))))
... Yet it actually does work.
arc> (mac no-mac (x) `(no ,x))
#(tagged mac #<procedure: no-mac>)
arc> ((complement no-mac) 2)
t
It's clearly using some kind of black magic with the Arc compiler, because macex-ing it makes it fail.
arc> (macex1 '(complement no-mac))
(fn gs2704 (no (apply no-mac gs2704)))
arc> ((fn gs2704 (no (apply no-mac gs2704))) 2)
Error: "Function call on inappropriate object #(tagged mac #<procedure: no-mac>) (2)"
...Ohai, special cases, printed right there at the top of ac.scm.
; the next three clauses could be removed without changing semantics
; ... except that they work for macros (so prob should do this for
; every elt of s, not just the car)
((eq? (xcar (xcar s)) 'compose) (ac (decompose (cdar s) (cdr s)) env))
((eq? (xcar (xcar s)) 'complement)
(ac (list 'no (cons (cadar s) (cdr s))) env))
((eq? (xcar (xcar s)) 'andf) (ac-andf s env))
Well. That explains it, at any rate...
arc> ((complement no-mac 2 3 4) (is 2 3))
nil
Heh.
I do like the side effect that (a:b:c x) is the same as (a (b (c x))) even if a,b,c are macros. That's something I'd hate to give up. This seems it could be implemented in either of some ways:
1. [current] A call to 'compose in functional position is special-cased by the compiler. This seems like a bit of a hack, although it's served pretty well and isn't likely to fail in the near future.
2. The thing that expands ssyntax will expand (a:b c ...) to (a (b c ...)). This would be hard and would suck, because then ssyntax would no longer be just intra-symbol. (An "ssexpand" function that just takes a symbol argument would be insufficient.)
2a. If ssexpansion is done by the reader (which I do believe it should be), like how [f _] becomes (fn (_) (f _)), then this might be tolerable. Being a reader change, this will and should apply everywhere, even inside quotes; for example, "(a '(b:c d.e))" would get read as (a (quote (b (c (d e))))). I think this might be something to aim for.
3. We make macros first class, so they can be applied, and probably make the compiler capable of optimizing such cases. I think this, combined with (2a) as a cheap way to optimize, would be good.
That's the metafn meaning I was talking about. >.>
---
This seems it could be implemented in either of some ways
My preferred way, which you didn't mention, is to have macros return intermediate things that can either be unwrapped into expressions or applied as syntax operators themselves. That way "compose" can be a syntax operator and "(compose a b c)" can also be a syntax operator. I describe this idea in context with several of my other ideas in http://arclanguage.org/item?id=13071, "A rough description of Penknife's textual syntax."
In the past couple of days, I've also been toying with the idea of having : be a read macro. It can start a list and stop once it reaches an ending bracket, without consuming that bracket. This would be similar in effect to http://arclanguage.org/item?id=13450.
(accum acc: each x args: acc:* 2 x)
One thing it gives up is the ability to say (map a:b c); you have to say (map [a:b _] c) instead. Also, it doesn't give you a:b.c, and it's not clear to me how to indent it. :-p
I don't see a good read macro equivalent for a.b; a read macro has to come before the things it reads, like "!a b", but chaining with "!!!!a b c d e" wouldn't be nearly as nice. Any reader-level solution for a.b ssyntax would probably need to ditch the Racket reader (or at least ditch it within certain delimiters), and it would probably use something like Penknife's or ar's approach, biting off a block of text somehow--using brackets, line breaks, whitespace, or whatnot--then parsing it all at once. ...Technically we might be able to replace Racket's list syntax with a syntax that keeps a public stack of subexpressions, and then have . pop off of that stack, but that strategy doesn't help at the top level.
Yeah, in wart call started out as just funcall then turned into a macro so it could handle macros. Hmm, would I need a transform to get that if I somehow make wart a lisp-1?
Also, it always bugged me that call needed to be aware of compose. But now that I have open def it's cleaner.
