Re: LISPPA
From: Gareth McCaughan (gareth.mccaughan_at_pobox.com)
Date: 04/20/04
- Next message: Barry Margolin: "Re: New implementation: Emacs Common Lisp"
- Previous message: RobertMaas_at_YahooGroups.Com: "Re: I'm not the only one who values interval-arithmetic"
- In reply to: Alexander Baranovsky: "Re: LISPPA"
- Next in thread: Alexander Baranovsky: "Re: LISPPA"
- Reply: Alexander Baranovsky: "Re: LISPPA"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 20 Apr 2004 02:46:29 +0100
Alexander Baranovsky wrote:
> First of all, thank you for your answer as it turns the discussion
> into serious direction, at least.
You're welcome.
> > I'm sure it's very nice, but the only thing it has in common
> > with Lisp is (1) the first four letters of its name and
> > (2) the fact that it provides a way of working with sequences
> > of arbitrary objects in a programming language. So I'm not
> > sure why you've posted it to comp.lang.lisp.
>
> (1) Both Lisp and LISPPA have relation to the list processing. LISPPA
> uses a "classic" data structure in the imperative programming, namely
> the array, for the representation of linked lists. Both directions try
> to "reconcile" the functional and imperative approaches of the
> programming: Pure functional Lisp introduces "imperative" concepts via
> side effects, LISPPA tries to provide uniform and concise data
> representation and algorithmes for the recursive data structures what
> is peculiar to the functional approach. It explains the name.
I'm puzzled by the statement that "Pure functional Lisp
introduces imperative concepts via side effects"; once
there are side effects the language isn't "pure functional",
so I suppose what you mean is that Lisp starts with a
"pure functional" core and adds imperative side-effect-ful
bits on. But Lisp hasn't been "pure functional" for a
long, long, long time, and Lisp as it is now is certainly
*not* accurately described as a functional language with
imperative extensions. (You could probably describe O'Caml,
for instance, that way.)
In short: Lisp is not a functional language with some
imperative bits; it is a multi-paradigm language that
supports both functional and imperative styles of
programming.
> (2) I hoped that the comparison of both approaches can be interesting.
OK.
> > so perhaps the answer is that you think your LISPPA thing
> > is going to make Lisp obsolete by providing ways to solve
> > the problems Lisp is good at, while remaining palatable to
> > the "majority of programmers".
>
> No, I did not think that. However, I suppose that mentioned imperative
> languages are more claimed at present time. You cannot avoid to see
> it. At the same time, they have many drawbacks. I have tried to remove
> one such defect.
I think the defect you've tried to remove isn't anything to do
with the functional/imperative distinction. There's no reason
at all why a functional language has to have lists[1] of arbitrary-typed
elements (Haskell doesn't) and no reason at all why a language with
lists of arbitrary-typed elements has to be functional (Python isn't).
Now, obviously you know this, since your languages are themselves
non-functional languages with lists of arbitrary-typed elements, but
you do seem to be suggesting that somehow your languages with LISPPA
are nearer to being "functional" than they would be without. I don't
think they are. The two issues are completely separate.
[1] Or vectors, or whatever.
> > But there are already languages that do what your LISPPA
> > does. Have a look at Python, for instance; it has "polymorphic
> > arrays"
>
> This is the second mention about Python (the first I've received in a
> private email). Not only Python uses polymorphic arrays. JavaScript,
> PHP and many other languages use it. In particular, there are a lot
> languages which support Variant types and COM technology.
Right: tons of them. I mentioned Python rather than the others
because I think it's the nicest language of its kind, and if you're
only going to look at one of them then Python is a good choice.
Of course, opinions on this matter vary :-).
> I never
> stated that the polymorphic array is a new concept. But, it seems, the
> using arrays for the representation and processing of linked lists is
> quite new idea.
Take a look at Peter Norvig's "Python for Lisp programmers"
page at http://www.norvig.com/python-lisp.html ; he mentions
an implementation of linked lists using Python tuples in his
feature-comparison table. That's quite recent too, of course.
Mostly, it hasn't been done because if you want linked lists
then using a general-purpose polymorphic array type to build
them is inefficient. At least, it usually is; perhaps your
languages have a special implementation of polymorphic arrays
that makes small p.a.'s particularly space-efficient.
> Indeed, in terms of the arrays we can give the simple
> recursive definition of lists and binary trees. For example:
>
> 1. NULL (undefined variable) is empty list.
> 2. If L is a list, the one-dimensional array A with two elements A(0)
> and A(1) = L is a list too.
>
> We cannot produce such concise definition of the linked list using
> standard approach based on pointers. This is the start point, further
> LISPPA offers a uniform ways to process lists and other dynamic data
> structures.
I don't see why we can't produce a similarly concise definition
using pointers.
1 The null pointer represents the empty list.
2 If L is a list and X any object, then a block
of memory containing two pointers, one of which
points to X and the other of which points to L,
is a list.
By the way, let me advise you not to use the same thing to mean
both "undefined variable" and "empty list".
> Please note, that the presence of polymorphic arrays in an imperative
> programming language not yet provides
> effective programming. A few extra conditions are required. LISPPA
> uncovers a minimal set of such conditions. (In this relation, you can
> take a look at the discussion about LISPPA in comp.lang.php).
I don't know much about PHP. Isn't it rather similar to Perl?
Because Perl has somewhat adequate polymorphic arrays. (You have
to take references everywhere, otherwise horrible splicing things
happen when you put a list inside another list, but that's all.)
> > And yet, despite the existence of Python, Lisp
> > programmers don't seem to have given up. Why might that be?
> > Answer: the advantages of Lisp are *not* all about the "data
> > domains" it can handle, but about the facilities it provides
> > for writing powerful software efficiently and concisely.
>
> I think the real advantages of LISPPA can be discovered after its
> implementation in a compiler such as Visual Basic or Delphi. (It is
> quite easy to extend well known Variant types to take into
> consideration LISPPA requirements). Benefits of it are obvious, I
> hope.
>
> > LISPPA, so far as I can see, offers none of this.
>
> Sorry, I cannot agree with it. See, for example:
>
> http://www.virtlabs.com.ua/paxscript/demo_basic_lists.htm
> http://www.virtlabs.com.ua/paxscript/demo_basic_trees.htm
>
> http://www.virtlabs.com.ua/paxscript/demo_pascal_lists.htm
> http://www.virtlabs.com.ua/paxscript/demo_pascal_trees.htm
>
> http://www.virtlabs.com.ua/paxscript/demo_c_lists.htm
> http://www.virtlabs.com.ua/paxscript/demo_c_trees.htm
>
> http://www.virtlabs.com.ua/paxscript/demo_js_lists.htm
> http://www.virtlabs.com.ua/paxscript/demo_js_trees.htm
>
> > Random example: your symbolid differentiation program has
> > a function called "InOrder" that produces an infix
> > representation of an expression. It's 30 lines long.
> > In Lisp it would say [danger: untested code!] ............
>
> The function is written bad, I can accept it.
The point is: I'm not sure it *is* written badly. (I mentioned
one little bug, but good code can have bugs.) I think the reason
why the Lisp code is so much shorter (and, to my mind, neater)
is simply that Lisp is a better language than Pascal, even when
you add a handy new variant type to Pascal and provide some
features for building arrays of variants. Certainly adding
variants and nicer arrays is an improvement to Pascal, but
the deficiencies of Pascal in comparison to Lisp go so much
deeper than that.
> But it is not a typical
> example. I think more interesting example is Compress procedure which
> allows you to compress a sub-tree of a tree without having to relocate
> the whole tree in each act of the compression. The body of the
> procedure is not short, but quite uniform and clear for understanding.
> I do not think that you will use less number of lines to express the
> same in Lisp.
Oh, really? :-) [Warning: very untested code ahead.]
(defun build-matcher (pattern x escape-tag already-seen body)
(cond
((null pattern)
(values `(if ,x (go ,escape-tag) (progn . ,body)) already-seen))
((symbolp pattern)
(if (member pattern already-seen)
(values `(if (equal ,x ,pattern) (progn . ,body) (go ,escape-tag)) already-seen)
(values `(let ((,pattern ,x)) . ,body) (cons pattern already-seen))))
((or (atom pattern) (eq (first pattern) 'quote))
(values `(if (equal ,pattern ,x) (progn . ,body) (go ,escape-tag))
already-seen))
(t
(let ((x-sym (gensym)) (body-sym (gensym)))
(multiple-value-bind (car-matcher already-seen)
(build-matcher (car pattern) `(car ,x-sym)
escape-tag already-seen body-sym)
(multiple-value-bind (cdr-matcher already-seen)
(build-matcher (cdr pattern) `(cdr ,x-sym)
escape-tag already-seen body)
(values `(let ((,x-sym ,x))
(unless (consp ,x-sym) (go ,escape-tag))
,(subst (list cdr-matcher) body-sym car-matcher))
already-seen)))))))
(defmacro matching-bind (pattern x escape-tag &body body)
(build-matcher pattern x escape-tag nil body))
(defmacro match-case (x &rest clauses)
(let ((x-sym (gensym)) (escape-tag (gensym)) (block-name (gensym)))
`(let ((,x-sym ,x))
(block ,block-name
,@(loop for (pattern . body) in clauses collect
`(macrolet ((next-case () (go ,escape-tag)))
(tagbody
(return-from ,block-name
(matching-bind ,pattern ,x-sym ,escape-tag . ,body))
,escape-tag)))))))
(defun compress (expr)
(if (atom expr)
expr
(setf expr (mapcar #'compress expr))
(match-case expr
(('- x)
(if (is-constant x) (- x) expr))
(('+ x 0) x)
(('+ 0 x) x)
(('+ x x) `(* 2 x))
(('+ x ('- y)) `(- ,x ,y))
(('+ ('- x) y) `(- ,y ,x))
(('+ ('* a b) ('* a d)) `(* ,a (+ ,b ,d)))
(('+ ('* a b) ('* c b)) `(* (+ ,a ,c) ,b))
(('+ ('* a b) a) `(* ,a (+ ,b 1)))
(('+ ('* b a) a) `(* ,a (+ ,b 1)))
(('+ ('+ a b) c)
(if (is-constant c)
(cond ((is-constant a) `(+ b ,(+ a c)))
((is-constant b) `(+ a ,(+ b c)))
(t (next-case)))
(next-case)))
(('+ a ('+ b c))
(if (is-constant a)
(cond ((is-constant b) `(+ c ,(+ a b)))
((is-constant c) `(+ b ,(+ a c)))
(t (next-case)))
(next-case)))
(('+ ('- a b) c)
(if (is-constant c)
(cond ((is-constant a) `(- ,(+ a c) b))
((is-constant b) `(+ a ,(- c b)))
(t (next-case)))
(next-case)))
(('+ a ('- b c))
(if (is-constant a)
(cond ((is-constant b) `(- ,(+ a b) c))
((is-constant c) `(+ b ,(- a c)))
(t (next-case)))
(next-case)))
(('+ x y)
(if (and (is-constant x) (is-constant y)) (+ x y) `(+ x y)))
;; ... another 35 lines for - ...
(('* x 0) 0)
(('* 0 x) 0)
(('* x 1) x)
(('* 1 x) x)
(('* ('- x) y) `(* -1 (* ,x ,y)))
(('* x ('- y)) `(* -1 (* ,x ,y)))
(('* x x) `(expt ,x 2))
(('* ('expt x a) ('expt x b)) `(expt ,x (+ ,a ,b)))
(('* x (expt x a)) `(expt ,x (+ ,a 1)))
(('* (expt x a) x) `(expt ,x (+ ,a 1)))
(('* ('* x y) ('expt x a)) `(* ,y (expt ,x (+ ,a 1))))
(('* ('* y x) ('expt x a)) `(* ,y (expt ,x (+ ,a 1))))
(('* ('* (expt x a) y) ('expt x b)) `(* ,y (expt ,x (+ ,a ,b))))
(('* ('* y (expt x a)) ('expt x b)) `(* ,y (expt ,x (+ ,a ,b))))
(('* ('expt x a) ('* x y)) `(* ,y (expt ,x (+ ,a 1))))
(('* ('expt x a) ('* y x)) `(* ,y (expt ,x (+ ,a 1))))
(('* ('expt x b) ('* (expt x a) y)) `(* ,y (expt ,x (+ ,a ,b))))
(('* ('expt x b) ('* y (expt x a))) `(* ,y (expt ,x (+ ,a ,b))))
(('* ('* x y) x) `(* ,y (expt ,x 2)))
(('* ('* y x) x) `(* ,y (expt ,x 2)))
(('* ('* ('expt x a) y) x) `(* ,y (expt ,x (+ ,a 1))))
(('* ('* y ('expt x a)) x) `(* ,y (expt ,x (+ ,a 1))))
(('* x ('* ('expt x a) y)) `(* ,y (expt ,x (+ ,a 1))))
(('* x ('* y ('expt x a))) `(* ,y (expt ,x (+ ,a 1))))
(('/ x 1) x)
(('/ 0 x) 0)
(('/ x ('expt y a)) `(* ,x (expt ,y (- ,a))))
(('/ x 0) (error "Division by zero"))
(('/ x y) `(* ,x (expt ,y -1)))
(('expt x 1) x)
(('expt x 0) 1)
(x x))))
This will produce code a little less efficient than your Pascal, because
it doesn't take advantage of the opportunities for merging the initial
bits of the matching clauses. It's about 55% of the length of your
Pascal code (and yes, I am including the 35 lines I didn't bother to
write), and the ratio will only become more favourable as the number
of simplifications increases. (I'm not sure what the rationale
is for the particular set you've chosen.) And I think it's much easier
to read.
(Actually, the ratio is more favourable to Lisp than the above
suggests, because I haven't included the code for your functions
IsMult, IsPow, and so on, which aren't needed in the Lisp version.
I have used something called IS-CONSTANT, which I haven't defined,
but you could substitute NUMBERP and it would work fine.)
If the efficiency loss matters, it isn't too hard to write a much
smarter MATCH-CASE macro. That might add another 50-100 lines,
bringing the Lisp code to almost the same length as the Pascal --
but still much easier to read and much more concisely extensible.
Oh, and you can use MATCH-CASE for the differentiation too:
(defun differentiate (expr)
(match-case expr
('x 1)
(('- x) `(- ,(differentiate x)))
(('+ x y) `(+ ,(differentiate x) ,(differentiate y)))
(('- x y) `(- ,(differentiate x) ,(differentiate y)))
(('* x y) `(+ (* ,x ,(differentiate y)) (* ,y ,(differentiate x))))
(('/ x y) `(/ (- (* ,y ,(differentiate x)) (* ,x ,(differentiate y)))
(expt ,y 2)))
(('log x) `(/ ,(differentiate x) ,x))
(('pow x a) `(* (+ (* (differentiate ,a) (log ,x))
(* ,a (/ (differentiate ,x) ,x)))
(expt ,x ,a)))
((x . y) (error "Syntax error"))
(x 0)))
> Besides you might take a look at the source code of the theoprem
> proving program in paxBasic
...
> or in paxPascal
...
> and compare this code with source code presented in book Chang C.L and
> Lee R.C. "Symbolic Logic and Mechanical Theorem Proving". Then you can
> conclude what of codes is more suitable for understanding.
I don't have that book; sorry.
> Finally, the ancients spoke: "If two man do the same thing, it already
> is not same thing". I think that alternative approaches are always
> useful for the consideration. Not?
Perhaps. And it may be that your languages with "LISPPA technology"
are useful to people who are (for whatever reason) unable to program
in Lisp or in other languages with polymorphic arrays such as Python.
But here in comp.lang.lisp, that's not your audience :-).
-- Gareth McCaughan .sig under construc
- Next message: Barry Margolin: "Re: New implementation: Emacs Common Lisp"
- Previous message: RobertMaas_at_YahooGroups.Com: "Re: I'm not the only one who values interval-arithmetic"
- In reply to: Alexander Baranovsky: "Re: LISPPA"
- Next in thread: Alexander Baranovsky: "Re: LISPPA"
- Reply: Alexander Baranovsky: "Re: LISPPA"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
