Funktionallogische Programmierung - Versionsgeschichte

Agathenon: /* Einleitung */ wikifiziert

2025-06-09T10:52:06Z

Einleitung: wikifiziert

← Nächstältere Version		Version vom 9. Juni 2025, 12:52 Uhr
Zeile 1:		Zeile 1:
	Die '''Funktionallogische Programmierung''' ist die Vereinigung des ~~funktionalen~~ mit dem logischen Paradigma in einer Programmiersprache. Dies schließt die meisten starken Konzepte der Paradigmen mit ein, dazu gehören Funktionen höherer Ordnung, nicht-deterministische Ausführung und Unifikation. Wegbereiter dieser Schöpfung war [[λProlog]]<ref>{{Literatur \|Autor=Gopalan Nadathur, D. Miller \|Hrsg=D. M. Gabbay, C. J. Hogger, J. A. Robinson \|Titel=Logic Programming \|Reihe=Handbook of Logic in Artificial Intelligence and Logic Programming \|BandReihe=5 \|Verlag=Oxford University Press \|Datum=1998 \|ISBN=0-19-853792-1 \|Kapitel=Higher-Order Logic Programming \|Seiten=499–590}}</ref> in den Neunzigern. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].		Die '''Funktionallogische Programmierung''' ist die Vereinigung des [[Funktionale Programmierung\|funktional]]en mit dem [[Logik\|logischen]] [[Paradigma]] in einer [[Programmiersprache]]. Dies schließt die meisten starken Konzepte der Paradigmen mit ein, dazu gehören Funktionen höherer Ordnung, nicht-deterministische Ausführung und Unifikation. Wegbereiter dieser Schöpfung war [[λProlog]]<ref>{{Literatur \|Autor=Gopalan Nadathur, D. Miller \|Hrsg=D. M. Gabbay, C. J. Hogger, J. A. Robinson \|Titel=Logic Programming \|Reihe=Handbook of Logic in Artificial Intelligence and Logic Programming \|BandReihe=5 \|Verlag=Oxford University Press \|Datum=1998 \|ISBN=0-19-853792-1 \|Kapitel=Higher-Order Logic Programming \|Seiten=499–590}}</ref> in den [[1990er\|Neunzigern-Jahren]]. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].

	== Grundlagen ==		== Grundlagen ==

Prüm: /* Einzelnachweise */

2024-04-15T04:19:34Z

Einzelnachweise

← Nächstältere Version		Version vom 15. April 2024, 06:19 Uhr
Zeile 107:		Zeile 107:

	[[Kategorie:Programmierparadigma]]		[[Kategorie:Programmierparadigma]]
	[[Kategorie:Programmiersprache als Thema]]

Phzh: Form, typo

2022-10-31T13:59:01Z

Form, typo

← Nächstältere Version		Version vom 31. Oktober 2022, 15:59 Uhr
Zeile 1:		Zeile 1:
	Die '''Funktionallogische Programmierung''' ist die Vereinigung des funktionalen mit dem logischen Paradigma in einer Programmiersprache. Dies schließt die meisten starken Konzepte der Paradigmen mit ein, dazu gehören Funktionen höherer Ordnung, nicht-deterministische Ausführung und Unifikation. Wegbereiter dieser Schöpfung war [[λProlog]]<ref>{{~~cite~~ ~~book~~		Die '''Funktionallogische Programmierung''' ist die Vereinigung des funktionalen mit dem logischen Paradigma in einer Programmiersprache. Dies schließt die meisten starken Konzepte der Paradigmen mit ein, dazu gehören Funktionen höherer Ordnung, nicht-deterministische Ausführung und Unifikation. Wegbereiter dieser Schöpfung war [[λProlog]]<ref>{{Literatur \|Autor=Gopalan Nadathur, D. Miller \|Hrsg=D. M. Gabbay, C. J. Hogger, J. A. Robinson \|Titel=Logic Programming \|Reihe=Handbook of Logic in Artificial Intelligence and Logic Programming \|BandReihe=5 \|Verlag=Oxford University Press \|Datum=1998 \|ISBN=0-19-853792-1 \|Kapitel=Higher-Order Logic Programming \|Seiten=499–590}}</ref> in den Neunzigern. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].
	\|first1=Gopalan
	\|last1=Nadathur
	\|first2=D.
	\|last2=Miller
	\|chapter=Higher-Order Logic Programming
	\|title=Logic Programming
	\|volume=5 \| isbn=0198537921
	\|series=Handbook of Logic in Artificial Intelligence and Logic Programming
	\|editor=D. M. Gabbay, C. J. Hogger, J. A. Robinson
	\|publisher=Oxford University Press
	\|year=1998
	\|pages=499–590}}</ref> in den Neunzigern. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].

	== Grundlagen ==		== Grundlagen ==
Zeile 17:		Zeile 5:

	=== Funktionale Programmierung ===		=== Funktionale Programmierung ===
	Ein funktionales Programm ist eine Ansammlung von Funktionen oder Regeln. Eine funktionale Berechnung besteht aus dem Ersetzen von Teilausdrücken durch (unter Berücksichtigung der Funktionsdefinition) gleichwertige Teilausdrücke, solange bis keine Ersetzungen bzw. Reduktionen mehr möglich sind und ein Ergebnis bestimmt oder eine [[Normalform]] erreicht wird. Einen Teilausdruck, der reduziert werden kann, wird auch als Redex (von {{~~EnS~~\|reducible expression\|Audio=\|IPA=\|de=reduzierbarer Ausdruck}}) bezeichnet. Für die nächsten Beispiele sei die Funktion <code>verdoppeln</code> definiert durch		Ein funktionales Programm ist eine Ansammlung von Funktionen oder Regeln. Eine funktionale Berechnung besteht aus dem Ersetzen von Teilausdrücken durch (unter Berücksichtigung der Funktionsdefinition) gleichwertige Teilausdrücke, solange bis keine Ersetzungen bzw. Reduktionen mehr möglich sind und ein Ergebnis bestimmt oder eine [[Normalform]] erreicht wird. Einen Teilausdruck, der reduziert werden kann, wird auch als Redex (von {{enS\|reducible expression\|Audio=\|IPA=\|de=reduzierbarer Ausdruck}}) bezeichnet. Für die nächsten Beispiele sei die Funktion <code>verdoppeln</code> definiert durch

	verdoppeln x <span style="color:green">'''='''</span> x <span style="color:darkgreen">'''+'''</span> x		verdoppeln x <span style="color:green">'''='''</span> x <span style="color:darkgreen">'''+'''</span> x
Zeile 29:		Zeile 17:
	verdoppeln (''1 <span style="color:darkgreen">'''+'''</span> 2'') → ''verdoppeln 3'' → ''3 <span style="color:darkgreen">'''+'''</span> 3'' → 6		verdoppeln (''1 <span style="color:darkgreen">'''+'''</span> 2'') → ''verdoppeln 3'' → ''3 <span style="color:darkgreen">'''+'''</span> 3'' → 6

	In diesem Fall führen beide Auswertungen zum gleichen Resultat. Diese Eigenschaft heißt [[Konfluenz (Informatik)\|Konfluenz]] und folgt aus der fundamentalen Eigenschaft reiner funktionaler Sprachen, der [[~~referenzielle~~ Transparenz\|referenziellen Transparenz]]: der zu bestimmende Wert eines Ausdrucks hängt nicht (z. B. aufgrund von Seiteneffekten) von der Reihenfolge oder dem Zeitpunkt der Auswertung ab. Daher sind Beweise leichter zu führen und die Programme leicht wartbar.		In diesem Fall führen beide Auswertungen zum gleichen Resultat. Diese Eigenschaft heißt [[Konfluenz (Informatik)\|Konfluenz]] und folgt aus der fundamentalen Eigenschaft reiner funktionaler Sprachen, der [[Referenzielle Transparenz\|referenziellen Transparenz]]: der zu bestimmende Wert eines Ausdrucks hängt nicht (z. B. aufgrund von Seiteneffekten) von der Reihenfolge oder dem Zeitpunkt der Auswertung ab. Daher sind Beweise leichter zu führen und die Programme leicht wartbar.

	=== Algebraische Datentypen ===		=== Algebraische Datentypen ===
Zeile 76:		Zeile 64:
	Das Einschränken ist insbesondere nützlich, da es ermöglicht, Funktionen wie Relationen zu handhaben; Werte können auf gewisse Art in beide Richtungen bestimmt werden. Unter anderem illustriert dies das vorhergehende Beispiel.		Das Einschränken ist insbesondere nützlich, da es ermöglicht, Funktionen wie Relationen zu handhaben; Werte können auf gewisse Art in beide Richtungen bestimmt werden. Unter anderem illustriert dies das vorhergehende Beispiel.

	Wie bereits angemerkt können Einschränkungen wie eine Reduktion des Auswertegraphs aufgefasst werden und es gibt häufig viele verschiedene Wege (Strategien) einen Graphen zu reduzieren. Antoy et al.<ref>{{~~cite~~ ~~journal~~		Wie bereits angemerkt können Einschränkungen wie eine Reduktion des Auswertegraphs aufgefasst werden und es gibt häufig viele verschiedene Wege (Strategien) einen Graphen zu reduzieren. Antoy et al.<ref>{{Literatur \|Autor=Sergio Antoy, Rachid Echahed and Michael Hanus \|Titel=A Needed Narrowing Strategy \|Sammelwerk=Journal of the ACM \|Band=47 \|Nummer=4 \|Verlag=ACM \|Datum=2007 \|ISSN=0004-5411 \|Seiten=776–822 \|Online=https://dl.acm.org/doi/10.1145/347476.347484 \|DOI=10.1145/347476.347484}}</ref> bewiesen in den Neunzigern, dass eine bestimmte Strategie, das ''needed narrowing,'' optimal ist mit möglichst wenigen Reduktionen eine Normalform zu erhalten. Needed narrowing ist eine Form von [[Lazy Evaluation\|Bedarfsauswertung]], im Gegensatz zur SLD-Auflösungsstrategie<!-- siehe [[:en:SLD resolution\|SLD resolution]] (engl. WP) --> von Prolog.
	\| author = Sergio Antoy, Rachid Echahed and Michael Hanus
	\| title = A Needed Narrowing Strategy
	\| journal = Journal of the ACM
	\| volume = 47
	\| issue = 4
	\| pages = 776–822
	\| publisher = ACM
	\| year = 2007
	\| url = https://dl.acm.org/doi/10.1145/347476.347484
	\| issn = 0004-5411
	\| doi = 10.1145/347476.347484
	}}</ref> bewiesen in den Neunzigern, dass eine bestimmte Strategie, das ''needed narrowing,'' optimal ist mit möglichst wenigen Reduktionen eine Normalform zu erhalten. Needed narrowing ist eine Form von [[Lazy Evaluation\|Bedarfsauswertung]], im Gegensatz zur SLD-Auflösungsstrategie<!-- siehe [[:en:SLD resolution\|SLD resolution]] (engl. WP) --> von Prolog.

	=== Funktionale Muster ===		=== Funktionale Muster ===
Zeile 97:		Zeile 73:
	last (ys <span style="color:darkgreen">++</span> <span style="color:maroon">[</span>e<span style="color:maroon">]</span>) <span style="color:green">'''='''</span> e		last (ys <span style="color:darkgreen">++</span> <span style="color:maroon">[</span>e<span style="color:maroon">]</span>) <span style="color:green">'''='''</span> e

	Rein funktionale Sprachen erlauben eine derartige Definition nicht, da das Muster auf der linken Seite eine definierte Funktion enthält (nämlich den Operator <code>++</code>), die nicht notwendig [[Injektivität\|injektiv]] ist; ein solches Muster heißt funktionales Muster.<ref> Sergio Antoy and Michael Hanus: Declarative Programming with Function Patterns, LOPSTR 2005 {{~~doi~~\|10.1007/11680093_2}}</ref> Funktionale Muster werden durch die Kombination der funktionalen und logischen Eigenschaften sowie der Unterstützung von einfachen Aufgabendefinitionen, die tiefe Mustervergleiche in hierarchische Strukturen erfordern. In diesem Beispiel ist <code>++</code> allgemein nicht injektiv, denn jede nicht-leere Liste kann mit <code>[] ++ l</code> als auch <code>l ++ []</code> erzeugt werden; jedoch können die freien Variablen hier nur auf eine mögliche Art gewählt werden, da sie Einschränkungen unterliegen.		Rein funktionale Sprachen erlauben eine derartige Definition nicht, da das Muster auf der linken Seite eine definierte Funktion enthält (nämlich den Operator <code>++</code>), die nicht notwendig [[Injektivität\|injektiv]] ist; ein solches Muster heißt funktionales Muster.<ref>Sergio Antoy and Michael Hanus: Declarative Programming with Function Patterns, LOPSTR 2005 {{DOI\|10.1007/11680093_2}}</ref> Funktionale Muster werden durch die Kombination der funktionalen und logischen Eigenschaften sowie der Unterstützung von einfachen Aufgabendefinitionen, die tiefe Mustervergleiche in hierarchische Strukturen erfordern. In diesem Beispiel ist <code>++</code> allgemein nicht injektiv, denn jede nicht-leere Liste kann mit <code>[] ++ l</code> als auch <code>l ++ []</code> erzeugt werden; jedoch können die freien Variablen hier nur auf eine mögliche Art gewählt werden, da sie Einschränkungen unterliegen.

	=== Nichtdeterminismus ===		=== Nichtdeterminismus ===
Zeile 106:		Zeile 82:
	x <span style="color:darkgreen">?</span> y <span style="color:green">'''='''</span> y		x <span style="color:darkgreen">?</span> y <span style="color:green">'''='''</span> y

	Daher gibt die Auswertung des Ausdrucks <code>0 ? 1</code> sowohl <code>0</code> als auch <code>1</code> zurück. Das Rechnen mit nichtdeterministischen Operationen und das Rechnen mit freien Variablen unter Einschränkungen hat die gleiche Ausdrucksstärke.<ref> Sergio Antoy and Michael Hanus: Overlapping Rules and Logic Variables in Functional Logic Programs, International Conference on Logic Programming 2006 {{~~doi~~\|10.1007/11799573_9}}</ref>		Daher gibt die Auswertung des Ausdrucks <code>0 ? 1</code> sowohl <code>0</code> als auch <code>1</code> zurück. Das Rechnen mit nichtdeterministischen Operationen und das Rechnen mit freien Variablen unter Einschränkungen hat die gleiche Ausdrucksstärke.<ref>Sergio Antoy and Michael Hanus: Overlapping Rules and Logic Variables in Functional Logic Programs, International Conference on Logic Programming 2006 {{DOI\|10.1007/11799573_9}}</ref>

	Die Regeln, mit denen <code>?</code> definiert wurde, zeigen ein wichtiges Merkmal funktionallogischer Sprachen: Alle Regeln werden versucht um eine bestimmte Operation auszuwerten; insbesondere wird nicht die oberste realisierbare Gleichung angewendet. Daher kann man mit		Die Regeln, mit denen <code>?</code> definiert wurde, zeigen ein wichtiges Merkmal funktionallogischer Sprachen: Alle Regeln werden versucht um eine bestimmte Operation auszuwerten; insbesondere wird nicht die oberste realisierbare Gleichung angewendet. Daher kann man mit
Zeile 123:		Zeile 99:

	definiert, die jede Permutation einer gegebenen Liste zurückgibt.		definiert, die jede Permutation einer gegebenen Liste zurückgibt.

	== Belege ==
⚫	<references/>

	== Weblinks ==		== Weblinks ==
	* [https://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel		* [https://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel

			== Einzelnachweise ==
		⚫	<references />

	[[Kategorie:Programmierparadigma]]		[[Kategorie:Programmierparadigma]]

DerMaxdorfer: Zeichensetzung, fehlendes Wort ergänzt

2021-08-24T15:07:53Z

Zeichensetzung, fehlendes Wort ergänzt

← Nächstältere Version		Version vom 24. August 2021, 17:07 Uhr
Zeile 32:		Zeile 32:

	=== Algebraische Datentypen ===		=== Algebraische Datentypen ===
	Ebenso wie funktionale Sprachen unterstützen viele funktionallogische Sprachen die Definition von algebraischen Typen indem ihre Konstruktoren aufgelistet werden. Beispielsweise wird der Datentyp <code>Bool</code> für Wahrheitswerte mit den Konstruktoren <code>True</code> und <code>False</code> wie folgt definiert:		Ebenso wie funktionale Sprachen unterstützen viele funktionallogische Sprachen die Definition von algebraischen Typen, indem ihre Konstruktoren aufgelistet werden. Beispielsweise wird der Datentyp <code>Bool</code> für Wahrheitswerte mit den Konstruktoren <code>True</code> und <code>False</code> wie folgt definiert:

	'''<span style="color:darkblue">data</span>''' <span style="color:purple">Bool</span> <span style="color:green">'''='''</span> <span style="color:maroon">True</span> <span style="color:green">'''\|'''</span> <span style="color:maroon">False</span>		'''<span style="color:darkblue">data</span>''' <span style="color:purple">Bool</span> <span style="color:green">'''='''</span> <span style="color:maroon">True</span> <span style="color:green">'''\|'''</span> <span style="color:maroon">False</span>
Zeile 61:		Zeile 61:
	Es sei zur Demonstration die Funktion <code>last</code> beschrieben, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.		Es sei zur Demonstration die Funktion <code>last</code> beschrieben, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.

	Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:		Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird, indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:

	last <span style="color:green">'''::'''</span> <span style="color:purple">[</span>a<span style="color:purple">]</span> <span style="color:green">'''->'''</span> a		last <span style="color:green">'''::'''</span> <span style="color:purple">[</span>a<span style="color:purple">]</span> <span style="color:green">'''->'''</span> a
Zeile 69:		Zeile 69:
	'''<span style="color:darkblue">where</span>''' ys, e '''<span style="color:darkblue">free</span>'''		'''<span style="color:darkblue">where</span>''' ys, e '''<span style="color:darkblue">free</span>'''

	Hier wird das Symbol <code>=:=</code> für Gleichheitsbedingungen benutzt, um sie syntaktisch von definierenden Gleichheiten und Vergleichen zu unterscheiden. Auf ähnliche Weise können zusätzliche Variablen gebunden indem sie explizit mit <code>where … free</code> deklariert werden. Die Deklaration ist notwendig und sinnvoll um Tippfehler zu vermeiden. Eine bedingte Gleichung der Form <code>L \| B  =  R</code> kann angewendet werden, falls die Bedingung <code>B</code> gelöst wurde. Im Gegensatz zu rein funktionalen Sprachen, deren Bedingungen ausschließlich Muster oder Ausdrücke vom Typ <code>Bool</code> sein können, unterstützen funktionallogische Sprachen außerdem das Lösen von Bedingungen durch das Erraten von Werten der Unbekannten in der Bedingung; Muster-Bedingungen sind ein Spezialfall davon. Einschränkungen, die im Folgenden erklärt werden, werden dafür herangezogen.		Hier wird das Symbol <code>=:=</code> für Gleichheitsbedingungen benutzt, um sie syntaktisch von definierenden Gleichheiten und Vergleichen zu unterscheiden. Auf ähnliche Weise können zusätzliche Variablen gebunden werden, indem sie explizit mit <code>where … free</code> deklariert werden. Die Deklaration ist notwendig und sinnvoll um Tippfehler zu vermeiden. Eine bedingte Gleichung der Form <code>L \| B  =  R</code> kann angewendet werden, falls die Bedingung <code>B</code> gelöst wurde. Im Gegensatz zu rein funktionalen Sprachen, deren Bedingungen ausschließlich Muster oder Ausdrücke vom Typ <code>Bool</code> sein können, unterstützen funktionallogische Sprachen außerdem das Lösen von Bedingungen durch das Erraten von Werten der Unbekannten in der Bedingung; Muster-Bedingungen sind ein Spezialfall davon. Einschränkungen, die im Folgenden erklärt werden, werden dafür herangezogen.

	=== Einschränkungen ===		=== Einschränkungen ===

Aka: https, Kleinkram

2021-01-21T18:54:04Z

https, Kleinkram

← Nächstältere Version		Version vom 21. Januar 2021, 20:54 Uhr
Zeile 41:		Zeile 41:
	not <span style="color:maroon">False</span> <span style="color:green">'''='''</span> <span style="color:maroon">True</span>		not <span style="color:maroon">False</span> <span style="color:green">'''='''</span> <span style="color:maroon">True</span>

	Das Vorgehen Ausdrücke durch gleichwertige zu ersetzen ist weiterhin gültig, wenn die Ausdrücke die entsprechende Form haben:		Das Vorgehen Ausdrücke durch gleichwertige zu ersetzen ist weiterhin gültig, wenn die Ausdrücke die entsprechende Form haben:

	not (''not <span style="color:maroon">False</span>'') → ''not <span style="color:maroon">True</span>'' → <span style="color:maroon">False</span>		not (''not <span style="color:maroon">False</span>'') → ''not <span style="color:maroon">True</span>'' → <span style="color:maroon">False</span>

	Kompliziertere Datenstrukturen werden durch rekursive Datentypen dargestellt. Beispielsweise eine Liste über einem beliebigen Typen, deren Elemente ebendiesen Typ haben, ist entweder die leere Liste <code>[]</code> oder eine nicht-leere Liste mit einem ersten Element <code>x</code> und einem Restglied <code>xs</code>, dargestellt durch <code>x : xs</code>.		Kompliziertere Datenstrukturen werden durch rekursive Datentypen dargestellt. Beispielsweise eine Liste über einem beliebigen Typen, deren Elemente ebendiesen Typ haben, ist entweder die leere Liste <code>[]</code> oder eine nicht-leere Liste mit einem ersten Element <code>x</code> und einem Restglied <code>xs</code>, dargestellt durch <code>x : xs</code>.

	'''<span style="color:darkblue">data</span>''' <span style="color:purple">List</span> a <span style="color:green">'''='''</span> <span style="color:maroon">[]</span> <span style="color:darkgreen">-- [] ist ein parameterloser Konstruktor (d. h. ein Literal), das die leere Liste darstellt.</span>		'''<span style="color:darkblue">data</span>''' <span style="color:purple">List</span> a <span style="color:green">'''='''</span> <span style="color:maroon">[]</span> <span style="color:darkgreen">-- [] ist ein parameterloser Konstruktor (d. h. ein Literal), das die leere Liste darstellt.</span>
Zeile 59:		Zeile 59:

	=== Logische Programmierung ===		=== Logische Programmierung ===
	Es sei zur Demonstration die Funktion <code>last</code> beschrieben, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.		Es sei zur Demonstration die Funktion <code>last</code> beschrieben, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.

	Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:		Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:
Zeile 85:		Zeile 85:
	\| publisher = ACM		\| publisher = ACM
	\| year = 2007		\| year = 2007
	\| url = ~~http~~://~~doi~~.acm.org/10.1145/347476.347484		\| url = https://dl.acm.org/doi/10.1145/347476.347484
	\| issn = 0004-5411		\| issn = 0004-5411
	\| doi = 10.1145/347476.347484		\| doi = 10.1145/347476.347484
Zeile 128:		Zeile 128:

	== Weblinks ==		== Weblinks ==
	* [~~http~~://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel		* [https://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel

	[[Kategorie:Programmierparadigma]]		[[Kategorie:Programmierparadigma]]

H3xc0d3r: /* Logische Programmierung */ fehlendes Verb eingefügt

2020-11-06T13:16:41Z

Logische Programmierung: fehlendes Verb eingefügt

← Nächstältere Version		Version vom 6. November 2020, 15:16 Uhr
Zeile 59:		Zeile 59:

	=== Logische Programmierung ===		=== Logische Programmierung ===
	Es sei zur Demonstration die Funktion <code>last</code>, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.		Es sei zur Demonstration die Funktion <code>last</code> beschrieben, die das letzte Element einer nicht-leeren Liste zurückgibt. Für alle Listen <code>xs</code> und Elemente <code>e</code> gilt: <code>last xs</code> ergibt <code>e</code> genau dann, wenn <code>ys ++ [e]</code> gleich <code>xs</code> für eine geeignete Liste <code>ys</code>.

	Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:		Basierend auf dieser Spezifikation können wir mittels logischer Programmiertechniken eine Funktion definieren, die diese erfüllt. Ähnlich wie logische Sprachen bieten funktionallogische Sprachen Lösungen für die Suche nach existentialquantifizierten Variablen. Im Gegensatz zu rein logischen Sprachen unterstützen sie das Lösen von Gleichungen mit funktionalen Teilausdrücken, sodass <code>ys ++ [e]  =  [1, 2, 3]</code> gelöst wird indem <code>ys</code> mit der Liste <code>[1, 2]</code> und <code>e</code> mit dem Wert <code>3</code> instantiiert wird. Dann kann <code>last</code> wie folgt definiert werden:

Aka: Tippfehler entfernt, Leerzeichen in Überschrift

2018-06-30T18:39:55Z

Tippfehler entfernt, Leerzeichen in Überschrift

← Nächstältere Version		Version vom 30. Juni 2018, 20:39 Uhr
Zeile 13:		Zeile 13:
	\|pages=499–590}}</ref> in den Neunzigern. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].		\|pages=499–590}}</ref> in den Neunzigern. Andere, neuere funktionallogische Programmiersprachen sind [[Curry (Programmiersprache)\|Curry]] und [[Mercury (Programmiersprache)\|Mercury]].

	==Grundlagen==		== Grundlagen ==
	Die Beispiele sind in der Syntax von [[Curry (Programmiersprache)\|Curry]].		Die Beispiele sind in der Syntax von [[Curry (Programmiersprache)\|Curry]].

	===Funktionale Programmierung===		=== Funktionale Programmierung ===
	Ein funktionales Programm ist eine Ansammlung von Funktionen oder Regeln. Eine funktionale Berechnung besteht aus dem Ersetzen von Teilausdrücken durch (unter Berücksichtigung der Funktionsdefinition) gleichwertige Teilausdrücke, solange bis keine Ersetzungen bzw. Reduktionen mehr möglich sind und ein Ergebnis bestimmt oder eine [[Normalform]] erreicht wird. Einen Teilausdruck, der reduziert werden kann, wird auch als Redex (von {{EnS\|reducible expression\|Audio=\|IPA=\|de=reduzierbarer ~~Ausruck~~}}) bezeichnet. Für die nächsten Beispiele sei die Funktion <code>verdoppeln</code> definiert durch		Ein funktionales Programm ist eine Ansammlung von Funktionen oder Regeln. Eine funktionale Berechnung besteht aus dem Ersetzen von Teilausdrücken durch (unter Berücksichtigung der Funktionsdefinition) gleichwertige Teilausdrücke, solange bis keine Ersetzungen bzw. Reduktionen mehr möglich sind und ein Ergebnis bestimmt oder eine [[Normalform]] erreicht wird. Einen Teilausdruck, der reduziert werden kann, wird auch als Redex (von {{EnS\|reducible expression\|Audio=\|IPA=\|de=reduzierbarer Ausdruck}}) bezeichnet. Für die nächsten Beispiele sei die Funktion <code>verdoppeln</code> definiert durch

	verdoppeln x <span style="color:green">'''='''</span> x <span style="color:darkgreen">'''+'''</span> x		verdoppeln x <span style="color:green">'''='''</span> x <span style="color:darkgreen">'''+'''</span> x
Zeile 71:		Zeile 71:
	Hier wird das Symbol <code>=:=</code> für Gleichheitsbedingungen benutzt, um sie syntaktisch von definierenden Gleichheiten und Vergleichen zu unterscheiden. Auf ähnliche Weise können zusätzliche Variablen gebunden indem sie explizit mit <code>where … free</code> deklariert werden. Die Deklaration ist notwendig und sinnvoll um Tippfehler zu vermeiden. Eine bedingte Gleichung der Form <code>L \| B  =  R</code> kann angewendet werden, falls die Bedingung <code>B</code> gelöst wurde. Im Gegensatz zu rein funktionalen Sprachen, deren Bedingungen ausschließlich Muster oder Ausdrücke vom Typ <code>Bool</code> sein können, unterstützen funktionallogische Sprachen außerdem das Lösen von Bedingungen durch das Erraten von Werten der Unbekannten in der Bedingung; Muster-Bedingungen sind ein Spezialfall davon. Einschränkungen, die im Folgenden erklärt werden, werden dafür herangezogen.		Hier wird das Symbol <code>=:=</code> für Gleichheitsbedingungen benutzt, um sie syntaktisch von definierenden Gleichheiten und Vergleichen zu unterscheiden. Auf ähnliche Weise können zusätzliche Variablen gebunden indem sie explizit mit <code>where … free</code> deklariert werden. Die Deklaration ist notwendig und sinnvoll um Tippfehler zu vermeiden. Eine bedingte Gleichung der Form <code>L \| B  =  R</code> kann angewendet werden, falls die Bedingung <code>B</code> gelöst wurde. Im Gegensatz zu rein funktionalen Sprachen, deren Bedingungen ausschließlich Muster oder Ausdrücke vom Typ <code>Bool</code> sein können, unterstützen funktionallogische Sprachen außerdem das Lösen von Bedingungen durch das Erraten von Werten der Unbekannten in der Bedingung; Muster-Bedingungen sind ein Spezialfall davon. Einschränkungen, die im Folgenden erklärt werden, werden dafür herangezogen.

	===Einschränkungen===		=== Einschränkungen ===
	Das Einschränken ist ein Mechanismus, bei dem eine Variable an einen Wert anhand von Alternativen, die von Einschränkungen auferlegt werden, gebunden wird. Alle möglichen Werte werden in einer bestimmten Reihenfolge ausprobiert, wobei der Rest des Programms aufgerufen wird, um die Korrektheit der Bindung zu überprüfen. Einschränkungen sind insofern eine Erweiterung des logischen Programmierens, dass sie eine ähnliche Suche ergeben, jedoch kann sie vielmehr Werte als Teil der Suche erzeugen als lediglich auf das Überprüfen beschränkt zu sein.		Das Einschränken ist ein Mechanismus, bei dem eine Variable an einen Wert anhand von Alternativen, die von Einschränkungen auferlegt werden, gebunden wird. Alle möglichen Werte werden in einer bestimmten Reihenfolge ausprobiert, wobei der Rest des Programms aufgerufen wird, um die Korrektheit der Bindung zu überprüfen. Einschränkungen sind insofern eine Erweiterung des logischen Programmierens, dass sie eine ähnliche Suche ergeben, jedoch kann sie vielmehr Werte als Teil der Suche erzeugen als lediglich auf das Überprüfen beschränkt zu sein.

Zeile 90:		Zeile 90:
	}}</ref> bewiesen in den Neunzigern, dass eine bestimmte Strategie, das ''needed narrowing,'' optimal ist mit möglichst wenigen Reduktionen eine Normalform zu erhalten. Needed narrowing ist eine Form von [[Lazy Evaluation\|Bedarfsauswertung]], im Gegensatz zur SLD-Auflösungsstrategie<!-- siehe [[:en:SLD resolution\|SLD resolution]] (engl. WP) --> von Prolog.		}}</ref> bewiesen in den Neunzigern, dass eine bestimmte Strategie, das ''needed narrowing,'' optimal ist mit möglichst wenigen Reduktionen eine Normalform zu erhalten. Needed narrowing ist eine Form von [[Lazy Evaluation\|Bedarfsauswertung]], im Gegensatz zur SLD-Auflösungsstrategie<!-- siehe [[:en:SLD resolution\|SLD resolution]] (engl. WP) --> von Prolog.

	===Funktionale Muster===		=== Funktionale Muster ===

	Die Regel, mit der oben die Funktion <code>last</code> definiert wurde, zeigt die Tatsache, dass das eigentliche Argument das Ergebnis des Ausdrucks <code>ys ++ [e]</code> treffen muss, wobei für <code>ys</code> und <code>e</code> beliebige Werte eingesetzt werden dürfen. Da auf einer Seite nur ein Parameter vorkommt, kann man das alternativ auch auf eine sehr prägnante Art ausdrücken:		Die Regel, mit der oben die Funktion <code>last</code> definiert wurde, zeigt die Tatsache, dass das eigentliche Argument das Ergebnis des Ausdrucks <code>ys ++ [e]</code> treffen muss, wobei für <code>ys</code> und <code>e</code> beliebige Werte eingesetzt werden dürfen. Da auf einer Seite nur ein Parameter vorkommt, kann man das alternativ auch auf eine sehr prägnante Art ausdrücken:
Zeile 99:		Zeile 99:
	Rein funktionale Sprachen erlauben eine derartige Definition nicht, da das Muster auf der linken Seite eine definierte Funktion enthält (nämlich den Operator <code>++</code>), die nicht notwendig [[Injektivität\|injektiv]] ist; ein solches Muster heißt funktionales Muster.<ref> Sergio Antoy and Michael Hanus: Declarative Programming with Function Patterns, LOPSTR 2005 {{doi\|10.1007/11680093_2}}</ref> Funktionale Muster werden durch die Kombination der funktionalen und logischen Eigenschaften sowie der Unterstützung von einfachen Aufgabendefinitionen, die tiefe Mustervergleiche in hierarchische Strukturen erfordern. In diesem Beispiel ist <code>++</code> allgemein nicht injektiv, denn jede nicht-leere Liste kann mit <code>[] ++ l</code> als auch <code>l ++ []</code> erzeugt werden; jedoch können die freien Variablen hier nur auf eine mögliche Art gewählt werden, da sie Einschränkungen unterliegen.		Rein funktionale Sprachen erlauben eine derartige Definition nicht, da das Muster auf der linken Seite eine definierte Funktion enthält (nämlich den Operator <code>++</code>), die nicht notwendig [[Injektivität\|injektiv]] ist; ein solches Muster heißt funktionales Muster.<ref> Sergio Antoy and Michael Hanus: Declarative Programming with Function Patterns, LOPSTR 2005 {{doi\|10.1007/11680093_2}}</ref> Funktionale Muster werden durch die Kombination der funktionalen und logischen Eigenschaften sowie der Unterstützung von einfachen Aufgabendefinitionen, die tiefe Mustervergleiche in hierarchische Strukturen erfordern. In diesem Beispiel ist <code>++</code> allgemein nicht injektiv, denn jede nicht-leere Liste kann mit <code>[] ++ l</code> als auch <code>l ++ []</code> erzeugt werden; jedoch können die freien Variablen hier nur auf eine mögliche Art gewählt werden, da sie Einschränkungen unterliegen.

	===Nichtdeterminismus===		=== Nichtdeterminismus ===
	Da funktionallogische Sprachen in der Lage sind, Funktionsaufrufe mit unbekannten Parametern enthaltende Gleichungen zu lösen, baut das Ausführungssystem auf [[Determinismus (Algorithmus)\|nichtdeterministischen]] Berechnungen auf. Dieser Mechanismus ermöglicht auch die Definition von nicht-deterministischen Operationen, die mehrere verschiedene Ergebnisse zu einer gegebenen Eingabe liefern. Die Mutter der nichtdeterministischen Operationen ist der vordefinierte Infix-Operator <code>?</code>, der Auswahl-Operator, der nichtdeterministisch einen seiner Operanden zurückliefert.		Da funktionallogische Sprachen in der Lage sind, Funktionsaufrufe mit unbekannten Parametern enthaltende Gleichungen zu lösen, baut das Ausführungssystem auf [[Determinismus (Algorithmus)\|nichtdeterministischen]] Berechnungen auf. Dieser Mechanismus ermöglicht auch die Definition von nicht-deterministischen Operationen, die mehrere verschiedene Ergebnisse zu einer gegebenen Eingabe liefern. Die Mutter der nichtdeterministischen Operationen ist der vordefinierte Infix-Operator <code>?</code>, der Auswahl-Operator, der nichtdeterministisch einen seiner Operanden zurückliefert.

Zeile 124:		Zeile 124:
	definiert, die jede Permutation einer gegebenen Liste zurückgibt.		definiert, die jede Permutation einer gegebenen Liste zurückgibt.

	==Belege==		== Belege ==
	<references/>		<references/>

	==Weblinks==		== Weblinks ==
	* [http://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel		* [http://www.informatik.uni-kiel.de/~mh/FLP/ Functional logic programming] an der Universität Kiel

DerSpezialist: /* Grundlagen */ Stilistisch überarbeitet

2018-06-30T15:42:52Z

Grundlagen: Stilistisch überarbeitet

Änderungen zeigen

Mabschaaf: Parameter-Fix

2018-06-30T09:22:18Z

Parameter-Fix

← Nächstältere Version		Version vom 30. Juni 2018, 11:22 Uhr
Zeile 8:		Zeile 8:
	\|volume=5 \| isbn=0198537921		\|volume=5 \| isbn=0198537921
	\|series=Handbook of Logic in Artificial Intelligence and Logic Programming		\|series=Handbook of Logic in Artificial Intelligence and Logic Programming
			\|editor=D. M. Gabbay, C. J. Hogger, J. A. Robinson
	\|editor1-first=D. M.
	\|editor1-last=Gabbay
	\|editor1-link=Dov Gabbay
	\|editor2-first=C. J.
	\|editor2-last=Hogger
	\|editor3-first=J. A.
	\|editor3-last=Robinson
	\|editor3-link=John Alan Robinson
	\|publisher=Oxford University Press		\|publisher=Oxford University Press
	\|year=1998		\|year=1998

DerSpezialist: /* Einfache Konzepte */ Typographie

2018-04-24T14:18:16Z

Einfache Konzepte: Typographie

← Nächstältere Version		Version vom 24. April 2018, 16:18 Uhr
Zeile 51:		Zeile 51:
	Kompliziertere Datenstrukturen werden durch rekursive Datentypen dargestellt. Beispielsweise eine Liste über einem beliebigen Typen, deren Elemente ebendiesen Typ haben, ist entweder die leere Liste <code>[]</code> oder eine nicht-leere Liste mit einem ersten Element <code>x</code> und einem Restglied <code>xs</code>, dargestellt durch <code>x : xs</code>.		Kompliziertere Datenstrukturen werden durch rekursive Datentypen dargestellt. Beispielsweise eine Liste über einem beliebigen Typen, deren Elemente ebendiesen Typ haben, ist entweder die leere Liste <code>[]</code> oder eine nicht-leere Liste mit einem ersten Element <code>x</code> und einem Restglied <code>xs</code>, dargestellt durch <code>x : xs</code>.

	'''<span style="color:darkblue">data</span>''' <span style="color:purple">List</span> a <span style="color:green">'''='''</span> <span style="color:maroon">[]</span> <span style="color:darkgreen">-- [] ist ein parameterloser Konstruktor (d. h. ein Literal), das die leere Liste darstellt.</span>		'''<span style="color:darkblue">data</span>''' <span style="color:purple">List</span> a <span style="color:green">'''='''</span> <span style="color:maroon">[]</span> <span style="color:darkgreen">-- [] ist ein parameterloser Konstruktor (d. h. ein Literal), das die leere Liste darstellt.</span>
	<span style="color:green">'''\|'''</span> a <span style="color:maroon">''':'''</span> <span style="color:purple">List</span> a <span style="color:darkgreen">-- Der Konstruktor wird infix notiert und ist der Doppelpunkt.</span>		<span style="color:green">'''\|'''</span> a <span style="color:maroon">''':'''</span> <span style="color:purple">List</span> a <span style="color:darkgreen">-- Der Konstruktor wird infix notiert und ist der Doppelpunkt.</span>
	<span style="color:darkgreen">-- Er hat zwei Parameter: ein Listenelement und ein Restglied, welches auch leer sein darf.</span>		<span style="color:darkgreen">-- Er hat zwei Parameter: ein Listenelement und ein Restglied, welches auch leer sein darf.</span>