ballpointpenthief <·················@yahoo.co.uk> writes:
> Hello,
> Pick the bones out of this please - hardly elegant and readable I
> know! > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> language.
>
> Be as harsh as you like.
OK, here's the code, reformatted using Emacs.
===================
(defstruct binary-tree-node
(value)
(left)
(right))
(defun remove-leftmost (tree)
(cond ((null tree) nil)
((null (binary-tree-node-left tree))
(values tree))
((null (binary-tree-node-left
(binary-tree-node-left tree)))
(let* ((temp (binary-tree-node-left
(binary-tree-node-left tree))))
(setf (binary-tree-node-left
(binary-tree-node-left tree)) nil)
(values temp)))
(t (remove-leftmost (binary-tree-node-left tree)))))
(defun remove-rightmost (tree)
(cond ((null tree) nil)
((null (binary-tree-node-right tree))
(values tree))
((null (binary-tree-node-right
(binary-tree-node-right tree)))
(let* ((temp (binary-tree-node-right
(binary-tree-node-right tree))))
(setf (binary-tree-node-right
(binary-tree-node-right tree)) nil)
(values temp)))
(t (remove-rightmost (binary-tree-node-right tree))
nil)))
(defun remove-node (value tree)
(cond ((null tree) nil)
((string< value (binary-tree-node-value tree))
(cond ((null (binary-tree-node-left tree)) nil)
(t
(cond ((string= value (binary-tree-node-value
(binary-tree-node-left tree)))
(cond ((null (binary-tree-node-left
(binary-tree-node-left tree)))
(setf (binary-tree-node-left
tree)
(binary-tree-node-right
(binary-tree-node-left tree))))
((null (binary-tree-node-right
(binary-tree-node-left tree)))
(setf (binary-tree-node-left tree)
(binary-tree-node-left
(binary-tree-node-left tree))))
(t ((let* ((moved-node
(remove-rightmost tree)))
(setf (binary-tree-node-left moved-node)
(binary-tree-node-left
(binary-tree-node-left tree)))
(setf (binary-tree-node-right moved-node)
(binary-tree-node-right
(binary-tree-node-left tree)))
(setf (binary-tree-node-left tree) moved-node))))))
(t (remove-node value (binary-tree-node-left tree)))))))
((string> value (binary-tree-node-value tree))
(cond ((null (binary-tree-node-right tree)) nil)
(t
(cond ((string= value (binary-tree-node-value
(binary-tree-node-right tree)))
(cond ((null (binary-tree-node-left
(binary-tree-node-right tree)))
(setf (binary-tree-node-right tree)
(binary-tree-node-right
(binary-tree-node-right tree))))
((null (binary-tree-node-right
(binary-tree-node-right tree)))
(setf (binary-tree-node-right tree)
(binary-tree-node-left
(binary-tree-node-right tree))))
(t ((let* ((moved-node (remove-leftmost tree)))
(setf (binary-tree-node-left moved-node)
(binary-tree-node-left
(binary-tree-node-right tree)))
(setf (binary-tree-node-right moved-node)
(binary-tree-node-right
(binary-tree-node right tree)))
(setf (binary-tree-node-right tree)
moved-node))))))
(t (remove-node value (binary-tree-node-right tree)))))))
((string= value (binary-tree-node-value tree))
nil)))
===================
A couple of general observations.
(1) The use of VALUES is not necessary. It should be reomved.
(2) The final cases of remove-leftmost and remove-rightmost return
different values. That is probably not what you want. This
could be a case where a defining macro could be used so that you
get the same structure in both branches.
(3) If find the two-level nesting of accesses a bit verbose, but don't
have an immediate answer to how to improve it. It would take some
thought, but I think it should be possible. Perhaps additional
recursion would work for it.
(4) In REMOVE-NODE, you have (t (cond ...)), which is redundant. you
should just promote the body of the included cond up to the level
of the first COND and eliminate some indentation levels.
(5) Again, there is a lot of parallel structure in the remove node
code, essentially just a mirror image again. I would use helper
functions for those, and probably introduce a defining macro to
make sure that they end up looking the same.
An example of a defining macro for the first case, and how one would go
about writing it:
[a] Start with the original code:
(defun remove-leftmost (tree)
(cond ((null tree) nil)
((null (binary-tree-node-left tree))
(values tree))
((null (binary-tree-node-left
(binary-tree-node-left tree)))
(let* ((temp (binary-tree-node-left
(binary-tree-node-left tree))))
(setf (binary-tree-node-left
(binary-tree-node-left tree)) nil)
(values temp)))
(t (remove-leftmost (binary-tree-node-left tree)))))
[b] notice that the only real difference is the name of the accessor
used for getting and setting values. Abstract that into a pattern:
`(defun remove-leftmost (tree)
(cond ((null tree) nil)
((null (,accessor tree))
tree)
((null (,accessor (,accessor tree)))
(let* ((temp (,accessor (,accessor tree))))
(setf (,accessor (,accessor tree)) nil)
temp))
(t (remove-leftmost (,accessor tree)))))
[c] notice the recursion and the need to supply a name and add
that to the pattern:
`(defun ,name (tree)
(cond ((null tree) nil)
((null (,accessor tree))
tree)
((null (,accessor (,accessor tree)))
(let* ((temp (,accessor (,accessor tree))))
(setf (,accessor (,accessor tree)) nil)
temp))
(t (,name (,accessor tree)))))
[d] Now make this into a macro that takes a name and accessor:
(defmacro def-tree-remover (name accessor)
`(defun ,name (tree)
(cond ((null tree) nil)
((null (,accessor tree))
tree)
((null (,accessor (,accessor tree)))
(let* ((temp (,accessor (,accessor tree))))
(setf (,accessor (,accessor tree)) nil)
temp))
(t (,name (,accessor tree)))))
[e] Use the macro to define the removal functions:
(def-tree-remover remove-leftmost binary-tree-node-left)
(def-tree-remover remove-rightmost binary-tree-node-right)
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> ballpointpenthief <·················@yahoo.co.uk> writes:
>> Pick the bones out of this please
> A couple of general observations.
> (2) The final cases of remove-leftmost and remove-rightmost return
> different values. That is probably not what you want.
Also, the second case returns a tree only when it's empty:
> ((null (binary-tree-node-left
> (binary-tree-node-left tree)))
> (let* ((temp (binary-tree-node-left
> (binary-tree-node-left tree))))
> (5) Again, there is a lot of parallel structure in the remove node
> code, essentially just a mirror image again. I would use helper
> functions for those, and probably introduce a defining macro to
> make sure that they end up looking the same.
Another approach is to put the code in a macrolet and call it directly,
once for the string< branch and once for string>.
A couple more points:
There are several CONDs that can be replaced with AND or IF,
especially the outer ones.
There are several occurances of the expressions
(binary-tree-node-side tree)
and
(binary-tree-node-side (binary-tree-node-side tree)),
where side = left|right.
With LET*, you can define a local variable for the first expression,
and then use that variable to define another variable for the
second expression. The second variable is your temp variable.
It can be used everywhere except with SETF.
--
Dan
www.prairienet.org/~dsb/
Thomas A. Russ wrote:
> (3) [I] find the two-level nesting of accesses a bit verbose, but don't
> have an immediate answer to how to improve it.
I think the standard approach is to test for value equality of the
current node. If it's equal, you process it, otherwise you recurse
left or right as appropriate. remove-node takes three more arguments
to do this: a reference to the current node, which becomes the parent;
the access function that currently returns the node you're recursing
into; and the corresponding remove-tree function.
--
Dan
www.prairienet.org/~dsb/
One week since I started this topic. I guess I've been going at a
steady pace.
On 17 Apr, 18:37, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> ballpointpenthief <·················@yahoo.co.uk> writes:
> > Pick the bones out of this please
> > Be as harsh as you like.
>
> OK, here's the code, reformatted using Emacs.
> A couple of general observations.
>
<snip>
> (5) Again, there is a lot of parallel structure in the remove node
> code, essentially just a mirror image again. I would use helper
> functions for those, and probably introduce a defining macro to
> make sure that they end up looking the same.
>
> An example of a defining macro for the first case, and how one would go
> about writing it:
<snip>
My latest attempt is below. The code is probably about twice as long
as it should be. I hope I have not messed up the indentation like my
posts last week!
1) Take a look at remove-node-left, and remove-node-right. There is an
obvious pattern to these functions, how can I write this as a macro?
(The advice quoted above was for an identical pattern)
2) I'm returning a dotted list from remove-leftmost / remove-
rightmost. This is because I now need to return two pieces of
information from the function. Is this a common technique?
Thanks to the people who gave me pointers.
Matt
==========================
;;;; Sorted Binary String Tree Functions
(defmacro* tree-node (value left right)
`(cons ,value
(cons ,left
(cons ,right nil))))
;; ease-of-use functions
(defun node-value (tree) (car tree))
(defun node-left (tree) (cadr tree))
(defun node-right (tree) (caddr tree))
(defun print-bin-tree (tree)
(if (null tree)
nil
(progn (print-bin-tree (node-left tree))
(print (node-value tree))
(print-bin-tree (node-right tree)))))
(defun insert-value (value tree)
(cond ((null tree) (tree-node value nil nil))
((string< value (node-value tree))
(tree-node (node-value tree)
(insert-value value (node-left tree))
(node-right tree)))
(t (tree-node (node-value tree)
(node-left tree)
(insert-value value (node-right tree))))))
;; Returns a dotted pair :
;; ( removed-node . remaining-tree )
(defun remove-rightmost (tree)
(let* ((child (node-right tree))
(grandchild (node-right child)))
(if (null grandchild)
(cons child
(tree-node (node-value tree)
(node-left tree)
nil))
(let* ((recursive-result (remove-rightmost child)))
(cons (car recursive-result)
(tree-node (node-value tree)
(node-left tree)
(cdr recursive-result)))))))
;; Returns a dotted pair :
;; ( removed-node . remaining-tree )
(defun remove-leftmost (tree)
(let* ((child (node-left tree))
(grandchild (node-left child)))
(if (null grandchild)
(cons child
(tree-node (node-value tree)
nil
(node-right tree)))
(let* ((recursive-result (remove-leftmost child)))
(cons (car recursive-result)
(tree-node (node-value tree)
(cdr recursive-result)
(node-right tree)))))))
;; Should only be called from the remove-node function
(defun remove-node-left (tree)
(cond ((null tree) nil)
((null (node-left tree)) tree)
((null (node-left (node-left tree)))
(tree-node (node-value tree)
(node-right (node-left tree))
(node-right tree)))
((null (node-right (node-left tree)))
(tree-node (node-value tree)
(node-left (node-left tree))
(node-right tree)))
(t (let* ((temp (remove-rightmost (node-left tree)))
(switched-node (car temp))
(remaining-tree (cdr temp)))
(tree-node (node-value tree)
(tree-node (node-value switched-node)
(node-left remaining-tree)
(node-right remaining-tree))
(node-right tree))))))
;; Should only be called from the remove-node function
(defun remove-node-right (tree)
(cond ((null tree) nil)
((null (node-right tree)) tree)
((null (node-left (node-right tree)))
(tree-node (node-value tree)
(node-left tree)
(node-right (node-right tree))))
((null (node-right (node-right tree)))
(tree-node (node-value tree)
(node-left tree)
(node-left (node-right tree))))
(t (let* ((temp (remove-rightmost (node-right tree)))
(switched-node (car temp))
(remaining-tree (cdr temp)))
(tree-node (node-value tree)
(node-left tree)
(tree-node (node-value switched-node)
(node-left remaining-tree)
(node-right remaining-tree)))))))
;; Return a tree with the specified value removed.
(defun remove-value (value tree)
(cond ((null tree) nil)
((string= value (node-value tree)) nil)
((string< value (node-value tree))
(cond ((string= value (node-value (node-left tree)))
(remove-node-left tree))
((string< value (node-value (node-left tree)))
(tree-node (node-value tree)
(tree-node (node-value (node-left tree))
(remove-value value (node-left tree))
(node-right (node-left tree)))
(node-right tree)))
((string> value (node-value (node-left tree)))
(tree-node (node-value tree)
(tree-node (node-value (node-left tree))
(node-left tree)
(remove-value value (node-left tree)))
(node-right tree)))))
((string> value (node-value tree))
(cond ((string= value (node-value (node-right tree)))
(remove-node-right tree))
((string< value (node-value (node-right tree)))
(tree-node (node-value tree)
(node-left tree)
(tree-node (node-value (node-right tree))
(remove-value value (node-left tree))
(node-right (node-right tree)))))
((string> value (node-value (node-right tree)))
(tree-node (node-value tree)
(node-left tree)
(tree-node (node-value (node-right tree))
(node-left (node-right tree))
(remove-value value (node-right tree)))))))))
;(defun sort (tree))
;(defun balance (tree))
=======================
On 17 Apr 2007 08:21:19 -0700, ballpointpenthief <·················@yahoo.co.uk> wrote:
> I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> language.
CLISP is the name of one implementation, not the name of the language.
The language is called "Common Lisp" and usually abbreviated CL.
As for your code, you should post from somewhere where your formatting
isn't totally destroyed. It'd be a PITA to read this.
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
ballpointpenthief <·················@yahoo.co.uk> writes:
> On 17 Apr, 16:32, Edi Weitz <········@agharta.de> wrote:
> > On 17 Apr 2007 08:21:19 -0700, ballpointpenthief <·················@yahoo.co.uk> wrote:
> >
> > > I'm a fairly new programmer (18 months) learning CL as a 3rd
> > > language.
>
>
> > As for your code, you should post from somewhere where your formatting
> > isn't totally destroyed.
>
> I'm not sure where - paste.lisp.org seems to do the same thing.
> I've made the names shorter instead.
The problem isn't the names. The long names help in readability.
The problem is the amount of indentation for the first level under the
(def... forms.)
--
Thomas A. Russ, USC/Information Sciences Institute
In article <·············@agharta.de>, Edi Weitz <········@agharta.de>
wrote:
> On 17 Apr 2007 08:21:19 -0700, ballpointpenthief
> <·················@yahoo.co.uk> wrote:
>
> > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> > language.
>
> CLISP is the name of one implementation, not the name of the language.
> The language is called "Common Lisp" and usually abbreviated CL.
Common Lisp is not a language, it is a family of languages.
From http://www.lisp.org/HyperSpec/Body/sec_1-1-2.html :
"Common Lisp was designed as a description of a family of languages."
rg
In article <·······························@news.gha.chartermi.net>,
Ron Garret <·········@flownet.com> wrote:
> In article <·············@agharta.de>, Edi Weitz <········@agharta.de>
> wrote:
>
> > On 17 Apr 2007 08:21:19 -0700, ballpointpenthief
> > <·················@yahoo.co.uk> wrote:
> >
> > > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> > > language.
> >
> > CLISP is the name of one implementation, not the name of the language.
> > The language is called "Common Lisp" and usually abbreviated CL.
>
> Common Lisp is not a language, it is a family of languages.
>
> From http://www.lisp.org/HyperSpec/Body/sec_1-1-2.html :
>
> "Common Lisp was designed as a description of a family of languages."
>
> rg
What about ANSI Common Lisp?
--
http://lispm.dyndns.org
From: Kent M Pitman
Subject: Re: Common Lisp is not a language
Date:
Message-ID: <uslays9rd.fsf@nhplace.com>
Rainer Joswig <······@lisp.de> writes:
> In article <·······························@news.gha.chartermi.net>,
> Ron Garret <·········@flownet.com> wrote:
>
> > In article <·············@agharta.de>, Edi Weitz <········@agharta.de>
> > wrote:
> >
> > > On 17 Apr 2007 08:21:19 -0700, ballpointpenthief
> > > <·················@yahoo.co.uk> wrote:
> > >
> > > > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> > > > language.
> > >
> > > CLISP is the name of one implementation, not the name of the language.
> > > The language is called "Common Lisp" and usually abbreviated CL.
> >
> > Common Lisp is not a language, it is a family of languages.
> >
> > From http://www.lisp.org/HyperSpec/Body/sec_1-1-2.html :
> >
> > "Common Lisp was designed as a description of a family of languages."
> >
> > rg
>
> What about ANSI Common Lisp?
As I recall, the referenced paragraph, quoted here, and the entire
section it was in, was written by a coalition of people as a kind of
consensus view of the history. I'm not sure whether the individual
quoted sentence is due to me, and even if it was, it was a long time
ago, so my views here are through the haze of memory, as augmented
by the obvious issues of textual context:
| In April 1981, after a DARPA-sponsored meeting concerning the
| splintered Lisp community, Symbolics, the SPICE project, the NIL
| project, and the S-1 Lisp project joined together to define Common
| Lisp. Initially spearheaded by White and Gabriel, the driving force
| behind this grassroots effort was provided by Fahlman, Daniel Weinreb,
| David Moon, Steele, and Gabriel. Common Lisp was designed as a
| description of a family of languages. The primary influences on Common
| Lisp were Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp, and
| Scheme. Common Lisp: The Language is a description of that design. Its
| semantics were intentionally underspecified in places where it was
| felt that a tight specification would overly constrain Common Lisp
| esearch [sic] and use.
(Presumably we meant "research", not "esearch"... sigh.)
In historical context, there was a risk that the entire language
family containing the enumerated languages would not be selected by
DARPA as the language of choice for research. (As I recall it,
Interlisp had been proposed by some as the language most used. But
the little dialects got together and said "no, we're really all the
same language, you just can't see it".) The loose-knit coalition
papered over their differences and spun the story they were all a
single idea. The move succeeded, and these dialects displaced
Interlisp, rather than vice versa. However, with the 1984 publication
of CL, those dialects were also slowly obsoleted by CL, which CL did
not really "describe" so much as "supplant".
The only lingering sense in which CL remained in any sense a language
family, and I don't think anyone would have described it that way even
then, is that code was not easily ported from implementation to
implementation. The original language definition did not seriously
address portability, probably because no one had the patience for such
issues until they had used the language for a while. (I wrote a
conference paper on the subject and it was rejected as uninteresting
in that timeframe. I just don't think anyone thought consciously
about how the language and its portability mattered.) ANSI CL
corrected that deficiency, by making portability a real issue and
seriously attempting to address it.
But I don't think CL presents itself (other than in this stray
sentence) as itself a language family. Lisp is the name of the family
of languages. (Whether there are usefully nameable subfamilies, I
suppose, is an open question.)
(Note well: My opinion is no particular authority on the matter. I
WAS there, and WAS a first-hand observer, but my views as expressed
here are still just my personal opinions. I don't claim any special
credential of rightness just because of the "writeness" of my involvement.)
Kent M Pitman wrote:
> (Presumably we meant "research", not "esearch"... sigh.)
The scary thing is that if you offset each character of "esearch" by two
you get "google".
kt
--
http://www.theoryyalgebra.com/
"Algebra is the metaphysics of arithmetic." - John Ray
In article <·············@nhplace.com>,
Kent M Pitman <······@nhplace.com> wrote:
> The only lingering sense in which CL remained in any sense a language
> family, and I don't think anyone would have described it that way even
> then, is that code was not easily ported from implementation to
> implementation.
I think that is quite significant, and I'm apparently not the only one
who thinks so. I draw your attention to:
http://groups.google.com/group/comp.lang.lisp/msg/7d9ebe2eac85a679
and in particular the following exchange between myself and Pascal
Costanza:
PC: You're certainly aware of the fact that Common Lisp is not a
programming language, but a family of languages.
RG: I knew that Lisp was a family. I was unaware that Common Lisp was
considered a family, and not a single language.
PC: [Long excerpt from CTLT2 elided] And, more to the point, from the
HyperSpec (Section 1.1.2): "Common Lisp was designed as a description of
a family of languages."
RG: I stand corrected.
PC: That's a good start, because EVERYTHING ELSE FOLLOWS FROM THERE.
[Emphasis added.]
rg
Ron Garret wrote:
> In article <·············@nhplace.com>,
> Kent M Pitman <······@nhplace.com> wrote:
>
>
>>The only lingering sense in which CL remained in any sense a language
>>family, and I don't think anyone would have described it that way even
>>then, is that code was not easily ported from implementation to
>>implementation.
>
>
> I think that is quite significant,
You mean because sockets and FFI were not standardized, and in a few
places in those 1000 pages things get left up to implementations?
Aggravation does not rise to the level of "hey, those are two different
languages!" though I certainly felt as if that might be the case porting
from Symantec C to CodeWarrior C.
>
> PC: [Long excerpt from CTLT2 elided] And, more to the point, from the
> HyperSpec (Section 1.1.2): "Common Lisp was designed as a description of
> a family of languages."
Was the author writing under the cloak of infallibility, channeling the
word of G*d, and is our Talmudic interpretation of those awkward words
precise? The legislative history shows that CL got designed to address
concerns of The Big Customer over language fragmentation, so it is hard
to imagine an intent other than to define one language. The next step
was a pretty tight ANSI standard language specification.
Too easy? (I know, it is mroe fun being contrarian.)
kt
--
http://www.theoryyalgebra.com/
"Algebra is the metaphysics of arithmetic." - John Ray
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
In article <·············@nhplace.com>,
Kent M Pitman <······@nhplace.com> wrote:
> Rainer Joswig <······@lisp.de> writes:
>
> > In article <·······························@news.gha.chartermi.net>,
> > Ron Garret <·········@flownet.com> wrote:
> >
> > > In article <·············@agharta.de>, Edi Weitz <········@agharta.de>
> > > wrote:
> > >
> > > > On 17 Apr 2007 08:21:19 -0700, ballpointpenthief
> > > > <·················@yahoo.co.uk> wrote:
> > > >
> > > > > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
> > > > > language.
> > > >
> > > > CLISP is the name of one implementation, not the name of the language.
> > > > The language is called "Common Lisp" and usually abbreviated CL.
> > >
> > > Common Lisp is not a language, it is a family of languages.
> > >
> > > From http://www.lisp.org/HyperSpec/Body/sec_1-1-2.html :
> > >
> > > "Common Lisp was designed as a description of a family of languages."
> > >
> > > rg
> >
> > What about ANSI Common Lisp?
>
> As I recall, the referenced paragraph, quoted here, and the entire
> section it was in, was written by a coalition of people as a kind of
> consensus view of the history. I'm not sure whether the individual
> quoted sentence is due to me, and even if it was, it was a long time
> ago, so my views here are through the haze of memory, as augmented
> by the obvious issues of textual context:
>
> | In April 1981, after a DARPA-sponsored meeting concerning the
> | splintered Lisp community, Symbolics, the SPICE project, the NIL
> | project, and the S-1 Lisp project joined together to define Common
> | Lisp. Initially spearheaded by White and Gabriel, the driving force
> | behind this grassroots effort was provided by Fahlman, Daniel Weinreb,
> | David Moon, Steele, and Gabriel. Common Lisp was designed as a
> | description of a family of languages. The primary influences on Common
> | Lisp were Lisp Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp, and
> | Scheme. Common Lisp: The Language is a description of that design. Its
> | semantics were intentionally underspecified in places where it was
> | felt that a tight specification would overly constrain Common Lisp
> | esearch [sic] and use.
>
> (Presumably we meant "research", not "esearch"... sigh.)
>
> In historical context, there was a risk that the entire language
> family containing the enumerated languages would not be selected by
> DARPA as the language of choice for research. (As I recall it,
> Interlisp had been proposed by some as the language most used. But
> the little dialects got together and said "no, we're really all the
> same language, you just can't see it".) The loose-knit coalition
> papered over their differences and spun the story they were all a
> single idea. The move succeeded, and these dialects displaced
> Interlisp, rather than vice versa. However, with the 1984 publication
> of CL, those dialects were also slowly obsoleted by CL, which CL did
> not really "describe" so much as "supplant".
>
> The only lingering sense in which CL remained in any sense a language
> family, and I don't think anyone would have described it that way even
> then, is that code was not easily ported from implementation to
> implementation. The original language definition did not seriously
> address portability, probably because no one had the patience for such
> issues until they had used the language for a while. (I wrote a
> conference paper on the subject and it was rejected as uninteresting
> in that timeframe. I just don't think anyone thought consciously
> about how the language and its portability mattered.) ANSI CL
> corrected that deficiency, by making portability a real issue and
> seriously attempting to address it.
>
> But I don't think CL presents itself (other than in this stray
> sentence) as itself a language family. Lisp is the name of the family
> of languages. (Whether there are usefully nameable subfamilies, I
> suppose, is an open question.)
If ANSI Common Lisp is a family of languages, this family
would have member languages (unless there is the empty
set of languages).
Is OpenMCL a programming language? LispWorks? Or just
extended/simplified implementations of ANSI CL?
Are there other descriptions of languages based on
ANSI Common Lisp? Hmm.
Mostly I see in the manuals of current Common Lisp systems:
a) we (try to) do ANSI Common Lisp
b) here are some places where we don't do ANSI CL
c) here we say how we implement some ANSI CL
d) we extend/simplify ANSI CL with the following ...
e) this is our library
a), b), and c) is just ANSI CL.
Now would d) make it a language?
What could be in d) ?
1) language extensions like tail recursion elimination
2) added special forms
3) new built-in data types (decimal arithmetic)
4) parallel computing constructs
d) could also describe a sublanguage. Say a Common Lisp
without CLOS.
>
> (Note well: My opinion is no particular authority on the matter. I
> WAS there, and WAS a first-hand observer, but my views as expressed
> here are still just my personal opinions. I don't claim any special
> credential of rightness just because of the "writeness" of my involvement.)
--
http://lispm.dyndns.org
From: Kent M Pitman
Subject: Re: Common Lisp is not a language
Date:
Message-ID: <uabx41k6j.fsf@nhplace.com>
Rainer Joswig <······@lisp.de> writes:
> Is OpenMCL a programming language? LispWorks? Or just extended/simplified
> implementations of ANSI CL? Are there other descriptions of languages
> based on ANSI Common Lisp? Hmm.
I think it's entirely reasonable to take the position personally that
Lisp either is or is not a "language family", that Common Lisp either
is or is not a "language", that Scheme is or is not part of one of
those categorizations, etc. I certainly don't mean to contest that
anyone believes what they believe, nor that they get value for doing
so.
I often don't use the terminology in the way most people seem to, so
who am I to tell another that they shouldn't?
I do think sometimes people see a written document and try to
interpret it in an overly specific way. I don't like to say I have
the uniquely right interpretation as much as to say "please don't
assume your own reading is the only possible reading". Sometimes I
think it doesn't occur to people that the thing they so carefully read
even MIGHT have meant something other than what they infer. And it's
in that light that many of my remarks should be taken.
> Mostly I see in the manuals of current Common Lisp systems:
>
> a) we (try to) do ANSI Common Lisp
> b) here are some places where we don't do ANSI CL
> c) here we say how we implement some ANSI CL
> d) we extend/simplify ANSI CL with the following ...
> e) this is our library
>
> a), b), and c) is just ANSI CL.
>
> Now would d) make it a language?
>
> What could be in d) ?
>
> 1) language extensions like tail recursion elimination
> 2) added special forms
> 3) new built-in data types (decimal arithmetic)
> 4) parallel computing constructs
>
> d) could also describe a sublanguage. Say a Common Lisp
> without CLOS.
I don't personally approach the problem this way, although I think these
are good thought questions. I find the terminology manipulates me, and I
prefer to pick terminology to match what I'm thinking.
I think I think of those things you're remarking on as dialectal
variations. That is, I look to the social behavior of ahering to a
common reference as evidence that they are a common language. The day
any of those implementations says "we don't care what ANSI CL says" is
the day it's not a CL. The day any of those implementations say "we
don't care what the Lisp community does" is the day it's not a Lisp.
Exactly because of this, I generally don't see Scheme as Lisp. Not
because of the similarities or differences with other Lisps, but
because of the social behavior of not caring whether and how a change
made to the language will affect or relate to other Lisps.
Most commonly, though not consistently, I personally refer to Lisp as
a language, CL as a dialect of Lisp, and things like MCL and LispWorks
and Allegro as implementations of Lisp. Some may say Lisp is not a
language, since it designates no specific dictionary of words, but by
the same claim, there is no English, only British and American. I
reject that. I find it more natural to say people speak dialects, in
part to remind myself that the claim that one can speak a "neutral
version" of a language rather than a "dialect" is non-sensical. Like
everyone claiming they have no spoken accent, and that only others
(who don't have their own neutrality) have an accent.
It's trivially true that any language that inherits from another
language creates a language family. But one must be careful about
that. Familyness cannot be said to be transitive or we will follow
our family trees around and every one of us will be found to be of one
family. Which is ok. But if that's all you mean by "family", then
give it up, the word is useless. Words are useful only if you can
make a distinction by having used or not used them. It must be
possible to make breaks among languages, and so I make that break
subjectively. To me, it relies on the intent of the designer and
community as to how referencing will work. Human families are the
same. Some people think second cousins are family; others don't even
keep up with first cousins. And even within the same "family",
individuals disagree. But this doesn't negate the meaning of the
term, it just means you have to establish a frame of reference for
understanding the use in order to interpret remarks made using the
term.
I use the term language family rarely, but when I do it's to establish
relations among languages for a moment of discussion. It's rarely a
permanent aggregation... more like a coalition of the moment.
I might aggregate languages by feature, independent of their
derivation and call this a language family. Kind of like multiple
inheritance, though with the understanding that the features I'm
talking about are descriptive, not implementational. There is a
family I call the "line noise" languages, like Teco and APL, that are
sparing in their syntax, making each character a command. There is a
family of "straight line" languages that imperatively execute from top
to bottom (BASIC, FORTRAN, and the assembly languages, but also
HyperTalk and bash and other scripting languages). I wouldn't object
to the term "object oriented languages" as a family, but for the fact
that we'd have to talk for hours about what "object oriented" means in
order to know which languages were in them (and whether Lisp was even
one of them), but certainly as a feature set (once you know which of
the several features that are variously called "object oriented"
you're talking about), it's as good as any.
I might sometimes group them in clusters for ease of presentation,
like clicking to show/hide a tree of subdirectories in a file browser.
I think the relevant things are not the words, but the thoughts
underlying them. There are too many important things to say to be
held back by someone telling you that the words don't permit you to
say them.
Like most things in life, I think the enlightenment comes from learning
what questions to ask, and from continuing to ask them (often learning
that the answers you give change with time and an open mind and dialog
and personal growth). Seen that way, the answer almost doesn't really
matter, does it?
Rainer Joswig <······@lisp.de> wrote:
+---------------
| Mostly I see in the manuals of current Common Lisp systems:
| a) we (try to) do ANSI Common Lisp
| b) here are some places where we don't do ANSI CL
| c) here we say how we implement some ANSI CL
| d) we extend/simplify ANSI CL with the following ...
| e) this is our library
| a), b), and c) is just ANSI CL.
+---------------
The CLHS speaks to this:
http://www.lisp.org/HyperSpec/Body/sec_1-5-1-1.html
1.5.1.1 Required Language Features
http://www.lisp.org/HyperSpec/Body/sec_1-5-1-5.html
1.5.1.5 Conformance Statement
...
If the implementation conforms with some but not all of the
requirements of this standard, then the conformance statement
shall be: ...[prototype]...
Also see this glossary entry:
http://www.lisp.org/HyperSpec/Body/glo_p.html#purports_to_conform
PURPORTS TO CONFORM v. makes a good-faith claim of conformance.
This term expresses intention to conform, regardless of whether
the goal of that intention is realized in practice. For example,
language implementations have been known to have bugs, and while
an implementation of this specification with bugs might not be
a conforming implementation, it can still purport to conform.
This is an important distinction in certain specific cases; e.g.,
see the variable *features*.
And this Variable entry:
http://www.lisp.org/HyperSpec/Body/var_stfeaturesst.html
...
:ansi-cl
If present, indicates that this specification has been
adopted by ANSI as an official standard, and that the
implementation purports to conform.
I would suspect that almost all popular CL implementations
*at least* "purport to conform" to the ANSI Standard.
+---------------
| Now would d) make it a language?
| What could be in d) ?
| 1) language extensions like tail recursion elimination
| 2) added special forms
| 3) new built-in data types (decimal arithmetic)
| 4) parallel computing constructs
+---------------
The CLHS speaks to this:
http://www.lisp.org/HyperSpec/Body/sec_1-5-1-3.html
1.5.1.3 Documentation of Extensions
A conforming implementation shall be accompanied by a document that
separately describes any features accepted by the implementation
that are not specified in this standard, but that do not cause any
ambiguity or contradiction when added to the language standard.
Such extensions shall be described as being ``extensions to Common
Lisp as specified by ANSI <<standard number>>.''
So depending on the exact style of integration with base CL,
all of your "d)1-4" *might* be permissible extensions to CL.
But watch out for the restrictions here:
http://www.lisp.org/HyperSpec/Body/sec_1-6.html
1.6 Language Extensions
...
An implementation can have extensions, provided they do not
alter the behavior of conforming code and provided they are
not explicitly prohibited by this standard.
...
The following list contains specific guidance to implementations
concerning certain types of extensions.
- Extra return values ... [prohibited] ...
- Unsolicited messages ... [prohibited] ...
- Implementation of macros and special forms
Macros and special operators defined in this standard
must not be functions.
+---------------
| d) could also describe a sublanguage. Say a Common Lisp
| without CLOS.
+---------------
The CLHS speaks to this:
http://www.lisp.org/HyperSpec/Body/sec_1-7.html
1.7 Language Subsets
The language described in this standard contains no subsets,
though subsets are not forbidden.
For a language to be considered a subset, it must have
the property that any valid program in that language has
equivalent semantics and will run directly (with no extralingual
pre-processing, and no special compatibility packages) in
any conforming implementation of the full language.
A language that conforms to this requirement shall be
described as being a ``subset of Common Lisp as specified
by ANSI <<standard number>>.''
Note: From time to time I have noodled around with the notion of
defining a subset of CL which meets the constraints of CLHS 1.7
and is still sufficiently rich to be interesting and/or useful
[e.g., for "scripting" or CGI or the like]. It's not as easy as
it might at first appear. Little fiddly bits in one corner of
the language interact in subtle ways with fiddly bits in other
corners of the language.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: Re: Common Lisp is not a language
Date:
Message-ID: <ufy6vzo9y.fsf@nhplace.com>
····@rpw3.org (Rob Warnock) writes:
> Note: From time to time I have noodled around with the notion of
> defining a subset of CL which meets the constraints of CLHS 1.7
> and is still sufficiently rich to be interesting and/or useful
> [e.g., for "scripting" or CGI or the like]. It's not as easy as
> it might at first appear. Little fiddly bits in one corner of
> the language interact in subtle ways with fiddly bits in other
> corners of the language.
An alternative might be to start from ISLISP and work up.
ISLISP is not specifically ANSI CL compatible, mind you, but I like to
think of it as "culturally compatible" with ANSI CL... Certainly
moreso than, say, Scheme. It's quite small, and lacking a lot of the
power of CL, but what it has got is in a style that's similar to CL.
Whether it would suit any given purpose is hard to know, which is why
you'd have to look for yourself.
Kent M Pitman <······@nhplace.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Note: From time to time I have noodled around with the notion of
| > defining a subset of CL which meets the constraints of CLHS 1.7
| > and is still sufficiently rich to be interesting and/or useful
| > [e.g., for "scripting" or CGI or the like]. It's not as easy as
| > it might at first appear. Little fiddly bits in one corner of
| > the language interact in subtle ways with fiddly bits in other
| > corners of the language.
|
| An alternative might be to start from ISLISP and work up.
+---------------
I *have* actually considered that. But after several cursory readings
of the ISLISP spec, I have come to the provisional conclusion that
ISLISP, while quite interesting *in its own right*, isn't really
a suitable candidate for "a subset of Common Lisp as specified by
ANSI X3.226" under the constraints of CLHS "1.7 Language Subsets".
For one thing [and this is a big one!], as far as I can tell, getting
a non-trivial ISLISP program to load into a CL implementation would
require at least *some* sort of "compatibility package" to have been
pre-loaded into the CL implementation, something that is expressly
excluded from the definition of a CL subset by CLHS 1.7.
That is, to me at least, whether there even *can* be one or more
useful "subsets of CL" in the strict CLHS 1.7 sense is separate
and very different question from that of what "a good small Lisp"
could/would/sholud look like... and whether Scheme or ISLISP or
XYZ [name your favorite] is a good starting point for that. Both
questions are interesting, but the one I was addressing in the
above-quoted "Note" was the former, not the latter.
By the way, in the interest of exposing a little of my motivation
for looking into the "subset" question, let me say that I am
perfectly happy these days to use a "full" Common Lisp for almost
all of my Lisp-family needs [e.g., I haven't written any new Scheme
code for several years now!], but there are a *few* situations
where my usual CL environment (CMUCL) cannot run [or at least not
conveniently enough for it to be feasible] and it would be very
nice to have an implementation of a small subset of CL which
*could* run. Being a "subset" in the CLHS 1.7 sense would mean
that most of the code could be developed & tested in the "full"
environment. It would also make it more likely to be portable
to some other "full" environment than the one I currently favor.
Plus, I have yet to hear of anyone who has managed to come up
with a non-trivial yet useful "subset of ANSI CL" in the strict
CLHS 1.7 sense. It's a bit of an intellectual challenge.
+---------------
| ISLISP is not specifically ANSI CL compatible, mind you, but I like
| to think of it as "culturally compatible" with ANSI CL... Certainly
| moreso than, say, Scheme. It's quite small, and lacking a lot of the
| power of CL, but what it has got is in a style that's similar to CL.
+---------------
Based on my somewhat-limited reading of the spec, I quite agree
on all of these points.
+---------------
| Whether it would suit any given purpose is hard to know, which
| is why you'd have to look for yourself.
+---------------
(See the above...)
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kent M Pitman
Subject: Re: Common Lisp is not a language
Date:
Message-ID: <ubqhjzha4.fsf@nhplace.com>
····@rpw3.org (Rob Warnock) writes:
> That is, to me at least, whether there even *can* be one or more
> useful "subsets of CL" in the strict CLHS 1.7 sense is separate
> and very different question from that of what "a good small Lisp"
> could/would/sholud look like.
Oh, it definitely is not a subset. I was just suggesting it if you
wanted a small Lisp dialect that was similar to CL for an independent
scripting purpose.
> ... there are a *few* situations
> where my usual CL environment (CMUCL) cannot run [or at least not
> conveniently enough for it to be feasible] and it would be very
> nice to have an implementation of a small subset of CL which
> *could* run. ...
Ah. Indeed, if you want to move your programs back and forth, it gets
a bit trickier.
> Plus, I have yet to hear of anyone who has managed to come up
> with a non-trivial yet useful "subset of ANSI CL" in the strict
> CLHS 1.7 sense. It's a bit of an intellectual challenge.
Paul Robertson did work on this at one point and did the best job of
outlining such a subset. It was part of his review comments on the
standard. I have that data somewhere offline, and keep meaning to put
it online...
From: Kent M Pitman
Subject: Re: Common Lisp is not a language
Date:
Message-ID: <ud51tb83x.fsf@nhplace.com>
Kent M Pitman <······@nhplace.com> writes:
> ...
> Paul Robertson did work on this at one point and did the best job of
> outlining such a subset. It was part of his review comments on the
> standard. I have that data somewhere offline, and keep meaning to put
> it online...
Oh, that comment by Paul Robertson is _already_ online... I guess I had
dredged it up previously and had forgotten.
http://www.nhplace.com/kent/CL/Public-Review-PRobertson.html
It's the best stab at a theory of subsets I've seen anyone do.
Kent M Pitman wrote:
> Kent M Pitman <······@nhplace.com> writes:
>
>
>>...
>>Paul Robertson did work on this at one point and did the best job of
>>outlining such a subset. It was part of his review comments on the
>>standard. I have that data somewhere offline, and keep meaning to put
>>it online...
>
>
> Oh, that comment by Paul Robertson is _already_ online... I guess I had
> dredged it up previously and had forgotten.
>
> http://www.nhplace.com/kent/CL/Public-Review-PRobertson.html
>
> It's the best stab at a theory of subsets I've seen anyone do.
That's a great window on the do-or-die mood driving the development of
CL. Here's my favorite line:
> If we leave everything in, the language will not be used
> except by a decreasing number of LISP zealots. That too is a disaster.
Disaster? Ha! Lisp! It's mine! It's all mine!!!!! MWUAHAHAHAHAHAAAA!!!!
(And we prefer "smug Lisp weenies".)
kenny
--
http://www.theoryyalgebra.com/
"Algebra is the metaphysics of arithmetic." - John Ray
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
Ron Garret <·········@flownet.com> writes:
> In article <·············@agharta.de>, Edi Weitz <········@agharta.de>
> wrote:
>
>> On 17 Apr 2007 08:21:19 -0700, ballpointpenthief
>> <·················@yahoo.co.uk> wrote:
>>
>> > I'm a fairly new programmer (18 months) learning CLISP as a 3rd
>> > language.
>>
>> CLISP is the name of one implementation, not the name of the language.
>> The language is called "Common Lisp" and usually abbreviated CL.
>
> Common Lisp is not a language, it is a family of languages.
>
> From http://www.lisp.org/HyperSpec/Body/sec_1-1-2.html :
>
> "Common Lisp was designed as a description of a family of languages."
In addition, one can implement a subset of Common Lisp and all it
rightly and legaly a "subset of Common Lisp", therefore Common Lisp an
indeed be desribed as a family of languages, the union of all its
subsets.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Specifications are for the weak and timid!"
ballpointpenthief wrote:
> Be as harsh as you like.
I think if you made it purely functional and used a pattern matcher it would
be about 10 lines of code.
Relevant code from the OCaml stdlib:
let rec remove_min_elt = function
Empty -> invalid_arg "Set.remove_min_elt"
| Node(Empty, v, r, _) -> r
| Node(l, v, r, _) -> bal (remove_min_elt l) v r
let rec remove x = function
Empty -> Empty
| Node(l, v, r, _) ->
let c = Ord.compare x v in
if c = 0 then merge l r else
if c < 0 then bal (remove x l) v r else bal l v (remove x r)
--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet