Me:
> Python has the ability to do exactly
> what you're saying (domain language -> AST -> Python code or AST ->
> compiler). It's rarely needed (I've used it twice now in my six years
> or so of Python), so why should a language cater to make that
> easy at the expense of making frequent things harder?
As an example, here's a quick hack of a way to parse a simple
stack-based language and make a native Python function out
of it. I am the first to admit that it's ugly code, but it does work.
I am curious to see the equivalent code in Lisp. Here's the spec
All tokens are separated by whitespace (space, tab, newline, and
include vertical tab and form feed if you want).
Numbers are the standard IEEE floats (excepting NaN, Inf, etc)
and represented "as usual".
The operators are addition ("+"), subtraction ("-"), multiplication
("*"), division ("/"), and exponentiation ("**"). These are binary
operators only, so to get -b use 0 b - .
The variable names are of the form [A-Za-Z_][A-Za-z0-9_]*
and must be passed to the function when making the function call.
The order of names is the same as the order the names appear
in the RPN expression, so in "b a +" the function created takes
"b" as the first argument and "a" as the second.
Here's some examples of using the Python version
>>> import rpn
>>> f = rpn.compile("a 2 b * +")
>>> f(3, 4)
11.0
>>> f(a=4, b=3)
10.0
>>> f(b=4, a=3)
11.0
>>> g = rpn.compile("1 2 3 4 5 + + + + a **")
>>> g(2)
225.0
>>> h = rpn.compile("""
... 0 b -
... b 2 **
... 4 a c * *
... -
... 0.5 **
... +
... 2 a *
... /
... """)
>>> h(a=1, b=6, c=3)
-0.55051025721682212
>>> (-6+(6*6-4*1*3)**0.5)/(2*1)
-0.55051025721682212
>>>
Note that the code also handles errors reasonably well.
Eg, the following examples show that it correctly reports
the line numbers as given in the original string
>>> h(a="q", b=6, c=3)
Traceback (most recent call last):
File "<interactive input>", line 1, in ?
File "<RPN string RPN2>", line 3, in RPN2
TypeError: can't multiply sequence to non-int
>>> h(a=1, b="", c=3)
Traceback (most recent call last):
File "<interactive input>", line 1, in ?
File "<RPN string RPN2>", line 1, in RPN2
TypeError: unsupported operand type(s) for -: 'float' and 'str'
>>> h(a=0, b=6, c=4)
Traceback (most recent call last):
File "<interactive input>", line 1, in ?
File "<RPN string RPN2>", line 7, in RPN2
ZeroDivisionError: float division
>>>
Here's an error detected by the translator
>>> f = rpn.compile("a + 2 * b")
Traceback (most recent call last):
File "<interactive input>", line 1, in ?
File "E:\dalke\rpn.py", line 122, in compile
return translate(parse(tokenize(s)))
File "E:\dalke\rpn.py", line 98, in translate
stack.add_oper(_oper_table[token.val], token)
File "E:\dalke\rpn.py", line 72, in add_oper
raise RPNError(
RPNError: Binary operator at line 0 char 3 missing terms
And here's a problem detected during tokenization
>>> rpn.compile("5t")
Traceback (most recent call last):
File "<interactive input>", line 1, in ?
File "E:\dalke\rpn.py", line 122, in compile
return translate(parse(tokenize(s)))
File "E:\dalke\rpn.py", line 56, in parse
tokens = list(tokens) # this tree is very flat :)
File "E:\dalke\rpn.py", line 46, in tokenize
raise RPNError(
RPNError: Unknown token '5t' at line 0, character 1
>>>
I expect any similar Lisp implementation to track the
line numbers for error reporting.
Andrew
·····@dalkescientific.com
import re
import sys
from compiler import ast, misc, pycodegen
class RPNError(Exception):
pass
class Token:
VAR = 1
FLOAT = 2
OPER = 3
def __init__(self, type, val, lineno, charpos):
self.type = type
self.val = val
self.lineno = lineno
self.charpos = charpos
_symbol_re = re.compile(r"\S+")
_operators = "+ - * / **".split()
_variable_re = re.compile(r"[A-Za-z_][A-Za-z0-9_]*$")
def tokenize(s):
for lineno, line in enumerate(s.split("\n")):
for match in _symbol_re.finditer(line):
word = match.group(0)
charpos = match.start(0) + 1
try:
yield Token(Token.FLOAT, float(word),
lineno, charpos)
continue
except ValueError:
# okay, it isn't a float
pass
if word in _operators:
yield Token(Token.OPER, word,
lineno, charpos)
continue
if _variable_re.match(word):
yield Token(Token.VAR, word,
lineno, charpos)
continue
# Hmm, wonder what it is.
raise RPNError(
"Unknown token %r at line %d, character %d" %
(word, lineno, charpos))
class ParseTree:
def __init__(self, param_names, tokens):
self.param_names = param_names
self.tokens = tokens
def parse(tokens):
tokens = list(tokens) # this tree is very flat :)
param_names = []
for token in tokens:
if token.type == Token.VAR:
if token.val not in param_names:
param_names.append(token.val)
return ParseTree(param_names, tokens)
class Stack:
def __init__(self):
self.stack = []
def add_term(self, term, token):
term.lineno = token.lineno
self.stack.append(term)
def add_oper(self, klass, token):
if len(self.stack) < 2:
raise RPNError(
"Binary operator at line %d char %d missing terms" %
(token.lineno, token.charpos))
term = klass(self.stack[-2:])
term.lineno = token.lineno
self.stack[-2:] = [term]
_id_gen = iter(xrange(sys.maxint))
_oper_table = {
"+": ast.Add,
"-": ast.Sub,
"*": ast.Mul,
"/": ast.Div,
"**": ast.Power,
}
def translate(parse_tree):
stack = Stack()
for token in parse_tree.tokens:
if token.type == Token.FLOAT:
stack.add_term(ast.Const(token.val), token)
elif token.type == Token.VAR:
stack.add_term(ast.Name(token.val),
token)
elif token.type == Token.OPER:
stack.add_oper(_oper_table[token.val], token)
else:
raise AssertionError(repr(token.type))
stack = stack.stack
if len(stack) != 1:
raise RPNError("evaluation ends with stack size %d" %
len(stack))
# go through an ugly bit of shenanigans
# (I don't like the compiler API ):
fctn_name = 'RPN' + str(_id_gen.next())
fctn = ast.Function(fctn_name,
parse_tree.param_names, [],
0, None,
ast.Stmt([ast.Return(stack[0])]))
mod = ast.Module(None, ast.Stmt([fctn]))
misc.set_filename("<RPN string " + fctn_name + ">", mod)
code = pycodegen.ModuleCodeGenerator(mod).getCode()
d = {"__builtins__": {}}
exec code in d, d
return d[fctn_name]
def compile(s):
return translate(parse(tokenize(s)))
def main():
assert compile("a 2 3 + -")(a=6) == 1
assert compile("a 2 3 + -")(7) == 2
assert compile("a b *")(2, 3) == 6
assert compile("a b -")(b=2, a=3) == 1
assert compile("1 2 3 4 + + +")() == 10
print "All tests passed"
if __name__ == "__main__":
main()
"Andrew Dalke" <······@mindspring.com> writes:
> As an example, here's a quick hack of a way to parse a simple
> stack-based language and make a native Python function out
> of it. I am the first to admit that it's ugly code, but it does work.
>
> I am curious to see the equivalent code in Lisp. Here's the spec
You could of course do something similar in Lisp, but normally you'd
just use S-expressions instead of concocting your own weird syntax
every time you want to build a small language into something. Then
you just use the regular Lisp "read" function and the S-expressions
get parsed automatically for you. Your whole parser becomes just one
line of code.
Paul Rubin:
> You could of course do something similar in Lisp, but normally you'd
> just use S-expressions instead of concocting your own weird syntax
> every time you want to build a small language into something. Then
> you just use the regular Lisp "read" function and the S-expressions
> get parsed automatically for you. Your whole parser becomes just one
> line of code.
Ahh, but that's writing the domain language to fit the implementation
language. The moral equivalent for Python would be to use Python's
syntax to define a function, which is simple. Eg, Suppose the domain
language required that identifiers be labeled with parens, as in a
chemistry specific language where you might want
1-1'-(ethylenediimino)di-2-proponal
as a native identifier.
Andrew
·····@dalkescientific.com
Andrew Dalke wrote:
> Paul Rubin:
>
>>You could of course do something similar in Lisp, but normally you'd
>>just use S-expressions instead of concocting your own weird syntax
>>every time you want to build a small language into something. Then
>>you just use the regular Lisp "read" function and the S-expressions
>>get parsed automatically for you. Your whole parser becomes just one
>>line of code.
>
>
> Ahh, but that's writing the domain language to fit the implementation
> language.
Yes. The point is that you can do that in CL easily. Not so in Python.
> The moral equivalent for Python would be to use Python's
> syntax to define a function, which is simple.
CL binds morality with parcticality. Morality in CL is always practical :)
> Eg, Suppose the domain
> language required that identifiers be labeled with parens, as in a
> chemistry specific language where you might want
> 1-1'-(ethylenediimino)di-2-proponal
> as a native identifier.
cl-prompt> (symbolp '|1-1'-(ethylenediimino)di-2-proponal|)
T
In Python there is no equivalent AFAIK, in Java you can to
"1-1'-(ethylenediimino)di-2-proponal".intern()
to achieve a similar (although not so confortable) effect.
This is no surprise, given that the designers of Java knew Lisp.
Note also that in CL it is extremely easy to make the system accept
chemical "concentration" variables like the following example
(equation [CycB] (- k1 (* (+ k2p (*k2pp [Cdh1])) [CycB])))
or (with the INFIX package)
(equation [CyCB] #I(k1 - (k2p + k2pp * [Cdh1]) * [CycB]))
This is just a few reader macros away (and the use of the INFIX package).
In Python, you always have to com up with you full fledged parser.
Cheers
--
Marco
Marco Antoniotti:
> Yes. The point is that you can do that in CL easily. Not so in Python.
But, but, but, ... I do it all the time in Python.
> cl-prompt> (symbolp '|1-1'-(ethylenediimino)di-2-proponal|)
> T
Again, that's forcing the domain language to fit the requirements
of the implementation language. It's a shortcut, and requires the
domain experts to have more knowledge of the implementation
and means the domain language cannot be reimplemented outside
of a Lisp environment. (Yes, I know, why would you want to.
Answer: because that's the way life is.)
> In Python there is no equivalent AFAIK, in Java you can to
Indeed. In Python I wouldn't translate such a system directly
into Python. Eg, I would write an emulator for that language
in Python, or my translation would do some munging for me.
> This is just a few reader macros away (and the use of the INFIX package).
>
> In Python, you always have to com up with you full fledged parser.
You use reader macros for that. I use parser generators. You
cheat by storing the domain language directly as s-exps, I cheat
by storing the domain language in native Python data structures.
I fail to see a fundamental difference.
The point of my exercise was to show that such a task is
not hard in Python. Yes, it's about twice as long as the Lisp
code - this is a place where Lisp shines, just like perl shines
for doing command-line extraction of data from line-oriented
files - but it isn't hard.
Andrew
·····@dalkescientific.com
P.S.
I noticed the reply-to was sent to c.l.l; I don't follow that
group so my continuation in this branch will be by personal
mail only.
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <y8vdc6m1.fsf@comcast.net>
"Andrew Dalke" <······@mindspring.com> writes:
> Marco Antoniotti:
>> Yes. The point is that you can do that in CL easily. Not so in Python.
>
> But, but, but, ... I do it all the time in Python.
>
>> cl-prompt> (symbolp '|1-1'-(ethylenediimino)di-2-proponal|)
>> T
>
> Again, that's forcing the domain language to fit the requirements
> of the implementation language.
Huh?
Literally putting 1-1'-(ethylenediimino)di-2-proponal in your computer
is probably a bad idea, so you are *already* fitting the problem to
the implementation. Putting a multicharacter escape around a symbol
is no more `forcing' a fit than putting double quotes around it or
ensuring that there is whitespace on either side.
I can see objecting to something like this:
(attach (make-instance 'proponal-group)
(make-instance 'ethylenediimino)
...)
but not to a vertical bar.
> It's a shortcut, and requires the domain experts to have more
> knowledge of the implementation and means the domain language cannot
> be reimplemented outside of a Lisp environment.
People who cannot figure out how to remove the | at each end
should not be manipulating chemicals.
Andrew Dalke wrote:
> Marco Antoniotti:
>
>>Yes. The point is that you can do that in CL easily. Not so in Python.
>
>
> But, but, but, ... I do it all the time in Python.
>
>
>>cl-prompt> (symbolp '|1-1'-(ethylenediimino)di-2-proponal|)
>>T
>
>
> Again, that's forcing the domain language to fit the requirements
> of the implementation language. It's a shortcut, and requires the
> domain experts to have more knowledge of the implementation
> and means the domain language cannot be reimplemented outside
> of a Lisp environment. (Yes, I know, why would you want to.
> Answer: because that's the way life is.)
>
>
>>In Python there is no equivalent AFAIK, in Java you can to
>
>
> Indeed. In Python I wouldn't translate such a system directly
> into Python. Eg, I would write an emulator for that language
> in Python, or my translation would do some munging for me.
>
>
>>This is just a few reader macros away (and the use of the INFIX package).
>>
>>In Python, you always have to com up with you full fledged parser.
>
>
> You use reader macros for that. I use parser generators. You
> cheat by storing the domain language directly as s-exps, I cheat
> by storing the domain language in native Python data structures.
> I fail to see a fundamental difference.
You fail to see the point because your objective is to show that there
are tasks that are equally difficult in either Python or Common Lisp.
If you have to write a parser for a any language (say Ada 9x, just for
the heck of it), then obviously you have to resort to the full parse
toolchain (tokenizer, AST constructor etc etc). It does not matter if
you use INTERCAL or Python.
But, and here your argument does not hold, in Common Lisp you have an
extra trick up your sleeve. You can make your "domain language" S-expr
based (instead of inventing an XML format :) ). This is *in addition*
to what you can achieve with Python or other languages. And this
*addition* makes CL more powerful. Not only that. With reader macros,
CL has even more flexibility for achieving these effects. So, yes, it
is a trick. It is a trick that makes the language more usable.
>
> The point of my exercise was to show that such a task is
> not hard in Python. Yes, it's about twice as long as the Lisp
> code - this is a place where Lisp shines,
Yes. The CL code also compiles down to fast native code (how close is
Psyco to ECL?). Another place where Common Lisp shines. Especially
when you have to do numerical computations.
Cheers
--
Marco
Andrew Dalke writes:
> Paul Rubin:
>> You could of course do something similar in Lisp, but normally you'd
>> just use S-expressions instead of concocting your own weird syntax
>> every time you want to build a small language into something. Then
>> you just use the regular Lisp "read" function and the S-expressions
>> get parsed automatically for you. Your whole parser becomes just one
>> line of code.
>
> Ahh, but that's writing the domain language to fit the implementation
> language. The moral equivalent for Python would be to use Python's
> syntax to define a function, which is simple. Eg, Suppose the domain
Bingo, that's exactly the point :-)
The idiomatic way of developing little/domain-specific languages in
Lisp is to leverage its sexp-based syntax whenever possible and
appropriate. And yes, the scary macros are one of the main tools used
for this. Python's mileage might (and the current threads suggest that
it does :) vary.
Is Lisp's approach complicated or confusing for certain domain experts
or non programmers? Quite possibly. But they may not be the intended
audience of Lisp.
Learning Lisp, and the idiomatic ways of using it, does take time and
effort, but Lispers believe that this pays off. Those who prefer other
approaches have lots of alternatives, including Python.
As to why one may want to design little/domain-specific languages with
sexp-based syntax, some insight is provided in this paper by Olin
Shivers:
A Universal Scripting Framework - or - Lambda: the ultimate "little language"
http://www.ai.mit.edu/~shivers/ll.ps
Abstract: The "little languages" approach to systems programming is
flawed: inefficient, fragile, error-prone, inexpressive, and
difficult to compose. A better solution is to embed task-specific
sublanguages within a powerful, syntactically extensible, universal
language, such as Scheme. I demonstrate two such embeddings that
have been implemented in scsh, a Scheme programming environment for
Unix systems programming. The first embedded language is a highlevel
process-control notation; the second provides for Awk-like
processing. Embedding systems in this way is a powerful technique:
for example, although the embedded Awk system was implemented with
7% of the code required for the standard C-based Awk, it is
significantly more expressive than its C counterpart.
Although Shivers presents examples in Scheme, the ideas apply to other
Lisp dialects, and possibly also to other languages. The `scsh' system
mentioned in the paper is available at:
http://scsh.sourceforge.net
Paolo
--
Paolo Amoroso <·······@mclink.it>
Andrew Dalke wrote:
> Paul Rubin:
>
>>You could of course do something similar in Lisp, but normally you'd
>>just use S-expressions instead of concocting your own weird syntax
>>every time you want to build a small language into something. Then
>>you just use the regular Lisp "read" function and the S-expressions
>>get parsed automatically for you. Your whole parser becomes just one
>>line of code.
>
>
> Ahh, but that's writing the domain language to fit the implementation
> language.
Yes, but we Lispers don't care about that. As I said before, syntax is
boring. ;)
To be more specific:
Getting domain-specific in Lisp doesn't (necessarily) mean to adopt the
notation of that domain. Lisp is rather pigheaded wrt notation - it
strongly prefers s-expressions, i.e. prefix notation.
Getting domain-specific rather means to model the abstractions of that
domain.
This means that when you program in most languages, the program source
code will consist of objects, methods, functions, closures, and so on.
Whereas when you get domain-specific, you see the abstractions of that
domain and nothing else (or at least not much else).
For example, the + operator is an abstraction of the domain of
mathematics. Getting domain-specific means to make the + operator
available in a way so that you don't care how it is actually implemented
beneath. It doesn't necessarily mean that you need to switch to infix
notation.
Pascal
In article <·················@newsread4.news.pas.earthlink.net>, "Andrew
Dalke" <······@mindspring.com> wrote:
> Me:
> > Python has the ability to do exactly
> > what you're saying (domain language -> AST -> Python code or AST ->
> > compiler). It's rarely needed (I've used it twice now in my six years
> > or so of Python), so why should a language cater to make that
> > easy at the expense of making frequent things harder?
>
> As an example, here's a quick hack of a way to parse a simple
> stack-based language and make a native Python function out
> of it. I am the first to admit that it's ugly code, but it does work.
>
> I am curious to see the equivalent code in Lisp.
Here's a quick and dirty version:
(defvar *operations* '(+ - * / **))
(defun ** (n e) (expt n e))
(defun rpn-compile (expr)
(let ( stack free-vars )
(dolist (term expr)
(cond ( (numberp term) (push term stack) )
( (member term *operations*)
(push (list term (pop stack) (pop stack)) stack)
(rotatef (second (first stack)) (third (first stack))) )
(t (push term stack)
(pushnew term free-vars))))
(unless (= (length stack) 1) (error "Syntax error"))
(eval `(lambda (&key ,@free-vars) ,(first stack)))))
? (funcall (rpn-compile '(0 b - b 2 ** 4 a c * * - 0.5 ** + 2 a * /))
:a 1 :b 6 :c 3)
-0.5505102572168221
?
E.
Erann Ga
> Here's a quick and dirty version:
>
> (defvar *operations* '(+ - * / **))
>
> (defun ** (n e) (expt n e))
>
> (defun rpn-compile (expr)
> (let ( stack free-vars )
> (dolist (term expr)
> (cond ( (numberp term) (push term stack) )
> ( (member term *operations*)
> (push (list term (pop stack) (pop stack)) stack)
> (rotatef (second (first stack)) (third (first stack))) )
> (t (push term stack)
> (pushnew term free-vars))))
> (unless (= (length stack) 1) (error "Syntax error"))
> (eval `(lambda (&key ,@free-vars) ,(first stack)))))
>
>
> ? (funcall (rpn-compile '(0 b - b 2 ** 4 a c * * - 0.5 ** + 2 a * /))
> :a 1 :b 6 :c 3)
> -0.5505102572168221
> ?
You know, I messed up a bit in the explanation in several
ways. First, I wanted to show that Python code could directly
manipulate the AST and generate usable code. I then chose
a problem which could be done that way and implemented it
in the canonical tokenizer/parser/translater/compiler framework
Kaz Kylheku (to whom I was responding) wanted, when it's
inappropriate for this case, hence complicating my original code.
If I were actually asked to solve that problem I would have
done it like you did
import re
_name_re = re.compile("[A-Za-z_][A-Za-z_0-9]*$")
_operators = "* + - / **".split()
def compile(s):
stack = []
names = []
for token in s.split():
try:
stack.append(float(token))
continue
except ValueError:
pass
if _name_re.match(token):
names.append(token)
stack.append(token)
elif token in _operators:
s = "(%s)%s(%s)" % (stack[-2], token, stack[-1])
stack[-2:] = [s]
else:
raise AssertionError(token)
assert len(stack) == 1
s = "def RPN(" + ",".join(names) + "):\n\treturn "
s += str(stack[0])
exec s in {"__builtins__": {}}
return d["RPN"]
That is, just build up then exec a string to get the function.
Second, I didn't mention until the end that I expected the
Lisp code to report the location (line numbers and even
character positions) of where an error occured in the RPN.
The code you have, and this quick approach, don't attempt
to handle error numbers, making it much more succinct.
Third, I didn't stress the requirement to identify illegal
inputs, like 'a(', which are accepted by your code up
until the eval step. (I could have made it worse for
all of us if I allowed the characters '()#; in an identifier ;)
OTOH, the quick&dirty solution I just now did
doesn't allow Python keywords as variable names,
while my AST approach does. That could be solved
with a bit of variable munging, but complicates things.
Eg, I changed my re pattern (in my AST version) to
accept anything other than a number or operator as a
keyword. The following then works
f = compile("(#) ');; try + -")
# can't call the keyword arguments directly since they
# aren't legal Python names.
print f(**{"(#)": 5, "');;": 7, "try": 3})
and gives -5. Our eval/exec approaches just could not
handle that case.
What does your code do for my example above? ;)
Andrew
·····@dalkescientific.com
Me:
> if _name_re.match(token):
> names.append(token)
Should be
if _name_re.match(token):
if token not in names:
names.append(token)
Andrew
·····@dalkescientific.com
Me:
> I then chose
> a problem which could be done that way and implemented it
> in the canonical tokenizer/parser/translater/compiler framework
> Kaz Kylheku (to whom I was responding) wanted, when it's
> inappropriate for this case, hence complicating my original code.
Here's what the code would look like without that strict
partitioning. It can be made a bit smaller (I don't really need the
'Stack' class; it just helps simplify dealing with line numbers,
and the is_float make the if/elif/else structure nice, compared
to using a try/except.)
The point though is that Python allows the same sorts of
domain language -> AST -> "native" AST -> native code
steps that Kaz Kylheku wanted.
Andrew
·····@dalkescientific.com
import re, sys
from compiler import ast, misc, pycodegen
class RPNError(Exception):
pass
_symbol_re = re.compile(r"\S+")
#_variable_re = re.compile(r"[A-Za-z_][A-Za-z0-9_]*$")
# Let's take anything!
_variable_re = re.compile(r".*$")
class Stack:
def __init__(self):
self.stack = []
def add_term(self, term, lineno):
term.lineno = lineno
self.stack.append(term)
def add_oper(self, klass, lineno, charpos):
if len(self.stack) < 2:
raise RPNError(
"Binary operator at line %d char %d missing terms" %
(lineno, charpos))
term = klass(self.stack[-2:])
term.lineno = lineno
self.stack[-2:] = [term]
def is_float(s):
try:
float(s)
return 1
except ValueError:
return 0
_id_gen = iter(xrange(sys.maxint))
_oper_table = {
"+": ast.Add,
"-": ast.Sub,
"*": ast.Mul,
"/": ast.Div,
"**": ast.Power,
}
def compile(s):
param_names = []
stack = Stack()
for lineno, line in enumerate(s.split("\n")):
for match in _symbol_re.finditer(line):
word = match.group(0)
charpos = match.start(0) + 1
if is_float(word):
stack.add_term(ast.Const(float(word)), lineno)
elif word in _oper_table:
stack.add_oper(_oper_table[word],
lineno, charpos)
elif _variable_re.match(word):
stack.add_term(ast.Name(word), lineno)
if word not in param_names:
param_names.append(word)
else:
# Hmm, wonder what it is.
raise RPNError(
"Unknown token %r at line %d, character %d" %
(word, lineno, charpos))
stack = stack.stack
if len(stack) != 1:
raise RPNError("stack ends with size %d" %
len(stack))
# go through an ugly bit of shenanigans
# (I don't like the compiler API ):
fctn_name = 'RPN' + str(_id_gen.next())
fctn = ast.Function(fctn_name, param_names, [],
0, None,
ast.Stmt([ast.Return(stack[0])]))
mod = ast.Module(None, ast.Stmt([fctn]))
misc.set_filename("<RPN string " + fctn_name + ">", mod)
code = pycodegen.ModuleCodeGenerator(mod).getCode()
d = {"__builtins__": {}}
exec code in d
return d[fctn_name]
def main():
assert compile("2 3 **")() == 8
assert compile("a 2 3 + -")(a=6) == 1
assert compile("a 2 3 + -")(7) == 2
assert compile("a b *")(2, 3) == 6
assert compile("a b -")(b=2, a=3) == 1
assert compile("1 2 3 4 + + +")() == 10
f = compile("(#) ') try + -")
print f(**{"(#)": 5, "')": 7, "try": 3})
print "All tests passed"
if __name__ == "__main__":
main()
"Andrew Dalke" <······@mindspring.com> writes:
> Me:
> > Python has the ability to do exactly what you're saying (domain
> > language -> AST -> Python code or AST -> compiler). It's rarely
> > needed (I've used it twice now in my six years or so of Python),
> > so why should a language cater to make that easy at the expense of
> > making frequent things harder?
>
> As an example, here's a quick hack of a way to parse a simple
> stack-based language and make a native Python function out of it. I
> am the first to admit that it's ugly code, but it does work.
>
> I am curious to see the equivalent code in Lisp. Here's the spec
>
> All tokens are separated by whitespace (space, tab, newline, and
> include vertical tab and form feed if you want).
>
> Numbers are the standard IEEE floats (excepting NaN, Inf, etc)
> and represented "as usual".
>
> The operators are addition ("+"), subtraction ("-"), multiplication
> ("*"), division ("/"), and exponentiation ("**"). These are binary
> operators only, so to get -b use 0 b - .
>
> The variable names are of the form [A-Za-Z_][A-Za-z0-9_]*
> and must be passed to the function when making the function call.
> The order of names is the same as the order the names appear
> in the RPN expression, so in "b a +" the function created takes
> "b" as the first argument and "a" as the second.
Okay, here's a Common Lisp version. Because Lisp functions take either
keyword or positional arguments, I choose to make the generated
functions use keyword arguments. But the variables are gathered in the
right order, so take out the '&key' below to use positional arguments:
(defun compile-rpn (input)
(compile nil (parse input)))
(defun parse (input)
(let (stack variables (idx 0))
(loop
(multiple-value-bind (tok next-idx) (read-from-string input nil nil :start idx)
(labels
((line-number () (1+ (count #\Newline input :end idx)))
(pop-arg ()
(or (pop stack)
(error "Not enough arguments for ~a at position ~d (line ~d)." tok idx (line-number)))))
(cond
((not tok) (return `(lambda (&key ,@(nreverse variables)) (prog1 ,@stack))))
((member tok '(+ * - /)) (push (cons tok (reverse (list (pop-arg) (pop-arg)))) stack))
((eq tok '**) (push (cons 'expt (reverse (list (pop-arg) (pop-arg)))) stack))
((numberp tok) (push tok stack))
((variablep tok) (push tok stack) (pushnew tok variables))
(t (error "Invalid token ~a at position ~d (line ~d)." tok idx (line-number))))
(setq idx next-idx))))))
(defun variablep (sym)
(and (symbolp sym) (every #'alpha-char-p (string sym))))
Here's how it works (FUNCALL is the Common Lisp operator to calls a
function object such as the one returned by compile-rpn):
* (funcall (compile-rpn "1 2 3 4 5 + + + + a **") :a 2)
225
Compile-time error messages:
* (compile-rpn "a + 2 * b")
Error: Not enough arguments for + at position 2 (line 1).
* (compile-rpn "5t")
Error: Invalid token 5T at position 0 (line 1).
Runtime error handling:
* (funcall (compile-rpn "a b +") :a "foo" :b 2)
Error: `"foo"' is not of the expected type `NUMBER'
And for grins here's the x86 machine code generated for the first function:
* (disassemble (compile-rpn "1 2 3 4 5 + + + + a **"))
;; disassembly of #<Function (:ANONYMOUS-LAMBDA 51) @ #x7608e53a>
;; formals: &KEY A
;; constant vector:
0: NIL
1: 1
2: :A
3: EXPT
;; code start: #x7608e4d4:
0: 55 pushl ebp
1: 8b ec movl ebp,esp
3: 56 pushl esi
4: 83 ec 2c subl esp,$44
7: 89 45 08 movl [ebp+8],eax
10: 89 55 0c movl [ebp+12],edx
13: 8d 09 leal ecx,[ecx+0]
15: 8d 45 08 leal eax,[ebp+8]
18: 8d 55 e0 leal edx,[ebp-32]
21: 33 db xorl ebx,ebx
23: b3 48 movb bl,$72
25: ff 57 4f call *[edi+79] ; SYS::KWDSCAN
28: 8d 5d e0 leal ebx,[ebp-32]
31: 8b 13 movl edx,[ebx+0]
33: 3b fa cmpl edi,edx
35: 75 1a jnz 63
37: 8b d7 movl edx,edi
39: 80 7f 97 00 cmpb [edi-105],$0 ; SYS::C_INTERRUPT
43: 74 02 jz 47
45: cd 64 int $100 ; EXCL::TRAP-SIGNAL-HIT
47: 8b 5e 1e movl ebx,[esi+30] ; EXPT
50: 33 c0 xorl eax,eax
52: b0 3c movb al,$60
54: ff 57 27 call *[edi+39] ; SYS::TRAMP-TWO
57: f8 clc
58: c9 leave
59: 8b 75 fc movl esi,[ebp-4]
62: c3 ret
63: 8b 53 04 movl edx,[ebx+4]
66: eb e3 jmp 39
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel:
> Okay, here's a Common Lisp version. Because Lisp functions take either
> keyword or positional arguments, I choose to make the generated
> functions use keyword arguments. But the variables are gathered in the
> right order, so take out the '&key' below to use positional arguments:
Cool code. I like that it identifies some of the error locations.
> * (funcall (compile-rpn "a b +") :a "foo" :b 2)
> Error: `"foo"' is not of the expected type `NUMBER'
My Python code reports a line number for this. I figured it
would be harder for simple Lisp code to do the same. But
that's because I'm cheating; the Python stack trace normally
reports the line number so I get most of it for free. I suspect
it would be more complicated if the spec said to report the
line number *and* character position of the operator which
failed.
(Not all that hard though; I can use a new object
class Add:
def __init__(self, lineno, charpos):
self.lineno = lineno
self.charpos = charpos
def __call__(self, left, right):
try:
return left + right
except:
... report the error location ...
and make the code look like
Mult(4, 2)(3.0, Add(1, 30)(a, 1) + 9.8)
but if I'm making a native Python function which doesn't
manipulate its own stack then it's probably for the speed,
and the above will be slow.)
In my reply to Erann Gat I noted that his eval approach
might exclude the possibility of using names like 'a)' as identifiers.
(I don't know if it does, because I don't know enough Lisp.)
My AST solution could easily be changed to support that
case, as well as variable like ";;b" and "#c" and ":d:".
I'll ask the same of you. Does your code require that the
RPN names also be valid Lisp tokens? If so, what happens
if it isn't?
(Looking at it, the key line is
> ((not tok) (return `(lambda (&key ,@(nreverse
variables)) (prog1 ,@stack))))
but I don't know what @() does nor what happens if a "strange"
value is used as the list of keywords)
> And for grins here's the x86 machine code generated for the first
function:
I was never any good at Intel assembly, and I thankfully haven't
touched it in about 15 years. I was trying to figure out if it
optimized the additions into 15**a, but I could see neither the
sequence 1, 2, 3, 4, 5 nor the value 15 (octal 17, hex F) anywhere
in the code. Pointers?
Andrew
·····@dalkescientific.com
"Andrew Dalke" <······@mindspring.com> writes:
> Peter Seibel:
> > Okay, here's a Common Lisp version. Because Lisp functions take either
> > keyword or positional arguments, I choose to make the generated
> > functions use keyword arguments. But the variables are gathered in the
> > right order, so take out the '&key' below to use positional arguments:
>
> Cool code. I like that it identifies some of the error locations.
>
> > * (funcall (compile-rpn "a b +") :a "foo" :b 2)
> > Error: `"foo"' is not of the expected type `NUMBER'
>
> My Python code reports a line number for this.
Right. Well that's one disadvantage, such as it is, of having the
compiler built in--I'm at the mercy of its error reporting and Lisp
isn't big on line-numbers, perhaps because many definitions don't come
from a file. What I didn't show in the output was that I was actually
dropped into the debugger at that point so had all the capabilities
that it provided to figure out what was going wrong. Anyway, that's
the price I pay for getting machine code I guess. I could, if it was
really important wrap all the function calls in condition handling
code that reported the line number but it didn't seem worth it.
> In my reply to Erann Gat I noted that his eval approach might
> exclude the possibility of using names like 'a)' as identifiers. (I
> don't know if it does, because I don't know enough Lisp.)
>
> My AST solution could easily be changed to support that case, as
> well as variable like ";;b" and "#c" and ":d:".
>
> I'll ask the same of you. Does your code require that the RPN names
> also be valid Lisp tokens? If so, what happens if it isn't?
Sure. I just used the built in Lisp reader because the syntax you
specified was compatibile. But if I wanted to allow names including
special characters I could either tweak the readtable so the Lisp
reader didn't treat them as special or I could do something like this.
Notice that the actual change to the parse function is to one function
call, replacing a call to the built-in READ-FROM-STRING with my own
next-token function. The rest of the patch is my own simple tokenizer.
(And I had to redefine variablep to allow weird variable names.) The
tokenizer could probably be written better but it's late here and I
should be in bed.
==== //depot/lisp-book/code/rpn.cl#1 - /home/peter/localperforce/lisp-book/code/rpn.cl ====
@@ -10,7 +10,7 @@
(defun parse (input)
(let (stack variables (idx 0))
(loop
- (multiple-value-bind (tok next-idx) (read-from-string input nil nil :start idx)
+ (multiple-value-bind (tok next-idx) (next-token input :start idx)
(labels
((line-number () (1+ (count #\Newline input :end idx)))
(pop-arg ()
@@ -25,8 +25,35 @@
(t (error "Invalid token ~a at position ~d (line ~d)." tok idx (line-number))))
(setq idx next-idx))))))
-(defun variablep (sym)
- (and (symbolp sym) (every #'alpha-char-p (string sym))))
+
+
+(defun next-token (input &key (start 0))
+ (multiple-value-bind (str end) (next-string input :start start)
+ (when str
+ (values
+ (if (digit-char-p (char str 0))
+ (read-from-string str nil nil)
+ (intern (string-upcase str)))
+ end))))
+
+(defun next-string (input &key (start 0))
+ (let ((real-start (skip-white-space input :start start)))
+ (loop for idx from real-start below (length input)
+ while (not (white-space-p (char input idx)))
+ finally (return
+ (values
+ (if (= real-start idx) nil (subseq input real-start idx))
+ (skip-white-space input :start idx))))))
+
+(defun skip-white-space (input &key (start 0))
+ (loop for idx from start below (length input)
+ while (white-space-p (char input idx))
+ finally (return idx)))
+
+(defun white-space-p (char)
+ (member char '(#\Space #\Newline #\Tab)))
+
+(defun variablep (sym) (symbolp sym))
> (Looking at it, the key line is
> > ((not tok) (return `(lambda (&key ,@(nreverse
> variables)) (prog1 ,@stack))))
>
> but I don't know what @() does nor what happens if a "strange"
> value is used as the list of keywords)
Actually the key line is the one I patched above. This is just
generating the form which Lisp knows how to compile. But since Lisp
symbols can actually contain any character, as long as they're
properly escaped I have no real problems.
>
> > And for grins here's the x86 machine code generated for the first
> function:
>
> I was never any good at Intel assembly, and I thankfully haven't
> touched it in about 15 years. I was trying to figure out if it
> optimized the additions into 15**a, but I could see neither the
> sequence 1, 2, 3, 4, 5 nor the value 15 (octal 17, hex F) anywhere
> in the code. Pointers?
Well, I know less about it than you. I just threw that in to point out
that my 24-line compiler generates machine code.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel:
> Right. Well that's one disadvantage, such as it is, of having the
> compiler built in--I'm at the mercy of its error reporting and Lisp
> isn't big on line-numbers, perhaps because many definitions don't come
> from a file.
True enough, but I sketched out a few ways that could work in
Python and they would work equally well in Lisp.
> What I didn't show in the output was that I was actually
> dropped into the debugger at that point so had all the capabilities
> that it provided to figure out what was going wrong. Anyway, that's
> the price I pay for getting machine code I guess.
I haven't used the Python debuggers (I'm still stuck in the
archaic era of print statements ;) so I can't compare. In any
case, the error reporting is going to be at the level of the
translated code, which may or may not be helpful.
There is a compiler for Python code called Psyco, but it only
works for Intel hardware and my primary platform is a Mac.
I have an old copy on my Intel box, but it needs a recompile
to support dumping the assembly code, and that's too much
effort for this task.
> I could, if it was
> really important wrap all the function calls in condition handling
> code that reported the line number but it didn't seem worth it.
Yup, it ain't.
> replacing a call to the built-in READ-FROM-STRING with my own
> next-token function. The rest of the patch is my own simple tokenizer.
Interesting. The code reminds me of working with strings
in Pascal, because it tracks the string and the offset. Equivalent
C code would use the pointers directly. But Python code
works as a larger chunk level, with split() and regexps, in
part because working at the lowest level requires a lot of
fiddling around with things that are slow in native Python. (Eg,
I would do i=s.find("a") instead of
for i in range(len(s)): if s[i] == 'a': break )
Well, *I* thought it was interesting.
> (And I had to redefine variablep to allow weird variable names.) The
> tokenizer could probably be written better but it's late here and I
> should be in bed.
Understood. Also, my schedule is so backwards now that I'm
going to bed when the sun rises. :(
> Actually the key line is the one I patched above. This is just
> generating the form which Lisp knows how to compile. But since Lisp
> symbols can actually contain any character, as long as they're
> properly escaped I have no real problems.
Got it. I was thinking {} is equivalent to a paste when it's
more like an insert.
Andrew
·····@dalkescientific.com
In article <·················@newsread4.news.pas.earthlink.net>,
Andrew Dalke <······@mindspring.com> wrote:
> > And for grins here's the x86 machine code generated for the first
> > function:
>
> I was never any good at Intel assembly, and I thankfully haven't
> touched it in about 15 years. I was trying to figure out if it
> optimized the additions into 15**a, but I could see neither the
> sequence 1, 2, 3, 4, 5 nor the value 15 (octal 17, hex F) anywhere
> in the code. Pointers?
It did indeed optimize the constants. What you're missing is that in
most implementations Lisp fixnums are tagged so that they can fit in a
descriptor slot by themselves and not be boxed in more structure. In
almost all (x86) implementations I've seen a fixnum is 30 high bits of
signed number and 2 low bits of zero.
If a value has a non-zero low tag than it is something else like a
pointer, and not a fixnum.
These fixnums have the property that you can add two of them and get a
third with no shifting at all, and to multiply, you only need to shift
one of them.
So the number you're looking for is 60, which is 15 << 2.
47: 8b 5e 1e movl ebx,[esi+30] ; EXPT
50: 33 c0 xorl eax,eax
52: b0 3c movb al,$60
54: ff 57 27 call *[edi+39] ; SYS::TRAMP-TWO
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
On Wed, 22 Oct 2003 13:31:25 GMT, Brian Downing <·············@lavos.net> wrote:
> What you're missing is that in most implementations Lisp fixnums are
> tagged so that they can fit in a descriptor slot by themselves and
> not be boxed in more structure. In almost all (x86) implementations
> I've seen a fixnum is 30 high bits of signed number and 2 low bits
> of zero.
Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
CL-USER 10 > (log most-positive-fixnum 2)
22.99999982801734
Does anybody have an idea why this is the case? Historical reasons?
Thanks,
Edi.
Edi Weitz <···@agharta.de> writes:
> CL-USER 10 > (log most-positive-fixnum 2)
> 22.99999982801734
>
> Does anybody have an idea why this is the case? Historical reasons?
Some implementations use enough tag bits to store the whole object
type in the tag instead of in the heap. These days on 32-bit machines
that's not so great, because it eats too many address bits.
In article <··············@bird.agharta.de>, Edi Weitz <···@agharta.de> wrote:
> On Wed, 22 Oct 2003 13:31:25 GMT, Brian Downing <·············@lavos.net> wrote:
> Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
>
> CL-USER 10 > (log most-positive-fixnum 2)
> 22.99999982801734
>
> Does anybody have an idea why this is the case? Historical reasons?
If I had to take a wild guess, I'd say they traded off big fixnums for
more pointer types.
CMUCL/SBCL (the only implementations I know the details of) call the low
3 bits the 'lowtag'. From these three bits you can get eight types of
things. For SBCL (albeit on PPC) they are:
Low bits Object type
-------- ---------------
000 Even fixnum
001 Pointer to structure
010 Even "Other immediate"
011 Pointer to list/cons
100 Odd fixnum
101 Pointer to function
110 Odd "Other immediate"
111 Pointer to anything else
Pointers can be aligned to eight bytes - you zero out the tag bits
before using it. You can get a 30-bit signed fixnum because it uses up
two tags - even and odd.
On the even and odd "Other immediate" type, the bottom eight bits make
up a 'widetag'. This gives you 64 other kinds of descriptors, which
have the lower 8 bits as the 'widetag' and the upper 24 bits as data.
Obviously there are too many of these to list here.
If you made fixnums 24 bits and put them on an "other immediate", you
would free up two more possible pointer types which could possibly make
your GC more efficient. I imagine Lispworks makes some tradeoff here.
Whether it is correct is hard to tell without knowing more detail.
http://cmucl.cons.org/ftp-area/cmucl/doc/cmucl-design/object.html
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Edi Weitz <···@agharta.de> writes:
> Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
>
> CL-USER 10 > (log most-positive-fixnum 2)
> 22.99999982801734
this is slightly off-topic, but I just wanted to remind the reader of
integer-length (since it tends to be forgotten by lispers who only
occasionally do bit-fiddling arithmetics):
CL-USER 2 > (integer-length most-positive-fixnum)
23
--
(espen)
On 22 Oct 2003 16:44:52 +0200, Espen Vestre <·····@*do-not-spam-me*.vestre.net> wrote:
> Edi Weitz <···@agharta.de> writes:
>
> > Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
> >
> > CL-USER 10 > (log most-positive-fixnum 2)
> > 22.99999982801734
>
> this is slightly off-topic, but I just wanted to remind the reader
> of integer-length (since it tends to be forgotten by lispers who
> only occasionally do bit-fiddling arithmetics):
>
> CL-USER 2 > (integer-length most-positive-fixnum)
> 23
Thanks, I must have skipped the letter 'I' last time I tried to
memorize the HyperSpec. 978 external symbols are too much for an old
man like me... :)
I'm very happy now that I didn't post
CL-USER 2 > (nth-value 0 (round (log most-positive-fixnum 2)))
23
which I wanted to do originally... :)
Cheers,
Edi.
In article <··············@bird.agharta.de>, Edi Weitz <···@agharta.de> wrote:
> Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
>
> CL-USER 10 > (log most-positive-fixnum 2)
> 22.99999982801734
>
> Does anybody have an idea why this is the case? Historical reasons?
If I had to take a wild guess, I'd say they traded off big fixnums for
more pointer types.
CMUCL/SBCL (the only implementations I know the details of) call the low
3 bits the 'lowtag'. From these three bits you can get eight types of
things. For SBCL (albeit on PPC) they are:
Low bits Object type
-------- ---------------
000 Even fixnum
001 Pointer to structure
010 Even "Other immediate"
011 Pointer to list/cons
100 Odd fixnum
101 Pointer to function
110 Odd "Other immediate"
111 Pointer to anything else
Pointers can be aligned to eight bytes - you zero out the tag bits
before using it. You can get a 30-bit signed fixnum because it uses up
two tags - even and odd.
On the even and odd "Other immediate" type, the bottom eight bits make
up a 'widetag'. This gives you 64 other kinds of descriptors, which
have the lower 8 bits as the 'widetag' and the upper 24 bits as data.
Obviously there are too many of these to list here.
If you made fixnums 24 bits and put them on an "other immediate", you
would free up two more possible pointer types which could possibly make
your GC more efficient. I imagine Lispworks makes some tradeoff here.
Whether it is correct is hard to tell without knowing more detail.
http://cmucl.cons.org/ftp-area/cmucl/doc/cmucl-design/object.html
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Brian Downing <·············@lavos.net> writes:
> In article <··············@bird.agharta.de>, Edi Weitz <···@agharta.de> wrote:
> > Not in LispWorks (LW pro 4.2.7 on Linux x86), unfortunately:
> >
> > CL-USER 10 > (log most-positive-fixnum 2)
> > 22.99999982801734
> >
> > Does anybody have an idea why this is the case? Historical reasons?
That is a factor. We devised this design for a 386, to work with a
simpler compiler with few optimizations. It was probably a better
trade-off then than it is now. Certainly 2^23-element arrays weren't
a pressing concern back then. Recoding all the low-level integer and
array code now would obviously be costly (but not impossible).
> If I had to take a wild guess, I'd say they traded off big fixnums for
> more pointer types.
That's it.
> If you made fixnums 24 bits and put them on an "other immediate", you
> would free up two more possible pointer types which could possibly make
> your GC more efficient.
That's the idea. It was not actually the GC that was the overriding
concern, it was speed of type checking. This was seen as a major
drain on performance, and all stops were pulled out to code type
checks are tightly as possible. (I suppose that helps GC as well.)
So, if I still remember this (there was a time I could read LWW core
dumps):
Low bits Object type
-------- ---------------
000 immediate
001 cons
010 compiled function object
011 unused
100 other
101 unused
110 unused
111 unused
The unused ones aren't totally unused: they are used for stack markers
and GC tricks, but they never appear on a Lisp datum. I think even
with an optimizing compiler and decent declarations, some programs
spend a lot of time testing for NULL and CONSP, so this still has its
advantages.
--
Pekka P. Pirinen, Global Graphics Software Limited
Don't force it, get a larger hammer.
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <k76x2u01.fsf@comcast.net>
"Andrew Dalke" <······@mindspring.com> writes:
> I was never any good at Intel assembly, and I thankfully haven't
> touched it in about 15 years. I was trying to figure out if it
> optimized the additions into 15**a, but I could see neither the
> sequence 1, 2, 3, 4, 5 nor the value 15 (octal 17, hex F) anywhere
> in the code. Pointers?
When you read the raw machine code you have to remember that
entities are tagged. I believe line 52
52: b0 3c movb al,$60
is the relevant one. 60 = 15 * 4, so it seems that this
implementation represents fixnums by shifting left by two.
Perhaps lisp is not so well-liked is because there are not enough
standard libraries available. Perl has the CPAN libraries that
you can simply download and use. I've heard the Python also
has a huge number of such libraries. But if i want a lisp-tk
CLOS library, i'd have to write it myself, or lisp-DOM, or
lisp-cvs, or lisp-mySQL.
On this note, has anyone ever heard of openAccess or openEDA?
http://www.openeda.org/
it's an open source database for dealing with EDA design
data. Currently there is a C++ interface and Python.
At Tcl interface is either here on on its way.
In my opinion a CLOS library would be much easier to use
than any of the other, if it existed. But what i've decided
to do in the mean time is to start from scratch learing
Python.
The C++ standard API is open, and well documented. Does
anyone volunteer to start such a openAcces --> CLOS
project?
-jim
Jim Newton wrote:
> Perhaps lisp is not so well-liked is because there are not enough
> standard libraries available. Perl has the CPAN libraries that
> you can simply download and use. I've heard the Python also
> has a huge number of such libraries. But if i want a lisp-tk
> CLOS library, i'd have to write it myself, or lisp-DOM, or
> lisp-cvs, or lisp-mySQL.
>
> On this note, has anyone ever heard of openAccess or openEDA?
> http://www.openeda.org/
Wow. That's the first open source project that demanded a license
agreement or something before letting me download. They use that word
Open so much, but I do not think it means what they think it means. :)
Anyway, I just wanted to see what everyone is interfacing to. Oops. You
already said C++. Might take a C wrapper so Lisp FFIs can cope.
>
> it's an open source database for dealing with EDA design
> data. Currently there is a C++ interface and Python.
> At Tcl interface is either here on on its way.
>
> In my opinion a CLOS library would be much easier to use
> than any of the other, if it existed. But what i've decided
> to do in the mean time is to start from scratch learing
> Python.
If you are not part of the solution, you are part of the problem.
Tilton's Law: Solve the right problem. Your problem is not that you do
not know Python. A giveaway is that learning Python will not help you
use OpenEDA from Lisp. That is your problem. What is the solution? UFFI
bindings for OpenEDA. Regrettably, possibly also some gluing of C++
classes to C structs so Lisp FFIs can cope. The good news is that the
problem is linear and finite, albeit tedious. But crafty Lisp macros can
help. Might take a week or two. I and others here can help with that.
Tilton's Law: Move towards the light. If you have to do some hard work
over the next few weeks, would you rather (a) know and be using Python
or (b) know Lisp FFIs (it's not /that/ bad) and be using Lisp?
>
> The C++ standard API is open, and well documented. Does
> anyone volunteer to start such a openAcces --> CLOS
> project?
>
<g> Yep, some guy named:
>
> -jim
>
And I can help you with the FFI. Do they /really/ use C++ classes, or is
it just C in C++ clothing? Is it a persistent C++ DB format? Probably
not. I am thinking, just read the DB in Lisp, eliminate the bothersome
middleman. They didn't use XML? Or is it more than a DB, really?
kenny
--
http://tilton-technology.com
What?! You are a newbie and you haven't answered my:
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey
Jim Newton <·····@rdrop.com> writes:
> Perhaps lisp is not so well-liked is because there are not enough
> standard libraries available. Perl has the CPAN libraries that
> you can simply download and use. I've heard the Python also
> has a huge number of such libraries. But if i want a lisp-tk
> CLOS library, i'd have to write it myself, or lisp-DOM, or
> lisp-cvs, or lisp-mySQL.
The Debian distribution seems to have a lot of cl packages. I am
quite sure that a mysql and postresql are among them. If you are
running debian, do an apt-cache search. Otherwise, go to
www.debian.org and search for packages there.
The Lisp community seems to be growing, not shrinking. It may just
be my perception. The packages are comming and so are the
repositories.
--
One Emacs to rule them all. One Emacs to find them,
One Emacs to take commands and to the keystrokes bind them,
All other programming languages wish they were Lisp.
From: Joe Marshall
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <fzhkexxp.fsf@ccs.neu.edu>
"Andrew Dalke" <······@mindspring.com> writes:
> As an example, here's a quick hack of a way to parse a simple
> stack-based language and make a native Python function out
> of it....
[code elided]
Let's take on something more complicated. A lot more complicated.
Suppose I am solving problems that are best expressed
non-deterministically, and I need a domain language that has the
following non-deterministic constructs:
EITHER --
Used as a mechanism to combine expressions
non-deterministically as in
(either <expr1> <expr2> <expr3> ...)
or, if you prefer infix
<expr1> either <expr2> either <expr3>
or possibly
either:
<expr1>
<expr2>
<expr3>
Whatever the syntax, EITHER introduces a choice-point. It
begins by attempting evaluation of the first subexpression.
If that subexpression returns a value, EITHER returns that
value. If the subexpression `fails', EITHER attempts to
evaluate the next subexpression. The first subexpression
to produce a value is the value of the whole expression.
If all subexpressions `fail', then the EITHER form itself
`fails'.
FAIL --
Causes an expression to `fail'. This means that control is
immediately returned to the nearest enclosing EITHER form
(backtracking) which will then proceed to attempt to evaluate
the next subexpression. If the current subexpression is the
last form in the enclosing EITHER, the EITHER form propagates
the failure up to the next enclosing EITHER.
ALL-VALUES --
Used to collect all possible values returned by a
non-deterministic expression. If all possible choice-points
in the expression yield failure, then ALL-VALUES
deterministically returns an empty collection. Thus failures
cannot propagate past an ALL-VALUES form.
Syntax could be something like
(all-values <expr>)
or
all-values <expr>
or
all-values { <expr> }
ONE-VALUE --
Returns the first possible value returned by a non-deterministic
expression, or some sort of distinguished token if no value
can be found. Also blocks propagation of `failure'.
Since I am unsure of the entire details of the problem I am solving, I
also wish to have these forms integrated into a reasonably complete
computer language. Obviously this new language will have syntactic
differences from anything other language (via the introduction of
these forms), but by and large, the subexpressions of this new
language ought to be something familiar.
So if we extended Lisp, for example, I could write:
(defun an-integer-between (low high)
(if (> low high)
(fail)
(either low (an-integer-between (+ low 1) high))))
(defun pythagorean-triples (n)
(all-values
(let ((opposite (an-integer-between 1 n))
(adjacent (an-integer-between 1 n))
(hypotenuse (an-integer-between 1 n)))
(if (= (+ (* opposite opposite)
(* adjacent adjacent))
(* hypotenuse hypotenuse))
(list opposite adjacent hypotenuse)
(fail)))))
and (pythagorean-triples 10)
would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
on the other hand, if we extended Python, I could write:
def anIntegerBetween(low, high):
if(low > high):
fail
either:
return low
return anIntegerBetween(low + 1, high)
def pythagoreanTriples(n):
all-values:
opposite = anIntegerBetween(1, n)
adjacent = anIntegerBetween(1, n)
hypotenuse = anIntegerBetween(1, n)
if(hypotenuse * hypotenuse == opposite * opposite + adjacent * adjacent):
return [opposite, adjacent, hypotenuse]
fail
and I'd get back something like
[[3, 4, 5], [4, 3, 5], [6, 8, 10], [8, 6, 10]]
-----------------
This is a tricky problem, but one approach in Lisp is to make
ALL-VALUES and EITHER be rather complicated macros.
The advantage of doing this is that the rest of the language, LET,
DEFUN, *, +, conditionals, strings, CLOS, i.e. everything, is pretty
much intact. Since I know that Lisp is a `reasonably complete'
substrate, I don't have to worry about designing and parsing an entire
non-deterministic language. I can just graft my extension on to
something people will be familiar with.
Yes, I know that adding non-determinism to the language is going to
mean a change in how people would program (how could it not?!) but
I'm attempting to *minimize* the intellectual burden by making the
non-deterministic language very similar to one that already exists.
How would one approach this in Python? If Python had macros, then
one could take exactly the same approach as Lisp. What does a Pythonista
do when encountering a problem like this? (I'm actually curious,
not raising rhetorical questions. I assume that there is *something*
one would do, but not being a python hacker, I don't know what it is.)
Joe Marshall <···@ccs.neu.edu> writes:
> Let's take on something more complicated. A lot more complicated.
>
> Suppose I am solving problems that are best expressed
> non-deterministically, and I need a domain language that has the
> following non-deterministic constructs:
>...
> This is a tricky problem, but one approach in Lisp is to make
> ALL-VALUES and EITHER be rather complicated macros.
This is the well known standard approach.
>...
> How would one approach this in Python?
Give up and call out to a Prolog interpreter.
/Jon
On Thu, 23 Oct 2003 12:11:30 -0400, Joe Marshall wrote:
> So if we extended Lisp, for example, I could write:
> (defun pythagorean-triples (n)
> (all-values
> (let ((opposite (an-integer-between 1 n))
> (adjacent (an-integer-between 1 n))
> (hypotenuse (an-integer-between 1 n)))
> (if (= (+ (* opposite opposite)
> (* adjacent adjacent))
> (* hypotenuse hypotenuse))
> (list opposite adjacent hypotenuse)
> (fail)))))
How to write such macros in Lisp? Looks like they would require non-local
rewriting of program structure, I don't see how it's possible at all.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> On Thu, 23 Oct 2003 12:11:30 -0400, Joe Marshall wrote:
>
> > So if we extended Lisp, for example, I could write:
>
> > (defun pythagorean-triples (n)
> > (all-values
> > (let ((opposite (an-integer-between 1 n))
> > (adjacent (an-integer-between 1 n))
> > (hypotenuse (an-integer-between 1 n)))
> > (if (= (+ (* opposite opposite)
> > (* adjacent adjacent))
> > (* hypotenuse hypotenuse))
> > (list opposite adjacent hypotenuse)
> > (fail)))))
>
> How to write such macros in Lisp? Looks like they would require
> non-local rewriting of program structure, I don't see how it's
> possible at all.
Huh? It's not only possible it's been done. Many times. In fact it
is just this sort of thing that people have been trying to explain
that makes them so enormously useful in producing _naturally_
expressive code.
The above example (with some differing details I think) is given by
Paul Graham in 2-3 pages of code in On Lisp in the Nondeterminism
chapter. He then uses this to implement an embedded Prolog in another
couple pages (the continuation style implementation for Prolog is not
the best one for Common Lisp - though probably fine for Scheme with
call/cc. Norvig gives a good one in PAIP, with it's own embedded
compiler - all with macros).
/Jon
On Thu, 23 Oct 2003 19:35:05 -0400, Jon S. Anthony wrote:
> The above example (with some differing details I think) is given by
> Paul Graham in 2-3 pages of code in On Lisp in the Nondeterminism
> chapter.
In Scheme it doesn't use macros but continuations.
On Lisp's implementation of continuations for Common Lisp requires
changing the way functions are written (=defun, =values, =bind, =apply,
=funcall, =lambda). Writing it in a more natural style requires a code
walker ("beyond the scope of this book"), so it's not reusing the language
but reimplementing all the control structures in order to CPS-transform
everything. I don't see how a code walker can CPS-transform primitive
functions defined in C which call back to Lisp (e.g. mapcar) - how does it
do it?
If it can do it without reimplementing each such function, I would be
impressed. If not, this is only a partially correct solution; a full
solution requires continuations and it doesn't need macros.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <smljh25n.fsf@comcast.net>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> On Thu, 23 Oct 2003 19:35:05 -0400, Jon S. Anthony wrote:
>
>> The above example (with some differing details I think) is given by
>> Paul Graham in 2-3 pages of code in On Lisp in the Nondeterminism
>> chapter.
>
> In Scheme it doesn't use macros but continuations.
>
> On Lisp's implementation of continuations for Common Lisp requires
> changing the way functions are written (=defun, =values, =bind, =apply,
> =funcall, =lambda). Writing it in a more natural style requires a code
> walker ("beyond the scope of this book"), so it's not reusing the language
> but reimplementing all the control structures in order to CPS-transform
> everything. I don't see how a code walker can CPS-transform primitive
> functions defined in C which call back to Lisp (e.g. mapcar) - how does it
> do it?
You don't need to CPS convert everything because the backtracking
continuations are upwards only.
On Fri, 24 Oct 2003 01:09:43 +0000, prunesquallor wrote:
> You don't need to CPS convert everything because the backtracking
> continuations are upwards only.
I don't know what are upward continuations but it doesn't seem to be
possible. Assume that during mapcar one lambda returns a choice, and
some further lambda fails. How can macros cause mapcar to go back a few
elements, without reimplementing mapcar? Does Common Lisp support some
restricted kind of continuations?
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <k76vgyyt.fsf@comcast.net>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> On Fri, 24 Oct 2003 01:09:43 +0000, prunesquallor wrote:
>
>> You don't need to CPS convert everything because the backtracking
>> continuations are upwards only.
>
> I don't know what are upward continuations but it doesn't seem to be
> possible. Assume that during mapcar one lambda returns a choice, and
> some further lambda fails. How can macros cause mapcar to go back a few
> elements, without reimplementing mapcar? Does Common Lisp support some
> restricted kind of continuations?
CATCH and THROW are a restricted kind of continuation. The only allow
transfer of control in one direction and the transfer can only take
place once.
If you are curious about how mapcar interacts, I suggest you download
the screamer package from
http://www.ece.purdue.edu/~qobi/software.html
On Fri, 24 Oct 2003 02:18:38 +0000, prunesquallor wrote:
> CATCH and THROW are a restricted kind of continuation. The only allow
> transfer of control in one direction and the transfer can only take
> place once.
It's not enough to implement backtracking (or I'm really confused).
> If you are curious about how mapcar interacts, I suggest you download
> the screamer package from
> http://www.ece.purdue.edu/~qobi/software.html
It CPS-transforms all nondeterministic code. And from what I read I guess
my mapcar example would simply not work - funcall must be used on deter�
ministic functions only, a lambda which uses "either" is nondeterministic,
and mapcar uses funcall internally or is equivalent - and is not handled
specially.
It must reimplement language constructs it wants to work with as I thought.
It shows how macros are useful for implementing a backtracking sublanguage
which looks like Lisp; it doesn't show how to add backtracking to an
existing language.
;;; Limitations
[...]
;;; 6. Doesn't handle most CommonLisp special forms.
;;; Currently handle:
;;; BLOCK
;;; FUNCTION
;;; GO
;;; IF
;;; LET
;;; LET*
;;; MULTIPLE-VALUE-CALL
;;; MULTIPLE-VALUE-PROG1
;;; PROGN
;;; QUOTE
;;; RETURN-FROM
;;; SETQ
;;; TAGBODY
;;; THE
;;; Probably will never handle:
;;; CATCH
;;; DECLARE
;;; EVAL-WHEN
;;; FLET
;;; LABELS
;;; MACROLET
;;; PROGV
;;; THROW
;;; UNWIND-PROTECT
;;; CLtL1 obsolete:
;;; COMPILER-LET
;;; CLtL2 additions:
;;; GENERIC-FLET
;;; GENERIC-LABELS
;;; LOAD-TIME-VALUE
;;; LOCALLY
;;; WITH-ADDED-METHODS
;;; SYMBOL-MACROLET
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> On Thu, 23 Oct 2003 19:35:05 -0400, Jon S. Anthony wrote:
>
> > The above example (with some differing details I think) is given by
> > Paul Graham in 2-3 pages of code in On Lisp in the Nondeterminism
> > chapter.
>
> In Scheme it doesn't use macros but continuations.
I pointed that out. But it's irrelevant to the general capability and
point.
> impressed. If not, this is only a partially correct solution; a full
> solution requires continuations and it doesn't need macros.
The real point here is that even in Scheme where you have
continuations, the implementation here would make use of macros to
provide the natural expression of the intent. It's just that the
macros would expand into stuff using continuations.
/Jon
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <he1zim1n.fsf@comcast.net>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> On Thu, 23 Oct 2003 12:11:30 -0400, Joe Marshall wrote:
>
>> So if we extended Lisp, for example, I could write:
>
>> (defun pythagorean-triples (n)
>> (all-values
>> (let ((opposite (an-integer-between 1 n))
>> (adjacent (an-integer-between 1 n))
>> (hypotenuse (an-integer-between 1 n)))
>> (if (= (+ (* opposite opposite)
>> (* adjacent adjacent))
>> (* hypotenuse hypotenuse))
>> (list opposite adjacent hypotenuse)
>> (fail)))))
>
> How to write such macros in Lisp? Looks like they would require non-local
> rewriting of program structure, I don't see how it's possible at all.
It ain't easy, but it is possible. (In Scheme it is a bit easier
because of first-class continuations, but that's a different issue.)
The key point here is that the authors (Jeffrey Mark Siskind and David
McAllester) of the macros didn't have to implement an entire
non-deterministic language, they merely had to extend the existing one
with a small well-designed set of macros. Things like garbage
collection, interrupts, unwind-protect, parsers, code-generators,
file-system i/o, etc. are time consuming and tricky. By extending
an existing known implementation, they finesse *all* that work.
Additionally, I don't have to learn an entire domain-specific language
to use their package. I learn a few extra macros and I'm done.
(pprint (macroexpand '(all-values
(let ((a (an-integer-between 1 n))
(b (an-integer-between 1 n))
(c (an-integer-between 1 n)))
(unless (= (+ (* a a) (* b b)) (* c c)) (fail))
(list a b c)))))
=>
(LET* ((VALUES 'NIL) (LAST-VALUE-CONS NIL) (TRAIL-POINTER (FILL-POINTER *TRAIL*)))
(CATCH 'FAIL
(LET ((*NONDETERMINISTIC?* T))
(UNWIND-PROTECT
(PROGN
(LET* ((#:DUMMY-728 N)
(#:CONTINUATION-730
(LAMBDA (&OPTIONAL #:DUMMY-710 &REST #:OTHER-711)
(LET* ((#:DUMMY-723 N)
(#:CONTINUATION-725
(LAMBDA (&OPTIONAL #:DUMMY-712 &REST #:OTHER-713)
(LET* ((#:DUMMY-718 N)
(#:CONTINUATION-720
(LAMBDA (&OPTIONAL #:DUMMY-714 &REST #:OTHER-715)
(LET ((C #:DUMMY-714)
(B #:DUMMY-712)
(A #:DUMMY-710))
(IF (NULL (= (+ (* A A) (* B B)) (* C C)))
(FAIL))
(LET* ((#:DUMMY-708 (LIST A B C))
(VALUE #:DUMMY-708))
(GLOBAL
(COND ((NULL VALUES)
(SETF LAST-VALUE-CONS (LIST VALUE))
(SETF VALUES LAST-VALUE-CONS))
(T
(SETF
(REST LAST-VALUE-CONS)
(LIST VALUE))
(SETF
LAST-VALUE-CONS
(REST LAST-VALUE-CONS)))))
(FAIL))))))
(AN-INTEGER-BETWEEN-NONDETERMINISTIC
#:CONTINUATION-720
1
#:DUMMY-718)))))
(AN-INTEGER-BETWEEN-NONDETERMINISTIC
#:CONTINUATION-725
1
#:DUMMY-723)))))
(AN-INTEGER-BETWEEN-NONDETERMINISTIC #:CONTINUATION-730 1 #:DUMMY-728)))
(BLOCK NIL
(TAGBODY
LOOP (IF (= (FILL-POINTER *TRAIL*) TRAIL-POINTER) (RETURN))
(FUNCALL (VECTOR-POP *TRAIL*))
(SETF (AREF *TRAIL* (FILL-POINTER *TRAIL*)) NIL)
(GO LOOP))))))
VALUES)
Joe Marshall <···@ccs.neu.edu> wrote in message news:<············@ccs.neu.edu>...
> "Andrew Dalke" <······@mindspring.com> writes:
>
> > As an example, here's a quick hack of a way to parse a simple
> > stack-based language and make a native Python function out
> > of it....
>
> [code elided]
>
> Let's take on something more complicated. A lot more complicated.
>
> Suppose I am solving problems that are best expressed
> non-deterministically, and I need a domain language that has the
> following non-deterministic constructs:
>
> EITHER --
> Used as a mechanism to combine expressions
> non-deterministically as in
>
> Whatever the syntax, EITHER introduces a choice-point. It
> begins by attempting evaluation of the first subexpression.
> If that subexpression returns a value, EITHER returns that
> value. If the subexpression `fails', EITHER attempts to
> evaluate the next subexpression. The first subexpression
> to produce a value is the value of the whole expression.
> If all subexpressions `fail', then the EITHER form itself
> `fails'.
>
> FAIL --
> Causes an expression to `fail'. This means that control is
> immediately returned to the nearest enclosing EITHER form
> (backtracking) which will then proceed to attempt to evaluate
> the next subexpression. If the current subexpression is the
> last form in the enclosing EITHER, the EITHER form propagates
> the failure up to the next enclosing EITHER.
>
> ALL-VALUES --
> Used to collect all possible values returned by a
> non-deterministic expression. If all possible choice-points
> in the expression yield failure, then ALL-VALUES
> deterministically returns an empty collection. Thus failures
> cannot propagate past an ALL-VALUES form.
>
> ONE-VALUE --
> Returns the first possible value returned by a non-deterministic
> expression, or some sort of distinguished token if no value
> can be found. Also blocks propagation of `failure'.
>
>
> Since I am unsure of the entire details of the problem I am solving, I
> also wish to have these forms integrated into a reasonably complete
> computer language. Obviously this new language will have syntactic
> differences from anything other language (via the introduction of
> these forms), but by and large, the subexpressions of this new
> language ought to be something familiar.
>
> So if we extended Lisp, for example, I could write:
>
> (defun an-integer-between (low high)
> (if (> low high)
> (fail)
> (either low (an-integer-between (+ low 1) high))))
>
> (defun pythagorean-triples (n)
> (all-values
> (let ((opposite (an-integer-between 1 n))
> (adjacent (an-integer-between 1 n))
> (hypotenuse (an-integer-between 1 n)))
> (if (= (+ (* opposite opposite)
> (* adjacent adjacent))
> (* hypotenuse hypotenuse))
> (list opposite adjacent hypotenuse)
> (fail)))))
pythagoreanTriples n =
[ (opposite,adjacent,hypotenuse) |
opposite <- [1..n],
adjacent <- [1..n],
hypotenuse <- [1..n],
opposite^2 + adjacent^2 == hypotenuse^2]
{- or with alternative syntax
pythagoreanTriples n = do
opposite <- [1..n]
adjacent <- [1..n]
hypotenuse <- [1..n]
guard (opposite^2 + adjacent^2 == hypotenuse^2)
return (opposite,adjacent,hypotenuse)
-}
> and (pythagorean-triples 10)
> would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
*Main> pythagoreanTriples 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
pythagoreanTriples n =
[ (opposite,adjacent,hypotenuse) |
let ns = [1..n],
opposite <- ns,
adjacent <- ns,
hypotenuse <- ns,
opposite^2 + adjacent^2 == hypotenuse^2 ]
behaves better... Don't try this with the Lisp.
I wonder if something along the lines of,
[ (x,y) |
range <- rangeOfRanges,
x <- range,
y <- range ]
works with the Lisp version and does the Right Thing, namely give:
[(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)] when rangeOfRanges
is (either (either 1 2) (either 3 4)) or something to that affect
([[1,2],[3,4]] was used to get the above numbers).
> on the other hand, if we extended Python, I could write:
Oops! Wrong language. Also forgot to extend the language. *sigh* I
can't do anything right.
> This is a tricky problem, but one approach in Lisp is to make
> ALL-VALUES and EITHER be rather complicated macros.
>
> The advantage of doing this is that the rest of the language, LET,
> DEFUN, *, +, conditionals, strings, CLOS, i.e. everything, is pretty
> much intact. Since I know that Lisp is a `reasonably complete'
> substrate, I don't have to worry about designing and parsing an entire
> non-deterministic language. I can just graft my extension on to
> something people will be familiar with.
>
> Yes, I know that adding non-determinism to the language is going to
> mean a change in how people would program (how could it not?!) but
> I'm attempting to *minimize* the intellectual burden by making the
> non-deterministic language very similar to one that already exists.
>
> How would one approach this in Python? If Python had macros, then
> one could take exactly the same approach as Lisp. What does a Pythonista
> do when encountering a problem like this? (I'm actually curious,
> not raising rhetorical questions. I assume that there is *something*
> one would do, but not being a python hacker, I don't know what it is.)
(posted mostly for my own amusement though I am interested in how the
rangeOfRanges example is handled)
(cancelled an inadvertant follow-up to clpy. followups to cll)
Helu
* (Darius) <····························@posting.google.com> :
|
| I wonder if something along the lines of,
| [ (x,y) |
| range <- rangeOfRanges,
| x <- range,
| y <- range ]
| works with the Lisp version and does the Right Thing, namely give:
| [(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4)] when rangeOfRanges
| is (either (either 1 2) (either 3 4)) or something to that affect
| ([[1,2],[3,4]] was used to get the above numbers).
I suspect lisp's simple syntax makes this a non-issue, or it "forces
you" to do the right thing. With the SCREAMER package for CL
(referenced elsewhere in this thread)
* (pprint
(all-values
(let* ((range (a-member-of '((1 2) (3 4))))
(x (a-member-of range))
(y (a-member-of range)))
(list x y))))
produces
((1 1) (1 2) (2 1) (2 2) (3 3) (3 4) (4 3) (4 4))
I may have misunderstood 'range'. (A-MEMBER-OF range-list)
non-deterministically returns an element from the range-list. Screamer
provides separate forms for specifying interval ranges
(AN-INTEGER-BETWEEN low high) is specifically a range between
[low..high]. But the example would work on the same principle.
--
Regards
Madhu
From: Joe Marshall
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <oew6u18w.fsf@ccs.neu.edu>
·······@hotpop.com (Darius) writes:
> pythagoreanTriples n =
> [ (opposite,adjacent,hypotenuse) |
> opposite <- [1..n],
> adjacent <- [1..n],
> hypotenuse <- [1..n],
> opposite^2 + adjacent^2 == hypotenuse^2]
>
> {- or with alternative syntax
> pythagoreanTriples n = do
> opposite <- [1..n]
> adjacent <- [1..n]
> hypotenuse <- [1..n]
> guard (opposite^2 + adjacent^2 == hypotenuse^2)
> return (opposite,adjacent,hypotenuse)
> -}
>
>> and (pythagorean-triples 10)
>> would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
>
> *Main> pythagoreanTriples 10
> [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
>
> Oops! Wrong language. Also forgot to extend the language. *sigh* I
> can't do anything right.
Yes, the suggestion was extending the language to support
nondeterminism. That particular problem was illustrative, but it can
obviously be solved via nested looping.
I think this one may be more difficult:
In a directed graph a `k-simple' path is a path from a vertex U to a
vertex V that does not contain any vertex more than K times. A simple
non-deterministic algorithm for enumerating the k-simple paths between
two verticies is this:
(defun k-simple-paths (u v k)
(if (= (node-visits u) k) (fail))
(local (incf (node-visits u)))
(either (progn (unless (eq u v) (fail)) (list u))
(cons u (k-simple-paths (a-member-of (node-children node)) v k))))
(defun a-member-of (x)
(if (null x) (fail))
(either (car x) (a-member-of (cdr x))))
The LOCAL macro arranges for the side effects in its body to be undone
upon failure. Assume that a node is a structure with a field that can
be used to count visits and a field that contains a list of children.
> (posted mostly for my own amusement though I am interested in how the
> rangeOfRanges example is handled)
I'll try it out when I get home. My work computer does not have
Screamer installed.
Joe Marshall <···@ccs.neu.edu> wrote in message news:<············@ccs.neu.edu>...
> ·······@hotpop.com (Darius) writes:
>
> > pythagoreanTriples n =
> > [ (opposite,adjacent,hypotenuse) |
> > opposite <- [1..n],
> > adjacent <- [1..n],
> > hypotenuse <- [1..n],
> > opposite^2 + adjacent^2 == hypotenuse^2]
> >
> > {- or with alternative syntax
> > pythagoreanTriples n = do
> > opposite <- [1..n]
> > adjacent <- [1..n]
> > hypotenuse <- [1..n]
> > guard (opposite^2 + adjacent^2 == hypotenuse^2)
> > return (opposite,adjacent,hypotenuse)
> > -}
> >
> >> and (pythagorean-triples 10)
> >> would return ((3 4 5) (4 3 5) (6 8 10) (8 6 10))
> >
> > *Main> pythagoreanTriples 10
> > [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
> >
> > Oops! Wrong language. Also forgot to extend the language. *sigh* I
> > can't do anything right.
>
> Yes, the suggestion was extending the language to support
> nondeterminism. That particular problem was illustrative, but it can
> obviously be solved via nested looping.
That isn't looping... or it is. It depends on how you look at it.
The above is the standard (naive) way of encoding non-determinism in
Haskell. The list monad is also known as the non-determinism monad.
(Actually Set would be more appropriate theoretically but there are
some technical and semantical issues with that.) The actual runtime
behavior is a depth-first backtracking search due to laziness.
At any rate, below the following is the massively altered version that
very likely works just like Screamer.
Hinze's backtracking monad transformer; will be handy later.
-- Raffael would cry.
newtype BacktrT m a
= BTT { runBacktrT :: forall b.(a -> m b -> m b) -> m b -> m b }
instance Monad m => Monad (BacktrT m) where
return a = BTT ($ a)
(BTT f) >>= k = BTT (\c -> f (\a -> runBacktrT (k a) c))
fail s = mzero
instance Monad m => MonadPlus (BacktrT m) where
mzero = BTT (\c -> id)
(BTT m) `mplus` (BTT n) = BTT (\c -> m c . n c)
instance MonadTrans BacktrT where
lift m = BTT (\c f -> m >>= \a -> c a f)
collect m = runBacktrT m (\a fk -> do as <- fk; return (a:as))
(return [])
This is a bit overpowerful for this purpose, but here's the above
promised massively altered example,
pythagoreanTriples n = allValues $ do
opposite <- amb [1..n]
adjacent <- amb [1..n]
hypotenuse <- amb [1..n]
guard (opposite^2 + adjacent^2 == hypotenuse^2)
return (opposite,adjacent,hypotenuse)
amb = msum . map return
allValues = runIdentity . collect
Far enough from a loop for ya? More seriously, that was part of my
point; this was a rather pathetic example.
> I think this one may be more difficult:
Okay.
[moved]
> The LOCAL macro arranges for the side effects in its body to be undone
> upon failure. Assume that a node is a structure with a field that can
> be used to count visits and a field that contains a list of children.
Changing the spec, eh? Now I have to add state to a pure language as
well as non-determinism. So, some preliminaries; luckily I have them
lying around, along with Hinze's backtracking monad. Knew they'd come
in handy some time and now they're handy two times.
-- I have a more general version of this
type LP s = BacktrT (ST s)
runLP :: (forall s. LP s a) -> [a]
runLP m = runST (collect m)
type LPRef = STRef
newLPRef :: a -> LP s (LPRef s a)
newLPRef = lift . newSTRef
readLPRef :: LPRef s a -> LP s a
readLPRef = lift . readSTRef
writeLPRef :: LPRef s a -> a -> LP s ()
writeLPRef ref a = BTT (\k fk -> do
a' <- readSTRef ref
writeSTRef ref a
k () (writeSTRef ref a' >> fk))
> In a directed graph a `k-simple' path is a path from a vertex U to a
> vertex V that does not contain any vertex more than K times. A simple
> non-deterministic algorithm for enumerating the k-simple paths between
> two verticies is this:
data Node a s = Node !Int a [LPRef s (Node a s)]
-- quick cheezy node type
> (defun k-simple-paths (u v k)
> (if (= (node-visits u) k) (fail))
> (local (incf (node-visits u)))
> (either (progn (unless (eq u v) (fail)) (list u))
> (cons u (k-simple-paths (a-member-of (node-children node)) v k))))
kSimplePaths u v k = do
Node uVisits a uChildren <- readLPRef u
guard (uVisits /= k)
writeLPRef u (Node (uVisits+1) a uChildren)
mplus (do guard (u == v)
return [u])
(do child <- aMemberOf uChildren -- you have node; I assume
u
liftM (u:) (kSimplePaths child v k))
> (defun a-member-of (x)
> (if (null x) (fail))
> (either (car x) (a-member-of (cdr x))))
aMemberOf = amb
Note: I've tested most of this code and this is all of it except for
some imports and compiler flags. I have however changed it some while
copying. So this isn't exactly the code in my files. I'm fairly
confident that it still works, but I haven't run it through a type
checker ;). It does something that looks like working.
> > (posted mostly for my own amusement
this still holds
> I'll try it out when I get home. My work computer does not have
> Screamer installed.
I didn't know what function to call because I just downloaded it,
hacked it to work with CLISP, and never read the documentation or even
extracted it. I'm not sure the version posted by another person does
what I want in general, though I'd be very surprised if I couldn't get
precisely what I wanted.
Personally, I had the impression that you were advocating that macros
let you easily extend Lisp without effectively writing a good chunk of
compiler*, yet Screamer does this. So I don't find Screamer a
particularly good example, especially coupled with the fact that it
isn't a complete or seamless integration. So ranking them: Scheme's
got us both beat hands-down. call/cc let's you define (some of) the
primitives in less than a page and the result is utterly seamless
(with perhaps a few simple syntax-rules to thunkify things). I put
Haskell second for this one. The implementation is pretty simple, the
interface is pretty clean and it's more or less normal monadic Haskell
programming. CL/Screamer is third. It probably wins for speed (it'd
better!), but that isn't too surprising since it's basically a
compiler for a non-deterministic lisp**. If I'm not mistaken Screamer
implements local by searching the form for setf's and replacing them
with it's own version, which makes me wonder what it does if the
setf's aren't obvious (e.g. a compiled closure), I severely doubt it
delivers on it's seeming promise of interopability (no doubt
disclaimed in the documentation unless I'm mistaken), considering it
works be redefining defun, among others, and translation to CPS and
via a codewalker. Basically, I don't see writing the equivalent using
Template Haskell for Haskell, or whatever for Python, or as an
external tool being significantly more complicated than Screamer. No
word from the Pythonistas.
* I agree with this. Macros are the characterizing feature of
(Common) Lisp for me. I think they can be used to good effect and
would like to see Template Haskell move much more toward Lisp macros.
** Actually, I wouldn't be too surprised if a Scheme with a good
call/cc could beat or at least be comparable with Screamer, or even
the Haskell (with a few obvious optimizations). It depends on how
much static analysis and optimization transformations Screamer
performs. If it's mainly just getting CL to CPS then there's
probably a good chance.
From: ·············@comcast.net
Subject: Re: Why don't people like lisp?
Date:
Message-ID: <k76ufbxc.fsf@comcast.net>
·······@hotpop.com (Darius) writes:
>
> Changing the spec, eh? Now I have to add state to a pure language as
> well as non-determinism. So, some preliminaries; luckily I have them
> lying around, along with Hinze's backtracking monad. Knew they'd come
> in handy some time and now they're handy two times.
Sniff sniff....
Wait a second. This isn't Python!
> Personally, I had the impression that you were advocating that macros
> let you easily extend Lisp without effectively writing a good chunk of
> compiler*, yet Screamer does this.
Actually, I am advocating that macros supply a broad range of
advantages from tweaking some local syntax to rewriting a good chunk
of the compiler.
> So I don't find Screamer a particularly good example, especially
> coupled with the fact that it isn't a complete or seamless
> integration.
It isn't perfect by a long shot, but I like the example because it is
in use rather than something academic.
> So ranking them: Scheme's got us both beat hands-down. call/cc
> let's you define (some of) the primitives in less than a page and
> the result is utterly seamless (with perhaps a few simple
> syntax-rules to thunkify things).
Seeing as I work for the PLT Scheme project, how could I object?
> I put Haskell second for this one. The implementation is pretty
> simple, the interface is pretty clean and it's more or less normal
> monadic Haskell programming.
I'm not too familiar with Haskell, but laziness is interesting.
> CL/Screamer is third. It probably wins for speed (it'd better!),
> but that isn't too surprising since it's basically a compiler for a
> non-deterministic lisp**.
Probably. It is a good compromise.
> If I'm not mistaken Screamer implements local by searching the form
> for setf's and replacing them with it's own version, which makes me
> wonder what it does if the setf's aren't obvious (e.g. a compiled
> closure), I severely doubt it delivers on it's seeming promise of
> interopability (no doubt disclaimed in the documentation unless I'm
> mistaken), considering it works be redefining defun, among others,
> and translation to CPS and via a codewalker. Basically, I don't see
> writing the equivalent using Template Haskell for Haskell, or
> whatever for Python, or as an external tool being significantly more
> complicated than Screamer. No word from the Pythonistas.
Well, I wouldn't `call out' a Python implementation that had the same
restrictions.