Re: User definable operators

jdean@puma.pa.dec.com (Jeff Dean)
18 Dec 1996 00:08:11 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: User definable operators cef@geodesic.com (Charles Fiterman) (1996-12-15)
Re: User definable operators mslamm@pluto.mscc.huji.ac.il (Ehud Lamm) (1996-12-15)
Re: User definable operators ddean@CS.Princeton.EDU (1996-12-15)
Re: User definable operators dennis@netcom.com (1996-12-15)
Re: User definable operators fjh@mundook.cs.mu.OZ.AU (1996-12-15)
Re: User definable operators burley@gnu.ai.mit.edu (Craig Burley) (1996-12-18)
Re: User definable operators jdean@puma.pa.dec.com (1996-12-18)
Re: User definable operators neitzel@gaertner.de (1996-12-18)
Re: User definable operators tim@franck.Princeton.EDU (1996-12-20)
Re: User definable operators nkramer@cs.cmu.edu (Nick Kramer) (1996-12-20)
Re: User definable operators hrubin@stat.purdue.edu (1996-12-24)
Re: User definable operators preston@tera.com (1996-12-26)
Re: User definable operators burley@gnu.ai.mit.edu (Craig Burley) (1996-12-26)
[11 later articles]
| List of all articles for this month |

From: jdean@puma.pa.dec.com (Jeff Dean)
Newsgroups: comp.compilers
Date: 18 Dec 1996 00:08:11 -0500
Organization: DEC Western Research Lab
References: 96-12-088
Keywords: design

William Clodius (wclodius@lanl.gov) wrote:
: Many programming languages allow the user to overload of language
: defined operators. But a few languages also allow the user to define
: their own operators. I would like to have some feedback on the
: experience of others with user definable operators with respect to
: specifying their syntax, associativity, precedence, semantics (e.g.,
: side effects or not), etc.


You might be interested in how the Cecil language handles this. Cecil
allows programmers to define their own infix binary operators (as well
as user-defined unary operators). The following excerpt from the
Cecil Language Specification Manual describes how operator precedence
and associativity are specified through user-defined declarations.


More info about Cecil's approach can be found from the following URLs
(most-specific to least-specifc):


o Specific section of the above manual describing precendence declarations,
including a comparison of Cecil's approach with that of Self and ML (sorry
for the long URL/long line):
    http://www.cs.washington.edu/research/projects/cecil/www/Refman/wmwork/www/cecil-spec_11.html#HEADING34
o Cecil Language Specification & Rationale document:
    http://www.cs.washington.edu/research/projects/cecil/www/Papers/cecil-spec.html
o UW Cecil Project home page:
    http://www.cs.washington.edu/research/projects/cecil/


----------------------------------------------------
2.6.2 Precedence and Associativity Declarations in Cecil


Cecil allows the precedence and associativity of infix operators to be
specified by programmers through precedence declarations. The syntax of
these declarations is as follows:


        prec_decl ::= "precedence" op_list [associativity] {precedence} ";"
        associativity ::= "left_associative" |
                                            "right_associative" |
                                            "non_associative"
        precedence ::= "below" op_list |
"above" op_list |
"with" op_list
        op_list ::= op_name { "," op_name }


For example, the following declarations might appear as part of the
standard prelude for Cecil:


        precedence ** right_associative; -- exponentiation
        precedence *, / left_associative below ** above +;
        precedence +, - left_associative below * above =;
        precedence =, !=, <, <=, >=, > non_associative below * above;
        precedence & left_associative below = above |;
        precedence | left_associative below &;
        precedence % with *;
        precedence ! left_associative above =; -- array indexing


By default, an infix operator has its own unique precedence, unrelated
to the precedence of any other infix operator, and is non-associative.
Expressions mixing operators of unrelated precedences or multiple
sequential occurrences of an operator that is non-associative must be
explicitly parenthesized.


The effect of a precedence declaration is to declare the relationship
of the precedences of several binary operators and/or to specify the
associativity of a binary operator. Like SML, the information provided
by a precedence declaration is used during the scope of the
declaration, and declarations of the same operator at one scope
override any from an enclosing scope. Two precedence declarations
cannot define the precedence of the same operator in the same scope.


A precedence declaration of the form


        precedence bin-op1, ..., bin-opn
associativity
below bin-opB1, ..., bin-opBn
above bin-opA1, ..., bin-opAn
with bin-opW1, ..., bin-opWn;


declares that all the bin-opi belong to the same precedence group, and
that this group is less tightly binding than the precedence groups of
any of the bin-opBi and more tightly binding than those of the
bin-opAi. If any bin-opWi are provided, then the bin-opi belong to the
same precedence group as the bin-opWi; all the bin-opWi must already
belong to the same precedence group. Otherwise, the bin-opi form a new
precedence group. The associativity of the bin-opi is as specified by
associativity, if present. If absent, then the associativity of the
bin-opi is the same as the bin-opWi, if provided, and non-associative
otherwise. As illustrated by the example above, the ordering of two
precedence groups may be redundantly specified. Cycles in the
tighter-binding-than relation on precedence groups are not
allowed. All operators in the same precedence group must have the same
associativity.


Taken together, precedence declarations form a partial order on groups
of infix operators. Parentheses may be omitted if adjacent infix
operators are ordered according to the precedence declarations, or if
adjacent infix operators are from the same precedence group and the
precedence group has either left- or right-associativity. Otherwise,
parentheses must be included. For example, in the expression


v ! (i + 1) < (v ! i) + 1


the parentheses around i+1 and v!i are required, since ! and + are not
ordered by the above precedence declarations. However, both ! and +
are more tightly binding than <, so no additional parentheses are
required.


In Cecil, a declaration within a declaration block is visible
throughout the block, including during textually earlier declarations
within the block. This applies to precedence declarations as well,
somewhat complicating parsing. The implementation strategy used in
the UW Cecil system parses expressions involving binary operators into
a list of operators and operands, and these lists are converted into a
traditional parse tree form only after all visible declarations have
been processed.


Precedence declarations apply to infix message names, not to
individual methods. Multiple methods may implement the same infix
message, for different kinds of arguments, but all methods with a
particular name share the same precedence in a given scope.
--------------------------------------------------------------------------


In practice, we find that we don't litter Cecil code with arbitrary
user-defined operators. However, we do use them where it makes sense,
and there are often cases where the ability to define new user-defined
operators with arbitrary names truly does make the code more usable.
For example, we realized that we could fairly easily define an
implication operator, and that this could make some of our code more
readable:


    -- Implication operator: A => B
    precedence => non_associative below |;


    -- "implies"
    method =>(l@:bool, r@:bool):bool { not(l) | r }


Cecil also allows operators to consist of normal alphanumeric symbols,
if they are preceeded by an '_' character. This also aids in the
defining of understandable infix operators. For example:


  precedence _is_stronger_than non_associative below _or above =;


  method is_stronger_than(l@cse_information, r@cse_information):bool {... }


  if(A _is_stronger_than B, { ... });


The ability to define new operator symbols, rather than being forced
to graft new semantics onto a set of predefined operators, is
invaluable in having new code be understandable. I agree with our
moderator that grafting new functionality onto an existing predefined
set of operators (ala C++, which uses overloads the shift operators
(<< and >>), because they happen to be the predefined operators that
have the appropriate precedence) results in code that is initially
confusing, because the programmer's mindset does not expect '<<' to be
performing I/O.


-- Jeff


------------------------------------------------------------------------------
Jeffrey Dean (jdean@pa.dec.com) Member of Research Staff
Western Research Laboratory Digital Equipment Corporation
                                      http://www.research.digital.com/people/jdean
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.