adamhaney / lispy

An implementation of scheme that can call python modules

lispy

An extension of Peter Norvig's lispy (http://norvig.com/lispy.html) which includes the ability to access symbols from python packages as if they were written in lispy.

This experiment was initially intended to let me play with scheme while still having access to python's batteries.

Getting Started

To start hacking with the latest "stable" (we're being very liberal with english here) version of lispy you simply need to

$ pip install lispy
$ lispy

This will open a lispy repl, for more commandline options run

$ lispy --help

By default Lispy uses a scheme dialect as described by Peter Norvig in his minimalist implementation of scheme (http://norvig.com/lispy.html) once you've familiarized yourself with this implementation you're ready for some of the "cool" stuff we've layered on top of Norvig's implementation.

Lispy can access any python module in python environment it's run from (note that lispy can also be run from inside a virtual environment, though that's not well documented yet, you can reach out to me or open an issue if you'd like help with this). In order to access a function or library from a python module simply call it using the colon symbol notation.

> (print os:environ)

Also in order to eval a bit of python code (to for example access the builtin python functions) simply namespace the function name with py:

> (py:getattr datetime:datetime "now")

is equivalent to

>>> import datetime
>>> datetime.datetime.now()

Motivation

I've been writing a lot of python code, and I love the python ecosystem. It has wonderful tools for web application development (Django, Flask, Pyramid), data munging (Beautiful Soup, requests) and data analysis (NumPy, SciPy, Pandas, IPython). I'd like to learn more about the internal implementation of python, its introspection abilities and its design decisions. I'd also like to better understand the LISP ecosystem, what better way than implementing a LISP in python.

Current Features

• A minimal scheme implementation in Python (based on Peter Norvig's lispy)
• A scheme implementation which can call python functions within the same process
• The begining of a "dialect framework" which will allow customized lisp dialects with changes to the lanage implemented in either python or a lispy dialect

Architecture

I'm doing my very best to keep this language rather sparse, but configurable. There are many LISP dialiects and rather than start bikeshedding wars about the way that this LISP on python should be implemented I'd like to make language decisions configurable with reasonable defaults. Because of this I've created the concept of "dialects" currently there are two dialects the 'norvig' dialect which tries to stay true to Peter Norvig's original implementation of LISP in python and the "haney" dialiect which includes language additions that I think are interesting.

As we add features to the language or pieces from other languages I intend to also implement them as seperate dialects so that the mechanics of parsing, scoping, and evaluation can be snapped together to form a lisp that solves the problem at hand for a given developer. This also has the added benefit of (potnentially) being able to knit together lisp code written in many dialects together into python (and Java using Jython).

A dialect is currently not very well defined, but it will include a Scope object that determines scoping rules, an eval function or object, and a SpecialForms object. It will also include a settings variable that will list the class paths for the definitions of these various components so a dialect that only needs to change a particular aspect of the language can inherit from other dialects.

When a new language feature is added by me it wil attempt to follow this loosely coupled pattern. This will, hopefully allow us to make the language modular, and well tested enough that we can add language features to solve domain specific problems better than other languages (there are plans for work that would enable easier distributed systems and parallel computing problem solving)

Goals

This is currently a pet project to facilitate learning the LISP and scheme ecosystems and to bring about a better understanding of the theory and complexity of language design. My roadmap includes several additions to lispy to make it a toolkit for python developers who might be interested in dipping their toe in LISP. For functionality that's left to be implemented please check the issue tracker for the project at https://github.com/adamhaney/lispy/issues

Anti-Goals

There are a few things this project is not aiming to achieve. While I do want lispy to be able to run in python 2.x and 3.x I do not intend to mask some of the differences between 2.x and 3.x namely the different ways the two python branches handle math (in 2.x integer division returns a truncated value, in 3.x it returns a float). Trying to translate between these two design decisions is outside the scope of this project.

lispy's Issues

Implement the features of lispy2

I didn't realize that Norvig had included a new version of lispy (lispy2) that includes many of the features I was interested in implementing.

http://norvig.com/lispy2.html

Integrating this portion of the code base into lispy could eliminate the process of implementing reader macros (#10 ) which could allow us to move on to other more exciting language features. Only a portion of this code base should be used for reference and the changes from this version should be contained within the norvig dialect.

Test and fix codebase for jython

Currently we're not testing against jython, but being able to run in jython would be really cool because the jython interpreter can run much faster in some situations and would give lispy access to Java libraries.

Add automatic parallelization of maps and nested forms

Currently python is plagued by the GIL, wouldn't it be nice if we broadcast s-expressions to eager mapping interpreters so that they could be evaluated outside the GIL?

Proposed approach:

• A master process is the command and control that serves as the entry point to the running program
• Workers are spawned in the background on startup and work is fed to them when functions that are guaranteed parallelizable can be called on multiple workers send those functions down to the workers
• Add options to call maps etc without parallelization

Add better developer UI to the REPL

Currently you can't backspace in the repl or press the up arrow to find previous code. It would be much nicer if the REPL functioned more like the python REPL.

Set up scoping for python builtins

Decouple scoping rules from other parts of dialect definitions

Currently (as of 6/28/13) the scoping class is being imported by the norvig dialect directly (which makes sense for now, norvig scheme uses norvig scope) but in the future it would be nice if this scoping rule was decoupled by configuration (this might also bring about the need to do a Cartesian of all possible language parts with all other language parts and run a test suite against them for integration testing).

Add support for a shebang

It would be really cool if I could write lispy programs and call them as

!/bin/lispy

at the top of a bit of lispy code and have it be evaluated.

Set up testing framework and continuous integration

Add a rational datatype

One of the cool parts of common lisp is the fact that it returns rationals in terms of a set of tuples (numerator / divisor) so may conducted with this type is absolutely correct with no rounding error.

A python implementation of this in C https://gmpy2.readthedocs.org/en/latest/

Implement memoization as a a language level feature

It would be cool if function results were stored in a cache so that recursive computations could be implemented without recomputing values.

Ideally IMHO this a cache object should be configurable as an argument to the interpreter so that decisions about cache expiration and storage can be handled by the object (think storing memoized results stored in a large memcached cluster, or an approach that uses caching techniques smarter than LRU based on function "expense").

Implement a built in function profiler

For memoization/debuging etc it would be interesting to know the ammount of time spent in given functions (cpu time/wall clock time/time spent in IO wait) etc. This could be used for all sorts of goodies.

Add support for calling lispy code from outside files

Currently you can access outside python modules with the ":" syntax (ie (print os:environ)) but you can't do the same for other lispy files, add support to the norvig dialect to do this

Add a type system

Python is dynamically typed. Which is great, but can lead to some rather frustrating bugs. Functional languages like Haskell make their type system an aid to a developer (instead of a hinderance like some statically typed languages).

I think it would be very interesting if lispy could enforce types (not sure if this should be optional or if a type configuration could take place as a part of a dialect so that a "typed" dialiect would require type annotations).

Typed racket (http://docs.racket-lang.org/ts-guide/ts-guide.pdf) seems like a good starting point for such a system though research (and honestly writing more exploratory code in) into other strongly typed functional languages could be enlightening.

Attempt to detect impure functions

Pure functions are functions that always have the same result for a given input. This implicitly means that all functions that don't make system calls are pure (as system calls allow IO, time references, randomness, etc).

I would be interesting to me to detect when code did things like this. There are a few features that could build off of such a system

1. Invalidate memoization / don't memoize none pure functions
2. Monads / Forcing functions that do IO to ask permission.
3. Deterministic debugging / profiling?

Add support for reader macros

Not too sure how to do this, but everyone in the LISP community always pitches reader macros as the best reason to use LISP, so we should probably implement them in Lispy.

Experiment with Lazy Evaluation

Since lispy is aimed at mainly providing a functional environment it would be very interesting to me if return types could be lazy. Currently I can think of a very simple way that this would work:

Class LazyResult(object):
    expression = <non evaluated expression>

    def getattr(self, *args, **kwargs):
        return expression.getattr(self, *args, **kwargs)

Expressions instead of being evaluated could just be stored in lazy results that were returned (and any operation against them would cause them to be evaluated). This is just a rough idea and I'm sure it would be more complicated.