===================[ Midterm Warm-Up ]===================

These are the warm-up problems for the midterm. The actual midterm
problems will be harder; these problems should give you a taste
of their smaller parts.

1. Forest for the trees.

Assume that you are given trees with numbers, symbols, or strings
at the nodes, one value of the above type at each node. These trees
are represented as LISP lists as follows: (VALUE CHILD_SUBTREE1 CHILD_SUBTREE2 ...)
for nodes that have subtrees under them, and (VALUE) for nodes that
do not (the leaf nodes), where a CHILD_SUBTREE is in turn a list
formatted as above.

Write recursive functions that, for a given tree, return:
  - the sum of all numbers in it
  - the list of all numbers in it (in the depth-first traversal (DFT) order)
  - the list of all strings in it (in DFT)
   - the tree in which all strings are converted to symbols 
      (assume all strings are legal symbol names in your LISP). Do not
      change the original tree.
  - the _original_ tree in which all strings are converted to symbols 
      (assume all strings are legal symbol names in your LISP). This is
      "destructive" w.r.t. the original tree.
  - the tree in which at each level the nodes are reordered
      so that those with numbers come first, then those with strings,
        then those with symbols
  - the string that is a concatenation of all strings in it, in *breadth-first order*

Reuse code when possible---e.g., when two tasks are almost similar,
such as the 2nd and 3rd above, write one function for the traversal
and another to test a value at a node.

Do the above with tail-recursion, if possible. Use the accumulator
trick (see OnLisp, class notes).

2. Unwinding the Golden Spiral

Write a program to compute the 100000th Fibonacci number in Lisp (or Ruby).

(See http://world.mathigon.org/Sequences for the Fibonacci numbers definition
and the spiral)

3. A poor man's counter object

In a Common LISP or in Elisp with _lexical binding_ (Emacs 24 or later),
write a LISP function MAKE-COUNTER that will return a list of
three anonymous functions (lambdas/closures). When called (with FUNCALL),
these functions shall, respectively, return the value of a counter,
increment that counter by 1, and decrement the counter by 1. The next
invocations should show the updated value.

Each invocation of the MAKE-COUNTER should give you a triple of
functions that operate on a new counter.

Have MAKE-COUNTER take optional values for the starting counter value
and the increment/decrement value other that the default 1.

How will the above code evaluate under dynamic binding (Elisp's default)?

4. From Ruby to LISP and Back Again, via Sexps.

Ruby (starting with 2.0) can output the S-expressions (sexps)
that its parser produces for programs. For example:

[:program,
 [[:binary,
    [:@int, "2", [1, 0]],
       :+,
          [:binary, [:@int, "2", [1, 2]], :*, [:@int, "3", [1, 6]]]]]]

(The third elements of each :@int, such as [1, 0], [1, 2] and [1, 6]
above are parser's internal record of the line and column position of
the respective input tokens. They do not play a role in the evaluation.)

If we change in this all square brackets to round ones and remove commas,
we will get a LISP list.

Write a LISP function that evaluates such lists derived from Ruby arithmetic
expressions, and rejects sexps that don't come from arithmetic expressions.
You can print the rejection message with the line and column number if you
like.

------------------ A dirty ruby hack for the substitution ---------------
#  This is quick-and-very-dirty! What if strings in the sexp contain []s,
#   commas, newlines? Escaping should be observed for a proper way to do this!
require 'ripper'
require 'pp'
code = "2+2 * 3"
puts Ripper.sexp(code).pretty_inspect.tr("[],\n", "()  ")
-------------------------------------------------------------------------

5. I am picking anchors off HTML trees

The SBCL package "cl-html-parse" (see class notes on LISP packages
on how to install it) produces LISP representations of HTML documents 
parsed into LISP lists.

Write a function that gets such a list representing a syntactically
valid HTML document, and prints all "A" (anchor) elements in it, as
follows: first the URL, then the text of the anchor. For example,

<a href="https://www.quicklisp.org/">QuickLisp <i>Beta</i></a>

should produce

https://www.quicklisp.org/ QuickLisp Beta

(notice that the anchor text may contain any HTML markup, which
your function should remove, preserving the plain text).

I'll provide some parses to practice on, but just in case:

------------------ Using cl-html-parse with strings and files -------------------
CL-USER> (ql:quickload "cl-html-parse")
To load "cl-html-parse":
  Load 1 ASDF system:
      cl-html-parse
      ; Loading "cl-html-parse"

("cl-html-parse")

CL-USER> (html-parse:parse-html "<a href=\"http://www.quicklisp.org/\">QuickLisp <i>Beta</i></a>")
(((:A :HREF "http://www.quicklisp.org/") "QuickLisp " (:I "Beta")))

CL-USER> (html-parse:parse-html (open "myhtmlfile.html"))

((:HEAD (:TITLE "My page"))
 (:BODY
   (:P "Nothing here but plain old 1990s "
      ((:A :HREF "http://www.w3schools.com/html/") "HTML"))))
CL-USER> 
----------------------------------------------------------------------------------
(see http://www.gigamonkeys.com/book/files-and-file-io.html for
  hints on LISP file I/O)