{ "cells": [ { "cell_type": "markdown", "id": "7359298e-63ac-4080-9139-aa90c8043b2a", "metadata": {}, "source": [ "# A more systematic introduction to Prolog" ] }, { "cell_type": "markdown", "id": "49fd5211", "metadata": {}, "source": [ "### Propositions\n", "Prolog programs consist of <b>clauses</b>.\n", "A clause is always terminated by a dot (```.```).\n", "Propositions start with a lower case letter or you can use quotes to use (almost) arbitrary strings as propositions.\n", "The simplest clauses are facts. Here we define three propositions to be true, for the last two we use quotes:" ] }, { "cell_type": "code", "execution_count": 13, "id": "93e05f7b-a91c-4262-861e-a399e094b710", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "rains.\n", "'I am not wearing a hat'.\n", "'The sun is shining'.\n", "beach :- fail." ] }, { "cell_type": "markdown", "id": "b05ae74b", "metadata": {}, "source": [ "We can now ask the Prolog system whether the sun is shining:" ] }, { "cell_type": "code", "execution_count": null, "id": "14013336", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1;31mfalse" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- beach." ] }, { "cell_type": "code", "execution_count": 15, "id": "20b05b2c", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-'The sun is shining'." ] }, { "cell_type": "markdown", "id": "50c188fa", "metadata": {}, "source": [ "More complicated clauses make use of the implication operator ```:-```. They are also called rules. Logically they stipulate that the left-hand side of the clause must be true if the right-hand side is true. The right-hand side can contain multiple propositions separated by commas. The comma can be read as a logical conjunction (and)." ] }, { "cell_type": "code", "execution_count": 16, "id": "2b8b84a0", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "carry_umbrella :- rains, 'I am not wearing a hat'.\n", "rainbow :- rains, 'The sun is shining'." ] }, { "cell_type": "code", "execution_count": 17, "id": "4e6314e8", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- rainbow." ] }, { "cell_type": "markdown", "id": "161b0f75", "metadata": {}, "source": [ "The corresponding logic formula to the rule for `rainbow` is \n", "`rainbow ← rains ∧ 'The sun is shining'`" ] }, { "cell_type": "markdown", "id": "7eeb709b", "metadata": {}, "source": [ "Using propositional logic is limited, but we can for example encode the logic circuit example from the lecture as follows. Note that ```\\+``` is the Prolog symbol for negation." ] }, { "cell_type": "code", "execution_count": 18, "id": "46e4fea5", "metadata": {}, "outputs": [], "source": [ ":- dynamic a/0,b/0,c/0,d/0,e/0.\n", "a. c. e.\n", "% first-level circuits\n", "\n", "and11 :- a,b.\n", "or11 :- b,c.\n", "and12 :- c,d.\n", "not1 :- \\+ e.\n", "\n", "% second-level circuits\n", "or21 :- and11.\n", "or21 :- not1.\n", "\n", "and2 :- or11, not1.\n", "\n", "or22 :- and12.\n", "or22 :- not1.\n", "\n", "not2 :- \\+ not1.\n", "\n", "% third-level circuits\n", "and3 :- or21, and2.\n", "\n", "or3 :- or22.\n", "or3 :- not2.\n", "\n", "% fourth-level circuits\n", "or4 :- and3.\n", "or4 :- or3.\n", "\n", "and4 :- or3, not2.\n", "\n", "% last level\n", "and5 :- and4, or4.\n", "\n", "output :- and5." ] }, { "cell_type": "code", "execution_count": 19, "id": "e137f152", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-output." ] }, { "cell_type": "markdown", "id": "349b3e69", "metadata": {}, "source": [ "Still, propositional logic is much too limited for most applications. Hence we move to predicate logic." ] }, { "cell_type": "markdown", "id": "d7254b1b", "metadata": {}, "source": [ "### Predicates\n", "Instead of propositions we can also use predicates with arguments within our clauses. The arguments to predicates denote objects for which the predicate is true. Arguments which start with an upper-case letter are logical variables. Below ```X``` is such a variable and it can stand for any object." ] }, { "cell_type": "markdown", "id": "5f5810f7", "metadata": {}, "source": [ "Prolog provides a few built-in predicates like `>` or `=` or `is`." ] }, { "cell_type": "code", "execution_count": null, "id": "c646de97", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1;31mfalse" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- 2>3." ] }, { "cell_type": "code", "execution_count": 21, "id": "600c0ea6", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- is(X,3+2)." ] }, { "cell_type": "markdown", "id": "0686241a", "metadata": {}, "source": [ "Let us now define our own predicates.\n", "In this case `mother/2` and `grandma/2`.\n", "Note: we often use the notation `p/n` to denote the fact that the predicate `p` takes `n` arguments. `n` is called the arity of `p`." ] }, { "cell_type": "code", "execution_count": 22, "id": "1d6eed4f", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "mother(a,b).\n", "mother(b,c).\n", "grandma(a,c) :- mother(a,b),mother(b,c)." ] }, { "cell_type": "markdown", "id": "e645f31e", "metadata": {}, "source": [ "You can now ask questions about logical consequences of your logic program. In simple queries you provide all arguments:" ] }, { "cell_type": "code", "execution_count": 23, "id": "a2ab9e95", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-grandma(a,c)." ] }, { "cell_type": "code", "execution_count": 24, "id": "838bc91a", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- grandma(a,c) ; mother(c,d)." ] }, { "cell_type": "markdown", "id": "c8d0600e", "metadata": {}, "source": [ "## Logical variables\n", "Variables start with an upper-case letter or an underscore.\n", "Variables are called `logical variables` in Prolog: once assigned, their value is immutable and cannot be changed (except upon backtracking)." ] }, { "cell_type": "code", "execution_count": 25, "id": "93e47505", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X=1." ] }, { "cell_type": "markdown", "id": "d82e2815", "metadata": {}, "source": [ "Above we have set the logical variable `X` to 1. The scope of the name `X` is a Prolog clause (i.e., a fact or rule or a query). Thus, in the query below we talk about another `X`:" ] }, { "cell_type": "code", "execution_count": 26, "id": "0c4d96e2", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X=2." ] }, { "cell_type": "markdown", "id": "3a3b14b8", "metadata": {}, "source": [ "However, in the same scope we cannot change the value of `X`, once assigned:" ] }, { "cell_type": "code", "execution_count": null, "id": "47e57f93", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1;31mfalse" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X=1, X=2." ] }, { "cell_type": "code", "execution_count": 28, "id": "d9369af3", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 1,\n", "X2 = 2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X=1, X2 is X+1." ] }, { "cell_type": "markdown", "id": "fdbee9bb", "metadata": {}, "source": [ "Within a clause variables are implicitly unversally quantified.\n", "Let us now define the grandma predicate in a more general fashion:" ] }, { "cell_type": "code", "execution_count": 29, "id": "7fd70461", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "grandma(X,Y) :- mother(X,Z), mother(Z,Y)." ] }, { "cell_type": "markdown", "id": "51f5f6a4", "metadata": {}, "source": [ "The above clause is equivalent to this logical formula:\n", "\n", "`∀ X,Y,Z . grandma(X,Y) ← mother(X,Z)∧ mother(Z,Y)`\n", "\n", "Let us query the predicate:" ] }, { "cell_type": "code", "execution_count": 30, "id": "81724623", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = c" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- grandma(a,X)." ] }, { "cell_type": "markdown", "id": "3dce4ccd", "metadata": {}, "source": [ "When we have variables in a query, Prolog gives us solutions for variables such that the instantiated predicate calls are logical consequences of your program.\n", "\n", "We can find all solutions using the `print_table` command of our Jupyter kernel:" ] }, { "cell_type": "code", "execution_count": 31, "id": "4d656338", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/markdown": [ "X | \n", ":- | \n", "c | " ], "text/plain": [ "X | \n", ":- | \n", "c | " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_table(grandma(a,X))" ] }, { "cell_type": "markdown", "id": "d90546b0", "metadata": {}, "source": [ "Prolog also has a built-in predicate called ```findall``` which can be used to find all solutions in one go:" ] }, { "cell_type": "code", "execution_count": 32, "id": "a7478245", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mResults = [c]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-findall(X,grandma(a,X),Results)." ] }, { "cell_type": "markdown", "id": "74c96ce2", "metadata": {}, "source": [ "### Prolog terms and substitutions\n", "\n", "Terms represent data values (aka objects). We have that\n", "- constants like `a` and `b` are terms\n", "- variables like `X` are terms\n", "- terms can also be constructed using function symbols\n", "\n", "A predicate call takes terms as arguments.\n", "E.g. for `grandma(a,X)` we have the term `a` as first argument and the term `X` as second argument." ] }, { "cell_type": "markdown", "id": "fd8a78b7", "metadata": {}, "source": [ "## Exercise\n", "Let us try exercise 2.1.1 (iii) from the Art of Prolog (https://mitpress.mit.edu/9780262691635/the-art-of-prolog/), describing the layout of Figure 2.3 using `left_of/2` and `above/2`.\n", "" ] }, { "cell_type": "code", "execution_count": 33, "id": "9e3be61b", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "left_of(bicycle,camera).\n", "left_of(pencil,hourglass).\n", "left_of(hourglass,butterfly).\n", "left_of(butterfly,fish).\n", "\n", "above(bicycle,pencil).\n", "above(camera,butterfly)." ] }, { "cell_type": "markdown", "id": "db2baf14", "metadata": {}, "source": [ "We can use the Jupyter notebook to render the graph.\n", "The `print_transition_graph` predicate requires a ternary predicate,\n", "so that we can provide the edge labels:" ] }, { "cell_type": "code", "execution_count": 34, "id": "6781d789", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "edge(A,above,B) :- above(A,B).\n", "edge(A,left_of,B) :- left_of(A,B)." ] }, { "cell_type": "code", "execution_count": 35, "id": "bb98ad05", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mA = bicycle,\n", "B = above,\n", "C = pencil" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- edge(A,B,C)." ] }, { "cell_type": "markdown", "id": "74b3c8d1", "metadata": {}, "source": [ "By calling jupyter:print_transition_graph(PredSpec, FromIdx, ToIdx, LabelIdx),\n", "a transition graph can be created (FromIdx is the number of argument specifying the origin, ToIdx the destination and LabelIdx the label)." ] }, { "cell_type": "code", "execution_count": 36, "id": "186fe078", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "image/svg+xml": [ "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n", " -->\n", "<!-- Pages: 1 -->\n", "<svg width=\"173pt\" height=\"418pt\"\n", " viewBox=\"0.00 0.00 173.28 417.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 413.5)\">\n", "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-413.5 169.28,-413.5 169.28,4 -4,4\"/>\n", "<!-- bicycle -->\n", "<g id=\"node1\" class=\"node\">\n", "<title>bicycle</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"89.23\" cy=\"-391.5\" rx=\"37.53\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"89.23\" y=\"-386.45\" font-family=\"Times,serif\" font-size=\"14.00\">bicycle</text>\n", "</g>\n", "<!-- pencil -->\n", "<g id=\"node2\" class=\"node\">\n", "<title>pencil</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"56.23\" cy=\"-303\" rx=\"33.44\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"56.23\" y=\"-297.95\" font-family=\"Times,serif\" font-size=\"14.00\">pencil</text>\n", "</g>\n", "<!-- bicycle->pencil -->\n", "<g id=\"edge1\" class=\"edge\">\n", "<title>bicycle->pencil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M77.71,-373.99C74.18,-368.33 70.55,-361.82 67.98,-355.5 65.01,-348.16 62.71,-339.92 60.96,-332.21\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"64.43,-331.71 59.02,-322.6 57.57,-333.1 64.43,-331.71\"/>\n", "<text text-anchor=\"middle\" x=\"83.36\" y=\"-342.2\" font-family=\"Times,serif\" font-size=\"14.00\">above</text>\n", "</g>\n", "<!-- camera -->\n", "<g id=\"node3\" class=\"node\">\n", "<title>camera</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"127.23\" cy=\"-249\" rx=\"38.04\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"127.23\" y=\"-243.95\" font-family=\"Times,serif\" font-size=\"14.00\">camera</text>\n", "</g>\n", "<!-- bicycle->camera -->\n", "<g id=\"edge3\" class=\"edge\">\n", "<title>bicycle->camera</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M94.79,-373.47C96.59,-367.77 98.56,-361.38 100.23,-355.5 107.63,-329.54 115.17,-299.72 120.4,-278.42\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"123.8,-279.27 122.76,-268.72 117,-277.61 123.8,-279.27\"/>\n", "<text text-anchor=\"middle\" x=\"122.23\" y=\"-342.2\" font-family=\"Times,serif\" font-size=\"14.00\">left_of</text>\n", "</g>\n", "<!-- hourglass -->\n", "<g id=\"node5\" class=\"node\">\n", "<title>hourglass</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"46.23\" cy=\"-195\" rx=\"46.23\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"46.23\" y=\"-189.95\" font-family=\"Times,serif\" font-size=\"14.00\">hourglass</text>\n", "</g>\n", "<!-- pencil->hourglass -->\n", "<g id=\"edge4\" class=\"edge\">\n", "<title>pencil->hourglass</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M49.22,-285.2C47.19,-279.53 45.25,-273.08 44.23,-267 41.92,-253.12 42.07,-237.52 42.94,-224.48\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"46.4,-225.11 43.76,-214.85 39.42,-224.52 46.4,-225.11\"/>\n", "<text text-anchor=\"middle\" x=\"62.23\" y=\"-243.95\" font-family=\"Times,serif\" font-size=\"14.00\">left_of</text>\n", "</g>\n", "<!-- butterfly -->\n", "<g id=\"node4\" class=\"node\">\n", "<title>butterfly</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"87.23\" cy=\"-106.5\" rx=\"42.65\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"87.23\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">butterfly</text>\n", "</g>\n", "<!-- camera->butterfly -->\n", "<g id=\"edge2\" class=\"edge\">\n", "<title>camera->butterfly</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M126.66,-230.61C125.45,-209.21 121.72,-172.07 110.23,-142.5 109.05,-139.45 107.57,-136.39 105.94,-133.42\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"109.02,-131.76 100.79,-125.09 103.07,-135.44 109.02,-131.76\"/>\n", "<text text-anchor=\"middle\" x=\"140.36\" y=\"-189.95\" font-family=\"Times,serif\" font-size=\"14.00\">above</text>\n", "</g>\n", "<!-- fish -->\n", "<g id=\"node6\" class=\"node\">\n", "<title>fish</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"87.23\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"87.23\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">fish</text>\n", "</g>\n", "<!-- butterfly->fish -->\n", "<g id=\"edge6\" class=\"edge\">\n", "<title>butterfly->fish</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M87.23,-88.41C87.23,-76.76 87.23,-61.05 87.23,-47.52\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"90.73,-47.86 87.23,-37.86 83.73,-47.86 90.73,-47.86\"/>\n", "<text text-anchor=\"middle\" x=\"105.23\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">left_of</text>\n", "</g>\n", "<!-- hourglass->butterfly -->\n", "<g id=\"edge5\" class=\"edge\">\n", "<title>hourglass->butterfly</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M54.33,-176.91C60.01,-164.94 67.71,-148.7 74.23,-134.93\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"77.38,-136.46 78.5,-125.92 71.06,-133.46 77.38,-136.46\"/>\n", "<text text-anchor=\"middle\" x=\"88.23\" y=\"-145.7\" font-family=\"Times,serif\" font-size=\"14.00\">left_of</text>\n", "</g>\n", "</g>\n", "</svg>\n" ], "text/plain": [ "digraph {\n", " \"bicycle\" -> \"pencil\" [label=\"above\", color=\"black\", style=\"solid\"]\n", " \"camera\" -> \"butterfly\" [label=\"above\", color=\"black\", style=\"solid\"]\n", " \"bicycle\" -> \"camera\" [label=\"left_of\", color=\"black\", style=\"solid\"]\n", " \"pencil\" -> \"hourglass\" [label=\"left_of\", color=\"black\", style=\"solid\"]\n", " \"hourglass\" -> \"butterfly\" [label=\"left_of\", color=\"black\", style=\"solid\"]\n", " \"butterfly\" -> \"fish\" [label=\"left_of\", color=\"black\", style=\"solid\"]\n", "}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_transition_graph(edge/3, 1, 3, 2)." ] }, { "cell_type": "markdown", "id": "4ffad2ee", "metadata": {}, "source": [ "We now define the predicates `right_of` and `below` in terms of the existing predicates:" ] }, { "cell_type": "code", "execution_count": 37, "id": "de721f76", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "right_of(X,Y) :- left_of(Y,X).\n", "below(X,Y) :- above(Y,X)." ] }, { "cell_type": "code", "execution_count": 38, "id": "ea9e3961", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/markdown": [ "X | Y | \n", ":- | :- | \n", "camera | bicycle | \n", "hourglass | pencil | \n", "butterfly | hourglass | \n", "fish | butterfly | " ], "text/plain": [ "X | Y | \n", ":- | :- | \n", "camera | bicycle | \n", "hourglass | pencil | \n", "butterfly | hourglass | \n", "fish | butterfly | " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_table(right_of(X,Y))" ] }, { "cell_type": "code", "execution_count": 39, "id": "9febc43e", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "% next(A,B) :- above(A,B); below(A,B) ; left_of(A,B) ; right_of(A,B).\n", "next(A,B) :- edge(A,_,B).\n", "next(A,B) :- edge(B,_,A)." ] }, { "cell_type": "code", "execution_count": 40, "id": "180088b8", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/markdown": [ "X | Y | \n", ":- | :- | \n", "bicycle | pencil | \n", "camera | butterfly | \n", "bicycle | camera | \n", "pencil | hourglass | \n", "hourglass | butterfly | \n", "butterfly | fish | \n", "pencil | bicycle | \n", "butterfly | camera | \n", "camera | bicycle | \n", "hourglass | pencil | \n", "butterfly | hourglass | \n", "fish | butterfly | " ], "text/plain": [ "X | Y | \n", ":- | :- | \n", "bicycle | pencil | \n", "camera | butterfly | \n", "bicycle | camera | \n", "pencil | hourglass | \n", "hourglass | butterfly | \n", "butterfly | fish | \n", "pencil | bicycle | \n", "butterfly | camera | \n", "camera | bicycle | \n", "hourglass | pencil | \n", "butterfly | hourglass | \n", "fish | butterfly | " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_table(next(X,Y))" ] }, { "cell_type": "markdown", "id": "aacfbf9d", "metadata": {}, "source": [ "## Recursion\n", "\n", "Recursion is also allowed in Prolog rules.\n", "We now define the simple graph of Figure 2.4 of the Art of Prolog as Prolog facts.\n", "\n", "Note that Prolog allows the same predicate name to be used with multiple arities.\n", "Above we have defined `edge/3`, below we define `edge/2`. For Prolog these two\n", "predicates are different and there is no confusion within the Prolog system.\n", "However, for programmers it can be a bit tricky to read code which uses\n", "the same predicate name with multiple arities." ] }, { "cell_type": "code", "execution_count": 41, "id": "12f78859", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "edge(a,b). edge(a,c).\n", "edge(b,d). edge(c,d).\n", "edge(d,e).\n", "edge(f,g)." ] }, { "cell_type": "markdown", "id": "16ffb236", "metadata": {}, "source": [ "With the underscore we indicate that we are not interested in an argument; it is an anonymous logical variable. Here we use this to find the last element of a list:" ] }, { "cell_type": "code", "execution_count": 42, "id": "99bfae95", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "image/svg+xml": [ "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n", " -->\n", "<!-- Pages: 1 -->\n", "<svg width=\"206pt\" height=\"260pt\"\n", " viewBox=\"0.00 0.00 206.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n", "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 202,-256 202,4 -4,4\"/>\n", "<!-- a -->\n", "<g id=\"node1\" class=\"node\">\n", "<title>a</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"63\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n", "</g>\n", "<!-- b -->\n", "<g id=\"node2\" class=\"node\">\n", "<title>b</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"27\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n", "</g>\n", "<!-- a->b -->\n", "<g id=\"edge1\" class=\"edge\">\n", "<title>a->b</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M54.65,-216.76C50.42,-208.55 45.19,-198.37 40.42,-189.09\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"43.68,-187.79 36,-180.49 37.46,-190.99 43.68,-187.79\"/>\n", "</g>\n", "<!-- c -->\n", "<g id=\"node3\" class=\"node\">\n", "<title>c</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"99\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"99\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n", "</g>\n", "<!-- a->c -->\n", "<g id=\"edge2\" class=\"edge\">\n", "<title>a->c</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M71.35,-216.76C75.58,-208.55 80.81,-198.37 85.58,-189.09\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"88.54,-190.99 90,-180.49 82.32,-187.79 88.54,-190.99\"/>\n", "</g>\n", "<!-- d -->\n", "<g id=\"node4\" class=\"node\">\n", "<title>d</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"63\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n", "</g>\n", "<!-- b->d -->\n", "<g id=\"edge3\" class=\"edge\">\n", "<title>b->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M35.35,-144.76C39.58,-136.55 44.81,-126.37 49.58,-117.09\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"52.54,-118.99 54,-108.49 46.32,-115.79 52.54,-118.99\"/>\n", "</g>\n", "<!-- c->d -->\n", "<g id=\"edge4\" class=\"edge\">\n", "<title>c->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M90.65,-144.76C86.42,-136.55 81.19,-126.37 76.42,-117.09\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"79.68,-115.79 72,-108.49 73.46,-118.99 79.68,-115.79\"/>\n", "</g>\n", "<!-- e -->\n", "<g id=\"node5\" class=\"node\">\n", "<title>e</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"63\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"63\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">e</text>\n", "</g>\n", "<!-- d->e -->\n", "<g id=\"edge5\" class=\"edge\">\n", "<title>d->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M63,-71.7C63,-64.41 63,-55.73 63,-47.54\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"66.5,-47.62 63,-37.62 59.5,-47.62 66.5,-47.62\"/>\n", "</g>\n", "<!-- f -->\n", "<g id=\"node6\" class=\"node\">\n", "<title>f</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"171\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n", "</g>\n", "<!-- g -->\n", "<g id=\"node7\" class=\"node\">\n", "<title>g</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"171\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"171\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">g</text>\n", "</g>\n", "<!-- f->g -->\n", "<g id=\"edge6\" class=\"edge\">\n", "<title>f->g</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M171,-215.7C171,-208.41 171,-199.73 171,-191.54\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"174.5,-191.62 171,-181.62 167.5,-191.62 174.5,-191.62\"/>\n", "</g>\n", "</g>\n", "</svg>\n" ], "text/plain": [ "digraph {\n", " \"a\" -> \"b\"\n", " \"a\" -> \"c\"\n", " \"b\" -> \"d\"\n", " \"c\" -> \"d\"\n", " \"d\" -> \"e\"\n", " \"f\" -> \"g\"\n", "}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_transition_graph(edge/2, 1, 2,0)." ] }, { "cell_type": "code", "execution_count": 44, "id": "7a790ea4", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "conn(A,A) :- true.\n", "%conn(X,Y) :- edge(X,Y).\n", "conn(X,Y) :- edge(X,Z), conn(Z,Y)." ] }, { "cell_type": "code", "execution_count": 45, "id": "440d2412", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/markdown": [ "X | \n", ":- | \n", "a | \n", "b | \n", "d | \n", "e | \n", "c | \n", "d | \n", "e | " ], "text/plain": [ "X | \n", ":- | \n", "a | \n", "b | \n", "d | \n", "e | \n", "c | \n", "d | \n", "e | " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- jupyter:print_table(conn(a,X))." ] }, { "cell_type": "code", "execution_count": 46, "id": "f50f25de", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mLs = [a,b,d,e,c,d,e],\n", "Len = 7" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- findall(X, conn(a,X),Ls), length(Ls,Len)." ] }, { "cell_type": "markdown", "id": "466ece27", "metadata": {}, "source": [ "Let us now try and define the transitive and reflexive closure of edge." ] }, { "cell_type": "code", "execution_count": 47, "id": "5627c07e", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "connected(N,N).\n", "connected(N1,N2) :- edge(N1,Link), connected(Link,N2)." ] }, { "cell_type": "code", "execution_count": 48, "id": "428e3101", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = a" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- connected(a,X)." ] }, { "cell_type": "code", "execution_count": 49, "id": "ae00f8b8", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "image/svg+xml": [ "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n", " -->\n", "<!-- Pages: 1 -->\n", "<svg width=\"344pt\" height=\"260pt\"\n", " viewBox=\"0.00 0.00 343.56 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n", "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 339.56,-256 339.56,4 -4,4\"/>\n", "<!-- _22252 -->\n", "<g id=\"node1\" class=\"node\">\n", "<title>_22252</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"38.56\" cy=\"-234\" rx=\"38.56\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"38.56\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">_22252</text>\n", "</g>\n", "<!-- _22252->_22252 -->\n", "<g id=\"edge1\" class=\"edge\">\n", "<title>_22252->_22252</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M66.2,-246.9C81.29,-249.2 95.11,-244.9 95.11,-234 95.11,-225.91 87.5,-221.46 77.4,-220.64\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"77.56,-217.13 67.71,-221.04 77.85,-224.12 77.56,-217.13\"/>\n", "</g>\n", "<!-- a -->\n", "<g id=\"node2\" class=\"node\">\n", "<title>a</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"140.56\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"140.56\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n", "</g>\n", "<!-- b -->\n", "<g id=\"node3\" class=\"node\">\n", "<title>b</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"108.56\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"108.56\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n", "</g>\n", "<!-- a->b -->\n", "<g id=\"edge2\" class=\"edge\">\n", "<title>a->b</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M132.97,-216.41C129.35,-208.48 124.91,-198.78 120.82,-189.84\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"124.06,-188.49 116.71,-180.85 117.69,-191.4 124.06,-188.49\"/>\n", "</g>\n", "<!-- d -->\n", "<g id=\"node4\" class=\"node\">\n", "<title>d</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"172.56\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"172.56\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n", "</g>\n", "<!-- a->d -->\n", "<g id=\"edge3\" class=\"edge\">\n", "<title>a->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M139.87,-215.59C142.81,-191.24 152.55,-146.81 161.01,-118.11\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"164.31,-119.27 163.96,-108.68 157.63,-117.18 164.31,-119.27\"/>\n", "</g>\n", "<!-- a->d -->\n", "<g id=\"edge6\" class=\"edge\">\n", "<title>a->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M148.81,-216.43C156.76,-192.64 167.05,-148.47 171.68,-119.41\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"175.1,-120.24 173.04,-109.84 168.17,-119.25 175.1,-120.24\"/>\n", "</g>\n", "<!-- e -->\n", "<g id=\"node5\" class=\"node\">\n", "<title>e</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"108.56\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"108.56\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">e</text>\n", "</g>\n", "<!-- a->e -->\n", "<g id=\"edge4\" class=\"edge\">\n", "<title>a->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M116.67,-225.31C98,-216.84 74.07,-201.52 63.56,-180 41.34,-134.52 66.95,-75.11 87.91,-42.67\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"90.56,-44.99 93.34,-34.77 84.79,-41.02 90.56,-44.99\"/>\n", "</g>\n", "<!-- a->e -->\n", "<g id=\"edge7\" class=\"edge\">\n", "<title>a->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M122.34,-220.44C108.31,-211.49 90.29,-197.89 81.56,-180 60.1,-136.07 83.26,-79.14 98.41,-46.08\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"101.5,-47.75 102.53,-37.21 95.15,-44.81 101.5,-47.75\"/>\n", "</g>\n", "<!-- c -->\n", "<g id=\"node6\" class=\"node\">\n", "<title>c</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"236.56\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"236.56\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n", "</g>\n", "<!-- a->c -->\n", "<g id=\"edge5\" class=\"edge\">\n", "<title>a->c</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M158.16,-220.16C172.55,-209.67 193.13,-194.66 209.6,-182.66\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"211.49,-185.61 217.51,-176.89 207.37,-179.95 211.49,-185.61\"/>\n", "</g>\n", "<!-- b->d -->\n", "<g id=\"edge8\" class=\"edge\">\n", "<title>b->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M122.13,-146.15C130.61,-136.87 141.72,-124.73 151.35,-114.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"153.82,-116.68 157.98,-106.94 148.65,-111.96 153.82,-116.68\"/>\n", "</g>\n", "<!-- b->e -->\n", "<g id=\"edge9\" class=\"edge\">\n", "<title>b->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M108.56,-143.59C108.56,-119.61 108.56,-76.14 108.56,-47.42\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"112.06,-47.62 108.56,-37.62 105.06,-47.62 112.06,-47.62\"/>\n", "</g>\n", "<!-- d->e -->\n", "<g id=\"edge12\" class=\"edge\">\n", "<title>d->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M158.98,-74.15C150.5,-64.87 139.39,-52.73 129.76,-42.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"132.46,-39.96 123.13,-34.94 127.3,-44.68 132.46,-39.96\"/>\n", "</g>\n", "<!-- c->d -->\n", "<g id=\"edge10\" class=\"edge\">\n", "<title>c->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M222.98,-146.15C214.5,-136.87 203.39,-124.73 193.76,-114.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"196.46,-111.96 187.13,-106.94 191.3,-116.68 196.46,-111.96\"/>\n", "</g>\n", "<!-- c->e -->\n", "<g id=\"edge11\" class=\"edge\">\n", "<title>c->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M235.03,-143.75C232.5,-124.33 225.86,-92.79 208.56,-72 191.75,-51.81 165.22,-38.25 143.71,-29.91\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"145.02,-26.66 134.42,-26.53 142.62,-33.23 145.02,-26.66\"/>\n", "</g>\n", "<!-- f -->\n", "<g id=\"node7\" class=\"node\">\n", "<title>f</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"308.56\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"308.56\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n", "</g>\n", "<!-- g -->\n", "<g id=\"node8\" class=\"node\">\n", "<title>g</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"308.56\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"308.56\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">g</text>\n", "</g>\n", "<!-- f->g -->\n", "<g id=\"edge13\" class=\"edge\">\n", "<title>f->g</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M308.56,-215.7C308.56,-208.41 308.56,-199.73 308.56,-191.54\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"312.06,-191.62 308.56,-181.62 305.06,-191.62 312.06,-191.62\"/>\n", "</g>\n", "</g>\n", "</svg>\n" ], "text/plain": [ "digraph {\n", " \"_22252\" -> \"_22252\"\n", " \"a\" -> \"b\"\n", " \"a\" -> \"d\"\n", " \"a\" -> \"e\"\n", " \"a\" -> \"c\"\n", " \"a\" -> \"d\"\n", " \"a\" -> \"e\"\n", " \"b\" -> \"d\"\n", " \"b\" -> \"e\"\n", " \"c\" -> \"d\"\n", " \"c\" -> \"e\"\n", " \"d\" -> \"e\"\n", " \"f\" -> \"g\"\n", "}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_transition_graph(connected/2, 1, 2,0)." ] }, { "cell_type": "markdown", "id": "fa7eb5e5", "metadata": {}, "source": [ "How should we adapt the definition to only provide the transitive (non-reflexive) closure?" ] }, { "cell_type": "code", "execution_count": 50, "id": "4ac0a146", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "conn1(X,Y) :- edge(X,Y).\n", "conn1(N1,N2) :- edge(N1,Link), conn1(Link,N2)." ] }, { "cell_type": "code", "execution_count": 51, "id": "713979ea", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = b" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- conn1(a,X)." ] }, { "cell_type": "code", "execution_count": 52, "id": "edfb9af1", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "image/svg+xml": [ "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n", " -->\n", "<!-- Pages: 1 -->\n", "<svg width=\"318pt\" height=\"260pt\"\n", " viewBox=\"0.00 0.00 318.00 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n", "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 314,-256 314,4 -4,4\"/>\n", "<!-- a -->\n", "<g id=\"node1\" class=\"node\">\n", "<title>a</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"123\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"123\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n", "</g>\n", "<!-- b -->\n", "<g id=\"node2\" class=\"node\">\n", "<title>b</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"27\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"27\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n", "</g>\n", "<!-- a->b -->\n", "<g id=\"edge1\" class=\"edge\">\n", "<title>a->b</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M105.39,-220.16C91,-209.67 70.42,-194.66 53.96,-182.66\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"56.19,-179.95 46.04,-176.89 52.06,-185.61 56.19,-179.95\"/>\n", "</g>\n", "<!-- c -->\n", "<g id=\"node3\" class=\"node\">\n", "<title>c</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"155\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"155\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n", "</g>\n", "<!-- a->c -->\n", "<g id=\"edge2\" class=\"edge\">\n", "<title>a->c</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M130.58,-216.41C134.21,-208.48 138.64,-198.78 142.73,-189.84\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"145.87,-191.4 146.84,-180.85 139.5,-188.49 145.87,-191.4\"/>\n", "</g>\n", "<!-- d -->\n", "<g id=\"node4\" class=\"node\">\n", "<title>d</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"91\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"91\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n", "</g>\n", "<!-- a->d -->\n", "<g id=\"edge7\" class=\"edge\">\n", "<title>a->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M114.74,-216.43C106.8,-192.64 96.51,-148.47 91.87,-119.41\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"95.39,-119.25 90.51,-109.84 88.46,-120.24 95.39,-119.25\"/>\n", "</g>\n", "<!-- a->d -->\n", "<g id=\"edge9\" class=\"edge\">\n", "<title>a->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M123.69,-215.59C120.74,-191.24 111,-146.81 102.55,-118.11\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"105.93,-117.18 99.6,-108.68 99.24,-119.27 105.93,-117.18\"/>\n", "</g>\n", "<!-- e -->\n", "<g id=\"node5\" class=\"node\">\n", "<title>e</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"155\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"155\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">e</text>\n", "</g>\n", "<!-- a->e -->\n", "<g id=\"edge8\" class=\"edge\">\n", "<title>a->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M141.22,-220.44C155.25,-211.49 173.26,-197.89 182,-180 203.46,-136.07 180.29,-79.14 165.14,-46.08\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"168.41,-44.81 161.02,-37.21 162.06,-47.75 168.41,-44.81\"/>\n", "</g>\n", "<!-- a->e -->\n", "<g id=\"edge10\" class=\"edge\">\n", "<title>a->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M146.88,-225.31C165.55,-216.84 189.49,-201.52 200,-180 222.21,-134.52 196.6,-75.11 175.65,-42.67\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"178.76,-41.02 170.21,-34.77 173,-44.99 178.76,-41.02\"/>\n", "</g>\n", "<!-- b->d -->\n", "<g id=\"edge3\" class=\"edge\">\n", "<title>b->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M40.57,-146.15C49.06,-136.87 60.17,-124.73 69.8,-114.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"72.26,-116.68 76.43,-106.94 67.09,-111.96 72.26,-116.68\"/>\n", "</g>\n", "<!-- b->e -->\n", "<g id=\"edge11\" class=\"edge\">\n", "<title>b->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M28.53,-143.75C31.05,-124.33 37.7,-92.79 55,-72 71.8,-51.81 98.33,-38.25 119.84,-29.91\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"120.93,-33.23 129.13,-26.53 118.54,-26.66 120.93,-33.23\"/>\n", "</g>\n", "<!-- c->d -->\n", "<g id=\"edge4\" class=\"edge\">\n", "<title>c->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M141.43,-146.15C132.94,-136.87 121.83,-124.73 112.2,-114.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"114.91,-111.96 105.57,-106.94 109.74,-116.68 114.91,-111.96\"/>\n", "</g>\n", "<!-- c->e -->\n", "<g id=\"edge12\" class=\"edge\">\n", "<title>c->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M155,-143.59C155,-119.61 155,-76.14 155,-47.42\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"158.5,-47.62 155,-37.62 151.5,-47.62 158.5,-47.62\"/>\n", "</g>\n", "<!-- d->e -->\n", "<g id=\"edge5\" class=\"edge\">\n", "<title>d->e</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M104.57,-74.15C113.06,-64.87 124.17,-52.73 133.8,-42.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"136.26,-44.68 140.43,-34.94 131.09,-39.96 136.26,-44.68\"/>\n", "</g>\n", "<!-- f -->\n", "<g id=\"node6\" class=\"node\">\n", "<title>f</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"283\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"283\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">f</text>\n", "</g>\n", "<!-- g -->\n", "<g id=\"node7\" class=\"node\">\n", "<title>g</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"283\" cy=\"-162\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"283\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">g</text>\n", "</g>\n", "<!-- f->g -->\n", "<g id=\"edge6\" class=\"edge\">\n", "<title>f->g</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M283,-215.7C283,-208.41 283,-199.73 283,-191.54\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"286.5,-191.62 283,-181.62 279.5,-191.62 286.5,-191.62\"/>\n", "</g>\n", "</g>\n", "</svg>\n" ], "text/plain": [ "digraph {\n", " \"a\" -> \"b\"\n", " \"a\" -> \"c\"\n", " \"b\" -> \"d\"\n", " \"c\" -> \"d\"\n", " \"d\" -> \"e\"\n", " \"f\" -> \"g\"\n", " \"a\" -> \"d\"\n", " \"a\" -> \"e\"\n", " \"a\" -> \"d\"\n", " \"a\" -> \"e\"\n", " \"b\" -> \"e\"\n", " \"c\" -> \"e\"\n", "}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_transition_graph(conn1/2, 1, 2,0)." ] }, { "cell_type": "markdown", "id": "7b4487b6", "metadata": {}, "source": [ "## Arithmetic\n", "Prolog provides integers and floating point numbers as primitive data structures.\n", "With the `is` predicate we can for example compute with those numbers:" ] }, { "cell_type": "code", "execution_count": 53, "id": "04ea12a1", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 1606938044258990275541962092341162602522202993782792835301376" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X is 2^200." ] }, { "cell_type": "code", "execution_count": 54, "id": "6056f98a", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = 2.0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- X is 1.0+1." ] }, { "cell_type": "markdown", "id": "53b594a2", "metadata": {}, "source": [ "# Compound data values\n", "\n", "So far we have seen these primitive Prolog data values:\n", "- constants (called atoms in Prolog) like `a` and `b`\n", "- integers\n", "- floats\n", "\n", "More complex data values can be wrapped in so-called functors (also called function symbols).\n", "Like predicates they have an arity and take terms as arguments.\n", "Unlike predicates, they denote a value and not a logical truth value.\n", "\n", "This can be confusing to beginners: whether something is a predicate or functor depends on the position in the Prolog file:\n", "- top-level symbols in Prolog clauses are predicates\n", "- arguments to predicates and functors only contain functors\n", "\n", "Functors have many uses in Prolog. The can be used for simple records up to recursive data structures like lists or trees.\n", "\n", "Below we first use the functor `employe/2` as a simple record." ] }, { "cell_type": "code", "execution_count": 55, "id": "d4664fd8", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "\n", "construct(Name,Department,employe(Name,Department)).\n", "\n", "get_name(employe(Name,_),Name).\n", "get_dept(employe(_,Dept),Dept)." ] }, { "cell_type": "code", "execution_count": 56, "id": "08715fa2", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mE1 = employe(peter,cs),\n", "E2 = employe(mary,cs),\n", "N1 = peter,\n", "D2 = cs" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- construct(peter,cs,E1), construct(mary,cs,E2), get_name(E1,N1), get_dept(E2,D2)." ] }, { "cell_type": "markdown", "id": "0b9c268b", "metadata": {}, "source": [ "Let us work out a small database example using such compound terms for data abstraction:" ] }, { "cell_type": "code", "execution_count": 57, "id": "96c11101", "metadata": {}, "outputs": [], "source": [ "% Facts for courses with time slot and location:\n", "course(logic_programming,time(tuesday,1430,1600),location(25,'5F')).\n", "course(sks,time(monday,1430,1600),location(25,'5G')).\n", "course(drones,time(thursday,1430,1600),location(25,'12.O2.55')).\n", "course(navigating_tomorrow,time(thursday,1430,1600),location(25,'12.O2.21')).\n", "% separate facts about which programme the courses belong to (can be multiple):\n", "programme(logic_programming,bachelor_cs).\n", "programme(logic_programming,master_dsai).\n", "programme(sks,master_cs).\n", "programme(navigating_tomorrow,bachelor_cs).\n" ] }, { "cell_type": "markdown", "id": "51907e39", "metadata": {}, "source": [ "Let us try and write a predicate for:\n", "- which courses take place on a particular day\n", "- which courses take place in a particular building (e.g., 25)\n", "- which courses are available for multiple programmes\n", "- which courses are in conflict (time-wise)\n", "- on which days there are courses a given programme (e.g., bachelor_cs)." ] }, { "cell_type": "code", "execution_count": null, "id": "a8a5625e", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "149e358b", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "aec2105d", "metadata": {}, "source": [ "Here is a solution. You will see that the compound term encoding of times and buildings\n", "has some advantages and drawbacks over a flatter representation such as course/6 with 6 arguments:\n", "```\n", "course(logic_programming,tuesday,1430,1600,25,'5F').\n", "```" ] }, { "cell_type": "code", "execution_count": 58, "id": "cc7b8797", "metadata": {}, "outputs": [], "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "day(Lect,Day) :- course(Lect,time(Day,_,_),_).\n", "building(Lect,Bldg) :- course(Lect,_,location(Bldg,_)).\n", "multi(Lect) :- course(Lect,_,_), programme(Lect,P1), programme(Lect,P2), P1\\=P2.\n", "conflict(L1,L2) :- course(L1,T,_), course(L2,T,_), L1\\=L2.\n", "lecture_day(Day,Progr) :- course(L1,time(Day,_,_),_), programme(L1,Progr)." ] }, { "cell_type": "code", "execution_count": 59, "id": "9d4f0001", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mL = logic_programming" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- multi(L)." ] }, { "cell_type": "code", "execution_count": 60, "id": "45f00463", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = drones,\n", "Y = navigating_tomorrow" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- conflict(X,Y)." ] }, { "cell_type": "code", "execution_count": 61, "id": "ea56ead2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mL = [tuesday,thursday]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- findall(D,lecture_day(D,bachelor_cs),L)." ] }, { "cell_type": "markdown", "id": "e2ed5de7", "metadata": {}, "source": [ "## Peano Arithmetic\n", "\n", "The arguments to a functor can in term also make use of a functor.\n", "\n", "We can also use functors of arity 1. (Functors of arity 0 are simply constants, i.e., atoms in Prolog terminology.)\n", "This can be used to represent natural numbers:\n", "- we can represent zero using the atom `zero/0`\n", "- we can represent the successor of a number using a functor `s/1` \n", "\n", "Thus the number 1 is represented by the term `s(zero)` and the number 2 by `s(s(zero))`.\n", "\n", "How could one write predicates to check if a term is a valid natural number in that representation?\n", "E.g., `s(zero)` is valid, `s(a)` is not.\n", "How could one write addition and multiplication predicate to add or multiply two numbers?\n" ] }, { "cell_type": "code", "execution_count": null, "id": "cef93eeb", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "e031e64c", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "52bc63a8", "metadata": {}, "source": [ "A possible solution is this one.\n", "This is also called Peano arithmetic. Note, that contrary to built-in arithmetic (using is/2), these predicates are reversible" ] }, { "cell_type": "code", "execution_count": 68, "id": "09e61f7e", "metadata": {}, "outputs": [], "source": [ "\n", "\n", "\n", "\n", "nat(zero).\n", "nat(s(X)) :- nat(X).\n", "\n", "plus(zero,X,X).\n", "plus(s(X),Y,s(Z)) :- plus(X,Y,Z).\n", "\n", "mult(zero,_,zero).\n", "mult(s(X),Y,Z) :- mult(X,Y,XY), plus(Y,XY,Z). % (x+1)*y = x*y + y\n", "\n", "exp(zero,s(_),zero).\n", "exp(s(_),zero,s(zero)).\n", "exp(Y,s(X),Z) :- exp(Y,X,YX), mult(YX,Y,Z)." ] }, { "cell_type": "code", "execution_count": 69, "id": "990174c1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mR = s(s(s(zero)))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-plus(s(s(zero)),s(zero),R)." ] }, { "cell_type": "code", "execution_count": 70, "id": "a37beda4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mR = s(s(s(s(s(s(zero))))))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-mult(s(s(zero)),s(s(s(zero))),R)." ] }, { "cell_type": "code", "execution_count": 71, "id": "52900216", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mR = s(s(s(s(s(s(s(s(zero))))))))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-exp(s(s(zero)),s(s(s(zero))),R)." ] }, { "cell_type": "code", "execution_count": 72, "id": "4b8f4ae7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = s(zero)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-plus(X,s(zero),s(s(zero)))." ] }, { "cell_type": "code", "execution_count": 73, "id": "fe699c18", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = s(s(zero))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-mult(X,s(zero),s(s(zero)))." ] }, { "cell_type": "markdown", "id": "71792fd2", "metadata": {}, "source": [ "## Recursive Data Structures\n", "\n", "Compound terms can be used the represent complex data structures, as will see below.\n", "First, think on how one could represent a list of objects, say a list of length 2 containing `a` and `b`.\n", "\n", "One could for example represent a list in Prolog by using\n", "a functor `cons/2` to denote a non-empty list and `nil/0` to denote\n", "an empty list.\n", "(Remember, a functor of arity 0 is simply a constant (aka atom in Prolog).)\n", "So a list of length two with a and b as elements can be represented as follows:" ] }, { "cell_type": "code", "execution_count": 74, "id": "313194bb", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mMylist = cons(a,cons(b,nil))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- Mylist = cons(a,cons(b,nil))." ] }, { "cell_type": "markdown", "id": "f2b1a0cd", "metadata": {}, "source": [ "Let us now try and define some useful predicates for our data type:\n", "- is_empty/1 to check if something is the empty list\n", "- is_list/1 to check if something is a list\n", "- head/1 to get the first element of a list\n", "- element_of/2 to check if something is an element of a list\n", "- last/1 to get the last elemetn of a list" ] }, { "cell_type": "code", "execution_count": 75, "id": "e0eed7cc", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "is_empty(nil) :- true." ] }, { "cell_type": "markdown", "id": "6efab831", "metadata": {}, "source": [ "This should succeed:" ] }, { "cell_type": "code", "execution_count": 76, "id": "82f68320", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- is_empty(nil)." ] }, { "cell_type": "code", "execution_count": null, "id": "6c2de157", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1;31mfalse" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- is_empty(cons(a,nil))." ] }, { "cell_type": "markdown", "id": "d0e8eb01", "metadata": {}, "source": [ "Let us now define is_list0 (is_list is predefined):" ] }, { "cell_type": "code", "execution_count": 78, "id": "c2615402", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "is_list0(nil).\n", "is_list0(cons(_,B)) :- is_list0(B).\n", "\n", "is_non_empty_list(cons(_,B)) :- is_list0(B)." ] }, { "cell_type": "code", "execution_count": 79, "id": "d2b8accc", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?-is_list0(cons(employe(a,cs),cons(b,nil)))." ] }, { "cell_type": "code", "execution_count": 80, "id": "9cf37f7f", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "head(First,cons(First,_)) :- true." ] }, { "cell_type": "code", "execution_count": 81, "id": "05f68119", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = employe(a,b)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- head(X,cons(employe(a,b),cons(b,nil)))." ] }, { "cell_type": "code", "execution_count": 82, "id": "bef84acb", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "element_of(First,cons(First,_)).\n", "element_of(H,cons(_,T)) :- element_of(H,T)." ] }, { "cell_type": "code", "execution_count": 83, "id": "b1707b0f", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mY = cons(c,_8970)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- element_of(c,cons(a,cons(b,Y)))." ] }, { "cell_type": "code", "execution_count": 84, "id": "0cdcb148", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mY = cons(_8968,cons(c,_8976))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:retry." ] }, { "cell_type": "code", "execution_count": 85, "id": "4365798d", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mFirst = a" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- element_of(First,cons(a,nil))" ] }, { "cell_type": "code", "execution_count": 86, "id": "097687f9", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/markdown": [ "X | \n", ":- | \n", "a | \n", "b | " ], "text/plain": [ "X | \n", ":- | \n", "a | \n", "b | " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_table(element_of(X,cons(a,cons(b,nil))))" ] }, { "cell_type": "code", "execution_count": 87, "id": "e3c67e2b", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "last0(X,cons(X,nil)).\n", "last0(X,cons(_,Y)) :- last0(X,Y)." ] }, { "cell_type": "code", "execution_count": 88, "id": "1c91221d", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mX = b" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- last0(X,cons(a,cons(b,nil)))." ] }, { "cell_type": "markdown", "id": "e8582b42", "metadata": {}, "source": [ "Exercise: write predicates prefix/2 and suffix/2 which is true if the first argument is a prefix or suffix of the second one." ] }, { "cell_type": "code", "execution_count": null, "id": "58013688", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "e7c6f995", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "5f251e4d", "metadata": {}, "source": [ "## Trees\n", "\n", "As a quick example let us represent binary trees using compound Prolog terms.\n", "For this we use a ternary functor `tree/3`.\n", "It has three arguments:\n", "- the left sub-tree\n", "- the information at the root of the tree\n", "- the right sub-tree\n", "We also need the empty tree, which we represent by `nil`.\n", "\n", "For example, how would you represent this tree:\n", "" ] }, { "cell_type": "code", "execution_count": 89, "id": "0dcf1d4c", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mMytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- Mytree = tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil)))." ] }, { "cell_type": "markdown", "id": "bf99403d", "metadata": {}, "source": [ "Let us now try to write a predicate which reverses (mirrors) the tree, swapping left and right children:" ] }, { "cell_type": "code", "execution_count": 90, "id": "52fb0c11", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "revtree(nil,nil).\n", "revtree(tree(L,Info,R),tree(RR,Info,RL)) :- revtree(L,RL), revtree(R,RR)." ] }, { "cell_type": "code", "execution_count": 91, "id": "c3a7cd35", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mMytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),\n", "Result = tree(tree(tree(nil,d,nil),c,nil),b,tree(nil,a,nil))" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- Mytree = tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),\n", " revtree(Mytree,Result)." ] }, { "cell_type": "markdown", "id": "d883817f", "metadata": {}, "source": [ "## Optional Appendix: Visualising data values as trees\n", "\n", "Below we try to use the Jupyter graph visualisation to represent data values\n", "in a tree-like fashion." ] }, { "cell_type": "code", "execution_count": 92, "id": "ffe1cbc6", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ ":- use_module(library(lists))." ] }, { "cell_type": "markdown", "id": "05730fc3", "metadata": {}, "source": [ "We define a subtree relation, using the =.. built-in predicate, which deconstructs a term\n", "by generating a list consisting of the function symbol and all its arguments:" ] }, { "cell_type": "code", "execution_count": 93, "id": "39fc2aab", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mList = [tree,nil,a,nil]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- tree(nil,a,nil) =.. List." ] }, { "cell_type": "markdown", "id": "4088fdfa", "metadata": {}, "source": [ "We can now define a subtree relation:" ] }, { "cell_type": "code", "execution_count": 94, "id": "536475da", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "subtree(Term,Nr,SubTerm) :- Term =.. [_|List], nth1(Nr,List,SubTerm)." ] }, { "cell_type": "code", "execution_count": 95, "id": "eb820f56", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mMytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),\n", "Nr = 1,\n", "SubTerm = tree(nil,a,nil)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- Mytree = tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),\n", " subtree(Mytree,Nr,SubTerm)." ] }, { "cell_type": "markdown", "id": "69ae338f", "metadata": {}, "source": [ "For the Jupyter graph visualisation we also need to restrict this relation and define a set of terms of interest.\n", "Indeed, otherwise there are infinitely many terms.\n", "\n", "For this we define the transitive and reflexive closure of the subtree relation and only consider subtrees of a given starting term (here `tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil)))`)." ] }, { "cell_type": "code", "execution_count": 96, "id": "4b4732c1", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [ "rec_subtree(Term,Sub) :- Term = Sub.\n", "rec_subtree(Term,Sub) :- subtree(Term,_,X), rec_subtree(X,Sub).\n", "\n", "of_interest(Term) :- rec_subtree(tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),Term).\n", "\n", "subt(Term,Nr,SubTerm) :-\n", " of_interest(Term), % only consider subterms of the above term as nodes\n", " subtree(Term,Nr,SubTerm)." ] }, { "cell_type": "code", "execution_count": 97, "id": "2992249a", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "text/plain": [ "\u001b[1mMytree = tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))),\n", "Nr = 1,\n", "SubTerm = tree(nil,a,nil)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "?- Mytree = tree( tree(nil,a,nil), b, tree(nil,c,tree(nil,d,nil))),\n", " subtree(Mytree,Nr,SubTerm)." ] }, { "cell_type": "code", "execution_count": 98, "id": "2b76644b", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [ { "data": { "image/svg+xml": [ "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n", "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n", " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n", "<!-- Generated by graphviz version 10.0.1 (20240210.2158)\n", " -->\n", "<!-- Pages: 1 -->\n", "<svg width=\"474pt\" height=\"310pt\"\n", " viewBox=\"0.00 0.00 474.31 309.50\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 305.5)\">\n", "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-305.5 470.31,-305.5 470.31,4 -4,4\"/>\n", "<!-- tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil))) -->\n", "<g id=\"node1\" class=\"node\">\n", "<title>tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"177.26\" cy=\"-283.5\" rx=\"177.26\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"177.26\" y=\"-278.45\" font-family=\"Times,serif\" font-size=\"14.00\">tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))</text>\n", "</g>\n", "<!-- tree(nil,a,nil) -->\n", "<g id=\"node2\" class=\"node\">\n", "<title>tree(nil,a,nil)</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"153.26\" cy=\"-106.5\" rx=\"59.54\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"153.26\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">tree(nil,a,nil)</text>\n", "</g>\n", "<!-- tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->tree(nil,a,nil) -->\n", "<g id=\"edge1\" class=\"edge\">\n", "<title>tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->tree(nil,a,nil)</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M162.84,-265.22C152.71,-251.89 140.02,-232.49 134.51,-213 127.17,-187.05 134.15,-156.67 141.59,-135.19\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"144.81,-136.56 145.03,-125.96 138.26,-134.11 144.81,-136.56\"/>\n", "<text text-anchor=\"middle\" x=\"138.63\" y=\"-189.95\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n", "</g>\n", "<!-- b -->\n", "<g id=\"node3\" class=\"node\">\n", "<title>b</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"177.26\" cy=\"-195\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"177.26\" y=\"-189.95\" font-family=\"Times,serif\" font-size=\"14.00\">b</text>\n", "</g>\n", "<!-- tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->b -->\n", "<g id=\"edge2\" class=\"edge\">\n", "<title>tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->b</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M177.26,-265.41C177.26,-253.76 177.26,-238.05 177.26,-224.52\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"180.76,-224.86 177.26,-214.86 173.76,-224.86 180.76,-224.86\"/>\n", "<text text-anchor=\"middle\" x=\"180.63\" y=\"-234.2\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n", "</g>\n", "<!-- tree(nil,c,tree(nil,d,nil)) -->\n", "<g id=\"node4\" class=\"node\">\n", "<title>tree(nil,c,tree(nil,d,nil))</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"321.26\" cy=\"-195\" rx=\"98.95\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"321.26\" y=\"-189.95\" font-family=\"Times,serif\" font-size=\"14.00\">tree(nil,c,tree(nil,d,nil))</text>\n", "</g>\n", "<!-- tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->tree(nil,c,tree(nil,d,nil)) -->\n", "<g id=\"edge3\" class=\"edge\">\n", "<title>tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))->tree(nil,c,tree(nil,d,nil))</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M205.71,-265.41C228.18,-251.91 259.73,-232.96 284.18,-218.27\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"285.78,-221.4 292.55,-213.25 282.17,-215.4 285.78,-221.4\"/>\n", "<text text-anchor=\"middle\" x=\"264.63\" y=\"-234.2\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n", "</g>\n", "<!-- nil -->\n", "<g id=\"node5\" class=\"node\">\n", "<title>nil</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"249.26\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"249.26\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">nil</text>\n", "</g>\n", "<!-- tree(nil,a,nil)->nil -->\n", "<g id=\"edge4\" class=\"edge\">\n", "<title>tree(nil,a,nil)->nil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M165.03,-88.6C172.93,-77.97 183.96,-64.34 195.51,-54 202.7,-47.56 211.19,-41.46 219.27,-36.22\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"220.89,-39.33 227.53,-31.08 217.19,-33.39 220.89,-39.33\"/>\n", "<text text-anchor=\"middle\" x=\"198.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n", "</g>\n", "<!-- tree(nil,a,nil)->nil -->\n", "<g id=\"edge6\" class=\"edge\">\n", "<title>tree(nil,a,nil)->nil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M177.45,-89.73C185.62,-84.02 194.59,-77.3 202.26,-70.5 211.76,-62.07 221.38,-51.89 229.41,-42.81\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"231.97,-45.21 235.87,-35.36 226.68,-40.63 231.97,-45.21\"/>\n", "<text text-anchor=\"middle\" x=\"221.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n", "</g>\n", "<!-- a -->\n", "<g id=\"node6\" class=\"node\">\n", "<title>a</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"153.26\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"153.26\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">a</text>\n", "</g>\n", "<!-- tree(nil,a,nil)->a -->\n", "<g id=\"edge5\" class=\"edge\">\n", "<title>tree(nil,a,nil)->a</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M153.26,-88.41C153.26,-76.76 153.26,-61.05 153.26,-47.52\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"156.76,-47.86 153.26,-37.86 149.76,-47.86 156.76,-47.86\"/>\n", "<text text-anchor=\"middle\" x=\"156.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n", "</g>\n", "<!-- tree(nil,c,tree(nil,d,nil))->nil -->\n", "<g id=\"edge7\" class=\"edge\">\n", "<title>tree(nil,c,tree(nil,d,nil))->nil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M299.88,-176.97C285.51,-164.19 267.6,-145.36 258.51,-124.5 247.85,-100.04 246.3,-69.41 246.96,-47.46\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"250.44,-47.93 247.44,-37.77 243.45,-47.59 250.44,-47.93\"/>\n", "<text text-anchor=\"middle\" x=\"261.63\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n", "</g>\n", "<!-- c -->\n", "<g id=\"node7\" class=\"node\">\n", "<title>c</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"301.26\" cy=\"-106.5\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"301.26\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">c</text>\n", "</g>\n", "<!-- tree(nil,c,tree(nil,d,nil))->c -->\n", "<g id=\"edge8\" class=\"edge\">\n", "<title>tree(nil,c,tree(nil,d,nil))->c</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M316.14,-176.62C314.56,-171.02 312.88,-164.77 311.51,-159 309.73,-151.55 308.02,-143.45 306.51,-135.92\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"309.97,-135.38 304.64,-126.22 303.1,-136.71 309.97,-135.38\"/>\n", "<text text-anchor=\"middle\" x=\"314.63\" y=\"-145.7\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n", "</g>\n", "<!-- tree(nil,d,nil) -->\n", "<g id=\"node8\" class=\"node\">\n", "<title>tree(nil,d,nil)</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"406.26\" cy=\"-106.5\" rx=\"60.05\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"406.26\" y=\"-101.45\" font-family=\"Times,serif\" font-size=\"14.00\">tree(nil,d,nil)</text>\n", "</g>\n", "<!-- tree(nil,c,tree(nil,d,nil))->tree(nil,d,nil) -->\n", "<g id=\"edge9\" class=\"edge\">\n", "<title>tree(nil,c,tree(nil,d,nil))->tree(nil,d,nil)</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M338.05,-176.91C350.59,-164.15 367.91,-146.53 381.95,-132.23\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"384.21,-134.93 388.73,-125.34 379.22,-130.02 384.21,-134.93\"/>\n", "<text text-anchor=\"middle\" x=\"374.63\" y=\"-145.7\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n", "</g>\n", "<!-- tree(nil,d,nil)->nil -->\n", "<g id=\"edge10\" class=\"edge\">\n", "<title>tree(nil,d,nil)->nil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M373.45,-91.18C360.24,-85.15 344.97,-77.83 331.51,-70.5 313.06,-60.45 293.07,-47.98 277.42,-37.82\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"279.36,-34.91 269.08,-32.36 275.53,-40.77 279.36,-34.91\"/>\n", "<text text-anchor=\"middle\" x=\"334.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n", "</g>\n", "<!-- tree(nil,d,nil)->nil -->\n", "<g id=\"edge12\" class=\"edge\">\n", "<title>tree(nil,d,nil)->nil</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M387.59,-89.14C374.45,-78.19 356.08,-64 338.26,-54 321.15,-44.4 300.88,-36.21 284.01,-30.17\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"285.51,-26.98 274.91,-27.01 283.21,-33.6 285.51,-26.98\"/>\n", "<text text-anchor=\"middle\" x=\"364.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n", "</g>\n", "<!-- d -->\n", "<g id=\"node9\" class=\"node\">\n", "<title>d</title>\n", "<ellipse fill=\"none\" stroke=\"black\" cx=\"406.26\" cy=\"-18\" rx=\"27\" ry=\"18\"/>\n", "<text text-anchor=\"middle\" x=\"406.26\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">d</text>\n", "</g>\n", "<!-- tree(nil,d,nil)->d -->\n", "<g id=\"edge11\" class=\"edge\">\n", "<title>tree(nil,d,nil)->d</title>\n", "<path fill=\"none\" stroke=\"black\" d=\"M406.26,-88.41C406.26,-76.76 406.26,-61.05 406.26,-47.52\"/>\n", "<polygon fill=\"black\" stroke=\"black\" points=\"409.76,-47.86 406.26,-37.86 402.76,-47.86 409.76,-47.86\"/>\n", "<text text-anchor=\"middle\" x=\"409.63\" y=\"-57.2\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n", "</g>\n", "</g>\n", "</svg>\n" ], "text/plain": [ "digraph {\n", " \"tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))\" -> \"tree(nil,a,nil)\" [label=\"1\", color=\"black\", style=\"solid\"]\n", " \"tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))\" -> \"b\" [label=\"2\", color=\"black\", style=\"solid\"]\n", " \"tree(tree(nil,a,nil),b,tree(nil,c,tree(nil,d,nil)))\" -> \"tree(nil,c,tree(nil,d,nil))\" [label=\"3\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,a,nil)\" -> \"nil\" [label=\"1\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,a,nil)\" -> \"a\" [label=\"2\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,a,nil)\" -> \"nil\" [label=\"3\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,c,tree(nil,d,nil))\" -> \"nil\" [label=\"1\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,c,tree(nil,d,nil))\" -> \"c\" [label=\"2\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,c,tree(nil,d,nil))\" -> \"tree(nil,d,nil)\" [label=\"3\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,d,nil)\" -> \"nil\" [label=\"1\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,d,nil)\" -> \"d\" [label=\"2\", color=\"black\", style=\"solid\"]\n", " \"tree(nil,d,nil)\" -> \"nil\" [label=\"3\", color=\"black\", style=\"solid\"]\n", "}" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\u001b[1mtrue" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "jupyter:print_transition_graph(subt/3, 1, 3,2)." ] }, { "cell_type": "code", "execution_count": null, "id": "f65812f1", "metadata": { "vscode": { "languageId": "prolog" } }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Prolog", "language": "prolog", "name": "prolog_kernel" }, "language_info": { "codemirror_mode": "prolog", "file_extension": ".pl", "mimetype": "text/x-prolog", "name": "Prolog" } }, "nbformat": 4, "nbformat_minor": 5 }