Home » forums » LtU Forum

a logic of precedences. Suggestions

Hi, I'm new to programming language theory but like I suppose
everyone else around here I have some ideas about the theme.

Anyways I'm asking about an idea I have for my pet programming language.
It is a mixture of ml syntax, functional, in the future I'll implement a
static typesystem and ultimately add lazy evaluation, but now I'm trapp'd
with this kind of subsystem.

It is a precedence based logic. With it the programmer can
declare precedence and associavity.

Now, suppose we have the basic infix aritmetic 'operators' +, -, *, and div
like this:

+ a b / a + b, +:int->int->int.

We can declare their precedence with:

precedences { aritmetic := {+ - * div}, + = -, * = /, * > + }

or the more cute 'ladder syntax':

precedences { aritmetic := (* div) (+ -) }

I have developed a 'logic of precedences' that can deal with
relations ,= between symbols (function names) and/or classes of
symbols (like the previous aritmetic class) that I still have to refine
but right now it seems fine with pen and paper.

When a program or library grows you can still declare precedences without
the burden to cuantify levels explicitly, just declare relations.
Example, factorial:

! n / n !.
	precedences { ! > aritmetic }

I know that the emblematic languages like ocaml or haskell don't provide
such expresive feature. And they have limited levels of associativity. Why?
Do they envisioned that this feature is unimportant?

What do you think about this idea of declaring precedences with a 'logic system'?

The language will have types like disjoint sets (a la ocaml's but with
no restriction in the syntax of constructors). A sugaring feature is the
alternative type declaration called 'lexems' instead of 'type'. This mode
raises an invariant to the system that no function extern to the module
where it is declared will use a parameter of this type. So, they can be
safely used as lexems and data structures in DSLs.

With types declared as lexems, aplication modes of functions and precedence system
the if-then-else control structure can be coded like this (% is comments):

% control structures for if-then-else
lexemas iftest := { iftest(bool) }
lexemas elsesol x := { thensol(x) elsesol }

% declarations (not required but useful to see ugly types)
if / if : bool -> iftest bool.
then ifcont thenexp / ifcont then thenexp, then : iftest -> x -> elsesol x.
else thencont elseexp / thencont else elseexp, else : elsesol x -> x -> x.

% this declaration puts 'if' 'then' 'else' operators to a 'ifexp' class
% (classes of precedence are useful to handle DSLs or operators related
% as a whole). It reads as: "'if' has more precedence than 'then', and 'then'
% has more precedence than 'else'; all of then put on a class 'ifexp' whose
% precedence level is greater than the rest of functions, including default
% aplication level". It also raises the invariant that no other declaration 
% can mess with their relation nor merge between the 'ifexp' owned levels 
% so from this point of view the DSL is unaltered.
fixed_precedences { ifexp := if then else, ifexp > all, }

% if-then-else implementation (requires lazy evaluation, naturally)
if b = iftest(b).

then ifcont exp = ifcont
 con iftest(true) -> thensol(exp)
 con iftest(false) -> elsesol.

else branch elseexp = branch 
  con  thensol(x) -> x
  con  elsesol -> elseexp.

By fbraunin at 2011-04-06 02:30 | LtU Forum | previous forum topic | next forum topic | other blogs | 4955 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Why not?

The problem with allowing unconstrained definition of associativity and precedence is that it can change the meaning of existing code.

And if its constrained to new operators, there can be differences of associativity and precedence for the same operator defined in two separate libraries, meaning that you can't use them together.

By LexTrotman at Wed, 2011-04-06 03:07 | login or register to post comments

That's the burden this system avoids

I think I dont understand that point because I'm assuming any module
is unique and any function is defined in a module. So there would be
no colision.

Of course you can use this just to make something with no meaning
but if you intend it, it scales and is very deterministic.

Besides, every new function defined is automatically located in
the 'base' class (as a default) so if you just want prefix aplication
just ommit the precedences, on the other side the fact that a programmer
can identify every function (previously defined) and/or groups of
functions makes it more easy.

And also there are some useful fake clases exported by the system, those
can be acceced only on a relation.

  - base: contains any symbol which has not modified it's default precedence
	  level. 
  - all:  contains all the symbols on the system.
  - clases: contains all the symbols belonging to a class. These fake classes
            aren't considered.
  - noclased: contains all the symbols not belonging to any class. Fake classes
	      aren't considered.

I'm not that creative person but I think that on every comment I'll add
a function or DSL ussing the expressed tools to make my point.

Example, factorial:

! n / ! n .
precedences { ! > arithmetic }

By fbraunin at Wed, 2011-04-06 22:59 | login or register to post comments

I was simply providing some

I was simply providing some possible answers to your question why most languages do not allow unconstrained setting of associativity and precedence.

If a + b * c had the precedence of * below that of + it would be very confusing for anyone trying to maintain the code. So most languages allow me to define + and * on my number type but not change the precedence and associativity.

Most languages allow importing symbols from separately compiled modules so most languages would be vulnerable to clashes. You can disambiguate based on the classes of operand, but you can't identify the operands until you know the precedence and associativity, eg in a + b * c is * disambiguated on (type of b, type of c) or on (return type of +, type of c)? If there is a clash in associativity and/or precedence the compiler and human can't tell.

By LexTrotman at Wed, 2011-04-06 23:25 | login or register to post comments

Reminds me of a few things...

I have no idea why designers of popular functional languages chose their particular infix systems. But your questions reminded me of a few things.

First, utility theory. Check it out, especially w.r.t. preference orderings. Preferences - basically, your precedences - have to follow certain rules, and are generally trickier to deal with than utilities. Combining a bunch of preferences means some kind of voting system, if you don't reject incompatible preference orderings outright. And then you run into Arrow's impossibility theorem and other nasty negative results.

Utilities never have these problems. I wouldn't say that that's why the designers of, say, Haskell, went with precedence levels - basically, utilities - but they may have had similar issues in mind.

Second, your idea reminds me of method resolution in multiple-argument dispatch OO, like in CLOS. It's not at all the same thing, but seems related. Last I heard, Perl 6 had a particularly stupid way to do it, which amounted to voting, which runs into Arrow's impossibility theorem. Imagine modules trying to game method dispatch in the same way that political parties try to game voting systems. Ick. Try to avoid this.

Third, you'll want to make sure your precedence system is compositional: it shouldn't matter what order precedences are declared in. It would be confusing if "import foo; import bar" entailed different operator precedence in the following code than "import bar; import foo".

Good luck!

By Neil Toronto at Thu, 2011-04-07 13:20 | login or register to post comments

the workflow that I want to

the workflow that I want to provide feels like hindley-milner on types where you
don't really have to type every function because it can infere them. But there
will always be corner cases where it is needed help from programmer, in this case
you can do multiple assertions against a symbol so to be certain where will
it be confined.

The rules as are in a copybook right now are seemingly subjective but I keep it conservative,
that is, don't invent things that are not declared.

I think I'll start coding it tomorrow all the way down. The funny thing is that when
I envisioned a posible implementation for this I was basically redefining a binary tree...
one of those times when your are inventing the wheel and realize... well I do get afraid
on those times!!

By fbraunin at Thu, 2011-04-07 23:01 | login or register to post comments

speculating about the relation based precedence system entry

I've posted a blog entry wich refers to the system I've speculated in this post... well it is also an speculation but it maybe useful to
someone if not to me...

here it is: http://asteriscox.blogspot.com/

By fbraunin at Tue, 2011-05-24 23:50 | login or register to post comments