Arc Forum | Infix Math

Arc Forum

Infix Math

17 points by eds 6387 days ago | 34 comments

There has been some discussion recently about adding an infix math syntax to Arc. One suggestion I liked involved evaluating an expression as infix when the functional position in a call is filled by a number.

http://arclanguage.org/item?id=2434

To show how this can work, I wrote a function that can be called from ar-apply to evaluate an infix expression. My solution includes basic operator precedence for + - * and /. (You can also use other functions, which have a lower precedence than the math operators, but this is not necessarily suggested.)

This allows

  (3 + 4 * 5 - 6)

rather than

  (+ 3 (- (* 4 5) 6))

You can also do function calls in the middle of infix code

  (3 + (sqrt 16) * 5 - 6)

which would normally be

  (+ 3 (- (* (sqrt 16) 5) 6))

The current implementation is rather naive in that it doesn't do much error checking, but for it should work for reasonable input. It is also probably wildly inefficient, but I figure that is fine for just a demonstration of the concept.

The code can be run by itself, but to make it work in Arc you will need to add the contents of the module infix-eval to ac.scm somewhere, uncomment the line containing

  (,(eval (ac-global-name '+)) 1)

(necessary to make Arc's + operator work properly), and add the following to ar-apply (probably right after the line about string calls)

  ((number? fn) (infix-eval (cons fn args)))

The code can be obtained at the following url. (If people like it I might consider adding it to the git repo.)

http://blackthorncentral.net/files/infix-eval.scm

2 points by cadaver 6387 days ago | link

From the arc1 source:

  ; another possibility: constant in functional pos means it gets
  ; passed to the first arg, i.e. ('kids item) means (item 'kids).

If this gets added to the language, then that's really all the support you need to make even precedence analysis happen; you'll just have to put analysis into the definitions of +-*/ rather than doing it globally in the core.

-----

2 points by vrk 6386 days ago | link

Now that's an interesting idea. However, it would create some confusion if combined with the . operator:

  item!kids   ; Should really be item.'kids
  'kids.item  ; Huh? It's the same?

Granted, it would simplify some expressions, and you would get that "dot operator as in other programming languages" for free.

-----

1 point by eds 6386 days ago | link

I was under the impression cadaver was talking about infix math, because looking in the second position for the functional argument allows infixy syntax analysis.

You could combine it with the dot operator of course but I wouldn't really see a reason for it. (Why would you use 3.+.4 instead of (3 + 4)?)

And actually, the example you gave doesn't quite work (because of quote, you can't actually put a symbol in the functional position using the . operator).

  arc> (= item (table))
  #hash()
  arc> item!kids
  nil
  arc> 'kids.item
  kids.item

-----

1 point by eds 6387 days ago | link

Yeah, I was looking at that comment right as I was writing my code. It was encouraging to see pg was thinking along similar lines.

But I'm not quite clear on your point about defining precedence in the definitions of +-*/. Perhaps you could elaborate.

-----

3 points by cadaver 6387 days ago | link

Nothing more than that user-code could redefine the arithmetic functions and do exactly the kind of analysis that your infix-eval already does in the core.

infix-eval is like an implicit function that gets added before every number-in-functional-position. If, like the arc1 comment suggests, a literal-in-functional-position gets applied to its first argument (swapped positions), then every infix expression that would have been handled with infix-eval could be handled by the first infix function:

  (1 + 2 * 3)

is currently handled like:

  ([infix-eval] 1 + 2 * 3)

but could also be handled by the first +:

  (+ 1 2 * 3)

The + is passed almost exactly the same info as infix-eval, except that has to account for itself being missing from the argument list.

EDIT: This would also take care of the case where you use infix notation within a prefix expression, e.g. (+ 1 2 * 3), which infix-eval would not get the opportunity to handle. Not sure whether that's important though.

-----

2 points by cadaver 6387 days ago | link

Example, redefining +:

  (def + args
    (infix-eval
      (cons (car args)
            (cons + (cdr args)))))

-----

1 point by eds 6387 days ago | link

Ok, I see what you are saying. It happens that + is already a scheme lambda wrapper around the scheme primitive +, so I guess you'd just modify the existing function. But you would have to add wrappers for the other primitives.

It seems a little strange to me to mix infix and prefix. But I don't see any reason to disallow it.

-----

1 point by eds 6386 days ago | link

After a little work I got +-/* to handle infix evaluation themselves, allowing ar-apply to just switch the positions of the first two arguments. This allows user defined operators, but you have to be careful to make a base case for after infix to prefix conversion. For example:

  (def % args
    (if (some [isa _ 'fn] args)
        (infix-eval (cons (car args) (cons % (cdr args))))
        (apply mod args)))

In (3 % 4 + 5), % will get called twice, once to get the initial infix conversion going, and again after the expression has been converted to prefix. So if you don't have the second case, you'll just get into an infinite loop.

I'm still trying to work out what is the best way to allow user-defined precedence. In the above case, (3 % 4 + 5) will evaluate as (% 3 (+ 4 5)) not (+ (% 3 4) 5), because by default it is lowest precedence. I wrote a little set-precedence function that can be called to do the job:

  (set-precedence % 2)

  (set-precedence % *)

(The second version looks up the precedence of * and sets % to that precedence.)

But this method of setting precedence seems a little like a hack. And it doesn't play nicely with =. Any suggestions would be welcome.

-----

4 points by treef 6387 days ago | link

that is not a bad idea, I was against adding infix stuff to lisp till i saw this this makes 1 still act like lisp and 2 look nice without any sort of additional syntax, good job eds.

-----

2 points by eds 6387 days ago | link

Which 1 and 2 are you referring to exactly? The only points I see right now are those in the previous discussion but those don't entirely make sense in view of your comments.

I was really glad when cadaver suggested this solution to infix syntax. I just don't like the look of expressions like

  +[*[2; f[x/3]]; y]

even if your syntax allows you to shorten math expressions to (for example)

  2*f[x/3]+y

because in my opinion you lose on everything else. But now I'm just rambling....

-----

5 points by cadaver 6387 days ago | link

I think treef was simply enumerating the good points.

-----

1 point by eds 6384 days ago | link

I've been working on a version of infix syntax written in arc that relies only on the ability to switch the first and second places in a function call when the functional position contains a number. This means that the solution relies on minimal changes to ac.scm, and can be loaded either automatically or optionally into the running arc toplevel.

I also added setter forms so the user can now define precedence of an operator as such:

  (= (precedence %) 2)

  (= (precedence %) /)

And I also experimented with pg's other suggestion for literals being constant functions when in functional position. I found you can have both that and switching arguments at the same time, for example:

  [3] ; always evaluates to 3
  (3 + 4) ; same as (+ 3 4)
  (3 + 4 * 5 - 6) ; when using my infix library

This version being written directly in arc, it is probably slower than the scheme version. But considering it is much less intrusive to ac.scm, I will probably push this version to the arc-wiki.

The code can be obtained at the following url:

http://blackthorncentral.net/files/infix.arc

Changes to ac.scm required to make this work:

  (define (literal? x)
    ; ...
    (procedure? x) ; to allow (eval `(,+ 3 4))

  (define (ar-apply fn args)
    ; ...
    ((or (number? fn) (symbol? fn)) ; (3 + 4) means (+ 3 4)
     (if (pair? args) (apply (car args) fn (cdr args)) fn))

-----

1 point by eds 6381 days ago | link

Pushed this to the arc-wiki.

This means that infix.arc now gets loaded by default when arc starts. Since infix.arc redefines the existing +-/* operators, if you don't want this to happen when arc loads, you can remove it from the list in libs.arc, then load it or not at your leisure.

-----

2 points by bogomipz 6387 days ago | link

Most of the values in math expressions are in the form of variables. How do you handle that? Stick a dummy number in front like this?

  (0 + x * y * scale)

The compiler will optimize that away, right?

-----

4 points by cadaver 6387 days ago | link

The variables/sub-expressions are first evaluated completely, only then infix analysis will happen. It's exactly like with lists:

  (= somelist '(1 2))
  ...
  (somelist 1)

works just like

  ('(1 2) 1)

does.

As to your second argument, the +-*/ operators are passed as first-class functions, so, there shouldn't be any optimization happening. Worst thing that can happen is that the compiler doesn't understand literal numbers in functional position, or arithmetic operators applied to first-class functions, and signals an error.

-----

4 points by eds 6387 days ago | link

Assuming x, y and scale are numbers, just

  (x * y * scale)

should do the trick. As cadaver said, the arguments are evaluated completely before infix evaluation. So you can also do

  (x * y * (sqrt z))

  (x * Y * (sqrt (t * u + v)))

-----

2 points by bogomipz 6386 days ago | link

Ah ok, in that case this is no less than brilliant! :)

-----

3 points by sacado 6387 days ago | link

Yep, I think that would be great on the git :)

-----

3 points by eds 6387 days ago | link

After a little adventure getting git to work, I added my code to the git repo. (Being new to git, I didn't know you have to add before you can commit, and you have to commit before you can push....)

Everyone feel free to make improvements as you see fit.

-----

3 points by almkglor 6387 days ago | link

defsop would too ^^

-----

1 point by dreeves 6385 days ago | link

Thanks for writing this. I think it would be a lot better if we didn't have to intersperse all that whitespace, like (a+b) vs (a + b). To allow that, arc needs to disallow special characters in variable names. I think the benefits from tricks like this and other syntactic sugar is much more valuable than being able to have symbol names like foo* or w/bar or even set-car.

Think what an awful idea it would be to modify the language of math so that + and - were valid parts of variable names. We treat those specially for a reason.

-----

7 points by kennytilton 6385 days ago | link

Old-time lispers rather enjoy our punctuated names and get great mileage out of (especially) using it to flag special variables thus: foo.

Meanwhile, this is all fun, but exactly how often does one put formulas into code, especially formulas one is forever revising meaning we need the editing to be a breeze?

I doubt I code one formula a year, and I write a lot of code. Maybe the engineers out there should just toss off a w/infix macro within which the highly optimized language of math is understood. A starting point might be a Common Lisp infix package, ask on comp.lang.lisp for recommendations.

-----

4 points by eds 6385 days ago | link

Personally I don't think the whitespace is that much of a problem. Certainly I don't think whitespace makes infix less readable; it probably makes it more readable if anything. And it don't think there is a terribly appreciable difference in typing or reading time because of the extra characters. (Arguably the space bar is the easiest key to hit on the entire keyboard.)

While I wouldn't necessarily miss punctuation characters that much, I don't really think it is worth it just to remove the whitespace from infix expressions. You could interpret +-/* as separate in infix expressions only, but I think that creates unnecessary uniformities in the language.

And I do think that math matters. Maybe there are a lot of areas in which you wouldn't really gain much with the infix notation, but exactly the opposite can be said for other fields. I've been working on simple 2D game in CL, and all the math expressions were getting a bit annoying. I would love to try rewriting it in Arc if Arc ever got bindings to any good game libraries.

-----

3 points by kennytilton 6385 days ago | link

Sorry for my repetitiveness (said the same elsewhere) but The Lisp Way when you need a domain-specific syntax is to implement that with a macro and then use the syntax wrapped by the macro. Then Peter does not need to rob Paul (in this case by impoverishing the Arc naming syntax to get math syntax).

Has anyone looked at the CL infix packages?

-----

2 points by eds 6385 days ago | link

If you will simply go without not having whitespace between operators, then you doesn't need to disallow cool characters in symbols or add macro calls in front of all the infix expressions in your code. Honestly, all you save in whitespace you probably spend immediately in having to make the call explicit. I like that the current system integrates infix math seamlessly with s-expressions, that's why I spent my time writing that code. (Admittedly, the infix parts aren't perfect, but the integration itself is fairly seamless.)

I did look at some of the CL infix packages. And if I didn't have programming assignments to work on I might consider porting one.

-----

2 points by dreeves 6385 days ago | link

(Note your foo surrounded by asterisks got interpreted as italics here.)

Could you get most of the same mileage out of capitalization conventions? foo vs Foo vs FOO...

I tried to argue elsewhere that math matters more than you're suggesting: http://arclanguage.org/item?id=2412

I guess this is kind of a religious thing though. :)

-----

2 points by kennytilton 6385 days ago | link

Yeah, I saw that about the foo getting italicized. I guess I'll use octothorpes for asterisks from now one. :)

The coolest hackery has beautiful mathematical gems at the core or in the cleverest bits.

I guess I am not emitting the coolest hackery. :) I know I never put math formulas in my code because it is such a PITA when I do. :) I thought about challenging math infix proponents to post one or two examples from their code, no cheating and contest closed to scientists and engineers.

I do not see it as religious, just a simple question: how often does this come up? And I tried to make another point: this is a Lisp with an intelligible macro mechanism, do what at least one CL project did: write an infix-eating macro! Then you do not need whitespace either, you can have any syntax you want inside the macro. If the task sounds daunting, well that is why I suggested asking on c.l.lisp for the recommended infix package -- just port it to Arc.

-----

2 points by cadaver 6385 days ago | link

There are two concepts under discussion:

First, disallowing arithmetic operators in symbol names, so that (a+b/c) is interpreted like (a + b / c). All the replies to that, up till now, can be summed up like this:

  eds: *I don't really think it is worth it*
  kennytilton: *impoverishing the Arc naming syntax*
  cadaver: *seems not such a good idea after all*

Secondly, whether or not to have some language support for infix. As can be seen in previous discussion, with eds's system, you only need swapped positions where a literal-in-functional-position is encountered for infix support. Paul Graham said that literals in functional position are valuable real estate, nevertheless a comment regarding such an idea can be found in the arc1 source.

One good point of having support is brevity for math-infix users. The only bad point that I see is that we use up the valuable number-in-functional-position real estate, which could have been used for something else.

Supporting infix may not only be good for math. Consider the following:

  (sort (fn (sm gr) (sm < gr)) somelist)

I'm sorry that I can't supply any good examples of heavy maths in real world programs, though I don't doubt that such exist (ciphers?). On the other side, if in a program there isn't any heavy use of maths at all, except for a single mathematical formula that the programmer would like to write in infix, then using a separate macro package would introduce a dependency, and that might make the programmer grudgingly write out the formula in prefix. Another good case for lisp-infix is that when, like me, you tend to copy other's non-lisp formulae then, in eds's infix system, it would look more like its original form.

-----

2 points by kennytilton 6385 days ago | link

Supporting infix may not only be good for math. Consider the following: (sort (fn (sm gr) (sm < gr)) somelist)

Consider: (sort < somelist)

And if (sort (fn (x y) (< x y)) somelist) looks awkward then maybe the issue is prefix altogether? I think anyone trying Arc who is new to Lisp might try Just Lisping (in Arc, of course) for a few weeks before even thinking about changing the language. These things take time and until one has done enough coding to get fluent (or throw up ones hands and say it has been three weeks and I still hate this!) one cannot even form an opinion about the whatever that thing might be. It is like an editor or IDE -- I hated the IDE I love now but made myself wait a month before ripping the vendor a new one. Now people accuse me of being on their sales team.

Case in point: Arc. It is hard judging the brevity/parens stuff because I am in pain anyway without a decent IDE, without a debugger, without a standard library... but I slogged my way thru a port of Cells from Lisp to Arc and some of the brevity is growing on me (I deliberately stopped doing a transliteration and reinvented over the keyboard so I could feel the language better) and at this point I think I can say I would not kick Arc out of bed. Something like that.

btw, if we are just talking about one math formula in a blue moon, why bother? I mean, it would be fun if it had no cost, sure, but apparently pg has plans for numbers in the functional position. Anyway...

-----

2 points by cadaver 6385 days ago | link

cadaver wrote:

  (sort (fn (sm gr) (sm < gr)) somelist)

Yes, a stupid example, sorry.

What are those plans for numbers in the functional position? pg's comments in the arc1 source are completely compatible with eds's system:

Comment 1 is about literal numbers as functions: (1) evaluates to 1

But that is not incompatible with comment two, which is about swapping first and second positions: (1 + 1) evaluates to 2

In fact, math-infix can only benefit if both were added to the language.

-----

1 point by eds 6385 days ago | link

Although literals in functional position may be valuable real estate, I think that infix math is valuable enough to justify using it (at least until we think of something more important).

The only other thing that was suggested in the comment in ar-apply was that literals in functional position might be constant functions. I think infix syntax gives the programmer far more expressive power than being able to denote constant functions.

-----

1 point by cadaver 6385 days ago | link

Since a number-in-functional-position introduces a context for its own s-expression (not for any of its sub-expressions), it would be possible to expand intrasymbol arithmetic, much like with the . and ! notations, only in infix-context.

  (1 + x/y        ;expanded: x / y
   + (w/bar func) ;not expanded, function call

This would effectively keep you from referring to any symbols that contain arithmetic operators from infix-context, but maybe this is not really such a problem.

For this to work you'd need truly first-class macros, since it is not possible to definitely detect infix-context at compile-time:

  (1 + x/y)           ;infix, but may be subject to macro expansion
  ((sqrt 16)*4 + x/y) ;need to decide at runtime

Being able to work with symbols, instead of the functions they are bound to, would also be better for precedence analysis, since infix is essentially a visual thing.

-----

1 point by eds 6385 days ago | link

Possibly. But you still need whitespace in the first position in the call or Arc will try to evaluate the variable a+b rather than the expression (+ a b).

As for precedence analysis, you need some evaluation to happen in order to know that the object in the functional position is a number, after which all your symbols representing functions have been evaluated too.

But even if you did manage to get a hold of the symbols, you would have to make arbitrary decisions about what is an operator and what is a function. (Unless you start evaluating stuff, which gets us back to where we started.) For example, even though expt isn't defined as an operator in the current version, this expression still works:

  (2 expt 3)

You might not get proper precedence when using it like this, but at least it is interpreted correctly as a function.

-----

2 points by cadaver 6385 days ago | link

Regarding infix context

True, (a+b) has no infix context, havn't thought about that; seems not such a good idea after all.

Regarding symbol precedence

Getting hold of the symbols: it's the same with macros, you need some evaluation to happen to know that the object in the functional position is a macro. That's why I said truly first-class macros; the functional position is evaluated first and only then a decision is made to either evaluate the already compiled form in the case of a function call, or to macro-expand the uncompiled form in case of a macro expansion.

Arbitrary decisions about operator/function: macros have all the power, you can handle precedence exactly like in your current system, but get the precedence information by looking up a table with the symbols as keys. This will work exactly the same for functions and yield more predictable precedence for operators.

On the other hand, I'd prefer that functions with undefined precedence were forbidden wherever precedence matters, because it's very easy to unwittingly redefine a function that has precedence defined for it. By itself, (2 expt 3) is fine; no precedence handling necessary.

Think of it as: infix-functions make precedence invisible (masked through the binding, you see the symbol not the function); infix-symbols make precedence obvious.

EDIT: Actually, you wouldn't need first-class macros, if you could redefine "fn" and "set" to handle specially all functions that get bound/assigned to symbols that have some precedence defined for them.

There seems to be some difficulty doing this in arc1; "fn" and "set" are kind of special:

  arc> set
  Error: "reference to undefined identifier: _set"
  arc> fn
  Error: "reference to undefined identifier: _fn"

-----