[HN Gopher] I'm not mutable, I'm partially instantiated
___________________________________________________________________
I'm not mutable, I'm partially instantiated
Author : tlack
Score : 146 points
Date : 2024-11-07 03:17 UTC (19 hours ago)
(HTM) web link (blog.dnmfarrell.com)
(TXT) w3m dump (blog.dnmfarrell.com)
| lelag wrote:
| I've noticed quite a lot of Prolog content lately. I don't know
| if it's just a case of the Baader-Meinhof phenomenon, but it
| looks to me that recent article[1] about Prolog being able to
| improve LLM reasoning abilities renewed some interest in the
| language.
|
| [1] https://shchegrikovich.substack.com/p/use-prolog-to-
| improve-...
| worldsayshi wrote:
| Here's the hacker news post:
| https://news.ycombinator.com/item?id=41831735
| dang wrote:
| Thanks! Macroexpanded:
|
| _Use Prolog to improve LLM 's reasoning_ -
| https://news.ycombinator.com/item?id=41831735 - Oct 2024 (155
| comments)
| weinzierl wrote:
| Which is strange considering how old and limited Prolog in a
| sense is. I wonder why no superset ever gained traction and
| what it would look like. I imagine it fitting somewhere in the
| hierarchy
|
| Theorem Prover [?] SMT Solver [?] SAT Solver
|
| since
|
| Theorem Prover [?] Prolog
| Byamarro wrote:
| Learning curve perhaps? There doesn't have to be an overlap
| between people working on this and the tools you have
| mentioned
| knome wrote:
| limited in what sense?
|
| prolog is turing complete.
| Epa095 wrote:
| He might be thinking about the SLDNF resolution happening.
| But yes, you can implement any prover in prolog. This
| distinction is discussed a bit here:
| https://www.metalevel.at/prolog/theoremproving
| sixfiveotwo wrote:
| Indeed, you can get a lot more from dependent types than
| Damas-Hindley-Milner inference, yet does it mean that you
| should use the former everywhere?
| Epa095 wrote:
| The post in OP has the following hyphothesis:
|
| > Why Prolog? [...] Due to it's declarative nature it might
| be a bit easier for LLMs to generate code, because LLM
| doesn't need to generate precise control flow.
|
| This is an interesting point, and my guess is that prolog is
| the declarative programming language with most example code
| out there for it to learn on(excluding SQL). Alternatively it
| could try to create some problem description for an automated
| theorem prover. My (absolute ignorant) guess is that the
| prolog aproach works better for two reasons:
|
| - The amount of prolog code in the training set is higher
|
| - It is still only able to create code for problems easy
| enough that prolog can handle them.
| dsabanin wrote:
| Another attractive feature of Prolog is that it's homoiconic,
| like lisp.
| p4bl0 wrote:
| I don't get where the `-` comes from in `key-value` result lines
| after the "refactoring" title. I feel like it should stay a `,`
| like at the beginning. Can someone more knowledgeable in Prolog
| explain that? Is that because of an hidden use of this `to_list`
| predicate that comes later in the post?
| JadeNB wrote:
| (The initial version of this comment missed the point of your
| question; sorry.) The author says:
|
| > We also store pairs as the pair type (Key-Value), instead of
| two separate values. This makes easy to serialize a dictionary
| into a list of pairs, which are sortable using the builtin
| keysort/2.
|
| `Key, Value` is two values, not one. I suspect something like
| `kv(Key, Value)` would work as well.
|
| By the way, I disagree that the refactored version doesn't cut;
| `-> ;` is syntactic sugar over a cut.
| danieldk wrote:
| Operators like _-_ are just an infix functor for a Prolog term
| with arity 2: ?- functor(123-"foo", Name,
| Arity, Type). Name = (-), Arity = 2,
| Type = compound. ?- 1-"foo" = '-'(1,"foo").
| true.
|
| Functors like _-_ only become arithmetic in combination with
| _is_ : ?- A is '-'(42, 1). A = 41.
| ?- A is 42 - 1. A = 41.
| tannhaeuser wrote:
| It's purely a convention to use terms of the form "key - value"
| for 2-tuples here (or '-'(key, value) in funtional/canonical
| notation which can be used as well). minus is just used because
| it's already predeclared as an infix operator, and indeed
| ','(key, value) could be used as well but comma is also used as
| argument separator and for conjunctions in clause bodies and
| thus tends to be avoided. You also can see '=' being used for
| the same thing eg. [ key = value, ...]
|
| (for example, as used for representing attributes by SGML/XML
| parsing libs for SWI, Quintus/SICStus, and others), not to be
| confused with '=' being interpreted as unification operation in
| goals/clause bodies.
|
| If you think about it, the simplest convention in Prolog to
| represent "assignment" of a value to a symbol (not a variable)
| would be key(value).
|
| That is, to use the "key" atom as functor itself, rather than
| use functors/operators in ad-hoc ways. This is exactly what
| Quantum Prolog can do (optionally, and in addition to ISO
| Prolog's conventions).
|
| Specifically, if you have a list of fact-like terms
| L = [ p(1), q(2), r(what(ever)) ]
|
| then Quantum Prolog can answer queries against such term list,
| just like answering against the global default database eg.
| call(L ?- q(X))
|
| binds X = 2
|
| and would also bind additional values for q(X) on backtracking
| if the term list contained any. This is a natural extension to
| regular querying in Prolog because a term list [a, b] in
| Prolog's square bracket notation is just syntactic sugar for
| using the dot operator '.'(a, '.'(b, []))
|
| and a Prolog program is syntactically just a list of clause
| terms.
|
| In the container planning demo on the Quantum Prolog site [1],
| this feature is used for backtracking over (un)loading and
| travelling actions which would normally change state via
| destructive assert and retract calls and hence not allow
| backtracking to search for optimal sequences of actions.
|
| [1]: https://quantumprolog.sgml.net/container-planning-
| demo/part2...
| YeGoblynQueenne wrote:
| There's no -/2 operator in the initial definition of lookup/3
| though: lookup(Key, dict(Key,X,Left,Right),
| Value) :- ! ,X=Value. lookup(Key,
| dict(Keyl,X,Left,Right), Value) :- Key < Keyl
| ,lookup(Key,Left,Value). lookup(Key,
| dict(Keyl,X,Left,Right), Value) :- Key > Keyl
| ,lookup(Key,Right,Value).
|
| You can also see that in the first call to lookup/3 where
| there's no -/2.
|
| If I understand correctly, that's what the OP is asking:
| Where did the -/2 come from, not what it's for.
|
| The call with the -/2 is under the heading "Refactoring the
| dictionary" so it's possible the author mixed up the
| implementations while writing the article and listed the
| output of an implementation that represents key-value pairs
| as -/2 terms.
|
| The refactored version makes more sense btw and indeed I see
| the author switches to K-V later on in the article.
| jfmc wrote:
| A classic library, you can play with it here: https://ciao-
| lang.org/playground/#https://github.com/ciao-la...
| anfelor wrote:
| Partially instantiated data structures are also available in
| Haskell (via Laziness), in OCaml (via tail modulo cons,
| https://inria.hal.science/hal-03146495/document) and Koka (via
| constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398)
| bmacho wrote:
| I don't think Haskell _can_ do this, can have a growable linked
| list for example. 'last a' is 'last a', regardless what is
| between them (modulo shadowing and such).
|
| And I suspect that Prolog's Partial Instantiation is, while not
| mutating data, but it is mutating references somewhere
| skybrian wrote:
| Haskell has cyclic data structures, which also can't be
| implemented without a mutable reference somewhere, though it
| may be buried in the implementation.
|
| The difference is being able to define an incomplete data
| structure (with a forward reference) and then defining the
| target of the reference _at runtime._ Most languages will
| complain about an undefined reference if it's not defined by
| the end of a module.
|
| You could do it with soft references, though. Use a symbol or
| string to refer to something and define it later.
| bmacho wrote:
| I rather think the fact the the same symbol/string always
| denotes the same thing is especially helpful for cyclic
| structures.
|
| Anyway I think I misunderstood the article, I thought they
| added things to a dictionary in the prolog repl, which
| would be impossible in haskell/ghci afaik.
| whateveracct wrote:
| Technically, Haskell laziness is just mutability under the
| hood :)
|
| And the "difference list" mentioned in the article is also in
| Haskell - although framed differently (more "functionally")
| type DList a = [a] -> [a] concat :: DList a ->
| DList a -> DList a concat = (.) toList
| :: DList a -> [a] toList d = d []
| fromList :: [a] -> DList a fromList = (++)
| skybrian wrote:
| Also, you can do lazy initialization in any language that has
| functions by passing a getter function around instead of a
| value.
|
| I recently had need for this to implement validation for
| recursive data structures in TypeScript. It depends on support
| for forward references in the body of a function. The tricky
| bit is ensuring that the getter isn't called until the cycle is
| completed by defining the forward reference's target. The type
| system doesn't help; you just have to write the implementation
| so it doesn't call the getter.
| colanderman wrote:
| Laziness and TMC are fundamentally different from partial
| instantiation in that they are implementation details,
| mostly/wholly invisible to the language semantics themselves.
|
| A key aspect of partial instantiation is that the "holes" may
| be filled in by a _semantically unrelated_ piece of code, which
| is not the case for either laziness or TMC (wherein the
| contents data structure must be defined in one place, even if
| the implementation does not evaluate it immediately).
|
| (I don't know Koka so I can't speak to that.)
| anfelor wrote:
| Yes, that is true! Koka's constructor contexts also allow you
| to do this. A constructor context is a data structure with
| exactly one hole which you can fill in with an arbitrary
| value (or even several arbitrary values, copying the
| constructor context in the process).
| openasocket wrote:
| I've never used it in production, but I have a deep love of
| Prolog, just because of how different it is from any other
| programming language I've used. As a programming paradigm, it
| found it as eye-opening as functional programming. What I found
| interesting is that you are operating on logical statements and
| pattern matching, which often means that the same "function" can
| be used for multiple different things. For example:
|
| append([], List, List).
|
| append([Head|Tail], List, [Head|Rest]) :- append(Tail, List,
| Rest).
|
| Is a simple list append function: append(X, Y, Z) is a predicate
| that match if Z is the list of all elements of X, followed by all
| elements of Y. You can use it to concatenate lists, of course.
| But you can also use it to confirm that a particular list start
| with a particular sequence, or ends with a particular sequence!
| The idea that the same predicate can be used in multiple
| different ways is really fascinating to me. I have no idea to
| what extent that would scale in a large system, but it's very
| interesting
| agumonkey wrote:
| Same, I love the bidirectional aspect of relations
| wizzwizz4 wrote:
| It doesn't scale that well because integers are their own,
| opaque thing in Prolog, and the is predicate is unidirectional.
| However, there's no inherent reason this has to be the case:
| you can construct your own representation of the integers from
| the Peano axioms, and recover bidirectionality of addition.
| (You'll want to be using some typed variant of Prolog with the
| "unary tree of units" optimisation, otherwise integers take
| O(n) space in memory, but it's possible in the language.)
| Prolog works how it does, because it's (mostly) backwards-
| compatible with a facts database used for symbolic AI research,
| where all atoms were opaque.
| lmkg wrote:
| Check out the CLP(Z) library by Markus Triska, who is also
| the author of Scryer Prolog. It defines new comparison
| predicates that lets you use bidirectional logical
| programming on standard integers with standard math
| operations.
|
| https://github.com/triska/clpz
| dsabanin wrote:
| Markus is not the author of Scryer Prolog, Mark Thom is.
| ahoka wrote:
| "you can construct your own representation of the integers
| from the Peano axioms"
|
| This is how the Idris prelude defines nat, the type of
| natural numbers (with some magic making it actually fast). I
| think that's very cool.
| rscho wrote:
| There are many ways to recover relational behaviour. Libs
| such as clp(fd) (superseded by clp(Z)), clp(BNR) and others.
| Avshalom wrote:
| BNR notably works with real numbers and non linear
| constraints.
| coliveira wrote:
| Modern Prolog libraries have handled the issues of
| unidirectional integer predicates, so the old ways of
| handling numeric values is not relevant for most problems.
| lynx23 wrote:
| Do you have a suggestion on where to / how to start learning
| Prolog beyond towers-of-hanoi? Prolog is basically the last
| language on my list of things I want to look at, but whenever I
| tried, I failed to find anything practical to do/try.
| dbcurtis wrote:
| Try a rules-based synthesis problem. Prolog style (put
| simplisticly) is to write down what is true about a solution,
| and turn the search engine loose. Prolog is still procedural,
| unfortunately, so practical Prolog requires understanding the
| search algorithm. A suggestion: produce the XY locations of
| the nails for a building-code-compliant nailing pattern for a
| panel of plywood roof sheathing. Allow different stud spacing
| and wind speed zones. This is a small toy problem but will
| channel your thought process toward something Prologgy.
| amock wrote:
| I've enjoyed https://www.metalevel.at/prolog but I'm not a
| Prolog Programmer.
| lynx23 wrote:
| Ah, thanks for the link! I know his YouTube channel, but
| somehow I never realized there is a webpage too!
| coliveira wrote:
| I always thought that pattern matching would be an excellent
| feature for other programming languages, but it seems that it
| hasn't become popular. Many strategies available to Prolog
| could become possible just by the addition of this feature. One
| possible implementation of the idea occurs with C++ templates
| specialized with numerical parameters. It also seems that
| Mathematica provides pattern matching, but I don't use that
| language.
| mananaysiempre wrote:
| Matching of _patterns_ , with only a single occurrence
| allowed for each variable, is fairly popular in languages
| designed in the last two decades, isn't it? A lot of those
| have or at least borrow from ML heritage, and that of course
| places a big emphasis on algebraic types and pattern
| matching. Full-blown unification remains niche, that's true,
| but it's just a fairly heavyweight feature, and I don't
| really know how you'd integrate it without turning your
| language into (a superset of) Prolog.
| harrisi wrote:
| Erlang, Elixir, Swift, Rust, Python, probably some others.
|
| That list is roughly in order of how capable and useful the
| pattern matching is in each of those languages. Erlang was
| originally written in Prolog.
|
| Also, I definitely agree it's a feature I miss everywhere
| when not using Erlang/Elixir.
| macintux wrote:
| I mostly ignored Python until my job required it, about 8
| years ago. Coming from Erlang, I was pleasantly astonished
| to find that I could use tuple pattern matching in function
| headers... until I discovered that was dropped in Python 3
| and I had been using the mostly-dead version 2 runtime.
| harrisi wrote:
| I think I'd call this destructuring, as opposed to
| patterns and matches, and Python still does it, just not
| in the function head.
|
| I do wish they went the opposite direction and made the
| feature better instead of keeping it as a weird
| assignment thing in the body. The match statement is a
| similarly unfortunate solution, in my opinion.
|
| Oh well. :)
| samweb3 wrote:
| I am actually working on a logical query language that's a
| successor to prolog here: https://memelang.net/02/. Any feedback
| appreciated!
| wizzwizz4 wrote:
| It might be worth using standard vocabulary. For example:
|
| > Reciprocal relations are their own inverse.
|
| The usual word for this is "symmetric".
|
| > Recursive relations can be chained to themselves infinitely.
| For example, "my ancestor's ancestor is also my ancestor."
|
| The usual word for this is "transitive".
|
| A reflexive, symmetric, transitive relation is called an
| "equivalence relation", and it can be used much like equality.
| It'd be nice if your language had support for this, though I
| don't immediately see how to add it.
| simplify wrote:
| Alternative would be interesting, but successor is thought
| provoking. Do you mean to say most all Prolog capabilities will
| be possible to do in Meme?
| samweb3 wrote:
| That's the goal, but please let me know if there's anything
| you find that you can't do.
| shawa_a_a wrote:
| It's a bold statement to call something a Prolog successor! Are
| you aiming for a general purpose logic programming language
| like Prolog, or targeting the use case of querying knowledge
| bases?
|
| One of the draws to Prolog is its immensely simple syntax:
| A.R:B = true in your case would be represented as simply r(A,
| B).
|
| It looks like you've elevated some set theory properties to
| syntax, and have added some neat sugar over chained relations.
| Have you found areas where this really shines as compared to
| writing more standard Prolog/Datalog queries? I'm afraid I
| couldn't see many examples on first look at your Github.
| tolerance wrote:
| This is philosophically intriguing.
| bedobi wrote:
| Partial instantiation is cool and all, but tbh I prefer just
| capturing the initial incomplete attributes in one complete
| record, pass that around, and then instantiate the real thing
| when you have all attributes data class
| IncompletePerson(val name: String) data class
| Person( val name: String, val email: String
| )
|
| or data class Person( val
| initialAttributes: IncompletePerson, val email: String
| )
|
| if you want to nest it.
|
| if you're the type to instead do this data
| class Person( val name: String, val email:
| String? )
|
| I never want to work with your code. Now, there's no
| disambiguation between the complete object and the incomplete
| one, I always have to check before doing anything with it, and
| people will inevitably try send an incomplete object someplace
| that can't handle it and generate bugs.
| skybrian wrote:
| How would you define a cyclic data structure?
| skybrian wrote:
| It seems like whether this represents a mutable or immutable data
| structure depends on the operations you allow. If polling with
| nonvar() is allowed, couldn't you see variables mutate as you do
| more unification? But if it's not allowed, I guess you get a
| variable to be defined later?
|
| Compare with a Promise. If you can check whether it resolved, you
| can see it mutate. If the only operation allowed is to await it
| then from the code's point of view, it might be considered an
| immutable reference to the pending result.
| colanderman wrote:
| Yes, `nonvar/1` is considered "extralogical", in that it can be
| used to observe these side effects. If one sticks to "pure"
| logical operations (which unintuitively excludes `\\+`
| negation) they are not observable.
| ks2048 wrote:
| Is "The Art of Prolog" a good place to start with the lanugage?
___________________________________________________________________
(page generated 2024-11-07 23:00 UTC)