Hacker News new | comments | ask | show | jobs | submit login
Logic Programming and Compiler Writing (1980) [pdf] (sovietov.com)
95 points by weatherlight 5 months ago | hide | past | web | favorite | 8 comments

If you'd like to see a much smaller worked example of an assembler and machine, I built a Prolog implementation of the reddit dailyprogrammer challenge "Halt Machine" a few years ago. My code is here:


The challenge itself is here:


It would be cool to see a "many worlds" version of this, where the interpreter forks every time a RANDOM instruction is executed such that one fork has the value 0 and the other has the value 1, and the output tells whether or not all the forks have halted within 100,000 instructions.

it is very interesting to see an actual implementation of such kind of compiler in a set of logical rules. I see in the reddit link that there are implementations in other languages but everyone seems to be an expert in the languages they are using (e.g. the JS one seems to be the most straightforward and the Common Lisp quite verbose actually)

Do you have a similar experience using other languages or paradigms? what were your subjective challenges and the benefits compared with other languages?

The idea at work here is Alan Kay's, to bring the spec into the language as code somehow. Prolog is better suited to this than many other languages, simply because it is so easy to reuse existing operators and structures but overlay them with new semantics, as well as adding your own operators. But I think you can do that same fundamental idea in any language. The ROI will often be lower though, if you tried to do what I did in Java, for instance. In this case the core is very procedural. That was kind of fun to do, just as a reminder that Prolog can do that without it being onerous. But the ROI would have been even higher if the core problem involved nondeterminism, constraints or deduction in some unavoidable way.

A lot of the code I write in Prolog is written to demonstrate you can do practical things in Prolog without it turning into C or Pascal. I feel that Lisp managed to shed the "this is only for AI" stigma, thanks to books like Practical Common Lisp and partly thanks to Emacs itself. But Prolog is still sort of thought of as this freak language only really useful for solving Einstein puzzles and sudoku.

Prolog is not my strongest language, and I am far from an expert in it. But, I don't think you have to be an expert in it to use it productively and enjoy it. If I had tried to do this problem in Haskell or Python or Java, I would probably have solved it in a completely different way.

I don't know if this addresses your questions or not, but I'm glad to talk more.

it's interesting to mention that both Alan Kay (see "The early history of Smalltalk") and John McCarthy (see "advice taker") have very high opinion of logic programming.

Thanks for showing your code! I just placed my minimalist DSL tools and decided to use "Halt Problem" as an example. Here is my code: https://github.com/true-grue/dsl-tools

Very beautiful code! Thanks for sharing it, I really like the simplicity of your parser combinators.

Thank you very much! I decided to place my DSL tools (they contain a tiny amount of code, but I've used them successfully in a number of compiler projects) on github and just started looking for some illustrative examples. And your solution for Halt Problem (never heard about this problem before -- I mean this reddit challenge, of course, not Rice's theorem) appeared just in a right time. Thank you! :)

As a side note. It would be interesting to investigate power of a Prolog-like language which has terms, term variables, pattern matching (maybe even without full unification) and only local backtracking. Plus an ability to make user-defined execution strategies (tree traversals etc) in the form of combinators. I already use most of these constucts in dsl_match module and I got my inspiration mostly from Stratego/XT. Still it would be good to see similiar general-purpose language and compare its expressiveness with Prolog.

This is basically the Lisp program. See below. Does not seem to be that verbose:

  (defun run (&optional (stream *standard-input*))
    (let ((pc     0)
          (mem    (make-array 32 :element-type 'bit :initial-element 0))
          (halted nil))
      (labels ((execute (code &optional a b)
                 (macrolet ((mref (idx) `(sbit mem ,idx)))
                   (ecase code
                     (and    (setf (mref a) (logand (mref a) (mref b))))
                     (or     (setf (mref a) (logior (mref a) (mref b))))
                     (xor    (setf (mref a) (logxor (mref a) (mref b))))
                     (not    (setf (mref a) (if (zerop (mref a)) 1 0)))
                     (mov    (setf (mref a) (mref b)))
                     (set    (setf (mref a) b))
                     (random (setf (mref a) (random 2)))
                     (jmp    (setf pc (1- a)))
                     (jz     (when (zerop (mref b)) (setf pc (1- a))))
                     (halt   (setf halted t)))))
               (interpret (codes)
                 (loop for nil = (apply #'execute (aref codes pc)) and cycles from 1
                       do (incf pc)
                       until (or halted (>= cycles 100000))
                       finally (if halted
                                   (format t "Program halts! ~a instructions executed.~%" cycles)
                                 (format t "Unable to determine if program halts.~%"))))
               (read-program ()
                 (coerce (loop for pc below (parse-integer (read-line stream)) collect
                               (read-from-string (concatenate 'string "(" (read-line stream) ")")))
        (interpret (read-program)))))
Adapted from: https://www.reddit.com/r/dailyprogrammer/comments/1euacb/052...

The rest in the example is an actual compiler.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact