Introducing Evo: The Original Purpose of Lispy

When I first envisioned the Lispy project I had only one goal in mind, which I’ll get to soon. As I started writing code, first in Scheme, then C then again in Scheme, the Lispy project evolved into something else. It changed into a platform for me to learn more about programming and the implementation of language features. Writing Lispy, in all its variations, has been a very educational and rewarding experience, so much so that I consider the project an overwhelming success, even though I didn’t realize the original purpose.

So what was the original purpose of Lispy? I’ll give you the tag line that I wrote when Lispy was nothing but an idea… Lispy is a distributed self-optimizing program by example language.

What does that mean? When I first became interested in programming I had 2 goals; to create a program like MetaStock (I’ve since written pyTrade) and to create Artificial Intelligence. Modest goals, I know. In my AI research I came across genetic programming and immediately took a liking to it, probably because I was still new to writing code and the idea that I could write code that wrote code fascinated me.

The main problem with genetic programming is that it is often difficult to write fitness tests for your problems. Somewhere along the way I noticed that programmers were writing fitness tests all the time in the form of unit tests for their code. In addition, the fact that 99% of the time the CPU sits idle while we browse reddit, kept rattling around in my head. Why not take advantage of those wasted cycles by using a programming language that used those cycles to optimize the code you just wrote?

Then I had another idea. Why write code at all? Why not just write the unit tests and let the code evolve on its own? It took me about an hour to realize that this wasn’t going to work on anything but the smallest applications. However another few weeks and I realized that, maybe it could work, given enough computers were running Lispy.

Anyway I have about 25 half-finished papers on Evo which I might get around to finishing and posting here. I’ll give the highlights and post a link to the github account where you can find more info. Evo is meant to be integrated with Lispy (though I don’t know when I’ll get around to that).

Evo is an evolutionary search based function optimizer. It provides an interface for defining new modules and functions as well as an evolutionary programming based method for optimizing those functions. Evo does not use the standard generational approach to GP, rather it uses “gene pools”, that contain functions of indefinite life, from which new functions can be evolved and tested one at a time.

When defining an Evo function you can choose to optimize it for speed, space or code length. Each function can have multiple gene pools that are each optimized for a different purpose. Using gene pools instead of a single population generational approach helps to avoid stagnation within the population as is a common occurrence with the standard generational model.

Evo is very much unfinished, however it can successfully run on its own and evolve solutions to problems. Because of this I am going to put the code out there in case anyone wishes to contribute. I used the implementation of Evo as an excuse to firm up my understanding of closures, as a result the majority of the program is written in a slightly OOP fashion. There is also a Tk based GUI for browsing modules and adding new functions and fitness tests, though its use is completely optional.

Without further ado, here’s the link to the Evo repo.

Scheme in Lispy

Now that we have our basic interpreter set up, it’s time to start writing some languages. Before we start experimenting with Lispy, we will implement a small subset of Scheme.

Implementing Scheme will let us test our implementation with a language that is already specified.

Create a new file, I’ll call it scheme_in_lispy.lispy, but you can name it whatever you like. We’ll be doing most of our work here so I’ll leave out the main lispy file.

We’ll start with define-primitive which we’ll simply copy from the old syntax.chicken, though we won’t use it until later.

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr)))
                 env)))

The first primitive form we’ll introduce is define. For this we’re going to do a little more copy and paste. Scheme’s define form is just a combination of our previous define and function. define sets a value to a symbol, but it also provides a shorthand for setting a lambda to a symbol (define (a x) x) is equivalent to (define a (lambda (x) x)). To figure out which one we need to produce, we only have to look at the first value in expr. If it is a symbol we just set the symbol name to the evaluated value. If it is a list we create a proc and set that as the value to symbol.

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))
(define a 42)
;===> #<unspecified>
a
;===> 42
(define (b x) x)
;===> #<unspecified>
(b 42)
;===> 42

lambda is simple after that. All we have to do is rip out the (make-proc …) procedure and drop it into lambda with one small change. With define we received a procedure definition as ((name arg-1 arg-2 arg-n) body), however an anonymous function does not have a name. We receive a lambda definition as ((arg-1 arg-2 arg-n) body).

(scheme-syntax lamb
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               env)))
(define c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42
((lambda (y) y) 42)
;===> 42

if is a straight copy/paste from our old syntax file.

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))
(if 1 2 3)
;===> 2
(if #f 2 3)
;===> 3

quote is one of the simplest forms in Scheme. All quote does is return its argument unevaluated.

(scheme-syntax quote
  (lambda (expr env)
    (car expr)))
(quote (+ 1 2))
;===> (+ 1 2)

set! is pretty simple too, it’s basically just a limited form of define.

(scheme-syntax set!
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))
(set! a 42)
;===> #<unspecified>
a
;===> 42
(set! b (if #f 2 3))
;===> #<unspecified>
b
;===> 3
(set! c (lambda (x) x))
;===> #<unspecified>
(c 42)
;===> 42

begin is pretty straightforward, in fact we have already implemented it as eval-body (we used it for procedures).

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))
(begin 1 2 3)
;===> 3
(begin (define x 42) x)
;===> 42

let is almost the same as begin, except we have to extend the environment with the given bindings before we evaluate the body of the let. This version uses cons cells instead of 2 element lists to set symbols. You could add support for (let ((x 35) (y 7)) …) if you like. Since making a Scheme is not my goal, I will not do that now.

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))
(let ((x . 35) (y . 7)) (if x x y))
;===> 35
x
;===> Error: Unbound symbol: x

equal? is easily snarfed from the underlying Scheme. equal? could also be defined using define-primitive (define-primitive equal? equal?).

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))
(equal? 2 2)
;===> #t
(equal? 2 (if 1 2 3))
;===> #t
(equal? 1 2)
;===> #f

Finally we’ll snarf some primitives from the underlying Scheme to make our mini-Scheme a little more usable.

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)
(+ 1 2)
;===> 3
(- 3 2)
;===> 1
(< 1 2)
;===> #t
(> 1 2)
;===> #f
(cons 1 2)
;===> (1 . 2)
(car (cons 1 2))
;===> 1
(cdr (cons 1 2))
;===> 2
(define (loop x) (if (< x 0) (print 'finished) (begin (print x) (loop (- x 1)))))
;===> #<unspecified>
(loop 3)
3
2
1
0
finished
;===> #<unspecified>

There is a lot that is left out, error handling and advanced features like call-with-current-continuation or macros, for example. But for a simple Scheme to help test the implementation of our interpreter this is just about all we need.

Most of the rest of Scheme can be implemented as derived forms from the primitives we just defined. What cannot be, can be implemented using our scheme-syntax macro.

Finally, here’s the full source of scheme_in_lispy.lispy for you to play with.

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr)))
                 env)))

(scheme-syntax define
  (lambda (expr env)
    (if (list? (car expr))
        (set-symbol! (caar expr)
                     (make-proc (cdar expr)
                                (cdr expr)
                                env) env)
        (set-symbol! (car expr) (lispy-eval (cadr expr) env) env))))

(scheme-syntax lambda
  (lambda (expr env)
    (make-proc (car expr)
               (cdr expr)
               env)))

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))

(scheme-syntax quote
  (lambda (expr env)
    (car expr)))

(scheme-syntax set!
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))

(scheme-syntax begin
  (lambda (expr env)
    (eval-body expr env)))

(scheme-syntax let
  (lambda (expr env)
    (eval-body (cdr expr) (extend-environment (car expr) env))))

(scheme-syntax equal?
  (lambda (expr env)
    (equal? (lispy-eval (car expr) env)
            (lispy-eval (cadr expr) env))))

(define-primitive + +)
(define-primitive - -)
(define-primitive < <)
(define-primitive > >)
(define-primitive car car)
(define-primitive cdr cdr)
(define-primitive cons cons)
(define-primitive print print)

GOTO Table of Contents

Lispy in Scheme | Lispy Procedures

The goal for this part is to implement procedures in Lispy.

To begin implementing Lispy procedures we have to define a procedure type, just like we did with primitives. A procedure has 3 basic parts. A list of parameters, a body and an environment. So we’ll set up our new procedure type with these fields and call it proc to avoid a name clash with Scheme’s procedure?.

Like primitives, procedures are handled by the lispy-apply procedure. We’ll change lispy-apply to use a cond instead of nested ifs and temporarily put in a placeholder for procedures. In addition we need a way to define new procedures from within Lispy. If we were writing a Scheme, the define form would allow us to both set symbols and procedures. For the moment we’ll separate the two usual jobs of define and create a new form (function (parameters) body) to set procedures.

(use srfi-69)

(define global-syntax-definitions (make-hash-table))
(define-record primitive function)
(define-record proc parameters body environment)

(define (current-environment env) (car env))
(define (enclosing-environment env) (cdr env))

(define (extend-environment bindings base-environment)
  (cons (alist->hash-table bindings) base-environment))

(define the-global-environment (extend-environment '() '()))

(define (set-symbol! symbol value env)
  (hash-table-set! (current-environment env) symbol value))

(define (lookup-symbol-value symbol environment)
  (if (null? environment)
    (error 'unbound-symbol "Unbound symbol:  " symbol)
    (if (hash-table-exists? (current-environment environment) symbol)
        (hash-table-ref (current-environment environment) symbol)
        (lookup-symbol-value symbol (enclosing-environment environment)))))

(define (self-evaluating? expr)
  (or (number? expr) (string? expr) (char? expr) (boolean? expr)))

(define (lispy-eval expr env)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-symbol-value expr env))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr) env)
              (lispy-apply (lispy-eval (car expr) env) (eval-arguments (cdr expr) env))))))

(define (eval-arguments args env)
  (map (lambda (x) (lispy-eval x env)) args))

(define (lispy-apply procedure arguments) 
  (cond ((primitive? procedure)
           (apply (primitive-function procedure) arguments))
        ((proc? procedure)
           "Attempted to apply a Lispy procedure")
        (else
           "Error: Undefined procedure")))

(hash-table-set! global-syntax-definitions 'scheme-syntax
  (lambda (expr env)
    (hash-table-set! global-syntax-definitions (car expr) (eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'load
  (lambda (expr env)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e env)
                             (loop (read f)))))))

((hash-table-ref global-syntax-definitions 'load) '("syntax.chicken") the-global-environment)

(define (repl)
  (define input (read))
  (print ";===> " (lispy-eval input the-global-environment))
  (repl))

syntax.chicken

(scheme-syntax define
  (lambda (expr env)
    (set-symbol! (car expr) (lispy-eval (cadr expr) env) env)))

(scheme-syntax if
  (lambda (expr env)
    (if (lispy-eval (car expr) env)
        (lispy-eval (cadr expr) env)
        (lispy-eval (caddr expr) env))))

(scheme-syntax define-primitive
  (lambda (expr env)
    (set-symbol! (car expr)
                 (make-primitive (eval (cadr expr))))))

(scheme-syntax function
  (lambda (expr env)
    (set-symbol! (caar expr)
                 (make-procedure (cdar expr)
                                 (cdr expr)
                                 env) env)))
(function (a x) x)
;===> #<unspecified>
a
;===> #<proc>
(a 42)
;===> Attempted to apply a Lispy procedure

Now that we have a basic outline for what our procedures will look like, we can focus on making them work!

To apply a procedure we have to evaluate the body. In the example above the body of the procedure is just x. However we can’t just evaluate x because x is not bound to anything yet.

First we need to create a new environment and bind the parameters to the arguments supplied in the procedure call. In this case we have to bind x to the value 42. For this we’ll use a helper procedure called assign-values.

The body is evaluated in the same way that we evaluate arguments. The difference is that we only return the last expression of the body. For now we’ll create a procedure named eval-body that will call eval-arguments, then return the last evaluated argument (it’s not the most efficient implementation, but it is simple and reuses code that we have already wrote).

(use srfi-69)
(use srfi-1)

(define global-syntax-definitions (make-hash-table))
(define-record primitive function)
(define-record proc parameters body environment)

(define (current-environment env) (car env))
(define (enclosing-environment env) (cdr env))

(define (extend-environment bindings base-environment)
  (cons (alist->hash-table bindings) base-environment))

(define the-global-environment (extend-environment '() '()))

(define (set-symbol! symbol value env)
  (hash-table-set! (current-environment env) symbol value))

(define (lookup-symbol-value symbol environment)
  (if (null? environment)
    "Error: Unbound symbol";(error 'unbound-symbol "Unbound symbol:  " symbol)
    (if (hash-table-exists? (current-environment environment) symbol)
        (hash-table-ref (current-environment environment) symbol)
        (lookup-symbol-value symbol (enclosing-environment environment)))))

(define (self-evaluating? expr)
  (or (number? expr) (string? expr) (char? expr) (boolean? expr)))

(define (lispy-eval expr env)
  (cond ((self-evaluating? expr) expr)
        ((symbol? expr) (lookup-symbol-value expr env))
        (else
          (if (hash-table-exists? global-syntax-definitions (car expr))
              ((hash-table-ref global-syntax-definitions (car expr)) (cdr expr) env)
              (lispy-apply (lispy-eval (car expr) env) (eval-arguments (cdr expr) env))))))

(define (eval-arguments args env)
  (map (lambda (x) (lispy-eval x env)) args))

(define (eval-body args env)
  (last (eval-arguments args env)))

(define (assign-values procedure args)
  (map cons (proc-parameters procedure) args))

(define (lispy-apply procedure arguments) 
  (cond ((primitive? procedure)
           (apply (primitive-function procedure) arguments))
        ((proc? procedure)
           (eval-body (proc-body procedure)
                      (extend-environment (assign-values procedure arguments)
                                          (proc-environment procedure))))
        (else
           "Error: Undefined procedure")))

(hash-table-set! global-syntax-definitions 'scheme-syntax
  (lambda (expr env)
    (hash-table-set! global-syntax-definitions (car expr) (eval (cadr expr)))))

(hash-table-set! global-syntax-definitions 'load
  (lambda (expr env)
    (define f (open-input-file (car expr)))
    (let loop ((e (read f)))
      (if (equal? e #!eof) "Successfully Loaded!"
                           (begin
                             (lispy-eval e env)
                             (loop (read f)))))))

((hash-table-ref global-syntax-definitions 'load) '("syntax.chicken") the-global-environment)

(define (repl)
  (define input (read))
  (print ";===> " (lispy-eval input the-global-environment))
  (repl))
(function (test pred conseq alt)
  (if pred conseq alt))
;===> #<unspecified>
(test 1 2 3)
;===> 2

With that, we have implemented procedures in Lispy! In 58 lines we have defined an interpreter framework that we can use to write just about any parenthesized, applicative-order, lexically scoped language. In the next few parts we’ll implement a very basic Scheme, then McCarthy’s LISP and finally begin work on the implementation of Lispy.

Also note that there is very little error-checking going on here. For instance calling a procedure with the wrong number of arguments results in the whole interpreter crashing. This would not be good in a production language. However including error checking in this code would probably triple its size at least. The point of this exercise is to learn the concepts, not write a bullet-proof language.

GOTO Table of Contents