Jak radzić sobie z długimi liniami w Pattern Matching?

Czy pattern maching to regexp 2.0? W sensie brzydki i ciężko coś wydzielać? Alternatywą jest chyba tylko drabina ifów które będą o wiele bardziej rozwlekłe i przez to gorzej czytelne?

Mój przypadek dotyczy Haskella ale pewnie można to spotkać w każdym języku który gdzie jest pattern matching. Mam sobie kod:

peepholeOptimize2 :: InstructionList -> InstructionList
peepholeOptimize2 (IAL (SPure (Cons c)) : IAL (SPure (Indexed (IImmediate i) Move)) : ICF (Labeled LTop (Branch t)) : il) = optimizeBranchCondition i t c <> peepholeOptimize2 il
peepholeOptimize2 (i : il)                                                                                                = i : peepholeOptimize2 il
peepholeOptimize2 []                                                                                                      = []

Na pytanie czemu to takie brzydkie odpowiadam: to wiem właśnie to chciałym rozwiazać.
Na pytanie czemu to wygląda jak assembler tylko poziomo - bo to jest fragment optymalizatora mojego ezoterycznego asemblera dla maszyny stosowej. Chodzi o to żeby w programie napisanym w esoasemblerze wyłapać fragment

pushConst *const*       # liczba do przetestowania
moveImediate *index*    # ładuje wartość labele gdzie skoczyć na szczyt stosu (tak, labele są liczbami naturalnymi jak w basicu, ale można na nich jeszcze robić obliczenia artymetyczne :D ) 
branch *testCondition*  # jak EZ (Equals Zero) lub LTN (Less Then Zero)

na skok kezwarunkowy lub brak skoku w zalezności od tego co uda się wyliczyć podczas optymalizacji

Reszta funkcji odpowiada za żeby wywołać się rekurencyjnie dla kolejnych przypadków lub zwrócić pustą listę dla końca listy instruckji.

Aktulanie to jest mój najdłuższyb przypadek, ale czuję że będą dłuższe :D Pytanie czy macie jakies pomysły co można z tym zrobić? Czy ktoś z was pisał kod gdzie matchowało się 3, 4, 5 elementów listy?

UPDATE w Scali wiem jakie by mogło być rozwiązanie, np trzymać to jako PartialFunction. Ale nawet jeśli można w scali to czy to dobre rozwiązanie?

Jak dla mnie pattern marching to jest biedna próba podejścia deklaratywnego w imperatywnych językach, i często wydaje mi się że nawet gorzej zrobiona niż regexpy.

Riddle napisał(a):

Jak dla mnie pattern marching to jest biedna próba podejścia deklaratywnego w imperatywnych językach,

OK, ale to jest przykład z Haskella więc trudno o bardziej deklaratywny język ogólnego przeznaczenia (ogólnego przeznaczenia czyli język do klepania CRUDów :P )

@Riddle: W takim razie może znasz jakąś deklaratywną alternatywę dla pattern marchingu?

KamilAdam napisał(a):

Czy pattern maching to regexp 2.0? W sensie brzydki i ciężko coś wydzielać? Alternatywą jest chyba tylko drabina ifów które będą o wiele bardziej rozwlekłe i przez to gorzej czytelne?

jeśli pattern matching działa na AST to jest to zupełnie coś innego niż regex. z drugiej strony peephole optimization działające na jakimś bajtkodzie dającym się opisać gramatyką regularną mogłyby być właśnie ogarnięte przez regexy. zależy czy chcesz się w to pchać.

UPDATE w Scali wiem jakie by mogło być rozwiązanie, np trzymać to jako PartialFunction. Ale nawet jeśli można w scali to czy to dobre rozwiązanie?

myślę, że akceptowalne. dodatkowo w scali pattern matching można sobie zmodularyzować za pomocą extractor objects z metodą unapply: https://docs.scala-lang.org/tour/extractor-objects.html wtedy możesz sobie skrócić sam pattern matching (wydzieilć logikę pattern matchingu do tego extractor objectu) i mieć np kod typu:

object PeepCompareConstantsAndBranch {
  def unapply(instructions: List[Instruction]): Option[(Constant, Pointer, ComparisonType, List[Instruction])] = {
    instructions match {
      case <original code for matching> => Some((constant, pointer, cmpType, nextInstructions)) // matched, so return some
      case _ => None // not matched, so return none
    }
  }
}

def peepholeOptimize2(instructions: List[Instruction]): List[Instruction] = instructions match {
  case PeepCompareConstantsAndBranch(constant, instructionPointer, comparisonType, nextInstructions) =>
    optimizeBranchCondition(constant, instructionPointer, comparisonType) ::: peepholeOptimize2(nextInstructions)
  case ... => ... // more cases
}

ps:
javowego bajtkodu raczej się nie ogarnie regexpami przez wzgląd na instrukcje lookupswitch i tableswitch: https://en.wikipedia.org/wiki/List_of_Java_bytecode_instructions

LLVM oraz GCC podchodzą do tego tematu z wykorzystaniem osobnej składni do pattern-matchingu - w przypadku LLVM jest TableGen, a w GCC jest GIMPLE:

https://github.com/gcc-mirror/gcc/blob/0c5e64c4249322a178e1a0e843874e4d6b43b992/gcc/match.pd#L776

/* X - (X / Y) * Y is the same as X % Y.  */
(simplify
 (minus (convert1? @0) (convert2? (mult:c (trunc_div @@0 @@1) @1)))
 (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type))
  (convert (trunc_mod @0 @1))))

(https://medium.com/@prathamesh1615/adding-peephole-optimization-to-gcc-89c329dd27b3)

Przy czym spora część optymalizacji w obydwu kompilatorach jest mimo wszystko oparta na imperatywnym "seek and destroy":

https://github.com/llvm/llvm-project/blob/a38b2d77610fe4541892e335230611772399f83e/llvm/lib/CodeGen/PeepholeOptimizer.cpp#L1368

Patryk27 napisał(a):

LLVM oraz GCC podchodzą do tego tematu z wykorzystaniem osobnej składni do pattern-matchingu - w przypadku LLVM jest TableGen, a w GCC jest GIMPLE:

nawet hotspot (jvm) ma własnego DSLa to pattern matchingu

Przy czym spora część optymalizacji w obydwu kompilatorach jest mimo wszystko oparta na imperatywnym "seek and destroy":

hotspot też :)

przypuszczam, że problem z tymi DSLami jest taki, że prawdopodobnie trudno się takie coś debuguje. hotspot ma narzędzie o nazwie "ideal graph visualizer" do przeglądania AST wypluwanego przez poszczególne fazy optymalizacji (przykładowy artykuł pokazujący to narzędzie: https://robcasloz.github.io/blog/2021/04/22/improving-the-ideal-graph-visualizer.html ). myślę, że budowanie samemu takiego narzędzia (do hobbystycznego języka) jest trochę przesadą i pewnie lepiej po prostu naklepać kod taki jak podałem wyżej i mieć normalne standardowe debugowanie. oczywiście to tylko spekulacje, więc traktujcie to jako luźną opinię i sami oceńcie.

KamilAdam napisał(a):

Riddle napisał(a):

Jak dla mnie pattern marching to jest biedna próba podejścia deklaratywnego w imperatywnych językach,

@Riddle: W takim razie może znasz jakąś deklaratywną alternatywę dla pattern marchingu?

Znaczy według mnie takie miksowanie paradygmatów jest od strzała skazane na porażkę.

Jeśli chce się to ogarnąć to lepiej pisać moim zdaniem 100% deklaratywnie albo 100% imperatywnie (np FP+OOP). Moim zdaniem takie robienie trochę tak trochę tak jest średnie.

@Riddle: piszesz jakimś szyfrem chyba, bo nie rozumiem do czego chcesz nas przekonać

1. programowanie funkcyjne stoi na pattern matchingu.
2. widzisz gdzieś tutaj programowanie imperatywne?

KamilAdam napisał(a):

wyłapać fragment

pushConst *const*       # liczba do przetestowania
moveImediate *index*    # ładuje wartość labele gdzie skoczyć na szczyt stosu (tak, labele są liczbami naturalnymi jak w basicu, ale można na nich jeszcze robić obliczenia artymetyczne :D ) 
branch *testCondition*  # jak EZ (Equals Zero) lub LTN (Less Then Zero)

Czy to musi być pattern matching?

Bo kurczę, jak masz wykryć 3 instrukcje wg jakiegoś schematu, to nazywaj to sobie optymalizacją, ale dalej jak dla mnie to pewien rodzaj parsowania. Więc nie możesz tego sparsować tak, jak resztę?

czyli masz wzorzec listy instrukcji do wykrycia:

1. pushConst const
2. moveImediate index
3. branch testCondition

wtedy przechodzsz optymalizatorem po kolejnych instrukcjach i za jedną iteracją wykrywasz tylko jedną instrukcję. I próbujesz przyrównać to do różnych wzorców. I masz np.

pushConst 42

i widzisz, że odpowiada to wzorcowi pushConst *const* więc sobie to odnotowujesz, później idziesz dalej, widzisz linijkę

moveImmediate 1234

i jednocześnie patrzysz na kolejną część wzorca moveImmediate *index*, bo też pasuje
I albo dojdziesz do końca wzorca (jest match!) albo coś się nie będzie zgadzać po drodze i nie ma dopasowania.

Tak zrobiłem przynajmniej, jak się bawiłem w robienie biblioteki JS do wykrywania różnych patternów.

Innymi słowy wydaje mi się (o ile dobrze zrozumiałem twój problem), że twój problem można przeformułować na:
masz ciąg [a, b, c, d, x, b, c, a, b, v, d
i musisz znaleźć wszystkie ciągi ab*d.
czyli odpowiedzią będzie abcd, abvd
natomiast to można rozwiązać idąc element za elementem.
nie trzeba łapać od razu 4 elementów naraz.

LukeJL napisał(a):

Bo kurczę, jak masz wykryć 3 instrukcje wg jakiegoś schematu, to nazywaj to sobie optymalizacją, ale dalej jak dla mnie to pewien rodzaj parsowania. Więc nie możesz tego sparsować tak, jak resztę?

czyli masz wzorzec listy instrukcji do wykrycia:

1. pushConst const
2. moveImediate index
3. branch testCondition

Tylko ja nie zawsze dostanę tak prosty kod. Może być też coś w rodzaju:

pushConst 0
pushConst 4
sub         # wyliczanie waruneku (liczby do przetestowania)

pushConst 5
pushConst 1
sub         # wyliczanie indeksu
move        # pobiera indeks ze stosu i zamienia na *label*

branch NE   # pobiera warunek i label ze stosu

Ogólnie to najpierw parsuje. Potem wyliczam wszystkie wartości (jak push 0; push 4; sub) a potem przepuszczam to przez trzy różne funkcje peepholeOptimize które podmieniają operacja proste na bardziej złożone, a złożone zamieniają na prostsze jeśli można dokonać uproszczenia

Chociaż coś w tym jest , teraz jak o tym myślę. Czytałem o jednej bibliotece do parsowania do Haskella i ona potrafi pracować nie tylko na 5 rodzajach stringów w Haskellu (String czyli leniwa lista Charów, Text, Lazy.Text, ByteString i Lazy.ByteString :D ) ale także na dowolnych wartościach jeśli mnie pamięć nie myli. Więc można by jej tam użyć. Tylko która to była? I czy dalej jest rozwijana?

a może zrobić jakiś częściowy interpreter? By odpalał program niby normalnie, ale wyliczałby stałe:

pushConst 0
pushConst 4
sub         # wyliczanie waruneku (liczby do przetestowania)

powiedzmy, że pushowałby na stos 0 i 4 i potem by zdjął ze stosu, odjął od siebie i wstawił na stos sam wynik.
Tak jak przy interpretowaniu w maszynie stosowej, tylko tutaj stos wartości byłby jednocześnie stosem instrukcji

no i musiałby wykryć, czy coś da się przeliczyć, czy może jest niewiadoma, której nie da się przewidzieć, bo zależy od jakichś zewnętrznych zmiennych. Wtedy by jakoś omijał taki kod

https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/pattern_synonyms.html

jarekr000000 napisał(a):

https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/pattern_synonyms.html

Nie rozumiem do końca nawet po przeczytaniu dokumentacji. Dodatkowo ja pattern matchuję listę czyli jeden z gorszych rodzajów bo liczba elementów jest zmienna XD

LukeJL napisał(a):

a może zrobić jakiś częściowy interpreter? By odpalał program niby normalnie, ale wyliczałby stałe:

To właśnie miałem na myśli pisząc Potem wyliczam wszystkie wartości (jak push 0; push 4; sub)

LukeJL napisał(a):

dalej jak dla mnie to pewien rodzaj parsowania. Więc nie możesz tego sparsować tak, jak resztę?

Męcząc dalej temat parsowania, przemyslałem to sobie, i jednak sytuacja jest trochę inna. Parser wczytuje 1 lub więcej tokenów (lub brak odpowiedniego tokenu) i na tej podstawie produkuje jeden token (przynajmniej z parserów mi znanych). Ja wczytuję 2 lub więcej tokenów i tworzę na tej podstawie 0 lub więcej tokenów. Ale wpadłem na pewien pomysł. Parsery monadyczne w Haskellu implementują Alternative. I jak spojrzałem to Haskellowe Alternative to na moje oko jest odpowiednik PartialFunction ze Scali, czyli to co szukałem. Chodzi mi głownie o metodę (<|>) (Ah, te nazwy metod w Haskellu XD ), która zdaje się być odpowiednikiem metody orElse ze Scali

@Riddle: dlaczego? Moje pytanie bylo jak zrobić ladnie ifa w haskellu a ty je do inżynierii przenosisz i to prawie dwa miesiace po tym jak otrzymalem odpowiedz i watek jest "do zamknięcia"