Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
182 lines (131 sloc) 6.83 KB

with-stack.el - An embedded stack language for Emacs Lisp


with-stack.el implements a stack based language inside emacs lisp. The language will be familiar to anyone who knows Forth, and more familiar to anyone who knows factor, on which it is more closely based (and towards which it will develop, although for various reasons it will never really converge with).

With stack lets you write something like this:

(setq x (||| 1 1 2>+))	 

Which should be read as a regular emacs expression until the form ||| which tells emacs to start acting like a stack language. The rest of the form reads, in words, "push 1 on the stack, push 1 on the stack, and then take two arguments off of the stack and pass them to the emacs lisp + function, pushing the result onto the stack. Finally, return the top of the stack."

One concession to the emacs environment is that the emacs lisp stack language uses the emacs lisp reader. Numbers, strings, and vectors are indicated the same way as in elisp, and pushed onto the stack as they are encountered. Quoted objects are pushed onto the stack also. There is one wrinkle, however. the syntax n>symbol instructs the stack language to take n arguments from the stack and pass them to the elisp function indicated by the symbol, if n is a number. If n is literally the symbol n, then the stack language reads the top of the stack (at runtime) to determine how many arguments to grab. For instance.

(||| 1 2 3 4 3>list) -> (2 3 4)


(||| 1 2 3 4 5 1 1 + n>list) -> (4 5)

This makes it easy to call emacs functions from the stack language without writing a lot of glue code.

The stack language supports lambda-like quotations, inspired by Factor. A quotation is just a list, constructed in any way you want, usually by direct quotation:

(||| 1 '(3 +) call) -> 4

I really love Factor's approach, so you'll find that quotations play a big role in how the stack language works. The if statement, for instance, uses quotations:

(||| 5 10 2<< '('true) '('false) if) -> 'true


(||| 5 10 2<> '('true) '('false) if) -> 'false

In other words, if expects the stack to have a condition, a true branch quotation, and a false branch quotation to be on the stack, and it calls the appropriate branch.

I've snuck in a feature here you might not have noticed: if is not an emacs lisp function. It is a stack language word. You will eventually be able to write words in emacs stack language, but for now they are defined by using emacs lisp.

(defstackword stack-plus 
  (let ((arg1 (pop *stack*))
        (arg2 (pop *stack*)))
     (push (+ arg1 arg2) *stack*)))

Note that with the current implementation, you can sort of write words in the stack language itself using the emacs macro |||- (as opposed to |||). Whereas ||| introduces a stack language form with a fresh, empty stack (and retain stack, for those who care), |||- uses the stack currently in the dynamic scope. So we could define the "push to the retain stack" word in two ways:

(defstackword >r 
   (push (pop *stack*) *retain-stack*))

(using pure emacs lisp) or:

(defstackword >r 
   (|||- '(push) swap 1>list compose '(*retain-stack*) compose
   1>eval drop))

Here we use lists and the compose operator to construct an emacs lisp phrase and pass it to eval. Not the most obvious way of doing things, but a nice example.

You can now also implement words within the stack language itself.

(||| word: plus-eleven 11 + end:)
(||| '( 22 + ) 'plus-twenty-two set-word!)
(||| 12 plus-eleven ) ;-> 23
(||| 1 plus-twenty-two) ;-> 23

When the language encounters a symbol during compilation, it first checks to see if there is a stack word associated with it, then it tries to expand it into an emacs lisp call. If it can't do either, an error is thrown. The compiler is smart enough so that you can define a stack-language word + and still use the n>+ syntax to access the emacs function. There are a few stack words defined in the code now (swap, dup, drop, etc) and some words for working with quotations (curry, compose), and some words for doing control (if, and loop). Where possible, I am going to hew pretty close to Factor's style, not Forth's.


You can use the stack to work with emacs values using stack interpolation. This can be accessed in two ways. In the first, you surround a variable name with {} to push that emacs variable value on the stack:

(let ((x 10))
  (||| {x} 25 +)) ;-> 35

In the second you use the immediate word lisp-val:, which does the same thing.

(let ((x 10))
  (||| lisp-val: x 25 +)) ;-> 35

Lisp val is an immediate word, so it is evaluated at compile time, with the future words and values making up the stack language source code on the stack. Immediate words transform the source code of the emacs stack language at run time. You can create them using defstackword-immediate.

The Fry Word

One of the things to wrap your head around when learning factor is that flat quotations serve the same role as lambda does in a non-stack based language. Since there is no scope, by default, in a stack language one creates closures by taking values on the stack in inserting them into quotations in particular ways. The curry and compose words do this in the emacs stack language (like in Factor):

(||| 4 '(2>+) curry 'plus-four set-word! 5 plus-four) ;-> 9

Since quotations are lists, curry is the same as 2>cons.

(||| '(4) '(2>+) compose 'plus-four set-word! 5 plus-four) ;-> 9

Again, its easy to see that compose is the same as 2>append. For complicated quotation construction, this can get tedious, so Factor and this language provide the fry word. fry takes a quotation, and traverses it, filling in _ and @ with objects from the stack. If a _ is encountered, then an item from the stack is inserted directly into the quotation. An @ causes the item, which must be a list, to be "spliced" into the quotation. The items are spliced in from right to left:

(||| 4 '(_ 2>+) fry) ;-> (4 2>+)
(||| '(2 2 2>+) '(@ 2>+) fry) -> (2 2 2>+ 2>+)

This makes it easier to construct closure-like quotations.


I'd like to implement functional words like map and fold.


28 May 2010: added a bunch of stack-words.

29 May 2010: added more stack words of the bi family, also created a bivalent-stack-word macro for quickly declaring stack word interfaces to emacs lisp functions which usually take two arguments

30 May 2010: added word: defining word and the fry word.

31 May 2010: added stack type checking macros for use in el, added foldl and leach words. Added an "assert-stack-predicates" word which checks the types on the stack simply and easily.

6 June 2010: added interpolation syntax and immediate word.