A critic of Guido's blog on Python's lambda

[David C. Ullrich]

On Tue, 09 May 2006 05:35:47 -0500, David C. Ullrich
<ullrich at math.okstate.edu> wrote:

>On Mon, 08 May 2006 18:46:57 -0400, Ken Tilton <kentilton at gmail.com>
>wrote:
>[...]
>
>If you, um, look at the code you see that "cells.a = 42" triggers
>cells.__setattr__, which fires a's callback; the callback then
>reaches inside and sets the value of b _without_ going through
>__setattr__, hence without triggering b's callback.
>
>In Cells you can't have A depend on B and also B depend on A?
>That seems like an unfortunate restriction - I'd want to be
>able to have Celsius and Farenheit, so that setting either
>one sets the other.

Realized later that I hadn't thought this through.

I'd been assuming that of course we should be allowed to
have A and B depend on each other. Hence if a change in
A propagates to a change in B that change in B has to
be a non-propagating change - thought I was just so
clever seeing a way to do that.

But duh, if that's how things are then we can't have 
transitive dependencies working out right; surely we
want to be able to have B depend on A and then C
depend on B...

(And also if A and B are allowed to depend on each
other then the programmer has to ensure that the
two rules are inverses of each other, which seems
like a bad constraint in general, something non-trivial
that the programmer has to get right.)

So fine, no loops. If anything, if we know that
there are no loops in the dependencies that simplifies
the rest of the programming, no need for the sort of
finagling described in the first paragraph above.
But this raises a question:

Q: How do we ensure there are no loops in the dependencies?

Do we actually run the whole graph through some algorithm
to verify there are no loops?

The simplest solution seems like adding the cells one
at a time, and only allowing a cell to depend on 
previously added cells. It's clear that that would
prevent loops, but it's not clear to me whether or
not that disallows some non-looping graphs. A
math question the answer to which is not immediately
clear to me (possibly trivial, the question just
ocurred to me this second):

Say G is a (finite) directed graph with no loops. Is it always
possible to order the vertices in such a way that
every edge goes from a vertex to a _previous_ vertex?

>Of course if there are no loops it's easier to see how
>you managed to do the stuff you were talking about elsewhere,
>(at least sometimes) delaying execution until needed.
>
>>Anyway...)
>>
>>> 
>>> 
>>>>all
>>>>the *programmer* has to care about is what values a slot depends on --
>>>>Cells takes care of inverting that for you, which is important because
>>>>that's a job that a computer is much better at than a human.
>>> 
>>> 
>>> Fine. I suppose that is better; if b is going to return a + 1
>>> the fact that this is what b returns should belong to b, not
>>> to a. So a has an update list including b, so when a's value
>>> is set a tells b it needs to update itself.
>>> 
>>> If we're allowed to pass (at some point, to some constructor
>>> or other) something like (b, a + 1, [a]), which sets up a
>>> cell b that shall return a + 1, and where the [a] is used
>>> in the constructor to tell a to add b to a's update list
>>> then this seems like no big deal.
>>> 
>>> And doing that doesn't seem so bad - now when the programmer
>>> is writing b he has to decide that it should return a + 1
>>> and also explicitly state that b shall depend on a; this
>>> is all nice and localized, it's still _b_ telling _a_ to
>>> add b to a's update list, and the programmer only has
>>> to figure out what _b_ depends on when he's writing _b_.
>>> Doesn't seem so bad. 
>>> 
>>> But of course it would be better to be able to pass just 
>>> something morally equivalent to (b, a + 1) to whatever 
>>> constructor and have the system figure out automatically 
>>> that since b returns a + 1 it has to add a to b's update 
>>> list. There must be some simple trick to accomplish that 
>>> (using Python, without parsing code).
>>
>>Right, you do not want to parse code. It really would not work as 
>>powerfully as Cells, which notice any dynamic access to another cell 
>>while a rule is running. So my rule can call a function on "self" (the 
>>instance that wons the slot being calculated, and since self can have 
>>pointers to other instances, the algorithm can navigate high and low 
>>calling other functions before finally reading another ruled slot. You 
>>want to track those.
>>
>>> Exactly what the trick is I 
>>> don't see immediately.
>>
>>To compute a value for a slot that happens to have a rule associated 
>>with it, have a little cell datastructure that implements all this and 
>>associate the cell with the slot and store a pointer to the rule in the 
>>cell. Then have a global variable called *dependent* and locally:
>>
>>     currentdependent = *dependent*
>>     oldvalue = cell.value
>>     newvalue = call cell.rule, passing it the self instance
>>     *dependent* = currentvalue
>>
>>     if newvalue not = oldvalue
>>          call on-change on the slot name, self, newvalue and oldvalue
>>          (the on-chnage needs to dispatch on as many arguments as
>>          the language allows. Lisp does it on them all)
>>
>>In the reader on a slot (in your getattr) you need code that notices if 
>>the value being read is mediated by a ruled cell, and if the global 
>>*dependent* is non empty. If so, both cells get a record of the other 
>>(for varying demands of the implementation).
>>
>>> 
>>> In Cells do we just pass a rule using other cells to
>>> determine this cell's value, or do we also include
>>> an explicit list of cells that this cell depends on?
>>
>>Again, the former. Just write the rule, the above scheme dynamically 
>>figures out the dependencies. Note then that dependencies vary over time 
>>because of different branches a rule might take.
>>
>>I want to reassure the community that this (nor the spreadsheet analogy 
>><g>) is not just my crazy idea. In 1992:
>>
>>     http://www.cs.utk.edu/~bvz/active-value-spreadsheet.html
>>
>>"It is becoming increasingly evident that imperative languages are 
>>unsuitable for supporting the complicated flow-of-control that arises in 
>>interactive applications. This paper describes a declarative paradigm 
>>for specifying interactive applications that is based on the spreadsheet 
>>model of programing. This model includes multi-way constraints and 
>>action procedures that can be triggered when constraints change the 
>>values of variables."
>>
>>Cells do not do multi-way constraints, btw. 
>
>My _guess_ is that a "multi-way constraint" is something like
>what's above, where A depends on B and B depends on A?
>
>>Nor partial constraints. To 
>>hard to program, because the system gets non-deterministic. That kinda 
>>killed (well, left to a small niche) the whole research programme. I 
>>have citations on that as well. :)
>>
>>kenny
>
>
>************************
>
>David C. Ullrich


************************

David C. Ullrich