# 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.