Lisp

At this point we’ve developed a complete, though very simple, interpreter and runtime environment.  To some degree, this interpreter is all we need.  It can express any function, it can easily be extended, it has a simple parser, and it has a working garbage collector.  What more could we ask for?  Life is good.

Life is good, that is, until we ask somebody else to use it.  Their first response is probably an annoyance at the syntax — it’s a little surprising to have to write (+ 1 1) after grade school has burned 1 + 1 into our minds — and, truth be told, the S-Expression syntax isn’t the most natural or compact for every problem.

Luckily we can, with a little work, entirely eliminate this complaint by creating a parser generator — a function that takes as input a grammar (a formal description of a language), and produces as output a parser for that language.

Read the rest of this entry »

In the previous articles of this series we’ve seen how to create a simple Scheme interpreter, then how to write an S-Expression parser to feed the interpreter, and in the last article we saw how to most conveniently bind C++ functions to our interpreter with the strategic application of template classes and a “meta-circular” code-generator that built up a vital part of our interpreter (using our interpreter to do it).

Though we’ve come a long way, there’s still one glaring hole in our interpreter design: we’ve left the allocate<T> function unspecified.  This function is meant to allocate a garbage collected value of type T, which implies that we’ve got to write a garbage collector.  In this article, that’s exactly what we’ll do.

Read the rest of this entry »

Paul Graham released a new dialect of Lisp at http://arclanguage.org/ Arc is designed above all for exploratory programming: the kind where you decide what to write by writing it. A good medium for exploratory programming is one that makes programs brief and malleable, so that’s what we’ve aimed for. This is a medium for sketching software. […]

Lab49 has created a public repository for open source software projects.

I have a few projects up that I’d like to tell you about.
Read the rest of this entry »

If you can’t work with us, work like us.

Details inside …
Read the rest of this entry »

We recently had an internal presentation covering a variety of fundamental theories of computation that underly several important programming languages. Here are a few papers that might help explain those theories in more depth (if not the actual interpreters we developed):

• Foundational Calculi for Programming Languages
• Introduction to Lambda Calculus
• Making [Erlang] (Joe Armstrong’s PhD thesis)

Read the rest of this entry »

The Earley Parser is a general method for parsing any context-free grammar. Although it avoids the significant faults of its narrower associates (e.g.: infinite loops on left recursive rules in top-down parsers, or reduce-reduce conflicts on ambiguous rules in table-based parsers), it’s a very inefficient algorithm.

A few years back I implemented Earley’s algorithm, and bound it to a small Scheme interpreter I’d made. The result is a simple environment for interactively creating parsers and experimenting with their output:

Download Earley.zip (227 KB)

An example of an interaction one might have:

> (define arith-parser
(make-parser
(concat
“E ::= Val | Val Op E;”
“Val ::= Num | \”(\” E \”)\”;”
“Op ::= \”+\” | \”-\” | \”*\” | \”/\”;”
“Num ::= ‘[0-9]+’;”
)))

> (arith-parser “(5+3)*2″)
(E (VAL “(” (E (VAL (NUM “5″)) (OP “+”) (E (VAL (NUM “3″)))) “)”) (OP “*”) (E (VAL (NUM “2″))))

Read the rest of this entry »

A year or so ago, I wrote this small interactive interpreter as a tool to help with some other work I was doing. It might be of some general interest to anybody interested in Scheme.

Download Lisp49.zip (134 KB)

Read the rest of this entry »

Peter Seibel, author of the really rather fine book Practical Common Lisp is speaking at the NYC Lisp User’s group, on May 9th at 7PM at the Trinity Lutheran Church. Full directions on their site here. I’m going to be away unfortunately, but it sounds fun. And it’s in the East Village, so you can readily go drinking with Lev afterwards.

LSharpyard longest moviemovies swingerfree length xxx movies fullsex free online movieshorny moviesmovies black lesbiansapphic extreme moviesfree xxx movie directory adult Map

(defun m (i j k)
(cond ((= i 0) (1+ k))
((and (= i 1) (= k 0)) j)
((and (= i 2) (= k 0)) 0)
((= k 0) 1)
(t (m (1- i) j (m i j (1- k))))))

eval (m 4 4 4) => ?

The format is annoying, but the material is interesting. Click the link on the left called “Design Patterns in Dylan or Lisp” if you want to get to the basics. Basically a thesis on how Design Patterns are a compensation for limitations in OO languages.

Design Patterns and Lisp

http://www.gigamonkeys.com/book/