Algorithm = Logic and Control [pdf]
67 points by acmerfight 7 days ago | 12 comments
  • acmerfight 7 days ago |
    An algorithm can be regarded as consisting of a logic component, which specifies the knowledge to be used in solving problems, and a control component, which determines the problem-solving strategies by means of which that knowledge is used. The logic component determines the meaning of the algorithm whereas the control component only affects its efficiency. The efficiency of an algorithm can often be improved by improving the control component without changing the logic of the algorithm. We argue that computer programs would be more often correct and more easily improved and modified if their logic and control aspects were identified and separated in the program text.
  • forks a day ago |
    Fantastic podcast interviewing the author: https://thesearch.space/episodes/1-the-poet-of-logic-program...
  • upghost a day ago |
    Scryer Prolog meetup on the 7th/8th if Nov in Vienna if you happen to be around and into this sort of thing :)
  • charlieflowers a day ago |
    Hexagonal / ports and adapters / onion / functional core imperative shell all try to do this.
  • anjiro a day ago |
    (1979)
  • EgoIsMyFriend 20 hours ago |
    Does anyone use prolog in their day to day life? I would love to hear some anecdotes.

    My experience with the language from doing a constraint programming course in master's is that programs that can be solved quickly on procedural languages tend to require immense thinking and testing to be done in prolog. It's gotten so bad that all students don't even bother learning it since you aren't given much time during the exam and the problems are very complex.

    • YeGoblynQueenne 18 hours ago |
      I've done the majority of my programming work in Prolog in the last 6 years, both in academia and for a brief stint in the industry (although that was with Visual Prolog which is a very idiosyncratic form of Prolog) [edit: oh, I forget: I did two stints in the industry working with Prolog haha.].

      My standard advice is that if you find Prolog too hard then you shouldn't try to learn it because you will most likely never need it in your day to day work and you'll be just wasting time you could use familiarising yourself with the latest js framework or whatever is needed in your line of work. If for some reason you are forced to learn Prolog (as far as I know most university courses don't make it mandatory) and you're trying to solve problems that can be "solved quickly on [imperative] languages" then either those are not good problems to solve to learn Prolog and you should ask your tutor to come up with better ones, or you are trying to program in Prolog using an imperative style that it doesn't support, but again it would be too much hard work trying to learn not to do that so just bite the bullet and wait for the pain to be over.

      Don't marry someone you don't love and don't learn a language you don't need. Simple, yes?

      • YeGoblynQueenne 18 hours ago |
        Here's a more personal perspective. I first learned Prolog 15 ish years ago, in the second year of my CS (with games design) degree. The difficulty hit me like a ton of bricks. With no exaggeration it took me a week to figure out how to do the simplest of things: cycle through a list of options (those were the turn phases for a Magic: the Gathering game engine. Nobody ever accused of starting with the easy stuff first). I persevered partly because the idea of executing First Order Logic theorems as a computer program took my breath away and partly because everyone agreed that Prolog was so damn hard and I just wanted to brag about being able to learn it to my peers.

        I learned it. It took years. I don't think I had the chance to brag to my peers. I went to the university library and picked up every textbook I could find on Prolog, returned home with knees trembling under the weight of my backpack bulging at the seams with K N O W L E D G E and spent weeks lost in them. The more I learned, the more I forgot about bragging and the more I got hooked, like a fool who tries crack for just the one time. The more I used Prolog, the more it hurt me, the more I couldn't understand it, the more I finally got it, the more I got drawn in, deeper and deeper.

        It took a few years before I could indulge my passion and follow what our Dang would call my intellectual curiosity, and start a PhD on Inductive Logic Programming (i.e. machine learning × logic programming) but I finally got my wish and like I say above, I've basically done all my programming in Prolog as a day job for the last 6 years or so, with a smattering of Python and R in between.

        And now I'm out of a job and I might have to go back to C# and SQL. But, it was good while it lasted. If you want to go on an adventure of the mind, don't put it off. You won't regret it. Find your own Prolog. Go. Go!

        • EgoIsMyFriend 16 hours ago |
          thank you for the passionate response!

          If you have a bit of time to translate the problems I was talking about from french to english here they are for example: (2022 - exercise 3) [0] solution [1], directory of past exams[2]

          [0] https://perso.usthb.dz/~aisli/AmarIsli_files/M2SII/Corriges/...

          [1] https://perso.usthb.dz/~aisli/AmarIsli_files/M2SII/Corriges/...

          [2]https://perso.usthb.dz/~aisli/AmarIsli_files/M2SII/Corriges/

          • YeGoblynQueenne 15 hours ago |
            Mmouais, quesque j'ai dit? C'est pas comme ça qu' on represente les matrices en Prolog. Pas comme une liste mais comme un terme qu' on utilise comme un tableau 2d (array) en row-major ordre. Sinon c'est le bordel.

            J'ai une implementation la dedans:

            https://github.com/stassa/ijclr_2024_experiments/tree/master...

            Mais c'est un peut partout, dans deux ou trois fichiers, pas facile a trouver.

            En tout cas, c'est pas une bonne exercise pour Prolog, une matrice. J'aurais preferrer une balanced heap, par example.

            Et avec des transposees en plus. Non mais il est debile le prof?

            Apologies for the lack of proper punctuation :)

            • EgoIsMyFriend 15 hours ago |
              haha wasn't expecting the french response. I wish I spoke it that well. But yeah, the university I was in (usthb) is notorious (in algeria) for having the most difficult exams so stuff like this is expected
              • YeGoblynQueenne 9 hours ago |
                Ah, Algeria! Well, I'm Greek but I never miss a chance to try my French on :)