Lunar Programming Language

by David A. Moon
January 2017 - January 2018



For Statement

The for statement provides a more general and powerful form of iteration than the while and until statements, but is more concise and readable than an iterative function.

A for statement consists of four parts, which must appear in order:

  1. one or more emitters, which produce a value on each iteration for one or more iteration variables
  2. zero or more end tests, which together with the emitters determine when to end the iteration
  3. zero or more collector declarations, which control the result of the for statement
  4. the body, which is executed once for each iteration

Example:

def input_list = [ -1, 0, 0, 3, 1, 5, 4, 3, 2, 6 ]

for x,y in input_list while x < y using collect
  if y > 0
    collect "$x < $y"

yields [ "0 < 3", "1 < 5" ]
Here x,y in input_list is an emitter, while x < y is an end test, using collect is a collector declaration, and the rest is the body. The result is a list of strings.

An emitter consists of one or more left-hand sides separated by commas, followed by a name that identifies the type of emitter, followed by additional syntax specific to that emitter type. A left-hand side can be a simple name or a destructuring. Not all emitters allow more than one left-hand side.

On each iteration, the emitter defines values for the left-hand sides. Within the end tests and body, the left-hand sides are defined as constants with different values on each iteration. For example, in emits successive members of a sequence that is the result of the expression following in.

An emitter can also provide an implicit end test. For example, in ends when the sequence is exhausted.

If multiple emitters are present, they are separated by commas.

An explicit end test consists of while or until followed by an expression that is evaluated on each iteration. The iteration terminates if the result of the expression is false or non-false respectively. If there are multiple end tests, they are not separated by any punctuation.

If any collector declarations are present, they are introduced by the name using and are separated by commas. A collector declaration consists of a collector name, followed by optional additional syntax specific to that collector name. The collector name is defined as a macro that is in scope in the body. In effect, a collector is a locally defined statement. For example, the collect macro takes an expression and adds the result of that expression to the end of a list that will be the result of the for statement.

If no collector declarations are present, the result of the for statement is false.

A newline is not permitted in front of the end tests nor in front of the collector declarations, because it would be ambiguous with the start of the body. However, a newline can always be inserted after a comma or a backslash.

Predefined Emitters

The following emitters are provided by the Lunar implementation:

Name Syntax Emitted Values
in x in expression Members of sequence expression
in x,y in expression Members of sequence expression, two at a time
in key => value in expression Keys and members of keyed sequence expression
in key1 => val1, key2 => val2 in expr Keys and members of keyed sequence expr, two at a time
= x = expr expr on every iteration
= x = first then next first on first iteration, next subsequently

The in emitter allows any number of left-hand sides. For simplicity of notation, the above table only shows one or two.

In an = emitter, the left-hand side of every emitter is in scope in the next expression. If there is no next expression, x = expr turns into x = expr then expr and the left-hand side of every emitter is in scope only in the second copy of expr.

Predefined Collectors

The following collectors are provided by the Lunar implementation:

Name Syntax of Use Result of for Statement
return return expression Immediate exit and result is expression
collect [type] collect expression type containing all expressions where type is list (default), stack, or string
append [type] append expression collect all members of sequence expression
always always expression true if no expression is false
never never expression true if every expression is false
any any expression true if any expression is not false
count count [expression] Number of times expression (default true) is not false
sum sum expression Sum of all expressions
minimize minimize expression Minimum of all expressions, false if none
maximize maximize expression Maximum of all expressions, false if none

Certain collectors, e.g. count and sum, always and never, or collect and append with the same type are compatible and can be used together.

The always, never, and any collectors are allowed to exit the iteration early if the result is known.

Extending Emitters

Emitters for the for statement are defined by defining methods for the for_emitter function.

The parameters of for_emitter are:

  1. emitter name
  2. left-hand sides as a sequence[expression]
  3. token stream
  4. indentation
  5. scope

The token stream, indentation, and scope should be used to parse additional syntax after the emitter name.

The result of for_emitter is a list of:

  1. prelude, executed before iteration begins
  2. one or more formal parameters of the iteration function
  3. actual parameters of the iteration function for the first iteration
  4. actual parameters of the iteration function for subsequent iterations
  5. prefix, executed before the body on each iteration

All results are typically token lists generated by templates.

The prelude typically executes the right-hand side of the emitter and saves the result in a constant whose definition is invisible to the body but visible to the actual parameters and prefix because of the hygienic macro mechanism.

The prefix can include end tests written so the body is incorporated into the if statement that performs the end test.

The prelude and the prefix should end with a newline if they are not empty and the indentation of that newline should reflect the desired nesting. The formal and actual parameters should not end with a newline.

The = emitter could have been defined by:

def for_emitter(#\=, lhss, tokens, indentation, scope)
  if lhss.length ~= 1 then error("for x = y then z allows only one x")
  def rhs = parse_expression(tokens, indentation, scope, true)
  def rhs2 = if match?(tokens, #then)
               parse_expression(tokens, indentation, scope, true)
             else
               rhs
  [ ``,                                 ; no prelude
    first(lhss),                        ; lhs is formal parameter
    rhs,                                ; actual parameter first time
    rhs2,                               ; actual parameter subsequent times
    `` ]                                ; no prefix

The in emitter is more complex. It could have been defined by:

def for_emitter(#in, lhss, tokens, indentation, scope)
  def rhs = parse_expression(tokens, indentation, scope, true)
  def context = macro_context()         ; for `

  ;; The prefix defines all the left-hand sides and does the end test
  ;; There is one position for each left-hand side to minimize
  ;; the number of invocations of iterate
  def last_position = name("position$(lhss.length)", context)
  def prefix = for lhs in lhss, i = 1 then i + 1 using append
                 def position = name("position$i", context)
                 append `if more?(sequence, $position)
                           def $lhs = next(sequence, $position)
                           `
                 if i < lhss.length
                   def next_position = name("position$(i + 1)", context)
                   append `def $next_position = iterate(sequence, $position)
                          `

  ;; Expansion of the emitter
  [ `def sequence = $rhs                  ; prelude
    `,
    `position1`,                          ; formal parameter
    `iterate(sequence)`,                  ; actual parameter first time
    `iterate(sequence, $last_position)`,  ; actual parameter subsequent times
    prefix ]

TODO: Add support for => for keyed_sequence iteration

If we wanted as a synonym for in as an emitter, it could be defined by:

def for_emitter(#\∈, lhss, tokens, indentation, scope)
  for_emitter(#in, lhss, tokens, indentation, scope)

Extending Collectors

Collectors for the for statement are defined by defining methods for the for_collector function.

The parameters of for_collector are:

  1. collector name
  2. hygienic context
  3. token stream
  4. indentation
  5. scope

The token stream, indentation, and scope can be used to parse additional syntax after the collector name in the using clause.

The result of for_collector is a list of:

  1. prelude, executed before iteration begins
  2. postlude, executed after iteration ends, its result is the for statement's result
  3. prefix, executed before the body on each iteration, typically a macro definition

All results are typically token lists generated by templates. The prelude should end with a newline if it is not empty and the indentation of that newline should reflect the desired nesting. The postlude and prefix should not end with a newline.

Only collectors whose preludes are equal and whose postludes are equal can be used together in a single for statement.

The always collector could have been defined by:

def for_collector(#always, context, tokens, indentation, scope)
  def result = `result`                 ; for nested `
  [ `def result := true                 ; prelude
    `,
    `result`,                           ; postlude
    `defmacro \always expression =>     ; prefix
       \`if not \$expression then $result := false\` ` ]

TODO: The always, never, and any collectors are allowed to exit the iteration early if the result is known. Not implemented above.

The collect collector could have been defined by:

def for_collector(#collect, context, tokens, indentation, scope)
  def type = parse_name(tokens, indentation, scope, false) or #list
  def result = `result`                     ; for nested `
  case name(type, false)                    ; strip hygienic context
    #list =>
      [ `def result = stack()               ; prelude
        `,
        `list(result...)`,                  ; postlude
        `defmacro \collect expression =>    ; prefix
           \`push!($result, \$expression)\` ` ]
    #stack =>
      [ `def result = stack()               ; prelude
        `,
        `result`,                           ; postlude
        `defmacro \collect expression =>    ; prefix
           \`push!($result, \$expression)\` ` ]
    #string =>
      [ `def result = stack[character]()    ; prelude
        `,
        `string(result)`,                   ; postlude
        `defmacro \collect expression =>    ; prefix
           \`append!($result, string(\$expression))\` ` ]
    default:
      error("collect type must be list, stack, or string, not $type")

The return collector could have been defined by:

def for_collector(#return, context, tokens, indentation, scope)
  def returner = `returner`             ; for nested `
  [ `block exit: returner               ; prelude
       `,
    ``,                                 ; no postlude
    `defmacro \return expression =>     ; prefix
       \`$returner(\$expression)\` ` ]

Definition of the for Macro

The for statement could have been defined by:

defmacro for =>
  ;; Data structures to collect pieces of the expansion
  def preludes = stack()
  def formals  = stack()
  def initials = stack()
  def repeats  = stack()
  def prefixes = stack()
  def macros   = stack()
  def lhss     = stack()
  def collector_prelude  := false
  def collector_postlude := `false`
  def collector_context   = macro_context(scope)

  ;; Subroutines

  def parse_left_hand_sides()
    ;; precedence 70 prevents gobbling = or in, but allows gobbling (
    push!(lhss, parse_expression(tokens, indentation, scope, true, 70))
    if match?(tokens, #\,) parse_left_hand_sides()

  def parse_emitters()
    clear!(lhss)
    parse_left_hand_sides()
    def [prelude, formal, initial, repeat, prefix] =
                for_emitter(next!(tokens), lhss, tokens, indentation, scope)
    append!(preludes, prelude)
    push!(formals,    formal)
    push!(initials,   initial)
    push!(repeats,    repeat)
    append!(prefixes, prefix)
    if match?(tokens, #\,) parse_emitters()

  def parse_endtests()
    if match?(tokens, #while)
      def test = parse_expression(tokens, indentation, scope, true)
      append!(prefixes, `if $test
                           `)
      parse_endtests()
    else if match?(tokens, #until)
      def test = parse_expression(tokens, indentation, scope, true)
      append!(prefixes, `if not $test
                           `)
      parse_endtests()

  def parse_collectors()
    def [prelude, postlude, prefix] =
                for_collector(next!(tokens), collector_context, tokens, indentation, scope)
    if collector_prelude
      if collector_prelude ~= prelude or collector_postlude ~= postlude
        error("Incompatible collectors cannot be used in the same for statement")
    else
      append!(preludes, prelude)
      collector_prelude := prelude
      collector_postlude := postlude
    append!(macros, prefix)
    if match?(tokens, #\,) parse_collectors()

  def parse_for_body()
    ;; Parse the body with collector macro definitions in scope
    ;; by pushing the macros into the incoming token stream before the body
    ;; Put a newline after each macro definition
    insert!(tokens, `${$macros
                     }`)
    ;; Make a block containing the local macros and the body
    parse_body(tokens, indentation, scope, true)

  ;; Main body of the for statement parser begins here
  parse_emitters()
  parse_endtests()
  if match?(tokens, #using)
    parse_collectors()
  def body = parse_for_body()

  ;; Assemble the expansion as a tail-recursive function
  `$preludes
   def loop(${$formals & , })
     $prefixes $body
     loop(${$repeats & , })
   loop(${$initials & , })
   $collector_postlude`


Previous page   Table of Contents   Next page



Creative Commons License
Lunar by David A. Moon is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Please inform me if you find this useful, or use any of the ideas embedded in it.
Comments and criticisms to dave underscore moon atsign alum dot mit dot edu.