Concatting a list of strings in Prolog

Question

I'm writing a Lisp to C translator and I have a problem with handling strings. This is a code that transforms an unary Lisp function to a C equivalent:

define(F) --> fun_unary(F), !.

fun_unary(F) --> "(define (", label(Fun), spaces, label(Arg1), ")", spaces, expr(Body), ")",
  {swritef(F, "data *%t(data *%t) { return(%t); }", [Fun, Arg1, Body])}, !.


funs([F])  --> define(F), !.
funs([F|Fs]) --> define(F), spaces, funs(Fs), !.

Now I want to read any number of functions and return them as a single string. The above funs is the best I could come up with, but it works like this:

?- funs(F, "(define (carzero l) (= (car l) 0)) (define (zero n) (= 0 n))", []).
F = ["data *carzero(data *l) { return(eq(car(l), make_atom_int(0))); }", "data *zero(data *n) { return(eq(make_atom_int(0), n)); }"].

While I want something like this:

F = "data *carzero(data *l) { return(eq(car(l), make_atom_int(0))); }\n\ndata *zero(data *n) { return(eq(make_atom_int(0), n)); }".

so that I can nicely swritef is into a complete program, between #includes and main(). An alternative solution is to modify the highest level translator to handle the list. It curently looks like this:

program(P) --> define(F), {swritef(P, "#include \"lisp2c.h\" \n\n%t \nint main() { return 0; }", [F])}, !.

How would I do any of these two? I'm using SWI Prolog.

Shennashensi

The subject line mentions Prolog, while the body of the question asks about "Lisp to C" translation. Help me sort out what's what here. The code snippets look a little like Prolog, perhaps because the special DCG syntax is being confused with Prolog's more basic syntax for rules. While the subject line asks about "a list of strings in Prolog", it seems parsing of strings that contain Lisp code is involved. Concatenation of a list of strings is a relatively simple task in Prolog. Your example predicate funs/2 suggests you would like to throw in a couple of newline characters between... – Epispastic

...consecutive strings being concatenated. If that's the scope of the question, I can answer it, and we can sort out the confusion of syntaxes (if needed). – Epispastic

Lisp to C translation is what the program does. The program is written in Prolog, using the DCG syntax to translate individual cases. Most of the predicated parse Lisp code, with their argument being the resulting C code. I want two newlines between concatenated strings. Hope that's it. – Shennashensi

So the Lisp-to-C translation part wasn't really part of the question :) Cool idea though. How do you handle memory allocation? – Physic

If I knew the specific Prolog implementation you are using, I could tailor the answer to that. There are three data representations of "strings" common to Prolog: strings, atoms, and lists of characters. The ISO standard says read/1 and related predicates should treat double quoted text as strings, but because of historical support for this syntax to denote lists of characters, implementations usually deal with the issue with options of varying syntax. – Epispastic

@larsmans: I just malloc space for each variable. So far, only #t and () are initialised just once and I allocate space for each number every time it's used, but I'm planning to keep a list of numbers that are already allocated and reuse them if necessary (by assert, probably). – Shennashensi

Answer 1

Setting aside for now the purpose for which it's needed, let's write a Prolog predicate that concatenates a list of strings into one string, placing a double newline between each consecutive pair of strings (but not at the end of the output string, judging by the example that Jerry posted).

SWI-Prolog Manual: Normally I'd post "deep" links to the documentation, but the SWI-Prolog site uses a style of URL that triggers cross-site scripting (XSS) warnings with many browser/plugin combinations. So instead I'll refer than link to the appropriate section.

Section 4.22 Representing text in strings says (in part), "String objects by default have no lexical representation and thus can only be created using the predicates below or through the foreign language interface." This can be a little confusing, as SWI-Prolog writes strings as double-quoted text, but reads double-quoted text (by default) as lists of character codes.

Here's code for a predicate that concatenates the strings in a list, inserting another string Separator in between consecutive string pairs:

strSepCat([ ],_,Empty) :-
    string_to_list(Empty,[ ]).
strSepCat([H|T],Separator,StrCat) :-
    strSepCat(T,Separator,H,StrCat).

strSepCat([ ],_,StrCat,StrCat).
strSepCat([H|T],Sep,Str,Cat) :-
    string_concat(Sep,H,SepH),
    string_concat(Str,SepH,StrSepH),
    strSepCat(T,Sep,StrSepH,Cat).

Note that we've defined two predicates, strSepCat/3 and strSepCat/4. The former is defined in terms of the latter, a typical design pattern in Prolog that introduces an extra argument as an accumulator that binds to an output when recursion is complete. Such a technique is often helpful in getting a tail recursive definition.

To use the predicate strSepCat/3, we'd generally need to construct the separator string with (the escape sequence for) two newlines:

?- funs(Fs,Lisp,[ ]), string_to_list(Sep,"\n\n"), strSepCat(Fs,Sep,CProg).

Epispastic

Answer 2

What about using DCG notation for appending the strings?

concat([]) --> [].
concat([List|Lists]) --> List, "\n\n", concat(Lists).

Edgeways

Answer 3

A simpler (and more generic) solution than the accepted answer is to use reduce with the existing string_concat as a parameter:

reduce3(_, [],  Default, Default).
reduce3(_, [A], _, A).
reduce3(P3, [A,B|T], _, D):-
    call(P3, A, B, C),
    reduce3(P3, [C|T], _, D).

?- reduce3(string_concat, ["123", "456", "789"], "", R).
R = "123456789"
?- reduce3(string_concat, ["123"], "", R).
R = "123"
?- reduce3(string_concat, [], "", R).
R = ""

strings_concat(Strings, String):-
    reduce3(string_concat, Strings, "", String).

SWISH notebook: https://swish.swi-prolog.org/p/reduce.swinb

Hearty

Answer 4

Since strings in Prolog are really lists of character codes, you can use append in a custom predicate that also inserts the newlines:

concat_program([], "").
concat_program([L|Ls], Str) :-
    concat_program(Ls, Str0),
    append("\n\n", Str0, Str1),
    append(L, Str1, Str).

Usage:

funs(Fs, Lisp, []),
concat_program(Fs, P),
write("#include ...\n"),
writef(P).

Physic

funs(F, "(define (zero x) 0) (define (one n) 1)", []), concat_program(F, X). is false. – Shennashensi

F = ["data *carzero(data *l) { return(eq(car(l), make_atom_int(0))); }", "data *zero(data *n) { return(eq(make_atom_int(0), n)); }"], concat_program(F,X). works. I can't see what's wrong in the rest of your code since you haven't given the full grammar. – Physic

The general idea is correct but I suspect the premise "strings in Prolog are really lists of character codes" may be faulty for the Prolog implementation in use. See this discussion for SWI-Prolog strings and concatenation: sci.hkbu.edu.hk/scilab/doc/prolog/sec-3.20.html – Epispastic

@hardmath: this works in SWI and SICStus. I wasn't aware of Prolog implementations that handle string in a different way. The OP may want to replace append with concat or string_concat to see if that works. – Physic