Recreational programming: Tacit programming in Prolog

[hurufu]

Nothing serious, I just find it interesting.

main(R) :-
    phrase(main, [1,2,3|S], [R|S]).

% Look! No variables!
main --> mul, add, is_, dup, pi, sub, swp, pow, abs, is_.

pop --> [_].
dup, [A,A] --> [A].
swp, [B,A] --> [A,B].
add, [A+B] --> [A,B].
sub, [A-B] --> [A,B].
mul, [A*B] --> [A,B].
pow, [A^B] --> [A,B].
neg, [-A] --> [A].
rec, [1/A] --> [A].
abs, [abs(A)] --> [A].
sin, [sin(A)] --> [A].
cos, [cos(A)] --> [A].
tan, [tan(A)] --> [A].
pi, [pi] --> [].
is_, [X] --> [A], { X is A }.

?- main(R).
   R = 0.05023761449883708.

[UWN]

13211-3 conformity approved

[jjtolton]

What does this mean? 🤔

[bakaq]

13211-3 is the newly published DCGs ISO standard. This post fully conforms to it.

[emummel20]

Honestly, lack of tacit syntax is virtually the only thing preventing prolog from truly being a god-tier language for me. I hate writing code like

foo(A,B),
bar(B,C),
baz(C,D),

when all I needed was D. I know there's library(func) but I really wish it was just the actual language syntax.

I saw this idea on binate relational syntax for prolog and thought it was interesting.

[emummel20]

if you would use tacit programming techniques everywhere

Certainly not everywhere, because sometimes you write predicates that make use of those intermediate variables, and you're correct that in cases of omnidirectional predicates explicitly declaring variables helps with reasoning over your code, debugging, etc, but I wish I was given the choice to mix & match as needed. I don't think there's anything in principle that would prevent us from doing that. Again, in cases like foo(A,B),bar(B,C),baz(C,D) where my logic is unidirectional and all I need is that final value D, I don't necessarily need to see all of those intermediate variables and all the explicit declarations do is clutter my code and cost dev time.

[emummel20]

Really cool btw, thanks for sharing. It's a good reason for me to learn semi-context notation.

Actually I'm wondering if there's a way to set up the DCGs so that you can run operations in between stack values as well? Meaning: Taking stack-based lang Uiua as an example, in both cases you can perform LIFO operations like dup, add, and swap

but you can also perform operations between two stack values

and I'm wondering if this can be used to simulate all of uiua's stack operations, because I think it would be pretty dope to be able to solve a problem like this simulating the uiua solution

▽⤚≡(/×=₁ /+⍉ =¤)⊓⧅⋅⋅1¤ ⊙(⇡10) ⊣⊸△ [8_9_6 9_8_3 2_4_6 8_4_3]

in a prolog dsl like

solve(Input,Solution) :-
     phrase((

        op1,
        op2,
        op3
       ...

     ),Input,Solution)

%?- solve([[8,9,6],[9,8,3],[2,4,6],[8,4,3]],Solution).

[hurufu]

Yes you can, but for this example I didn't do it, because I wanted to use exclusively atoms in a language.

psh(X), [X] --> [].

Next your example works:

?- phrase((dup,psh(3),dup,add,is_,swp), [5], S).
   S = [5,6,5].

Second argument to phrase/3 is [5] this is how I pre-populate stack with some values, alternatively you can do everything explicitly:

?- phrase((psh(5),dup,psh(3),dup,add,is_,swp), [], S).
   S = [5,6,5].

[hurufu]

IMO, CLP(Z) is very well suited to solve the problem that you have linked.

[hurufu]

Also if you are interested in stack based sub-languages you can checkout this: #853 (comment), but it uses rational trees and it is a nasty beast to work with.

[haijinSk]

A related 2021 example by Markus @triska: https://news.ycombinator.com/item?id=28966133#28970769

[hurufu]

Oh, interesting I wasn't aware of this technique before so it looks like I've re-invented the wheel :) At least it is quite fun exercise.

[hurufu]

I forgot to describe what code in my first post does.

It implements simple stack-based language (like Forth, but without loops and less elegant). Every word operates on variables on a stack. Consider following definition:

add, [A+B] --> [A,B].

You can read it imperatively if you find it easier: Word add removes 2 elements from the stack (A and B) and pushes single term A + B back to the stack.

[maksimac]

I guess the other way to do this is

opt(pop,[_|S],S).
opt(dup,[A|S],[A,A|S]).
opt(swp,[A,B|S],[B,A|S]).
opt(add,[A,B|S],[C|S]) :- C is A+B.

stack([],S,S).
stack([Op|Ops],S,S0) :-
  opt(Op,S,S_),
  stack(Ops,S_,S0).

%%%%%%%%%%%

?- stack([swp],[3,5],X).
X = [5, 3].

?- stack([swp,dup],[3,5],X).
X = [5, 5, 3].

?- stack([swp,dup,add],[3,5],X).
X = [10, 3].

?- stack([swp,dup,add,add],[3,5],X).
X = [13].

?- stack([swp,dup,add,add,pop],[3,5],X).
X = [].

[hurufu]

This method isn't that much different ;). If you look into expanded code it describes exactly the same predicates:

?- maplist(listing, [pop/2, dup/2, swp/2]).
pop(A,B) :-
   A=[C|B].
dup(A,B) :-
   A=[C|D],
   B=[C,C|D].
swp(A,B) :-
   A=[C,D|E],
   B=[D,C|E].
   true.

The are two differences though:

• In your example you need a special interpreter stack/3 which actually executes instructions.
• Difference in add, because I decided to use explicit evaluation using is_, and you have decided to use immediate evaluation

[hurufu]

It just occured to me, that "functional" style can be easily implemented using delimeted continuations from library(cont). Here is a quick sketch, very slow, but just to show the idea:

:- use_module(library(cont)).
:- use_module(library(lists)).

:- op(990, xfx, :=).

triangle_area(X) :-
    X := (side_1 * side_2 * sin(angle_between_sides)) / 2.

side_1 :- return(5).
side_2 :- return(4).
angle_between_sides :- return(pi/6).
A * B :- return(A*B).
A + B :- return(A+B).
A / B :- return(A/B).
cos(A) :- return(cos(A)).
sin(A) :- return(sin(A)).

return(X) :- shift(return(X)).
Return := Evaluable :-
    callable(Evaluable) ->
        Evaluable =.. [F|Args],
        maplist((:=), Rets, Args),
        Function =.. [F|Rets],
        reset(Function, return(X), _), !,
        Return is X
    ;   Return is Evaluable.

Then just run:

?- triangle_area(X).
   X = 4.999999999999999.

Operator (:=)/2 doesn't need to be for arithmetic only, Just remove is from it and special handling for numbers.

[hurufu]

It is even smaller with term expansion:

:- use_module(library(cont)).
:- use_module(library(lists)).

:- op(990, xfx, :=).

user:term_expansion((A := B), (A :- shift(return(B)))).

main(X) :-
    X := triangle_area(side_1, side_2, angle_between_sides).

side_1 := 5.
side_2 := 4.
angle_between_sides := pi/6.
triangle_area(A, B, Angle) := 1/2 * A * B * sin(Angle).

Return := Evaluable :-
    callable(Evaluable) ->
        Evaluable =.. [F|Args],
        maplist((:=), Rets, Args),
        Function =.. [F|Rets],
        reset(Function, return(X), _),
        Return is X
    ;   Return is Evaluable.

UPDT: I've played with this code and it has a lot of problems with modules and pi and portability, so I wouldn't recommend using it.

[jjtolton]

What a gem!! Speaking of reinventing the wheel, I am very excited to try your stack machine with library(async). An async stack machine is something I've wanted for a long time, I never thought Prolog would be the thing to make it happen!

[hurufu]

I found this paper: https://apps.dtic.mil/sti/tr/pdf/ADA632218.pdf, so it looks like I've re-invented the wheel once again.