Thursday, 12 December 2013

The riddle of loop recur in Clojure

When writing programs with loop / recur, its not always clear to me how to arrive at a solution from first principles. Initially loop / recur seems like a bit of a mystery.

Consider the problem of adding up numbers from 1. E.g. The base case is 0.

[0]       -> 0
[1]       -> 1
[1 2]     -> 3
[1 2 3]   -> 6
[1 2 3 4] -> 10

The classical solution to the problem might have a function with 2 arities (1 and 3 arguments in this case). It might be invoked as (add-up 3) with an expected answer of 6. This invokes the first arity: (add-up 3 0 0), subsequent recursions will then invoke via the 2nd arity.

(defn add-up
  ([limit] (add-up limit 0 0 ))
  ([limit current sum]
    (if (< limit current)
      (add-up limit (+ 1 current) (+ current sum)))))

The problem with the above function is that it could blow the stack because Clojure is not naturally tail recursive. It must be told to be tail recursive by means of recur. Refactor it to use recur in the tail call position:

(defn add-up
  ([limit] (add-up limit 0 0 ))
  ([limit current sum]
    (if (< limit current)
      (recur limit (+ 1 current) (+ current sum)))))

It works now, and will not blow the stack but it's not idiomatic. Refactor again by removing the arities, replace the 2nd arity call by loop with with the function argument no longer passed in. The two other arguments, which had previously been initialised in the first arity call are now initialised at the loop

(defn add-up
  (loop [current 0 sum 0]
    (if (< limit current)
      (recur (+ 1 current) (+ current sum)))))

This is now idiomatic Clojure. Testing:

user=> (add-up 0)
user=> (add-up 4)
user=> (add-up 1000000)

Sunday, 8 December 2013

More Links



Standard ML, SML baby steps

  • SML: Google: "download SML"
  • Download and run the smlnj.msi installer.
  • It will install the SML REPL which is run from the command line. f:\user>SML

Exit the REPL with Ctrl+Z

I'm not sure anyone actually uses the REPL, alone. It can be invoked from Emacs and one could just paste one's file into it - only if you're desperate. It's easier to use it from Emacs. If you hate Emacs, you can use sublime text, or another editor of your choice.

SML Mode for Emacs

Get Emacs up and running.

Install SML mode via the command: Meta-X List Packages

  • Type: Alt-X list-packages RET
  • Scroll down to sml-mode, mouse click on sml-mode, mouse click on Install
  • Exit Emacs: Ctrl-x, ctrl-c

Run some SML code from within Emacs

  • Reopen Emacs
  • Open a file: Ctrl-x, Ctrl-f, Filename
    Or: drag a file onto Emacs, provided it has a .sml extension
  • Make sure your file has some code in it. e.g.
    val x = 2 + 4;
    val y = 3 * x;
  • Save a file: Ctrl-x, Ctrl-s (notice how the disk icon decolorizes)
  • Execute the file: Ctrl-c, Ctrl-s, RET
  • This brings up the REPL in a window below the editing window, with it pointing to the same folder as the file we opened.
  • Finally, enter: use "test.sml"; to execute the file being edited
  • Quit the REPL: Ctrl-d
  • Close the 2nd window: C-x 0

REPL notes (from Dan Grossman's coursera Programming Languages)

  1. Edit a file with extension .sml. You should be in SML-mode, using Tab to indent your code well.
  2. To create the *sml* buffer (which holds the REPL), type C-c C-s (and then Return/Enter) in the buffer with the .sml file. (Note: This will not work in the *scratch* buffer that Emacs starts in because this buffer is not in SML Mode.)
  3. Keep the .sml file(s) you are working with for a particular assignment in the same folder. When you type C-c C-s to start the REPL from a buffer for foo.sml, the REPL will look in the right folder for foo.sml when you type use "foo.sml" and will look in the same folder for any other file you use such as foo_tests.sml. This is less confusing than trying to keep track of different folders and paths while using the REPL although that is possible.
  4. To end and restart a REPL session, type C-d (to end it) and C-c C-s (and then Return/Enter) (to restart it). You must type C-d while in the *sml* buffer; you can type C-c C-s from the *sml* buffer or a buffer with a .sml file.
  5. By ending and restarting a session, the new session has an empty environment. Your earlier interactions are still in the *sml* buffer, so you can save them, cut-paste them, etc., but they have no effect on the evaluation in the restarted REPL session.
  6. Evaluation can go into an infinite loop.
    • This has likely occurred if you are not getting the "- -" prompt back and nothing appears to be happening.
    • C-c C-c will interrupt evaluation and get you your prompt back.
  7. If you forget to end your binding with a ";" character, the REPL will print an "=" character on the next line, which is just its way of saying, "you are not done { continue your binding," so type a ";" and hit Return/Enter. This is not an infinite loop (nothing is being evaluated; the REPL is waiting for you) so C-c C-c does not do anything.
  8. If the printed result looks "pretty good," but part of what you expected to see has been replaced by a "#" or "...," do not worry. The REPL has a limit on how many characters it prints, which is good since you might make a large value, such as a list with tens of thousands of elements. You can adjust the limit if you want.


Thanks to Stefan Monnier for maintaining SML Mode.