Not to argue with the claim—Prolog does feel magic sometimes—and maybe I'm not sufficiently idiomatic in Prolog, but I would express them similarly: something like
concat([], Bs, Bs).
concat([A|As], Bs, [A|Cs]) :- concat(As, Bs, Cs).
concat [] bs = bs
concat (a:as) bs = a:(concat as bs)
(define (concat as bs)
(if (null? as)
bs
(cons (car as) (concat (cdr as) bs))))
Is one of these an un-idiomatic way to do it? (If you downvote, of course that's your right, but I'm not being sarcastic or dismissive; I really would like to know, as not a professional programmer in or fluent speaker of any of these languages, if I'm not writing idiomatically, so I'd be grateful if the downvote came with a comment!)
- The head function (with X unknown and L known): concat([X],_,L).
- Produce all splits of a list (with X and Y unknown): concat(X,Y,L).
- Does this list start with the prefix [a,b]? If yes, let Y be the tail (Y unknown): concat([a,b],Y,L).
... and many more.
From my functional/imperative programming experience, when originally picking up Prolog, I conceptualized the kind of operations you describe (e.g., “all splits”) as “running the function backwards” — going from output L to inputs X, Y.
But as you write, the truth is that Prolog is modeling the relation of concatenation.
[eclipse 2]: concat(A,[_,_],[0,1,2,3,4]).
A = [0, 1, 2]
Yes (0.00s cpu, solution 1, maybe more) ? ;
No (0.00s cpu)
[eclipse 3]: concat(A,B,[0,1,2]).
A = []
B = [0, 1, 2]
Yes (0.00s cpu, solution 1, maybe more) ? ;
A = [0]
B = [1, 2]
Yes (0.00s cpu, solution 2, maybe more) ? ;
A = [0, 1]
B = [2]
Yes (0.00s cpu, solution 3, maybe more) ? ;
A = [0, 1, 2]
B = []
Yes (0.00s cpu, solution 4) (define (concast as bs)
(match as
['() bs]
[(cons a as) (cons a (concat as bs))]))I think the Scheme version might be considered unidiomatic due to the inefficiency: because it's not tail recursive, you're building a huge stack of cons calls (whose depth is the length of `as`) which only resolve once you reach the end of `as`.
On the other hand, the version with accumulator would need to traverse as and bs in full, twice (once for the accumulation and once for the terminal reverse).
> At the same time, recursion does not lead to particularly
> bad performance in Racket, and there is no such thing as
> stack overflow; you can run out of memory if a computation
> involves too much context, but exhausting memory typically
> requires orders of magnitude deeper recursion than would
> trigger a stack overflow in other languages. These
> considerations, combined with the fact that tail-recursive
> programs automatically run the same as a loop, lead Racket
> programmers to embrace recursive forms rather than avoid
> them.
AFAIK the Scheme standard doesn't specify either behaviour. So, with regards to the standard both Racket and other Scheme implementations are free to implement this in whichever way they prefer. And the Scheme implementations that I'm using (Gambit-C, Chicken and Guile) all work the same as Racket. I only know of Bigloo (of about 10 years ago, maybe it changed?) as a Scheme implementation that uses the machine stack to implement Scheme continuation frames, and Bigloo (again back then) doesn't (didn't?) implement call/cc efficiently either. Arguably to implement the Scheme standard including call/cc efficiently the machine stack can't be used, thus any 'proper' Scheme implementation will behave like Racket.
I've written lots of non-Racket Scheme code and my code always assumes that it won't run out of stack before running out of heap. Some Scheme implementations allocate stack frames more efficiently than cons cells thus the straight-forward solution (recursion, not iteration then reversion) is also the more efficient one.
There is a tendency of claiming Racket is somehow fundamentally different from Scheme which sometimes feels a bit like a racket. I'm not opposed to Racket but think it would be better to take it as what it is, Scheme plus extensions and tooling, which most other Scheme implementations are as well. Racket may be doing that more extensively but I think it calling itself a different language should primarily be understood as a marketing ploy, or maybe as a move to justify moving ahead with own ideas without caring about the rest of the Scheme community.
It is difficult to use the machine stack and have a fast call/cc. But I think Chez Scheme proves it's possible.
If you want to have code work everywhere and thus code defensively, yes. Of course you're not coding defensively when coding for Racket, either. But I guess I may have misunderstood you--Racket simply gives you a guarantee; as do some (other) Scheme implementations, so you get the same benefit with some/many other Scheme implementations as well--but even those "differ from Scheme (the standard)", by giving such a guarantee outside of the standard. It's not "Racket vs. Scheme implementations", it's "the (Racket|Scheme) implementations vs. Scheme (the standard)". Apologies then for my inappropriate rant about false claims.
> It is difficult to use the machine stack and have a fast call/cc. But I think Chez Scheme proves it's possible.
Chez doesn't seem to be using the machine stack either. I've tested with this code and "ulimit -s 1000" on Linux and it runs fine:
(define (conc a b)
(if (null? a)
b
(cons (car a)
(conc (cdr a) b))))
(define (iot n)
(if (negative? n)
'()
(cons n (iot (- n 1)))))
(display (length (conc (iot 10000000) (iot 10000000))))
(newline)
I don't know whether Chez still uses the same strategy, but a major part of Dybvig's thesis (very readable) was dedicated to explain the details of a possible implementation strategy.
https://mitpress.mit.edu/books/reasoned-schemer-second-editi...
Racket and Perl 6 are the only small userbase languages in the last 8-10 years to amaze me with their feature sets and to make me want to learn them just for the sake of experiencing them.
> A logic programming library for Clojure & ClojureScript. core.logic offers Prolog-like relational programming, constraint logic programming, and nominal logic programming for Clojure.
Minikanren seems to be closer to the mark, and I thank the commenters who pointed it out!
That is, saying that minikanren seems to be closer to the mark than core.logic is a little bit nonsensical (please read that in a good sense!)
I don't want to do logic programming in clojure (or whatever other language), I want to do logic programming in Prolog and drop it into my clojure project and have to do as little plumbing as possible.
The nearest analogy I can come up with is LINQ. In the examples in [1] the experience of the developer is closer to writing SQL in the middle of a C# or VB file, rather than having a good C# database query library.
[1] https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...
That's super common, both as bridges to Prolog systems from other host languages and as implementations of Prolog semantics (or a subset like Datalog) as libraries in other host languages; also MiniKanren is available for many host languages.
Even a simple thing like concatenation of two lists, that in Prolog it could be done purely declaratively, without expressing how it needs to be performed, seems levels more magical than how it is done in lisps.