Na zakończenie wykładu z Programowania w Logice chciałbym dokonać krótkiego podsumowania.

1. Omówiony został jeden z ciekawszych języków programowania, który wywodzi się bezpośrednio z logiki, a dokładniej z rachunku predykatów pierwszego rzędu [1].
2. Prolog jest przykładem języka deklaratywnego, w którym opisuje się problem bez podawania algorytmu jego rozwiązania [2].
3. Dostępne implementacje Prologu dostarczają nie tylko maszynę abstrakcyjną i kompilator na tę maszynę ale również liczne moduły ułatwiające praktyczne zastosowania tego języka (grafika, dostęp do baz danych, serwer/klient HTTP, parser SGML/XML, programowanie ograniczeń, przetwarzanie języka naturalnego, sieci semantyczne, obsługa SSL, …).
4. Szczególnie interesujące są moduły CLPFD, CLPB, CLPQ, CLPR i CHR, które dostarczają programowanie ograniczeń, w istotny sposób przyspieszające znajdowanie rozwiązań.
5. Programowanie ograniczeń dostarczane jest w postaci bibliotek i rozszerzeń dla wielu języków programowania. Należy jednak pamiętać, że po raz pierwszy opracowano je dla języka Prolog jako CLP (Constraint Logic Programming), w naturalny sposób rozszerzając deklaratywność tego języka (pierwsze implementacje to Prolog III, CLP(R) i CHIP).
6. Między innymi firma IBM dostarcza komercyjną bibliotekę IBM ILOG CP Optimizer dla języków C++ i Java [3]. Biblioteka ta jest omawiana na kursie Technologia więzów (kurs wybieralny na studiach drugiego stopnia).

Przykłady z biblioteki IBM ILOG CP Optimizer

Język C++

// -------------------------------------------------------------- -*- C++ -*-
// File: ./examples/src/cpp/color.cpp
// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5725-A06 5725-A29
// Copyright IBM Corporation 1990, 2014. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

/* ------------------------------------------------------------

Problem Description
-------------------

The problem involves choosing colors for the countries on a map in
such a way that at most four colors (blue, white, yellow, green) are
used and no neighboring countries are the same color. In this exercise,
you will find a solution for a map coloring problem with six countries:
Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands.

------------------------------------------------------------ */

#include <ilcp/cp.h>

const char* Names[] = {"blue", "white", "yellow", "green"};

int main(int , const char * []){
  IloEnv env;
  try {
    IloModel model(env);
    IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"),
      France(env, 0, 3, "F"), Germany(env, 0, 3, "D"),
      Luxembourg(env, 0, 3, "L"), Netherlands(env, 0, 3, "NE");
    model.add(Belgium != France);
    model.add(Belgium != Germany);
    model.add(Belgium != Netherlands);
    model.add(Belgium != Luxembourg);
    model.add(Denmark != Germany );
    model.add(France != Germany);
    model.add(France != Luxembourg);
    model.add(Germany != Luxembourg);
    model.add(Germany != Netherlands);
    IloCP cp(model);
    if (cp.solve())
      {
      cp.out() << std::endl << cp.getStatus() << " Solution" << std::endl;
      cp.out() << "Belgium:     " << Names[cp.getValue(Belgium)] << std::endl;
      cp.out() << "Denmark:     " << Names[cp.getValue(Denmark)] << std::endl;
      cp.out() << "France:      " << Names[cp.getValue(France)] << std::endl;
      cp.out() << "Germany:     " << Names[cp.getValue(Germany)] << std::endl;
      cp.out() << "Luxembourg:  " << Names[cp.getValue(Luxembourg)]  << std::endl;
      cp.out() << "Netherlands: " << Names[cp.getValue(Netherlands)] << std::endl;
    }
  }
  catch (IloException& ex) {
    env.out() << "Error: " << ex << std::endl;
  }
  env.end();
  return 0;
}

/*
Feasible Solution
Belgium:     yellow
Denmark:     blue
France:      blue
Germany:     white
Luxembourg:  green
Netherlands: blue
*/

Język Java

// ---------------------------------------------------------------*- Java -*-
// File: ./examples/src/java/Color.java
// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5725-A06 5725-A29
// Copyright IBM Corporation 1990, 2017. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

/* ------------------------------------------------------------

Problem Description
-------------------

The problem involves choosing colors for the countries on a map in
such a way that at most four colors (blue, white, yellow, green) are
used and no neighboring countries are the same color. In this exercise,
you will find a solution for a map coloring problem with six countries:
Belgium, Denmark, France, Germany, Luxembourg, and the Netherlands.

------------------------------------------------------------ */

import ilog.cp.*;
import ilog.concert.*;

public class Color {
    public static String[] Names = {"blue", "white", "yellow", "green"};
    public static void main(String[] args) {
        try {
            IloCP cp = new IloCP();
            IloIntVar Belgium = cp.intVar(0, 3);
            IloIntVar Denmark = cp.intVar(0, 3);
            IloIntVar France = cp.intVar(0, 3);
            IloIntVar Germany = cp.intVar(0, 3);
            IloIntVar Luxembourg = cp.intVar(0, 3);
            IloIntVar Netherlands = cp.intVar(0, 3);


            cp.add(cp.neq(Belgium , France));
            cp.add(cp.neq(Belgium , Germany));
            cp.add(cp.neq(Belgium , Netherlands));
            cp.add(cp.neq(Belgium , Luxembourg));
            cp.add(cp.neq(Denmark , Germany));
            cp.add(cp.neq(France , Germany));
            cp.add(cp.neq(France , Luxembourg));
            cp.add(cp.neq(Germany , Luxembourg));
            cp.add(cp.neq(Germany , Netherlands));

            if (cp.solve())
                {
                   System.out.println();
                   System.out.println( "Belgium:     " + Names[(int)cp.getValue(Belgium)]);
                   System.out.println( "Denmark:     " + Names[(int)cp.getValue(Denmark)]);
                   System.out.println( "France:      " + Names[(int)cp.getValue(France)]);
                   System.out.println( "Germany:     " + Names[(int)cp.getValue(Germany)]);
                   System.out.println( "Luxembourg:  " + Names[(int)cp.getValue(Luxembourg)]);
                   System.out.println( "Netherlands: " + Names[(int)cp.getValue(Netherlands)]);
                }
        } catch (IloException e) {
            System.err.println("Error " + e);
        }
    }
}

Język CPO (modele dla programu CPoptimizer)

// Decision variables:
Belgium = intVar(1..4);
Denmark = intVar(1..4);
France = intVar(1..4);
Germany = intVar(1..4);
Luxembourg = intVar(1..4);
Netherlands = intVar(1..4);

/* Constraints: */
Belgium != France;
Belgium != Germany;
Belgium != Netherlands;
Belgium != Luxembourg;
Denmark != Germany;
France != Germany;
France != Luxembourg;
Germany != Luxembourg;
Germany != Netherlands;

parameters {
  SearchType = DepthFirst;
}

Dziękuję wszystkim za udział w kursie. Życzę powodzenia podczas sesji i udanego odpoczynku podczas wakacji. Mam nadzieję, że spotkamy się w październiku na uczelni, a nie tylko zdalnie przez sieć.


Bibliografia

1. John Wylie Lloyd. Foundation of Logic Programming. Springer-Verlan, 1993.
2. Robert Kowalski. Logika w rozwiązywania zadań. WNT, 1989. (PDF)
3. IBM ILOG CPLEX Optimization Studio. CP Optimizer User's Manual.

Tags: podsumowanie, język CPO, język C++, język Java, rachunek predykatów, programowanie ograniczeń

(Obejrzano 1 razy)

Tags: pseudokod, formalna weryfikacja, TANTRIX Discovery, węzeł celtycki, podział prostokąta, logika Hoare'a, najsłabszy warunek wstępny

(Obejrzano 4 razy)

Tags: ograniczenie globalne, etykietowanie zmiennych, strategia sterowania etykietowaniem