Arc Forumnew | comments | leaders | submitlogin
Defcall for numbers: Multiplication?
4 points by rocketnia 4901 days ago | 3 comments
This is kind of a reply to http://arclanguage.org/item?id=12841, where waterhouse said,

I'll add that numbers and atoms are... atomic. Pure and indivisible, the building blocks that you can make everything else in Lisp with. I'm fine with compound data structures being functions, because they can be implemented with functions as featureful as you want, but I think atoms should be simple, basic pieces.

IMO, it would be fitting if types that simulated algebraic fields had multiplication be their function call behavior. That way you get things like this:

  (/ (+ -.b (sqrt:- b.b 4.a.c))
     2.a)
Continuing along these lines, matrices could be used directly in places where linear transformation functions are expected. Maybe matrices aren't a strong point of Arc just yet, but we can still prepare for them. :-p

Another 'defcall option I've thought about is the Church numeral interpretation of natural numbers. Namely, we could have 3.f be the same as f:f:f. I think this is a bit more axiomatic and elegant, but it suggests an impractical math API design (inefficient Church arithmetic), and it's not as clearly extensible to negative numbers, rationals, etc.

So, suppose we do have function calls perform multiplication over fields. We could still have field-bound numbers do interesting things with values outside their own field. For instance, as long as we consider '+ to be the standard thing to extend when defining monoid operations like concatenation, then if we have (3 '(a b c)) rely on '+, we can end up with the meaningful behavior (a b c a b c a b c).

In fact, if we have a type of value that has a unary function meaning but no (other) obvious monoid meaning, we can treat it as a monoid under function composition. If we do, 3.f will actually have its Church numeral interpretation for those values of f. Since Church numerals multiply when they're applied to each other anyway, natural numbers will end up sharing a lot of their behavior with this new function type, so there may be times the numbers can be used in place of the special functions without any explicit case-checking code.

Pretty elegant, huh? ^_^ Would multiplication be less useful than raising an error? Are there better ideas this approach misses out on?



1 point by waterhouse 4901 days ago | link

Interesting... very interesting. I have to say I like it. I suppose it makes theoretical sense: you don't need numbers to write a Lisp that can do 'eval, and they could in fact be implemented as whatever you like. Integers are only fundamental because they're fundamental to the machines that implement everything. And that is so elegant:

  (/ (+ -.b (sqrt:- b.b 4.a.c))
     2.a)
It's very reminiscent of using juxtaposition, as in "4xy", to represent multiplication; also of using little dots, as in "4·x·y". And, notwithstanding my dislike for using '+ for concatenation (which I could perhaps get used to), (3 '(a b c)) is quite nice--and it even fits the "juxtaposition as multiplication" rule. (We have a macro called n-of which does this too (though it multiply-evaluates), but it's nice when you don't need that.)

The only possible problem I can think of is difficulty of (efficient) implementation. Methinks a good Arc compiler will have to be extremely good with type inference, or perhaps a JIT compiler.

Other thing: Regarding the design of things that "simulate algebraic fields": Note that this might eventually lead to conflicts if you create a general-purpose algebra system, in which objects like polynomials are built from lists or hash tables, and you expect to be able to multiply diverse things with (poly n) [where poly = polynomial and n = integer], because that would require overriding lookups, which might destroy the functions that work with those objects. However, lists could be accessed anyway with car and cdr, and perhaps we should make a 'hash-ref function that will work no matter what. (A more heavy-duty solution might be to tag, or 'annotate, objects. Perhaps I should try that.)

-----

1 point by rocketnia 4901 days ago | link

It's very reminiscent ... also of using little dots, as in "4·x·y".

Wow, I missed that. XD I was mainly thinking of juxtaposition.

The only possible problem I can think of is difficulty of (efficient) implementation.

Yeah, certainly an issue. Optimized code can use (* 4 a c) like usual though.

Other thing

Custom types should already use 'annotate when they need custom 'defcall behavior, right? For instance, if ax^2+bx+c is built using (annotate 'poly (list a b c)), you can index it using rep._.i and call it using _.i. If you're talking about having polynomial calls do polynomial multiplication instead when they're called, then you may have a design conflict (although I think the cases are mostly distinguishable here).

Anyway, as you sorta suggest, the multiplication of diverse things is still a bit weird in general. The concern I have in mind is that multiple dispatch rears its head. I think I'd end up doing something like this (untested!):

  ; Extend numbers so that they use '* as their call behavior.
  (mac defmulttype type
    `(defcall ,type form (apply * form)))
  defmulttype.int
  defmulttype.num
  
  ; Define another variable bound to '* so we won't lose track of it
  ; when we redefine it.
  (= *-base *)
  
  
  ; Define an extensible binary version of '*. This part's rudimentary
  ; for laziness's sake.
  
  (def *-binary (a b)
    (err:+ "Can't multiply " a " by " b "."))
  
  (def fn-defmult (test-a test-b body)
    (zap testify test-a)
    (zap testify test-b)
    (let old-*-binary *-binary
      (= *-binary (fn (a b)
                    (if (and do.test-a.a do.test-b.b)
                      (do.body a b)
                      (do.old-*-binary a b))))))
  
  (mac defmult (test-a test-b . body)
    `(fn-defmult ,test-a ,test-b (fn (a b) ,@body)))
  
  
  ; Define '* in terms of '*-binary. It's left-associative.
  (def * args
    (case args nil 1
      (reduce *-binary args)))
  
  ; Make multiplication with a nonnegative integer on the left use '+.
  (defmult [and (isa _ 'int) (<= 0 _)] [do t]
    (apply + (n-of a b)))
  
  ; Provide the multiplication cases that used to be built in,
  ; overriding the integer rule in the process.
  (defmult number number
    (*-base a b))
This gives just enough multiple dispatch for people to put (defmult [isa _ 'poly] [isa _ 'int] ...) in one library and (defmult [isa _ 'poly] [isa _ 'snargle] ...) in another one, and they can use (defmult 'poly [do t] ...) if they only need single dispatch.

I'd also give an actual example of using polynomials, but I'm out of time. :-p It would have just been an exploration of having (defmult [isa _ 'poly] isa-poly-arg ...) and (defmult [isa _ 'poly] [isa _ 'poly] ...) be separate cases.

-----

1 point by rocketnia 4901 days ago | link

This is kind of a reply to http://arclanguage.org/item?id=12841

Just quoting that for linkification. ^^;

-----