Proposal: Shen should take care of TCO
Dominikus
vasil
transformer will remove the need of TCO from requirements to target
platform, will remove requirements of partial application and so on. KL
code after transformation may be easily mapped even to C language with
some GC library (like Boehm GC library).
> --
> You received this message because you are subscribed to the Google
> Groups "Qilang" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/qilang/-/strpKkv3ixkJ.
> To post to this group, send email to qil...@googlegroups.com.
> To unsubscribe from this group, send email to
> qilang+un...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/qilang?hl=en.
Mark Tarver
easy, so 'recur' doesn't add much except to add a primitive that
really belongs to a different paradigm. The more challenging bit is
to identify the proper construction in the host language that performs
the iteration.
Regarding partial application, you can of course map all (defun f (x
y) ....) to
(defun f (x) (lambda y ...)). Indeed this was tried in a prelease
version of Shen and it was found to have undesirable performance
consequences so another approach was found (see the document on
porting where three different approaches were discussed for partial
application).
The upshot was that I decided that the question of how best to
implement partial application was a platform specific question and
hence it was a mistake to try to anticipate the best solution by hard-
wiring Shen in one direction.
Mark
>
> - Show quoted text -
Ramil Farkhshatov
> The specification of Shen says that Shen's mission is to be an
> "ultra-portable version of Qi". This is contrasted by the requirement that
> "tail recursion optimisation is a must" for Kl implementations.
>
> I think it is easier to introduce a primitve such as "recur" in Kl (as is
> done in Clojure) to explicitly indicate tail recursion. Implementing
> "recur" in any "traditional" language like JavaScript, Ruby, Python etc. is
> a breeze, since iteration can be used. Without "recur" each and every
> implementor for JavaScript, Ruby, Python etc. has to implement some code
> that does an tail call analysis and optimization. This risks buggy and
> unnecessary complex implementations. Why is TCA and TCO not done by Shen?
> Shen has Prolog and all the tools required on board. Shen could generate Kl
> code with all tail calls being identified by "recur".
It's not hard to write kl->kl translator that adds `recur` in
appropriate places. It you're not afraid of horrible code you can look
how translator.shen of shen-js deals with tail recursive calls. For new
shen-js I've made kl->kl translator implementing partial application
support.
> Along the same line of argumentation: Why must Kl support partial
> application? Shen could offer a standardized solution via Kl!
> If TCO and partial application would be removed from Kl (but not Shen), the
> only implementation "challenge" is the dual namespace model and possibly
> error handling. Other than that, implementing Kl in any target language
> would be simple, easy and fun.
>
> What do you think?
I think that with current Shen specification one can choose the best
suitable for host language methods of partial application and TCO.
Standardized solution might be inefficient on some platforms.
Jan Burse
and some clause instantiation techniques give much more speed
than TCO. Especially for predicates such as member/2 etc..
Einsteins riddle you mention on the Wiki can be solved
not only by 300 kLIPS, ordinary Prolog systems do it in 3
mLIPS and above. Already for a couple of decades.
https://plus.google.com/u/0/b/103259555581227445618/103259555581227445618/posts/Wien54QZFpW
I didn't try YAP Prolog, which is one of the fastest Prologs
around, but I guess it will do it with around 30 mLIPS.
Mark Tarver schrieb:
Mark Tarver
lower level of instruction closer to machine code or assembler.
Mark
On Feb 29, 7:23 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> Clause indexing and a couple of resource elimination techniques
> and some clause instantiation techniques give much more speed
> than TCO. Especially for predicates such as member/2 etc..
>
> Einsteins riddle you mention on the Wiki can be solved
> not only by 300 kLIPS, ordinary Prolog systems do it in 3
> mLIPS and above. Already for a couple of decades.
>
>
> >> - Show quoted text -- Hide quoted text -
Dominikus
Am Mittwoch, 29. Februar 2012 18:34:02 UTC+1 schrieb Ramil Farkhshatov:
Am Mittwoch, 29. Februar 2012 18:34:02 UTC+1 schrieb Ramil Farkhshatov:
Jan Burse
> To get that kind of performance you need to compile Prolog into a
> lower level of instruction closer to machine code or assembler.
Not necessarely, Jekejeke and SWI don't use machine code, both
use an intermediate form. And you get ~3 mLIPS.
YAP uses machine code heavily and even some JIT specialization.
As a result it is usually ~10 times faster.
Mark Tarver
compile, the faster the performance. Shen is not in that category.
Mark
Jan Burse
> compile, the faster the performance. Shen is not in that category.
>
> Mark
Just did some Android/Dalvik metal testing. The
devices I used were running 1 GHz processors. I
used my Jekejeke Prolog interpreter again for
testing. The results are very disappointing:
Device AnTuTu Suite
HTC Wildfire 922 852'581 ms
Acer A501 4'971 109'613 ms
HTC One X 9'442 70'130 ms
MacBook Pro N/A 1'271 ms
AnTuTu is a general device benachmark, the higher
numbers the better. The suite is my set of test
programs among one finds usual Prolog stuff such
as nrev, queens, etc..
So a PC/JDK combination is 100-1000 faster than
a Anroid/Dalvik combination.
https://plus.google.com/u/0/103259555581227445618/posts/9uaE3vSyPnx
Just to lower the expectations for Android/Dalvik
in case there were some. The future might look
different though.
Bye