Title

Syntactic combiners for binary predicates

Author

Panicz Maciej Godek

Status

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-156@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

Recognizing binary predicates as a specific area in which the use of prefix operators is an impediment, we propose a thin layer of "syntactic stevia" for in-fixing such predicates. It can be implemented using regular Scheme macros. We suggest that the code (is x < y) should be transformed to (< x y), and (is x < y <= z) -- to (let ((y* y)) (and (< x y*) (<= y* z))). In addition, we suggest special meaning to the _ symbol: (is _ < y) and (is x < _) should be transformed to (lambda (_) (< _ y)) and (lambda (_) (< x _)), respectively. This SRFI document also describes some other uses of the is macro and its limitations.

Rationale

The power and universality of the prefix notation employed by Scheme and other dialects of Lisp can be intimidating. We find that there are occasions when prefix syntax can be confusing and lead to code that is not self-documenting. We have identified that one of areas is the use of asymmetrical binary predicates.

Probably the most common examples are the numerical comparison predicates <, <=, >= and >. It is non obvious, for instance, how the expression (< a b) should be pronounced.

The problem gets more serious in the case of user-defined binary predicates. For example, in the expression (divisor? x y) the role of arguments is unclear: we don't know whether the author of the divisor? predicate intended it to check whether x is a divisor of y or whether y is a divisor of x.

And while there seems to exist a silent convention among Schemers to interpret predicates like (has-something-to? x y) as "x has something to y", we believe that this convention should be made explicit, and confirmed by the forms available in the language.

In Evolution of Lisp Richard Gabriel and Guy Steele wrote:

The idea of introducing Algol-like syntax into Lisp keeps popping up and has seldom failed to create enormous controversy between those who find the universal use of S-expressions a technical advantage (and don’t mind the admitted relative clumsiness of S-expressions for numerical expressions) and those who are certain that algebraic syntax is more concise, more convenient, or even more natural (whatever that may mean, considering that all these notations are artificial).
However, even though the language of mathematics is an artificial invention of our civilization, there is a tradition of calling our spoken ethnic languages natural.

Ethnic languages usually allow us to express certain binary relations using a sort of infix syntax. We can say, for example, "John is taller than Tom", "Joe is in love with Jane" and so on.

Note that the order in which the elements appear in the sentence is crucial: even if Joe is in love with Jane, it need not be the case that Jane is in love with John; if John is taller than Tom, then it is reasonable to expect that Tom is not taller than John.

It should be apparent that the prefix notation employed by the Scheme programming language obscures the roles of specific objects from the relation. In the expression (taller-than? John Tom) it is unclear whether we mean that John is taller than Tom or the other way around.

Although we could in principle employ a consistent convention regarding the roles of arguments in such relations (and this has indeed been the case so far), the power of Scheme programming language allows us to go beyond a mere convention. In particular, we can extend Scheme with a syntactic form which embodies this convention.

Specification

Infix relations

This document proposes to augment Scheme with a new syntactic form, is, so that, for example, the expression (is John taller-than? Tom) is expanded to (taller-than? John Tom).

In addition to improved code readability, the introduction of the is form gives an occasion to provide some convenient special behaviour in some particular cases. While some Schemers may find the lack of regularity and predictability of the is form repulsive, we believe that it actually allows us to express some common operations more succinctly.

Short-hand lambda expressions

For example, we decided to treat the _ (underscore) symbol differently than other symbols. (is _ taller-than? John) is expanded to (lambda (_) (taller-than? _ John)), thereby making the functionality of the is form partially overlap with the cut special form defined in the SRFI 26 document.

We chose the underscore symbol, although the cut macro uses the <> symbol, because it has been used as a special non-bindable symbol in various pattern matchers for Scheme (as well as in the Prolog language). It has also traditionally been used to name values that are meant to be ignored, so we believe that our choice should not be in conflict with existing practices.

However, the _ symbol should not be bound to a new transformer, but instead it should be imported from (scheme base) and re-exported, so that it can be renamed by the users who prefer to stick with the <> symbol from SRFI-26.

Multiple instances of underscore

If more than one instance of the underscore symbol appears in the argument position of the is and isnt macros, each occurrence counts as a separate argument (increasing the arity of the resulting lambda accordingly). For example, (is _ < _) is equivalent to (lambda (_1 _2) (< _1 _2)).

Negation

In addition to the is form, this SRFI provides an implementation of the isnt form, which negates the behavior of is. Although we didn't find that form particularly useful, we are certain that it may find its use, and if it were absent from the language, Schemers would come up with their own implementations. As a matter of fact, in our experiments with parroting the English language, we initially used the isn't symbol, which failed to work on some implementations.

Handling fewer arguments

The is and isnt macros could technically be passed fewer than three arguments. In particular, we interpret (isnt x prime?) as (not (prime? x)), and (isnt _ prime?) as (lambda (_) (not (prime? _))). For consistency, we interpret the usages of the is macro similarly, although it may not seem particularly useful.

It is illegal to use the is and isnt macros with fewer than two arguments, and such attempts should raise a syntax error.

Handling more arguments

If the is macro is used with more than three arguments, then every second argument must be a predicate. In such case, the macro expands to a conjunction of conditions, in a way that is often used by mathematicians. For example, (is x < y <= z < w finite?) expands to

    (let ((y* y))
      (and (< x y*)
           (let ((z* z))
             (and (<= y* z*)
                  (let ((w* w))
                    (and (< z* w*)
                         (finite? w*)))))))
  
where y*, z* and w* are hygienic identifiers (i.e. they are guaranteed not to shadow any existing bindings).

Other use cases

It might be tempting to abuse the is macro, and come up with usages such as (map (is _ + 1) '(1 2 3)). We discourage such practice and advocate to limit the application of the is macro to binary and unary predicates and equality checking.

The lack of infix definitions

It might be tempting to extend the infix syntax cover not only usages, but also definitions of binary predicates. For example, one could wish to write

  (define/infix (is x divisible-by? y)
    (zero? (modulo x y)))
This SRFI does not provide anything like the define/infix form, as we do not think it is such a good idea. (However, modifying the behavior of the define form to check whether its first argument is is would be a much worse idea.)

We believe that in the definition context it's best to leave the roles of arguments to the convention that has been uttered in this SRFI.

Relation to other SRFIs

SRFI 105 Curly-infix-expressions

Some people may argue that the problem this SRFI is trying to address can be solved by applying the solution provided by the curly-infix-expressions.

However, we find the change proposed by the SRFI 105 very invasive and feel that their authors failed to provide the right justification for their idea. In particular, they didn't notice the difference between infix used with binary predicates and infix used for algebraic operations.

While we do not deny that infix syntax for algebraic formulas has its value, this value manifests itself mainly in the context of mathematical inquiries and education (for example, to explain the concepts of commutativity and associativity), and the context of software creation exposes different characteristics.

SRFI 26 Notation for Specializing Parameters Without Currying

The behavior of the is macro in the presence of the underscore symbol resembles the use of the cut macro. According to our investigation, the use of the cut macro to specialize one of arguments of a binary predicate accounts for some of its most common usages.

While we appreciate the mathematical insight which allows us to perceive fixing specific arguments as making cuts through some multi-dimensional domains, we claim that from the point of view of program comprehension, this insight is usually an irrelevant detail.

Implementation

The implementation consists of five macros. The infix/posix, extract-placeholders and identity-syntax are helper macros and are not intended to be used directly. The is and isnt macros were described in depth in the previous section.
  (define-syntax infix/postfix
    (syntax-rules ()
      ((infix/postfix x somewhat?)
       (somewhat? x))

      ((infix/postfix left related-to? right)
       (related-to? left right))

      ((infix/postfix left related-to? right . likewise)
       (let ((right* right))
         (and (infix/postfix left related-to? right*)
              (infix/postfix right* . likewise))))))

  (define-syntax extract-placeholders
    (syntax-rules (_)
      ((extract-placeholders final () () body)
       (final (infix/postfix . body)))

      ((extract-placeholders final () args body)
       (lambda args (final (infix/postfix . body))))

      ((extract-placeholders final (_ op . rest) (args ...) (body ...))
       (extract-placeholders final rest (args ... arg) (body ... arg op)))

      ((extract-placeholders final (arg op . rest) args (body ...))
       (extract-placeholders final rest args (body ... arg op)))

      ((extract-placeholders final (_) (args ...) (body ...))
       (extract-placeholders final () (args ... arg) (body ... arg)))

      ((extract-placeholders final (arg) args (body ...))
       (extract-placeholders final () args (body ... arg)))))

  (define-syntax identity-syntax
    (syntax-rules ()
      ((identity-syntax form)
       form)))

  (define-syntax is
    (syntax-rules ()
      ((is . something)
       (extract-placeholders identity-syntax something () ()))))

  (define-syntax isnt
    (syntax-rules ()
      ((isnt . something)
       (extract-placeholders not something () ()))))

Acknowledgements

I would like to thank John Cowan for encouraging me to write this SRFI, to Nils M Holm for his early appreciation of this work, and to Marc Nieper-Wißkirchen and Shiro Kawai for the discussion and support. I am also grateful to Bill from the comp.lang.scheme group for helping me trace the uses of the cut macro in the scheme code base.

This document would not see the daylight without the efforts of the editor, Arthur Gleckler, who's doing the great work of keeping the SRFI process running, deserving gratitude from the whole community.

I really appreciate the efforts of the whole Scheme community and every single person who contributed to the development of this beautiful language and culture over the years, and I am happy to be a part of it, however small.

Finally, I would like to thank my friend Ścisław Dercz for sincerely discouraging me from this undertaking. I think his rants contributed positively to the quality of this work (although perhaps not positively enough).

Copyright

Copyright (C) Panicz Maciej Godek (2017). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Arthur A. Gleckler