Concatenative Logic Programs?

Greg Buchholz — 2006-01-16 18:23:24

Lately I've been wondering if anyone has given thought to what

concatenative logic programming would look like.  Prolog programs seem

deeply intertwined with the idea of unifying terms and variables while

concatenative programs eschew variables altogether.  It seems like quite

a dichotomy (well, that combined with the fact that I view concatenative

programs as functional ones, with each combinator being a function from

stacks to stacks).  So I've been at a loss as to how one would write

logic programs in something Joy-like.  Let's take the "append" predicate

in a logical Joy for example...



    [a b c] [d e f] [a b c d e f] append



...that query would be true.  But how does one find the list which

results in [a b c d e f] when appended with [d e f]? (i.e. in prolog, the

X in append(X,[d,e,f],[a,b,c,d,e,f]))  If you wrote it as...



    [d e f] [a b c d e f] append



...how would you differentiate it from the other case (prolog:

append([a,b,c],X,[a,b,c,d,e,f]))? With stack shufflers (rot, swap, etc.)

somehow? Or maybe you'd have predicate modifiers which would indicate

which arguments on the stack are missing and therefore the unknowns we're

trying to find.  For lack of a better naming scheme, let's create a

family of predicate modifiers like "Xxx" and "xXx" where the capital 'X'

stands for the missing item(s).  (Below the "i" applies a modified

predicate to the stack items).  So our "append" examples might start to

look like...



    [a b c] [d e f] [a b c d e f] append.          (* True    *)

    [d e f] [a b c d e f] [append] [Xxx] modify i. (* [a b c] *)

    [a b c] [a b c d e f] [append] [xXx] modify i. (* [d e f] *)

    [a b c] [d e f] [append] [xxX] modify i. (* [a b c d e f] *)

    (* prolog: append([a|T],[d,e,f],[a,b,c,d,e,f]) *)

    a [cons] xX modify i [d e f] [a b c d e f] append. (* [b c] *) 



...or somesuch.  And that's just for making queries.  I don't have many

ideas on how you'd write the definition of "append" in the first place.



Thoughts?



Greg Buchholz





__________________________________________________

Do You Yahoo!?

Tired of spam?  Yahoo! Mail has the best spam protection around 

http://mail.yahoo.com

Jonathan Burns — 2006-01-16 21:12:40

On Tuesday 17 January 2006 05:23, Greg Buchholz wrote:



 >      Lately I've been wondering if anyone has given thought to what

>  concatenative logic programming would look like.  Prolog programs seem

>  deeply intertwined with the idea of unifying terms and variables while

>  concatenative programs eschew variables altogether.  It seems like quite

>  a dichotomy (well, that combined with the fact that I view concatenative

>  programs as functional ones, with each combinator being a function from

>  stacks to stacks).  So I've been at a loss as to how one would write

>  logic programs in something Joy-like.  



 
[ Snipping the append sketch.]



 >  Thoughts?



 
Hi, Greg. Only some thoughts, vague and tangential.



I have been thinking lately about categories and logic programming...



1. "Do category theory (CT) in Prolog." Meaning, make a systematic

list of CT definitions, so as to express them somehow as Prolog

predicates. Thence, produce a base of identities between arrow

compositions; these would be combinators in a typed concatenative

language. Prolog searching should be able (one would think) to

find the right arrow to complete a path, the right functor to express

an arrow as an equivalent with the right valence.



2. "Do Prolog in CT."  This is more like what you're reaching for.

I find it harder to think about than the other way. I ask, "What

kind of morphism is a Prolog term?" The answer seems to be,

for each case in which unification succeeds in the logic base,

it is a morphism between "environments", meaning, dictionaries

of assigned variables. But I don't have a grip on "the category

of dictionaries".



3. See what happens when these two snakes are allowed to

eat each others' tails.



I'm coming back to this after several years away. I've been

reading Burstall and Rydeheard:



Computational Category Theory 

http://www.cs.man.ac.uk/~david/categories/book/book.ps.



They do have a section on "A Categorical Unification Algorithm ",

giving a sketch which I haven't assimilated yet, along with a

collection of references.



Making slow progress with it. I didn't expect it to be easy.

Manfred Von Thun — 2006-01-18 08:52:08

On 17/1/06 5:23 AM, "Greg Buchholz" <sleepingsquirrel@...> wrote:



 >     Lately I've been wondering if anyone has given thought to what

> concatenative logic programming would look like.



 
[..]



One of (possibly many) answers is along these lines:

In logic programming we generally, though by no means always, want answers

in the form X = ... Y = ..., we really need those variables to give answers.

Consider a simple stereotyped data base, here written in postfix notation:

    john rich. jane rich. john mary loves.

    likes :- loves              (* note no parameters,

                                   so this is short for X Y likes :- X Y

loves *)

    is-liked-by :- swap likes.  (* again no parameters *)

    paul X likes :- X rich.

Now some queries and answers:

    mary rich.         no

    jane rich.         yes

    X rich.            X = john;

                       X = jane.

    X Y likes.         X = john, Y = mary

                       X = paul, Y = john

                       X = paul, Y = jane

    X john is-liked-by. X = mary

The two ³no parameter² cases in the definitions indicate some trivial

concatenative usages, hardly persuasive. But for the queries and answers

we really seem to need Prolog variables.



To a query involving append (Prolog¹s term for concatenation of lists):

    X Y [a b] append.

                       X = [], Y = [a b]

                       X = [a], Y = [b]

                       X = [a b], Y = []

This gives answers in the same style as for the database above.



 > ...or somesuch.  And that's just for making queries.  I don't have many

 
     ideas on how you'd write the definition of "append" in the first place.



Digging around in a part of my brain that has been dormant for over 15

years,

and translating into some sort of concatenative notation, the definition

must

be something like this:

    [] Y append.

    [X | Xs] Y [X | Zs] append  :-  Xs Y Zs append.

But all these named parameters, including the variables for parts of the

parameters, are not in the spirit of concatenative notation.



So, can we avoid these variables and replace them by dup, swap, uncons

and the like? Maybe, but it does not look promising. And if we insist

that variables should be allowed for the queries, then we no longer

have this Prolog principle: a query has the same structure as the

right hand side of a rule (a definition).



There is worse to come. Some queries and some rules use conjunctions:

    X rich, X young.            (³Who is rich and young?²)

    X lucky :- X rich, X young. (³If you are rich and young, then you are

lucky²)

The innocent looking comma would introduce an important new syntactic

element:

it is a binary operator, here written in infix notation. Semantically it

maps

to conjunction, just as concatenation maps onto function composition. Ooops!

It is hard to make sense of the two together. Maybe a conjunction

combinator:

        X lucky :- [X rich] [X young] and.

or      X lucky :- X [rich] [young] and.

or        lucky :- [rich] [young] and.



It all looks pretty dreadful to me. Maybe the purity of concatenative

notation

goes too far, and pattern matching should be allowed, as has been suggested

some time ago on this mailing group. Maybe (explicit) infix operators such

as

the comma for conjunction should be allowed. But maybe we have to conclude

that concatenative notation is fine for some areas but not for others.



Sorry that all this is not well thought out.



  - Manfred



















[Non-text portions of this message have been removed]

Manfred Von Thun — 2006-01-23 05:48:41

On 18/1/06 7:52 PM, "Manfred Von Thun" <m.vonthun@...> wrote:



 > 

> 

> 

> On 17/1/06 5:23 AM, "Greg Buchholz" <sleepingsquirrel@...> wrote:

> 

>> >     Lately I've been wondering if anyone has given thought to what

>> > concatenative logic programming would look like.

> 

> [..]

> 

 
I now think that my response was overly pessimistic, and that concatenative

notation could be used for such a language ­ call it Joylog.

 > 

 
The basic idea would have to be that Joylog has to start with an empty stack

and every program computes zero or more stacks of bindings, except that

the stack positions are anonymous. We can think of the stack elements as

implicit logical variables, ...S3 S2 S1, starting at the top. So a database

query ³who loves whom?² would be written

    loves.

might result in bindings such as

    S2 = john S1 = mary

    S2 = mary S1 = bob

except that S1 and S2 are not actually given. Instead we have as answers

    john mary

    mary bob

The query ³which rich person loves somebody² would be given as

    [rich] dip loves.

The query ³which person loves somebody who is rich² would be

    rich loves.

Anyone of these might give several answer sets, without using the

S1 S1 ... variables.



Other queries might be ³who loves mary²:

    mary loves.

with answer

    john.

and ³whom does mary love²:

    mary swap loves.

with answer

    bob



Finally, there might be queries without actual bindings, just

success or failure: ³does mary love john² becomes

    mary john loves

with answer (poor John) ³no²

and ³does john love mary² becomes

    mary john loves

with answer ³yes².



So, I think I was quite wrong about a concatenative logic language

needing variables for pattern matching ­ at least for database queries.



 > To a query involving append (Prolog¹s term for concatenation of lists):

>     X Y [a b] append.

>                        X = [], Y = [a b]

>                        X = [a], Y = [b]

>                        X = [a b], Y = []

> This gives answers in the same style as for the database above.



 
Without explicit variables the query ³which two lists appended result in [a

b]²

should be written

    [a b] append

and produce the three answers without variables:

    [] [a b]

    [a] [b]

    [a b] []



 >> > ...or somesuch.  And that's just for making queries.  I don't have many

>      ideas on how you'd write the definition of "append" in the first place.

> 

> Digging around in a part of my brain that has been dormant for over 15

> years,

> and translating into some sort of concatenative notation, the definition

> must

> be something like this:

>     [] Y append.

>     [X | Xs] Y [X | Zs] append  :-  Xs Y Zs append.

> But all these named parameters, including the variables for parts of the

> parameters, are not in the spirit of concatenative notation.

> 

 
I still don¹t have a definition in variable free notation, but I¹ll think

about it. One thing that is clear is that somewhere it will involve a test,

which in Joy is just ³is the top of the stack the empty list², but in Joylog

will have to be read as ³can the top of the stack be unified with [] ?²

    [] =

So, very importantly, like all predicates in a logical language, the

identity

predicate =  can succeed or fail, and succeeding might involve a binding.

That takes some getting used to.



 > 

> 

> There is worse to come. Some queries and some rules use conjunctions:

>     X rich, X young.            (³Who is rich and young?²)

>     X lucky :- X rich, X young. (³If you are rich and young, then you are

> lucky²)

> The innocent looking comma would introduce an important new syntactic element:

> it is a binary operator, here written in infix notation. Semantically it maps

> to conjunction, just as concatenation maps onto function composition. Ooops!

> It is hard to make sense of the two together. Maybe a conjunction

> combinator:

>         X lucky :- [X rich] [X young] and.

> or      X lucky :- X [rich] [young] and.

> or        lucky :- [rich] [young] and.

> 

 
Wrong again. Program concatenation maps onto function composition as in any

concatenative language. In Joylog the functions are from a stack of unbound

or bound anonymous variables to a result stack of possibly more bound

variables.

So syntactic concatenation of programs again maps onto semantic composition

of functions. One big difference is that the functions really are relations,

as

seen by multiple answers. (Jonathan: do you know about Allegories in

category

theory? Can you see a useful connection?)



So, I think there is some hope.



  - Manfred



 >  







 
[Non-text portions of this message have been removed]

Jonathan Burns — 2006-01-23 07:56:46

On Monday 23 January 2006 16:48, Manfred Von Thun wrote:



 >  Wrong again. Program concatenation maps onto function composition as in

> any concatenative language. In Joylog the functions are from a stack of

> unbound or bound anonymous variables to a result stack of possibly more

> bound variables.

>  So syntactic concatenation of programs again maps onto semantic

> composition of functions. One big difference is that the functions really

> are relations, as

>  seen by multiple answers. (Jonathan: do you know about Allegories in

>  category

>  theory? Can you see a useful connection?)



 
Only that, in a vague sense, allegories are to categories as relations are

to functions.



Not to dismiss allegories: they ought to map nicely onto relational database

"joins", and correspondingly to Prolog queries. My hunch is that this would

mean losing some strength in concatenative language algebra.



Allow me a few days (making Linux servers sit up and do tricks), and I'll

run some Prolog demos with trace on. Then I'll be able to see just what's

being pushed and popped.