dok/example/loops

Common Lisp loops

CL loop macro is nice because for every variable, in one line there is:

its initial value
the calculation of its next value, during loop continuation

This is a real example of mine CL code:

(defclass board ()
  (
   (number->extraction
    :type hash-table
    :documentation "Map a number to its extraction order."
    :accessor board-number->extraction
    :initarg :number->exctraction)
   (extraction->number
    :type (vector extraction)
    :documentation "From an extraction order like 3, to the corresponding number."
    :accessor board-extraction->number
    :initarg :extraction->number)
   (content
    :type (vector extraction)
    :documentation "The numbers inside the board, saved in extraction order format."
    :accessor board-content
    :initform (make-array 25 :element-type 'fixnum :fill-pointer 0 :adjustable t))
   (winner-extraction
    :type (or extraction null)
    :documentation "The board winning extraction, i.e. the first extraction completing a row."
    :initform nil
    :accessor board-winner-extraction)
   )
  (:documentation "A Bingo board where numbers are expressed according their extraction order.")
  )

(defun* (board-add-row! -> null) ((self board) (row sequence) &key ((add-to-content? boolean) t))
  "Add a row (or column) to the board and maintain board-state."
  (iter (for n in-sequence row)
        (for e = (gethash n (board-number->extraction self) -1))
        (with never-win = nil)
        (maximize e into row-winner)
        ; a row win when the last (maximum) number is extracted
        (after-each
          (if (= e -1)
            (setf never-win t)
            (when add-to-content? (vector-push-extend e (board-content self)))))
        (finally
           (unless never-win
             (setf (board-winner-extraction self) (nil-min2 row-winner (board-winner-extraction self))))
           nil)))
             ; the board win at the first (minimum) winning row

(defun* (parse-board! -> boolean)  ((self board) (in stream))
  "Start with a blank line and then complete the board. Return nil if there is no board to parse."
  (iter (for rs in-stream in using #'read-line)
        (for row = (map 'list #'parse-integer (str:split " " rs :omit-nulls t)))
        (for curr-row from 0)
        (for is-there-board? initially nil then t)
        (with cols = nil)
        (until (null row))
        (if-first-time
          (let ((d (length row)))
            (setf cols (make-array (list d d) :element-type 'fixnum))))
        (after-each
           (board-add-row! self row)
           (iter (for n in-sequence row)
                 (for curr-col from 0)
                 (setf (aref cols curr-col curr-row) n)))
        (finally
          (when cols
            (let+ (((col-i _) (array-dimensions cols)))
               (iter (for i from 0 below col-i)
                     (after-each (board-add-row! self (aops:sub cols i) :add-to-content? nil)))))

             (return is-there-board?))))

Dok Loop

This is the Dok code. Note:

I take inspiration from CL loop notation, for expressing compact “repeat” conditions. In particular I can write in the same place the initialization and next step for each variable.
I take inspiration from Smalltalk infixed methods like self between: 10 and: 100, and I can create statements with infix parts. I’m using this notation only for statements but not for function calls.

data Board [
  :# A bingo board where numbers are expressed according their extraction order.

  slot number->extraction::Hash-Table(From::Int, To::Int)
  :^# Map a number to its extraction order.

  slot extraction->number::Array/Growable(Of::Int)
  :^# From an extraction order like 3, to the corresponding number.

  :assert {
    repeat {
      var p -in self.number->extraction
      test self.extraction->number[p.to] == p.from
    }

    repeat {
      var p -in self.extraction->number
      test self.number->extraction[p.to] == p.from
    }
  }

  slot content::Queue/Array/Growable(Of Int)
  :^# The number inside the board, saved in extraction order format

  slot winner-extraction::Maybe(Int)
  :^# The board winning extraction, i.e. the first extraction completing a row.

  def !add-row(row*::Int*, with add-to-content? True) {
    :# Add a row and a column to the board, maintaining board-state.

    var never-win? False
    var row-winner::Maybe(Int)
    repet {
      with n -in row*
      #-NOTE at the end of the `n` in `row*` the `repeat` will terminate

      with e -when self.number->extraction[n]
      set row-winner -max e
      :^# a row win when the last (maximum) number is extracted
      set never-win? True
      when add-to-content? {
        self.content.push(e)
      }
    }

    when-not never-win? {
      set self.winner-extraction -min row-winner
    }
  }

  def !parse-board(in::Stream(Of::Char))::Bool {
    :constructor

    var cols::Array([50, 50]*)
    var is-there-board? False

    repeat {
      with curr-row::Int -from 0
      with n* -when in.!read-line.split(" ", with omit-null? True).map{ ~.parse::Integer }
      when n*.not-empty?
      #-NOTE if this condition is false, it will terminate the `repeat`

      when-not is-there-board? {
        :# Init the board with the correct size
        set is-there-board? True
        var d n*.length
        set cols!grow([d, d]*)
      }

      set self.!add-row(row*)
      repeat {
        var n -in n*
        var curr-col -from 0
        set cols[curr-col, curr-row] n
      }
    } -finally {
      when is-there-board?

      repeat {
        with i -from 0 -below curr-col
        set self.add-row!(cols.extract[i, *], with add-to-content? False)
      }
    }
    return is-there-board?
  }
]

Rationale

repeat is not an expression, but a statement. It does not return a value, but its implicit result are the effects on the variables changed inside the loop body, and other done actions.

The dok/example/common-greather-denominator example show a repeat with invariants (the :assert part) and the max number of loops, before knowing there is a bug in the code. This is inspired to Eiffel programming language.

The variable macros are inspired to Common Lisp approach.

Differences with structured programming

In structured programming loops are predictable because they have a single exit point, that is also the unique testing condition. But they are often cumbersome to write, and often they are reverted to some canContinue variable, which value depends from inner parts of the loop.

In Dok loops can have more than an exit point, but the nested transaction semantic make them predictable, because:

loop invariants specify what are the relationships between variables in the loop
these invariants must be mantained at each execution pass of the loop, but not in intermediate processing phases
when a loop condition is not respected, the loop is rollbacked to the previous completed pass, where the variables have safe values, and they respect the invariants

The macro on variable used as iterators allow to exit the loop when the first iterator find the end of the loop.

[Dokmelody scratchpad notes] [Main website]

dok/example/loops

Common Lisp loops

Dok Loop

Rationale

Differences with structured programming

Links to this note