[haskell/alg] user-defined operator precedence

[Apollo_Futurae]

ik ben een algemene wiskundige rekenmachine aan het schrijven in haskell. je kunt hierbij onder andere je eigen operators definiëren. mijn probleem is nu, hoe ik een gebruiker kan laten aangeven wat de precedence van een nieuwe operator is.

tot nu toe representeerde ik precedence als de plaats die de operator inneemt in een lijst van groepen operators:

code:

[ [ ^ ] , [ * , / ] , [ + , - ] ]

maar ik heb geen idee hoe ik nu iemand moet laten aangeven waar in deze lijst een nieuwe operator terecht moet komen.

complicaties:
- het aantal operators noch het aantal precedence levels staat vast: als je meer modules geladen hebt, zijn er meer operators en meer levels
- de benodigde methode moet ook bruikbaar zijn in batch mode; ik kan dus niet een lijstje met de huidige levels aan de gebruiker presenteren en hem/haar zo een level laten kiezen.

ik zou precedence kunnen representeren als een getal (zoals haskell zelf ook doet), maar dit heeft nadelen:
• het is onmogelijk om een precedence level te creëren tussen twee levels die maar 1 verschillen (of je zou met breuken moeten werken )
• getallen zeggen een gebruiker niets; je moet eerst opzoeken wat de getallen zijn van operators waar je iig boven of onder wil komen in precedence

heeft iemand een alternatieve oplossing of tips?

[Infinitive]

Je zou van een operator een set van relatieve verhoudingen tot andere (misschien niet eens beschikbare) operators kunnen aangeven.

code:

module 1:
"+" `equal priority` "-"

module 2:
"$" `higher_priority` "&&"
">>=" `lower_priority` "&&"

Je kan alleen te weinig informatie hebben om de prioriteiten te bepalen. In het bovenstaande voorbeeld weet je bv niets over de verhouding tussen bijv. "+" en "$".
Degene die nu bijde modules wilt gebruiken zal nu expliciet wat verhoudingen moeten aangeven:

code:

module 3 (uses 1 en 2)

"+" `lower priority` "$"
"+" `higher priority` "&&"

Nog een probleem is dat er ook conflicten kunnen onstaan. Eventueel zou je het dus mogelijk moeten maken bepaalde prioriteiten te overriden (maar dan slechts op module-niveau).

[ Voor 14% gewijzigd door Infinitive op 20-04-2003 18:58 ]

[Apollo_Futurae]

Infinitive schreef op 20 April 2003 @ 18:57:
Je zou van een operator een set van relatieve verhoudingen tot andere (misschien niet eens beschikbare) operators kunnen aangeven. (...)

dat is een mooi alternatief, maar je kunt er niet op vertrouwen dat er überhaupt een andere module geladen is waar je aan kunt refereren (in dat geval zou er ook geen probleem zijn trouwens).
daarnaast zouden er bij slechts een paar modules met elk een handvol operator al zeer veel van deze declaraties nodig zijn.
tenzij je zou toestaan dat operatoren uit verschillende modules tot hetzelfde precedence level behoren, maar dat kan problemen opleveren bij het parsen; het is dan de verantwoordelijkheid van de gebruiker om geen operatoren met dezelfde precedence en verschillende associativiteit door elkaar te gebruiken op straffe van een waarschuwing.

[mbravenboer]

In het Syntax Definition Formalism (SDF) wordt ook gewerkt met dergelijke relatieve prioriteiten. Ik heb even een paar voorbeeld opgezocht om te laten zien dat het best compact kan zijn... Zoals je wellicht ziet kan je ook nog aangeven dat bepaalde operatoren dezelfde prioriteit hebben ( tussen { .... } ), waarbij er dan wordt aangegeven hoe ze associeren (left, right).

Expressies in Java:

code:

  context-free priorities
    {
      Expr "[" Expr "]" -> ArrayAccess
      Expr "." Id -> FieldAccess
      Expr "." Id -> MethodId
    }
  >
    {right:
      Expr "++" -> Expr
      Expr "--" -> Expr
    }
  > {right:
      "++" Expr -> Expr
      "--" Expr -> Expr
      "+"  Expr -> Expr
      "-"  Expr -> Expr
      "~"  Expr -> Expr
      "!"  Expr -> Expr
      "(" Type ")" Expr -> Expr
    }
  > {left:
      Expr "*" Expr -> Expr
      Expr "/" Expr -> Expr
      Expr "%" Expr -> Expr
    } 
  > {left:
      Expr "+" Expr -> Expr
      Expr "-" Expr -> Expr
    }
  > {left:
      Expr "<<"  Expr -> Expr
      Expr ">>"  Expr -> Expr
      Expr ">>>" Expr -> Expr
    }
  > {left:
      Expr "instanceof" RefType -> Expr
      Expr "<"   Expr -> Expr
      Expr ">"   Expr -> Expr
      Expr "<="  Expr -> Expr
      Expr ">="  Expr -> Expr
    }
  > {left:
      Expr "=="  Expr -> Expr
      Expr "!="  Expr -> Expr
    }
  >   Expr "&"   Expr -> Expr
  >   Expr "^"   Expr -> Expr
  >   Expr "|"   Expr -> Expr
  >   Expr "&&"  Expr -> Expr
  >   Expr "||"  Expr -> Expr
  >   Expr "?" Expr ":" Expr -> Expr
  > {right:
      LHS "="    Expr -> Expr
      LHS "*="   Expr -> Expr
      LHS "/="   Expr -> Expr
      LHS "%="   Expr -> Expr
      LHS "+="   Expr -> Expr
      LHS "-="   Expr -> Expr
      LHS "<<="  Expr -> Expr
      LHS ">>="  Expr -> Expr
      LHS ">>>=" Expr -> Expr
      LHS "&="   Expr -> Expr
      LHS "^="   Expr -> Expr
      LHS "|="   Expr -> Expr
    }

Content specificatie in een DTD:

code:

  context-free priorities
    {
      Content "?" -> Content
      Content "*" -> Content
      Content "+" -> Content
    }
  > {non-assoc:
      Content "," Content -> Content
      Content "|" Content -> Content
    }

Generieke syntax definitie voor reguliere expressies over non-terminals:

code:

module regexp[Symbol]
 
exports
  sorts RegExp
 
  context-free syntax
    "E"        -> RegExp {cons("empty")}
    Symbol     -> RegExp {cons("sym")}
    RegExp "*" -> RegExp {cons("star")}
    RegExp "+" -> RegExp {cons("plus")}
    RegExp "?" -> RegExp {cons("opt")}
    RegExp "|" RegExp -> RegExp {cons("choice"), left}
    RegExp "," RegExp -> RegExp {cons("seq"), left}
    "(" RegExp ")" -> RegExp {bracket}
 
  context-free priorities
    {left:
      RegExp "*" -> RegExp
      RegExp "+" -> RegExp
      RegExp "?" -> RegExp
    }
  >   RegExp "," RegExp -> RegExp
  >   RegExp "|" RegExp -> RegExp

Overigens zal je de toe te passen prioriteit waarschijnlijk niet tijdens het parsen gaan bepalen (tenzij je een parser genereert). Omdat de prioriteit namelijk soms in de te parsen tekst gedefinieerd staat, is dit een aparte fase na het parsen. Tijdens het echte parsen is alles dan ambigu, maar zolang hier een constructie voor is in je expressie taal, is dat geen enkel probleem. Met behulp van dergelijke amb knopen wordt ook C/C++ nog weleens geparsed.

[ Voor 20% gewijzigd door mbravenboer op 21-04-2003 11:04 ]

[Apollo_Futurae]

mbravenboer schreef op 21 April 2003 @ 10:59:
In het Syntax Definition Formalism (SDF) wordt ook gewerkt met dergelijke relatieve prioriteiten. Ik heb even een paar voorbeeld opgezocht om te laten zien dat het best compact kan zijn... Zoals je wellicht ziet kan je ook nog aangeven dat bepaalde operatoren dezelfde prioriteit hebben ( tussen { .... } ), waarbij er dan wordt aangegeven hoe ze associeren (left, right).

bedankt voor de uitgebreide voorbeelden!
het probleem is, dat de verschillende operatoren worden gedefinieerd in verschillende modules, die in principe onafhankelijk zijn (er zullen natuurlijk wel afhankelijkheden zijn, maar niet tussen elke mogelijke combinatie van twee modules, ook niet indirect). ik zal er eens over nadenken, of de door jou aangedragen methode hieraan aan te passen is.

Overigens zal je de toe te passen prioriteit waarschijnlijk niet tijdens het parsen gaan bepalen (tenzij je een parser genereert). Omdat de prioriteit namelijk soms in de te parsen tekst gedefinieerd staat, is dit een aparte fase na het parsen. Tijdens het echte parsen is alles dan ambigu, maar zolang hier een constructie voor is in je expressie taal, is dat geen enkel probleem. Met behulp van dergelijke amb knopen wordt ook C/C++ nog weleens geparsed.

dit is gelukkig geen probleem: ik parse modules regel voor regel en na elke regel wordt de parser aangepast aan eventuele toegevoegde operatoren. zo voorkom ik ook wederzijdse afhankelijkheid van functies, operatoren en modules. (ik vraag me nu opeens af of dit niet belemmerend is. zijn er situaties denkbaar in deze context waarin wederzijdse afhankelijkheid noodzakelijk is?)

[mbravenboer]

Apollo_Futurae: het probleem is, dat de verschillende operatoren worden gedefinieerd in verschillende modules, die in principe onafhankelijk zijn

SDF is ook modulair en je kan prioriteiten dus ook verdelen over verschillende modules. Ook kunnen modules in sommige samenstellingen (complete gramaticas) wel of niet toegepast worden. Je kan dus ook prioriteiten verspreiden over verschillende modules.

dit is gelukkig geen probleem: ik parse modules regel voor regel en na elke regel wordt de parser aangepast aan eventuele toegevoegde operatoren.

Als je dit zeer strikt toepast speelt dat probleem inderdaad niet, maar je moet dan wel van de gebruiker eisen dat alle operator prioriteit declaraties altijd voor de toepassingen van die operatoren komen. Dit kan problematisch worden bij meerdere operatoren, in meerdere modules, met in verschillende modules prioriteit declaraties.

Ik denk eerlijk gezegd dat het makkelijker (voor zowel jezelf als de gebruiker) is om het oplossen van prioriteiten conflicten van door de gebruiker gedefinieerde operators los te zien van het parsen ...

[Apollo_Futurae]

mbravenboer schreef op 21 April 2003 @ 13:45:
Als je dit zeer strikt toepast speelt dat probleem inderdaad niet, maar je moet dan wel van de gebruiker eisen dat alle operator prioriteit declaraties altijd voor de toepassingen van die operatoren komen. Dit kan problematisch worden bij meerdere operatoren, in meerdere modules, met in verschillende modules prioriteit declaraties.

zou je een voorbeeld kunnen geven van de problemen die je verwacht?

Ik denk eerlijk gezegd dat het makkelijker (voor zowel jezelf als de gebruiker) is om het oplossen van prioriteiten conflicten van door de gebruiker gedefinieerde operators los te zien van het parsen ...

ik vind het een beetje eng om het te splitsen. als de parser een geldige operator tegenkomt, is die operator ergens gedefinieerd, dus is de precedence ook gespecificeerd (tenminste, als de gebruiker/library die moeite heeft genomen).

[mbravenboer]

Apollo_Futurae: zou je een voorbeeld kunnen geven van de problemen die je verwacht?

Bijvorbeeld:
- module A definieert een + en gebruikt + en -
- module B definieert een - en gebruikt een + en -
- beide modules importeren elkaar

Hoe ga je dit parsen, of ... hoe vervelend is het als dit verboden is?

[Apollo_Futurae]

mbravenboer schreef op 21 April 2003 @ 16:58:
[...]

Bijvorbeeld:
- module A definieert een + en gebruikt + en -
- module B definieert een - en gebruikt een + en -
- beide modules importeren elkaar

Hoe ga je dit parsen, of ... hoe vervelend is het als dit verboden is?

modules kunnen elkaar niet importeren. eigenlijk bestaat er ook niet zoiets als importeren; je kunt alleen een module laden. dit gaat als volgt:

je laadt een module Test
deze module Test laadt een module Blaat en een module Bliep
module Bliep laadt een module Sub
de modulehiërarchie is dan:

code:

Root
|-Test
  |-Blaat
  |-Bliep
    |-Sub

elke evaluatie heeft toegang tot alle modules die er op dat ogenblik geladen zijn.

hoe vervelend het is dat er geen wederzijdse afhankelijkheden mogen zijn? ik heb werkelijk geen idee, maar ik vermoed dat het in principe niet nodig is.

[Apollo_Futurae]

misschien is een combinatie van de twee belangrijkste opties nog wel het beste.
een nieuw voorstel:

precedence wordt gerepresenteerd als een getal (mogelijk negatief en/of niet-geheel).
een operator definieer je nu als volgt:

code:

a $$ b (none,= - 3,4) := (definitie)
a ~~ b (right,$$,* + 1,6) := (definitie)
b @ (between ~~ =,9) := (definitie)

na de associativiteit komt een door komma's gescheiden lijst van precedences. de elementen van deze lijst worden van links naar rechts geprobeerd. er zijn drie mogelijkheden voor een element:
• between operator operator: de nieuwe operator krijgt een precedence die precies tussen de precedences van de twee aangegeven operators ligt, mits deze beide bestaan.
• operator (+/- getal): de nieuwe operator krijgt de precedence van de aangegeven operator, mits deze bestaat, eventueel plus/min het aangegeven getal.
• getal: de nieuwe operator krijgt de aangegeven precedence.

als alle elementen falen, krijgt de gebruiker een foutmelding, maar dit hoeft nooit te gebeuren: je moet gewoon altijd als laatste in de lijst een getal geven.

[ Voor 9% gewijzigd door Apollo_Futurae op 21-04-2003 19:25 . Reden: extra mogelijkheden toegevoegd ]