leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:User Info.
View:Website (My Website).
You're looking at the latest 10 entries.
Missed some entries? Then simply jump back 10 entries

Tags:, ,
Subject:Continuation
Time:10:28 am
A pag. 137 del famoso saggio "The Little Schemer" di Daniel P. Friedman e Matthias Felleisen (Mit Press) ho trovato una funzione che non e' facile da capire per chi e' abituato/a alla programmazione imperativa perche' contiene un concetto tipico della programmazione funzionale, le continuation. Da una ricerca sul web ho scoperto che su questa funzione esistono almeno quattro diverse discussioni iniziate da persone che l'hanno trovata difficile da capire.

La funzione originale si chiama multirember&co, qui l'ho chiamata multico per avere righe piu' corte. L'ho testata e formattata con DrScheme (ho cambiato pochissimo, solo l'intestazione in modo da usare una define invece che define di lambda):
; Original function mame: multirember&co
(define (multico a lat col)
  (cond
     ((null? lat) (col '() '()))
     ((eq? (car lat) a)
      (multico a
               (cdr lat)
               (lambda (newlat seen)
                  (col newlat
                  (cons (car lat) seen)))))
     (else
      (multico a
               (cdr lat)
               (lambda (newlat seen)
                  (col (cons (car lat) newlat)
                  seen))))
     )
  )


; An usage example of multico:
(define menu '(ham tuna beer tuna beer))
(define (count1 x y) (length x))
(multico 'tuna menu count1) ; Output: 3
Come si puo' vedere e' breve. Lo scopo di questa funzione e' semplice: data una lista di atomi "lat", un atomo "a", e una funzione "col" che prende in ingresso due liste, divide lat in due diverse liste (che costruisce) e alla fine applica col a tali due liste e ne restituisce il risultato.
Esternamente come "col" ho definito una piccola funzione "count1" che usa length per restituire la lunghezza della prima lista. In questo caso in pratica restituisce quanti elementi diversi da 'tuna ci sono in "menu".

Le mie conoscenza del linguaggio Scheme e' scarsa rispetto a Python, per cui per capire un po' la funzione posso cominciare a rapportarla a codice equivalente in Python:
def splitmap(el, sequence, process):
    l1 = []
    l2 = []
    for x in sequence:
        if el == x:
            l2.append(x)
        else:
            l1.append(x)
    return process(l1, l2)

menu = "ham tuna beer tuna beer".split()
count1 = lambda x, y: len(x)
print splitmap("tuna", menu, count1)
Tale funzione Python puo' anche essere scritta in modo piu' sintetico ma ancora leggibile (le definzioni parallele di variabili su una sola riga le trovo accettabili quando a destra ci sono oggetti tutti uguali, cosi' non c'e' bisogno di capire cosa e' assegnato a cosa; oppure per fare swap e operazioni simili che richiedono la simultanea modifica di due o piu' variabili):
def splitmap(el, sequence, process):
    l1, l2 = [], []
    for x in sequence:
        ((l1, l2)[el == x]).append(x)
    return process(l1, l2)
In linguaggio Ruby il codice sarebbe ancora piu' corto (questa e' una approssimazione, dato che Ruby non lo conosco):
def splitmap(el, sequence, process)
    process sequence.split{|x| x==el}
end
Sono convinto che la prima versione Python sia oggettivamente uno dei modi piu' chiari e sensati per rappresentare questo semplice algoritmo, ma d'altronde lo scopo di tale saggio e' insegnare un po' di programmazione funzionale in Scheme, per cui e' giusto seguire le sue strategie anche se talvolta sembra mostrare cose poco sensate. La versione Python e' pythonica, ma non insegna a capire tale versione Scheme, per cui serve qualcosa di diverso. Questa e' la traduzione quasi letterale in Python del sorgente Scheme:
def splitmap(el, seq, coll):
  if not seq:
    return coll([], [])
  elif seq[0] == el:
    return splitmap(el, seq[1:],
       lambda s1, s2: coll(s1, seq[0:1] + s2))
  else:
    return splitmap(el, seq[1:],
       lambda s1, s2: coll(seq[0:1] + s1, s2))
(La formattazione e' stata troppo compressa per mantenere corte le righe).
Ricordo che le list Python sono array di riferimenti dinamiche a destra, non liste concatenate semplicemente, per cui tali operazioni di spuntamento e incollaggio sono lente, hanno complessita' computazionale lineare. Comunque questo codice ha fini didattici, per cui e' accettabile. (Comunque anche in Python forse c'e' modo di usare la struttura dati deque della standard library per abbattere tale complessita'. Ma rimarrebbe comunque l'eccesso di ricorsione, che Python non gestisce decentemente).

Tale codice funziona correttamente, ma nessuno scrive codice Python del genere, anche perche' basta una list di poche centinaia di elementi per produrre overflow dello stack (che comunque puo' essere esteso con sys.setrecursionlimit(n)). Nonostante la sua brevita' trovo tale codice solo poco piu' chiaro della versione Scheme, non e' quindi un problema di sintassi familiare o meno.

Un esempio di funzionamento:
splitmap(2, [], lambda x,y: not y)

Qui ho usato una funzione collector, usata anche nel testo, che semplicemente restutisce True se la seconda list e' True. Questo porta ad eseguire il primo then, per cui viene chiamato:

(lambda x,y: not y)([], [])
Che e' True.

Altro esempio:
splitmap(2, [2], lambda x,y: not y) # False

In questo caso viene eseguito il secondo then, per cui viene restituito il risultato della seguente chiamata ricorsiva:

splitmap(2, [], lambda s1,s2: (lambda x,y: not y)(s1, [2]+s2))

Tale chiamata fa eseguire il primo then, quindi equivale a:

(lambda s1,s2: (lambda x,y: not y)(s1, [2]+s2))([], [])
==>
(lambda x,y: not y)([], [2]+[]))
==>
(lambda x,y: not y)([], [2]))
==>
(lambda x,y: not y)([], [2]))
==>
not [2]
==>
False.


Facile, no?
Altro esempio:

splitmap(2, [1], lambda x,y: not y) # True
==>
(lambda s1,s2: (lambda x,y: not y)([1]+s1, s2))([], [])
==>
(lambda x,y: not y)([1]+[], [])
==>
(lambda x,y: not y)([1], [])
==>
not []
==>
True


Altro esempio (e' possibile che qui ci sia qualche piccolo errore):

splitmap(2, [1, 2], lambda x,y: not y) # False
==>
splitmap(2, [2],
  lambda s1, s2: (lambda x,y: not y)([1]+s1, s2)
)
==>
splitmap(2, [],
  (lambda s1, s2: (lambda s1, s2: (lambda x,y: not y)([1]+s1, s2)))(s1, []+s2)
)
==>
((lambda s1, s2: (lambda s1, s2: (lambda x,y: not y)([1]+s1, s2)))(s1, [2]+s2))([], [])
==>
(lambda s1, s2: (lambda x,y: not y)([1]+s1, s2))([], [2])
==>
(lambda x,y: not y)([1]+[], [2])
==>
(lambda x,y: not y)([1], [2])
==>
not [2]
==>
False

Per list piu' lunghe costruire la traccia di esecuzione diventa scomodo e difficile.
Quindi i parametri formali delle lambda vengono usati per memorizzare le due liste che si vanno costruendo, cioe' si usano come closure. Tali funzioni sono innestate una dentro l'altra, e solo la funzione piu' interna e' la collector che gli abbiamo fornito noi, tutte le altre sono state create, ed esse man mano che passano parametri alle funzioni piu' interne costruiscono due parametri-lista via via piu' lunghi. Per cui la collector data lavora sulle due liste complete.
Probabilmente un compilatore Scheme e' in grado di ottimizzare via gran parte di questa roba, producendo un codice sufficientemente efficiente.

Per spirito sperimentale ho testato il programma Python con una lista di 2000 elementi (dopo aver aumentato lo stack limit):
import sys
from random import randint
from memory import memory
sys.setrecursionlimit(10000)
print memory() # 1.7 MB
seq2 = [randint(1, 5) for _ in xrange(2000)]
def count12(x, y):
    print memory() # 18 MB
    return [len(x), len(y)]
print splitmap(2, seq2, count12)
Per funzionare ha richiesto circa 18MB (contro i 1.7 MB usati all'inizio), e circa un paio di secondi.
L'interpete Scheme e' tail recursive e probabilmente per far funzionare tale codice alloca meno memoria.
DrScheme e' uno dei migliori editor per programmi che abbia mai visto, e' capace di fare di tutto, ma e' avido di memoria, per far funzionare un programmino Scheme di poche righe puo' richiede ad esempio 100 MB di RAM.

Comunque anche in Scheme ci sono altri modi funzionali (e ricosivi) per risolvere lo stesso problema senza moltissime lambda, questa versione usa la funzione "apply":
(define (splitter x seq l1 l2)
  (cond
     ((null? seq) (cons l1 (cons l2 '())) )
     ((eq? (car seq) x)
      (splitter x
               (cdr seq)
               l1
               (cons (car seq) l2)
               ))
     (else
      (splitter x
               (cdr seq)
               (cons (car seq) l1)
               l2               
               ))
     )
  )

(define (multico2 a lat col)
  (apply col (splitter a lat '() '())))

(define menu '(ham tuna beer tuna beer food))
(define (count1 x y) (length x))
(multico2 'tuna menu count1) ; Output: 3
(Nota: al posto della "apply" si puo' usare una variabile locale definita con "let" e poi prendene il car  cdr per passarli alla funzione "col".)
Quest'ultimo codice funziona, e' abbastanza efficiente, e' facile da capire, e personalmente la preferisco di gran lunga (specialmente se la funzione splitter venisse inclusa dentro il namespace della multico2 e non nel namespace globale), ma non insegna l'argomento di cui parlava tale capitolo di "The Little Schemer".
comments: Leave a comment Add to Memories Tell a Friend

Tags:, ,
Subject:Add-A-Gram
Time:10:45 pm
This is the solution of a cute programming riddle:
http://www.itasoftware.com/careers/puzzle_archive.html?catid=39#Add-A-Gram

An "add-a-gram" is a sequence of words formed by starting with a 3-letter word, adding a letter and rearranging to form a 4-letter word, and so on. For example, here are add-a-grams of the word "CREDENTIALS":

ail + s =
sail + n =
nails + e =
aliens + t =
salient + r =
entrails + c =
clarinets + e =
interlaces + d =
CREDENTIALS (length 11)

Given the dictionary found here (1.6 MB), what is the longest add-a-gram?


If the link of that dictionary doesn't work you can also use another dictionary, like this smaller local one:
http://www.fantascienza.net/leonardo/so/word_chains/word_chains.zip


My Python solution:
http://www.fantascienza.net/leonardo/js/add_a_gram.zip


The zip file contains:
- add_a_gram.py: the program that solves the problem, with comments, doctests, docstrings, etc. This is the reference implementation, use this to understand the algorithm, etc.
- add_a_gram_short.py: a compact version of the program, without comments, just to show how much short a Python solution can be.
- add_a_gram_SS.py: the solving program adapted and simplified for ShedSkin (http://shedskin.sourceforge.net ), with little comments. This is not the official implementation of this program.


To see how the algorithm works you can see the commented Python code (add_a_gram.py), hopefully it is readable enough. Here is a very approximative explanation. We take all the cleaned words of the file, and we create a dictionary similar to the one used to find anagrams, but for each different signature we keep only the last seen word. Then for every word in the uniquely signed words starting from the longer one (to be sure to find the best solution) we look at all the signatures with a len-1 length, keeping the first one that is present into the dictionary. We stop if we reaach a len=3 word. We backtrack when we can't find a way to reach a len=3 word.
To speed up the program some you can remove the exception management, and use a *fixed len* list instead of a deque, with a pos index that points the current element. I have used a deque because it's a bit simpler (no need of the index, you just do append() and pop()) and this Python programs runs in few seconds on my very old PC, so speed optmizations aren't necessary.

Solution with WORD.LST:
underestimations
underestimation
determinations
antimodernist
terminations
nitrosamine
antinomies
nominates
mentions
tension
nitons
niton
into
ton


Italian solution with my lemmario_italiano.txt (not included):
deresponsabilizzarono
deresponsabilizzaron
deresponsabilizzano
responsabilizzando
responsabilizzano
responsabilizzan
responsabilizza
spersonalizzai
spersonalizza
polarizzasse
piazzassero
piazzasser
spezzarsi
sprezzai
sprizza
spazzi
pizza
aziz
zia
comments: 2 comments or Leave a comment Add to Memories Tell a Friend

Tags:,
Subject:A new museum + what's OOP
Time:11:56 pm
A new museum:
http://www.guardian.co.uk/religion/Story/0,,1946370,00.html
>They had one of the museum's 'scientists' standing next to Adam and Eve's animatronic pet baby T-Rex and explaining that there was no problem with the exhibit since dinosaurs didn't eat meat before the Fall of Man. Presumably the knife-edged teeth were for particularly tough mango skins.<
-------------------------

What's OOP:

>A class is a record with some pointers to functions as record members and which receive the record instance itself as an implicit argument.<

"objects are records of closures" motto actually is folklore, particularly in the functional world.

Anton's old gem:
The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."

Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
comments: Leave a comment Add to Memories Tell a Friend

Tags:
Subject:Links
Time:10:27 am
A very important article on global warming:
http://www.nybooks.com/articles/19131

Interesting notes on the faster languages:
http://scienceblogs.com/goodmath/2006/11/the_c_is_efficient_language_fa.php

vec and valarray seem useful for different kind of things, maybe can be added to ShedSkin too:
http://www.pixelglow.com/macstl/

Ragel State Machine Compiler:
http://www.cs.queensu.ca/home/thurston/ragel/

The molecule of the month is Fibrin:
http://mgl.scripps.edu/people/goodsell/pdb/pdb83
comments: Leave a comment Add to Memories Tell a Friend

Tags:, ,
Subject:Rationals with Scheme
Time:03:24 am
With a friend I'm slowly following the CS lessons by Abelson and Sussman:
http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/
Hopefully we'll see them all.
The lessons seen so far are about really basic stuff, but sometimes you need some brain to follow them, even if you already are a programmer.

The lecture 2b is quite easy, it shows a simple Scheme implementation of rational numbers. But those aren't just programming lessons, the authors try to teach important concepts right from the start. It looks like a crash course :-)
The real topic of this lesson (every video file is made of 3 lessons, so they are about 60 lesson total, but each lesson is just about 20 minutes long, I don't know why they are so short. Sometimes they are so packed that probably a much longer lesson is too much heavy for people just starting CS) was the data abstraction layer, that allows an high-lvel access the part of an object (this time implemented with just functions separated from the data).
Another less evident, but important sub-topic of the lesson was the choice of the correct placing of the gcd computation to simplify the rational. The teacher has shown that it can be put inside the constructor (it's an immutable type), or inside the "methods" (functions) that give numerator or denominator of a given rational. The teacher tells that this is a decision that has to be based on the specific usage of the rationals, it's not easy to chose. I have chosen to put the gcd inside the constructor on the base of a decision that now I think isn't based on solid grounds.

I have implemented the code first in Python, that I know way more. As usual I am using DrScheme, and for this code I've had to use the full language, instead of the "student reduced" one, otherwise I can't do:
(cons 1 2)

I have implemented both the Scheme and Python versions with and without data abstraction layer.

Scheme has the gcd function built in, while Python doesn't even has it in the standard library, this is curious, but it shows that Python is less targeted for numerical/scientific/mathematical purposes.

With Python I have chooses the most natural implementation, that is using a class. So I've had to define a __str__() method too. In the operator methods I haven't used self, but x to simplify the code.

Inside one Python version I have abstracted the data fully, using property() too, so numer / denom are getter properties.

I don't like the prefix syntax of Scheme still, this is the constructor of the rational:
(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g)
          (/ d g))
    )
  )
The postfix syntax of Forth-inspired languages is quite more readable to me still.

As a mnemonic help, to remember the meaning of car and cdr I see their alphanumeric order, the first one takes the first element, the second one takes the second one.

The code:
http://www.fantascienza.net/leonardo/js/scheme_rationals.zip
comments: Leave a comment Add to Memories Tell a Friend

Tags:, , ,
Subject:Algorithm representation
Time:09:44 pm
What's the best way to representing an algorithm? This is an old and widely discussed topic, but it isn't a fully solved problem, Wikipedia has used Python or unspecified pseudocode in the past, and now it encourages the use of a kind of standardised pseudocode. But I think this isn't the best solution.

Now and then I implement algorithms in modern languages, often copying them from articles and books, and sometimes I encounter some problems.

The textual explanations of the algorithm are important, they help me understand what some variables are for, the meaning of certain things done, and so on, but often they are just long demonstrations that the algorithm works as intended, or they are discussions of its computational complexity. Such demonstrations can be very important for an article, and sometimes interesting too, but they may be less necessary if you just trust the author and you just want to implement the algorithm.

In the past I have appreciated pseudocode a lot (I have never appreciated flowcharts much), it looks so simple and easy to understand. But in years I have found some problems implementing algorithms represented as pseudocode. Sometimes it is too much high-level, or it contains things to do that are far from simple, and such things can be done in a slightly different way that breaks the algorithm.

So now I often appreciate algorithms represented in a true programming language, because they are more precise than words, and they are more explicit than pseudocode.

Algol was designed and used for this purpose, many years ago, but today Algol compilers aren't common anymore, so ends used like pseudocode. Some people uses Pidgin Algol too to express algorithms, and sometimes it is readable enough. Functional pseudocode may be readable too, but sometimes it's not easy to implement into a procedural language.

My short answer about the best way to represent algorithms is: if you want to avoid pseudocode and if you have to choose a common enough language, then a well commented, and perfectly and coherently indented Pascal may be the best choice. It's not perfect, but it has some advantages.

Another possibility is to invent a different "testing" computer language with the only purpose of expressing algorithms, it's tempting, it means creating another Algol, but there are so many languages that inventing yet another for just that may be seen as a bit overkill, and it is a far from easy job to do. A group of parallel algorithms may need parallel commands absent in a basic language. An article talking about OOP may need a testing language that supports it. Algorithms about real time sound or graphics, or about device drivers, or 3D cards may need other things, and so on. There are many programming languages because there are many purposes, so it's difficult to invent a computer language able to express most kinds of algorithms. (Maybe it is possible, with few expansions, but it probably requires too much work, and making all people use it looks even more difficult). There are people that like to design new languages, like Wouter van Oortmerssen, that has created thirty of them for the Amiga computer too, they may find this like an interesting challenge.)

Pascal may be not perfect, but it was common enough to allow you to find free compilers for most operating systems.

Some of the qualities needed by such language:
- It has to be used to understand algorithms 30 or more years after they are written, so such language can't change much in time. (Languages like Python change too much fast for this.)
- It's better if it doesn't use symbols or complex constructs, it must spell most things explicitly, be regular and coherent, and simple. Some verbosity is necessary. (Pascal has a slightly incoherent management of begin/end and semicolons. Obviously it's not really incoherent, but sometimes from human eyes it doesn't look fully explicit. Compulsory semicolons and maybe even compulsory begin-end are better, they make code less compact, but more explicit for human eyes. C and Python languages uses too much symbols. Python has too much unusual functionality with subtle semantic. Python booleans can be used as integers. Python variables aren't listed explicitly at the beginning of the program, and you don't know their true type, and you can't specify the machine types you may need in the algorithm.)
- Indentation is very important, it's better if it is enforced by the compiler, because I have seen a lot of algorithms coming from very intelligent people written with wrong, ugly or incoherent indentations.
- Comments and variable names must be in English, and they must be readable and explicit. Variable names usually have to be 2 letters long or more.
- The algorithm has to be written in a txt document, and not in PostScript, PDF, etc. files, because copying it manually can introduce many errors. 7-bit ASCII with 2 or 4 spaces indentations is the best, it allows all kinds of successive processing and use.
- The language has to be synthetic because the shown code is often 10 lines long and you don't have much space to print it. (So Java and C# aren't good choices.)
- OOP can be useful, but often the code is short, so objects can make code less simple to understand and less simple to translate to no OO languages.
- A pure functional language isn't fit for this purpose, mostly because many languages aren't functional. Translating functional code to procedural one can require some skills. Forth, Lisp, K, and others are unfit languages, because of various problems.

After a first screening the most fit languages may be:
Ada Algol Basic C C C# C++ Fortran Java JavaScript Lisp Pascal Perl Python Ruby Scheme

But:
- Ada can be good, but isn't synthetic enough, and not common enough.
- C and C++ are too much low level, they use a too many strange symbols, and their semantic is often not explicit enough. The advantage of C is that you can find a free working compiler for most computers.
- Fortran isn't used much anymore (except some numerical fields), and old versions are too much low-level.
- JavaScript, Lisp and Scheme don't have a mainstream enough syntax.
- Perl isn't clear enough, its syntax isn't explicit enough.
- Ruby is may be less readable than Python. (But its closing ends are probably cleaner)
- Oberon, Algol, Simula, Nice, and many other languages aren't fit.
- C# is similar enough to Java, so Java is enough, and more common.
- For Algol it's not easy to have a compiler, and the language is too much limited and raw.
- Old Basic is too much raw and low level, and modern ones aren't standard enough.
- Java is well known, widely used, its syntax is quite readable and uniform. But it doesn't have functions, it uses too much OOP from the beginning, and algorithm code tends to become too much long.
- Pascal is a bit too much low level, its management of semicolons and begin-end labels can sometimes have a low readability. A correct indentation isn't enforced (as a good variable naming, but this isn't easy to enforce).
- Python doesn't have built-in multidimensional arrays, the language contains some too much complex and non standard ideas, the lack of ending labels may cause some problems and may become unclear when printed without vertical lines that show indentation levels. It uses too much symbols (to compute the module, for bitwise operations), it doesn't allow you to use unsigned bytes or short integers, or mutable strings, etc, that in some algorithms can be necessary.

So pseudocode, Pascal and Python seem the best choices, but they aren't perfect, there are ways to improve them if you want to use one of them:

1) For the pseudocode it's good to have a manual or reference. It is quite positive to use a mostly standardised pseudocode like Wikipedia is trying to do. And in the end you may even find a way to cheek for the syntax of such code automatically. It's also positive to write it in an explicit way, and to not put too much complex operations inside the code. If the algorithm becomes too much long you can call some separated sub-functions.

2) Python can be used, but its use requires some work and many attentions. The purpose is to use just a (working) subset of Python with a cleaner semantic and simper to implement in less flexible languages:
- Do not use most things that make Python different or better. No generators, decorators, iterators, little or no OOP, no lambdas, no functional programming, no oneliners, no slicing, no docstrings, no enumerate, no most of the stdlib, little or no operator overloading, little or no dynamism in lists usage,
- calling lists "arrays".
- Using user-defined functions with explicit names to do sgn, mod, raw_input, bitwise operations, a function that returns multidimensional lists (maybe managed with numarray-like modules, or as dicts, so you can use the comma to separate the indexes).
- Extensive use of parentheses, not relying on the operator precedence.
- Not relying on the integer meaning of booleans, and on the un-bool/int returned by or/and operators.
- Commenting code a bit, and using explicit names (variables), usually longer than just one letter.
- Using mutable strings when necessary or more clear.
- All such functions and classes created for the expression of algorithms can be distributed for free, from sourceforge or from some other well known and stable site(s).
- Being clear what kind (integer of floating point division to use. The \\ is preferred, as the truedivision from future, if needed).
- Sort and sorted are allowed if their meaning is clear.
- No complex string formatting.
- No ternary if-else expressions and with (present in Python 2.5).
- Complex numbers can be accepted, if useful and if they are used in an explicit way.
- Python multiprecision integers too can be used if their type can be explicitly and easily known. Bitwise operations on them has to be avoided, because the semantic isn't always clear.
- #endif, #endwhile, #endthen, etc, can be used to denote the ends of blocks in a more explicit way. Such ending tags can be used (by a program looking for lines whose first four noblank chars are #end) to recreate the exact original program if all leading spaces are removed from the code.
- range/xrange functions are left open, and lot of people that don't know Python ignore this. So instead of xrange/range yop have to use an interval(a, b) function, that yields integer numbers in a closed [a, b] interval, plus a inverseInterval (or something with a better name) for decrementing iteration on a closed interval. Both such functions require exactly two values. If you want, you can also define a character interval.
- At the beginning of the code of at the beginning of functions inside comments you can put a list of the used variables, plus their type.
- Future Python versions may accept case/switch, and do-while too, they can be accepted, their meaning is clear enough.
- A checker program can probably be applied too on the source code to verify that such coding rules are respected.

3) Pascal looks like a better choice, even if today it's not used anymore. You just have to enforce few things:
- Normal good coding standards, compulsory semicolons, like exact indentation (Python helps you to learn to do it), good variable naming, comments, spaces, coherent indentation style, etc.
- few higher-level functions like sort, matInverse, string functions, etc., etc., can be used (and defined elsewhere).
- A checker program can probably be applied too on the source code to verify that such coding rules are respected.
- Usual limitations of some older Pascals can be dropped (in string and array length, etc).


Few references:

http://en.wikipedia.org/wiki/Pseudocode
http://en.wikipedia.org/wiki/ALGOL
http://en.wikipedia.org/wiki/Pidgin_Algol
comments: Leave a comment Add to Memories Tell a Friend

Tags:,
Subject:Python Undo
Time:07:31 pm
In un recente blog post [ http://leonardo-m.livejournal.com/11619.html ] ho elencato alcune cose di basso livello presenti in Python. Per creare un linguaggio di livello piu' alto ispirato al Python si potrebbe pensare di aggiungere l'Undo. Non userei un programma di editing testuale, audio o grafico senza Undo, per cui mi pare almeno concepibile un Undo anche per un linguaggio di scripting.

Sarebbe utile poterlo avere almeno durante l'uso della shell interattiva. L'undo degli script e' meno essenziale (anche se puo' comunque essere utile, ma avere un Undo che annulla l'esecuzione dell'intero script spesso sarebbe gia' sufficiente).

Comunque implementare un Undo per Python potrebbe non essere facile. Potrebbe memorizzare solo uno o pochi livelli di Undo. Se la RAM non dovesse bastargli potrebbe appoggiarsi automaticamente ad un file di Undo, come fanno i programmi di grafica o di elaborazione di audio digitale. Quando si modifica una grande struttura dati potrebbe salvare solo la parte modificata, come fanno anche PaintShopPro, Photoshop, ecc.

Cosa *sia un livello di Undo* in un linguaggio di programmazione e' cosa su cui riflettere, non mi pare che si possa definire immediatamente. Se si limita l'Undo alla sola shell (per cui gli script non avrebbero Undo) credo che un livello di Undo possa essere definito come cio' che viene eseguito quando un utente ha finito di inserire un blocco di qualcosa e preme invio; in tal caso credo sia fattibile.

Come al solito non sono stato il primo a pensarci:
http://www.python.org/workshops/1997-10/proceedings/zukowski.html
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/306866

Adesso andrebbe implementato in modo standard, e rendere il tutto trasparente almeno nell'uso da shell :-)
comments: Leave a comment Add to Memories Tell a Friend

Tags:,
Time:01:59 am
This is the answer to this, by [info]11011110

Thank you for your comment. Sorry for writing it in Italian, it is just some blabla, so I have thought it wasn't interesting enough to translate it to English.


>If you want true multidimensional indexing (rather than lists of lists) and aren't so concerned about efficiency it might be simplest to use a dict. E.g. A={}; A[1,2]=3.<

I am using Python for more than a year now, so I know all such tricks; but I think efficiency is important, in space and time, so such solution with dict of tuple keys is good for small problem only.
Boo language has both typeless lists, and builtin typed multidimensional arrays, it is more efficient. Python has linear typed arrays in the standard lib, that sometimes Psyco uses very quickly. I don't know still how Boo manages without immutable tuples, this is a small test with Boo, it's strange, no errors raised, etc:

Enter boo code in the prompt below.
>>> d = {}
{}
>>> l = ["a", 1, 1.5]
['a', 1, 1,5]
>>> d[l] = 1
>>> d
{['a', 1, 1,5]: 1}
>>> l[1] = 2
>>> d
{['a', 2, 1,5]: 1}
>>> d[1]
>>> print d[1]

>>> d[1] = 2
>>> print d[1]
2
>>> print d[l]
>>> d
{['a', 2, 1,5]: 1, 1: 2}


>Immutable strings are necessary if you want to be able to use them as dictionary indices. Though, the same argument would apply as well to sets, and yet the built in set is mutable...<

Python 2.4 has frozensets (Python 2.3 has them in a library):

>>> d  = {}
>>> s1 = set([1, 2])
>>> d[s1] = 5
Traceback (most recent call last):
...
>>> s2 = frozenset([1, 2])
>>> d[s2] = 5
>>> d
{frozenset([1, 2]): 5}
>>> 2 in s2
True
>>> s3 = set(s2)
>>> s3.add(3)
>>> s3
set([1, 2, 3])
>>> d
{frozenset([1, 2]): 5}

If you care of efficiency you may have two string types, one mutable and one immutable, just like sets, with the ability to convert from one type to the other.
If you don't care too much of efficiency, they maybe you can find a way to quickly find mutable structures too, maybe with some kind of search tree instead of a hash. It may be a quite slow mess, but mutating strings seems a quite "natural" thing to do (but now I don't feel often the need to do it, and I can use python arrays of chars for that purpose).

Mathematica solves the problem in another way, here l is a mutable structure, a list. The d[0] defines a entry in the global hash for the function-symbol d, when applied to the value 0.
Then I change an element of l, and d[0] keeps working, because it doesn't contain a pointer to l (like in Python), the association is with the symbol l, so it works associating it with what's called l at that time. Late binding doesn't fit much in the Python language philosophy, but it can be useful.

In[1]:= l = {1, 2};
In[2]:= l
Out[2]= {1, 2}
In[3]:= d[0] := l
In[4]:= ?? d
     "Global`d"
     d[0] := l
In[5]:= d[0]
Out[5]= {1, 2}
In[6]:= l[[1]] = 10
Out[6]= 10
In[7]:= l
Out[7]= {10, 2}
In[8]:= d[0]
Out[8]= {10, 2}
comments: Leave a comment Add to Memories Tell a Friend

Tags:,
Subject:Python e livello linguaggi
Time:11:18 pm
Oggi di solito si dice che il linguaggio C e' di basso livello; esso contiene molte trappole e cose a cui dover fare attenzione, queste sono alcune di esse:
http://www.andromeda.com/people/ddyer/topten.html


Python viene considerato ad alto livello, ma anch'esso contiene cose di basso livello, difetti, o trappole, eccone alcune:

- iterare su una sequenza che si sta mutando.
- mettere lista tra i parametri di una funzione.
- niente supporto builtin array multidimensionali.
- giochi e trucchi con "puntatori", che non si vedono ma ci sono; con le liste spesso non ci sono veri assegnamenti. Se ci fossero veri assegnamenti la semantica sarebbe piu' facile da capire.
- se gli operatori sui bit si chiamassero AND, NOT, XOR, OR, sarebbero piu' facili da ricordare di simboli arbitrari.
- formattazioni stringa 5 sono hanno una sintassi di basso livello.
- niente possibilita' di definire pezzi di codice "statico" veloce piu' o meno come il C, utile anche al posto del codice vettoriale (usato con numarray, ecc). Questo porta alla creazione di molte soluzioni parziali, scomode, inaffidabili, e diverse tra loro.
- la sintassi del range/xrange non e' bella per niente.
- avere le stringhe immutabili puo' non essere l'ideale.
- la grafica e' poco nativa, e lenta, e scomoda e non antialesata. L'uso di grafica e audio dovrebbero essere nativi, antialesato, veloce, ecc.
- rappresentazione numeri ottali, ecc, e' una trappola.
- mancanza floating point a precisione multipla.
- tipo decimal non di default o builtin.
- la sintassi dei decoratori e' scadente.
- l'uso di super() e altre cose affini non e' facile, e ha trappole.
- Psyco non e' built-in.

I seguenti difetti forse verranno corretti in parte nel Python 3.0:

- stringhe unicode di default, ma sequenze di byte disponibili
- il comando printraw (o simili) potrebbe non mettere gli spazi e accapi.
- input al posto di raw_input.
- niente do-while, case-do, ecc.

Linguaggio ad alto livello significa anche che e' costruito per chi programma, e non per il computer.
Un Python senza queste e altre trappole sarebbe piu' facile per i principianti, cioe' sarebbe di livello piu' alto, anche se forse sarebbe un po' piu' lento (ma l'aggiunta di Psyco e del codice statico potrebbe risolvere parte del problema). Forse un giorno verra' creato.
comments: 2 comments or Leave a comment Add to Memories Tell a Friend

Tags:,
Subject:Albero Trie in Python - Trie tree in Python
Time:05:05 pm
http://www.fantascienza.net/leonardo/so/index.html#trie
comments: Leave a comment Add to Memories Tell a Friend

leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:User Info.
View:Website (My Website).
You're looking at the latest 10 entries.
Missed some entries? Then simply jump back 10 entries