December 2009 Mini-sprint Report and January 2010 Mini-sprint

[Jon Riehl]

Hey all,

I've posted a summary of our activities from the last mini-sprint here:

http://log.jonriehl.com/?p=85

Please let me know if you have any questions or comments.

Tyler and I are also going to have another mini-sprint this Friday
(tomorrow) in my office at the University of Chicago. Sorry for the
late notice, but again, if you have any comments, ideas, or questions,
please let me know. All are also welcome to join us later (about
5:30-ish) for happy hour.

Finally, I have replaced the MyFront parser with a new parser design.
This new parser should work in Python 2.6, so please update and try it
out if you have a chance.

Tyler: Do you have a page, blog, or profile I can link to? I was
thinking a linkedin profile at the very least.

Thanks!
-Jon

[Tyler Green]

Yo mython,

I finished the mylisp basic implementation. It handles, more or less,
all the core lisp special functions. What I would like to do now is
1) trampoline the "interp" function so it will be tail-recursive 2)
start writing the lisp standard prelude, in lisp, using mython, in the
same source file lispInterp.py source (maybe this would be a nice
concrete demonstration of mixing code in the same file). Also, I am
looking for ideas to call python functions from lisp using some
special syntax to clearly separate the namespaces, maybe (p.join ""
"abc" "def" "ghi") or p(join "" "abc" "def" "ghi"). Obviously this
will introduce complications to the parser/interpreter but snarfing
python's stuff certainly worth it. Anyway, I would like guidance on
#1 and #2 and thoughts on #3. Thanks.

-Tyler

[Jon Riehl]

Hey Tyler,

1. What do you mean trampoline the interp function? I didn't see
this mentioned in SICP.

I hope you aren't drinking my trampoline kool-aid. The trampoline
parsing method I developed is not "tail recursive", but instead uses
generators to keep a kind of call stack in the heap (so the Python
call stack is flat).

2. This is entirely doable. I don't think you'll need the full power
of Mython here; unless you want to avoid using escape characters for
special cases, just using a multi-line string should work. I assume
that you'll use the prelude at compile time, so the embedded code will
be checked then anyway.

Something like the following:

prelude_src = """(define ...)
...
"""
_, env = lisp_interpreter(prelude_src)

3. Are lists not good enough? What about quasi-quotes?

Something like this:

(python-lookup `(basil lang lisp parser))

This would only fail if there is some identifier in Python that is
invalid in Lisp.

Thanks,
-Jon

> --
> You received this message because you are subscribed to the Google Groups "mython" group.
> To post to this group, send email to myt...@googlegroups.com.
> To unsubscribe from this group, send email to mython+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/mython?hl=en.
>
>

[Tyler Green]

Hey,

I need to trampoline the interp function (called eval in SICP)
because python is not tail recursive (unlike the underlying scheme in
SICP). Norvig's Paradigm of AI talks about how to do this in Common
Lisp (which is not guaranteed to be tail recursive) but unfortunately
I left my copy at my old house in Dallas... I tried using the
@tail_recursive decorator but that is somewhat of a hack and only
cannot be applied in general to just any function. Anyway, just to
make sure, I did a factorial defined as

(def fac (fn (x acc) (if (= x 1) acc (fac (- x 1) (* x acc)))))

and for (fac 200 1) got of course:

RuntimeError: maximum recursion depth exceeded in cmp

For 2) I guess I could just use a multi line string but will probably
just define them all in a separate file to get syntax highlighting and
other benefits

-Tyler

[Jon Riehl]

Hi Tyler,

On Tue, Feb 9, 2010 at 5:59 PM, Tyler Green <tyler....@gmail.com> wrote:
> I need to trampoline the interp function (called eval in SICP)
> because python is not tail recursive (unlike the underlying scheme in
> SICP).  Norvig's Paradigm of AI talks about how to do this in Common
> Lisp (which is not guaranteed to be tail recursive) but unfortunately
> I left my copy at my old house in Dallas...  I tried using the
> @tail_recursive decorator but that is somewhat of a hack and only
> cannot be applied in general to just any function.  Anyway, just to
> make sure, I did a factorial defined as
>
> (def fac (fn (x acc) (if (= x 1) acc (fac (- x 1) (* x acc)))))
>
> and for (fac 200 1) got of course:
>
> RuntimeError: maximum recursion depth exceeded in cmp

Okay. After consulting LtU
(http://lambda-the-ultimate.org/node/2374), I've determined you are
asking for help with exactly the approach I'm using in the new parser
framework. The idea is to decouple the call stack of the interpreter
from the call stack of the interpreter's implementation language. In
Python, generators come in handy for this, and they are what I use to
get the parser's stack off of Python's call stack (other approaches
might involve CPS transforms, or using call/cc).

Unfortunately, a detailed explanation is harder for me to provide than
some sample code (see attached). I recommend you review my code, run
it with the verbose output, and read about generators in Python if you
don't understand what I'm doing.

The trampoline code (MyInterp.my_eval()) simply looks at the top of a
generator stack. It then asks the top generator, "what do I need to
do next?". The generator may do one of two things:

1. Tell the evaluator to push another evaluation context (contained in
a MyContext object).

2. Tell the evaluator that the generator has come up with a value
(contained in a MyResult object).

This was all hacked together in about an hour, and I'm not sure this
is the exact approach you want to take. I certainly don't like how
stateful this is (in some sense generators are supposed to hide state
in local variables, but we need a result stack to implement
coroutines). Another approach is to define an evaluator that manages
an evaluation state (which is either a 3-tuple of context stack,
environment, and expression, or a 2-tuple of context stack, and
value), but this seems easier to read and implement in a language with
pattern matching (this is the evaluation machine, for which I have a
Stratego implementation in .../sandbox/tapl/).

> For 2) I guess I could just use a multi line string but will probably
> just define them all in a separate file to get syntax highlighting and
> other benefits

Sounds fine.

Thanks,
-Jon