Monday, January 31, 2005

lab 27 - sh sexpr


lab 27 - sh sexpr


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 
          (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)


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.

Monday, January 10, 2005

lab 26 - greenspun's rule


lab 26 - greenspun's rule


Let me state up front, I do not know much about lisp. I've always been aware of it but never saw it's benefits so never used it. However, recently I've begun to read more about it, particularly the essays by Paul Graham, and his book On Lisp (which I'm still reading, on and off). I went a bit further and read Steele and Sussman's paper The Art of the Interpreter. Also, as a symptom of my Mathematica envy I became curious about symbolic programming languages, computer algebra systems, and how these are based on lisp dialects. I started playing with Maxima and yacas and also Mockmma

And so I think I finally got what lisp was about. (I still have much more reading to do. It's funny how a large and rich subculture within computer science suddenly opens up to you when you read about its core language. I have to ask myself, How could I not have noticed this for so long? The same surprise occurred to me when reading about smalltalk. It all makes me feel quite stupid and parochial.)

As an exercise in understanding lisp better I turned Inferno shell into a lisp dialect. I wrote a builtin module that provides an eval command and the seven primitive operators: quote, atom, car, cdr, eq, cons and cond.

I followed approximately the code in Paul Graham's paper The Roots of Lisp, and the interpreters described in the Steele and Sussman paper.

     % load ./lisp0.dis
     % eval {atom `a}
     % eval {atom `{a b c}}
     % eval {car `{a b c}}

Functions can be defined by assigning to a variable in shell. Scope within eval is dynamic.

     % 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}

The backquote is used as an abbreviation for the quote primitive.

In the builtin I hijack the parse tree and read or transform it for each primitive operator. I also use the shell Context as my symbol table for function parameters, definitions and variable values.


The attached file is the first of a few versions I'll provide as I add more features as described in Steele and Sussman, in particular lexical binding.

I wonder whether there is more value to having a dialect of lisp within the shell or whether a proper lisp implementation like scheme should be linked into the inferno VM or written in limbo. The shell already has a good interface to the whole system and mixing programming paradigms may have advantages. The problem is we may realize Greenspun's rule by being ad hoc, informally specified, bug ridden and slow.



Tuesday, January 04, 2005

lab 25 - accumulator generator


lab 25 - Accumulator Generator


The problem by Paul Graham is stated here and I quote

Write a function foo that takes a number n and returns a function that takes a number i, and returns n incremented by i.

I thought I'd attempt it in sh (I'm already assuming it's not possible in limbo). Here's my first attempt, which is wrong.

     % subfn foo {
      result={i:=$1; n=`{fc $n $i +}; echo $n}
     % n := 0
     % x=${foo 3}
     % $x 1

The problem is we can't create another accumulator generator in the same scope, since it will overwrite the variable n. Sh uses dynamic variable binding instead of lexical binding, as used by lisp.

The shell paper /doc/ mentions the issue and proposes a workaround but it doesn't really solve the stated problem. Here's a solution that incorporates the workaround.

     % subfn foo {
      x:= '{i:=$1; $'$n'=`{fc $$'$n' $i +}; echo $$'$n'}'
      result = ${parse $"x}
     % n := 1
     % x=${foo n}
     % $x 1

Now we're passing the name of a variable rather than the number. We can now create a number of accumulator generators. However, the syntax is ugly, and it's not something we'd want to code often. This seems a pity.


The problem is intended to emphasize the features of LISP, and in particular lexical binding and higher order functions. Indirectly it illustrates Greenspun's Rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally specified, bug-ridden, slow implementation of half of common lisp.

Put another way, the limit case for implementing the accumulator generator in sh is to turn it into a lisp dialect by, say, writing a shell builtin to evaluate a lisp type expression, or add lexical binding to the shell. It's interesting to note, from reading about lisp recently, that lisp used dynamic binding until the introduction of scheme during the 1970s, and all dialects of lisp eventually adopted it.