A new Common Lisp compiler/interpreter

[Douglas R. Miles/LogicMoo]

A new Common Lisp compiler/interpreter

https://github.com/TeamSPoon/wam_common_lisp/tree/master/prolog/wam_cl


About this Lisp:

* Translates Lisp source files into Prolog source files. ( compilation is done to Translated source)

* At the REPL, forms are converted from Lisp to Prolog then call/1d
Being written as an SWI-Prolog "pack"

* Continue to ensure can run in YAP (which Lisp to Prolog benchmarking shows about 4x speedup)

* One small code so far seems to run much faster than ECL, ABCL, CLISP but about ¼ the speed of SBCL

* Picks up freebies .. whatever the host prolog system offers such as
**Makes Executables and. So files
**Garbage Collection
**Memoization
**Embedding (from C/C++/Python/C#/Mono/Java)

* Gives back OO to Prolog programmers .. to keep later copy_term's cheap, it passes entire object references as atoms (nb_current/2 allows access to the object's property map)
….



Roadmap Items
*Expect to pass most all CL-ANSI tests
*Using SWICLI as FFI (SWICLI itself still needs work)
*ASDF
*Quicklisp
….

I've only spent a week on it ... I hope to recruit people that seem to know both Lisp and Prolog languages.

The main purpose is this impl is it to run prolog-in-lisp 1000x faster than the fastest lisps (like SBCL)
Be at least in the top 3 impls for speed … Also the type of lisp programs I like to run (SWALE, DAYDREAMER) are buggy partial impl of Greenspun's rule as applied to Prolog (Instead of Lisp)

- Douglas Miles

[burs...@gmail.com]

Good work!

Yes steel beams are difficult to melt (SBCL).

[Markus Triska]

Hi Douglas,

"Douglas R. Miles/LogicMoo" <logi...@gmail.com> writes:

> A new Common Lisp compiler/interpreter
>
> https://github.com/TeamSPoon/wam_common_lisp/tree/master/prolog/wam_cl

Thank you for sharing!

Discussion on Reddit:

https://www.reddit.com/r/Common_Lisp/comments/7cf79a/new_common_lisp_compilerinterpreter_in_prolog/?ref=share&ref_source=link

On HN:

https://news.ycombinator.com/item?id=15680787

Keep up the great work!

All the best,
Markus

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
The Power of Prolog: https://www.metalevel.at/prolog

[burs...@gmail.com]

https://www.metalevel.at/lisprolog/

(Is this part of Power of Prolog? Do
the HTML snippets a date somewhere?)

Ok I see:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Lisprolog -- Interpreter for a simple Lisp. Written in Prolog.
Written Nov. 26th, 2006 by Markus Triska (tri...@metalevel.at).
Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
https://www.metalevel.at/lisprolog/lisprolog.pl

But I guess Common Lisp posses an additional
challenge, since it has CLOS:
https://en.wikipedia.org/wiki/Common_Lisp_Object_System

Can we get rid of Logtalk now?

[Douglas R. Miles/LogicMoo]

Because some people have privately asked my questions offline, I'll reply inline (to my own mail) and correct some of the confusing misstatements I had made.

On Monday, November 13, 2017 at 6:17:39 AM UTC-8, Gavino himself wrote:

> On Saturday, November 11, 2017 at 4:01:16 PM UTC-5, Douglas Miles wrote:
> > A new Common Lisp compiler/interpreter
> >
> > https://github.com/TeamSPoon/wam_common_lisp/tree/master/prolog/wam_cl
> >
> >

> > About this Lisp:
> >
> > * Translates Lisp source files into Prolog source files. ( compilation is done to Translated source)
> >
> > * At the REPL, forms are converted from Lisp to Prolog then call/1d

> > Being written as a SWI-Prolog "pack"

> >
> > * Continue to ensure can run in YAP (which Lisp to Prolog benchmarking shows about 4x speedup)
> >
> > * One small code so far seems to run much faster than ECL, ABCL, CLISP but about ¼ the speed of SBCL
> >
> > * Picks up freebies .. whatever the host prolog system offers such as

> > Makes Executables and .So files
> > **Garbage Collection
> > **Memoization

> > **Embedding (from C/C++/Python/C#/Mono/Java) is done via host Prolog system
> > FFI
> >
> > * Gives back OO to Prolog programmers .. to keep later copy_term's cheap, it passes entire object references as atoms (nb_current/2 allows access to the object's property details stored in a Map)

> > ….
> >
> >
> >
> > Roadmap Items
> > *Expect to pass most all CL-ANSI tests
> > *Using SWICLI as FFI (SWICLI itself still needs work)
> > *ASDF
> > *Quicklisp
> > ….
> >
> > I've only spent a week on it ... I hope to recruit people that seem to know both Lisp and Prolog languages.
> >
> > The main purpose is this impl is it to run prolog-in-lisp 1000x faster than the fastest lisps

prolog-in-lisp(s) are *not* 1000x slower than prolog-in-c but certainly not as fast (I apologize, I should have said 5-10x time slower). The problem arises for Prolog programs like: English to CommonLogic converters (used in Natural Language Understanding), large-scale ontology checkers, KL-ONE language interpreters, and PDDL planners (Planning Domain Definition Language). Such programs perform fine when written entirely in Lisp or Prolog (neither better or worse). The problem is that they more often perform unacceptably poor when written in Prolog and then ran on a prolog-in-lisp interpreter.

This leads to another class of programs

> > and be at least in the top 3 impls

> > for speed … Also the type of lisp programs I like to run (SWALE, DAYDREAMER) are buggy partial impl of Greenspun's rule as applied to Prolog (Instead of Lisp)

I should clarify, SWALE and DAYDREAMER are *not* buggy implementations of Prolog! they are their own things. But there are certain routines they contain that make extensive use of unification and backtracking. These routines (for decades now) are examples where the data representations and processing their capabilities (well mostly domain sizes) have been scaled back due to virtually creating the same penalties of the "prolog-in-lisp" scenario. This scenario is similar to taking an assembly language program that twiddles bitmasks and using bignum math to emulate the registers of the Intel-4930k CPU. *You might just see some performance differences? We will be very lucky if 4x-10x was the only speed difference between running that same assembly code program directly on the processor or in our program.

> >
> > - Douglas Miles
>


> why tho?


First, the nonpractical reasons:

(to answer several questions)

Is it really super easy to implement _anything_ on Prolog? Some junior Prolog programmers would be surprised by Prolog doing any OO let alone MOP. After all, Prolog is very very simple when it comes to its types.

If it can be done, in the end, will it look as ugly as trying to implement and maintain a CommonLisp in a programing language like LOGO? Everyone who graduates with a CS degree was tasked with several disarming hour just trying to do something as simple as adding up a list of numbers in Prolog. In moments of horror they think how simple it would have been it has it been any other language than Prolog. Most come away with the misunderstanding that Prolog is only capable of certain pure tasks. And too awkward for everything else. Much like how LOGO is the best language for mornings you've woken desperately needing to draw a box inside a circle. Not so much for those mornings, you need to implement an HTTP client.

Other myths "prolog doesn't scale".. least will be busted that whenever a lisp program (that scales according to whatever "scale" means) is running on a lisp-in-prolog (like WAM-CL)

Practical reasons:

Several decades of Common Lisp development libraries can, within a matter of hours, be translated to useable Prolog development libraries.

Also, DAYDREAMER, Knowledge Machine, SWALE, and CYC might perform differently and be more practical at non-toy domains.

[burs...@gmail.com]

Thats an interesting statement. Like 6 months ago, I noticed the
LipsWorks has a Prolog. It even seems that Common Prolog has the
normal Prolog syntax (probably outdated, not really ISO):

KnowledgeWorks® and Prolog User Guide
http://www.lispworks.com/documentation/lw60/KW-W/html/kwprolog-w.htm

A.10 Edinburgh Syntax
http://www.lispworks.com/documentation/lw60/KW-W/html/kwprolog-w-198.htm

Do you say Prolog systems like SWI-Prolog, which are not
compiled rather interpreter, can beat such Prolog in lisp?
Do you ahve some examples and benchmarks.

I would like to run my simple core benchmark suite,
did not yet have time to install lisp, and maybe some
required extensions. I am also not that fluent in lisp.

[j4n bur53]

There is also a lisp / prolog hybrid, called shen:

http://shenlanguage.org/

http://shenlanguage.org/learn-shen/index.html#8%20Shen%20Prolog

I could see some benchmarks for this system, some
years ago, and it was horribly slow.

But its nevertheless a charming effort.

burs...@gmail.com schrieb:

[burs...@gmail.com]

SWISH Einstein Riddle:
35,967 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 5718576 Lips)

Shen Professional Edition 14 - running under Common Lisp, implementation: SBCL
prolog-tests: (load "einstein.shen") = loadedeinsteins_riddle
run time: 0.062000274658203125 secs
https://groups.google.com/d/msg/qilang/PpVKzRzgFk4/X5rMn2odEQAJ

[Douglas R. Miles/LogicMoo]

It was not responsible of me claim the SWI-Prolog will be faster all the various prolog's-in-lisp.


But in general, I have not encountered a prolog-in-lisp that doesn't end up making Prolog frames correspond to Lisp environment frames. Such implementations, so often, do it for good feature-istic reasons even beyond that it made the implementation much easier for them to code.

The feature being is you can mix you lisp and prolog code inline. But as a downside, unless both frame implementations (Lisp lexical frames and Prolog necks) are tail call optimized into the same looped construct, one environment will interfere with the other. Meaning the performance (or amount of consumed stack) caused by one of two languages (Lisp or Prolog) will likely have been affected adversely by trying to properly maintain the others.

An easy example is when you imagine a tail optimized Prolog predicate that is calling a C function that calls a different tail optimized Prolog predicate. Although, this is not a big problem for C because C is not maintaining lexical frames.

To be fair a prolog-in-lisp doesn't have to do things the way I described. Old EcoLisp (now called ECL) and https://github.com/sjl/temperance and (perhaps) so does Shen implement a Prolog abstract machine to maintain the lisp environment state. So that when calling Lisp-based coded functions it doesn't interfere (and visa versa). The problem for me (mentioned above about Shen) is how much Lisp or Prolog language that got sacrificed in the meanwhile.

Also, if either Prolog or Lisp did a good transpilation first all this would be mute. But how good does that transpilation have to be?

But also, how good are current prolog-in-lisps really? Given the bar I am moving and setting (about doing both languages fully as well and mixing functions) it makes it hard to really say. Still knowing that a certain prolog-in-lisp outperforms some prolog-in-c's would be a tremendous game changer in my thinking.


Here are two non-intuitive pieces of information (I still dont know quite what to do with) but involve PowerLOOM and CYC which are both lisp programs that need to do *lots* of non-deterministic backtracking so I categorize this as "prolog-in-lisp" "related".


PowerLOOM runs faster (and less memory) when you translate the Lisp sources to C++ sources than it does on SBCL. At least that is what one of its developers told me in a private email a year or two ago when I was considering running the Lisp version.

CYC runs 10-25% faster at its internal CycLOPS benchmarks (though at least twice as much memory) when you translate the Lisp sources to Java sources than it does even on the most expensive license of AllegroCL. Not only that, it starts up in 90 seconds instead of 300 seconds when loading its "knowledge base" from files.


I don't know what these things are telling us.