On 26/05/2013, at 12:43 PM, srean wrote:
>
>
> In fact the one most relevant to YOU (srean) is the costing of
> parallelisation.
> You want to split a job up into parallel parts. Which parts do you split up?
> How many pieces? What shape are the pieces?
>
>
> Ah ! this is a difficult one and enters the "sufficiently smart compiler"
> realm.
Yes, but its just a single example of the general optimisation problem.
Optimisations are examples of "Post productions" (named after some
fellow named Post). These are generalisations of grammars.
In grammar you have a single symbol on the lhs and many on the rhs:
statement = "for" variable "in" range ";"
The meaning for *generating* a language (which is why the RHS is called
a production) is that a statement symbol can be replaced by the RHS.
[If there are several statements, pick one]. A string of symbols is "in" a
language
if there exists a sequence of such replacements leading to that string.
Although such a sequence isn't deterministic in general, there are algorithms
which are guaranteed to find at least one such sequence in finite time.
They're called parsers.
In a Post production you have have many symbols on the LHS as well.
In other words pattern matching. Basically something like:
"rev" "rev" list = list
which says "when you see rev rev and a list, you can replace it with just the
list". Here's another one:
expr1 * expr2 + expr1 * expr3 => expr1 * (expr2 + expr3)
You probably recognise that as the distributive law. Note the LHS has 3 binary
operations, the RHS has only 2. So this replacement is an optimisation.
In fact ALL mathematical theorems are nothing more than optimisations.
If you think about it they just provide a way to calculate something faster.
The most important ones reduce infinite calculations to finite ones.
for example:
\sigma_{i=0}^{\inf} (1.0 / (real (i*i))) => 1.0
Finding orders to apply optimisations to get other ones is what mathematicians
do.
Its called "proving a theorem" (actually dreaming up nice theorems and systems
is the real job but anyhow we'll gloss over that).
So what's the point? An optimisation is a lemma. An optimisation scheme is a
theorem.
Finding a good optimisation scheme is very hard: lots of good optimisations are
known,
but a way to combine them is not.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Try New Relic Now & We'll Send You this Cool Shirt
New Relic is the only SaaS-based application performance monitoring service
that delivers powerful full stack analytics. Optimize and monitor your
browser, app, & servers with just a few lines of code. Try New Relic
and get this awesome Nerd Life shirt! http://p.sf.net/sfu/newrelic_d2d_may
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
