giriş - Prolog

Prolog
paradigma Mantık
Tarafından tasarlandı Alain Colmerauer , Robert Kowalski
İlk ortaya çıktı 1972 ; 49 yıl önce ( 1972 )
kararlı sürüm
Bölüm 1: Genel çekirdek-Baskı 1 (Haziran 1995 ; 26 yıl önce ) Bölüm 2: Modüller-Baskı 1 (Haziran 2000 ; 21 yıl önce )  ( 1995-06 )
 ( 2000-06 )
Yazma disiplini Türlenmemiş (tek veri türü "terim" dir)
Dosya adı uzantıları .pl, .pro,.P
İnternet sitesi Bölüm 1: www .iso .org /standard /21413 .html
Bölüm 2: www .iso .org /standard /20775 .html
Başlıca uygulamalar
B-Prolog , Ciao , ECLIPSe , GNU Prolog , Poplog Prolog, P# , Quintus Prolog , SICStus , Strawberry , SWI-Prolog , Tau Prolog , tuProlog, WIN-PROLOG , XSB , YAP .
lehçeler
ISO Prolog, Edinburg Prolog
Tarafından etkilenmiş
planlayıcı
Etkilenen
CHR , Clojure , Datalog , Erlang , KL0 , KL1 , Mercury , Oz , Strand , Visual Prolog , XSB

Prolog , yapay zeka ve hesaplamalı dilbilim ile ilişkili bir mantık programlama dilidir .

Prolog'un kökleri birinci dereceden mantığa , biçimsel bir mantığa dayanır ve diğer birçok programlama dilinden farklı olarak Prolog, öncelikle bildirimsel bir programlama dili olarak tasarlanmıştır : program mantığı, gerçekler ve kurallar olarak temsil edilen ilişkiler açısından ifade edilir . Bir hesaplama çalışan tarafından başlatılır sorguyu bu ilişkiler üzerinde.

Dil, 1972'de Fransa'nın Marsilya kentinde, Alain Colmerauer tarafından Philippe Roussel ile birlikte Robert Kowalski'nin Horn cümlelerinin prosedürel yorumuna dayalı olarak geliştirildi ve uygulandı .

Prolog, ilk mantıksal programlama dillerinden biriydi ve birkaç ücretsiz ve ticari uygulama ile bugün en popüler bu tür dil olmaya devam ediyor. Dil, teorem kanıtlama , uzman sistemler , terim yeniden yazma , tip sistemleri ve otomatik planlama için ve ayrıca orijinal kullanım amacı olan doğal dil işleme için kullanılmıştır . Modern Prolog ortamları , idari ve ağ bağlantılı uygulamaların yanı sıra grafik kullanıcı arabirimlerinin oluşturulmasını destekler .

Prolog, veritabanlarında arama , sesli kontrol sistemleri ve şablon doldurma gibi kural tabanlı mantıksal sorgulardan yararlanan belirli görevler için çok uygundur .

Sözdizimi ve anlambilim

Prolog'da program mantığı ilişkiler cinsinden ifade edilir ve bu ilişkiler üzerinden bir sorgu çalıştırılarak bir hesaplama başlatılır . İlişkiler ve sorgular, Prolog'un tek veri türü olan terim kullanılarak oluşturulur . İlişkiler yan tümcelerle tanımlanır . Bir sorgu verildiğinde, Prolog motoru reddedilen sorgunun bir çözümleme reddini bulmaya çalışır . Olumsuzlanan sorgu reddedilebilirse, yani yan tümcelerin birleşimini ve olumsuzlanan sorgudan oluşan tekli kümeyi yanlış yapan tüm serbest değişkenler için bir örnekleme bulunursa, bulunan örnekleme uygulanmış orijinal sorgunun bir programın mantıksal sonucu . Bu, Prolog'u (ve diğer mantıksal programlama dillerini) özellikle veritabanı, sembolik matematik ve dil ayrıştırma uygulamaları için faydalı kılar . Prolog saf olmayan yüklemlere izin verdiği için , belirli özel yüklemlerin doğruluk değerini kontrol etmek, ekrana bir değer yazdırmak gibi kasıtlı yan etkilere sahip olabilir . Bu nedenle , mantıksal paradigma uygun olmadığında programcının bir miktar geleneksel zorunlu programlama kullanmasına izin verilir . "Saf Prolog" adı verilen tamamen mantıksal bir alt kümeye ve bir dizi ekstralojik özelliğe sahiptir.

Veri tipleri

Prolog bekar veri türü olan terim . Terimler atomlar , sayılar , değişkenler veya bileşik terimlerdir .

  • Bir atom , içsel bir anlamı olmayan genel amaçlı bir isimdir. Atom örnekleri arasında x, red, 'Taco', ve bulunur 'some atom'.
  • Sayılar olabilir yüzer veya tamsayılar . ISO standardıyla uyumlu Prolog sistemleri, "sınırlı" Prolog bayrağını kontrol edebilir. Başlıca Prolog sistemlerinin çoğu, isteğe bağlı uzunluktaki tamsayı sayılarını destekler.
  • Değişkenler , harf, sayı ve alt çizgi karakterlerinden oluşan ve büyük harf veya alt çizgi ile başlayan bir dize ile gösterilir. Değişkenler, keyfi terimler için yer tutucu oldukları için mantıktaki değişkenlere çok benzer.
  • Bir bileşik terimi, bir "funktoru" ve yeniden terimleri "bağımsız değişken", bir dizi olarak adlandırılan bir atom oluşmaktadır. Bileşik terimler genellikle bir işlev olarak yazılır, ardından parantez içinde yer alan virgülle ayrılmış bir argüman terimleri listesi gelir. Argümanların sayısına terimin aritesi denir . Bir atom, aritesi sıfır olan bir bileşik terim olarak kabul edilebilir . Bileşik terime bir örnek person_friends(zelda,[tom,jim]).

Bileşik terimlerin özel durumları:

  • Bir Liste terimden oluşan bir sıralı topluluğudur. Terimler virgülle ayrılmış köşeli parantezlerle veya boş liste olması durumunda ile gösterilir []. Örneğin, [1,2,3]veya [red,green,blue].
  • Dizeler : Tırnak içine alınmış bir karakter dizisi ya (sayısal) karakter kodlarının bir listesine, bir karakter listesine (1 uzunluğundaki atomlar) ya da Prolog bayrağının değerine bağlı olarak bir atoma eşdeğerdir double_quotes. Örneğin, "to be, or not to be".

ISO Prolog sağlar atom/1, number/1, integer/1, ve float/1için yüklemler'ıN tip denetimi .

Kurallar ve gerçekler

Prolog programları, cümleler aracılığıyla tanımlanan ilişkileri tanımlar. Pure Prolog, Horn cümleleri ile sınırlıdır . İki tür cümle vardır: gerçekler ve kurallar. şeklinde bir kuraldır

Head :- Body.

ve "Vücut doğruysa Baş doğrudur" şeklinde okunur. Bir kuralın gövdesi, kuralın hedefleri olarak adlandırılan, yüklem çağrılarından oluşur . Dahili mantıksal operatör ,/2 (bir Arity 2 anlamına operatör adıyla ,) temsil eder bağlaç gol ve ;/2belirtmektedir ayrılma . Bağlaçlar ve ayrılıklar, bir kuralın başında değil, yalnızca vücutta görünebilir.

Boş gövdeli tümcelere olgular denir . Bir gerçeğe bir örnek:

cat(crookshanks).

hangi kurala eşdeğerdir:

cat(crookshanks) :- true.

Yerleşik yüklem true/0her zaman doğrudur.

Yukarıdaki gerçek göz önüne alındığında, şu sorulabilir:

crookshanks bir kedi mi?

 ?- cat(crookshanks).
 Yes

kediler ne tür şeyler

 ?- cat(X).
 X = crookshanks

Gövdeli tümcelere kural denir . Bir kuralın bir örneği:

animal(X) :- cat(X).

Bu kuralı ekleyip hayvanlar nelerdir diye sorsak?

 ?- animal(X).
 X = crookshanks

Birçok yerleşik yüklemin ilişkisel doğası nedeniyle, genellikle birkaç yönde kullanılabilirler. Örneğin, length/2bir listenin uzunluğunu ( length(List, L), verilen bir liste List) belirlemenin yanı sıra belirli bir uzunlukta bir liste iskeleti ( length(X, 5)) oluşturmak ve ayrıca hem liste iskeletlerini hem de uzunluklarını birlikte oluşturmak ( length(X, L)) için kullanılabilir. Benzer şekilde, append/3hem iki listeyi ( append(ListA, ListB, X)verilen listeler ListAve ListB) eklemek hem de append(X, Y, List)verilen bir listeyi parçalara ( , verilen bir liste List) bölmek için kullanılabilir . Bu nedenle, nispeten küçük bir kitaplık kümesi, birçok Prolog programı için yeterlidir.

Genel amaçlı bir dil olarak, Prolog ayrıca giriş/çıkış , grafik kullanma ve işletim sistemiyle iletişim kurma gibi rutin faaliyetleri gerçekleştirmek için çeşitli yerleşik yüklemler sağlar. Bu yüklemlere ilişkisel bir anlam verilmez ve yalnızca sistem üzerinde sergiledikleri yan etkiler için faydalıdır. Örneğin, yüklem write/1ekranda bir terim görüntüler.

Uygulamak

Bir Prolog programının yürütülmesi, kullanıcının sorgu adı verilen tek bir hedefi göndermesiyle başlatılır. Mantıksal olarak, Prolog motoru reddedilen sorgunun bir çözümleme reddini bulmaya çalışır . Prolog tarafından kullanılan çözümleme yöntemine SLD çözünürlüğü denir . Reddedilen sorgu reddedilebilirse, uygun değişken bağlamaları yerinde olan sorgunun programın mantıksal bir sonucu olduğu sonucu çıkar. Bu durumda oluşturulan tüm değişken bağlamaları kullanıcıya bildirilir ve sorgunun başarılı olduğu söylenir. Operasyonel olarak, Prolog'un yürütme stratejisi, diğer dillerdeki işlev çağrılarının bir genellemesi olarak düşünülebilir, bir fark, birden çok yan tümce başlığının belirli bir çağrıyla eşleşebilmesidir. Bu durumda sistem bir seçim noktası oluşturur , hedefi birinci alternatifin cümle başı ile birleştirir ve o ilk alternatifin hedefleriyle devam eder. Programın yürütülmesi sırasında herhangi bir hedef başarısız olursa, en son seçim noktası oluşturulduktan sonra yapılan tüm değişken bağlamaları geri alınır ve yürütme, o seçim noktasının bir sonraki alternatifiyle devam eder. Bu yürütme stratejisine kronolojik geri izleme denir . Örneğin:

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).
 
parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

Bu, aşağıdaki sorgunun doğru olarak değerlendirilmesine neden olur:

 ?- sibling(sally, erica).
 Yes

Bu, şu şekilde elde edilir: Başlangıçta, sorgu için eşleşen tek yan tümce-kafası sibling(sally, erica)birincidir, bu nedenle sorguyu kanıtlamak, bu yan tümcenin gövdesini yerinde uygun değişken bağlamaları, yani bağlaç ile kanıtlamaya eşdeğerdir (parent_child(Z,sally), parent_child(Z,erica)). Kanıtlanacak bir sonraki hedef, bu bağlaçların en solundaki, yani parent_child(Z, sally). İki madde başı bu hedefle eşleşiyor. Sistem bir seçim noktası yaratır ve gövdesi olan ilk alternatifi dener father_child(Z, sally). Bu hedef, olgu kullanılarak kanıtlanabilir father_child(tom, sally), böylece bağlama Z = tomoluşturulur ve kanıtlanacak bir sonraki hedef, yukarıdaki birleşimin ikinci kısmıdır: parent_child(tom, erica). Yine, bu ilgili gerçekle kanıtlanabilir. Tüm hedefler kanıtlanabildiğinden, sorgu başarılı olur. Sorgu değişken içermediğinden, kullanıcıya hiçbir bağlama bildirilmez. Değişkenler içeren bir sorgu, örneğin:

?- father_child(Father, Child).

geri izleme ile ilgili tüm geçerli cevapları numaralandırır.

Yukarıda belirtilen kodla, sorgunun ?- sibling(sally, sally).da başarılı olduğuna dikkat edin . İstenirse, ilgili kısıtlamaları tanımlamak için ek hedefler eklenebilir.

Döngüler ve özyineleme

Yinelemeli algoritmalar, özyinelemeli yüklemler aracılığıyla uygulanabilir.

olumsuzlama

Yerleşik Prolog yüklemi \+/1, monoton olmayan akıl yürütmeye izin veren başarısızlık olarak olumsuzlama sağlar . Amaç kuralında \+ illegal(X)

legal(X) :- \+ illegal(X).

şu şekilde değerlendirilir: Prolog kanıtlamaya çalışır illegal(X). Bu amaç için bir kanıt bulunabilirse, asıl amaç (yani, \+ illegal(X)) başarısız olur. Kanıt bulunamazsa, asıl amaç başarılı olur. Bu nedenle, \+/1Önek operatörüne "kanıtlanamaz" operatörü denir, çünkü ?- \+ Goal.Hedef kanıtlanabilir değilse sorgu başarılı olur. Olumsuzlama Bu tür ses onun argümanı ise "zemin" (yani hiçbir değişkenleri içerir). Argüman değişkenler içeriyorsa ve ispat prosedürü tamamlandıysa sağlamlık kaybolur. Özellikle, sorgu ?- legal(X).artık yasal olan her şeyi sıralamak için kullanılamaz.

Prolog'da Programlama

Prolog'da yükleme koduna danışma denir . Prolog, Prolog isteminde sorgular girilerek etkileşimli olarak kullanılabilir ?-. Çözüm yoksa Prolog yazar no. Bir çözüm varsa, yazdırılır. Sorgunun birden fazla çözümü varsa, bunlar noktalı virgül girilerek talep edilebilir ;. Kod verimliliğini, okunabilirliği ve sürdürülebilirliği geliştirmek için iyi programlama uygulamalarına ilişkin yönergeler vardır.

Burada Prolog'da yazılmış bazı örnek programları izleyin.

Selam Dünya

Bir sorgu örneği:

?- write('Hello World!'), nl.
Hello World!
true.

?-

Derleyici optimizasyonu

Herhangi bir hesaplama, durum geçişlerinin bir dizisi olarak bildirimsel olarak ifade edilebilir. Örnek olarak, üç optimizasyon geçişli bir optimize edici derleyici , bir ilk program ile optimize edilmiş formu arasında bir ilişki olarak uygulanabilir:

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

veya eşdeğer olarak DCG gösterimini kullanarak :

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

Hızlı sıralama

Quicksort onun sıralı sürümüne listesini ilişkin, sıralama algoritması:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

Prolog'un tasarım desenleri

Bir tasarım modeli yaygın olarak ortaya çıkan bir sorun genel bir yeniden çözüm yazılım tasarımı . Prolog'daki bazı tasarım kalıpları, iskeletler, teknikler, klişeler, program şemaları, mantık açıklama şemaları ve yüksek dereceli programlamadır .

Üst düzey programlama

Daha yüksek dereceli bir yüklem, bir veya daha fazla başka yüklemi argüman olarak alan bir yüklemdir. Üst düzey programlama için destek yüklemler üzerinde kantifikasyonunu izin vermez Birinci derece mantık alanında, dış Prolog sürse de, ISO Prolog şimdi bazı yerleşik gibi yüksek dereceden yüklemler vardır call/1, call/2, call/3, findall/3, setof/3, ve bagof/3. Ayrıca, rastgele Prolog hedefleri çalışma zamanında oluşturulup değerlendirilebildiğinden, maplist/2belirli bir listenin her bir üyesine rastgele bir yüklem uygulayan ve sublist/3belirli bir yüklemi karşılayan öğeleri filtreleyen gibi daha yüksek dereceli yüklemler yazmak kolaydır. , ayrıca körleme için izin veriyor .

Çözümleri zamansal temsilden (geri izlemede cevap ikameleri) uzaysal temsile (terimler) dönüştürmek için Prolog, belirli bir sorgunun tüm cevap ikamelerini bir listede toplayan çeşitli tüm çözümler yüklemlerine sahiptir. Bu, liste anlama için kullanılabilir . Örneğin, mükemmel sayılar , uygun bölenlerinin toplamına eşittir:

 perfect(N) :-
     between(1, inf, N), U is N // 2,
     findall(D, (between(1,U,D), N mod D =:= 0), Ds),
     sumlist(Ds, N).

Bu, mükemmel sayıları saymak ve ayrıca bir sayının mükemmel olup olmadığını kontrol etmek için kullanılabilir.

Başka bir örnek olarak, yüklem , bir çift listedeki karşılık gelen tüm konumlara maplistbir yüklem uygular P:

maplist(_, [], []).
maplist(P, [X|Xs], [Y|Ys]) :-
   call(P, X, Y),
   maplist(P, Xs, Ys).

Ne zaman Pherkes için bir yüklem olduğu X, P(X,Y)birleştirir Ytek benzersiz bir değerle, maplist(P, Xs, Ys)uygulamasına eş değerdir haritası işlevi fonksiyonel programlama olarak Ys = map(Function, Xs).

Prolog'daki yüksek mertebeden programlama stili HiLog ve λProlog'da öncülük etmiştir .

Modüller

İçin büyük programlama , Prolog bir sağlar modül sistemi . Modül sistemi ISO tarafından standardize edilmiştir. Ancak, tüm Prolog derleyicileri modülleri desteklemez ve ana Prolog derleyicilerinin modül sistemleri arasında uyumluluk sorunları vardır. Sonuç olarak, bir Prolog derleyicisinde yazılan modüller mutlaka başkaları üzerinde çalışmayacaktır.

Ayrıştırma

Kesin yan tümce gramerleri (DCG'ler) adı verilen özel bir gösterim vardır . Bunun -->/2yerine aracılığıyla tanımlanan bir kural :-/2, önişlemci ( expand_term/2, diğer dillerdeki makrolara benzer bir tesis) tarafından birkaç basit yeniden yazma kuralına göre genişletilir ve sıradan Prolog yan tümceleri ile sonuçlanır. En önemlisi, yeniden yazma, yüklemi , diğer dillerdeki monadlara benzer şekilde, durumu dolaylı olarak sarmak için kullanılabilen iki ek argümanla donatır . DCG'ler genellikle ayrıştırıcılar veya liste oluşturucular yazmak için kullanılır, çünkü bunlar aynı zamanda fark listelerine uygun bir arabirim sağlar.

Meta-yorumlayıcılar ve yansıma

Prolog eşsesli bir dildir ve yansıma için birçok olanak sağlar . Örtük yürütme stratejisi, saf Prolog kodu için kısa bir meta-dairesel değerlendirici ( meta-yorumlayıcı olarak da adlandırılır ) yazmayı mümkün kılar :

solve(true).
solve((Subgoal1,Subgoal2)) :- 
    solve(Subgoal1),
    solve(Subgoal2).
solve(Head) :- 
    clause(Head, Body),
    solve(Body).

nerede trueboş bir bağlacı temsil eder clause(Head, Body)ve formun veritabanındaki yan tümcelerle birleştirir Head :- Body.

Prolog programlarının kendileri :-/2, yerleşik mekanizmalar ( gibi ) kullanılarak kolayca okunan ve denetlenen Prolog terimlerinin dizileri olduğundan ( bir infix operatörüdür ), read/1Prolog'u etki alanına özgü özelliklerle artıran özelleştirilmiş yorumlayıcılar yazmak mümkündür. Örneğin, Sterling ve Shapiro, belirsizlikle akıl yürütme gerçekleştiren, burada küçük değişikliklerle yeniden üretilen bir meta-yorumlayıcı sunar:

solve(true, 1) :- !.
solve((Subgoal1,Subgoal2), Certainty) :-
    !,
    solve(Subgoal1, Certainty1),
    solve(Subgoal2, Certainty2),
    Certainty is min(Certainty1, Certainty2).
solve(Goal, 1) :-
    builtin(Goal), !, 
    Goal.
solve(Head, Certainty) :-
    clause_cf(Head, Body, Certainty1),
    solve(Body, Certainty2),
    Certainty is Certainty1 * Certainty2.

Bu yorumlayıcı, formun yerleşik Prolog yüklemlerinin bir tablosunu kullanır.

builtin(A is B).
builtin(read(X)).
% etc.

ve cümleleri olarak temsil edilir clause_cf(Head, Body, Certainty). Bunlar göz önüne alındığında , sonuç hakkında bir kesinlik ölçüsü solve(Goal, Certainty)yürütmek Goalve elde etmek olarak adlandırılabilir .

Turing bütünlüğü

Saf Prolog birinci dereceden bir alt kümesine dayanan yüklem mantığı , Horn maddeleri ise, Turing-tam . Prolog'un Turing eksiksizliği, bir Turing makinesini simüle etmek için kullanılarak gösterilebilir:

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).
 
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).
 
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
 
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
 
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

Basit bir örnek Turing makinesi gerçeklerle belirtilmiştir:

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

Bu makine, tekli kodlamada bir sayıdan biriyle artış gerçekleştirir: Herhangi bir sayıda "1" hücre üzerinde döngü yapar ve sonuna ek bir "1" ekler. Örnek sorgu ve sonuç:

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

Bu, herhangi bir hesaplamanın, Prolog'da ardışık ilgi durumları arasında bir ilişki olarak uygulanan bir dizi durum geçişi olarak bildirimsel olarak nasıl ifade edilebileceğini gösterir.

uygulama

ISO Giriş

ISO Prolog standardı iki bölümden oluşmaktadır. 1995 yılında yayınlanan ISO/IEC 13211-1, Prolog'un temel unsurlarının birçok uygulamasının mevcut uygulamalarını standartlaştırmayı amaçlamaktadır. Dilin daha önce belirsiz olan ve taşınabilir programlara yol açan yönlerini netleştirdi. Üç düzeltme vardır: Cor.1:2007, Cor.2:2012 ve Cor.3:2017. 2000 yılında yayınlanan ISO/IEC 13211-2, standarda modüller için destek ekler. Standart tarafından korunur , ISO / IEC JTC1 / SC22 / WG17 çalışma grubu. ANSI X3J17, standart için ABD Teknik Danışma Grubu'dur.

Derleme

Verimlilik için, Prolog kodu tipik olarak, genellikle kayıt tabanlı Warren Özet Makinesi (WAM) komut setinden etkilenen soyut makine koduna derlenir . Bazı uygulamalar , derleme zamanında yüklemlerin tür ve mod bilgilerini türetmek veya yüksek performans için gerçek makine koduna derlemek için soyut yorumlama kullanır . Prolog kodu için verimli uygulama yöntemleri tasarlamak, mantık programlama topluluğunda aktif bir araştırma alanıdır ve bazı uygulamalarda çeşitli diğer yürütme yöntemleri kullanılır. Bunlar, yan tümce ikilileştirme ve yığın tabanlı sanal makineleri içerir .

Kuyruk özyineleme

Prolog sistemleri tipik olarak, kuyruk özyineleme veya daha genel olarak kuyruk çağrıları sergileyen deterministik yüklemler için kuyruk çağrısı optimizasyonu (TCO) adı verilen iyi bilinen bir optimizasyon yöntemini uygular : Bir kuyruk konumunda bir çağrı gerçekleştirilmeden önce bir yan tümcenin yığın çerçevesi atılır. Bu nedenle, deterministik kuyruk özyinelemeli yüklemler, diğer dillerdeki döngüler gibi sabit yığın alanıyla yürütülür.

terim indeksleme

Bir sorguda bir terimle birleştirilemeyen tümceleri bulmak, tümce sayısında doğrusaldır. Terim indeksleme , alt-doğrusal zaman aramalarını sağlayan bir veri yapısı kullanır . İndeksleme sadece program performansını etkiler, semantiği etkilemez. Çoğu Prolog, tüm terimlerde dizin oluşturma pahalı olduğundan, yalnızca ilk terimde dizin oluşturmayı kullanır, ancak alan kodlu sözcüklere veya üst üste bindirilmiş kod sözcüklerine dayalı teknikler , tam sorgu ve kafa genelinde hızlı dizin oluşturma sağlar.

Hashing

WIN-PROLOG ve SWI-Prolog gibi bazı Prolog sistemleri, artık büyük veri kümelerini daha verimli bir şekilde işlemeye yardımcı olmak için karma uygulamaktadır. Bu, WordNet gibi büyük şirketlerle çalışırken çok büyük performans kazanımları sağlama eğilimindedir .

Tablolama

Bazı Prolog sistemleri ( B-Prolog , XSB , SWI-Prolog , YAP ve Ciao ), bir uygulamaya memoization denilen yöntem tablolama elle orta sonuçları saklamak kullanıcının serbest bırakır. Tablolama bir uzay-zaman değiş tokuşudur ; ara sonuçları depolamak için daha fazla bellek kullanılarak yürütme süresi azaltılabilir:

Bir sorgu değerlendirmesinde karşılaşılan alt hedefler, bu alt hedeflere verilen yanıtlarla birlikte bir tabloda tutulur. Bir alt hedefle yeniden karşılaşılırsa, değerlendirme, program maddelerine göre yeniden çözümleme yapmak yerine tablodaki bilgileri yeniden kullanır.

Tablolama çeşitli yönlerde genişletilebilir. SLG çözünürlüğü veya doğrusal tablolama yoluyla özyinelemeli tahminleri destekleyebilir. Çok iş parçacıklı bir Prolog sisteminde tablolama sonuçları bir iş parçacığına özel tutulabilir veya tüm iş parçacıkları arasında paylaşılabilir. Ve artımlı tablolamada, tablolama değişikliklere tepki verebilir.

Donanımda uygulama

Sırasında Beşinci Nesil Bilgisayar Sistemleri projesi , özel mimarileri ile daha hızlı yürütülmesine ulaşmak amacıyla donanım Prolog uygulanması için girişimler oldu. Ayrıca, Prolog'un paralel yürütme yoluyla hızlanmaya izin verebilecek bir dizi özelliği vardır. Daha yeni bir yaklaşım, kısıtlı Prolog programlarını bir alan programlanabilir geçit dizisine derlemek olmuştur . Bununla birlikte, genel amaçlı donanımdaki hızlı ilerleme, sürekli olarak daha özel mimarileri geride bırakmıştır.

sınırlamalar

Prolog, araştırma ve eğitimde yaygın olarak kullanılmasına rağmen, Prolog ve diğer mantıksal programlama dilleri, genel olarak bilgisayar endüstrisi üzerinde önemli bir etkiye sahip olmamıştır. Çoğu uygulama, endüstriyel standartlara göre küçüktür ve birkaçı 100.000 kod satırını aşar. Büyük yılında Programlama tüm Prolog derleyicileri modüllerini destekleyen çünkü karmaşık olmak kabul edilir ve büyük Prolog derleyicilerinde modül sistemleri arasında uyum sorunları vardır edilir. Prolog kodunun uygulamalar arasında taşınabilirliği de bir sorun olmuştur, ancak 2007'den bu yana yaşanan gelişmeler şu anlama gelmektedir: "Edinburgh/Quintus'tan türetilen Prolog uygulamaları ailesi içindeki taşınabilirlik, taşınabilir gerçek dünya uygulamalarının sürdürülmesine izin verecek kadar iyidir."

Prolog'da geliştirilen yazılımlar, geleneksel programlama dillerine kıyasla yüksek performans cezasına sahip olduğu için eleştiriliyor. Özellikle, Prolog'un deterministik olmayan değerlendirme stratejisi, deterministik hesaplamaları programlarken veya hatta "belirleyici olmamayı umursama"yı kullanırken (tüm olasılıklar üzerinde geriye gitmek yerine tek bir seçimin yapıldığı durumlarda) sorunlu olabilir. Arzu edilen performansı elde etmek için kesmeler ve diğer dil yapılarının kullanılması gerekebilir, bu da Prolog'un ana cazibe merkezlerinden biri olan programları "ileri ve geri" çalıştırma yeteneğini yok eder.

Prolog salt bildirimsel değildir: cut operatörü gibi yapılar nedeniyle, onu anlamak için Prolog programının prosedürel bir okuması gerekir. Dilin yürütme stratejisi buna bağlı olduğundan, bir Prolog programında tümcelerin sırası önemlidir. Datalog gibi diğer mantıksal programlama dilleri gerçekten bildirimseldir ancak dili kısıtlar. Sonuç olarak, birçok pratik Prolog programı, tamamen bildirimsel mantık programları yerine Prolog'un derinlik öncelikli arama sırasına uyacak şekilde yazılmıştır .

Uzantılar

Mantıksal programlama yeteneklerini çeşitli yönlerde genişletmek için Prolog'dan çeşitli uygulamalar geliştirilmiştir. Bunlar, türleri , modları, kısıtlamalı mantık programlamayı (CLP), nesne yönelimli mantık programlamayı (OOLP), eşzamanlılık, doğrusal mantık (LLP), işlevsel ve üst düzey mantık programlama yeteneklerini ve ayrıca bilgi tabanlarıyla birlikte çalışabilirliği içerir :

Türler

Prolog, yazılmamış bir dildir. Türleri tanıtma girişimleri 1980'lere kadar uzanıyor ve 2008'den itibaren hala Prolog'u türlerle genişletme girişimleri var. Tip bilgisi sadece tip güvenliği için değil, aynı zamanda Prolog programları hakkında muhakeme yapmak için de faydalıdır .

Modlar

mod belirteci Tercüme
+ nonvar girişte
- var girişte
? Belirtilmemiş

Prolog'un sözdizimi, bir yüklemin hangi argümanlarının girdi, hangilerinin çıktı olduğunu belirtmez. Ancak bu bilgiler önemlidir ve yorumlarda yer alması tavsiye edilir. Modlar, Prolog programları hakkında akıl yürütürken değerli bilgiler sağlar ve yürütmeyi hızlandırmak için de kullanılabilir.

kısıtlamalar

Kısıtlama mantığı programlaması , Prolog'u kısıtlama tatmininden gelen kavramları içerecek şekilde genişletir . Bir kısıtlama mantığı programı, aşağıdakiler gibi maddeler gövdesinde kısıtlamalara izin verir: A(X,Y) :- X+Y>0. Büyük ölçekli kombinatoryal optimizasyon problemlerine uygundur ve bu nedenle otomatik zaman çizelgeleme ve üretim çizelgeleme gibi endüstriyel ortamlardaki uygulamalar için kullanışlıdır . Çoğu Prolog sistemi, sonlu alanlar için en az bir kısıt çözücü ve genellikle rasyonel sayılar gibi diğer alanlar için çözücülerle birlikte gönderilir.

nesne yönelimi

Flora-2 , F mantığına dayalı nesne yönelimli bir bilgi temsili ve akıl yürütme sistemidir ve HiLog , İşlem mantığı ve geçersiz muhakeme içerir .

Logtalk , çoğu Prolog uygulamasını arka uç derleyici olarak kullanabilen nesne yönelimli bir mantık programlama dilidir. Çok paradigmalı bir dil olarak hem prototipler hem de sınıflar için destek içerir.

Oblog , EdCAAD, Edinburgh Üniversitesi'nden Margaret McDougall tarafından Prolog'un küçük, taşınabilir, nesne yönelimli bir uzantısıdır.

Objlog , nesneleri ve CNRS, Marsilya, Fransa'dan Prolog II'yi birleştiren çerçeve tabanlı bir dildi .

Prolog++ , Logic Programming Associates tarafından geliştirildi ve ilk olarak 1989'da MS-DOS PC'ler için piyasaya sürüldü. Diğer platformlar için destek eklendi ve 1995'te ikinci bir sürüm yayınlandı. 1994'te Addison-Wesley tarafından Chris Moss'un Prolog++ hakkında bir kitabı yayınlandı.

Visual Prolog , arayüzler, sınıflar, uygulamalar ve nesne ifadeleri içeren çok paradigmalı bir dildir.

Grafikler

Bir temin Prolog sistemleri grafik kütüphanesi olan SWI-Prolog , Görsel Prolog , WIN-Prolog ve B-Prolog .

eşzamanlılık

Prolog-MPI , Mesaj Geçirme Arayüzü üzerinden dağıtılmış bilgi işlem için açık kaynaklı bir SWI-Prolog uzantısıdır . Ayrıca çeşitli eşzamanlı Prolog programlama dilleri vardır.

Web programlama

Bazı Prolog uygulamaları, özellikle Visual Prolog , SWI-Prolog ve Ciao , web protokolleri, HTML ve XML desteği ile sunucu tarafı web programlamayı destekler . RDF ve OWL gibi anlamsal web formatlarını destekleyen uzantılar da vardır . Prolog ayrıca istemci tarafı bir dil olarak önerilmiştir . Ayrıca Visual Prolog, JSON-RPC ve Websockets'i destekler .

Adobe Flash

Cedar , ücretsiz ve temel bir Prolog yorumlayıcısıdır. 4 ve üzeri sürümlerden Cedar, FCA (Flash Cedar App) desteğine sahiptir. Bu, ActionScript aracılığıyla Prolog'da programlama için yeni bir platform sağlar .

Başka

  • F-logic , Prolog'u bilgi gösterimi için çerçeveler/nesnelerle genişletir .
  • İşlem mantığı , Prolog'u durum değiştiren güncelleme operatörlerinin mantıksal bir teorisiyle genişletir. Hem model-teorik hem de prosedürel anlambilime sahiptir.
  • OW Prolog , Prolog'un grafik ve arayüz eksikliğine cevap vermek için oluşturulmuştur.

Diğer dillere arayüzler

Prolog ve diğer diller arasında köprü kurabilen çerçeveler mevcuttur:

  • LPA İstihbarat Sunucu gömülmesini verir LPA Windows için Prolog C dahilinde, C #, C ++, Java, VB, Delphi, Net, Lua, Python ve diğer diller. LPA Prolog'un sağladığı özel dizi veri türünden yararlanır.
  • Logic Server API, Prolog'un C, C++, Java, VB, Delphi, .NET ve bir .dll veya .so çağırabilen herhangi bir dilde/ortamda hem uzantısına hem de gömülmesine izin verir. Amzi için uygulanıyor! Giriş Amzi! Prolog + Logic Server, ancak API spesifikasyonu herhangi bir uygulama için kullanılabilir hale getirilebilir.
  • JPL , varsayılan olarak SWI-Prolog ile birlikte gelen, Java ve Prolog'un birbirini (yinelemeli olarak) aramasına izin veren çift yönlü bir Java Prolog köprüsüdür. İyi bir eşzamanlılık desteğine sahip olduğu biliniyor ve aktif olarak geliştiriliyor.
  • Java ve Prolog arasında bir programlama kitaplığı köprüsü olan InterProlog , her iki dil arasında çift yönlü yüklem/yöntem çağrısı uygular. Java nesneleri Prolog terimleriyle eşlenebilir ve bunun tersi de mümkündür. Prolog katmanında mantık işlemeyi bırakırken, Java'da GUI'lerin ve diğer işlevlerin geliştirilmesine izin verir . Destekler XSB desteği ile, SWI-Prolog ve YAP 2013 için planlanmış.
  • Prova , Java, aracı mesajlaşma ve tepki kuralları ile yerel sözdizimi entegrasyonu sağlar. Prova, kendisini ara katman yazılımı için kural tabanlı bir komut dosyası (RBS) sistemi olarak konumlandırıyor. Dil, zorunlu ve bildirimsel programlamayı birleştirmede yeni bir çığır açıyor .
  • PROL Java için gömülebilir bir Prolog motoru. Küçük bir IDE ve birkaç kitaplık içerir.
  • Java için GNU Prolog , bir Java kitaplığı (gnu.prolog) olarak ISO Prolog'un bir uygulamasıdır.
  • Ciao , C, C++, Java ve ilişkisel veritabanları için arayüzler sağlar.
  • C#-Prolog , (yönetilen) C# ile yazılmış bir Prolog yorumlayıcısıdır. C# programlarına kolayca entegre edilebilir. Özellikler: güvenilir ve oldukça hızlı yorumlayıcı, komut satırı arabirimi, Windows arabirimi, yerleşik DCG, XML yüklemleri, SQL yüklemleri, genişletilebilir. Özel amaçlı uzantılar eklemek için kullanılabilen bir ayrıştırıcı oluşturucu da dahil olmak üzere eksiksiz kaynak kodu mevcuttur.
  • PHP için bir Warren Özet Makinesi PHP 5.3'te bir Prolog derleyicisi ve yorumlayıcısı. Stephan Buettcher'ın Java'daki çalışmasından çevrilmiş Symfony2.1 çerçevesi içinde veya bağımsız olarak kullanılabilen bir kitaplık [burada stefan .buettcher .org /cs /wam /index .html ]
  • tuProlog , yüklem kitaplıklarını yükleyerek/boşaltarak statik veya dinamik olarak yapılandırılacak minimum bir çekirdek etrafında kasıtlı olarak tasarlanmış, dağıtılmış uygulamalar ve altyapılar için hafif bir Prolog sistemidir. tuProlog yerel olarak çoklu paradigma programlamayı destekler ve Prolog ile ana akım nesne yönelimli diller (yani tuProlog Java sürümü için Java) ve tuProlog için herhangi bir .NET tabanlı dil (C#, F#..) arasında temiz, sorunsuz bir entegrasyon modeli sağlar. NET sürümü.

Tarih

Prolog adı , Philippe Roussel tarafından programmation en logique ( Fransızca mantıkta programlama için ) için bir kısaltma olarak seçilmiştir . 1972'de Alain Colmerauer tarafından Philippe Roussel ile birlikte Robert Kowalski'nin Horn maddelerinin prosedürel yorumuna dayalı olarak oluşturuldu . Kısmen, bildirimsel bir bilgi temsil dili olarak mantığın kullanımını, 1960'ların sonlarında ve 1970'lerin başlarında Kuzey Amerika'da popüler olan bilginin prosedürel temsili ile uzlaştırma arzusuyla motive edildi. Robert Kowalski'ye göre , ilk Prolog sistemi 1972'de Colmerauer ve Phillipe Roussel tarafından geliştirildi. Prolog'un ilk uygulaması Gerard Battani ve Henri Meloni tarafından Fortran'da yazılmış bir tercümandı. David HD Warren bu yorumlayıcıyı Edinburgh'a götürdü ve orada, çoğu modern uygulamada kullanılan “Edinburgh Prolog” sözdizimini tanımlamaya gelen alternatif bir ön uç uyguladı. Warren ayrıca Prolog için ilk derleyiciyi uygulayarak Fernando Pereira ile işbirliği içinde etkili DEC-10 Prolog'u yarattı. Warren daha sonra, Warren Soyut Makinesini yaratmak için DEC-10 Prolog'un arkasındaki fikirleri genelleştirdi .

Avrupalı ​​AI araştırmacıları Prolog'u tercih ederken, Amerikalılar Lisp'i tercih etti ve bildirildiğine göre dillerin esası hakkında birçok milliyetçi tartışmaya neden oldu. Prolog'un modern gelişiminin çoğu , ilk işletim sistemi için Kernel Language adlı bir Prolog varyantı geliştiren Beşinci Nesil Bilgisayar Sistemleri projesinin (FGCS) ivmesinden geldi .

Pure Prolog, başlangıçta, şu şekildeki Horn cümleleriyle bir çözünürlük teoremi ispatlayıcısının kullanımıyla sınırlıydı :

H :- B1, ..., Bn.

Teorem-kanıtlayıcının uygulanması, bu tür maddeleri prosedürler olarak ele alır:

to show/solve H, show/solve B1 and ... and Bn.

Bununla birlikte, Pure Prolog kısa süre sonra, not(B i ) formunun olumsuz koşullarının karşılık gelen pozitif koşulları B i çözmeye çalışıp başarısız olarak gösterildiği başarısızlık olarak olumsuzlamayı içerecek şekilde genişletildi .

Orijinal ekip tarafından Prolog'un sonraki uzantıları, uygulamalara kısıtlama mantığı programlama yeteneklerini getirdi.

Endüstride kullanım

Prolog, Watson'da kullanılmıştır . Watson, IBM'in DeepQA yazılımını ve Apache UIMA (Yapılandırılmamış Bilgi Yönetimi Mimarisi) çerçevesini kullanır. Sistem Java, C++ ve Prolog dahil olmak üzere çeşitli dillerde yazılmıştır ve dağıtılmış bilgi işlem sağlamak için Apache Hadoop çerçevesini kullanan SUSE Linux Enterprise Server 11 işletim sisteminde çalışır . Prolog, doğal dil ayrıştırma ağaçları üzerinde kalıp eşleştirme için kullanılır . Geliştiriciler şunları söyledi: "Ayrıştırma ağaçları ve diğer açıklamalar (adlandırılmış varlık tanıma sonuçları gibi) üzerinde kalıp eşleştirme kurallarını uygun bir şekilde ifade edebileceğimiz bir dile ve bu kuralları çok verimli bir şekilde uygulayabilecek bir teknolojiye ihtiyacımız vardı. Prolog'u bulduk. sadeliği ve etkileyiciliği nedeniyle dil için ideal seçimdi." Prolog, AI odaklı Düşük Kodlu Geliştirme Platformu GeneXus'ta kullanılıyor . Açık kaynak grafik veritabanı TerminusDB prolog'da uygulanmaktadır. TerminusDB, bilgi grafiklerini işbirliği içinde oluşturmak ve düzenlemek için tasarlanmıştır .

Ayrıca bakınız

İlgili diller

  • Gödel dil kesinlikle yazılı uygulamasıdır eşzamanlı kısıtlama mantık programlama . SICStus Prolog üzerine inşa edilmiştir.
  • Önceden PDC Prolog ve Turbo Prolog olarak bilinen Visual Prolog , standart Prolog'dan çok farklı olan, Prolog'un güçlü bir şekilde yazılmış nesne yönelimli bir lehçesidir. Turbo Prolog olarak Borland tarafından pazarlandı, ancak şimdi orijinal olarak onu üreten Danimarkalı firma PDC (Prolog Geliştirme Merkezi) tarafından geliştirildi ve pazarlandı.
  • Datalog , Prolog'un bir alt kümesidir. Katmanlı olabilen ilişkilerle sınırlıdır ve bileşik terimlere izin vermez. Prolog'un aksine, Datalog Turing-complete değildir .
  • Mercury , bir mod ve determinizm sisteminin yanı sıra statik, polimorfik bir sistemle büyük ölçüde yazılım mühendisliğine yönelik Prolog'un bir dalıdır.
  • GraphTalk, ek nesne yönelimli özelliklere sahip Warren's Abstract Machine'in tescilli bir uygulamasıdır.
  • Bazı yönlerden Prolog, Planner'ın bir alt kümesidir . Planner'daki fikirler daha sonra Bilimsel Topluluk Metaforunda daha da geliştirildi .
  • AgentSpeak , çok aracılı sistemlerde ajan davranışını programlamak için Prolog'un bir çeşididir .
  • Erlang , hayata Prolog tabanlı bir uygulama ile başladı ve Prolog'un birleştirme tabanlı sözdiziminin çoğunu koruyor.
  • Pilog , Prolog'un semantiğine sahip olan, ancak Lisp'in sözdizimini kullanan PicoLisp'in üzerine inşa edilmiş bir bildirim dilidir .

Referanslar

daha fazla okuma