Code and Data

Well, if you are just working with strings, you will end up having to do a lot of parsing if you want to manipulate the "code as data". That's the advantage of using a tree representation. The classic example is probably an exercise in symbolic differentiation. Here's an example in Common Lisp, although there's nothing special here that couldn't be done in a very similar way in C++, Ruby, Haskell and I presume Smalltalk and C#.

; Simple example of symbolic differentiation 
; to show manipulation of code as data...

(defpackage "SYM-ARITH" (:use "COMMON-LISP"))
(in-package sym-arith)

;Create a regular Common Lisp function...
; f(x) = x^2 + 12x - 7
(defun f (x) (- (+ (*  x x)
                   (* 12 x))
                7))
                
;Print out the symbolic representation...
(format t "~%f(x)   = ~A~%" (f 'x))

;Print out numerical value at x = 10...
(format t "~%f(10)  = ~A~%" (f 10))

;Symbolically differentiate f(x)...
(format t "~%f'(x)  = ~A~%" (simplify (sym-diff (f 'x) 'x)))

;Value of f'(10)...
(format t "~%f'(10) = ~A~%" (funcall (fun<-sym (sym-diff (f 'x) 'x)) 10))

;Helper functions...

;redefine +,-,* to work with symbolic values...
(shadow '+)
(defmethod + ((a number) (b number))
  (cl:+ a b))
(defmethod + (a b)
  `(+ ,a ,b))

(shadow '-)
(defmethod - ((a number) (b number))
  (cl:- a b))
(defmethod - (a b)
  `(- ,a ,b))

(shadow '*)
(defmethod * ((a number) (b number))
  (cl:* a b))
(defmethod * (a b)
  `(* ,a ,b))

;Symbolically differentiate an expression...
(defun sym-diff (expr var)
  (cond ((numberp expr) 0)
        ((eq expr var)  1)
        ((symbolp expr) 0)
        ((symbolp (first expr))
            (let ((op   (first  expr))
                  (arg1 (second expr))
                  (arg2 (third  expr)))
              (ecase op 
                ((+ -) (funcall op (sym-diff arg1 var)
                                   (sym-diff arg2 var)))
                ('* (+ (* (sym-diff arg1 var) arg2)
                       (* arg1 (sym-diff arg2 var)))))))))
                                
(defun fix-point (f x)
  (let ((y (funcall f x)))
    (if (equal x y)
        x
        (fix-point f y))))

;Apply simplifications until the expression stops changing...
(defun simplify (expr)
  (fix-point #'simp expr))
  
(defun zero? (n)
  (and (numberp n) (= n 0)))
(defun one? (n)
  (and (numberp n) (= n 1)))
  
;Simplify an expression by eliminating addition of zero
; multiplication by one, etc.
(defun simp (expr)
    (cond ((numberp expr) expr)
          ((symbolp expr) expr)
          ((symbolp (first expr)) 
              (let ((arg1 (second expr))
                    (arg2 (third  expr)))
                (case (first expr)
                    ('+ (cond ((zero? arg1) (simp arg2))
                              ((zero? arg2) (simp arg1))
                              ((equal arg1 arg2) `(* 2 ,arg1))
                              (t (+ (simp arg1) (simp arg2)))))
                    ('- (cond ((zero? arg2) (simp arg1))
                              ((equal arg1 arg2) 0)
                              (t (- (simp arg1) (simp arg2)))))
                    ('* (cond ((zero? arg1) 0)
                              ((zero? arg2) 0)
                              ((one?  arg1) arg2)
                              ((one?  arg2) arg1)
                              (t (* (simp arg1) (simp arg2))))))))))
                              
;compile a symbolic expression...
(defun fun<-sym (expr)
  (cond ((numberp expr) #'(lambda (x) expr))
        ((symbolp expr) #'(lambda (x) x))
        ((symbolp (first expr))
           (let ((op (first expr))
                 (f  (fun<-sym (second expr)))
                 (g  (fun<-sym (third expr))))
             (ecase (1- (length expr))
               (2  #'(lambda (x) (funcall op (funcall f x)
                                             (funcall g x)))))))))

In general, you can tell any class which compiler to use (allowing you to easily create domain specific languages).

are there any code examples of how to do things like this?

James we'd have a string, and just evaluate that at runtime
And "evaluate that at runtime" will still mean "Compiles the sourceStream into a parse tree, then generates code into a method."
The C# example starts from an explicit representation of the parse tree instead of a string. afaict the Cincom Smalltalk equivalent would use the classes in System-Compiler-Program Objects the subclasses of ProgramNode such as BlockNode SequenceNode MessageNode ... afaict those classes correspond fairly well to the C# 3.0 classes in System.Expressions the subclasses of Expression.

James creating code whose execution is deferred until later
The point was to show a code representation that could easily be modified later (transformed by some other program).

Greg ...just working with strings...
Cincom Smalltalk does use an explicit parse tree representation - look at the subclasses of ProgramNode. (And there's another tree representation as the refactoring browser implements it's own parser.)(We need comments from someone who knows these classes.)

Comment by James Robertson

The whole parse tree is available in Smalltalk - it's just not something that Smalltalkers tend to work with (outside of tools - see the Refactoring Browser, for instance). As to examples of compiler usage, load Distributed Smalltalk and look for implementors of the class method #compilerClass

And for those who aren't familiar with Lisp, here's a (simplified) Ruby version of the symbolic differentiation program above...

#!/usr/bin/ruby -w
# Symbolic differentiation example in Ruby
#  without any mathematical simplification...

class Expr
    def initialize(a,op,b)
      @arg1 = a; @op = op; @arg2 = b
    end
    def to_s; "(#@arg1 #@op #@arg2)" end 
    def +(arg2) Expr.new(self,:+,arg2) end
    def -(arg2) Expr.new(self,:-,arg2) end
    def *(arg2) Expr.new(self,:*,arg2) end
    def sym_diff(var)
      case @op
      when :+ then @arg1.sym_diff(var) + @arg2.sym_diff(var)
      when :- then @arg1.sym_diff(var) - @arg2.sym_diff(var)
      when :* then @arg1.sym_diff(var) * @arg2 + 
                   @arg1 * @arg2.sym_diff(var)
      end
    end
    def to_proc
      f = @arg1.to_proc
      g = @arg2.to_proc
      lambda {|x| f.call(x).send(@op,g.call(x))}
    end
end

Zero = Expr.new(0,:+,0)
One  = Expr.new(1,:+,0)

class Numeric
    def sym_diff(var) Zero end
    def to_proc; lambda {|n| self} end
end

class Symbol
    def sym_diff(var) self === var ? One : Zero end
    def +(arg2) Expr.new(self,:+,arg2) end
    def -(arg2) Expr.new(self,:-,arg2) end
    def *(arg2) Expr.new(self,:*,arg2) end
    def to_proc; lambda {|n| n} end
end

# Create a regular Ruby function...
#  f(x) = x^2 + 12x - 7
f = lambda {|x| x*x + x*12 - 7}

# Print the symbolic form
puts f.call(:x)
# Print the numeric value at f(10)
puts f.call(10)
# Symbolically differentiate 
puts f.call(:x).sym_diff(:x)
# Value of f'(10)
puts f.call(:x).sym_diff(:x).to_proc.call(10)

While I'm not sure how to parse the more complicated bits of the Ruby example, I think the mechanism it's using is remarkably like the mechanism we use in Glorp to take a subset of Smalltalk blocks and convert them automatically into SQL, making something that can be used as both select: block on objects in memory, or to find objects in the database.

The trick in this case being passing in an argument that isn't actually of the type of object expected, but rather something that builds up an expression tree based on the messages sent. 

Anonymous, please could you provide a code example of building up an expression tree for

[:a | a + 1]

Comment by Alan Knight

Well, I wasn't commenting on Don Box's example, but on the Ruby code in the comment immediately preceding. I don't think either of them is doing the same thing that Don Box's example is doing, programmatically building up an expression tree which is (or at least might be) the same as what the compiler uses. You could do that, but I don't feel up to figuring out what an example would look like. It's not an operation you commonly see in Smalltalk. People are more likely to build their own expression objects, which are pretty simple, or else just compose blocks and/or message sends and evaluate them. The examples I was referring to are building up an expression tree by executing a lambda passing in a different type of object than one might naively expect. So, I can provide a short code example, but it's not likely to be very informative

[:a | a + 1] asGlorpExpression.

My example, being for an entirely different purpose, doesn't hard-code the set of messages it responds to, but passes in a does not understand handler and then extracts the information out of that. The code is not that large, but large enough I wouldn't try to paste it into a blog comment without considerably simplification. See the Glorp package, classes MessageArchiver, BaseExpression, etc. For a simpler example, I expect you could transliterate the Ruby example above. Note that I am not volunteering to do so :-)

James,

I think people have done a reasonable job explaining why a string containing raw source text isn't the same as having an expression already sliced into a structured expression tree.

I know several people allude to the fact you can do it in Smalltalk - I just wish someone would write the 7 lines and post them (my ST skills are pretty lame so I'm not sure I'm qualified).

I think Alan Knight nails it when he talks about translating expressions that are authored in the "local" programming language into some external form for remote evaluation.  SQL is the most obvious target, but you'd be surprised how many of these suckers are out there.

DB

The expression tree for "[:a | a + 1]" would be built like: 

BlockNode new
    arguments:
        (Array with:
            (ParameterNode new
                variable: (VariableNode new name: 'a')
                type: nil))
    body:
        (SequenceNode new
            temporaries: #()
            statements:
                (Array with:
                    (MessageNode new
                        receiver: (VariableNode new name: 'a')
                        selector: #+
                        arguments: (Array with: (LiteralNode new value: 1)))))

By the way, I do think the manner in which you can declare an expression in C# and basically get the compiler to leave you with a parse tree is interesting.  Most Smalltalks have a mechanism called compile time literals...this basically lets you evaluate any smalltalk code at compile time and store the resulting object as a literal in the method...the notation is ##(<code>) ...so, if you have some message that will yield a parse tree from a block of code (i.e. #asParseTree), you could embed the resulting parse tree in the compiled method as a literal.  So, I could write a method that will give me the parse tree of "[ :a | a + 1]" as follows:

 

   getParseTree

        ^##([ :a | a + 1] asParseTree) 

 

When you call #getParseTree, there is no work to do to build the parse tree...it's was built when you saved (compiled) the method #getParseTree and is stored in the compiled method as a literal. 

Thanks Stephen I arrived at the same expression tree but there seemed to be a problem with compilerHints? We do want to compile and apply the compiled block.

Don, by now you could probably do Line 1 :-)

f := [:a| a + 1].

The parse tree nodes, as they exist in the base VW image don't have a lot of supporting methods for this sort of by-hand construction...if I were doing this, I would start with the example I gave (and probably reduce it even further to get right the meat of what we are trying to do and eliminate the noise).  Then, I would extend the parse node classes with the requisite supporting methods to yield something directly compilable (if that's what you want to do with the parse tree).  OTOH, if I wanted to do something else with this parse tree (such as translate it into another language, or produce decompiled code, or emit nicely formatted byte code documentation), I would create a visitor class to accomplish that.  And this is only the default paser/compiler in VW, there are plenty of third party ones that have slightly different objectives that one might consider for this task.  In any case, it's trivial to get this to actually compile, so I'll leave it as an exercise for the reader.  ;)

James, a couple of days ago you dismissed a specific new feature of C# 3.0 as "Crawling towards Past Achievements" and getting "up to Lisp and Smalltalk levels of technology, only a few decades late".

Now it seems that you've shone a light on something which has no API support in Cincom Smalltalk.

I don't think it's a huge problem that Cincom Smalltalk doesn't come out of the box with this functionality. But I don't think it looks good to blandly dismiss something as old stuff when we would need to roll-our-own implementation.

Comment by James Robertson

I rather expect that there won't be a lot of usage of that either.

What are you talking about?

Comment by James Robertson

What I meant to say, but didn't: Given the complexity of the C# example, it might as well not exist. I rather suspect that a simpler Smalltalk example could be rolled out by someone familiar with the field in a very short period of time - but it's not something Smalltalk was designed for. If you have those needs, Scheme or Lisp are probably better bets.

James Given the complexity of the C# example

Expression[Func[int, int]] e = a => a + 1;

What's so complex about that?

James it might as well not exist
On the contrary, instead of triggering a doesNotUnderstand exception and pillaging, it provides a direct way to get an expression tree.

James it's not something Smalltalk was designed for
True, but a little difficult to reconcile with earlier statements In any case, that shows some of the more dynamic features of Smalltalk. IMHO, they are far less baroque than what C# is adding, because Smalltalk was created with this kind of thing in mind. C# wasn't, and it shows.
(Patrick Logan also initially misunderstood the example but then gracefully acknowledged his mistake.)

Isaac, it is you that could learn a thing or two about "truth in adversting"...to say that there is "no API support in Cincom Smalltalk" for by-hand construction of parse trees is blatantly false.  There is a rich API for creating and manipulating parse trees in Cincom Smalltalk.  I was simply alluding to the fact that *I* would probably enrich the protocols in the base VW if I were going to do a lot of this by-hand manipulation of parse trees.  Why?  Because I would want my code that manipulates the parse trees to be as intention revealing as possible.  The fact that a few helper methods don't exist doesn't constitute "no API support"...if anything, it's exactly the opposite, there is rich API support.

blatantly false
Where's asParseTree implemented?

"The fact that a few helper methods don't exist doesn't constitute "no API support"...if anything, it's exactly the opposite, there is rich API support."
The fact that a few helper methods don't exist (aka API support) means that we each roll-our-own solutions - we each create our own application specific API.

Comment by James Robertson

So, the fact that the specific UI I want for my new application doesn't exist means that there's no API support then? Since I need to create an application specific API for having the UI and the domain communicate (for all but the most trivial kinds of applications) each time out?

By your reasoning Isaac, the term API has no real meaning at all.

So, the fact that the specific UI I want for my new application doesn't exist means that there's no API support then?
Non sequitur.

Since I need to create an application specific API for having the UI and the domain communicate (for all but the most trivial kinds of applications) each time out?
No we don't need to create an application specific API - we use the trigger-event API. Without defined helper methods for registering events and triggering events and removing events, we would each roll-our-own API on top of the base functionality.

Isaac, what you describe would be an issue if we were talking about some other languages, but it simply isn't an issue in Smalltalk...it's common, natural and easy to extend base classes in Smalltalk...in fact, it's essential to good factoring.  Yes, you might end up with multiple implementations of a method to build a parse tree, but who cares?  You are making an issue of something that simply isn't an issue.

Stephen, I've already said that "I don't think it's a huge problem that Cincom Smalltalk doesn't come out of the box with this functionality."

I think it's a problem when we attack a specific new feature in some other language as old stuff and then it turns out that we would have to roll-our-own implementation - it looks bad.

As Don Box said "I know several people allude to the fact you can do it in Smalltalk - I just wish someone would write the 7 lines and post them"