4 ms·

Thanks for the links! I have two replies for this: (1) I would like to implement a type inferencer in Prolog and (2) This doesn't justify what you originally s

by chubot 8y ago

Thanks for the links! I have two replies for this: (1) I would like to implement a type inferencer in Prolog and (2) This doesn't justify what you originally said (but we don't have to argue that point. I appreciate the response. :) ) ----- (1) Can you elaborate on what you mean by the type inferencer being identical to the interpreter? I see the type inferencer in Python in joy/utils/types.py. And I see your interpreter in Prolog -- but how does that do type inference? Why am I interested in type inference? I wrote a shell interpreter in 19K lines of Python: http://www.oilshell.org/release/0.6.pre8/metrics.wwz/line-counts/src.txt http://www.oilshell.org/release/0.6.pre8/metrics.wwz/line-co... (scroll to the end for line count) I want to compile it to faster code, and that likely involves type inference in the style of PyPy or ShedSkin (which are both used in production). Background: http://www.oilshell.org/blog/2018/03/04.html http://www.oilshell.org/blog/2018/03/04.html My understanding is that global type inference for 19K lines of code might be out of reach in terms of speed? As far as I know type inference algorithms are exponential in the worst case. While I'm using a relatively small subset of Python, the type system may still be considered rich (classes with single inheritance, __call__, varargs, perhaps typed dictionaries.) Do you think Prolog is feasible for this problem? Does it offer you help in terms of debugging and performance problems? Maybe I need some syntax for explicit annotation so I can "help" the backtracking succeed? I am not exactly sure how it will work. But doing it in Prolog seems somewhat appealing, if I can "prototype" the type system. Though there is the practical problem of simply getting the types into Prolog and back out. I think I would have to generate a prolog program with at least one clause for every variable in my 19K line interpreter? In any case, thanks for the links to your code. I will be looking at these further. ----- (2) A recent comment from someone with considerable expertise says that backtracking search just doesn't come up that often: https://www.reddit.com/r/ProgrammingLanguages/comments/9kb9z5/logic_programming_languages/ https://www.reddit.com/r/ProgrammingLanguages/comments/9kb9z... I seem to recall that Paul didn't just work with Mercury -- he worked on it -- and his Ph.D. work shows that: https://paul.bone.id.au/ https://paul.bone.id.au/ I think type inference is a great example of where it DOES come up. But very few people implement type systems (and production type checkers are often in imperative languages like TypeScript, or occasionally OCaml with Hack). Various types of scheduling may be another place, but I would also count that as a very small proportion of programming work. Not to mention games, network programming, kernels, etc. I believe you're wildly overstating the applicability of Prolog. A program might have small subproblems that could be expressed in Prolog, but the entire program doesn't fit that paradigm. Also, I also asked in that Reddit thread for "production" uses of Prolog, and I don't really see it. Erlang moved away from it for "engineering reasons", and they were one of the biggest advocates (I read Joe Armstrong's paper about prototyping Erlang in Prolog). Rust is maybe moving toward it, but they're probably using their own implementation and not an off-the-shelf Prolog interpreter. I think Prolog ironically falls in the category as Forth (and Joy is not even as practical as Forth). It's incredibly expressive for some things, and it has generated many epiphanies. But if you try to use it in production, you eventually "fall off a cliff" for parts of the program that don't fit the model. I experimented with both Forth and Joy a number of years ago, and have Manfred von Thun's papers printed out, sitting on my bookshelf. The quadratic formula was one small example of things that are awkward in stack languages, but I think there are others on a larger, architectural scale that are "dealbreakers". The conclusion I came to about Forth/Joy was that they're worth learning but there's a reason they aren't used much in production. I will probably end feeling the same way about logic programming (like Paul does after 10 years of deep experience), but I still want to learn it for the reasons everyone says.

nickpsecurity 8y ago
"I think Prolog ironically falls in the category as Forth (and Joy is not even as practical as Forth). It's incredibly expressive for some things, and it has generated many epiphanies. But if you try to use it in production, you eventually "fall off a cliff" for parts of the program that don't fit the model." I believe that's correct. It's why AI research usually used LISP with Prolog handling specific things it's good at. Often as a DSL, too. A good example which still sells is Allegro CL: https://franz.com/products/allegro-common-lisp/ https://franz.com/products/allegro-common-lisp/ On Prolog itself, there are commercial users outside AI/rules/NLP like this finance company: https://dtai.cs.kuleuven.be/CHR/files/Elston_SecuritEase.pdf https://dtai.cs.kuleuven.be/CHR/files/Elston_SecuritEase.pdf Far as efficiencies, most Prologs appear to be based on abstract machines that weren't quite optimized for real hardware. Whereas, Aquarius Prolog that Peter Van Roy posted here once seemed to show there's a lot of efficiency to be gained with optimized-for-metal designs: https://www.researchgate.net/publication/2813183_The_Making_of_the_Aquarius_Prolog_System https://www.researchgate.net/publication/2813183_The_Making_... So, that's just a few things I have. I never learned Prolog since I think it's too limited. There's quite a few systems that make tasks easy to express, with Prolog being one. I think ideal system would combine high-efficiency in base language, metaprogramming features (or term-rewriting logics), contracts (esp for automated analysis and testing), stuff like Prolog in DSL form, functional programming like Haskell/Mercury, and so on. All designed to interoperate well with C ecosystem and/or using assembly for optimized modules. General idea is you can always use the right tool for the job with base language integrating them smoothly in a way that maximizes productivity during development and performance during deployment.
carapace 8y ago
Ah! Oilshell, I knew there was a reason I remembered your username. :) I want to preface everything below by pointing out that, while I've been programming for about a quarter of a century, I've been programming in Prolog for about a quarter of a year. It's entirely likely that I haven't encountered the downsides of Prolog in an appreciable way yet. ;-) Now that I've admitted my ignorance, I'll proceed to pontificate in the traditions of this fine forum. ;-D > Can you elaborate on what you mean by the type inferencer being identical to the interpreter? I see the type inferencer in Python in joy/utils/types.py. And I see your interpreter in Prolog -- but how does that do type inference? Um, I can describe what happened. I wrote the Prolog interpreter then I wrote the type inferencer. Reviewing them afterward, I realized that I could rearrange the inferencer code a little bit and to make it identical to the interpreter code. So I deleted it. This is something I discovered, not something I planned. Basically, Prolog already does what the Python inferencer code does. If you give it logical variables instead of actual stack structures it deduces what they would be, for example: ?- thun([dup, *], StackIn, StackOut). StackIn = [_9846|_9848], StackOut = [_9864|_9848], _9846^2#=_9864, _9864 in 0..sup . This shows that the input stack has (at least) one item, which will be replaced by its square, which also implies that the result is between zero and "supremum" i.e. it's positive. > I want to compile it to faster code, and that likely involves type inference in the style of PyPy or ShedSkin (which are both used in production). So you want type inference for the Python code? Look for PySonar (you'll have to dig for it, the creator took it down for some reason but copies and forks are floating around.) It's a pretty sophisticated analyzer that can follow Python's dynamical nature. But if your main goal is just faster performance for your Python code (as opposed to a type inferencer for Oilshell code, which is what I thought you were talking about at first) I would try Cython. That said, yes, in my limited experience Prolog would be great for this. (I love Python FWIW but personally I would hate to try to type it even using Prolog.) > I think I would have to generate a prolog program with at least one clause for every variable in my 19K line interpreter? Oh no, you'd build a kind of symbol table as you go, I'd expect. I'll try to rustle up some references for you tomorrow. I know I've seen some. > A recent comment from someone with considerable expertise says that backtracking search just doesn't come up that often: But it's trivial to implement a meta-interpreter to use other search strategies. I took a look a Mercury (and a ton of other systems, there are dozens of variations and hybrids) but I'm sticking to ISO Prolog as much as possible for now. One of the fascinating things about Prolog is how incredibly simple it is (compared to other programming languages.) I want to take it as far as I can until I'm forced to use something additional by some real-world constraint. (I've got reddit blocked in my hosts file, it's too late tonight but I'll unblock it and read the thread you mentioned tomorrow.) You mention type inference and scheduling, ... > Not to mention games, network programming, kernels, etc. I believe you're wildly overstating the applicability of Prolog. A program might have small subproblems that could be expressed in Prolog, but the entire program doesn't fit that paradigm. Here's the thing about that: I'm coming to Prolog from a context of implementing a Joy interpreter and compiler; I'm working with Joy because it provides a very elegant language/notation for deriving programs (in the mathy Functional Programming way.) My ultimate goal is a system that generates provably-correct machine code (but that's also a lot simpler than the existing toolchains for that purpose.) Along comes this paper on using Prolog to write compilers and it's sooooo good. It's also just the beginning. Folks kept working: "Parsing and Compiling Using Prolog" Jacques Cohen and Timothy J. Hickey "Provably Correct Code Generation: A Case Study" Qian Wang, Gopal Gupta "From Programs to Object Code and back again using Logic Programming: Compilation and Decompilation" Jonathan Peter Bowen "Automatic Derivation of Code Generators from Machine Descriptions" R. G. G. Cattell Etc... So now I have Prolog, with an embedded Joy interpreter, and in a minute I'll have the compiler. My strong hunch is that this combo will be a big win. I think the pattern will be inverted: most of a given program can be specified in Prolog(-ish) with Joy to handle nitty-gritty stuff that just doesn't fit well in the Logical Paradigm. For things that really don't fit Prolog nor Joy, well, libraries and extensions. Prolog can load shared libs. With out going into detail, I should mention that Alan Kay's VPRI "Desktop to the metal in 20,000 LOC" STEPS research project makes extensive use of OMeta parsers, and Prolog DCGs are similar but more powerful. Also, "Compiling to categories" Conal Elliott http://conal.net/papers/compiling-to-categories/ http://conal.net/papers/compiling-to-categories/ Prolog+Joy makes this really easy... > The quadratic formula was one small example of things that are awkward in stack languages You're talking about "The annoying quadratic formula" article[1]? What do you think of this derivation[2]? [1] http://www.kevinalbrecht.com/code/joy-mirror/jp-quadratic.html http://www.kevinalbrecht.com/code/joy-mirror/jp-quadratic.ht... [2] http://joypy.osdn.io/notebooks/Quadratic.html http://joypy.osdn.io/notebooks/Quadratic.html Cheers!

by chubot 8y ago

nickpsecurity 8y ago

"I think Prolog ironically falls in the category as Forth (and Joy is not even as practical as Forth). It's incredibly expressive for some things, and it has generated many epiphanies. But if you try to use it in production, you eventually "fall off a cliff" for parts of the program that don't fit the model." I believe that's correct. It's why AI research usually used LISP with Prolog handling specific things it's good at. Often as a DSL, too. A good example which still sells is Allegro CL: https://franz.com/products/allegro-common-lisp/ https://franz.com/products/allegro-common-lisp/ On Prolog itself, there are commercial users outside AI/rules/NLP like this finance company: https://dtai.cs.kuleuven.be/CHR/files/Elston_SecuritEase.pdf https://dtai.cs.kuleuven.be/CHR/files/Elston_SecuritEase.pdf Far as efficiencies, most Prologs appear to be based on abstract machines that weren't quite optimized for real hardware. Whereas, Aquarius Prolog that Peter Van Roy posted here once seemed to show there's a lot of efficiency to be gained with optimized-for-metal designs: https://www.researchgate.net/publication/2813183_The_Making_of_the_Aquarius_Prolog_System https://www.researchgate.net/publication/2813183_The_Making_... So, that's just a few things I have. I never learned Prolog since I think it's too limited. There's quite a few systems that make tasks easy to express, with Prolog being one. I think ideal system would combine high-efficiency in base language, metaprogramming features (or term-rewriting logics), contracts (esp for automated analysis and testing), stuff like Prolog in DSL form, functional programming like Haskell/Mercury, and so on. All designed to interoperate well with C ecosystem and/or using assembly for optimized modules. General idea is you can always use the right tool for the job with base language integrating them smoothly in a way that maximizes productivity during development and performance during deployment.

carapace 8y ago

Ah! Oilshell, I knew there was a reason I remembered your username. :) I want to preface everything below by pointing out that, while I've been programming for about a quarter of a century, I've been programming in Prolog for about a quarter of a year. It's entirely likely that I haven't encountered the downsides of Prolog in an appreciable way yet. ;-) Now that I've admitted my ignorance, I'll proceed to pontificate in the traditions of this fine forum. ;-D > Can you elaborate on what you mean by the type inferencer being identical to the interpreter? I see the type inferencer in Python in joy/utils/types.py. And I see your interpreter in Prolog -- but how does that do type inference? Um, I can describe what happened. I wrote the Prolog interpreter then I wrote the type inferencer. Reviewing them afterward, I realized that I could rearrange the inferencer code a little bit and to make it identical to the interpreter code. So I deleted it. This is something I discovered, not something I planned. Basically, Prolog already does what the Python inferencer code does. If you give it logical variables instead of actual stack structures it deduces what they would be, for example: ?- thun([dup, *], StackIn, StackOut). StackIn = [_9846|_9848], StackOut = [_9864|_9848], _9846^2#=_9864, _9864 in 0..sup . This shows that the input stack has (at least) one item, which will be replaced by its square, which also implies that the result is between zero and "supremum" i.e. it's positive. > I want to compile it to faster code, and that likely involves type inference in the style of PyPy or ShedSkin (which are both used in production). So you want type inference for the Python code? Look for PySonar (you'll have to dig for it, the creator took it down for some reason but copies and forks are floating around.) It's a pretty sophisticated analyzer that can follow Python's dynamical nature. But if your main goal is just faster performance for your Python code (as opposed to a type inferencer for Oilshell code, which is what I thought you were talking about at first) I would try Cython. That said, yes, in my limited experience Prolog would be great for this. (I love Python FWIW but personally I would hate to try to type it even using Prolog.) > I think I would have to generate a prolog program with at least one clause for every variable in my 19K line interpreter? Oh no, you'd build a kind of symbol table as you go, I'd expect. I'll try to rustle up some references for you tomorrow. I know I've seen some. > A recent comment from someone with considerable expertise says that backtracking search just doesn't come up that often: But it's trivial to implement a meta-interpreter to use other search strategies. I took a look a Mercury (and a ton of other systems, there are dozens of variations and hybrids) but I'm sticking to ISO Prolog as much as possible for now. One of the fascinating things about Prolog is how incredibly simple it is (compared to other programming languages.) I want to take it as far as I can until I'm forced to use something additional by some real-world constraint. (I've got reddit blocked in my hosts file, it's too late tonight but I'll unblock it and read the thread you mentioned tomorrow.) You mention type inference and scheduling, ... > Not to mention games, network programming, kernels, etc. I believe you're wildly overstating the applicability of Prolog. A program might have small subproblems that could be expressed in Prolog, but the entire program doesn't fit that paradigm. Here's the thing about that: I'm coming to Prolog from a context of implementing a Joy interpreter and compiler; I'm working with Joy because it provides a very elegant language/notation for deriving programs (in the mathy Functional Programming way.) My ultimate goal is a system that generates provably-correct machine code (but that's also a lot simpler than the existing toolchains for that purpose.) Along comes this paper on using Prolog to write compilers and it's sooooo good. It's also just the beginning. Folks kept working: "Parsing and Compiling Using Prolog" Jacques Cohen and Timothy J. Hickey "Provably Correct Code Generation: A Case Study" Qian Wang, Gopal Gupta "From Programs to Object Code and back again using Logic Programming: Compilation and Decompilation" Jonathan Peter Bowen "Automatic Derivation of Code Generators from Machine Descriptions" R. G. G. Cattell Etc... So now I have Prolog, with an embedded Joy interpreter, and in a minute I'll have the compiler. My strong hunch is that this combo will be a big win. I think the pattern will be inverted: most of a given program can be specified in Prolog(-ish) with Joy to handle nitty-gritty stuff that just doesn't fit well in the Logical Paradigm. For things that really don't fit Prolog nor Joy, well, libraries and extensions. Prolog can load shared libs. With out going into detail, I should mention that Alan Kay's VPRI "Desktop to the metal in 20,000 LOC" STEPS research project makes extensive use of OMeta parsers, and Prolog DCGs are similar but more powerful. Also, "Compiling to categories" Conal Elliott http://conal.net/papers/compiling-to-categories/ http://conal.net/papers/compiling-to-categories/ Prolog+Joy makes this really easy... > The quadratic formula was one small example of things that are awkward in stack languages You're talking about "The annoying quadratic formula" article[1]? What do you think of this derivation[2]? [1] http://www.kevinalbrecht.com/code/joy-mirror/jp-quadratic.html http://www.kevinalbrecht.com/code/joy-mirror/jp-quadratic.ht... [2] http://joypy.osdn.io/notebooks/Quadratic.html http://joypy.osdn.io/notebooks/Quadratic.html Cheers!