Greetings! Just dreaming of the distant (possible) future and how one
might get there. I'm wondering whether there are any
scheme -> common lisp
emacs lisp -> common lisp
islisp -> common lisp
source translators available. If not, I'm interested in exploring the
difficulty of implementing such. I'm also interested in which dialect
is more suitable for hosting the others, if any.
Take care,
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
> * Camm Maguire <····@raunaprq.pbz> [2004-11-17 11:15:28 -0500]:
>
> Greetings! Just dreaming of the distant (possible) future and how one
> might get there. I'm wondering whether there are any
>
> scheme -> common lisp
> emacs lisp -> common lisp
CLOCC/CLLIB/elisp.lisp allows loading and executing elisp code in CL.
I tested it with emacs calendar.
> islisp -> common lisp
>
> source translators available. If not, I'm interested in exploring the
> difficulty of implementing such. I'm also interested in which dialect
> is more suitable for hosting the others, if any.
--
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
(let ((a "(let ((a %c%s%c)) (format a 34 a 34))")) (format a 34 a 34))
Camm Maguire wrote:
> I'm wondering whether there are any
>
> scheme -> common lisp
> emacs lisp -> common lisp
> islisp -> common lisp
>
> source translators available.
About the ISLISP -> CL translator: Kent Pitman probably has/had an
implementation of an early ISLISP draft, running in a Common Lisp, in
the namespace of a single package. This is quite straightforward to
implement, since ISLISP is roughly a subset of CL.
The Scheme -> CL translator from Jonathan Rees is available at
http://pluto.mumble.net/~jar/pseudoscheme/
Scheme -> CL translators are faced with two big problems:
- call-with-current-continuation is impossible to implement, because
CL has no primitives for copying the whole stack.
- Tail recursion elimination is a mandatory requirement for Scheme,
but not for CL. This means that CL implementations that are based
on C or the Java VM cannot fulfill this requirement. However, CL
implementations that are based on the .NET CLR and which optimize
tail recursion the way Scheme wants it would not have this problem.
Bruno
Bruno Haible <·····@clisp.org> writes:
> Scheme -> CL translators are faced with two big problems:
> - call-with-current-continuation is impossible to implement, because
> CL has no primitives for copying the whole stack.
Impossible is a strong word. I agree that a direct translation of
call-with-current-continuation is not possible. But of course it is
possible[1] to write a scheme compiler in common lisp that performs
the CPS transformation on the scheme source to remove calls to
call-with-current-continuation, such that the cl runtime would not
need to provide call/cc services.
-russ
[1] and relatively easy, if you have read Lisp in Small Pieces or
Essentials of Programming Languages, or PAIP.
On 17 Nov 2004 17:00:31 GMT, Bruno Haible <·····@clisp.org> wrote:
> The Scheme -> CL translator from Jonathan Rees is available at
> http://pluto.mumble.net/~jar/pseudoscheme/
>
> Scheme -> CL translators are faced with two big problems:
> - call-with-current-continuation is impossible to implement, because
> CL has no primitives for copying the whole stack.
> - Tail recursion elimination is a mandatory requirement for Scheme,
> but not for CL. This means that CL implementations that are based
> on C or the Java VM cannot fulfill this requirement. However, CL
> implementations that are based on the .NET CLR and which optimize
> tail recursion the way Scheme wants it would not have this problem.
See also
<http://www.ccs.neu.edu/home/dorai/scmxlate/scm2cl.html>
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Camm Maguire <····@enhanced.com> writes:
> I'm wondering whether there are any
>
> scheme -> common lisp
> emacs lisp -> common lisp
> islisp -> common lisp
>
> source translators available. If not, I'm interested in exploring
> the difficulty of implementing such.
I guess this depends on whether we want the result to be accurate or
maintainable. These goals are both possible but mutually incompatible.
In the case of Scheme -> CL I expect major difficulties with tail
calls, continuations, and perhaps even with distinguishing #f from '()
and nil.
It's a bit easier if we can assume that the CL implementation
optimizes all tail calls, which is non-portable. In this case
continuations still cause trouble: CPS transformation reqiures to
transform all code which calls transformed functions. For example you
can't use CL compiled mapcar with functions translated from Scheme,
without reimplementing mapcar. In general you can't mix code
translated from Scheme with arbitrary Lisp libraries, and you must
reimplement things like let, let*, lambda, cond etc.
If the CL implementation doesn't optimize all tail calls, it gets yet
worse. I think it would need the "trampoline" approach, as used in C,
where each function returns the next function to call, and a driver
loop forever calls the function and then its result etc., and
arguments are passed in some other place.
The #f vs. '() issue seems silly... It implies that all conditionals
in the resulting code would have to use custom constructs instead of
direct CL conditionals. Easy to do only if the result will not be
later edited by hand as CL code, or if we don't care whether it's
fully correct.
PS. For translation in the opposite direction, from CL to Scheme,
an issue comparable to tail calls is multiple values. CL is more
demanding in this respect: in cases where a single result is expected
but more have been provided, CL requires to take the first result,
where Scheme treats this as an error. So CL multiple values can't be
just built on top of Scheme multiple values, and without sophisticated
global analysis most function calls would have to have awkward code
generated which explicitly checks the number of results.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> In the case of Scheme -> CL I expect major difficulties with tail
> calls, continuations, and perhaps even with distinguishing #f from '()
> and nil.
Agreed.
> It's a bit easier if we can assume that the CL implementation
> optimizes all tail calls, which is non-portable.
This statement has implications that forms a recipe for disaster.
Tail call "optimization" is a meaningless term when used in mixed
company (CL/Scheme) because it means different things to both
groups. Scheme requires "space efficient tail recursion", which
is a completely different beast than the tail-merging that CL
implementations do. So in response to your statement, it is in
fact _never_ easier, because we can never assume that CL implementations
optimize all tail calls in the way Scheme requires.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig wrote:
> This statement has implications that forms a recipe for disaster.
> Tail call "optimization" is a meaningless term when used in mixed
> company (CL/Scheme) because it means different things to both
> groups. Scheme requires "space efficient tail recursion", which
> is a completely different beast than the tail-merging that CL
> implementations do. So in response to your statement, it is in
> fact _never_ easier, because we can never assume that CL implementations
> optimize all tail calls in the way Scheme requires.
I don't think that tail calls would be among the most pressing problems
for a unification of Common Lisp and Scheme. At least my impression is
that many Scheme _implementations_ also don't optimize all tail calls in
the way the Scheme _specification_ requires, and this seems to be
acceptable for Scheme programmers in practice. (But I may be wrong here.)
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Pascal Costanza <········@web.de> writes:
> I don't think that tail calls would be among the most pressing
> problems for a unification of Common Lisp and Scheme. At least my
> impression is that many Scheme _implementations_ also don't optimize
> all tail calls in the way the Scheme _specification_ requires, and
> this seems to be acceptable for Scheme programmers in practice. (But I
> may be wrong here.)
A language that claims to be Scheme, but doesn't support full
tail-call optimization is in serious violation of the standard. It is
essentially impossible to program in continuation-passing style
without having full tail-call optimization, and this is a common
technique in Scheme.
Pascal Costanza wrote:
> I don't think that tail calls would be among the most pressing problems
> for a unification of Common Lisp and Scheme.
I agree.
> At least my impression is
> that many Scheme _implementations_ also don't optimize all tail calls in
> the way the Scheme _specification_ requires, and this seems to be
> acceptable for Scheme programmers in practice. (But I may be wrong here.)
I wouldn't say "many". I can only think of one serious implementation
that doesn't guarantee Proper Tail Recursion in all circumstances.
(But there is almost certainly more examples) This is acceptable for
programmers using that implementation. Most Scheme programmers would
hesitate to call it a Scheme though, if the implementation lacks this
property.
--
Jens Axel Søgaard
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> In the case of Scheme -> CL I expect major difficulties with tail
> calls [..]
Giving this about 10 seconds of thought, couldn't this be solved
rather easily by a translation in style with this:
(define (length x accumulator)
(if (null x)
accumulator
(length (cdr x) (1+ accumulator))))
to this (ignoring issues of unintended name capture):
(defun length (x accumulator)
(tagbody length
(return-from length
(if (null x)
accumulator
(progn
(setf x (cdr x)
accumulator (1+ accumulator))
(go length))))))
the crucial point being the translation of the tail-call,
(length (cdr x) (1+ accumulator))
to
(progn
(setf x (cdr x)
accumulator (1+ accumulator))
(go length))
which to me seems like a simple translation that works the way Scheme
mandates, completely independently of CL implementation details. It
breaks any dynamic scope set up by the function body, of course, but
that's just the way things are; presumably the Scheme spec deals with
this somehow.
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> Giving this about 10 seconds of thought, couldn't this be solved
> rather easily by a translation in style with this:
[...]
No, because it applies only to tail recursion, not to tail calls to
other functions (which may even include statically unknown functions,
passed as first-class values).
Proper tail calls in a language without guarantees about tail calls
can only be implemented by changing the function calling protocol.
I know two portable styles: the "trampoline" described earlier
and putting the whole program in one function with a main loop.
In both cases you make your own stack for passing parameters and
locals.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> No, because it applies only to tail recursion, not to tail calls to
> other functions (which may even include statically unknown
> functions, passed as first-class values).
Ok, I didn't know Scheme mandated also non-recursive tail calls be
merged.
If you'll allow we to throw out some more mediocre ideas: isn't it a
reasonable assumption that the merging is only really necessary when
there's a cycle in the call graph? If so, perhaps it'd be possible to
detect this, for example if the function-body wrapping from before is
extended like so:
(defun length (x accumulator)
(let ((length t))
(declare (special length))
(loop
(setf (values x accumulator)
(tagbody length
(catch 'length
(return-from length
<scheme-body>)))))))
Now, inside scheme-body, each recursive tail-call is like before, e.g.
(progn
(setf x (cdr x)
accumulator (1+ accumulator))
(go length))
and non-recursive tail-calls become
(if (symbol-value 'length)
(throw 'length (values (cdr x) (1+ accumulator)))
(length (cdr x) (1+ accumulator)))
The intent being that the stack is unwound by the throw case upon the
first cyclic tail-call.
Might this be viable at all? It's not exactly wonderful from a
performance perspective, but could sort-of work, if only as a
fall-back for uncooperative implementations?
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> writes:
> If you'll allow we to throw out some more mediocre ideas: isn't it a
> reasonable assumption that the merging is only really necessary when
> there's a cycle in the call graph?
Yes or no, depending on how do you compare nodes in case of closures.
This can be a different function object each time, they can be created
and recycled forever as the program goes, with no repetition. Of course
some code address inside a closure will repeat, because the number of
different code addresses is smaller than the amount of memory.
BTW, Scheme also requires tail calls to 'eval' to not accumulate the
stack.
There is no need to detect exactly the point of a cycle however, no
matter how it is defined. You reminded me of another technique that I
forgot, used in some Haskell implementation on JVM. On each tail call
a global counter is incremented, and when it reaches some threshold
value, an exception is thrown which clears the system stack, and
computation restarts from some toplevel driver loop.
So local values are stored on a custom stack, like in the trampoline
style. This may be more efficient. On the fast path it uses an
increment, a conditional on the incremented value (not taken), and a
function call which remains being a call to a known function if the
target was known in the source. The trampoline style uses a function
return and a call which is always indirect.
This might even be the best way for CL, like it is for Java.
It reminds me of http://home.pipeline.com/~hbaker1/CheneyMTA.html
for C, which does not waste stack space between those unused return
addresses, but puts the young generation of the GC there. Instead
of a counter, it checks whether the stack pointer address is close to
a limit. In effect the control stack is stored on the heap, which is
constructed on the stack again :-)
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> So local values are stored on a custom stack, like in the trampoline
> style.
Ah, I was a bit wrong: contrary to the trampolined style, in the fast
path function arguments can be passed normally! Only when the stack is
being cleared, they must be transported to the driver loop along with
the function to call.
OTOH the program must still undergo complete CPS transformation, and
thus local variables and return addresses of non-tail calls must be
stored on an explicitly managed stack (except for functions which
don't contain non-tail calls), like in the trampoline style.
Non-tail calls are realized like this: remember the state on explicit
stack, perform a tail call which passes the continuation (return
address) as an additional argument, and code of the continuation
is placed in a separate target language function.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk wrote:
> PS. For translation in the opposite direction, from CL to Scheme,
> an issue comparable to tail calls is multiple values. CL is more
> demanding in this respect: in cases where a single result is expected
> but more have been provided, CL requires to take the first result,
> where Scheme treats this as an error. So CL multiple values can't be
> just built on top of Scheme multiple values, and without sophisticated
> global analysis most function calls would have to have awkward code
> generated which explicitly checks the number of results.
Special variables are the first thing I would miss if someone made me use
Scheme. Not sure if they can be easily faked in Scheme.
In article <··················@yahoo.com>,
Neo-LISPer <··········@yahoo.com> wrote:
> Marcin 'Qrczak' Kowalczyk wrote:
>
> > PS. For translation in the opposite direction, from CL to Scheme,
> > an issue comparable to tail calls is multiple values. CL is more
> > demanding in this respect: in cases where a single result is expected
> > but more have been provided, CL requires to take the first result,
> > where Scheme treats this as an error. So CL multiple values can't be
> > just built on top of Scheme multiple values, and without sophisticated
> > global analysis most function calls would have to have awkward code
> > generated which explicitly checks the number of results.
>
> Special variables are the first thing I would miss if someone made me use
> Scheme. Not sure if they can be easily faked in Scheme.
Easy! just use a macro to.... uh-oh. never mind!
:)
kenny
Kenneth Tilton wrote:
>>Special variables are the first thing I would miss if someone made me use
>>Scheme. Not sure if they can be easily faked in Scheme.
> Easy! just use a macro to.... uh-oh. never mind!
Easy! The Revised Progress Report on R6RS states that R6RS will
have a syntax-case like macro system.
<http://www.schemers.org/Documents/Standards/Charter/2004-10-13.pdf>
--
Jens Axel Søgaard
In article <·······················@dread12.news.tele.dk>,
Jens Axel S�gaard <······@soegaard.net> wrote:
> Kenneth Tilton wrote:
>
> >>Special variables are the first thing I would miss if someone made me use
> >>Scheme. Not sure if they can be easily faked in Scheme.
>
> > Easy! just use a macro to.... uh-oh. never mind!
>
> Easy! The Revised Progress Report on R6RS states that R6RS will
> have a syntax-case like macro system.
>
> <http://www.schemers.org/Documents/Standards/Charter/2004-10-13.pdf>
Too late. Common Lisp won. Now it is off with their heads.
kenny
Kenneth Tilton wrote:
> In article <·······················@dread12.news.tele.dk>,
> Jens Axel S�gaard <······@soegaard.net> wrote:
>
>
>>Easy! The Revised Progress Report on R6RS states that R6RS will
>>have a syntax-case like macro system.
>>
>><http://www.schemers.org/Documents/Standards/Charter/2004-10-13.pdf>
>
>
> Too late. Common Lisp won. Now it is off with their heads.
>
> kenny
What did Common Lisp win exactly? The congeniality award?
Lynn
In article <············@hood.uits.indiana.edu>,
Lynn Winebarger <········@indiana.edu> wrote:
> Kenneth Tilton wrote:
> > In article <·······················@dread12.news.tele.dk>,
> > Jens Axel S�gaard <······@soegaard.net> wrote:
> >
> >
> >>Easy! The Revised Progress Report on R6RS states that R6RS will
> >>have a syntax-case like macro system.
> >>
> >><http://www.schemers.org/Documents/Standards/Charter/2004-10-13.pdf>
> >
> >
> > Too late. Common Lisp won. Now it is off with their heads.
> >
> > kenny
>
> What did Common Lisp win exactly? The congeniality award?
>
Well, after Scheme lost all that weight so it could fit into that itsy
beeny teeny weeny bikini of a spec we knew we did not have a chance in
the swimsuit competition.
Fortunately real programmers score practicality higher, so our runaway
win in the new weightlifting segment gave us the Language du Jour crown.
Ruby took congeniality. :)
kenny
Camm Maguire wrote:
> Greetings! Just dreaming of the distant (possible) future and how one
> might get there. I'm wondering whether there are any
>
> scheme -> common lisp
pseudoscheme comes close, as far as I can see.
> emacs lisp -> common lisp
There is a project called Emacs Common Lisp at
http://www.lisp.se/emacs-cl/ - don't know much about it.
> islisp -> common lisp
ISLISP was specifically designed to be culturally compatible with Common
Lisp (as Kent Pitman has stated many times here in c.l.l). So this
should be just a matter of writing a compatibility library for Common
Lisp. I don't know if anyone has done this, but it doesn't seem to be
intellectually challenging enough.
> source translators available. If not, I'm interested in exploring the
> difficulty of implementing such. I'm also interested in which dialect
> is more suitable for hosting the others, if any.
I don't know enough about Emacs Lisp to comment on the possibilities here.
Scheme and Common Lisp are culturally very different. It would be
possible to implement one language in the other, but it wouldn't buy you
much AFAICS. The potential gain of embedding one language in the other
is to be able to seamlessly access libraries of the respective other
language. However, there are a few fundamental technical differences
that make this hard or impossible, and would buy you essentially "just
another implementation" of one or the other language, without
considerable synergistic effects. The most notable technical
differences, AFAICT, are Lisp-1 vs. Lisp-2 and inclusion/exclusion of
call/cc.
- Lisp-1 vs. Lisp-2: Here the problem is that modules/packages that
import definitions from Common Lisp code into Scheme code have to define
some arbitrary rules to select the symbol value vs. the symbol function.
I think the devil lies in the details here.
- There is a problem to make Scheme's call/cc and Common Lisp's
unwind-protect work together well. See
http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations.html
for more details.
"Culturally different" also means that it's hard to solve the problems
by implementing technical solutions for these mismatches. Schemers won't
accept ad-hoc solutions because their goal seems to be to make
everything fit an idealized language based on the lambda calculus
whereas Common Lispers won't accept constructs with nice mathematical
properties that don't cover important practical cases. This creates an
important gap that is hard to cross. (See
http://makeashorterlink.com/?E2E9254F6 for a list of major differences
between Scheme and Common Lisp.)
Maybe it's good that these two very different languages exist. The
respective other language can be regarded as a good lightning rod for
features that are considered politically incorrect in one's own
language. ;-)
Pascal
--
Pascal Costanza University of Bonn
·········@p-cos.net Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
>> islisp -> common lisp
>
> ISLISP was specifically designed to be culturally compatible with Common
> Lisp (as Kent Pitman has stated many times here in c.l.l). So this should
> be just a matter of writing a compatibility library for Common Lisp. I
> don't know if anyone has done this, but it doesn't seem to be
> intellectually challenging enough.
(defun islisp->cl (exp) exp)
is not too far from a real translator. Even it's definitely not true, islisp
can be viewed as a compatible subset of CLtL.
Except perhaps for dynamic variables that have specific Special Forms
(DYNAMIC, SET-DYNAMIC, DYNAMIC-LET),
islisp code nearly runs out-of-box on a CLtL environment and library is
80-90% the same.
But I'm not sure that a one-size-fits-all Lisp (CL) meets all needs. My
OpenLisp is for example perfect to execute interpreted dynamic Web pages.
One of the ISLISP goals was to allow a very efficient interpreters. Check
http://www.eligis.com/benchmarks.html to sse what I mean.
On PII 400Mhz, Gabriel's benchs run in 37s and remember that ISLISP has only
primitive functions (no CADR for exemple).
Christian
No, ISLISP is *NOT* a super-Lisp. It is just a published ISO standard
(ISO:IEC 13816:1997) with a different goal than CLtL.
Clearly, CLtL is more complete and more powerful than ISLISP has many more
language features and libraries.
My contribution was only to say that ISLISP has been made to fill a need:
smaller language that allows small and fast interperter/compiler.
CLtL has an interperter but is mainly taylored for compilation.
As a comparison, you can choose Java and the full JDK for your server
components but SuperWaba (a Java subset) is far better on your PDA (Pocket
PC or Palm OS).
The second goal of ISLISP was to easily go from ISLISP to CLtL if your
projet comes bigger and needs more features.
This answer the question:
islisp -> common lisp.
"Christopher C. Stacy" <······@news.dtpq.com> wrote in message
··················@news.dtpq.com...
>I missed: what is the point of this super-Lisp?
>
>