Desen eşleştirme - Pattern matching

Bu makale, işlevsel programlamada kalıp eşleştirme hakkındadır . Diğer kullanımlar için, dizi eşleştirme ve örüntü tanıma konusuna bakın .
Eşleşecek soyut kalıpları tanımlamada değişken eşleştirme ölçütlerinin kullanımı için, normal ifadeye bakın .

Olarak bilgisayar biliminin , desen eşleştirme , belirli bir kontrol eylemidir sekansı arasında jeton bazı bileşenlerinin varlığı için model . Örüntü tanımanın aksine , eşleşme genellikle kesin olmalıdır: "ya bir eşleşme olacak ya da olmayacak." Desenler genellikle diziler veya ağaç yapıları biçimindedir . Örüntü eşleştirmenin kullanımları, bir simge dizisi içindeki bir desenin konumlarının (varsa) çıktısının alınmasını, eşleşen desenin bazı bileşenlerinin çıktısının alınmasını ve eşleşen desenin başka bir simge dizisiyle değiştirilmesini (yani, ara ve değiştir ) içerir.

Dizi kalıpları (örneğin, bir metin dizisi) genellikle normal ifadeler kullanılarak tanımlanır ve geri izleme gibi teknikler kullanılarak eşleştirilir .

Ağaç desenleri, bazı programlama dillerinde , yapısına dayalı olarak verileri işlemek için genel bir araç olarak kullanılır , örneğin, C# , F# , Haskell , ML , Python , Ruby , Rust , Scala , Swift ve sembolik matematik dili Mathematica , ağacı ifade etmek için özel sözdizimine sahiptir. Koşullu yürütme ve buna dayalı değer alımı için kalıplar ve bir dil yapısı .

Genellikle tek tek denenen ve güçlü bir koşullu programlama yapısı veren alternatif modeller vermek mümkündür . Kalıp eşleştirme bazen korumalar için destek içerir .

Ayrıştırma algoritmaları, dizileri sözdizimi ağaçlarına dönüştürmek için genellikle kalıp eşleştirmeye dayanır .

Tarih

Desen eşleştirme yapıları ile Erken programlama dilleri şunlardır COMIT (1957), Snobol (1962), Refal (1968) ağaç bazlı desen eşleştirme ile, Prolog (1972), SASL'yi (1976), takibe (1977) ve KRC (1981).

Birçok metin düzenleyicileri çeşitli desen eşleştirme destekler: QED editör destekleri düzenli ifade arama ve bazı sürümleri TECO aramalarda OR operatörünü desteklemektedir.

Bilgisayar cebir sistemleri genellikle cebirsel ifadelerde örüntü eşleştirmeyi destekler.

Ayrıca bakınız: Normal ifade § Geçmiş

İlkel desenler

Kalıp eşleştirmedeki en basit kalıp, açık bir değer veya bir değişkendir. Örnek olarak, Haskell sözdizimindeki basit bir işlev tanımını ele alalım (işlev parametreleri parantez içinde değil, boşluklarla ayrılmış, = atama değil tanımdır): 

f 0 = 1

Burada 0, tek değerli bir kalıptır. Şimdi, ne zaman f argüman olarak 0 verilirse, kalıp eşleşir ve fonksiyon 1 döndürür. Başka herhangi bir argümanla, eşleştirme ve dolayısıyla fonksiyon başarısız olur. Sözdizimi, işlev tanımlarında alternatif kalıpları desteklediğinden, daha genel argümanlar almak için tanımı genişletmeye devam edebiliriz: 

f n = n * f (n-1)

Burada ilki n, kesinlikle herhangi bir argümanla eşleşecek ve onu tanımın geri kalanında kullanılmak üzere n ismine bağlayacak olan tek bir değişken kalıptır. Haskell'de (en azından Hope'un aksine ), modeller sırayla denenir, böylece ilk tanım, girdinin 0 olduğu çok özel durumda hala geçerlidir, diğer herhangi bir argüman için işlev n * f (n-1), argüman olarak n ile döner .

Joker karakter kalıbı (genellikle olarak yazılır _) da basittir: bir değişken adı gibi, herhangi bir değerle eşleşir, ancak değeri herhangi bir ada bağlamaz. Basit dizi eşleştirme durumlarında joker karakterleri eşleştirmek için algoritmalar , bir dizi özyinelemeli ve özyinelemesiz çeşitte geliştirilmiştir.

Ağaç desenleri

Önceki bölümün ilkel olanlarından daha karmaşık desenler oluşturulabilir, genellikle diğer değerlerin birleştirilmesiyle oluşturulan değerlerle aynı şekilde. O halde fark, değişken ve joker parçalarla, bir modelin tek bir değere dönüşmemesi, ancak somut öğelerin ve modelin yapısı içinde değişmesine izin verilen öğelerin birleşimi olan bir grup değerle eşleşmesidir. .

Bir ağaç deseni, bir düğümle başlayıp bazı dalları ve düğümleri belirterek ve bazılarını bir değişken ya da joker desenle belirtilmemiş bırakarak bir ağacın bir bölümünü tanımlar. Bir programlama dilinin soyut sözdizimi ağacını ve cebirsel veri türlerini düşünmek yardımcı olabilir .

Haskell'de aşağıdaki satır, bir tamsayı ve bir dizeyi saran Colortek bir veri oluşturucuya sahip bir cebirsel veri türünü tanımlar ColorConstructor. 

data Color = ColorConstructor Integer String

Yapıcı, bir ağaçtaki bir düğümdür ve tamsayı ve dize, dallardaki yapraklardır.

Soyut bir veri türü yapmak için işlevler yazmak istediğimizde, veri türüyle arabirime işlevler yazmak istiyoruz ve bu nedenle veri türünden bazı verileri, örneğin yalnızca dize veya yalnızca tamsayı kısmı çıkarmak istiyoruz. . ColorColor

Color türünde bir değişken iletirsek, verileri bu değişkenden nasıl çıkarabiliriz? Örneğin, tamsayı kısmını alacak bir fonksiyon için Colorbasit bir ağaç deseni kullanabilir ve şunu yazabiliriz: 

integerPart (ColorConstructor theInteger _) = theInteger

İlave olarak: 

stringPart (ColorConstructor _ theString) = theString

Bu işlevlerin oluşturulması, Haskell'in veri kaydı sözdizimi ile otomatikleştirilebilir .

Bir kırmızı-siyah ağacı ve öğe eklemeden sonra onu yeniden dengelemek için bir işlevi tanımlayan bu Ocaml örneği, özyinelemeli bir veri türü tarafından oluşturulan daha karmaşık bir yapı üzerinde nasıl eşleştirileceğini gösterir. 

type color = Red | Black
type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with
    | Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)
    | Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)                                  
    | Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))
    | Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))
        ->  Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))
    | _ -> t (* the 'catch-all' case if no previous pattern matches *)

Verileri kalıplarla filtreleme

Model eşleştirme, belirli bir yapının verilerini filtrelemek için kullanılabilir. Örneğin, Haskell'de bu tür filtreleme için bir liste kavrayışı kullanılabilir: 

[A x|A x <- [A 1, B 1, A 2, B 2]]

değerlendirir 

[A 1, A 2]

Mathematica'da desen eşleştirme

In Mathematica , var olan tek yapıdır ağaç sembolleri tarafından doldurulur. In Haskell şimdiye kadar kullanılan sözdizimi, bu şekilde tanımlanabilir 

data SymbolTree = Symbol String [SymbolTree]

Örnek bir ağaç daha sonra şöyle görünebilir 

Symbol "a" [Symbol "b" [], Symbol "c" []]

Geleneksel, daha uygun sözdiziminde, semboller oldukları gibi yazılır ve ağacın seviyeleri kullanılarak temsil []edilir, örneğin a[b,c]ebeveyn olarak a ve çocukları olarak b ve c olan bir ağaç.

Mathematica'daki bir model, o ağaçtaki konumlara "_" koymayı içerir. Örneğin, desen 

A[_]

A[1], A[2] veya daha genel olarak A[ x ] gibi öğelerle eşleşir, burada x herhangi bir varlıktır. Bu durumda, Asomut öğe iken _, değiştirilebilen ağaç parçasını ifade eder. Başına _eklenen bir sembol, eşleşmeyi bu değişken adına bağlarken, sonuna eklenen bir sembol _, eşleşmeleri o sembolün düğümleriyle sınırlar. Boşlukların bile dahili olarak Blank[]for _ve Blank[x]for olarak temsil edildiğine dikkat edin _x.

Mathematica işlevi Cases, ikinci bağımsız değişkendeki kalıpla eşleşen ilk bağımsız değişkenin öğelerini filtreler: 

Cases[{a[1], b[1], a[2], b[2]}, a[_] ]

değerlendirir 

{a[1], a[2]}

Kalıp eşleştirme , ifadelerin yapısı için geçerlidir . Aşağıdaki örnekte, 

Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]

İadeler 

{a[b[c],d], a[b[c],d[e]]}

çünkü yalnızca bu öğeler a[b[_],_]yukarıdaki desenle eşleşecektir .

Mathematica'da, nasıl veya nerede göründüklerine bakılmaksızın, hesaplama sırasında yaratıldıkları gibi yapıları çıkarmak da mümkündür. İşlev Trace, bir hesaplamayı izlemek ve bir modelle eşleşen ortaya çıkan öğeleri döndürmek için kullanılabilir. Örneğin, tanımlayabilir Fibonacci dizisi olarak 

fib[0|1]:=1
fib[n_]:= fib[n-1] + fib[n-2]

O halde şu soruyu sorabiliriz: Fib[3] verildiğinde, özyinelemeli Fibonacci çağrılarının sırası nedir? 

Trace[fib[3], fib[_]]

desenin fib[_]hesaplama yapısındaki oluşumlarını temsil eden bir yapı döndürür : 

{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}

bildirimsel programlama

Sembolik programlama dillerinde, işlevlerin argümanları veya veri yapılarının öğeleri olarak kalıplara sahip olmak kolaydır. Bunun bir sonucu, veri parçaları hakkında bildirimsel olarak ifadeler yapmak ve işlevlerin nasıl çalıştırılacağını esnek bir şekilde öğretmek için kalıpları kullanma yeteneğidir.

Örneğin, Mathematica işlevi Compile, kodun daha verimli versiyonlarını yapmak için kullanılabilir. Aşağıdaki örnekte ayrıntılar özellikle önemli değildir; önemli olan alt ifade olmasıdır {{com[_], Integer}}talimatını Compileformun ifadeleri o com[_]olduğu kabul edilebilir tamsayılar derleme amaçlı olarak: 

com[i_] := Binomial[2i, i]
Compile[{x, {i, _Integer}}, x^com[i], {{com[_],  Integer}}]

İçinde kutuları Erlang de bu şekilde çalışır.

Curry-Howard yazışma provaları ve programlar arasındaki ilgilidir ML için tarzı desen eşleştirme durum analizi ve bitkinlik tarafından ispat .

Desen eşleştirme ve diziler

Açık farkla en yaygın desen eşleştirme biçimi, karakter dizilerini içerir. Birçok programlama dilinde, dize karakterlerini tanımlayan kalıplar olan normal ifadeleri temsil etmek için belirli bir dize sözdizimi kullanılır.

Ancak, bu makale boyunca tartışılan aynı çerçeve içinde bazı dize desen eşleştirmeleri yapmak mümkündür.

Dizeler için ağaç desenleri

Mathematica'da dizeler, kök StringExpression'ın ağaçları ve tüm karakterler de kökün çocukları olarak sırayla temsil edilir. Bu nedenle, "herhangi bir sayıda sondaki karakter" ile eşleşmek için, yalnızca tek bir karakterle eşleşecek olan _ yerine yeni bir joker karakter ___ gerekir.

Haskell ve genel olarak fonksiyonel programlama dillerinde , karakter dizileri fonksiyonel karakter listeleri olarak temsil edilir . İşlevsel bir liste, boş bir liste veya mevcut bir listede oluşturulmuş bir öğe olarak tanımlanır. Haskell sözdiziminde: 

[] -- an empty list
x:xs -- an element x constructed on a list xs

Bazı öğeler içeren bir listenin yapısı şu şekildedir element:list. Kalıp eşleştirmede, belirli bir veri parçasının belirli bir kalıba eşit olduğunu iddia ederiz. Örneğin, işlevde: 

head (element:list) = element

head'nin argümanının ilk öğesinin öğe olarak adlandırıldığını ve işlevin bunu döndürdüğünü iddia ediyoruz . Listelerin tanımlanma şekli nedeniyle bunun ilk öğe olduğunu biliyoruz, tek bir öğe bir liste üzerine inşa edilmiştir. Bu tek öğe ilk olmalıdır. Boş bir listenin başı (oluşturulan ilk öğe) olmadığından, boş liste kalıpla hiç eşleşmez.

Örnekte, için kullanımımız yok list, bu yüzden onu göz ardı edebiliriz ve böylece işlevi yazabiliriz: 

head (element:_) = element

Eşdeğer Mathematica dönüşümü şu şekilde ifade edilir: 

head[element, ]:=element

Örnek dize kalıpları

Örneğin Mathematica'da, 

StringExpression["a",_]

iki karakterden oluşan ve "a" ile başlayan bir dizeyle eşleşir.

Haskell'deki aynı model: 

['a', _]

Bir dizgenin ilgili özelliklerinin birçok farklı sınıfını temsil etmek için sembolik varlıklar tanıtılabilir. Örneğin, 

StringExpression[LetterCharacter, DigitCharacter]

önce bir harf, ardından bir sayıdan oluşan bir dizeyle eşleşir.

Haskell'de, aynı eşleşmeleri elde etmek için korumalar kullanılabilir: 

[letter, digit] | isAlpha letter && isDigit digit

Sembolik dizi manipülasyonunun ana avantajı, ayrı, özel amaçlı bir alt birim olmaktan ziyade programlama dilinin geri kalanıyla tamamen entegre edilebilmesidir. Dilin tüm gücü, kalıpları kendileri oluşturmak veya bunları içeren programları analiz etmek ve dönüştürmek için kullanılabilir.

SNOBOL

Ana madde: SNOBOL

SNOBOL ( String Oriented and symBOlic Language ) 1962 ve 1967 yılları arasında AT&T Bell Laboratuvarlarında David J. Farber , Ralph E. Griswold ve Ivan P. Polonsky tarafından geliştirilmiş bir bilgisayar programlama dilidir .

SNOBOL4, birinci sınıf bir veri türü olarak kalıplara sahip olmasıyla ( yani , değerleri programlama dilindeki diğer herhangi bir veri türüne izin verilen her şekilde değiştirilebilen bir veri türü) ve kalıp birleştirme ve değiştirme için operatörler sağlayarak çoğu programlama dilinden farklıdır. . Yürütme sırasında oluşturulan dizeler, program olarak kabul edilebilir ve yürütülebilir.

SNOBOL 1960'ların sonlarında ve 1970'lerin başlarında daha büyük ABD üniversitelerinde oldukça yaygın bir şekilde öğretildi ve 1970'lerde ve 1980'lerde beşeri bilimlerde bir metin işleme dili olarak yaygın olarak kullanıldı .

SNOBOL'un yaratılmasından bu yana, Awk ve Perl gibi daha yeni diller , düzenli ifadeler aracılığıyla dizi işlemeyi moda haline getirdi . Ancak SNOBOL4 kalıpları, bağlamdan bağımsız gramerlere eşdeğer ve normal ifadelerden daha güçlü olan BNF gramerlerini kapsar .

Ayrıca bakınız

Referanslar

Dış bağlantılar