Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Tim Golden <mail@timgolden.me.uk>
Newsgroups: comp.lang.python
Subject: Re: Algorithm for sequencing a collection of dependent equations
Date: Fri, 22 Jul 2016 17:35:34 +0100
Lines: 27
Message-ID: <mailman.59.1469205349.22221.python-list@python.org>
References: <1469203273.1522601.673919081.7AC3AFEA@webmail.messagingengine.com> <38f58976-713b-a59f-a030-ddf3d21a8439@timgolden.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.uni-berlin.de SrThGEXeD1jWUsZnyhhC6Q06rYRXkMCfKAmaEsXYuflw==
Return-Path: <mail@timgolden.me.uk>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.010
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'dependency': 0.07; 'expressions': 0.07; 'translate': 0.15; '...]': 0.16; 'expressions)': 0.16; 'expressions.': 0.16; 'from:addr:timgolden.me.uk': 0.16; 'from:name:tim golden': 0.16; 'language)': 0.16; 'malcolm': 0.16; 'message-id:@timgolden.me.uk': 0.16; 'received:74.55.86': 0.16; 'received:74.55.86.74': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'received:smtp.webfaction.com': 0.16; 'received:webfaction.com': 0.16; 'tjg': 0.16; 'wrote:': 0.16; 'dependent': 0.23; 'header:In- Reply-To:1': 0.24; 'sort': 0.25; 'header:User-Agent:1': 0.26; 'figure': 0.27; 'least': 0.27; 'sequence': 0.27; 'referencing': 0.29; "i'm": 0.30; "we're": 0.30; 'similar': 0.33; 'structure': 0.34; 'list': 0.34; 'done': 0.35; 'evaluation': 0.36; 'structures': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'associated': 0.38; 'data': 0.39; 'received:192': 0.39; 'to:addr:python.org': 0.40; 'challenge': 0.61; 'determine': 0.61; 'charset:windows-1252': 0.62; 'ending': 0.63; 'from:addr:mail': 0.70; 'analysis': 0.72; 'evaluate': 0.72; 'dsl': 0.84; 'imagine': 0.96
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0
In-Reply-To: <1469203273.1522601.673919081.7AC3AFEA@webmail.messagingengine.com>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <38f58976-713b-a59f-a030-ddf3d21a8439@timgolden.me.uk>
X-Mailman-Original-References: <1469203273.1522601.673919081.7AC3AFEA@webmail.messagingengine.com>
Xref: csiph.com comp.lang.python:111766

On 22/07/2016 17:01, Malcolm Greene wrote:
> We're working on a DSL (domain specific language) that we translate into
> a list of tokenized expressions. My challenge is to figure out how to
> sequence evaluation of these expressions so that we evaluate these
> expressions in the proper order given that expressions have dependencies
> on other expressions.
>
> We've done the work to determine the full list of tokens associated with
> each expression (after referencing other expressions) and we've detected
> expressions that result in loops.

[... snip ...]

> I'm looking for an algorithm/data structure that will me to start with
> the least dependent expression (t, x, y) and move through the list of
> expressions in dependency order ending with the expression with the most
> dependencies.
>
> I imagine that spreadsheets have to perform a similar type of analysis
> to figure out how to recalculate their cells.
>
> Suggestions on algorithms and/or data structures (some form of graph?)
> to support the above goals?

I think that what you're looking for is a topological sort

TJG