| ||||||||
| Scheme lists (as the list of Python) can contain any kind of S-expression/object, it suffices to have the sub-expressions correctly written and the brackets balanced: ("hi" ((((1 2 3 (4))))) 42/7) What kind of data structures we may have if we allow unbalanced brackets too, like for example: ((1 2) It may be like a strange way to represent partially undefined trees. For simplicity we can hypothesise that to obtain all the defined trees from that undefined representation we can only add closed brackets, then that may represent any of: ((1) 2) ((1 2)) That is: +--+ | 2 + 1Or: +--+ | | + + 1 2A way to represent multiple or partially undefined structures may be useful for various purposes (like to express a situation of partial approximation, or to represent a double meaning of natural words, or something like the Koans, where few ideograms can be read in few different ways with different meanings, etc), but this time I haven't found a way to use them for something practical still. --------------------------- Le liste Scheme (come le list Python), possono contenere ogni tipo di oggetto, e' sufficiente che gli atomi siano scritti correttamente e che le parentesi siano bilanciate: ("hi" ((((1 2 3 (4))))) 42/7) Che tipo di struttura dati si avrebbe se si permettessero anche scritture con parentesi non bilanciate, ad esempio: ((1 2) Potrebbe essere un modo strano per rappresentare alberi parzialmente indefiniti. Se per semplicita' ipotizziamo che per ottenere tutti gli alberi definiti a partire da una tale rappresentazione indefinita si possano aggiungere solo parentesi chiuse, allora tale espressione potrebbe rappresentare una qualunque di: ((1) 2) ((1 2)) Cioe': +--+ | 2 + 1Oppure: +--+ | | + + 1 2Avere modi per rappresentare strutture "multiple" o parzialmente indefinite e' potenzialmente utile per vari scopi (potrebbe essere un modo per esprimere una situazione di parziale approssimazione, o per rappresentare qualcosa di simile ai giochi di parole cioe' a dei doppi sensi matematici, o ai Koan dove degli ideogrammi hanno significati multipli, ecc), ma in questo caso non sono ancora riuscito a trovare una possibile applicazione pratica. | ||||||||
comments: Leave a comment   |
leonardo
|
|||||||||||||
March 24th, 2007
March 15th, 2007
| ||||||||
| 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 |
October 2nd, 2006
| ||||||||
| With a friend I'm slowly following the CS lessons by Abelson and Sussman: http://swiss.csail.mit.edu/classes/6.00 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/leonard | ||||||||
| comments: Leave a comment |
leonardo
|
|||||||||||||