I came across a small Logo example function on Brian Harvey's site,
that I translated into a few languages for comparison:
http://lojic.com/blog/2007/08/31/logo-ruby-javascript
I also translated it to Common Lisp (see below), but I'm not sure if
using loop is the best approach. Also, printing a list of words as a
space separated sentence seems cumbersome, so I expect there's an
easier way.
The original Logo program with output is here: http://www.cs.berkeley.edu/~bh/logo-sample.html
Any ideas to express this better in CL?
(defun print-choice (lst)
(loop for i in lst do (format t "~a " i))
(format t "~%"))
(defun choices (menu sofar)
(cond
(menu
(loop for i in (car menu) do (choices (cdr menu) (append sofar
(list i)))))
(t
(print-choice sofar))))
(choices (list
(list "small" "medium" "large")
(list "vanilla" "ultra chocolate" "lychee" "rum raisin"
"ginger")
(list "cone" "cup")) '())
Thanks,
Brian Adkins
--
http://lojic.com/blog/
On 1 Sep, 21:26, Brian Adkins <···········@gmail.com> wrote:
> I came across a small Logo example function on Brian Harvey's site,
> that I translated into a few languages for comparison:http://lojic.com/blog/2007/08/31/logo-ruby-javascript
>
> I also translated it to Common Lisp (see below), but I'm not sure if
> using loop is the best approach. Also, printing a list of words as a
> space separated sentence seems cumbersome, so I expect there's an
> easier way.
Well a straight forward translation would give you this:
(defun choices (menu &optional sofar)
(if (null menu) (format t "~a~%" (reverse sofar))
(mapc (lambda(x) (choices (rest menu) (cons x sofar))) (first
menu))))
(choices '((small medium large) (vanilla) (cup cone)))
(SMALL VANILLA CUP)
(SMALL VANILLA CONE)
(MEDIUM VANILLA CUP)
(MEDIUM VANILLA CONE)
(LARGE VANILLA CUP)
(LARGE VANILLA CONE)
and if you're concerned about matching the logo appearance exactly you
can manipulate the list output using format control sequences and pass
strings rather than symbols.
On 1 Sep, 22:36, Chris Russell <·····················@gmail.com>
wrote:
> On 1 Sep, 21:26, Brian Adkins <···········@gmail.com> wrote:> I came across a small Logo example function on Brian Harvey's site,
> > that I translated into a few languages for comparison:http://lojic.com/blog/2007/08/31/logo-ruby-javascript
>
> > I also translated it to Common Lisp (see below), but I'm not sure if
> > using loop is the best approach. Also, printing a list of words as a
> > space separated sentence seems cumbersome, so I expect there's an
> > easier way.
>
> Well a straight forward translation would give you this:
>
> (defun choices (menu &optional sofar)
> (if (null menu) (format t "~a~%" (reverse sofar))
> (mapc (lambda(x) (choices (rest menu) (cons x sofar))) (first
> menu))))
Actually it should be:
(defun choices (menu &optional sofar)
(if (null menu) (format t "~a ~%" (reverse sofar)))
(mapc (lambda(x) (choices (rest menu) (cons x sofar))) (first
menu)))
the mapc should lie outside the if statement and rely on the lack of
members to enforce termination.
Whoops.
A friend of mine submitted a Python solution that seems somewhat Lispy
to me.
optstr = lambda x : (type(x)==str)*str(x)+(type(x)!=str)*' '.join(x)
prod1 = lambda elem, vec : map(lambda x : optstr(elem)+'
'+optstr(x), vec)
xprod = lambda vec1, vec2 : reduce(list.__add__,map(lambda elem :
prod1(elem ,vec2), vec1))
choices = lambda x : '\n'.join(reduce(xprod, x))
q = [['small','medium','large'],
['vanilla', ['ultra', 'chocolate'], 'lychee', ['rum', 'raisin'],
'ginger'],
['cone', 'cup']]
print choices(q)
My Lisp chops aren't up to making a quick translation (although I plan
on making one on Sunday), but I did make a direct translation to Ruby,
so between the two versions, maybe a Lisper could show the Lisp
equivalent. I like the fact that the cross products are computed
beforehand and printed with a single print at the end.
Ruby version (I had to write reduce :( )
def reduce fn, lst
return lst if lst.length < 2
result = fn.call(lst[0],lst[1])
return lst.length == 2 ? result : reduce(fn,
[fn.call(lst[0],lst[1])] + lst[2..-1])
end
optstr = lambda {|x| x.instance_of?(String) ? x : x.join(' ')}
prod1 = lambda {|elem, vec| vec.map {|x| optstr.call(elem)+'
'+optstr.call(x)}}
xprod = lambda {|vec1, vec2| reduce(lambda {|a, b| a+b}, vec1.map {|
elem| prod1.call(elem, vec2)})}
choices = lambda {|x| reduce(xprod, x).join("\n")}
q = [ ['small','large'],
['vanilla', ['ultra', 'chocolate'], ['rum', 'raisin']],
['cone', 'cup'],
[ 'here', 'to go'] ]
puts choices.call(q)
I find having to append .call to the lambdas unnatural in Ruby. I much
prefer the more transparent Lisp way.
Brian
Brian Adkins wrote:
> Got impatient :) Had to research to find #\Newline and write join-
> string. Surely there's something like Ruby's list.join(str) or
> Python's str.join(list) already, but I couldn't find it.
You can find it in my first answer:
(defun join-string (sep list)
(format nil (concatenate 'string "~{~A~#[~:;" sep "~]~}") list))
And in Common Lisp there is no need to use abbreviations like "lst". It is
common to use meaningful names.
Another idea is this:
(defun join-string (sep list)
(reduce (lambda (x y) (concatenate 'string x sep y)) list))
I don't know if there is a function like "join" in Common Lisp, maybe the
reason is that it is so simple to write your own version, if you need it.
In Haskell it looks like this:
joinString sep = foldl1 (\x y -> x ++ sep ++ y)
I really like currying :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <······························@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Brian Adkins wrote:
>
> > Got impatient :) Had to research to find #\Newline and write join-
> > string. Surely there's something like Ruby's list.join(str) or
> > Python's str.join(list) already, but I couldn't find it.
>
> You can find it in my first answer:
>
> (defun join-string (sep list)
> (format nil (concatenate 'string "~{~A~#[~:;" sep "~]~}") list))
>
> And in Common Lisp there is no need to use abbreviations like "lst". It is
> common to use meaningful names.
>
> Another idea is this:
>
> (defun join-string (sep list)
> (reduce (lambda (x y) (concatenate 'string x sep y)) list))
>
> I don't know if there is a function like "join" in Common Lisp, maybe the
> reason is that it is so simple to write your own version, if you need it.
Only that it is inefficient since it concatenates lots of strings.
Instead of consing one string, it conses n-1 strings.
> In Haskell it looks like this:
>
> joinString sep = foldl1 (\x y -> x ++ sep ++ y)
>
> I really like currying :-)
Yeah, currying is nice. But not for programming.
--
http://lispm.dyndns.org
Brian Adkins wrote:
> I came across a small Logo example function on Brian Harvey's site,
> that I translated into a few languages for comparison:
> http://lojic.com/blog/2007/08/31/logo-ruby-javascript
>
> I also translated it to Common Lisp (see below), but I'm not sure if
> using loop is the best approach. Also, printing a list of words as a
> space separated sentence seems cumbersome, so I expect there's an
> easier way.
I think the easiest way is this:
(loop for first in '("small" "medium" "large") do
(loop for second in '("vanilla" "ultra chocolate" "lychee"
"rum raisin" "ginger") do
(loop for third in '("cone" "cup") do
(format t "~a ~a ~a~%" first second third))))
but this is not in the spirit of the Logo program, which works for any
number of categories and items in each category. I think you mean something
like this:
(defun choices (list &optional sofar)
(destructuring-bind (first . rest) list
(if first
(loop for item in first do
(choices rest (cons item sofar)))
(format t "~{~A~#[~:; ~]~}~%" (reverse sofar)))))
(choices '(("small" "medium" "large")
("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
("cone" "cup")))
Note that you don't need to use "list" for building a list and that it is a
common idiom in Lisp to use "cons" and "reverse" (or nreverse) for building
a list, because it needs O(n) runtime, compared to O(n^2) with append.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Cesar Rabak
Subject: Re: choices sample Logo -> Lisp
Date:
Message-ID: <fbco3b$oi6$1@aioe.org>
Frank Buss escreveu:
> Brian Adkins wrote:
>
[snipped]
> but this is not in the spirit of the Logo program, which works for any
> number of categories and items in each category. I think you mean something
> like this:
>
> (defun choices (list &optional sofar)
> (destructuring-bind (first . rest) list
> (if first
> (loop for item in first do
> (choices rest (cons item sofar)))
> (format t "~{~A~#[~:; ~]~}~%" (reverse sofar)))))
>
>
> (choices '(("small" "medium" "large")
> ("vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
> ("cone" "cup")))
>
You need to protect destructuring-bind of attempting to destructure a
nil, don't you?
Cesar Rabak wrote:
> You need to protect destructuring-bind of attempting to destructure a
> nil, don't you?
I don't know. This is something I don't like in Common Lisp: If it works
with your implementation, you can't be sure that it is valid Common Lisp,
something which is nearly impossible e.g. for Java.
But I think it is valid: 3.4.4.1 in the CLHS says:
| Destructuring is the process of decomposing a compound object into its
| component parts, using an abbreviated, declarative syntax, rather than
| writing it out by hand using the primitive component-accessing functions.
I think "nil" is an object and when "writing it out by hand", I would use
car and cdr, which is defined for nil. But I didn't found something in the
CLHS, that destructuring lambda lists uses car and cdr, too.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <······························@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Cesar Rabak wrote:
>
> > You need to protect destructuring-bind of attempting to destructure a
> > nil, don't you?
>
> I don't know. This is something I don't like in Common Lisp: If it works
> with your implementation,
Did you try it?
If there is an error, then you should send a bug report.
> you can't be sure that it is valid Common Lisp,
> something which is nearly impossible e.g. for Java.
Why is it nearly impossible for Java?
>
> But I think it is valid: 3.4.4.1 in the CLHS says:
>
> | Destructuring is the process of decomposing a compound object into its
> | component parts, using an abbreviated, declarative syntax, rather than
> | writing it out by hand using the primitive component-accessing functions.
NIL is no compound object.
>
> I think "nil" is an object and when "writing it out by hand", I would use
> car and cdr, which is defined for nil. But I didn't found something in the
> CLHS, that destructuring lambda lists uses car and cdr, too.
--
http://lispm.dyndns.org
Rainer Joswig wrote:
>> I don't know. This is something I don't like in Common Lisp: If it works
>> with your implementation,
>
> Did you try it?
>
> If there is an error, then you should send a bug report.
It works with LispWorks. The problem is that I don't know, if it works in
all Common Lisp implementations. Should I send a bug report for LispWorks,
if it works in this implementation, but not in other implemenations?
>> you can't be sure that it is valid Common Lisp,
>> something which is nearly impossible e.g. for Java.
>
> Why is it nearly impossible for Java?
because there is nearly no undefined behaviour in Java. But there are more
than 200 pages in the CLHS which contains the word "undefined". Some
interesting ones:
(copy-list '#1=(1 . #1#))
(setf (elt (symbol-name 'cdr) 1) #\x)
(atan 0 0)
Java: Math.atan2(0,0)=0 is defined
(aref (make-array 10) 0)
Java: Elements of an array are always initialized
(defconstant +foo+ 1) (setf +foo+ 2)
Java: overwriting final variables causes a compile time error
>>| Destructuring is the process of decomposing a compound object into its
>>| component parts, using an abbreviated, declarative syntax, rather than
>>| writing it out by hand using the primitive component-accessing functions.
>
> NIL is no compound object.
I don't know, I can't find the definition of "compound object" in the CLHS.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <································@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Rainer Joswig wrote:
>
> >> I don't know. This is something I don't like in Common Lisp: If it works
> >> with your implementation,
> >
> > Did you try it?
> >
> > If there is an error, then you should send a bug report.
>
> It works with LispWorks.
Destructuring NIL works with LispWorks? Not for me.
CL-USER 23 > (let ((a nil)) (destructuring-bind (x . y) a (list x y)))
Error: NIL does not match (X . Y).
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
> The problem is that I don't know, if it works in
> all Common Lisp implementations. Should I send a bug report for LispWorks,
> if it works in this implementation, but not in other implemenations?
I would first assume that the implementation which shows different
bahaviour has a problem.
> >> you can't be sure that it is valid Common Lisp,
> >> something which is nearly impossible e.g. for Java.
> >
> > Why is it nearly impossible for Java?
>
> because there is nearly no undefined behaviour in Java. But there are more
> than 200 pages in the CLHS which contains the word "undefined". Some
> interesting ones:
>
> (copy-list '#1=(1 . #1#))
> (setf (elt (symbol-name 'cdr) 1) #\x)
>
> (atan 0 0)
> Java: Math.atan2(0,0)=0 is defined
>
> (aref (make-array 10) 0)
> Java: Elements of an array are always initialized
>
> (defconstant +foo+ 1) (setf +foo+ 2)
> Java: overwriting final variables causes a compile time error
Then try the same with library functions...
> >>| Destructuring is the process of decomposing a compound object into its
> >>| component parts, using an abbreviated, declarative syntax, rather than
> >>| writing it out by hand using the primitive component-accessing functions.
> >
> > NIL is no compound object.
>
> I don't know, I can't find the definition of "compound object" in the CLHS.
compound means 'zusammengesetzt' in German. Of what is NIL 'zusammengesetzt'?
--
http://lispm.dyndns.org
Rainer Joswig wrote:
> Destructuring NIL works with LispWorks? Not for me.
>
> CL-USER 23 > (let ((a nil)) (destructuring-bind (x . y) a (list x y)))
>
> Error: NIL does not match (X . Y).
> 1 (abort) Return to level 0.
> 2 Return to top loop level 0.
>
> Type :b for backtrace, :c <option number> to proceed, or :? for other options
Looks like there is different behaviour in compiled code and at the REPL.
At the REPL I can reproduce your behaviour with LispWorks 4.3.7, but when
compiling this function:
(defun test ()
(let ((a nil)) (destructuring-bind (x . y) a (list x y))))
it returns (NIL NIL). I assume the reason are different default safety
levels.
>>> Why is it nearly impossible for Java?
>
> Then try the same with library functions...
This is not much a problem, because most users use the Sun implementation.
But at least the language is more strict defined. Maybe in Lisp it is not
so easy, because of the strong connection between language and library
functions.
>> I don't know, I can't find the definition of "compound object" in the CLHS.
>
> compound means 'zusammengesetzt' in German. Of what is NIL 'zusammengesetzt'?
That's right, so common sense could lead to the conclusion, that NIL is not
a compound object. But in general the CLHS glossary is fairly comprehensive
and missing the definition for it was the reason why I thought "compound
object" is something for which "car" and "cdr" is defined. Otherwise it
would make no sense, because a function or an array could be a compound
object, too. With my idea, defining it with car and cdr, at least it
"should" signal a type-error (btw: how is "should" defined in the CLHS?
E.g. other standard documents define, what "should", "must have" etc.
means).
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <································@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Rainer Joswig wrote:
>
> > Destructuring NIL works with LispWorks? Not for me.
> >
> > CL-USER 23 > (let ((a nil)) (destructuring-bind (x . y) a (list x y)))
> >
> > Error: NIL does not match (X . Y).
> > 1 (abort) Return to level 0.
> > 2 Return to top loop level 0.
> >
> > Type :b for backtrace, :c <option number> to proceed, or :? for other options
>
> Looks like there is different behaviour in compiled code and at the REPL.
> At the REPL I can reproduce your behaviour with LispWorks 4.3.7, but when
> compiling this function:
>
> (defun test ()
> (let ((a nil)) (destructuring-bind (x . y) a (list x y))))
>
> it returns (NIL NIL). I assume the reason are different default safety
> levels.
Well, I almost never use SAFETY 1 or below. ;-)
But right, it depends on the SAFETY level.
I think that is unwanted and should be reported.
Even if it would be allowed by the HyperSpec (which I'm too
lazy to look up), I would not want to see NIL destructured
when SAFETY is 1 or below. OpenMCL, SBCL do it correctly
even for SPEED=3/SAFETY=0 combinations.
ACL is similar to LispWorks. I see this as totally unwanted.
If Implementations diverge in those basic things,
users should complain.
> >>> Why is it nearly impossible for Java?
> >
> > Then try the same with library functions...
>
> This is not much a problem, because most users use the Sun implementation.
> But at least the language is more strict defined. Maybe in Lisp it is not
> so easy, because of the strong connection between language and library
> functions.
>
> >> I don't know, I can't find the definition of "compound object" in the CLHS.
> >
> > compound means 'zusammengesetzt' in German. Of what is NIL 'zusammengesetzt'?
>
> That's right, so common sense could lead to the conclusion, that NIL is not
> a compound object. But in general the CLHS glossary is fairly comprehensive
> and missing the definition for it was the reason why I thought "compound
> object" is something for which "car" and "cdr" is defined. Otherwise it
> would make no sense, because a function or an array could be a compound
> object, too. With my idea, defining it with car and cdr, at least it
> "should" signal a type-error (btw: how is "should" defined in the CLHS?
> E.g. other standard documents define, what "should", "must have" etc.
> means).
--
http://lispm.dyndns.org
In article <····························@news-europe.giganews.com>,
Rainer Joswig <······@lisp.de> wrote:
> In article <································@40tude.net>,
> Frank Buss <··@frank-buss.de> wrote:
>
> > Rainer Joswig wrote:
> >
> > > Destructuring NIL works with LispWorks? Not for me.
> > >
> > > CL-USER 23 > (let ((a nil)) (destructuring-bind (x . y) a (list x y)))
> > >
> > > Error: NIL does not match (X . Y).
> > > 1 (abort) Return to level 0.
> > > 2 Return to top loop level 0.
> > >
> > > Type :b for backtrace, :c <option number> to proceed, or :? for other options
> >
> > Looks like there is different behaviour in compiled code and at the REPL.
> > At the REPL I can reproduce your behaviour with LispWorks 4.3.7, but when
> > compiling this function:
> >
> > (defun test ()
> > (let ((a nil)) (destructuring-bind (x . y) a (list x y))))
> >
> > it returns (NIL NIL). I assume the reason are different default safety
> > levels.
>
> Well, I almost never use SAFETY 1 or below. ;-)
>
>
> But right, it depends on the SAFETY level.
>
> I think that is unwanted and should be reported.
> Even if it would be allowed by the HyperSpec (which I'm too
> lazy to look up), I would not want to see NIL destructured
> when SAFETY is 1 or below. OpenMCL, SBCL do it correctly
> even for SPEED=3/SAFETY=0 combinations.
> ACL is similar to LispWorks. I see this as totally unwanted.
>
> If Implementations diverge in those basic things,
> users should complain.
It is allowed by ANSI CL. But I think it is very ugly...
>
>
>
> > >>> Why is it nearly impossible for Java?
> > >
> > > Then try the same with library functions...
> >
> > This is not much a problem, because most users use the Sun implementation.
> > But at least the language is more strict defined. Maybe in Lisp it is not
> > so easy, because of the strong connection between language and library
> > functions.
> >
> > >> I don't know, I can't find the definition of "compound object" in the CLHS.
> > >
> > > compound means 'zusammengesetzt' in German. Of what is NIL 'zusammengesetzt'?
> >
> > That's right, so common sense could lead to the conclusion, that NIL is not
> > a compound object. But in general the CLHS glossary is fairly comprehensive
> > and missing the definition for it was the reason why I thought "compound
> > object" is something for which "car" and "cdr" is defined. Otherwise it
> > would make no sense, because a function or an array could be a compound
> > object, too. With my idea, defining it with car and cdr, at least it
> > "should" signal a type-error (btw: how is "should" defined in the CLHS?
> > E.g. other standard documents define, what "should", "must have" etc.
> > means).
--
http://lispm.dyndns.org
Rainer Joswig wrote:
> It is allowed by ANSI CL. But I think it is very ugly...
I think it is nice. The description at 3.4.4.1 says, it works like if you
would use primitive functions. As I wrote, I would use CAR and CDR, which
would work.
Where did you find that it is allowed with ANSI CL? Is the ANSI standard
more detailed than the CLHS? I've used this document:
http://www.lisp.org/HyperSpec/FrontMatter/index.html
And if it is allowed, is it mandatory and thus a bug in LispWorks and other
Lisp implementations?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <······························@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Rainer Joswig wrote:
>
> > It is allowed by ANSI CL. But I think it is very ugly...
>
> I think it is nice. The description at 3.4.4.1 says,
That one applies to macro lambda lists, not destructuring-bind..
> it works like if you
> would use primitive functions. As I wrote, I would use CAR and CDR, which
> would work.
But the standard defines another behavior. The pattern (a . b) does not destructure ().
Which I think is right.
http://www.lisp.org/HyperSpec/Body/mac_destructuring-bind.html#destructuring-bind
"If the result of evaluating the expression does not match the destructuring pattern, an error of type error should be signaled."
This means that destructuring () with the pattern (a . b) is an ERROR, but see below.
http://www.lisp.org/HyperSpec/Body/sec_1-4-2.html
"An error should be signaled"
"This means that an error is signaled in safe code, and an error might be signaled in unsafe code.
Conforming code may rely on the fact that the error is signaled in safe code. Every implementation
is required to detect the error at least in safe code. When the error is not signaled, the ``consequences are undefined''
(see below). For example, ``+ should signal an error of type type-error if any
argument is not of type number.''"
Which says in unsafe code implementations are not required to signal an error and
consequences are undefined. That A and B in the pattern are bound to NIL
is just arbitrary. They could be bound to 42 or anything else. The program can
also crash.
I think such 'library' functions like DESTRUCTURING-BIND should not introduce an
safety problems or different behavior depending on the SAFETY declaration.
I also think users should be aware that the default mode for running Lisp
code should be the safe code. Low safety should only be declared where
it is really needed.
>
> Where did you find that it is allowed with ANSI CL? Is the ANSI standard
> more detailed than the CLHS? I've used this document:
>
> http://www.lisp.org/HyperSpec/FrontMatter/index.html
>
> And if it is allowed, is it mandatory and thus a bug in LispWorks and other
> Lisp implementations?
--
http://lispm.dyndns.org
Rainer Joswig wrote:
>> I think it is nice. The description at 3.4.4.1 says,
>
> That one applies to macro lambda lists, not destructuring-bind..
The reason why I cited 3.4.4.1 was, that the DESTRUCTURING-BIND page says
"The lambda-list supports destructuring as described in Section 3.4.5
(Destructuring Lambda Lists).". And at this page is written "Destructuring
lambda lists are closely related to macro lambda lists; see Section 3.4.4
(Macro Lambda Lists).". At this page there is a link to "3.4.4.1
Destructuring by Lambda Lists".
> But the standard defines another behavior. The pattern (a . b) does not destructure ().
> Which I think is right.
>
> http://www.lisp.org/HyperSpec/Body/mac_destructuring-bind.html#destructuring-bind
>
> "If the result of evaluating the expression does not match the destructuring pattern, an error of type error should be signaled."
I don't think that this would explain it, but after searching a bit more,
I've found the definition of "compound object":
http://www.lisp.org/HyperSpec/Body/syscla_cons.html
| A cons is a compound object having two components, called the car and cdr.
Assuming that the other direction of this defintion is valid, too (every
compound object is a cons), and (CONSP NIL) is NIL, we have the prove that
NIL is not allowed for destructuring-bind :-)
Would be nice to have a more formal definition of Common Lisp. Maybe it
could be written in the form of asserts, post-conditions and implementation
example code for every function, or in a mathematical form?
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <······························@40tude.net>,
Frank Buss <··@frank-buss.de> wrote:
> Rainer Joswig wrote:
>
> >> I think it is nice. The description at 3.4.4.1 says,
> >
> > That one applies to macro lambda lists, not destructuring-bind..
>
> The reason why I cited 3.4.4.1 was, that the DESTRUCTURING-BIND page says
> "The lambda-list supports destructuring as described in Section 3.4.5
> (Destructuring Lambda Lists).". And at this page is written "Destructuring
> lambda lists are closely related to macro lambda lists; see Section 3.4.4
> (Macro Lambda Lists).". At this page there is a link to "3.4.4.1
> Destructuring by Lambda Lists".
>
> > But the standard defines another behavior. The pattern (a . b) does not destructure ().
> > Which I think is right.
> >
> > http://www.lisp.org/HyperSpec/Body/mac_destructuring-bind.html#destructuring-bind
> >
> > "If the result of evaluating the expression does not match the destructuring pattern, an error of type error should be signaled."
>
> I don't think that this would explain it, but after searching a bit more,
> I've found the definition of "compound object":
>
> http://www.lisp.org/HyperSpec/Body/syscla_cons.html
>
> | A cons is a compound object having two components, called the car and cdr.
>
> Assuming that the other direction of this defintion is valid,
> too (every compound object is a cons), and (CONSP NIL) is NIL, we have the prove that
> NIL is not allowed for destructuring-bind :-)
(a . b) describes a cons with two parts, a compound object. NIL is not a CONS.
NIL is also not a compound object.
http://www.lisp.org/HyperSpec/Body/syscla_null.html
So NIL can't be destructured by (a . b).
>
> Would be nice to have a more formal definition of Common Lisp. Maybe it
> could be written in the form of asserts, post-conditions and implementation
> example code for every function, or in a mathematical form?
Sure, have a go.
But I would just step back a bit. destructuring NIL to arbitrary datastructures makes no sense.
Destructuring some FOO with (a . b) should involve THREE steps:
1) (CONSP FOO) ?
2) (FIRST FOO) -> A
3) (REST FOO) -> B
NIL fails already at step one.
--
http://lispm.dyndns.org
Frank Buss <··@frank-buss.de> writes:
> Would be nice to have a more formal definition of Common Lisp. Maybe it
> could be written in the form of asserts, post-conditions and implementation
> example code for every function, or in a mathematical form?
For what it's worth, it was a conscious decision not to do this with
CL. As is common with things done for allegedly good reasons, some
people like the reasons and some people don't. Life's full of
trade-offs. But the issues were...
Creating a set of asserts, post-conditions, etc. means that the same
text either can't be written in English or if it is written in
English, might potentially diverge. As it is, the text is sometimes
in error. If the error is in English, people are quite forgiving.
There is text that is simply wrong, and everyone knows it, and it
works ok. (If that text were in formalese, I don't know that they
would have. There's something forbidding about formalese that makes
people not want to ignore it, but merely to bow to it, as if it were
their master.) But regardless of how forgiving people are, the mere
fact that a fact could be independently and divergently stated means
that a non-self-consistent document could have problems figuring out
which part of it was right. A war between formalists and
non-formalists could occur, and probably the formalists would assert
dominance, rendering the easily understood text useless. (A similar
problem is typically confronted in legal documents, and while the
Creative Commons and FSF have struggled to overcome it, it's a
non-trivial problem and I don't know what success they've had in life
and in courts. It's probably fair to say, though, that the solutions
offered in those realms are neither "trivial" nor "obviously without
potential headache".)
My recollection is that ANSI was quite worried about there being both
a hardcopy document and any form of online copy, fearing that if there
were and if some difference in presentation occurred, no one would
know which presentation represented the True Standard. So I'm pretty
sure this issue of "what to trust if a discrepancy arises" was not
imagined, but a real, expressed concern of the community (at least the
standards community, if not the Lisp community) at the time.
So we set about to make a document that was modular, removing multiple
references to the same fact, and trying to pare it down to saying
things in only one place. It wasn't done fully, due to budget, but it
was a known problem with CLTL that it had places that were messy and
seemingly conflicting, so we were trying to work away from that.
And, finally, to me, the most important issue was that the standard BE
accessible to regular people, as a part of the language's outreach.
Not tutorial, which is too hard, but certainly readable by ordinary
people and possible to understand, so they could not feel beholden to
the keepers of denotational semantics to learn the truth. This would
have disengaged a large population of users and put the standard out
of their reach to use as a first-order reference. You can make up
your own mind on this, but I personally regard the standard as a
strong success in this regard.
To be clear: I don't see any reason that someone can't create a
semantics as an outboard, free-standing document if they want, just as
they can define implementations. Implementations can take positions on
meaning, and disagree with one another, but they cannot change the standard.
It's like deciding what the US flag or Constitution stands for.
People disagree a lot about that. But the flag is still the flag, and
the Constitution is still the Constitution. I don't think a formally
codified statement of what they really mean would fix things.
And so telling everyone that a formal semantics for CL was, in fact,
the definition of the language would be to deny reality and would
really be an attempt to create two standards, with the potential for
them to disagree as to who was right, who was in power, etc.
Or such is my personal opinion, for what that's worth. None of my
statements above are formal representations of any organizational
opinion.
Brian Adkins wrote:
> I came across a small Logo example function on Brian Harvey's site,
> that I translated into a few languages for comparison:
> http://lojic.com/blog/2007/08/31/logo-ruby-javascript
BTW: if you like short solutions, which looks more like a mathematical
description of the problem and which doesn't bother with implementation
details how to solve it, you should try Haskell:
choices [] = [[]]
choices (x:xs) = [ item:list | item <- x, list <- (choices xs) ]
This returns a list of lists. To display it a bit nicer, we can define this
function (which I'm sure could be written nicer, maybe someone on the
Haskell newsgroup knows how)
showLists = putStr . unlines . map (foldl1 (\x y->x ++ " " ++ y))
Usage:
showLists [["foo", "bar"], ["baz"]]
foo bar
baz
We can use it like this:
showLists $ choices [["small", "medium", "large"],
["vanilla", "ultra chocolate", "lychee",
"rum raisin", "ginger"],
["cone", "cup"]]
small vanilla cone
small vanilla cup
small ultra chocolate cone
small ultra chocolate cup
small lychee cone
small lychee cup
small rum raisin cone
small rum raisin cup
small ginger cone
small ginger cup
medium vanilla cone
medium vanilla cup
medium ultra chocolate cone
medium ultra chocolate cup
medium lychee cone
medium lychee cup
medium rum raisin cone
medium rum raisin cup
medium ginger cone
medium ginger cup
large vanilla cone
large vanilla cup
large ultra chocolate cone
large ultra chocolate cup
large lychee cone
large lychee cup
large rum raisin cone
large rum raisin cup
large ginger cone
large ginger cup
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
In article <························@y42g2000hsy.googlegroups.com>,
Brian Adkins <···········@gmail.com> wrote:
> I came across a small Logo example function on Brian Harvey's site,
> that I translated into a few languages for comparison:
> http://lojic.com/blog/2007/08/31/logo-ruby-javascript
>
> I also translated it to Common Lisp (see below), but I'm not sure if
> using loop is the best approach. Also, printing a list of words as a
> space separated sentence seems cumbersome, so I expect there's an
> easier way.
>
> The original Logo program with output is here: http://www.cs.berkeley.edu/~bh/logo-sample.html
>
> Any ideas to express this better in CL?
Here is a version written in COMMON LISP:
(DEFUN CHOICES (LIST)
(IF (NULL LIST)
(LIST (LIST))
(MAPCAN (LAMBDA (X) (MAPCAR (LAMBDA (Y) (CONS X Y)) (CHOICES (CDR LIST)))) (CAR LIST))))
(PPRINT (CHOICES '((SMALL MEDIUM LARGE)
(VANILLA |ULTRA CHOCOLATE| LYCHEE |RUM RAISIN| GINGER)
(CONE CUP))))
>
> (defun print-choice (lst)
> (loop for i in lst do (format t "~a " i))
> (format t "~%"))
>
> (defun choices (menu sofar)
> (cond
> (menu
> (loop for i in (car menu) do (choices (cdr menu) (append sofar
> (list i)))))
> (t
> (print-choice sofar))))
>
> (choices (list
> (list "small" "medium" "large")
> (list "vanilla" "ultra chocolate" "lychee" "rum raisin"
> "ginger")
> (list "cone" "cup")) '())
>
> Thanks,
> Brian Adkins
>
> --
> http://lojic.com/blog/
Brian Adkins <···········@gmail.com> writes:
> I came across a small Logo example function on Brian Harvey's site,
> that I translated into a few languages for comparison:
> http://lojic.com/blog/2007/08/31/logo-ruby-javascript
>
> I also translated it to Common Lisp (see below), but I'm not sure if
> using loop is the best approach. Also, printing a list of words as a
> space separated sentence seems cumbersome, so I expect there's an
> easier way.
>
> The original Logo program with output is here: http://www.cs.berkeley.edu/~bh/logo-sample.html
>
> Any ideas to express this better in CL?
>
> (defun print-choice (lst)
> (loop for i in lst do (format t "~a " i))
> (format t "~%"))
;; This is actually so simple it is hardly worth a separate function:
(defun print-choice (choice-list)
(format t "~{~a~^ ~}~%" choice-list))
Other solutions to the other parts have been posted by others.
--
Thomas A. Russ, USC/Information Sciences Institute
On Sep 4, 1:06 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> Brian Adkins <···········@gmail.com> writes:
> ;; This is actually so simple it is hardly worth a separate function:
>
> (defun print-choice (choice-list)
> (format t "~{~a~^ ~}~%" choice-list))
Thanks, and I agree that in this context, a separate function isn't
necessary. I also discovered &optional, so the final version is:
(defun choices (menu &optional (sofar '()))
(if menu
(dolist (i (car menu))
(choices (cdr menu) (append sofar (list i))))
(format t "~{~a~^ ~}~%" sofar)))
(choices (list
(list "small" "medium" "large")
(list "vanilla" "ultra chocolate" "lychee" "rum raisin" "ginger")
(list "cone" "cup")))
With that, I think the Common Lisp version is among the top
aesthetically pleasing versions among the 10 languages on my blog
article.
http://lojic.com/blog/2007/08/31/logo-ruby-javascript
I need to go study format now.
Brian Adkins <···········@gmail.com> writes:
> I also discovered &optional, so the final version is:
>
> (defun choices (menu &optional (sofar '()))
> (if menu
> (dolist (i (car menu))
> (choices (cdr menu) (append sofar (list i))))
> (format t "~{~a~^ ~}~%" sofar)))
And if you want to improve the efficiency for longer lists, then using
the idiom (do they call them design patterns now?) of consing onto the
front of the list and reversing instead of appending, which I recall
someone else used.
(defun choices (menu &optional (sofar '()))
;; This builds up the list in reverse order and then reverses the
;; result just before printing. Can't use NREVERSE because SOFAR is
;; shared among many branches.
(if menu
(dolist (i (car menu))
(choices (cdr menu) (cons i sofar)))
(format t "~{~a~^ ~}~%" (reverse sofar))))
--
Thomas A. Russ, USC/Information Sciences Institute