Monads (no, bear with me!)

[christianp]

There are a few situations where we want some monad-like behaviour:

• Marking algorithms, where feedback accumulates as a side-effect of some functions
• The Eukleides extension, where modifiers act on parts of a drawing.
• Progressively modifying a complicated such as a graph

It would be nice to do something like this:

capture_feedback(
  step1;
  step2;
  step3
)

The capture_feedback function stores an object in the scope, and functions which play in that monad can fetch it and replace it with something else. The capture_feedback function is in charge of exactly how the feedback from the steps modifies its object.

Or, could it just be that the ; operator does all of this, and it's overloaded for different type signatures?

In the Eukleides extension, at the moment modifiers are implemented by overloading * and defining a modifier data type, so rect black filled works out as two calls to drawing * modifier, returning another drawing value. This becomes awkward when the implicit multiplication doesn't happen, for example if the drawing is a list of objects.

This modifier pattern occurs in other places, where I usually implement it as normal functions, so the above would have to be something like

filling(filled,colour(black,rect))

This ends up with a lot of brackets, and is hard to read.

It would be nice to have a special operator called something like >> which rewrites rect >> colour(black) >> filling(filled) to filling(filled,colour(black,rect)).

This also offers a nicer way of using constructor functions with lots of optional arguments, where you can progressively modify a base object. An example from the graph theory extension would be

edge(0,1)
  >> weight(5)
  >> undirected
  >> label("e")

Another one that's come up is showing working-out. Something like this:

working_out(
g, // keep the result of each step as the variable g

show_graph(g), // when displaying each step, show the graph g

  graph(...)  // make the initial graph
>>
  add_edge(g, ...)
>> 
  explanation("Add an edge")
>>
  highlight_edges(g, ...)
>>
  explanation("Consider edges connected to the last one")
>>
  ...
)

Which would produce a list of steps, each showing a line of explanation and the graph g at that point.

[christianp]

On the subject of working-out, I've made a prototype using the existing parser, and a couple of examples.

There's a function working_out(columns, algorithm) which produces a table of steps in the algorithm. columns is a list of definitions of columns to include in the table, showing the state of the algorithm, in the form [header, expression]. The algorithm is an expression which is evaluated in a special scope. There is a function comment(message) which produces a value of type workingout. The operator ; takes any value on its left-hand side and a workingout value on its right. The working message is added to the scope's list of steps, along with values for each of the defined columns evaluated against the current scope, and the left-hand value is returned. Once the algorithm is evaluated, the table of steps is rendered, using the messages and column values. The function returns the final result of the algorithm, and the rendered working out.

Here's one for decomposing permutations into cycles:

produced by this code:

working_out(
  [
    ["Cycles found so far","$"+join(map(show(c),c,cycles),"")+"$"]
  ],
let(
    [cycles,_], 
        iterate_until(
            let(
                i, min(available)
            ,
                raw_cycle, iterate_until(p[j], j, p[i], j=i)
                   ; comment(if(len(cycles)=0,"Start with $"+i+"$", "$"+i+"$ has not been considered yet.")) 
            ,
                cycle, cycle(map(x-1,x,raw_cycle))
            ,
                cycles,if(cycle<>perm("e"),cycles+[cycle],cycles)
                   ; comment("Repeatedly apply $p$ until you get back to $"+i+"$:")
                   ; comment("$"+join([i]+raw_cycle,' → ')+"$")
            ,
                [cycles, filter(not (x in raw_cycle),x,available)]
                   ; comment(if(cycle<>perm("e"),"So $"+show(cycle)+"$ is a cycle.","$"+i+"$ is mapped to itself, so we can omit this trivial cycle."))
            )
        ,
            [cycles, available]
        ,
            [[], list(1..n)]
        ,
            len(available)=0
        )[-1],
    cycles
      ; comment("Every position has now been considered.")
      ; comment("$p$ is the product of all the cycles we found.")
      ; comment("So $p = "+join(map(show(c),c,cycles),'')+"$")
)
)

The comments inside the let look like they're a step late: I can't use a variable in a comment until the line after the one which defines it. This is where it would be nice to have some special monad syntax, so let(...) could be replaced with something like

procedure(
 i := min(available) >> comment("{i} has not been considered yet");
 cycle := ...
)

And here's an example showing the Euclidean algorithm, which was the first algorithm we had to write working-out for in Numbas!

produced by this code:

working_out(
  [
    ["$a$",x],
    ["$b$",y],
    ["$a \\mod b$",r],
    ["Equation","$"+latex(substitute(["a":x,"b":y,"m":m,"r":r],expression("a = m*b+r")))+"$"]
  ],
  let([gcd,x,y],
    iterate_until(
      let(
        r, mod(x,y)
      ,
        m, (x-r)/y
      ,
        [y,r]
          ; comment("$"+y+"$ goes into $"+x+"$ $"+(m as "number")+"$ "+pluralise(m,"time","times")+" with remainder $"+r+"$.")
      )
    ,
      [x,y]
    ,
      [a,b]
    ,
      mod(x,y)=0
    ),
    gcd
  )
)

Another awkward part in this is that I can't just sub into TeX in the comment string normally, because substitution happens once the string is displayed in the page, when the original scope is lost.

Here's my prototype question: https://numbas.mathcentre.ac.uk/question/share/view/1b07c3fa-d2d3-4075-83fe-f80ec0279b08

[christianp]

We talked about how the procedure syntax might look like this:

procedure(
 i <- min(available) /* "{i} has not been considered yet" */ ;
 cycle <- whatever
)

So <- instead of := for assignment, and make the working-out annotation look a bit more like a comment. I've used /* ... */ above, which might be risky given it just marks a block comment in other languages. I'd like to have delimiters instead of a function, for conciseness.

Other options:

• << "step" >> (looks like French quote marks)
• __ "step" __ (looks like markdown italics)
• ; annotation( "step" ); (looks like a function call)
• <? "step" ?> (looks like PHP's interpolation delimiters)
• @ "step" (looks like WEB, newline ends the annotation)

Should the insides of these delimiters produce a string by default, and you have to escape out to JME code? Like

/* 
{{ if(condition, }} 
The condition is true 
{{ , }} 
The condition is false 
{{ ) }} 
*/

I don't want to have a proliferation of weird characters. Can we do it with spacing, or insisting annotation bits are on their own line?

Lines starting @ denote annotations, which are collected together:

procedure(
i <- min(available);
   if(i<10,
     @ $i = \var{i} < 10$
     @ which is quite interesting
  ,
     @ $\var{i}$ is 10 or more
  )
)

Code must be indented; annotations must start at the start of the line (like Knuth's literate programming):

procedure(
    i <- min(available);
    if(i<10,
$i = \var{i} < 10$
which is interesting
    ,
$\var{i}$ is 10 or more
    )
)

Or code lines must start with @:

procedure(
@ i <- min(available);
@ if(i<10,
$i = \var{i} < 10$
which is interesting
@ ,
$\var{i}$ is 10 or more
@ )
)