Re: LISPPA

From: Thomas Schilling (tjs_ng_at_yahoo.de)
Date: 05/09/04 

Date: Sun, 09 May 2004 15:40:45 +0200

Alexander Baranovsky wrote:
> http://www.cs.bham.ac.uk/research/poplog/paradigms_lectures/lecture20.html#unification
>
> which describes the unification algorithm in Scheme. I guess that
> Peter Norvig's book presents the same idea of unification.

> 1. I do not use the binding list. The bindings are expressed by means
> of aliases in my approach. Ok, I use extra structure which contains
> parameters of term, but this approach provides the linear algorithm of
> renaming variables.
> 2. I do not use search in the binding list.
> 3. I use one function Unify instead of two functions: unify and
> unify-variable.
> 4. I do not use the mutual recursion (of unify and unify-variable) in
> my algorithm, so it is much more easy to get a non-recursive version
> of the algorithm.
> 5. My algorithm is more concise and easy for understanding.

Here's the version from Norvig's compiler:

(defstruct var name (binding unbound))
;; in pascal this is like:
;; type
;; Var = record
;; name: ?;
;; binding: ^var; (* default value = unbound *)
;; end;

(defun bound-p (var) (not (eq (var-binding var) unbound)))
;; (var-binding var) would be var.binding

(defmacro deref (exp)
   "Follow pointers for bound variables."
   `(progn (loop while (and (var-p ,exp) (bound-p ,exp))
              do (setf ,exp (var-binding ,exp)))
           ,exp))
;; this is a macro, although in this case you can
;; remove all the "`" and "," and consider it as a function
;; being inlined in the actual code

(defun unify! (x y)
   "Destructively unify two expressions"
   (cond ((eql (deref x) (deref y)) t)
         ((var-p x) (set-binding! x y))
         ((var-p y) (set-binding! y x))
         ((and (consp x) (consp y))
          (and (unify! (first x) (first y))
               (unify! (rest x) (rest y))))
         (t nil)))

(defun set-binding! (var value)
   "Set var's binding to value. Always succeeds (returns t)."
   (setf (var-binding var) value)
   t)
;; (setf (var-binding var) value) means var.binding := value;

So, now concerning your remarks:
1) thesame (see the macro)
2) thesame
3) thesame
4) thesame. also: recursion must not be bad
5) well, that's a matter of taste (and getting used to).
    I tried to rewrite these functions into pascal style and I really
prefered the way it stands here ... all these "begin"s and "end"s and
"if"+"then". It also took a while for me to get used to the parentheses
but now i don't really see them anymore. Instead it looks to me like
cleaned-up pseudo-code

But let's get back to why I (just like many here) think lisp is superior
to pascal/basic/c/.. even with your LISSPA extension (no special order):

a) Lisp has first-class functions with closures. A nice example is:

(defun is (val)
   "returns a function that returns true if it's parameter is equal to x"
   #'(lambda (x) (eq val x))

You can then easily pass this function to a generalized search function as
the parameter for search termination. (BTW: it's also from Norvig's book.)
This is a feature that the languages you seem to prefer don't have. Well,
of course, you might not miss them if you've never used them. But that's
normal. I think if you once start using them you'll see the difference.
(Ok, you can probably live without them - but that's not the point. The
point is whether they can ease your life, and they definitely do that.)

b) macros:

I already told you that they're great. you can really create your own
special domain language without much effort. Especially they avoid very
much pure typing work (which is error-prone). Other nice cases are code
optimization macros (macros that optimize special code patterns) or reader
macros (allthough they're quite different kind of macros - actually
they're hooks into the read-function to allow special custom syntaxes.)
Again I'll give you an example:

(with-html-output (file)
   (:html
     (:body (:bgcolor "blue")
       (:p "some example paragraph")
       (:table
         (doimes (i 5)
           (htm (:tr (:td (print i)) (:td (print (* i i))))))))))))

This will print the following into the specified file:
"<html><body bgcolor="blue"><p>Some example paragraph</p>
<table>
<tr><td>0</td><td>0</td></tr>
<tr><td>1</td><td>1</td></tr>
<tr><td>2</td><td>4</td></tr>
<tr><td>3</td><td>9</td></tr>
<tr><td>4</td><td>16</td></tr>
</table></body></html>"

So this is a nice example of a sub-language and a "code-compression"-macro
because you could, of course, have written it out as a bunch of print or
format statements (oops, I mean expression, since lisp doesn't have
statements ;-). BTW: this macro is really quite simple in it's
implementation. Edi Weitz has written something like this, see
http://www.weitz.de/cl-who/.

The power of lisp macros is directly related to lisp's syntax (code =
data, i.e. code=syntax tree). There are extensions to other languages, but
they're much less powerful and full of special cases. Nervertheless,
writing good macros is an art of it's own, although definitely worth
learning ;-).

c) You can change a running program. This is especially useful for
long-running programs like servers or applications in, say, bioinformatics.
    If you encounter a bug your program get's interrupted. Now you can spot
the error, redefine the buggy function and try to continue the program. If
it still won't work you can continue debugging. Of course a server won't
response at the time you're debugging it, but OTOH no information is lost
and a shutdown+restart would probably be more annoying. (There are still
cases where a running program cannot continue running, but most chances
for hard-crashes are removed, especially pointer errors.)

d) REPL or Incremental Compilation.
    This is the Run-Eval-Print-Loop. You probably already heard about it.
It's quite comparable to d). You can modify your running program by
replacing functions, but you can also _extend_ your (running) program.
Well, normally your program doesn't run all the time, but in general you
only add your new functions instead of recompiling all you functions (the
CBRL - Compile-Build-Run-Loop ;-).
    This is one way to use the REPL, the other way is to first test your
newly written function and then add it to your running program. This is
the main way of programming in lisp (I think, at least it's mine).
    Many languages and IDEs tend towards this style of development. So this
is no longer purely a lisp feature but IMO lisp still does it best. (I
recently read an article about jython--java-compiling python--, which has
a REPL, but the basic message of the article was that you can use this to
easily test new functions instead of using it as your development style.
Well, ok, at least they see half of the benefit ;-)

e..?) There are still many other features that are really nice but I found
these to be most convincing. Other good features are it's nice (superior?)
object system (CLOS), powerful error handling, many built-in data-types
and functions, garbage collection, etc. etc.

All these features enable you to write your programs more effectively (by
means of develoment time) - bringing back the fun in programming. At least
it worked for me :-)

Maybe that helps you understanding why many here cannot understand that
you think pascal/c/basic would be comparable to lisp with your
LISPPA-extension.

Perhaps you have other arguments.
Perhaps you try out lisp ;-)

regards

Thomas

Relevant Pages

  • Re: New book about Common Lisp: Let Over Lambda
    ... I have read every lisp book I've been able to get my hands on ... Lisp macros are not given nearly enough ... I personally consider Let Over Lambda to be an unofficial sequel ... integral parts of the language. ...
    (comp.lang.lisp)
  • Re: Macro functionality at runtime?
    ... we don't know what the subtree is yet. ... "Returns a list of tokens matched to subtree. ... > be optimized out by the lisp compiler. ... >> If we have first class macros, ...
    (comp.lang.lisp)
  • Re: What is the main advantage of macros over functions?
    ... if one is allergic to reading Lambda one may better not use ... Lisp authors, doesn't help you much, I'd say. ... >> Readmacros are a completely different mechanism. ... Macros and Readmacros ...
    (comp.lang.lisp)
  • Re: Python syntax in Lisp and Scheme
    ... Alex Martelli wrote: ... > I never used Common Lisp in production: in the period of my life when I ... > did not happen to use it in TI), with some of the divergence hinging on ... > locally developed sets of macros. ...
    (comp.lang.lisp)
  • Re: A "killer" macro
    ... but then Ruby is dog slow anyway: ... Having notational convenience via macros plus efficiency is a big win ... From my perspective as a Ruby programmer learning Lisp, ... thought of having a more powerful language *and* orderof magnitude ...
    (comp.lang.lisp)