Tag: tutorial
La Ricorsione : stack e gestione delle procedure
Argomenti trattati :
# Stack
# Chiamate di procedure
# Ricorsione
Conoscenze minime :
# Un pò di C
# Concetti di programmazione
Inizio :
Come sappiamo,un programma in C per essere eseguito deve essere prima compilato,cioè tradotto in linguaggio macchina equivalente. Oggi voglio accennarvi brevemente ( per ora ) al modo in cui vengono gestite dal compilatore le chiamate di procedure,in tal modo capiremo meglio i problemi da affrontare e come sia vitale per la soluzione l'utilizzo di una struttura dati,lo stack.
Supponiamo che un a procedura Main chiami a un certo punto una procedura A1,la quale chiama a sua volta A2, la quale infine chiama A3. Possiamo schematizzare la situazione come segue :
CODE:
-
---------------
-
| proc. Main |
-
| - |
-
| - |
-
| call A1 |
-
| r: |
-
| - |
-
| - |
-
| return |
-
---------------
-
-
---------------
-
| proc. A1 |
-
| - |
-
| - |
-
| call A2 |
-
| s: |
-
| - |
-
| - |
-
| return |
-
---------------
-
-
---------------
-
| proc. A2 |
-
| - |
-
| - |
-
| call A3 |
-
| t: |
-
| - |
-
| - |
-
| return |
-
---------------
-
-
---------------
-
| proc. A3 |
-
| - |
-
| - |
-
| - |
-
| - |
-
| - |
-
| - |
-
| return |
-
---------------
Quando A3 termina la sua esecuzione l'istruzione che deve essere eseguita è quella,nella procedura A2, successiva alla chiamata A3 e di indirizzo t. Quando A2 termina,l'istruzione successiva deve essere quella di indirizzo s, e infine quando A1 termina va eseguita l'istruzione di indirizzo r.
I ritorni avvengono dunque in ordine inverso alle chiamate.
E' perciò importante che quando vengono chiamate le procedure gli indirizzi di ritorno vengono salvati in un recipiente da cui verranno prelevati in ordine inverso a quello di inserimento. Questo recipiente prende il nome di stack ed è una struttura dati cioè un oggetto su cui sono lecite operazioni particolari.
Uno stack viene anche detto una struttura LIFO ( Last In First Out ) in quanto l'ultimo elemento inserito nello stack è il primo ad uscire. Inizialmente lo stack è vuoto,quando la procedura Main chiama A1,l'indirizzo di ritorno r viene inserito ( push ) nello stack,quando A1 chiama A2 push dell'indirizzo s,quando A2 chiama A3 push di t. Lo stack durante l'esecuzione di A3 è il seguente :
CODE:
-
-----------
-
| t |
-
| s |
-
| r |
-
-----------
Nel momento in cui A3 termina viene prelevato ( pop ) dallo stack l'indirizzo che sta in cima ( top ) e va in esecuzione l'istruzione di indirizzo t. Quando A2 termina,pop di nuovo e va in esecuzione l'istruzione di indirizzo s,quando termina A1,pop ancora e va in esecuzione l'istruzione r.
Ogni volta che va effettuato un return,l'indirizzo a cui tornare si trova al top dello stack.
Ora passiamo ai progammi ricorsivi. Un programma è detto ricorsivo diretto se viene chiamato all'interno del programma stesso. Un programma F1 è detto ricorsivo indiretto se chiama un programma F2,che chiama a sua volta F3,e così via,finchè Fk chiama F1. Spesso si pensa che è più semplice programmare senza la ricorsione ( infatti molti linguaggi di programmazione non la permettono ) ed è vero in MOLTI casi. Spesso però la versione ricorsiva di un programma è più compatta e facile da capire. Il motivo più importante per usare la ricorsione è che vi sono problemi che sono più facilmente risolvibili utilizzandola.
Per farvi capire meglio,vi mostrerò forse il programma ricorsivo per eccellenza : Il fattoriale.
Possiamo scrivere una semplice funzione C di fattoriale in questo modo :
C:
-
int fact(int n)
-
{
-
if (n==1)
-
return 1;
-
else
-
return n*fact(n-1);
-
}
per capire però bene il meccanismo di ricorsione scriviamo la funzione in modo meno compatto,utilizzando un'altra variabile. I passaggi risultano in tal modo più chiari:
C:
-
int fact(int n)
-
{
-
int k;
-
if (n==1)
-
return 1;
-
else
-
k=fact(n-1);
-
return n*k;
-
}
ed ecco cosa succede eseguendo l'istruzione fattor=fact(3) :
CODE:
-
livello n k return
-
--------------------------------
-
1 3
-
2 2
-
3 1 1
-
2 2 1 2
-
1 3 2 6
Per effetto della chiamata,si entra per la prima volta nella funzione,n vale 3: poichè n non vale 1, la funzione viene chiamata una seconda volta con l'istruzione fact(n-1). Il parametro attuale vale (3-1)=2 per cui,quando entro nella funzione,n vale 2. Chiamo pertanto per la terza volta la funzione con l'istruzione fact(n-1), questa volta il parametro attuale vale (2-1) = 1. Riassumendo,le tre chiamate sono :
prima : fattor = fact(3);
seconda : k = fact(n-1) ( n vale 3 per cui (n-1)=2)
terza : k = fact(n-1) ( n vale 2 per cui (n-1)=1)
quando entro per la terza volta in fact,n vale 1 per cui esco subito dalla funzione restituendo il valore 1,torno all'ultima chiamata fatta,cioè la terza, e il valore 1 viene assegnato a k. Nel contempo,n automaticamente riassume il valore che aveva all'atto della terza chiamata(2).
Va quindi in esecuzione l'istruzione return n*k e viene restituito il valore 2*1=2. Si torna ora all'ultima chiamata fatta,cioè la seconda,k assume il valore 2 e n automaticamente riassume il valore 3. Va ora in esecuzione return n*k e viene restituito il valore 3*2=6. Si torna all'ultima chiamata fatta,questa volta è la prima,fattor = fact(3),e il valore 6 viene assegnato a fattor.
Vi ho mostrato la gestione delle chiamate di procedure mediante stack. Nel momento in cui abbiamo programmi ricorsivi le cose si complicano grandemente : infatti all'atto della chiamata ricorsiva oltre all'indirizzo di ritorno vanno salvati tutti i valori dei parametri in quel momento,e tali valori ripristinati al momento del return.
Per questo,anche se a volte sembra che ci " convenga " usare la ricorsione,dobbiamo stare attenti.
Programmi ricorsivi complessi richiedono il salvataggio di tutto un set di parametri per un numero di volte che dipende dal numero di livelli di ricorsione,questo complica molto il lavoro del compilatore per cui molti linguaggi di programmazione,come già detto,hanno " risolto " il problema alla radice non consentendo l'uso della ricorsione.
Questo è solo una prima parte,alla prossima,ciao !
Scroll boxes
Il titolo forse non è dei più immediati, ma vorrei presentare delle proprietà degli elementi HTML utilizzabili con Javascript per creare degli scroller personalizzabili o automatici ( classico box delle news a scorrimento continuo ) o quant'altro preveda il movimento di un blocco scrollabile.
Innanzitutto presentiamo le proprietà degli elementi HTML che utilizzeremo negli script.
clientHeight
Proprietà in sola lettura che ritorna il numero di pixels dell'altezza interna di un elemento, incluso il padding ma escluse l'altezza della scrollbar, del bordo o del margine.
JavaScript:
-
var element = document.getElementById(id);
-
var height = element.clientHeight;
clientWidtht
È il corrispettivo di clientHeight ma per la larghezza interna di un elemento.
JavaScript:
-
var widht = element.clientWidtht;
scrollHeight
È una proprietà in sola lettura che restituisce il numero di pixels dell'altezza di un elemento relativa al layout, quindi comprensiva di padding e bordi.
JavaScript:
-
var scrollHeight = element.scrollHeight;
scrollWidth
È il corrispettivo di scrollHeight ma riguardante la larghezza un elemento.
JavaScript:
-
var scrollWidth = element.scrollWidth;
scrollTop
È una proprietà in lettura e scrittura che può assumere un valore qualsiasi intero positivo rappresentate la distanza in pixel tra il lato superiore e la prima parte visibile dell'elemento countenuto.
JavaScript:
-
var scrollTop = element.scrollTop;
scrollLeft
È il corrispettivo di scrollHeight ma riguardante la larghezza un elemento.
JavaScript:
-
var scrollLeft = element.scrollLeft;
Schema riassuntivo
Note: le proprietà presentate sino ad ora sono state introdotto dal object model di MSIE, quindi non sono nè una specifica nè una raccomanandazione W3C. In ogni caso sono implementate anche dal render Gecko ( Firefox, Mozilla, Netscape, etc. )
Queste proprietà si applicano a numerosi elementi, per avere maggiori dettagli consultate pure la MSDN DHTML library
Form highlighting
Dopo l'autofocus, altro script a mio parere utilissimo è quello dell'highlighting degli input field e delle textarea, ovvero un semplice meccanismo javascript + css che permette di evidenziare il campo della form attualmente in uso. Vi propongo una funzione sviluppata in maniera che sia abbastanza adattabile ai diversi casi.
JavaScript:
-
window.onload = function(){
-
/*applico l'highlight a tutti i campi di input*/
-
var inputFields = document.getElementsByTagName("INPUT");
-
for(i=0; i<inputFields.length; i++){
-
var field = inputFields.item(i);
-
if ( field != undefined){
-
if ( field.type=="text" || field.type=="password" ){
-
/*onfocus cambio la classe corrente con quella focus*/
-
field.onfocus = function(){this.className="focus";}
-
/*onblur ripristino la classe di default*/
-
field.onblur = function(){this.className="";}
-
}
-
}
-
}
-
/*stesso vale per le textarea*/
-
var textareas = document.getElementsByTagName("TEXTAREA");
-
for(i=0; i<textareas.length; i++){
-
var textarea = textareas.item(i);
-
textarea.onfocus = function(){this.className="focus";}
-
textarea.onblur = function(){this.className="";}
-
}
-
}
Chiaramento a questo script va assocciato un opportuno foglio di stile con almeno una classe focus.
CSS:
-
input.focus{
-
border: 1px solid #a00;
-
}
-
textarea.focus{
-
border: 1px solid #a00;
-
}
-
input, textarea{
-
padding: 1px;
-
background-color: #eee;
-
border: 1px solid #999;
-
}
Visto che sostenere l'utilità di questi script può essere discutibile, vi propongo un esempio completo di una tipica form di contatti.
N.B: Questi script non trattano campi del tipo checkbox, ma in quel caso bisognerebbe studiare una soluzione ad hoc che evidenzi l'intera area contente tutti i radio button o checkbox e non il singolo, poichè la check box o i radio button sono uno o più valori per un campo.
Testato su:
Firefox 2.0.0.3 (Linux)
Mozilla 1.7.13 (Linux)
Epiphany 2.16.1 (Linux)
Galeon 2.0.2 (Linux)
IE 6.0 (Linux)
tips and tricks per la stampa: la Ribattuta
La "Ribattuta" è un metodo che viene usato da molti per far risaltare un testo (spesso bianco) su sfondi di colore omogeneo, o per lo più tale.
La cosa in sà© è molto semplice perchà© consiste nel riscrivere il testo a cui vogliamo dare importanza.
Creiamo un file (sia in InDesign che in Photoshop) a cui daremo uno sfondo in linea con quanto detto all'inizio.
Inseriamo il testo che dovrà comparire.
Applichiamo la "ribattuta" che non è altro che ribattere, da qui il nome, in un colore più scuro (in questo caso nero) il testo a cui vogliamo dare più importanza, metterlo in secondo piano rispetto al primo e spostarlo di un pixel verso destra e verso ilbasso.
Così facendo sia a video, che soprattutto a stampa, il testo ribattuto avrà un senso di profondità che lo farà emergere rispetto al resto "attirando" l'attenzione nel punto desiderato.
Autofocus e form usability
Leggendo l'articolo di Diego, Accessibilità ed usabilità nelle form, mi sono risorte in mente alcune questioni sulle form che reputo interessanti.
Prima fra tutte l'autofocus, uno script muove il cursore dell'utente direttamente su uno specifico campo di input al caricamento della pagina, come avviene in Google. Per il form proposto nell'articolo sopra citato lo script sarebbe:
JavaScript:
-
/*window.onload equivale all'evento onload del tag body*/
-
window.onload = document.forms[0].s.focus();
I problemi sorgono in quelle pagine in cui convivo più forms, spesso per esempio una form di login e una di ricerca. Capita quindi che l'utente vorrebbe autenticarsi, lo script sposta il cursore sul campo di ricerca e l'utente finito di digitare lo username compone la password, così oltre alla perdita di tempo si aggiunge magari la vista in chiaro della password nel campo di ricerca. Per risolvere questo problema riporto uno script che ho ritoccato in modo da renderlo più generico.
JavaScript:
-
window.onload=function(){
-
var isfocused = false;
-
/*ottengo tutti i tag input della pagina HTML*/
-
var inputFields = document.getElementsByTagName("INPUT");
-
/*scorro con un ciclo for ogni elemento della nodeList*/
-
for(i=0; i<inputFields.length; i++){
-
var current = inputFields.item(i);
-
/*considero solo gli elementi definiti e di tipo text*/
-
if(current != undefined){
-
if(current.type == "text" || current.type == "password")
-
{
-
/*controllo se nessun valore è stato cambiato*/
-
if(current.value != current.defaultValue){
-
isfocused = true;
-
}
-
}
-
}
-
}
-
var textarea = document.getElementsByTagName("TEXTAREA");
-
for(i=0; i<textareas.length; i++){
-
var current = textareas.item(i);
-
if(current !== undefined){
-
if(current.value != current.defaultValue){
-
isfocused = true;
-
}
-
}
-
}
-
/*se nessun valore di default cambia scatta l'autofocus*/
-
if(!isfocused){
-
inputFields.item(0).focus();
-
}
-
}
Testato su:
Firefox 2.0.0.3 (Linux)
Mozilla 1.7.13 (Linux)
Epiphany 2.16.1 (Linux)
Galeon 2.0.2 (Linux)
IE 6.0 (Linux)
Accessibilità ed usabilità nelle form
Dopo aver visto come creare e far funzionare un semplice motore di ricerca, ora vedremo, usando pochi accorgimenti, come renderlo accessibile via codice HTML.
Form iniziale:
HTML:
Il fatto di usare solo elementi strutturali usando l'elemento "fieldset" aiuta sicuramente l'interpretazione della pagina da parte dei browser testuali e tecnologie assistive. L'elemento "legend" servirà a dare un nome ai vari gruppi della form. Nel caso specifico avremo bisogno di un solo "legend".
HTML:
-
<legend>Modulo di Ricerca</legend>
-
</fieldset>
Occorre associare delle etichette (label) significative ai relativi input e legarle con l'attributo "for" al corrispettivo "id" dell'input.
Occorre controllare, soprattutto in caso di form molto complesse, che vi sia un ordine logico e che questo possa essere seguito anche attraverso la navigazione da tastiera spostando il focus delle azioni con il tasto "tab". Per far questo useremo l'attributo "tabindex".
HTML:
Per far si che le "input" siano accessibili anche usando le combinazioni dei tasti di scelta rapida, daremo loro l'attributo "accesskey" indicando nel label corrispettivo la lettera tra parentesi quadre.
HTML:
NB: IE: tasto ALT + numero o lettera tra parentesi + INVIO. FF: ALT + SHIFT + numero o lettera tra parentesi. Apple: componendo la combinazione del tasto CMD ("tasto mela") + numero o lettera tra parentesi.
Quindi il risultato finale del nostro semplice form sarà :
HTML:
Per approfondire:
10 useful links
A List Apart
http://www.alistapart.com/
[For people who makes websites.]
Accessibility101
http://accessibility101.org.uk/
[Accessible Website Design by Shaun Anderson.]
css Zen Garden
http://www.csszengarden.com/
[A demonstration of what can be accomplished visually through CSS-based design.]
Design Meltdown
http://www.designmeltdown.com/
[Design elements, trends, and problems in web design.]
Dexigner Design Portal
http://www.dexigner.com/
[Is the leading online information service for designers and artists.]
Good-Tutorials.com
http://www.good-tutorials.com/
[Good-Tutorials.com lists 13,180 and more Adobe Photoshop tutorials.]
Ideasonideas
http://www.ideasonideas.com/
[Is a blog that invites dialogue on issues relevant to communication designers and brand strategists]
Netdiver
http://www.netdiver.net/
[Digital culture magazine + new media design portal.]
WhatTheFont
http://www.myfonts.com/WhatTheFont/
[Upload a scanned image of the font and instantly find the closest matches.]
Will the browser apply the rule(s)?
http://centricle.com/ref/css/filters/
[Browser rules.]
