Horn Clause Predicates

[TheFo2sh]

Functional programming support in C# is getting increased , having the ability of writing horn clauses predicates simialaire to prolog in c# will be strong improvement in the language itself.

Suggested Syntax

Even(n)=> |2 => true |n => !Even(n-1);

And it can be used as a predicate
Even(4); //return true
or with linq
new[]{2,3,4,5,6,7,8,9,10,11,12}.Where(Even).Sum()

Related Language Feature

I made a fast prove of concept using f# pattern matching feature
let rec Even x= match x with | 2 -> true | _ -> not(Even(x-1))

Challenges

1- Infinite Recursion Problem
When the input domain contains a value out of the Predicate range , it will end up with infinite recursion and then stackoverflow. It could easily happen in the previous could by doing execution the previous code with Even(1)
this can be solved by modifying the previous code to be

A more complete version that work with all the integers
Even(n)=> |2 => true |n =>x>2 && !Even(n-1); |n =>x<2 && !Even(n+1);

which is equivalent to

let rec Even x= match x with | 2 -> true | x when (x>2) -> not(Even(x-1)) | x when (x<2) -> not(Even(x+1))

2- a strong challenge to make working is the lack of tail recursion optimization in c# so any attempt to executed the previously described code will end with stackoverflow exception.

Related proposal
#2544

[YairHalberstadt]

Even(n) => n switch { 2 => true, _ => !Even(n - 1)};

Is legal as of C# 8 switch expressions.

[MgSam]

Bonus points for the most over-complicated way to check if a number is even.

[The-Futurist]

@TheFo2sh

I'll admit I've never heard of "horn clauses" despite studying functional programming for some years, this is always interesting to stumble upon a new concept. So tell me how would you express what you're trying to express in a functional language - like F#? This may help me understand it better.

A cursory search seems to show this a concept from "logic programming" rather than functional, is that true?

Also can the "infinite recursion" and consequent stack overflow be addressed by tail recursion?

[TheFo2sh]

@Korporal
you are right horn clauses is initially a logic programming concept , as functional programming and logical programming share the same nature of being declarative Horn clauses can be used in both paradigms as a declarative constrain in other word horn clauses used to represent rules in logic paradigm and can be used to represent declarative condition predicate in functional paradigm.

As example of how horn clauses can be an alternative to complex conditions chain
select social media posts that have more then 10 likes or the sum of the likes on it is recursive comments (including comments on comments) are more 30.

Normal c# code

bool IsValid(post)
{
        if(post.Likes.Count()>=10)
            return true;
        if(post.Comments.Select(comment=>CommentsCount(comment)).Sum()>=30)
            return true;
    return false;
}

int CommentsCount(comment){
    return comment.Likes.Count()+comment.select(subcomment=>CommentsCount(subcomment)).Sum();
}

Horn clauses like syntax

IsValid(post) =>
	            |post.Likes.Count() >=10 =>true
	            |post.Comments.Any()&&TotalLikes(post.Comments) >=30 =>true


TotalLikes(comment) =>
	            |comment.Comments.Any()	=> comment.Likes().Count()
	            |_	                    => comment.Likes.Count()+comment.comments.Select(TotalLikes).Sum()

While the first imperative syntax is more common and more popular , the horn clause syntax is more declarative, we just write the conditional and not having any control on how it will get executed, imagine more business cases will emerge the horn clauses syntax will be able to get extended easier.

Regarding the f# implementation in the original post i had 2 example implementations using the pattern matching feature in f#.

i will write a separate comment on how why the new switch expression does not solve the same cases the horn clauses like predicate could solve.

[spydacarnage]

Looks a lot like local functions to me, which I use all the time for more declarative coding in C#

…

On Fri, 21 Jun 2019, 20:23 TheFo2sh, ***@***.***> wrote: @Korporal <https://github.com/Korporal> you are right horn clauses is initially a logic programming concept , as functional programming and logical programming share the same nature of being declarative Horn clauses can be used in both paradigms as a declarative constrain in other word horn clauses used to represent rules in logic paradigm and can be used to represent declarative condition predicate in functional paradigm. As example of how horn clauses can be an alternative to complex conditions chain select social media posts that have more then 10 likes or the sum of the likes on it is recursive comments (including comments on comments) are more 30. Normal c# code bool IsValid(post) { if(post.Likes.Count()>=10) return true; if(post.Comments.Select(comment=>CommentsCount(comment)).Sum()>=30) return true; return false; } int CommentsCount(comment){ return comment.Likes.Count()+comment.select(subcomment=>CommentsCount(subcomment)).Sum(); } Horn clauses like syntax IsValid(post) => |post.Likes.Count() >=10 =>true |post.Comments.Any()&&TotalLikes(post.Comments) >=30 =>true TotalLikes(comment) => |comment.Comments.Any() => comment.Likes().Count() |_ => comment.Likes.Count()+comment.comments.Select(TotalLikes).Sum() While the first imperative syntax is more common and more popular , the horn clause syntax is more declarative, we just write the conditional and not having any control on how it will get executed, imagine more business cases will emerge the horn clauses syntax will be able to get extended easier. Regarding the f# implementation in the original post i had 2 example implementations using the pattern matching feature in f#. i will write a separate comment on how why the new switch expression does not solve the same cases the horn clauses like predicate could solve. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://github.com/dotnet/csharplang/issues/2610?email_source=notifications&email_token=ADIEDQMCBFR6DAUAZHSYEL3P3UTBLA5CNFSM4HZ52CN2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODYJLXKA#issuecomment-504544168>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADIEDQPZFXKR4X26XCKV273P3UTBLANCNFSM4HZ52CNQ> .