Prev: discount, DSQUARED ,clothing ( paypal accept ) ( www.sneaker-fan.com ) discount, LRG ,clothing ( paypal accept ) ( www.sneaker-fan.com )
Next: please help me about path names.
From: Robert Maas, http://tinyurl.com/uh3t on 13 Apr 2008 21:47
> >> a 10-line recursive BFS
> > I assume you mean breadth-first search (in some sort of tree,
> > possibly binary)?
> From: vanekl <va...(a)acd.net>
> Nope, I mean DFS. I misspoke.

Oh..... nevermind.

Depth-first search is obviously recursive, assuming you don't
suffer stack overflow in which case you might emulate a stack using
a linked list.

> > While a depth-first search is nicely expressed recursively, since
> > the algorithm itself is essentially last-in first-out, hence
> > stack-like, hence recursive-like, a breadth-first search is
> > inherently first-in first-out, like a queue, not at all stack-like
> > or recursive-like.
> > It seems that a iterative loop of appending
> > newly-discovered branches at the end of the queue and popping the
> > next task-to-do off the front of the queue is the best way to
> > expresss the algorithm. Why even bother trying to emulate a queue
> > via some sort of recursion?
> Because it's simple, can be easily understood, and works.

To my mind, a queue is simple easily understood and works, and is
"obviously just right" for any fifo task such as breadth-first
search (the topic we accidently got on when you misspoke).

> Seem like pretty good ideas to me, especially when you are
> discussing code that you would like newbies to understand.

I disagree. We should show newbies what kinds of tasks just
naturally fit into iterative paradigms, and which fit just
naturally into recursive paradigms, and only later show how either
can emulate the other via tricky or nifty coding.

> You seem to think queues are easier to understand.

No, I think using queues for fifo tasks (such as BFS and
queue-at-bank), and using stacks for lifo tasks (such as DFS and
EVAL), are easier to understand than vice versa.

> From my experience, once you get over the hurdle of recursion,
> recursive code is quicker to understand, shorter, and less bug
> prone.

I disagree with such a general claim.

> Why even bother with possible efficiency issues at this point in
> the newbie's process of discovery?

That's a strawman. The issues are (1) fitting the most obviously
appropriate algorithm to the task at hand, and (2) avoiding really
dumb things that require immense amounts of pre-allocated
contiguous stack space that can't be recycled for any other use
until the application quits.

> ftp/pub/techreports/99-1.ps.gz+recursive+BFS&hl=en&ct=clnk&cd=3&gl=us&ie=UTF-8

Alert: Unable to access document.

> TCONC isn't a part of CL, nor do I think this is newbie "territory."
> You appear to differ.

Nothing beyond the ANSI spec is "part of CL". The second thing the
newbie needs to learn is how to write useful tools that go beyond
what's in the ANSI spec, and IMO implementing a fifo queue via
TCONC is a useful exercise for the newbie and a useful tool for
later use. I almost wish I had gone the TCONC way in my code.
Instead I push results onto a local variable called revres then
nreverse that at the return point. Maybe I'll copy the TCONC code I
posted into a utility file and use it from now on.

> So you're saying that CONS should be deprecated for newbies.

Absolutely not!! (Although perhaps a renaming of it should occur,
such as MAKE-PAIR or NEW-PAIR. After all, CONS is really a
constructor for an ordered pair data-object, and MAKE-whatever is
the usual convention in Common Lisp, such as MAKE-ARRAY
MAKE-HASH-TABLE MAKE-LIST MAKE-STRING MAKE-STRING-OUTPUT-STREAM
etc. It might be easire for a newbie to remember that MAKE-PAIR is
the way to make a new pair-object, instead of the special-case name
CONS that is a carry-over from when such pairs were the *only*
structures ever built in Lisp 1.5 or whatever so "construct what?"
wasn't a reasonble question.)

> While I agree your earnest attempt at optimizing algorithms is
> proper and even notable in some contexts, I believe, in the
> context of the premise of this discussion, you are beyond the pale.

There's a difference between what I advocate, namely choosing an
algorithm that naturally fits the task to be accomplished, which
isn't horribly inefficient, vs. micro-optimizing too early, which
is *not* what I advocate.

> > Try something like this instead, to implement a fifo queue:
> > (defun make-empty-tconc () (cons nil nil))
> > (defun is-empty-tconc (tc) (null (car tc)))
> > (defun append-tconc (tc el)
> > (let ((newcell (cons el nil)))
> > (cond ((is-empty-tconc tc) (setf (car tc) newcell) (setf (cdr tc) newcell))
> > (t (setf (cdr (cdr tc)) newcell) (setf (cdr tc) newcell)))))
> > (defun pop-tconc (tc) ;To get elements out one by one
> > (let ((popped (car (car tc))))
> > (setf (car tc) (cdr (car tc)))
> > (if (is-empty-tconc tc) (setf (cdr tc) nil))
> > popped))
> > (defun see-all-tconc (tc) ;To get list of all remaining elements at once
> > (car tc))
> > The TCONC object as defined above can be used both to visit nodes
> > in fifo sequence per breadth-first search (using append-tconc and
> > pop-tconc repeatedly), and to build up the final list of nodes to
> > return from the top level (using append-tconc repeatedly and
> > see-all-tconc just once at the return point).
> > (BBN/UCI Lisp had a slightly different naming convention for
> > essentially the same functionality.)
> Interesting, but I submit it is not something important enough that
> a newbie should be first exposed to.

In nearly any course in computer programming, one of the chapters
is API and specific commonly-useful examples: Stack, Queue, Binary
Search Tree (usually AVL), etc. I agree with the designers of those
courses that these examples are useful for teaching both the basic
idea of an API and the general idea of how to write decent
algorithms for commonly-useful kinds of tasks. Since Lisp has a
stack (lifo) API available already via PUSH and POP, or trivially
implementable via CONS and CAR/CDR, but doesn't have any queue
(fifo) API either directly avaiable nor trivially implementable, I
suggest that implementing a fifo queue in Lisp would be a useful
exercise to show how to build a slightly non-trivial API. In that
context, TCONC is one reasonable design for such an API. Two stacks
is another reasonable design. Maybe the student should be taught
both APIs, and any other fifo-queue API you would suggest, after
perhaps an in-class brainstorming exercise to see if any of the
students can invent a fifo-queue API all on their own.

So do you disagree that a course on algorithms should include the
queue API, or do you disagree that TCONC is a reasonble example of
how such an API might be implemented, to show that there's more
than one simple way to implement it, to give the students the clear
idea that there isn't just one way, that there are radically
different ways?

(snipped example of divide-in-half recursive algorithm for
computing maximum of a set)

> Now your disagreeing not because the algorithm is sound, but
> because you would rather have one that is more easily
> parallelizable. You continue to amaze me. I thought the entire
> premise for this collection of koans was for newbie education.

I think there are several issues, in addition to how to get the job
done on a single CPU Von Neumann machine with unlimited memory. One
issue is dealing with limited address space, especially causing
limited stack. Another issue is locality of reference, if there's
large address space but limited actual memory. Another issue is
dealing with multi-processing with shared structures that get
independently updated where the updates *are* or are *not* supposed
to be communicated between processes. A related issue is dealing
with multiple CPUs, especially a large number of CPUs all availble
to help share the workload to speed up processing a large amount of
data. I think some discussion of such topics is relevant to what a
newbie should learn about at some point.

> >> Example of clear, concise Lispy style:
> >> [From "Tutorial on Good Lisp Programming Style"]
> >> (defun count-all-numbers (exp)
> >> (typecase exp
> >> (cons
> >> (+ (count-all-numbers (first exp))
> >> (count-all-numbers (rest exp))))
> >> (number 1)
> >> (t 0)))
> > Minor quibble: The use of "first" and "rest" implies the
> > *intention* is nested lists, *not* arbitrary CONS trees.
> Yeah, and this distinction is important for newbs. </sarcasm>
> As if CAR and CDR are easier for newbies to grok.

IMO it's important for naming conventions to closely match the
intent of the API. Sometimes you really want to define a function
or macro that does nothing except change the name of some obscure
thing to more directly fit the context where you're using it. I do
not claim that the specific names CAR and CDR are optimal, merely
that they clearly indicate the intention of working directly with
arbitrary trees of CONS cells rather than restricting oneself to
nested proper lists as "first" and "rest" imply.

> They're /synonyms/, FCS.

Yeah, and CONS is a synomym for MAKE-HIST-CELL,
and CAR is a synomym for HIST-CELL-TOKEN,
and CDR is a synomym for HIST-CELL-COUNT.
But when you're writing lots of code to deal with cells in
histograms, if you use the histogram-cell-API names instead of the
CONS/CAR/CDR names you can mostly forget the internal
representation of histogram cells and just use the more descriptive
names instead.

> The *intention* is not conveyed by the language, per se,
> but how the language (e.g., the operators) is commonly used
> depending on context.

That point is debatable. When you write an API for some specific
data structure that has certain operations publicized as "proper"
for that structure, you give names that make sense for that API,
even if some of them are nothing more than synonyms for built-in
functions such as CADDR. Then when you write good code in the sense
of making sense to anyone reading it, you use these API names for
all the "proper" operations, rather than occasionally sneak in the
CADDR etc. low-level equivalents. Every time you use one of the API
functions, you are clearly showing anyone reading your code that
the *intent* is to perform a "proper" operation on an object of
this type as defined by the API.

I think a useful exercise for newbies would be to implement a
totally trivial API. For example, build&use records of the form
(givenName:string familyName:string yearBorn:integer)
and simply define a constructor and three accessors and three
setters, each with reasonable names per this specific structure of
data, first as functions, then as macros. Maybe even do it as
lists, as vectors, and as structs, to show how the same API can be
implemented multiple ways. By having the API be totally trivial,
the student can concentrate on the API itself without being
distracted by the difficulty of getting a complicated algorithm
working.

> Again, not important for newbs IMO. In fact, some newbies that
> I've talked to specifically mention that they find the CAR and
> CDR operators distasteful.

Show them how easy it is to define their own operators for both
the tree API
(something like MAKE-PAIR PAIR-LEFT PAIR-RIGHT)
and the nested-list API
(something like LIST-PREPEND-ELEMENT LIST-FIRST-ELEMENT REST-OF-LIST)
let them make up any names they will be comfortable with for these
two different *intentions* of using CONS to build structures looked
at in two different ways (as symmetric left/right, or as assymetric
firstElement/restOfListAfterFirstElement).

> Even after I mention that they never have to be used, they still
> are turned off by them.

You could always provide them with an init.lisp file which defines
aliases for both the symmetric-pair and element/rest intentions,
and teach the two APIs totally separately, as if they didn't really
use the same internal form. Whenever they want to create a literal
value per the symmetric-pair intention, they must strictly use
dotted notation, no list-shorthands allowed. Whenever they want to
create a literal list or nested lists, they must strictly use
non-dotted list notation, and they're forbidden from using any dots
at all, not dotted lists allowed. You could even provide toString
functions for each intention, which would either use strictly
dotted notation or strictly proper-list notation. So your students
wouldn't need to see CAR or CDR or CONS even once (unless they peek
at how you implemented your two APIs in your init.lisp file).

> > Yet the
> > code works with arbitrary CONS trees. CAR and CDR should be used
> > instead of FIRST and REST if the intention is to work with
> > arbitrary CONS trees.
> > If exp is (5 . 9), should it count one number or two numbers??
> Yes, the doc string is not explicit. Got me there :)

So, you gonna fix the doc string before you post that code again?

> >> SORT has to be handled with care, even if it is destructive.
> >> If you want to sort a list, you have to use the result of SORT.
> >> Wont give a newbie the expected result:
> >> (let ((mylist (list "c" "d" "a")))
> >> (sort mylist #'string<)
> >> mylist)
> > Yeah, this is a specific lesson about a specific
> > possibly-destructive function whose *result* rather than
> > side-effect is the *correct* result.
> Considering how often sort is used, even though it is minor
> lesson, it is still important, especially since it almost
> certainly will eventually bite the newb on the @ss.

I agree that at the point where SORT is presented, this point
should be made clear. The manuals that I use makes this point
clear. Perhaps in new online manuals there also should be an
appendix that lists *all* the built-in functions that are
destructive in such a way that their return value is the only
result you can rely on after the function is called. Each
definition of a particular function could have a footnote linking
to the appendix.

Let me check if the HyperSpec is like that ...
<http://www.lispworks.com/documentation/HyperSpec/Body/f_sort_.htm>
No, it's not. It has a link to a section about destructive
operations, but that section merely tells about avoiding modifying
a literal, and unpredictable behaviour if there's a transfer of
control out from the middle of a destructive operation. There's no
mention of the structure hanging from the original pointer *not*
being identical to the returned value, or indeed *not* being
anything reasonable whatsoever, in the case of sorting a list.
Maybe Kent can fix that to do what I recommend?

> >> Better:
> >> (let ((mylist (list "c" "d" "a")))
> >> (setq mylist (sort mylist #'string<))
> >> mylist)
> > Yes, but slightly inefficient compared to:
> > (let ((mylist (list "c" "d" "a")))
> > (setq mylist (sort mylist #'string<)))
> > because after all the return value from SETQ is the value that was assigned,
> > unlike defconstant whose return value is the symbol being assigned.
> Efficiency was not my prime motivation. Pedagogical value was.

Yeah. I suggest you make your newbie point about how you need to
return the value from the SETQ rather than the original given
argument. I.e. *not* do this:
(let* ((origlist (list "c" "d" "a")))
(sortedlist (sort origlist #'string<)))
origlist)
but do this instead:
(let* ((origlist (list "c" "d" "a")))
(sortedlist (sort origlist #'string<)))
sortedlist)
and don't even try to return both original and sorted list like this:
(let* ((origlist (list "c" "d" "a")))
(sortedlist (sort mylist #'string<)))
(values sortedlist origlist))
I like that way of having parallel examples.
Then after that main point is given, note how origlist is used in
only one places, so it needn't be assigned a named variable, it can
just be nested inside the call to sort:
(let* ((sortedlist (sort (list "c" "d" "a") #'string<)))
sortedlist)
Then note that sortedlist is used in only one place, so likewise
it needn't be assigned to a named variable:
(sort (list "c" "d" "a") #'string<)

P.S., if you've perhaps noticed, I like to debug in a PROG where
each line of code assigns a new variable, then later refactor the
syntax to get rid of some of the local variables by nesting
expressions if I feel like doing that, and convert the whole PROG
to LET* or some other nifty form if it's easy. What I like about
PROG is how it allows a sequence of statements to be listed all at
the same level of structure, and unlike LET* it allows an intermix
of SETQ and MULTIPLE-VALUE-SETQ which LET* doesn't currently
support.

A few days ago somebody suggested an extension of the LET* syntax
to support multiple values, which I rather like, and if implemented
would allow me to get rid of almost *all* my PROGs:
(LET** ((q r (rem x y)))
(format t "~D divided by ~D gives ~D with remainder ~D~%" x y q r))
(I introduced the second asterisk myself just now.)
Maybe someday I'll implement that as a macro and submit it to some
public repository of freely-usable code?
(Or maybe somebody with more free time will do it before I get around to it?)

> Did you notice the symmetry between the two examples? They were
> like that for a reason: it's easier to draw conclusions this way.

OK. See my alternate parallel structure using LET* which might
illustrate all the points slightly better?

> a good compiler could peephole optimize that last "mylist" out
> anyway.

Agreed. I think newbies should be shown how to write the same
algorithm with a named variable at every step (for ease in
debugging) and with all single-use values passed by nested
expresssions to avoid the need for named variables to temporarily
hold the value (for compactness), and be allowed to use whatever
combination between the two extremes they feel like using on any
given day for any given task, and be encouraged to use cut&paste to
refactor the syntax of such algorithms any time they feel like it.

Example:

Easy-to-debug one-line-at-a-time version:
(defun phvec-euclidean-diagonal (phvec)
(prog (squares sumsq diag)
(setq squares (mapcar #'(lambda (num) (* num num)) phvec))
(setq sumsq (reduce #'+ squares))
(setq diag (sqrt sumsq))
(return diag)))

Compactified version (beginners hate all these parens):
(defun phvec-euclidean-diagonal (phvec)
(sqrt (reduce #'+ (mapcar #'(lambda (num) (* num num)) phvec)))))

Completely rewritten version using LOOP with SUM also possible.

> >> And last, I would stay away from mentioning the eval operator.
> > Actually, when developing code line-at-a-time, which is the way I
> > strongly prefer in most cases, the REP is your biggest tool, and
> > EVAL really needs to be mentionned.
> Evaluation could be mentioned as apart of the REPL. The EVAL
> /operator/ doesn't. Two separate, but related concepts.

OK, for absolute newbies we are in complete agreement.
(Eventually EVAL as an explicit operator in code turns out to be
occasionally useful, but only after uses of FUNCALL and APPLY are
exhausted. I presume we're in agreement there too.)

> > Better to get
> > familiar with APPLY and FUNCALL rather than "consing up an
> > expression to pass to EVAL". Perhaps lots of examples of where
> > APPLY or FUNCALL is useful, would be a good tutorial, so the idea
> > of needing to explicitly call EVAL never arises in the first place.
> Yes, I showed an example of this already. See above (/\cfuncall/).

OK, we're in agreement. (I didn't happen to notice the cfuncall section.)

> ... newbies ... tend to look for the biggest hammer first, and
> showing them EVAL, IMO, is not helpful.

I think I see your point. Although mentionning EVAL in the context
of the read-eval-print loop might be useful early-on, the EVAL
operator mentionned explicitly as something anyone might put into
actual code is poison to the newbie's mind. Maybe instead of
Read-Eval-Print, the REP should be described as
Parse-Compute-Print. If they never hear about any function called
"EVAL", they won't be tempted to play with it in their code, and
they won't get the misguided idea that the big hammar EVAL is
better than the delicate tools FUNCALL and APPLY.

But I have an even better idea I thought of a year or two ago which
I haven't implemented yet but might "any time now", in conjunction
with my CookBook examples: I could set up a Web service that taught
how to compose D/P algorithms without any reference to any
particular programming language whatsoever. The main window would
allow browsing of data types, and within each data type browsing
the various useful functions commonly provided in programming
languages, with *descriptions* of functionality rather than names
of functions. The student would choose a desired functionality,
assign his/her personal name to it (which the CAI system would
remember), and query as to what parameters to pass to it, either
literal values (numbers or strings only) or previously-assigned
variables, and ask for a variable name to assign to the result (the
default is a GENSYMmed name). The student could build up sequences
of actions, and eventually collect them into a function, with the
student choosing the name of the function. There'd be a fast-browse
menu of all the functionalities the student has already used, as
well as a fast-browse menu of all the variable-value bindings the
student has previously set up. At any time the student could see
what a single line of code, or a completed function definition,
would look like in any of six or seven programming languages (PHP,
Perl, Lisp, C, C++, Java maybe also FlamingThunder), but just for
curiosity, not as anything needed for further work in the course.

For functions that return multiple values, the student would pick
more than one variable name, or get GENSYMed names for all the
ones not explicitly named. Perhaps the GENSYMed names would follow
a variation of the MacSyma convention.
Single value: D1
Single value: D2
Multiple values: D3, D3a
Single value: D4
Multiple values: D5, D5a, D5b

This would almost completely get rid of the need to teach a
*programming*language* right alongside teaching
*how*to*design*algorithms*, hence the need to **choose** which
programming language to *teach*. Instead only
*how*to*design*algorithms* need be taught to newbies.
So the common question in comp.programming
"What is the best first programming language to learn?"
would become moot!

> I (poorly) was referring to the newb who was just here asking for
> the best lisp operators to use, as if knowing the most common
> operators is going to help you when you are unable to articulate
> your algorithm.

Hmm, I think my idea of a Web-based CAI for how to program without
explicitly using *any* programming language would pretty much
eliminate those kinds of newbie questions. Instead of saying "Learn
these built-in Lisp functions", and in the C group being told
"Learn these C operators and library functions", and in the Java
group being told "Learn these Java classes, and the following
methods within them", and in comp.programming getting all that
contradictory advice plus admonitions to instead use C# or VB6 or
*.NET or FlamingThunder or Pascal or machine language or Fortran 77
or Scheme or Python etc. etc., instead all newbies asking such
questions can be sent to the non-language CAI service where all
such questions can be postponed for months or years.

> My preferred method of learning a new language: find a good book,
> read a chapter, put it in my lap as I do the most interesting
> chapter problems, and continue on to the next chapter.

That presents a dilemma. Write all answers to chapter problems
using pseudo code, whereby you have no way to check your algorithms
to see if they really work, or pick a particular programming
language and suffer whatever syntax it presents.

Suppose my proposed non-language online CAI-algorithm-design
service existed. Would you be willing to use it, instead of an
actual programming language, to work out the answers to the chapter
problems, to verify that your proposed algorithms really work to
solve the particular task?

> When I've learned enough to code without the book, put the book down.

That sounds reasonable. If my proposed non-language CAI-algorithm-design
service existed, you could initially:
- See problem in book, and suggestions of functions to call, browse
my index of functionality to find equivalent functionality, and
name it anything you want, like what the book says, or something
you prefer instead.
Then when you're at the put-book-down point, you switch to:
- Browse my index of functioality for anything you feel like
playing with, with no requirment to do what any book says,
instead invent/specify your own tasks that you feel you can
accomplish with just a little bit more effort in finding
existing functionality plus adding a layer of your own algorithms.

> My preferred book happened to be Norvig's PAIP.

So are you doing the examples in the book using some particular
programming language, or perhaps doing them in parallel using two
different languages, or doing them with just pseudocode?

> Even with the advent of the internet, it's still my preferred
> method, because published books are generally of higher quality
> than the language studies I find on the internet.

I would like to see that changed someday soon, to where
high-quality tutorials about algorithm design (for newbies) are
available over the Web.

Have you seen my proposed course outline for teaching computer
programming (using Lisp for now, using my proposed non-language Web
service eventually) starting from the absolute beginning?
<http://www.rawbw.com/~rem/HelloPlus/hellos.html#s4outl>
Critique please.
 | 
Pages: 1
Prev: discount, DSQUARED ,clothing ( paypal accept ) ( www.sneaker-fan.com ) discount, LRG ,clothing ( paypal accept ) ( www.sneaker-fan.com )
Next: please help me about path names.