https://kotlinlang.org logo
Title
m

Maxim Kizub

10/15/2019, 7:49 AM
Hello everyone. I've created a feature request to add logical programming paradigm to Kotling. https://youtrack.jetbrains.com/issue/KT-34350?project=kt , can you comment on this proposal?
x

Xavier F. Gouchet

10/15/2019, 7:55 AM
From your example, I'm not sure what more is needed in Kotlin to achieve the same thing ? 🤔 A rule is simply a
fun
that returns a Boolean, which can easily be written without needing changes in the language. Do you have an example of something that cannot be done with Kotlin that could be done with this new paradigm ?
m

Maxim Kizub

10/15/2019, 7:59 AM
I'm not sure I understand your point. Can you write an equivalent Kotlin code?
x

Xavier F. Gouchet

10/15/2019, 8:02 AM
rule isColor(String@ c) {
	c @= colors
;	c ?= "magenta"
;	c.startsWith('#'),
	{	c.length() == 4
	;	c.length() == 7
	}
}
Becomes
val colors = listOf("red", "orange", "yellow", "green", "blue", "violet")
fun isColor(c : String) : Boolean {
    return c in colors || c == "magenta" || c.startsWith("#")
}
You can even use an extension :
fun String.isColor() : Boolean = this in colors || this == "magenta" || this.startsWith("#"
m

Maxim Kizub

10/15/2019, 8:04 AM
But I don't see any 'yield' in your code. The 'rule' can search for al possible values.
x

Xavier F. Gouchet

10/15/2019, 8:05 AM
Well then maybe I didn't understand your proposal 😕
The 'rule' can search for al possible values.
What do you mean ?
m

Maxim Kizub

10/15/2019, 8:06 AM
If parameter 'c' is unbound on a first call, the 'rule' will iteratively return all found values for 'colors' on each subsequent call.
String@ c2; while (isColor(c2)) { ... }
x

Xavier F. Gouchet

10/15/2019, 8:09 AM
So this means you make a loop on all possible values that match the rule
You couldn't make it exactly like this but you could still have something similar in kotlin :
interface Rule<T: Any> {
    
    fun matches(value : T) : Boolean
    
    fun generator() : Sequence<T>
}
And you could then write a DSL to combine rules together to achieve the kind of nesting you have with the
c.startsWith('#'),
	{	c.length() == 4
	;	c.length() == 7
	}
m

Maxim Kizub

10/15/2019, 8:13 AM
Right, and what is the body of such class?
For lookup of values you need backtracking.
x

Xavier F. Gouchet

10/15/2019, 8:14 AM
For lookup of values you need backtracking.
What do you mean ?
m

Maxim Kizub

10/15/2019, 8:15 AM
c @= colors, c.length() > 5
x

Xavier F. Gouchet

10/15/2019, 8:16 AM
Do you mean the compiler generates automatically the code to find all possible values ?
m

Maxim Kizub

10/15/2019, 8:16 AM
You find a value from 'colors', then check it, if it does not match - backtrack and try another value.
Compiler generates a state machine, like for 'yield', to save current state, and to continue from it on next call. For logical programming it will also add backtracking into this state machine.
x

Xavier F. Gouchet

10/15/2019, 8:18 AM
c @= colors, c.length() > 5
could be written as
c = colors.filter { it.length > 5 }.firstOrNull()
no need of backtracking
and likewise if you want to iterate over all possible string matching the rule, you can generate a sequence and keep only the first value matching the predicate.
m

Maxim Kizub

10/15/2019, 8:24 AM
I'm trying to provide simple examples. Not rules for 20-30 lines I had in my real programs. You substitute solution lookup with filtering for this small example, but it does not work in real life.
x

Xavier F. Gouchet

10/15/2019, 8:26 AM
Well I'm trying to understand a use case that can not be done with kotlin currently. Honestly, I think that a logical paradigm could be interesting, but I'm trying to grasp what it can do that can't be done by hand.
m

Maxim Kizub

10/15/2019, 8:35 AM
Everything can be done by hand, in every language, even in assembler. So, why Kotlin has coroutines, they can be programed by hand. It will take 20 times more code and the code will be mostly boilerplate with small inclusions of unique code, but it could be done.
As I wrote in the feature request, I found this logical engine to be very useful. Otherwice I'd not propose it for Kotlin.
x

Xavier F. Gouchet

10/15/2019, 8:37 AM
I'm not saying it can't be useful, and not saying it shouldn't be done. I'm trying to understand the concept, but if I'm bothering you by asking questions I apologise
You have a knowledge on this that spans 20 years and I'm just looking into this, so I'm sorry if I'm not immediately understanding this
m

Maxim Kizub

10/15/2019, 8:39 AM
I referred a few tasks I did using this engine -
I used this integrated logical engine (in the compiler) for name resolution (lookup or types, fields and methods), for parsing (the language had user-defined prefix, postfix and infix operators with priorities, plus postfix operators for types, like WeakReference<> or PVar<>), for type inference and choise of methods (there was multiple-dispatch methods) and so on.
x

Xavier F. Gouchet

10/15/2019, 8:40 AM
Yes I read that but it's hard to understand how it works just by mentioning it.
m

Maxim Kizub

10/15/2019, 8:40 AM
All these tasks have (more or less) complex logic, right?
x

Xavier F. Gouchet

10/15/2019, 8:40 AM
Yes they do
m

Maxim Kizub

10/15/2019, 8:42 AM
So, I was writing code of size a few pages, that replaced (for these tasks) 10-20 times more verbose code. This means I was able to develop and modify the code, not be hited by it's complexity.
Well, yacc/bison parsers do this as well, from small amount of code they do their great work. But difference is that logical parading is not a DSL, it's a paradigm for general programming and can be used in many many areas.
x

Xavier F. Gouchet

10/15/2019, 8:45 AM
Ok this I understand, what I'm not getting is how this magic happens. Say for your color rule you shown. Does the compiler iterate over all possible strings and only keep the one matching the rule ? Or are there some tricks to make this efficient ?
Like how do you actually implement a rule ?
Do you have an exemple of your Kiev language you could show to help understand what you mean ?
m

Maxim Kizub

10/15/2019, 8:51 AM
Well, do you know how 'yield' is implemented? Compiler needs to save current state (save local variables and execution point) and restore the state on next call. For logical rules the compiler will also need to add some code to backtrack, to return to previous states and try another solution, if subsequent check failed.
x

Xavier F. Gouchet

10/15/2019, 8:52 AM
Yes that I understand.
m

Maxim Kizub

10/15/2019, 8:53 AM
Here's a simple rule from my real code, it's simple (I hope, at least it's strightforward describing logical rules as is:
public rule resolveNameR(ResInfo path)
		LVar@ var;
	{
		isInlinedByDispatcherMethod() , $cut, false
	;
		path.getPrevSlotName() == "targs" ||
		path.getPrevSlotName() == "params" ||
		path.getPrevSlotName() == "type_ref" ||
		path.getPrevSlotName() == "dtype_ref",
		$cut,
		path @= targs
	;
		path @= params
	;
		path @= targs
	;
		!this.isStatic() && path.isForwardsAllowed(),
		path.enterForward(path.env.proj.thisPar) : path.leaveForward(path.env.proj.thisPar),
		Env.ctxTDecl(this).getType(path.env).resolveNameAccessR(path)
	;
		path.isForwardsAllowed(),
		var @= params,
		var.isForward(),
		path.enterForward(var) : path.leaveForward(var),
		var.getType(path.env).resolveNameAccessR(path)
	}
It resolves names (symbols) in method. Checks names in type, check names in parameters, check forwarding through 'this' reference. After some nodes vere resolved, it checks if they are accessible (not private, for example).
It's not something you can't write in hand, but it literaly follows 'specs', so it's easier to understand and support.
x

Xavier F. Gouchet

10/15/2019, 8:58 AM
ok
e

elizarov

10/15/2019, 9:28 AM
I don’t think anything needs to be added to the language itself. You can implement back-tracking and logic programming simply as a library using Kotlin language support for coroutines. As an inspiration you can take a look at this parser-combinator library prototype that support backtracking: https://github.com/semoro/kt-parse-combine
m

Maxim Kizub

10/15/2019, 9:46 AM
Right, with support of coroutines and iterators, adding the logical paradigm wiol be easy. That's what I wrote initially. But how your solution (using libraries) will looks like? Closures/lambdas can easily be implemented using inner classes in java, but having a better syntax closures makes programming completely different. So, what is the syntax (that supports backtrackig) you can achieve with libraries and current DSL support in Kotlin? Can you point in your library an example?
Another issue is an optimization. Inline functions know nothing about following rules and where to backtrack. Analyzing the function ('rule') as whole allows to generate more optimal code.