4 ms·

Very intriguing! Is there an explanation anywhere of how this is different from Prolog? It seems like almost the same thing. That is not a criticism BTW, I love

by grose 4y ago

Very intriguing! Is there an explanation anywhere of how this is different from Prolog? It seems like almost the same thing. That is not a criticism BTW, I love Prolog. From what I can tell the main difference is it has functions with return values. It also looks like it has different semantics for the choice points, letting you nest alternatives in arguments and other expressions. I do like how choice points are seen as a more natural building block in the language vs. the 'magical' bagof in Prolog. For games, having real indexable arrays will be nice as well. % Verse: x:=(1|7|2); x+1 % Prolog: foo(X, Y) :- (X = 1 ; X = 7 ; X = 2), Y is X + 1. I think it might be nice to implement this language using Prolog. For example I think you could do the type definitions like this (let's ignore how :/2 is usually for module qualification): X:int :- freeze(X, integer(X)). Kind of off-topic but I've always been curious why variable attributes aren't generally used for type-checking like this in Prolog. Anyway, very cool. I'll be keeping an eye on it. Is Epic Games hiring logic programmers? :)

pbazant 4y ago
I was thinking the same! I love Prolog, but maybe Verse will turn out to be an actually better, cleaned-up Prolog? Implementing Verse in Prolog would be so much fun and very natural.
gergo_barany 4y ago
This definitely isn't Prolog, but in some ways it seems to be closer to Prolog than some other things. One thing you can do in Prolog is build partial data structures: `X = tree(Left, Right)` builds a tree node with two "holes" `Left` and `Right` that you can fill in later -- or, crucially, might choose not to fill in. You can pass this "partial" data structure around, and other parts of the program may or may not instantiate it further. This allows some nice programming tricks. It allows proper tail calls in cases where functional programming doesn't allow tail calls, or only with heroic help from the compiler. It allows you to decompose your program in different ways from languages where you must always build data structures "inside out". In contrast, Mercury is a syntactically Prolog-like language that doesn't allow this: (AFAIK) when you pass a term to a predicate, it must either be ground, i.e., without any leftover "holes", or a variable, i.e., completely uninstantiated. This throws away much of the power and convenience of Prolog. And any language that takes a pure "Prolog's logic variables are just sequence generators" approach must also fall into this category. Verse seems to be more lenient in the "it's all just sequences" department. You can pass uninstantiated stuff into functions and have it further instantiated in there. It's not clear to me to what extent this works, there are no examples with data structures in the slides and I haven't gone through the paper yet. I can well imagine this being closer to Prolog than to Mercury. But the "Everything is eventually evaluated" is definitely not fully Prolog-like; Prolog doesn't care about everything eventually being ground. There is no need for that. On a related note, even though it's popular to say that Prolog can "run code backwards", that is in fact not the case at all. Prolog always runs your code forwards. If your code is designed accordingly, you can often treat an argument `X` as an input and an argument `Y` as an output, and also have a use case of the same code where `Y` is an input and `X` is an output. But the code itself always runs in a well-defined top-to-bottom, left-to-right way. This is notably different in Mercury, where the compiler will explicitly compile different versions of your code for different use cases, reordering things so that sometimes you are actually running bottom-to-top when compared with the source code order. Evaluation order in Verse is... all over the place. I suspect this will be problematic in practice. If you understand how Prolog evaluates your code, you can work with it to write performant code. Verse seems to be too flexible in this regard, so that it will be difficult to impossible to understand what is actually going on in what order. If you treat all your values as generators that can start enumerating stuff at any point, it will be very easy to have cases of combinatorial explosion by choosing wrong orderings. I see that there are some notes on this in the paper, but not much more than "some things are obviously not what we want, but we don't know what exactly we want". So let's see what happens, but for now this doesn't seem to want to be close to Prolog. Final syntactic notes: Mercury has the Prolog-like predicate syntax that as noted can run "backwards". It also has a functional syntax where (AFAIK) it's not possible to run "backwards". This seems to be the right choice to me. You can mix and match predicates and functions to build what you want and retain clarity. Using a function syntax for things that can run "backwards" will be cute but confusing. Relations should be written as relations IMHO. As for micro-syntax, others have complained about `fst` and `snd`, and I also tend to think that we can afford a few more bytes. But my main complaint is with `false?`. If in the slides introducing your syntax you feel compelled to call something "quirky", that's a clear indication that it should change. It's such a weird name. Why the question mark? Why does the name evoke booleans if the language has no booleans and discourages boolean thinking? If I'm supposed to think in terms of sequences, a better way for a sequence that contains nothing would be `none`. If I'm supposed to think in terms of logic variables, a better name for a logic variable that is bound to no value is... also `none`. The name `false` is just such a surprisingly bad fit. This is something to watch, it's an interesting point in the design space. It might end up as something that (finally) is better than Prolog. It won't end up as being "almost the same thing" though, I don't think.
- haliq 4y ago
  I think false is sugar for the empty tuple / array. `?` is an operator that turns tuples / arrays back into choices. Thus `false?` can be seen as an expression that returns no values, which is semantically falsy in the language.
  - gergo_barany 4y ago
    Ah, that makes sense. Thanks! It should still not be the default name for this construct.
- grose 4y ago
  Thank you for the detailed explanation, much appreciated.
bodhiandphysics 4y ago
Major differences from Prolog seem to be as follows: Prolog always evaluates through unification (at least in theory). Verse is evaluated through reduction, including the unifications! This means a). there is a sublanguage in verse that doesn't do unification at all... it should have similar performance to a functional programming language like Haskell. b) verse is deterministic... the same prolog programs can at least theoretically produce two different answers to the same input. Verse has a defined denotational semantics (prolog has most of a defined operational semantics, but that's a different kind of thing). c). Verse an be type checked at compile time! It seems typechecking verse is undecidable, so presumably some type checks will be moved to run time, but lots of type checking can be done at compile time.
- gergo_barany 4y ago
  > Prolog always evaluates through unification (at least in theory). What do you mean? The actual "computational" part of Prolog lies more in resolution than in unification. Unification does not "evaluate" in any sense of the word I'm familiar with. > the same prolog programs can at least theoretically produce two different answers to the same input. What do you mean? Do you mean through side effects, or are you suggesting that Prolog's evaluation order or something else is not fully specified and deterministic? You would be wrong about the latter. EDIT: > Verse has a defined denotational semantics What do you mean? Verse (or rather the underlying calculus VC) has a rewrite semantics. Rewriting is pretty operational and not at all denotational.

by grose 4y ago

pbazant 4y ago

I was thinking the same! I love Prolog, but maybe Verse will turn out to be an actually better, cleaned-up Prolog? Implementing Verse in Prolog would be so much fun and very natural.

gergo_barany 4y ago

This definitely isn't Prolog, but in some ways it seems to be closer to Prolog than some other things. One thing you can do in Prolog is build partial data structures: `X = tree(Left, Right)` builds a tree node with two "holes" `Left` and `Right` that you can fill in later -- or, crucially, might choose not to fill in. You can pass this "partial" data structure around, and other parts of the program may or may not instantiate it further. This allows some nice programming tricks. It allows proper tail calls in cases where functional programming doesn't allow tail calls, or only with heroic help from the compiler. It allows you to decompose your program in different ways from languages where you must always build data structures "inside out". In contrast, Mercury is a syntactically Prolog-like language that doesn't allow this: (AFAIK) when you pass a term to a predicate, it must either be ground, i.e., without any leftover "holes", or a variable, i.e., completely uninstantiated. This throws away much of the power and convenience of Prolog. And any language that takes a pure "Prolog's logic variables are just sequence generators" approach must also fall into this category. Verse seems to be more lenient in the "it's all just sequences" department. You can pass uninstantiated stuff into functions and have it further instantiated in there. It's not clear to me to what extent this works, there are no examples with data structures in the slides and I haven't gone through the paper yet. I can well imagine this being closer to Prolog than to Mercury. But the "Everything is eventually evaluated" is definitely not fully Prolog-like; Prolog doesn't care about everything eventually being ground. There is no need for that. On a related note, even though it's popular to say that Prolog can "run code backwards", that is in fact not the case at all. Prolog always runs your code forwards. If your code is designed accordingly, you can often treat an argument `X` as an input and an argument `Y` as an output, and also have a use case of the same code where `Y` is an input and `X` is an output. But the code itself always runs in a well-defined top-to-bottom, left-to-right way. This is notably different in Mercury, where the compiler will explicitly compile different versions of your code for different use cases, reordering things so that sometimes you are actually running bottom-to-top when compared with the source code order. Evaluation order in Verse is... all over the place. I suspect this will be problematic in practice. If you understand how Prolog evaluates your code, you can work with it to write performant code. Verse seems to be too flexible in this regard, so that it will be difficult to impossible to understand what is actually going on in what order. If you treat all your values as generators that can start enumerating stuff at any point, it will be very easy to have cases of combinatorial explosion by choosing wrong orderings. I see that there are some notes on this in the paper, but not much more than "some things are obviously not what we want, but we don't know what exactly we want". So let's see what happens, but for now this doesn't seem to want to be close to Prolog. Final syntactic notes: Mercury has the Prolog-like predicate syntax that as noted can run "backwards". It also has a functional syntax where (AFAIK) it's not possible to run "backwards". This seems to be the right choice to me. You can mix and match predicates and functions to build what you want and retain clarity. Using a function syntax for things that can run "backwards" will be cute but confusing. Relations should be written as relations IMHO. As for micro-syntax, others have complained about `fst` and `snd`, and I also tend to think that we can afford a few more bytes. But my main complaint is with `false?`. If in the slides introducing your syntax you feel compelled to call something "quirky", that's a clear indication that it should change. It's such a weird name. Why the question mark? Why does the name evoke booleans if the language has no booleans and discourages boolean thinking? If I'm supposed to think in terms of sequences, a better way for a sequence that contains nothing would be `none`. If I'm supposed to think in terms of logic variables, a better name for a logic variable that is bound to no value is... also `none`. The name `false` is just such a surprisingly bad fit. This is something to watch, it's an interesting point in the design space. It might end up as something that (finally) is better than Prolog. It won't end up as being "almost the same thing" though, I don't think.

haliq 4y ago
I think false is sugar for the empty tuple / array. `?` is an operator that turns tuples / arrays back into choices. Thus `false?` can be seen as an expression that returns no values, which is semantically falsy in the language.
- gergo_barany 4y ago
  Ah, that makes sense. Thanks! It should still not be the default name for this construct.
grose 4y ago
Thank you for the detailed explanation, much appreciated.

bodhiandphysics 4y ago

Major differences from Prolog seem to be as follows: Prolog always evaluates through unification (at least in theory). Verse is evaluated through reduction, including the unifications! This means a). there is a sublanguage in verse that doesn't do unification at all... it should have similar performance to a functional programming language like Haskell. b) verse is deterministic... the same prolog programs can at least theoretically produce two different answers to the same input. Verse has a defined denotational semantics (prolog has most of a defined operational semantics, but that's a different kind of thing). c). Verse an be type checked at compile time! It seems typechecking verse is undecidable, so presumably some type checks will be moved to run time, but lots of type checking can be done at compile time.

gergo_barany 4y ago
> Prolog always evaluates through unification (at least in theory). What do you mean? The actual "computational" part of Prolog lies more in resolution than in unification. Unification does not "evaluate" in any sense of the word I'm familiar with. > the same prolog programs can at least theoretically produce two different answers to the same input. What do you mean? Do you mean through side effects, or are you suggesting that Prolog's evaluation order or something else is not fully specified and deterministic? You would be wrong about the latter. EDIT: > Verse has a defined denotational semantics What do you mean? Verse (or rather the underlying calculus VC) has a rewrite semantics. Rewriting is pretty operational and not at all denotational.