LISP to Python translator?
Joseph J. Strout
equivalent Python code.
This shouldn't be too difficult, and naturally I'll write it myself if nobody
speaks up, but I'm hoping somebody has already done it -- no sense reinventing
the wheel and all that.
Thanks,
-- Joe (j...@strout.net)
Magnus L. Hetland
> I need a program (preferably in Python!) which converts LISP code into
> equivalent Python code.
>
> This shouldn't be too difficult, and naturally I'll write it myself if nobody
> speaks up, but I'm hoping somebody has already done it -- no sense reinventing
> the wheel and all that.
At least I would recommend you John Aycocks "Compiling Little
Languages in Python." It's a very Pythonesque little framework for
parsing in Python, and it should be trivial to implement a lisp parser
in it. (Lisp is pretty trivial to parse in the first place, isn't it ;)
>
> Thanks,
> -- Joe (j...@strout.net)
--
Magnus
Lie
Hetland www.pvv.org/arcadia <arc...@pvv.org>
John Mitchell
> "Joseph J. Strout" <jst...@ucsd.edu> writes:
>
> > I need a program (preferably in Python!) which converts LISP code into
> > equivalent Python code.
>
> At least I would recommend you John Aycocks "Compiling Little
> Languages in Python." It's a very Pythonesque little framework for
> parsing in Python, and it should be trivial to implement a lisp parser
> in it. (Lisp is pretty trivial to parse in the first place, isn't it ;)
This paper was presented in the Seventh Intl. Python Conference. The
paper and framework is available from Mr. Aycocks' page:
http://www.csr.UVic.CA/~aycock/python/
(new version, 0.2, was released a week ago: Jan 19, 1999)
- j
Joe Strout
John Mitchell <jo...@magnet.com> wrote:
Thank you both for the tips. I'm hoping to make something that makes
Python code out of LISP code, however, not Python code that can
interpret LISP code.
Ideally, we'll be able to take a LISP file, run it through the
converter, and get a Python module out. The functions defined therein
should be callable from other Python code, just as if they'd been
defined in Python in the first place.
I have a start on this now. It's not pretty, but it does appear to be
working. If anyone else is interested -- especially if you have much
experience in LISP (which I do not) -- please drop me a line
(j...@strout.net).
Cheers,
-- Joe
Lyn A Headley
"Joseph J. Strout" <jst...@ucsd.edu> writes:
> I need a program (preferably in Python!) which converts LISP code into
> equivalent Python code.
>
> This shouldn't be too difficult, and naturally I'll write it myself if nobody
Sure. no problem. Shouldn't take much more than a man-year. Unless
you care about execution speed...
-Lyn
Lars Marius Garshol
* Joseph J. Strout
|
| I need a program (preferably in Python!) which converts LISP code
| into equivalent Python code.
|
| This shouldn't be too difficult,
As far as I can see it would be horribly difficult, and more or less
amount to implementing a Common Lisp in Python. What would you do
about stuff like generic methods in CLOS or advanced macros?
Or were you thinking about Scheme? Even in that case it would be
difficult, since Scheme programs often use closures to make objects
and this seems to me very difficult to translate.
--Lars M.
Lars Marius Garshol
* Magnus L. Hetland
|
| (Lisp is pretty trivial to parse in the first place, isn't it ;)
The basic language is easy, but you'd also have to parse format
strings and deal with things like read-macros. Read-macros aren't very
common, I think, but format strings are.
--Lars M.
Steven D. Majewski
On Wed, 27 Jan 1999, Joe Strout wrote:
>
> Thank you both for the tips. I'm hoping to make something that makes
> Python code out of LISP code, however, not Python code that can
> interpret LISP code.
>
> Ideally, we'll be able to take a LISP file, run it through the
> converter, and get a Python module out. The functions defined therein
> should be callable from other Python code, just as if they'd been
> defined in Python in the first place.
>
> I have a start on this now. It's not pretty, but it does appear to be
> working. If anyone else is interested -- especially if you have much
> experience in LISP (which I do not) -- please drop me a line
> (j...@strout.net).
I think translating trivial Lisp programs to Python is pretty trivial.
But if your Lisp code includes the use of features like macros and
readtables, that don't have a simple Python analogue, it could get
pretty hairy. Beware of the 80/20 rule: it's probable that getting
your translator to translate 80% of the Lisp code will take 20% of
the time -- and getting it to translate that other 20% will take
80% if the time.
Python, Lisp and PostScript are all pretty dynamic languages.
I mention PostScript because this problem has been discussed often
from that POV: analyzing arbitrary PostScript code untimately
requires a full PostScript interpreter. A restricted subset or
following document conventions makes it a simpler problem.
( And that's why we got PDF -- a kind of restricted, static PS subset
with a very strict document object model structure. )
As Dan Connelly used to ask: How do you find the last word on the
sixth page of a PostScript document without running it thru a PS
interpreter?
Some (perhaps mutually contradictory) things to consider:
* Only do the easy 80%: your code base may not make heavy use of
some of these features, and you may be able to do part of the
conversion by hand. Have the conversion program tag these
exceptions for you. ( I've been assuming your talking Common
Lisp here and not Scheme, which is a smaller language. )
* The higher level translation you do, the less to have to
translate every Common Lisp idiom -- encapsulate some of the
places where "difficult" lisp code is used into higher level
Python functions. ( Of cource, at the extreme, this really
translates into reengineering the whole program -- basically
treating the Lisp version as a prototype for the Python version-2.
Sometimes not a bad idea -- sometimes figuring out WHAT to do takes
more time than coding. )
* If the existing Lisp code is better than prototype, then there
may be other ways to integrate Lisp and Python code -- Xerox ILU
for one example.
* Do the Lisp->Python translator in Lisp --
which means you can do macro expansion in Lisp and not have to
write a Lisp-Macro-Expander in Python.
* I've seen either a Lisp-2-Fortran converter -- or was it Fortran-2
Lisp -- probably in the CMU Lisp repository. You might take a
look at that. It was intended for translating mathematical code,
so it may only translate a subset. ( I know there are Scheme to
C compilers -- I don't know about Common Lisp. )
But again -- if your existing Lisp code base is a basic subset of
Lisp (which is even more likely if the authors aren't experienced
Lisp programmers), the 80% solution may be quite enough. Don't let
me scare you off if this solution will really work for you.
I've got a fair knowledge of both Lisp and Python, and I'm using
both in current projects, so I may be able to help if you've got
some specific questions about translating one idiom to the other.
---| Steven D. Majewski (804-982-0831) <sd...@Virginia.EDU> |---
---| Department of Molecular Physiology and Biological Physics |---
---| University of Virginia Health Sciences Center |---
---| P.O. Box 10011 Charlottesville, VA 22906-0011 |---
"Is sloppiness in speech caused by ignorance or apathy?
I don't know and I don't care." -- William Safire.
Steven D. Majewski
You can also use objects to make closures.
You could also use modules, dictionaries (as args to exec), code objects,
name mangling, nested lambda expressions, and a whole bunch of other
techniques (see the many previous threads on closures), some of which
might look pretty ugly, but if we're talking about automatic translation,
ugliness is no barrier.
But I definetely agree with your 1st paragraph. (see my other posting
in this thread. )
Magnus L. Hetland
> Thank you both for the tips.
Actually, they are the same. :)
> I'm hoping to make something that makes
> Python code out of LISP code, however, not Python code that can
> interpret LISP code.
I understood that, but the first step is to parse it into a syntax
tree. Then all you have to do is traverse it and generate Python code
as you go :)
>
> Ideally, we'll be able to take a LISP file, run it through the
> converter, and get a Python module out.
Exactly.
(setq x (* 1 2))
parses to a tree:
setq -+- x
|
+- * -+- 1
|
+- 2
Which you traverse. (post-order, for instance.) The multiplication is
put together like [left] + [right], the setq is put together like
[left] = [right]... It all boils down to
x = 1 + 2
Of course, not everything is easily translatable into Python, but the
general technique should be feasible. I have made it to translate
between a lisp-syntax language (KIF) and another representation
language (GOL) and it worked beautifully.
If you need more details (for instance on using the "Visitor" pattern)
just mail me.
Lars Marius Garshol
* Lars Marius Garshol
|
| Or were you thinking about Scheme? Even in that case it would be
| difficult, since Scheme programs often use closures to make objects
| and this seems to me very difficult to translate.
* Steven D. Majewski
|
| You can also use objects to make closures.
Sure, it's just that when you use Scheme to make objects it's not
obvious what you're doing. You define a function with a lot of other
functions inside it and one of those functions calls the other ones
when given a symbolic argument and a list of arguments. Doesn't really
stand out from normal procedural programs. And inheritance is
determined by the last else-branch in the dispatching function...
If you use one of the ready-made OO packages then maybe that makes it
easier. I don't really know how to attack this and personally I would
feel like using ILU rather than trying to solve this, but maybe I'm
just being thick-headed here.
--Lars M.
Steven D. Majewski
On 27 Jan 1999, Lars Marius Garshol wrote:
>
> * Lars Marius Garshol
> |
> | Or were you thinking about Scheme? Even in that case it would be
> | difficult, since Scheme programs often use closures to make objects
> | and this seems to me very difficult to translate.
>
> * Steven D. Majewski
> |
> | You can also use objects to make closures.
>
> Sure, it's just that when you use Scheme to make objects it's not
> obvious what you're doing. You define a function with a lot of other
> functions inside it and one of those functions calls the other ones
> when given a symbolic argument and a list of arguments. Doesn't really
> stand out from normal procedural programs. And inheritance is
> determined by the last else-branch in the dispatching function...
>
I was talking about using Python objects to implement Scheme closures.
Objects (a little blob of data with some code/methods attached) and
closures (a little blob of code with some data/variable-bindings attached)
are orthagonal but functionally equivalent. ( I did agree though that
the fact that one implementation might be a lot uglier than another
could be significant. )
> If you use one of the ready-made OO packages then maybe that makes it
> easier.
But if you're talking about Scheme OO packages --
[1] they do just that sort of inversion, and it can be done less
staticly than your discription above makes it sound.
[2] Re: "Doesn't really stand out..." : well, in Lisp or Scheme,
*everything* looks sort of like functional application -- even
(SEND OBJ MESSAGE arg1 arg2 ) or ( OBJ MESSAGE arg )
[That, IMHO, is both the power and the curse of Lisp.
On the one hand - no syntactical contextual clues.
On the other, no endless arguments about syntax because
everything looks the same. ]
> I don't really know how to attack this and personally I would
> feel like using ILU rather than trying to solve this, but maybe I'm
> just being thick-headed here.
No -- that's the point I was getting at in my other post.
Complete 100% translation of Common Lisp would be very difficult.
Restricting the problem -- either a subset of Lisp, or Scheme,
which is a smaller language would be easier. Scheme without
macros would be pretty simple. ( trivial in theory I think, but
still a good bit of work actually implementing or building translators
for every standard function. )
Lars Marius Garshol
* Steven D. Majewski
|
| I was talking about using Python objects to implement Scheme closures.
Then I misread you, sorry.
| Objects (a little blob of data with some code/methods attached) and
| closures (a little blob of code with some data/variable-bindings
| attached) are orthagonal but functionally equivalent.
Yup, I was just worried about how easy it would be to translate and
get this right. But maybe you're right that it isn't very hard. And I
agree that if you get this right then the rest will follow.
* Lars Marius Garshol
|
| I don't really know how to attack this and personally I would feel
| like using ILU rather than trying to solve this, but maybe I'm just
| being thick-headed here.
* Steven D. Majewski
|
| Restricting the problem -- either a subset of Lisp, or Scheme, which
| is a smaller language would be easier. Scheme without macros would
| be pretty simple.
OK, I'll take your word for it. :)
--Lars M.
Joe Strout
the "To," "Cc," and "Newsgroups" headers for details. ]]
I ran across a serious problem in my LISP-to-Python plans late
yesterday. It appears that in LISP, an expression like (CDR FOO)
returns a reference to the second element of the linked list pointed to
by FOO. Changing one of the resulting elements (via SETF or some such)
changes FOO, as they are composed of the same elements.
In Python, I was implementing lists as lists, and CAR as foo[1:].
But the Python slice operator produces a new list; changing one element
of foo[1:] does not change foo. This basic semantic difference is
likely to cause a whole lot of problems, I think. And as far as I
know, there is no way in Python to get a reference to a sublist without
doing an implicit copy.
I can still imagine writing a little LISP interpreter in Python; it
would wrap LISP datatypes (including symbols, lists, etc.) in a small
set of Python classes, and operate only on these. You'd pass it some
LISP code, and it would return a LISP result (though of course you
could make translators to and from Python datatypes). I'm not sure how
useful this would be, though.
Cheers,
-- Joe
P.S. What I have so far converts a few simple LISP forms into Python
syntax, then executes that code. I will probably stop development of
that approach at this point, so if you want to see it, let me know.
Steven D. Majewski
On Thu, 28 Jan 1999, Joe Strout wrote:
> I ran across a serious problem in my LISP-to-Python plans late
> yesterday. It appears that in LISP, an expression like (CDR FOO)
> returns a reference to the second element of the linked list pointed to
> by FOO. Changing one of the resulting elements (via SETF or some such)
> changes FOO, as they are composed of the same elements.
>
> In Python, I was implementing lists as lists, and CAR as foo[1:].
> But the Python slice operator produces a new list; changing one element
> of foo[1:] does not change foo. This basic semantic difference is
> likely to cause a whole lot of problems, I think. And as far as I
> know, there is no way in Python to get a reference to a sublist without
> doing an implicit copy.
yes -- Python lists aren't the same as Lisp lists -- they are more like
Lisp vectors. If you want something with the same semantics you need
to create a class.
class CONS:
def __init__(self, head, tail ):
self.car = head
self.cdr = tail
and probably either a bunch of methods or generic function
for CAR, CDR, and if your doing Common Lisp: RPLACA, RPLACD, PUSH, ...
Christian Tismer
>
> On Thu, 28 Jan 1999, Joe Strout wrote:
>
> > I ran across a serious problem in my LISP-to-Python plans late
> > yesterday. It appears that in LISP, an expression like (CDR FOO)
> > returns a reference to the second element of the linked list pointed to
> > by FOO. Changing one of the resulting elements (via SETF or some such)
> > changes FOO, as they are composed of the same elements.
> >
> > In Python, I was implementing lists as lists, and CAR as foo[1:].
> > But the Python slice operator produces a new list; changing one element
> > of foo[1:] does not change foo. This basic semantic difference is
> > likely to cause a whole lot of problems, I think. And as far as I
> > know, there is no way in Python to get a reference to a sublist without
> > doing an implicit copy.
>
> yes -- Python lists aren't the same as Lisp lists -- they are more like
> Lisp vectors. If you want something with the same semantics you need
> to create a class.
>
> class CONS:
> def __init__(self, head, tail ):
> self.car = head
> self.cdr = tail
>
> and probably either a bunch of methods or generic function
> for CAR, CDR, and if your doing Common Lisp: RPLACA, RPLACD, PUSH, ...
Without creating the overhead of a class, to me this looks most
natural:
I'd translate a Lisp list node into a tuple (car, cdr) where
cdr is again such a tuple, or None.
def cons(car, cdr): return (car, cdr)
Maybe I'm wrong. I'm no longer fluent with Lisp.
--
Christian Tismer :^) <mailto:tis...@appliedbiometrics.com>
Applied Biometrics GmbH : Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101 : *Starship* http://starship.skyport.net
10553 Berlin : PGP key -> http://pgp.ai.mit.edu/
we're tired of banana software - shipped green, ripens at home
Lyn A Headley
Christian Tismer <tis...@appliedbiometrics.com> writes:
> I'd translate a Lisp list node into a tuple (car, cdr) where
> cdr is again such a tuple, or None.
>
> def cons(car, cdr): return (car, cdr)
I think you are right, except for one thing: set-{car, cdr}!
The solution seems to be to use 2-elt *lists* as the pair
representation, instead of tuples. Sam Rushing gave me this idea.
-Lyn
Steven D. Majewski
Yes. Pair-lists or pair-tuples would likely be more effecient that
objects. However, I was thinking ahead to adding __repr__ methods
and some other stuff to make them more Lisp-like.
Hrvoje Niksic
> I need a program (preferably in Python!) which converts LISP code
> into equivalent Python code.
I wonder if this is possible at all. Python doesn't implement lexical
closures, and its scoping rules in general are totally different.
Also, idioms common in Lisp, such as use of `cons', would translate to
amazingly inefficient Python.
Magnus L. Hetland
> On Thu, 28 Jan 1999, Lyn A Headley wrote:
[...]
>
> Yes. Pair-lists or pair-tuples would likely be more effecient that
> objects. However, I was thinking ahead to adding __repr__ methods
> and some other stuff to make them more Lisp-like.
How important is it to you to make the resulting code idiomatic
Python? If it is not, then everything can be either an atom or a pair
(both implemented as classes) and then you just make a simple visitor
class for evaluating the resulting structures, with a lookup-table for
the builtin functions. This would of course be pretty close to a lisp
interpreter, but you would at least have a file with python code...
--
Magnus
Lie
Hetland http://arcadia.laiv.org <arc...@laiv.org>
tav...@connix.com
Joe Strout <j...@strout.net> wrote:
> I ran across a serious problem in my LISP-to-Python plans late
> yesterday. It appears that in LISP, an expression like (CDR FOO)
> returns a reference to the second element of the linked list pointed to
> by FOO. Changing one of the resulting elements (via SETF or some such)
> changes FOO, as they are composed of the same elements.
>
> In Python, I was implementing lists as lists, and CAR as foo[1:].
> But the Python slice operator produces a new list; changing one element
> of foo[1:] does not change foo. This basic semantic difference is
> likely to cause a whole lot of problems, I think. And as far as I
> know, there is no way in Python to get a reference to a sublist without
> doing an implicit copy.
>
I'm not much (or any, really) of a Lisper, but my understanding that Lisp
lists are really linked lists, while Python lists are really arrays. That's
the source of your semantic disconnect.
However, a while back Mark Lutz suggested a Python data structure that may let
you continue with this. He used tuples, but (python) lists would work just as
well. He called them tuple stacks.
The idea is to use nested sequences. So, for a lisp list (1 2 3) the
equivalent python would be [1 [ 2 [ 3 ] ] ]
cdr would be equivalent to l[0], car would be equivalent to l[1]. And this way
you're still passing around references rather than copies, so changes get
propagated.
-Chris
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Lars Marius Garshol
* tav...@connix.com
|
| I'm not much (or any, really) of a Lisper, but my understanding that
| Lisp lists are really linked lists,
They are, and in fact it's even more complicated than that, since
cons/car/cdr can be used to build all kinds of graph structures. cons
just creates what is called a cons pair (a,b) where car returns a and
cdr returns b.
It's usually used for lists, but there's no requirement that it be
used for this.
| However, a while back Mark Lutz suggested a Python data structure
| that may let you continue with this. He used tuples, but (python)
| lists would work just as well. He called them tuple stacks.
|
| The idea is to use nested sequences. So, for a lisp list (1 2 3) the
| equivalent python would be [1 [ 2 [ 3 ] ] ]
This is almost exactly the way lists in CL/Scheme are represented, so
this might in fact work in the general case as well. And I think
essentially the same has also been suggested by others already.
--Lars M.
Christian Tismer
> | equivalent python would be [1 [ 2 [ 3 ] ] ]
>
> This is almost exactly the way lists in CL/Scheme are represented, so
> this might in fact work in the general case as well. And I think
> essentially the same has also been suggested by others already.
greetings - others :-)
Christian Tismer
>
> Christian Tismer <tis...@appliedbiometrics.com> writes:
>
> > I'd translate a Lisp list node into a tuple (car, cdr) where
> > cdr is again such a tuple, or None.
> >
> > def cons(car, cdr): return (car, cdr)
>
> I think you are right, except for one thing: set-{car, cdr}!
> The solution seems to be to use 2-elt *lists* as the pair
> representation, instead of tuples. Sam Rushing gave me this idea.
Obviously true, I just tried to give the minimum solution for
passing cdr references around. If these must also be changed,
lists are of course needed. Anyway, this isn't very cheap. Python
tuples/lists are not optimized for piling them up, the main usage
is using their length. I assume that a good lisp structure would
be optimized in another way, since consing is so much more frequent?
You might also look into Sam's Lumberjack (I guess you have
already?). Sam started something great there to marry Scheme,
Python and continuations. But I fear the project will sleep
for a longer period due to his new employment...
ciao - chris
Magnus L. Hetland
> * tav...@connix.com
[...]
> | However, a while back Mark Lutz suggested a Python data structure
> | that may let you continue with this. He used tuples, but (python)
> | lists would work just as well. He called them tuple stacks.
> |
> | The idea is to use nested sequences. So, for a lisp list (1 2 3) the
> | equivalent python would be [1 [ 2 [ 3 ] ] ]
>
> This is almost exactly the way lists in CL/Scheme are represented, so
> this might in fact work in the general case as well. And I think
> essentially the same has also been suggested by others already.
Well -- it's not exactly correct, is it? All dotted pairs (or "cons
pairs" as you call them) have two elements, and then there is the
empty list... (Is it nil or null? I never remember the difference...)
At least, all the lists (or pairs) should have two elements, like
this:
[1, [2, [3, []]]]
Otherwise, (cdr (cdr (cdr (1 2 3)))), or (cdddr (1 2 3)) would make no
sense. Now it should return an empt list.
>
> --Lars M.
Lars Marius Garshol
* tav...@connix.com
|
| The idea is to use nested sequences. So, for a lisp list (1 2 3) the
| equivalent python would be [1 [ 2 [ 3 ] ] ]
* Lars Marius Garshol
|
| This is almost exactly the way lists in CL/Scheme are represented, so
| this might in fact work in the general case as well. And I think
| essentially the same has also been suggested by others already.
* Magnus L. Hetland
|
| Well -- it's not exactly correct, is it? All dotted pairs (or "cons
| pairs" as you call them) have two elements, and then there is the
| empty list... (Is it nil or null? I never remember the difference...)
It's nil.
| At least, all the lists (or pairs) should have two elements, like
| this:
|
| [1, [2, [3, []]]]
Sure, I took for granted that the representation would use two-member
lists. (Maybe I should have been explicit about that.)
--Lars M.
Martin von Loewis
> At least, all the lists (or pairs) should have two elements, like
> this:
>
> [1, [2, [3, []]]]
Since we are in picky mode right now <0.5wink>: shouldn't it be
[1, [2, [3, None]]]
I assume that nil is better represented by None than [].
Regards,
Martin
Hrvoje Niksic
> > At least, all the lists (or pairs) should have two elements, like
> > this:
> >
> > [1, [2, [3, []]]]
>
> Since we are in picky mode right now <0.5wink>: shouldn't it be
>
> [1, [2, [3, None]]]
>
> I assume that nil is better represented by None than [].
In Lisp, nil serves three purposes:
* The empty list, as demonstrated by (cdr '(1)).
* The value of "false", as demonstrated by (not t).
* The read-only symbol with the name "nil", as demonstrated by
(intern "nil").
Given that Python doesn't have the concept of symbols, and that the
an empty Python list is also "false", I think it's best to represent
nil as [], not None.
Magnus L. Hetland
> I assume that nil is better represented by None than [].
Isn't None more like the lisp "null" as opposed to the
empty-list/false "nil"?
Anyaway -- a list is terminated by an empty pair, not a non-value.
It's done in the same way in prolog:
[1,2,3,4,5] = [1|[2|[3|[4|[5|[]]]]]]
>
> Regards,
> Martin
Lars Marius Garshol
* Magnus L. Hetland
|
| Isn't None more like the lisp "null" as opposed to the
| empty-list/false "nil"?
In Common Lisp null is a function that tests whether its argument is
nil/false/empty-list or not. :)
| Anyaway -- a list is terminated by an empty pair, not a non-value.
I don't think so. At least, that doesn't seem to make much sense as an
implementation choice and I can't see that the difference would affect
the language semantics. (I'm dog tired, though, so I might well be
wrong.)
--Lars M.