From SETL to Python translation

[Tim Peters]

[cyberian bear]
> Hi guys I have 2 programs below that I must have in Python but I have
> them in SETL(whatever the hell that is) and I don't know anything about
> it. I tried finding stuff about it on the web but all I found was two
> small, irrelevant pages and no tutorials.

You must have missed:

    http://birch.eecs.lehigh.edu/~bacon/doc.html

You can download Robert Dewar's introductory "The SETL Programming Language"
paper via a link on that page.

> The thing is, if at least I knew what the 'Euler path construction', or
> 'Prime factors' are, I could just program them on my own without looking
> at the SETL code, but i don't.

prime_factors(n) takes an integer as input and returns a list of its prime
factors, via repeated trial division by 2, then by the odd numbers from 3 up
to the ceiling of the square root of n.

Euler_path(G) takes an undirected graph represented as a set of 2-element
lists (representing edges via the nodes they connect), and returns an Euler
path as a list of the nodes of G in an Euler-path order; it returns OM
(SETL's spelling for "there's no meanigful result") if no Euler path exists.
An Euler path is a traversal of the graph such that each edge is taken
exactly once.

These are standard algorithms in their fields, and as such can be found all
over the web.

> Basically I just want to ask some good soul if he could translate these
> two programs for me from SETL to Python. I know chances of finding anyone
> who knows SETL are negligibe but i guess it's worth a try.
> ...

Finding someone who knows SETL is easier than finding someone who's keen to
solve what appears to be a homework problem <0.5 wink>.  Study the algorithms
and reimplement them from scratch; line-by-line translation of SETL is going
to be very frustrating.  For example, the closest simple and readable
translation of the SETL:

>         if #(odds := {x in nodes | odd(#G{x})}) > 2 then

is the Python:

    odds = []
    for x in nodes:
        successors = [y for (z, y) in G if z == x]
        if len(successors) % 2:
           odds.append(x)
    if len(odds) > 2:

but even then lots of representation changes have been made (the SETL set G
is taken to be a list of 2-tuples in Python instead; and the SETL set odds is
constructed instead as a Python list, exploiting that I happen to know no
element appears more than once in the SETL-set / Python-list "nodes").  The
SETL is a more direct translation of an English algorithm, reading "Let
'odds' be the set of nodes with an odd number of successors.  If there are
more than two of those, then ...".

prime_factors is (by far) the easier of the two, so start with that.

setl-is-to-ltes-as-python-is-to-nohtyp-ly y'rs  - tim