lab 27 - sh sexpr

NAME

lab 27 - sh sexpr

DESCRIPTION

The implementation of the lisp dialect in lab 26 had some problems. For each car or cdr operator I recursively descended the syntax tree rather than holding the lists in memory in a more convenient fomat and simply taking the head or tail of the list.

I did not want to build further on this implementation. Instead I wanted to rewrite eval to use the sexprs(2) module and convert the sh's syntax tree to an s-expression.

Converting from the syntax tree to an s-expression is pretty easy to do, though it took me a while to remember the method. The first file lisp1.b is a brute force implementation, which of course once I got working I remembered the method I should of used.

          % load ./lisp1
          % eval {a {b} c}
          (a (b) c)
          % unload ./lisp1

The second file lisp2.b maintains a global stack of lists of sexprs. As it recursively descends the syntax tree it pushes expressions onto the list at the top of the stack. If it descends into a new block, it pushes a new list.

Next lisp3.b handles all the syntax tree's node types. The result is an sexpr which preserves all information from the shell's abstract syntax tree.

          % load ./lisp3
          % eval {echo `{a b c} &}
          ((Nowait echo (Quote (a b c))))
          % eval { echo "{ (a (nested (list)))}}
          (echo (SquashQuote ((List a (List nested (List list))))))
          % eval {a 
          sequence
          of
          cmds}
          (Seq (a) (Seq (sequence) (Seq (of) (cmds))))
          % unload ./lisp3

The sequences should really be flattened to (Seq (a) (sequence) (of) (cmds)) But since I wanted to treat newlines not as sequences of commands but as lists I didn't bother.

The point here is that we represent the sh's abstract syntax tree as a symbolic expression ready for manipulation and evaluation. A new symbolic expression could be composed and converted back to the sh's AST for evaluation by the shell. The above builtin should not really be called eval since I am not evaluating the expression. I am just converting from input form into s-expression form.

In lisp4.b I implemented the special forms, cons, car,cdr, and atom, which are all trivial to implement given the sexpr data structure. I also added a builtin FullForm to print an shell expression converted to an s-expression, and eval now evaluates the expression using lisp semantics.

          % load ./lisp4.dis
          % FullForm { a b c {d} e {{f}}}
          (a b c (d) e ((f)))
          % FullForm {echo (a b c) `{cat t1}}
          (echo (List a b c) (quote (cat t1)))
          % eval {cdr `{a b c}}
          (b c)

In lisp5.b I added the define and lambda expressions bringing me back to the point I was at in lab 26. I have followed the evolution of eval described in the Sussman and Steele paper, The Art of the Interpreter. The environment for the eval builtin is stored as an sexpr and no longer uses the shell's Context.

The scope in lisp5.b is dynamic. The next step was to add lexical scope as is done in lisp6.b

          % eval {define {subst x y z} 
           {cond {{atom z} 
               {cond {{eq z y} x} 
                 {`t z}}}
            {`t {cons {subst x y {car z}}
                   {subst x y {cdr z}}}}}}
          % eval {subst `m `b `{a b { a b c} d} }
          (a m (a m c) d)

FUTURE

There are several steps to take including adding side effects, macros, and a method for calling builtins. Only side effects are still needed to implement the accumulator generator and some handling for math expressions.

This is still just for experimentation. It may be valuable in the long run to implement a real scheme compiler for dis.

Part of the experimentation is to try multiple evaluators, one of them is a lisp dialect, another is sh. I should try transforming the s-expression back to the sh syntax tree for evaluation or display to the user.

The principle being that I can take a parse tree, transform to FullForm (s-expressions), evaluate using a chosen evaluator, then transfrom to another parse tree for display. (I am not going to start using XML/XSL in these labs.)

I can experiment with a variety of input forms: man(6) macros, popi input form, Mathematica syntax. I can treat the s-expression as the standard form for all expressions within inferno and establish a standard semantics for this form.

The are other possible eval semantics I should look at: Transform by applying rules until the expression reaches a fixed point (as in Mathematica); All unbound variable names and functions to remain as symbols (as in other Computer Algebra Systems like Maxima).Seeessaysby Fateman on different symbolic evaluators.

Long term, I want a powerful, expressive, succinct language that can be embedded within a narrative and edited, and evaluated within the document by the editor (acme). If I can plug new languages into the inferno shell it may make a good vehicle for a range of expressive languages that could be included within an active essay.