A notebook is a dataflow graph

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.10%2C%3C3.15%22%0A%23%0A%23%20%5Btool.marimo-studio%5D%0A%23%20default%20%3D%20%22animation%22%0A%23%20runtimes%20%3D%20%5B%22server%22%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.25.1%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22A%20notebook%20is%20a%20dataflow%20graph%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20ast%0A%20%20%20%20import%20textwrap%0A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20ast%2C%20mo%2C%20textwrap%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20introduction(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20A%20notebook%20is%20a%20dataflow%20graph%0A%0A%20%20%20%20marimo%20reads%20which%20names%20each%20cell%20defines%20and%20which%20it%20references.%20An%20edge%0A%20%20%20%20runs%20from%20the%20cell%20that%20defines%20a%20name%20to%20every%20cell%20that%20reads%20it%2C%20and%20the%0A%20%20%20%20edges%20form%20a%20directed%20acyclic%20graph.%20Its%20cells%20therefore%20have%20a%0A%20%20%20%20*topological%20order*%2C%20in%20which%20every%20edge%20points%20forward.%20When%20you%20move%20a%0A%20%20%20%20slider%2C%20marimo%20reruns%20exactly%20the%20cells%20downstream%20of%20it%2C%20in%20that%20order.%0A%0A%20%20%20%20This%20notebook%20analyzes%20the%20small%20notebook%20below%20the%20same%20way%3A%20it%20parses%0A%20%20%20%20the%20file%2C%20builds%20the%20graph%2C%20sorts%20it%2C%20lays%20it%20out%20in%20layers%2C%20and%20finds%20the%0A%20%20%20%20cells%20each%20slider%20reruns.%20The%20Animation%20view's%20%60scene.py%60%20draws%20what%20this%0A%20%20%20%20notebook%20computes%20and%20computes%20nothing%20of%20its%20own.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20program(mo%2C%20textwrap)%3A%0A%20%20%20%20%23%20A%20marimo%20file%20lists%20each%20cell%20as%20a%20function%3A%20its%20parameters%20are%20the%20names%0A%20%20%20%20%23%20it%20reads%2C%20and%20its%20return%20value%20names%20what%20it%20defines.%20Cells%20may%20appear%20in%0A%20%20%20%20%23%20any%20order.%0A%20%20%20%20source%20%3D%20textwrap.dedent(%22%22%22%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20report(mo%2C%20figure%2C%20rmse)%3A%0A%20%20%20%20%20%20%20%20page%20%3D%20mo.vstack(%5Bfigure%2C%20mo.md(f%22RMS%20error%20%7Brmse%3A.3f%7D%22)%5D)%0A%20%20%20%20%20%20%20%20return%20(page%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20points(mo)%3A%0A%20%20%20%20%20%20%20%20points%20%3D%20mo.ui.slider(20%2C%20200%2C%20value%3D60%2C%20label%3D%22points%22)%0A%20%20%20%20%20%20%20%20return%20(points%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20grid(np%2C%20points)%3A%0A%20%20%20%20%20%20%20%20x%20%3D%20np.linspace(-1%2C%201%2C%20points.value)%0A%20%20%20%20%20%20%20%20return%20(x%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20chart(plt%2C%20x%2C%20y%2C%20y_hat)%3A%0A%20%20%20%20%20%20%20%20figure%2C%20axes%20%3D%20plt.subplots()%0A%20%20%20%20%20%20%20%20axes.scatter(x%2C%20y)%0A%20%20%20%20%20%20%20%20axes.plot(x%2C%20y_hat)%0A%20%20%20%20%20%20%20%20return%20(figure%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20truth(np%2C%20x)%3A%0A%20%20%20%20%20%20%20%20y_true%20%3D%20np.sin(3%20*%20x)%0A%20%20%20%20%20%20%20%20return%20(y_true%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20noise(mo)%3A%0A%20%20%20%20%20%20%20%20noise%20%3D%20mo.ui.slider(0.0%2C%201.0%2C%20value%3D0.3%2C%20label%3D%22noise%22)%0A%20%20%20%20%20%20%20%20return%20(noise%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20sample(np%2C%20y_true%2C%20noise)%3A%0A%20%20%20%20%20%20%20%20y%20%3D%20y_true%20%2B%20noise.value%20*%20np.random.default_rng(0).normal(size%3Dy_true.size)%0A%20%20%20%20%20%20%20%20return%20(y%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20degree(mo)%3A%0A%20%20%20%20%20%20%20%20degree%20%3D%20mo.ui.slider(1%2C%209%2C%20value%3D3%2C%20label%3D%22degree%22)%0A%20%20%20%20%20%20%20%20return%20(degree%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20fit(np%2C%20x%2C%20y%2C%20degree)%3A%0A%20%20%20%20%20%20%20%20coefficients%20%3D%20np.polyfit(x%2C%20y%2C%20degree.value)%0A%20%20%20%20%20%20%20%20return%20(coefficients%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20error(np%2C%20y%2C%20y_hat)%3A%0A%20%20%20%20%20%20%20%20rmse%20%3D%20float(np.sqrt(np.mean((y%20-%20y_hat)%20**%202)))%0A%20%20%20%20%20%20%20%20return%20(rmse%2C)%0A%0A%20%20%20%20%40app.cell%0A%20%20%20%20def%20predict(np%2C%20x%2C%20coefficients)%3A%0A%20%20%20%20%20%20%20%20y_hat%20%3D%20np.polyval(coefficients%2C%20x)%0A%20%20%20%20%20%20%20%20return%20(y_hat%2C)%0A%20%20%20%20%22%22%22).strip()%0A%20%20%20%20mo.md(f%22%60%60%60python%5Cn%7Bsource%7D%5Cn%60%60%60%22)%0A%20%20%20%20return%20(source%2C)%0A%0A%0A%40app.cell%0Adef%20graph(ast%2C%20source)%3A%0A%20%20%20%20%23%20Each%20cell%20reads%20the%20names%20in%20its%20parameters%20and%20defines%20the%20names%20it%0A%20%20%20%20%23%20returns.%20Names%20no%20cell%20defines%2C%20such%20as%20mo%20and%20np%2C%20come%20from%20setup.%0A%20%20%20%20cells%20%3D%20%5B%5D%0A%20%20%20%20for%20_node%20in%20ast.parse(source).body%3A%0A%20%20%20%20%20%20%20%20_returned%20%3D%20_node.body%5B-1%5D.value%0A%20%20%20%20%20%20%20%20_names%20%3D%20_returned.elts%20if%20isinstance(_returned%2C%20ast.Tuple)%20else%20%5B_returned%5D%0A%20%20%20%20%20%20%20%20cells.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22name%22%3A%20_node.name%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22reads%22%3A%20%5Bargument.arg%20for%20argument%20in%20_node.args.args%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22defines%22%3A%20%5Bname.id%20for%20name%20in%20_names%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20definer%20%3D%20%7B%0A%20%20%20%20%20%20%20%20name%3A%20index%20for%20index%2C%20cell%20in%20enumerate(cells)%20for%20name%20in%20cell%5B%22defines%22%5D%0A%20%20%20%20%7D%0A%20%20%20%20edges%20%3D%20sorted(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20(definer%5Bname%5D%2C%20target)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20target%2C%20cell%20in%20enumerate(cells)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20name%20in%20cell%5B%22reads%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20name%20in%20definer%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%20cells%2C%20definer%2C%20edges%0A%0A%0A%40app.cell%0Adef%20topology(cells%2C%20edges)%3A%0A%20%20%20%20%23%20Kahn's%20algorithm%3A%20repeatedly%20take%20the%20earliest%20cell%20in%20the%20file%20whose%0A%20%20%20%20%23%20inputs%20have%20all%20run.%20A%20cycle%20would%20leave%20cells%20behind.%0A%20%20%20%20children%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%5Btarget%20for%20source_cell%2C%20target%20in%20edges%20if%20source_cell%20%3D%3D%20index%5D%0A%20%20%20%20%20%20%20%20for%20index%20in%20range(len(cells))%0A%20%20%20%20%5D%0A%20%20%20%20_waiting%20%3D%20%5B%0A%20%20%20%20%20%20%20%20sum(1%20for%20_%2C%20target%20in%20edges%20if%20target%20%3D%3D%20index)%20for%20index%20in%20range(len(cells))%0A%20%20%20%20%5D%0A%20%20%20%20_ready%20%3D%20%5Bindex%20for%20index%2C%20count%20in%20enumerate(_waiting)%20if%20count%20%3D%3D%200%5D%0A%20%20%20%20topological%20%3D%20%5B%5D%0A%20%20%20%20while%20_ready%3A%0A%20%20%20%20%20%20%20%20_current%20%3D%20min(_ready)%0A%20%20%20%20%20%20%20%20_ready.remove(_current)%0A%20%20%20%20%20%20%20%20topological.append(_current)%0A%20%20%20%20%20%20%20%20for%20_child%20in%20children%5B_current%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_waiting%5B_child%5D%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_waiting%5B_child%5D%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ready.append(_child)%0A%20%20%20%20if%20len(topological)%20!%3D%20len(cells)%3A%0A%20%20%20%20%20%20%20%20raise%20ValueError(%22The%20cells%20form%20a%20cycle.%22)%0A%20%20%20%20backward%20%3D%20sum(1%20for%20source_cell%2C%20target%20in%20edges%20if%20source_cell%20%3E%20target)%0A%20%20%20%20return%20children%2C%20topological%0A%0A%0A%40app.cell%0Adef%20layout(cells%2C%20children%2C%20edges%2C%20topological)%3A%0A%20%20%20%20%23%20A%20cell's%20layer%20is%20the%20longest%20path%20to%20it%20from%20a%20slider.%20Sliders%20sit%20one%0A%20%20%20%20%23%20layer%20before%20their%20first%20reader%2C%20and%20the%20cells%20of%20a%20layer%20stack%20by%20the%0A%20%20%20%20%23%20average%20height%20of%20their%20parents.%0A%20%20%20%20_parents%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%5Bsource_cell%20for%20source_cell%2C%20target%20in%20edges%20if%20target%20%3D%3D%20index%5D%0A%20%20%20%20%20%20%20%20for%20index%20in%20range(len(cells))%0A%20%20%20%20%5D%0A%20%20%20%20_layer%20%3D%20%5B0%20for%20_%20in%20cells%5D%0A%20%20%20%20for%20_current%20in%20topological%3A%0A%20%20%20%20%20%20%20%20for%20_child%20in%20children%5B_current%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_layer%5B_child%5D%20%3D%20max(_layer%5B_child%5D%2C%20_layer%5B_current%5D%20%2B%201)%0A%20%20%20%20for%20_index%20in%20range(len(cells))%3A%0A%20%20%20%20%20%20%20%20if%20not%20_parents%5B_index%5D%20and%20children%5B_index%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_layer%5B_index%5D%20%3D%20min(_layer%5Bchild%5D%20for%20child%20in%20children%5B_index%5D)%20-%201%0A%20%20%20%20_height%20%3D%20%5B0.0%20for%20_%20in%20cells%5D%0A%20%20%20%20for%20_depth%20in%20range(max(_layer)%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20_members%20%3D%20sorted(%0A%20%20%20%20%20%20%20%20%20%20%20%20(index%20for%20index%20in%20topological%20if%20_layer%5Bindex%5D%20%3D%3D%20_depth)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20key%3Dlambda%20index%3A%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20-sum(_height%5Bparent%5D%20for%20parent%20in%20_parents%5Bindex%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%20max(len(_parents%5Bindex%5D)%2C%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20for%20_slot%2C%20_member%20in%20enumerate(_members)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_height%5B_member%5D%20%3D%20(len(_members)%20-%201)%20%2F%202%20-%20_slot%0A%20%20%20%20nodes%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22name%22%3A%20cell%5B%22name%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22file%22%3A%20index%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22rank%22%3A%20topological.index(index)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22layer%22%3A%20_layer%5Bindex%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22height%22%3A%20_height%5Bindex%5D%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20for%20index%2C%20cell%20in%20enumerate(cells)%0A%20%20%20%20%5D%0A%20%20%20%20return%20(nodes%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20nodes_table(mo%2C%20nodes)%3A%0A%20%20%20%20mo.ui.table(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22cell%22%3A%20node%5B%22name%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22file%20position%22%3A%20node%5B%22file%22%5D%20%2B%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22topological%20position%22%3A%20node%5B%22rank%22%5D%20%2B%201%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22layer%22%3A%20node%5B%22layer%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20node%20in%20sorted(nodes%2C%20key%3Dlambda%20node%3A%20node%5B%22rank%22%5D)%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20selection%3DNone%2C%0A%20%20%20%20%20%20%20%20pagination%3DFalse%2C%0A%20%20%20%20%20%20%20%20label%3D%22The%20cells%20in%20topological%20order%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20controls(mo)%3A%0A%20%20%20%20changed%20%3D%20mo.ui.radio(%0A%20%20%20%20%20%20%20%20%5B%22points%22%2C%20%22noise%22%2C%20%22degree%22%5D%2C%20value%3D%22noise%22%2C%20label%3D%22Move%20a%20slider%22%2C%20inline%3DTrue%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5Bchanged%5D%2C%20justify%3D%22start%22)%0A%20%20%20%20return%20(changed%2C)%0A%0A%0A%40app.cell%0Adef%20cascade(cells%2C%20changed%2C%20children%2C%20definer%2C%20topological)%3A%0A%20%20%20%20%23%20Moving%20a%20slider%20reruns%20the%20cells%20that%20read%20it%2C%20then%20everything%0A%20%20%20%20%23%20downstream%20of%20them%2C%20in%20topological%20order.%0A%20%20%20%20_stale%20%3D%20%7B%0A%20%20%20%20%20%20%20%20index%20for%20index%2C%20cell%20in%20enumerate(cells)%20if%20changed.value%20in%20cell%5B%22reads%22%5D%0A%20%20%20%20%7D%0A%20%20%20%20_frontier%20%3D%20list(_stale)%0A%20%20%20%20while%20_frontier%3A%0A%20%20%20%20%20%20%20%20for%20_child%20in%20children%5B_frontier.pop()%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_child%20not%20in%20_stale%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_stale.add(_child)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_frontier.append(_child)%0A%20%20%20%20rerun%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22slider%22%3A%20definer%5Bchanged.value%5D%2C%0A%20%20%20%20%20%20%20%20%22cells%22%3A%20%5Bindex%20for%20index%20in%20topological%20if%20index%20in%20_stale%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(rerun%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20summary(cells%2C%20changed%2C%20mo%2C%20rerun)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22Moving%20**%7Bchanged.value%7D**%20reruns%20%7Blen(rerun%5B'cells'%5D)%7D%20of%20%7Blen(cells)%7D%20%22%0A%20%20%20%20%20%20%20%20%22cells%3A%20%22%20%2B%20%22%20%E2%86%92%20%22.join(f%22%60%7Bcells%5Bindex%5D%5B'name'%5D%7D%60%22%20for%20index%20in%20rerun%5B%22cells%22%5D)%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A