Autore Topic: Idee e spunti per una calcolatrice - Parte Software  (Letto 21907 volte)

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Idee e spunti per una calcolatrice - Parte Software
« il: 31 Marzo 2015, 11:21:15 »
Per discutere la parte HARDWARE il topic è questo: http://www.nonsoloamiga.com/index.php?topic=3115


Ciao ragazzacci,

butto giù un po' di spunti e idee per la calcolatrice che sto sviluppando nel tempo libero. Discussione aperta a suggerimenti di ogni tipo!
Per facilitare l'implementazione su sistemi embedded ho iniziato lo sviluppo in due moduli principali: MathLang e un client testuale.
MathLang è una libreria statica in C++ puro (variante C++11), mentre Text Client è solo un aggancio lato console per inviare comandi (sotto forma di script) e ricevere risposte (come stringhe).

Una volta che l'engine sarà a buon punto sarà possibile creare un client diverso, magari con una bella grafica, adatto al dispositivo di destinazione.
MathLang è composto a sua volta da due parti principali: ScriptEngine per parsare ed eseguire gli script e MathEngine per l'esecuzione delle operazioni matematiche elementari.

A partire da uno script viene generato un albero ordinato (a parità di parent, i figli sono ordinati da sinistra a destra), dove ogni nodo è uno Statement e ogni statement a sua volta può essere un albero o una foglia.

BlockStatement, CallFunctionStatement, ReturnStatement, LoopStatement e ConditionalStatement sono alberi, mentre DefinitionStatement, AssignmentStatement sono foglie.
ScriptEntity rappresenta le entità più semplici (StringEntity, FunctionEntity, RealEntity, MatrixEntity, BooleanEntity, ListEntity, ecc...) e viene usata come classe base per gli argomenti e i tipi di ritorno delle Function.

Lo Script minimale è costituito da uno Statement, uno ScriptEnvironment, una lista di ScriptEntity (gli argomenti) e almeno un ReturnStatement. Lo script quindi rappresenta il concetto matematico di funzione.

Statement è la classe base che rappresenta i comandi elementari.
ScriptEnvironment è una mappa key-value di stringhe vs ScriptEntity. Contiene le variabili locali e gli argomenti della chiamata a funzione. Non esistono variabili globali.
DefinitionStatement rappresenta la definizione di un simbolo all'interno dello ScriptEnvironment () e la sua inizializzazione
AssignmentStatement rappresenta l'assegnazione di una nuova Entity dello stesso tipo o di un tipo compatibile rispetto a quello con cui è stata definita nell'Environment (se definisco una stringa e poi assegno un intero si incazza).
BlockStatement è un array di Statement.
CallFunctionStatement prende 2 parametri: FunctionEntity da chiamare e ListEntity per gli argomenti (possono essere a loro volta delle FunctionEntity). La FunctionEntity fa riferimento ad un nuovo script
ReturnStatement prende 1 parametro: ScriptEntity (classe base) da restituire al chiamante dello script
LoopStatement prende come parametri 3 oggetti: ScriptEntity contatore, ListEntity con i possibili valori da assegnare al contatore, Statement come corpo del loop
ConditionalStatement prende 3 parametri: BooleanEntity che è la condizione, Statement per il ramo IF e un altro Statement per il ramo ELSE

I vari tipi di ScriptEntity sono:
StringEntity: incapsula il concetto di stringa e le operazioni su di essa
FunctionEntity: incapsula il concetto di funzione, fa riferimento ad un nuovo Script, che possiede quindi un proprio Environment privato.
RealEntity: incapsula i numeri reali (double precision)
IntegerEntity: incapsula i numeri interi a precisione arbitraria (forse userò una lib già pronta per questi algoritmi)
BooleanEntity: incapsula il concetto di boolean
ListEntity: incapsula il concetto di lista eterogenea ordinata (la posizione è preservata)
SetEntity: incapsula il concetto di insieme eterogeneo non ordinato
MatrixEntity: incapsula il concetto di vettore multidimensionale omogeneo (tutte le Entity devono essere dello stesso tipo)

Ora.... alcune delle cose di cui sopra sono già state implementate, altre sono solo nella mia testa. Non ho ancora pensato ad una sintassi precisa per gli script, per cui accetto suggerimenti. Pensavo di basarmi su alcuni spunti presi da TI Basic e Python.
MathEngine espone al pubblico sia un'interfaccia di scripting executeScript(std::string text), sia un'inferfaccia a oggetti executeScript( Script* script ), per cui la prima parte dello sviluppo avverrà tramite la costruzione manuale dell'albero dello script e successivamente, quando avrò definito con precisione la grammatica, metterò mano ad un parser per gli script testuali.

Questo mi consente comunque la possibilità di avere in futuro una GUI furba che consenta di editare gli elementi in modo visuale, senza passare dallo script testuale, semplicemente manipolando gli oggetti dello Script.

Il progetto NON vuole essere un clone di Matlab o Mathematica (sarebbe pura e semplice follia), ma un esperimento ludico molto più modesto incentrato sul calcolo numerico. Mi piacerebbe in futuro aggiungere anche capacità di calcolo simbolico, ma è un argomento molto complesso e non credo di poterci arrivare con le mie capacità :D

Bon... vi aggiornerò con i progressi!
Fatevi sotto con le vostre idee, commenti e spunti :)
« Ultima modifica: 08 Aprile 2015, 12:16:23 da TheKaneB »

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #1 il: 31 Marzo 2015, 13:06:45 »
I numeri di riga non hanno senso di esistere nel 2015 :D
Sembra simile al Pascal perchè mi piace la tipizzazione forte (e mi piace il Pascal) :)

Però, ripeto, al momento non ho ancora pensato alla sintassi, solo alla semantica dei tipi.

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #2 il: 31 Marzo 2015, 13:16:59 »
Appena metterò mano sulla grammatica e relativo parser vedrò di studiare bene la faccenda. Al momento voglio focalizzarmi sulla semantica e l'engine di calcolo :)

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #3 il: 31 Marzo 2015, 13:25:24 »
Se alla Human interface hai un Line Editor non sei ancora nel 2015, ritenta tra qualche secolo ;D ;D ;D

Uhm... non mi piace il fatto che Little legge il testo man mano che lo interpreta (https://code.google.com/p/little-interpreter/source/browse/little.cpp).
Un po' troppo naive come approccio. Preferisco avere un AST di mezzo su cui poter fare delle operazioni prima della reale esecuzione, altrimenti ti leghi troppo alla sintassi ( e ripeto, che voglio offrire l'accesso all'albero rappresentato dalla classe Script, in modo da consentire al client un'interazione più libera possibile, anche tramite strumenti grafici e non solo testo).

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #4 il: 31 Marzo 2015, 14:05:35 »
infatti, quella roba puzzava di università lontano kilometri :D
Io ho sviluppato una forte repulsione per i metodi di scrittura del codice che insegnano all'Uni. Roba veramente distaccata dal mondo reale del software engineering.
Scrivere un interprete in quel modo ti porta via molto più tempo che usando un AST e la mantenibilità futura è praticamente nulla.

Un bel sistema a oggetti, con un AST ben definito si scrive molto facilmente e i singoli pezzi sono debuggabili come entità chiuse a se stanti. Puoi applicare facilmente centinaia di Unit Test e implementare roba futura in modo additivo senza spaccare le robe precedenti. Se invece ti appoggi pesantemente alla struttura sintattica, ogni modifica o aggiunta diventa "write only", auguri a debuggare ed espandere :D

Sarà una mia deformazione professionale, ma anche quando scrivo roba per hobby cerco di usare le tecniche più pulite che conosco, perchè so che mi aiuteranno a produrre di più in meno tempo e con meno sbattimenti :)

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #5 il: 31 Marzo 2015, 20:24:26 »
grazie mille!


Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #6 il: 31 Marzo 2015, 20:28:49 »
@legacy: il C lo evito il più possibile. In c++ è molto semplice implementare alberi e altre strutture complesse, non semplice come Java o C# ovviamente, ma comunque è un buon compromesso tra facilità di sviluppo e uso di risorse su sistemi embedded.
comunque considera che il mio target hardware sarà qualcosa tipo (minimo) ARM9 da 400MHz a salire con minimo 128MB di Ram. Embedded si, ma con un briciolo di dignità e possibilmente con un OS sotto al culo :D

Offline Z80Fan

  • Administrator
  • Guru
  • *****
  • Post: 1671
  • Karma: +13/-2
    • Mostra profilo
    • http://z80fan.altervista.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #7 il: 31 Marzo 2015, 20:48:30 »
Fatevi sotto con le vostre idee, commenti e spunti :)

Domande:
   - Hai già detto che il linguaggio sarà fortemente tipizzato, ma tipizzazione dinamica o statica?
   - Se uno "Script" è pari a una funzione, come è composto un programma con più funzioni? (un'idea la ho, ma voglio prima sentire la tua)
   - Il linguaggio supporta la ricorsione?
   - I vettori li fai con delle matrici che hanno righe/colonne == 1?
   - Implementerai una serie di passate per ottimizzare la AST prima di passare all'esecuzione vera e propria?
   - L'esecuzione la fai solo visitando la AST oppure generi un bytecode per ogni funzione? La prima è più semplice, ma la seconda può essere più veloce (e occupare meno memoria).

Comunque è un bel progettino; sopratutto è divertente di tanto in tanto iniziare qualche progettino di programmazione "pura" dove puoi decidere tutti i vincoli, senza dover stare dietro a nessuno. Io in questo periodo sono dietro a un semi-wrapper OpenGL (più che wrapper, sono utilità), e la mia produttività e voglia sono ai minimi storici in quanto sono totalmente vincolato da OpenGL e la sua maledetta state-machine interna, e quindi devo studiare attentamente sia quali funzionalità mettere, sia come strutturare l'interfaccia in modo che a OpenGL vada bene la sequenza di comandi che gli genero...

il mio target hardware sarà qualcosa tipo (minimo) ARM9 da 400MHz a salire con minimo 128MB di Ram. Embedded si, ma con un briciolo di dignità e possibilmente con un OS sotto al culo :D

Il mio gusto di embedded preferito! ;D

L'OS te lo fornisco io. 8) (Più che altro, potrebbe essere una scusa per riprendere in mano la seconda versione C++ che avevo iniziato; il blocco principale era il decidere alcuni dettagli della struttura del codice, ma ormai è da tanto che ho deciso e rimane solo da implementare).

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #8 il: 31 Marzo 2015, 21:13:58 »
Fatevi sotto con le vostre idee, commenti e spunti :)

Domande:
   - Hai già detto che il linguaggio sarà fortemente tipizzato, ma tipizzazione dinamica o statica?
Dinamica, così risulta più facile per i non programmatori.
Voglio poter fare roba così:
def A = 19.6 <--- Definizione con inizializzazione contestuale (obbligatoria?). Il tipo viene "dedotto" automaticamente dalla RValue
A = "banana" <--- qui si incazza, A è stato già definito come tipo Real

stessa cosa per le liste [1, 2, 3, "44beta", 11.787, altraVariabile, "stringazza"] e per i vettori { 2.3, 11.0, "beta" } <-- Errore: Tipi misti

Considera che NON consentirò la definizione di nuovi tipi. Infatti non è un linguaggio di programmazione vero e proprio ma solo un metodo per definire calcoli matematici in "batch". Quindi farò in modo che sia sempre possibile dedurre il tipo di una espressione adottando opportune convenzioni per ciascun tipo di literal.

Avevo pensato a fare così:
integer: 1234
real: 1234.0
string: "1234"
boolean: true, false ( sono keyword riservate )
lista: [1,2,3,4]
matrice: {{1,2}{3,4}}
funzione: def f = function(param1 : String, param2 : List, param3 : Real) : Boolean

Devo ancora capire se tipizzare fortemente il tipo funzione (quindi prendendo la lista degli argomenti e il tipo di ritorno come parte integrante del tipo) oppure se lasciare le funzioni weakly typed stile Javascript.
Forse meglio non complicarsi troppo la vita ed evitare la possibilità di passare in giro puntatori a funzione?


Citazione
   - Se uno "Script" è pari a una funzione, come è composto un programma con più funzioni? (un'idea la ho, ma voglio prima sentire la tua)

La mia idea è che il tuo ambiente di lavoro resta sempre la Home della calcolatrice e le funzioni che sviluppi siano di appoggio al tuo lavoro. Perciò non farò distinzione tra "programma" e "funzione". Per me sono tutte funzioni, e ne puoi definire quante ne vuoi nello stesso file.
Quello che cambia sarà solo lo scope di visibilità. Una funzione può chiamarne altre nello stesso file e può chiamare quelle importate con la keywork "import". Dal punto di vista del MathEngine, nel momento in cui carichi uno script, questo si comporta in modo simile a qualsiasi linguaggio di scripting:
Codice: [Seleziona]
-- il file si chiama Banana.script
def f = function(....) : Real
...
...
...
end

def A = f("banana") <--- questo viene eseguito
Quando butto questo file in pasto al MathEngine, lui assume che ci sia una function senza nome che contiene una serie di statement, tra cui un def function e una function call. La function senza nome non prende parametri e non dà output.

Comunque questa è solo un'idea fumosa. La migliorerò appena mi applicherò a pensare la grammatica del linguaggio. Ci sono alcune cose che non mi convincono molto, per cui sono aperto a suggerimenti di ogni tipo :)
Citazione
   - Il linguaggio supporta la ricorsione?
Yep

Citazione
   - I vettori li fai con delle matrici che hanno righe/colonne == 1?
Yep. Non molto efficiente, ma molto più facile da gestire lato codice. Eventuali funzioni potranno imporre delle restrizioni sulle dimensioni (ad esempio det(A) dovrà imporre che A abbia 2 dimensioni, e che abbiano entrambe la stessa quantità di elementi)
Citazione
   - Implementerai una serie di passate per ottimizzare la AST prima di passare all'esecuzione vera e propria?
Non so quanto sia complicato farlo. Penso di no, anche perchè non ne sono capace.
Citazione
   - L'esecuzione la fai solo visitando la AST oppure generi un bytecode per ogni funzione? La prima è più semplice, ma la seconda può essere più veloce (e occupare meno memoria).
Quando lavoravo nei VG mi è capitato di sviluppare un sistema di scripting a bytecode. Non è difficile, potrei farlo, ma magari lo lascio come ottimizzazione successiva.

Citazione
Comunque è un bel progettino; sopratutto è divertente di tanto in tanto iniziare qualche progettino di programmazione "pura" dove puoi decidere tutti i vincoli, senza dover stare dietro a nessuno. Io in questo periodo sono dietro a un semi-wrapper OpenGL (più che wrapper, sono utilità), e la mia produttività e voglia sono ai minimi storici in quanto sono totalmente vincolato da OpenGL e la sua maledetta state-machine interna, e quindi devo studiare attentamente sia quali funzionalità mettere, sia come strutturare l'interfaccia in modo che a OpenGL vada bene la sequenza di comandi che gli genero...

il mio target hardware sarà qualcosa tipo (minimo) ARM9 da 400MHz a salire con minimo 128MB di Ram. Embedded si, ma con un briciolo di dignità e possibilmente con un OS sotto al culo :D

Il mio gusto di embedded preferito! ;D

L'OS te lo fornisco io. 8) (Più che altro, potrebbe essere una scusa per riprendere in mano la seconda versione C++ che avevo iniziato; il blocco principale era il decidere alcuni dettagli della struttura del codice, ma ormai è da tanto che ho deciso e rimane solo da implementare).

eheh ok!
La parte Engine sarà certamente multiplatform (uso C++ puro, nessun aggancio a funzioni di sistema, solo un po' di cout per il logging degli errori), per cui mi toccherà fare la parte client ad hoc per il tuo OS. Magari faccio solo un sistema di input testuale interattivo (sempre che tu non decida di supportare roba ... tipo Qt ahah :D ).

Offline Z80Fan

  • Administrator
  • Guru
  • *****
  • Post: 1671
  • Karma: +13/-2
    • Mostra profilo
    • http://z80fan.altervista.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #9 il: 01 Aprile 2015, 01:24:21 »
Dinamica, così risulta più facile per i non programmatori.

Non so: parlo per sensazione ovviamente, ma forse avere il tipo di dato specificato esplicitamente può essere più semplice da capire per un novizio rispetto a regole di derivazione implicita.
Poi, certe volte è comodo poter specificare il tipo di dato senza ambiguità: se ad esempio voglio una lista di numeri reali, e la voglio caricare con 1, 2, 3, 4, dovrei scrivere:
def l = [1.0, 2.0, 3.0, 4.0]
Però è un po' scomodo dover sempre mettere .0 (sopratutto se magari lo metti in una calcolatrice con tasti piccoli o tastiera limitata), vorrei poter fare
def l = [1, 2, 3, 4]
però diventa una lista di interi, e se provo a fare operazioni con altre cose float darebbe errore (a meno che non consideri cast impliciti, però se vuoi interi a precisione arbitraria un cast può perdere informazione e potrebbe non essere quello che vuoi).
Oppure più in generale stai facendo un programmino veloce sulla tua calcolatrice, e vuoi provare diversi numeri nella lista: anche qui dover specificare sempre .0 nel caso il numero sia anche intero diventa fastidioso, sopratutto se come nel caso sopra la lista viene dedotta a lista di interi, e ti capita di passare la variabile a una funzione che si aspetta una lista di interi.

Puoi lasciare la deduzione automatica del tipo (che aiuta sopratutto nel fatto che obbliga a mettere un'inizializzazione; le variabili non inizializzate diventano errori di sintassi), e aggiungere un modo per specificare il tipo di dato prescelto, tipo
def l : ListReal = [1, 2, 3, 4]
def l = ListReal([1, 2, 3, 4])    // questo è più stile "cast"

e il compilatore sa che quei literal li deve interpretare come reali e non interi; ovviamente nel caso ci sia qualcosa tipo [1, 2, x, 4] dove x è una variabile di un tipo diverso da real, si avrà l'errore di conversione come al solito.


Da questo esempio viene fuori anche un altro "problema": come differenzi le Liste in base al tipo di dato contenuto? Nella specifica dei parametri delle funzioni devi poter indicare che vuoi una lista solo di un certo tipo, perchè ad esempio non avrebbe senso passare una lista di stringhe a una funzione che calcola la media, e questo errore dovrebbe essere catturato a compile time.
Dovresti o introdurre vari tipi di dato ListInteger, ListReal etc, oppure trovare una qualche sintassi List(Boolean), List.String.
È possibile fare liste di liste? Devi decidere la sintassi anche per quelle.

Devo ancora capire se tipizzare fortemente il tipo funzione (quindi prendendo la lista degli argomenti e il tipo di ritorno come parte integrante del tipo) oppure se lasciare le funzioni weakly typed stile Javascript.
Forse meglio non complicarsi troppo la vita ed evitare la possibilità di passare in giro puntatori a funzione?

Io credo di si, meglio che ogni funzione sia tipizzata secondo i suoi parametri; puoi sempre fare che, se una funzione funziona bene con qualsiasi input, puoi fare a meno di indicare il tipo di dato per quel parametro e il compilatore accetterà qualsiasi input.
I modi in cui puoi trattarlo lato interprete sono molteplici: o segui la strada dei template C++, ovvero rigeneri il corpo della funzione quando ne incontri un uso, il che ti permette di ottimizzare più aggressivamente il codice ma ti occupa più spazio nell'AST, oppure puoi lasciare il tipo "indefinito" e eseguire i controlli a runtime (e questo implica che non potrai a compile time trovare tutti i possibili errori di tipo di dato).

Secondo me è troppo lungo dover tener conto di queste possibilità, quindi io lascerei che ogni funzione è fortemente tipizzata e ogni parametro deve avere tipo definito.

Il passaggio di funzioni come parametro non dovrebbe essere troppo faticoso, ci sono però due problemi (o meglio, decisioni) da risolvere:
prima di tutto, visto che le funzioni sono fortemente tipizzate, devi decidere una sintassi per specificare un parametro di tipo funzione; una proposta può essere qualcosa tipo:
def f = function(param1 : String, param2 : List, param3 : function(Integer, Real) : String) : Boolean
o una funzione che ritorna funzioni che ritornano matrici:
def f2 = function(param1 : String) : function(List, Integer, String) : Matrix
Questa sintassi dovrebbe essere totalmente disambigua (mi sembra), ma potrebbe non essere totalmente leggibile.

Un'altra strada potebbe essere di indicare solo che si vuole che quel parametro sia una funzione, e lasciare a runtime il compito di verificare che la chiamata (eseguita tramite il riferimento) venga eseguita con il giusto numero e tipo di parametri della funzione che viene riferita dalla variabile. Questo causa un problema simile a quello sopra dove non si può catturare ogni problema di tipo a compile time.
Per facilitare la scrittura di grandi programmi che usano molte callback si può introdurre un costrutto di "alias" in stile:
alias callback = function(Integer, Real) : String
(essendo un "alias" e non un "def", questa riga non fa partire il blocco della funzione ma lo statement termina alla fine della riga)
Sarebbe circa come un "typedef", non so se rientra nella tua idea di "creare nuovi tipi di dato".

Secondo, visto anche che il linguaggio dovrebbe essere usato per problemi matematici, e per come è costruito, vorrai sicuramente avere chiusure:
def gen = function(x : Integer) : function(Integer) : Integer
    return function(y : Integer) : Integer
        return x + y
    end
end

def f5 = gen(5)
def z = f5(7)     // z = 12


Qui devi assicurarti che ogni funzione abbia accesso allo ScriptEnvironment della funzione padre, e se ne usa un valore, devi copiarlo (perchè potrebbe variare in futuro in altri punti del programma ma non si vuole che la chiusura venga influenzata).

Citazione
   - Il linguaggio supporta la ricorsione?
Yep

Per questo punto preciso, ho due domande/dubbi/osservazioni: la prima, molto semplice, è che una funzione ricorsiva crea un ciclo nell'AST, che quindi non è più un albero ma un grafo.
La seconda riguarda la sintassi, e in particolare gli scope:

def fattoriale = function(i : Integer) : Integer
    if i <= 1 then
        return 1
    else
        return i * fattoriale(i-1)
    end
end


In base a come esegui il parse del codice, e di come inserisci i valori nella tabella dei simboli, quando il compilatore arriva a leggere la riga con la chiamata ricorsiva, il simbolo "fattoriale" non è ancora definito (aspetti il parsing di function prima di definirlo), oppure è definito ma contiene un valore "vuoto" (se per esempio lo hai già inserito nel ScriptEnvironment).
Se vogliamo rimanere coerenti con il discorso delle chiusure di prima, quando una funzione incontra un simbolo definito nel padre, dovrebbe copiarlo, però in questo caso il simbolo o non esiste o contiene un valore "vuoto", quindi non è possibile in un solo passo abbinare la chiamata ricorsiva.

Mi sono chiesto come fa Lua a risolvere questo problema, visto che la sua sintassi e comportamento è estremamente simile a questo che stiamo inventando: il trucco è che le variabili in Lua sono di default globali, quindi nel caso simile al nostro, "fattoriale" nel return semplicemente sarebbe un riferimento al simbolo "fattoriale" che è definito (perchè l'abbiamo parsato), e quando la funzione sarà effettivamente eseguita avrà il giusto valore (perchè lo statement di creazione del simbolo "fattoriale" sarà già concluso).

Nel nostro linguaggio, visto che assumiamo che i simboli siano di default locali, questo sistema crolla, e crolla pure in Lua se dichiariamo la funzione come locale, simulando quindi il comportamento di default del nostro linguaggio:
local fact = function (n)
    if n == 0 then return 1
    else return n*fact(n-1)   -- buggy
    end
end


When Lua compiles the call fact(n-1), in the function body, the local fact is not yet defined. Therefore, that expression calls a global fact, not the local one.
(http://www.lua.org/pil/6.2.html)
La soluzione, in Lua, è dichiarare prima il simbolo come locale (quindi creandolo), e poi assegnarci la funzione, oppure usare la sintassi alternativa che è syntactic sugar per la stessa tecnica.

A meno di non mettere eccezioni nel parser, o cambiare il comportamento dello scope come in Lua, io direi di modificare un po' la sintassi per la creazione di funzioni:
function nome(..params..) : ritorno
    ...
end


Tutte le altre sintassi che abbiamo visto sopra rimangono valide (alla fine non sono altro che funzioni anonime assegnate poi a una variabile), e questa stessa sintassi è come un synctatic sugar delle precedenti, con la differenza che (circa come in Lua), il parser che analizza la funzione sa più direttamente che "nome" sarà il nome della funzione, quindi se si trova nella condizione di ricorsione:
function fattoriale(i : Integer) : Integer
    if i <= 1 then return 1
    else return i * fattoriale(i-1)
    end
end


Sa che per risolvere il "fattoriale" del return può usare direttamente la funzione stessa che sta parsando (semprechè la lista di parametri sia la stessa, altrimenti deve guardare in un contesto più ampio fuori dalla funzione stessa).

Yep. Non molto efficiente, ma molto più facile da gestire lato codice. Eventuali funzioni potranno imporre delle restrizioni sulle dimensioni (ad esempio det(A) dovrà imporre che A abbia 2 dimensioni, e che abbiano entrambe la stessa quantità di elementi)

Questo mi fa venire in mente un argomento parzialmente scorrelato: come gestisci gli errori di runtine? Immagino tu non voglia andare a programmare un sistema di eccezioni; semplicemente uccidi l'interprete quando c'è qualcosa che non va?

Sempre su questo tema, prevedi che le funzioni possano tornare più valori in uscita, ad esempio per tornare il risultato e un valore booleano di errore?

Citazione
   - Implementerai una serie di passate per ottimizzare la AST prima di passare all'esecuzione vera e propria?
Non so quanto sia complicato farlo. Penso di no, anche perchè non ne sono capace.

Alcune ottimizzazioni sono semplici : puoi fare una variante molto semplice di costant folding semplicemente "elaborando" l'AST ricorsivamente e sostituendo tutti i blocchi che tornano un risultato (che quindi non ritornano un "can't compute" come errore) con il loro valore elaborato; in qualcosa tipo 2*3*x, provando a elaborare l'AST si troverà un blocco * con operandi 2 e 3, che quindi è completamente calcolabile e può essere sostituito con la costante 6. Successivamente ci sarà un blocco * con input 6 e x che non sarà elaborabile (a meno che x non abbia un valore costante).
Ovviamente questo è il modo più banale nel vedere il constant folding: in molti casi (in base a come costruisci l'AST e alla sofisticatezza della visita), situazioni come 2*x + 3 + 4 potrebbero non essere elaborate (perchè prima si trova il blocco * che non è elaborabile, quindi +3 non è elaborabile, quindi +4 non è elaborabile), però potrà essere interessante in futuro provare a trovare qualche algoritmino.

La parte Engine sarà certamente multiplatform (uso C++ puro, nessun aggancio a funzioni di sistema, solo un po' di cout per il logging degli errori), per cui mi toccherà fare la parte client ad hoc per il tuo OS. Magari faccio solo un sistema di input testuale interattivo (sempre che tu non decida di supportare roba ... tipo Qt ahah :D ).

Qt decisamente no... ho solo una vita. :D E comunque è un problema di software utente, non di kernel. :P
Bisognerà vedere un po' su che piattaforma vorrai metterlo; su ARM già volevo far qualcosa (sulla Udoo, sulla quale ho già trovato il modo per far partire un mio binario personalizzato da U-Boot), quindi qualcosa dovrei riuscire a fornirti. Se pensavi qualcosa sulle linee dell'Arduino Due, meglio ancora, perchè la Udoo ha proprio il SAM3X on board.
Al minimo ti servirà sicuramente un gestore della memoria (un minimo di allocatore di pagine, per cose più granulari si trovano tanti allocatori in rete), giusto un minimo di scheduling ('che altrimenti che ci sta a fare un kernel? :P), e ovviamente un I/O testuale; tutte cose non assurde da fare, più che altro in ambito ARM bisogna conoscere la mappa di memoria del determinato SoC (ognuno è diverso), e alcuni dettagli delle periferiche.
In teoria con il nuovo sistema che ho imbastito nella riscrittura, gestire differenze tra piattaforme che usano la stessa CPU (nel senso di "ISA", come ARM o x86) è molto semplice, perchè il processore è separato dalla piattaforma, che è separata dai device driver (la "platform" è quella che detta legge, indicando al suo interno che processore vuole e quali device driver usare; un esempio di platform è "ibmpc" che usa cpu "x86" e ha vari device driver per il PIC, timer etc.).

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #10 il: 01 Aprile 2015, 14:44:38 »
@Z80Fan e @dsar:

grazie mille per i suggerimenti.
Come dicevo, questo qui non è il mio campo e non voglio farla fuori dal vasino :D
Ho implementato in passato la parte "esecutiva" di una virtual machine, quindi ho molto ben chiaro il funzionamento lato esecuzione di un AST. Quello che per me è totalmente nuovo è l'aspetto di language design e le problematiche che ciò si porta dietro relativamente al parsing.

Mi studierò volentieri tutto il materiale che mi gettate addosso e tornerò alla carica quando avrò capito meglio cosa voglio fare e come farlo.
Per quanto riguarda la gestione di funzioni e tipi, il mio obiettivo primario è quello di fare una calcolatrice, quindi un'applicativo dotato di due principali caratteristiche:
- Modalità interattiva come principale fonte di input
- Avere lato linguaggio TUTTI e SOLI gli strumenti utili a scopo matematico (numerico per il momento)

Quindi sarà importantissimo gestire liste, insiemi e matrici lato linguaggio, ma dev'essere anche intuitivo e veloce da usare in modalità interattiva.
Ad esempio, su obiezione di Z80Fan, penso sia ragionevole applicare conversioni automatiche Integer -> Double con perdita di precisione usando la stessa regola che usano le calcolatrici TI e HP : in una espressione, gli argomenti Double infettano gli altri operandi, castando SEMPRE verso double.

Quindi se faccio def mioArray = {1, 2, 3, 4.0} allora tutto l'array verrà convertito in Double in maniera silenziosa.
Analogamente se faccio def mioArray2 = {7, 8, 9, 10} sarà un array di soli interi, ma la somma mioArray + mioArray2 sarà un array di Double (il Double è infettivo).

Mi aspetto che l'utente sia abituato ad Hp e TI da questo punto di vista, inoltre, mi aspetto che l'utilizzo degli interi a precisione arbitraria sia ragionevolmente limitato a sole operazioni intere (principalmente matematica combinatoria), mentre se uso un misto di Integer e Double mi aspetto che l'utente sia interessato all'applicazione di metodi numerici approssimati.

Come vi sembra l'approccio? Può funzionare?
« Ultima modifica: 01 Aprile 2015, 14:55:15 da TheKaneB »

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #11 il: 01 Aprile 2015, 14:47:52 »
ma il target cosa e' ? la RPI ?

Si, pensavo una roba tipo la RPI, ma non necessariamente quella macchina specifica. Comunque sì, vorrei avere a disposizione una macchina relativamente potente sotto le chiappe come requisito minimo. In questo momento il mio "gold standard" è la HP Prime. Vorrei poter fare qualcosa che sia non dico nella sua categoria (è troppo avanzata per le mie capacità), ma che sia quantomeno ispirata a questa macchina (ARM9 400Mhz, Ram mi pare 64 o forse 128MB, schermo a colori ad "alta" risoluzione, possibilità di avere un OS non banale sotto i piedi).

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #12 il: 01 Aprile 2015, 15:00:52 »
l'AST rappresenta il codice già sbrogliato e pronto per la successiva fase. Nel mio caso la fase successiva era l'interpretazione ed esecuzione del codice direttamente sull'AST.

In parole povere, se piazzi un metodo virtuale execute() sulla classe base del Nodo dell'albero AST, e specializzi l'implementazione in base al tipo di nodo, per eseguire tutto l'albero ti basta alla fine fare un semplice AST * a = getAST(); a->execute(environment);

Ho lavorato anche su una VM basata su bytecode. In quel caso l'AST non me lo passavano, avevo già gli opcode finali e la VM era molto più complessa, perchè si comportava come una vera macchina, con i suoi cicli di fetch, execute e memory.
Era molto più efficiente ovviamente, ma la prima è più facile da implementare e la VM, di fatto, non esiste fisicamente ma è astratta dalla capacità stessa dell'AST di eseguire se stesso.

Offline TheKaneB

  • Human Debugger
  • *****
  • Post: 5292
  • Karma: +20/-23
    • Mostra profilo
    • http://www.antoniobarba.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #13 il: 01 Aprile 2015, 15:07:49 »
sisi, grandissimi quelli di Wolfram :)
RPI in UK ha preso il posto del vecchio BBC con 6502. E' diventato il punto di riferimento per l'educazione informatica nelle scuole, pertanto stanno sfornando una nuova generazione a colpi di Python e Mathematica, evviva :D

Offline Z80Fan

  • Administrator
  • Guru
  • *****
  • Post: 1671
  • Karma: +13/-2
    • Mostra profilo
    • http://z80fan.altervista.org
Re:Idee e spunti per una calcolatrice - Parte Software
« Risposta #14 il: 01 Aprile 2015, 15:38:01 »
Mi aspetto che l'utente sia abituato ad Hp e TI da questo punto di vista, inoltre, mi aspetto che l'utilizzo degli interi a precisione arbitraria sia ragionevolmente limitato a sole operazioni intere (principalmente matematica combinatoria), mentre se uso un misto di Integer e Double mi aspetto che l'utente sia interessato all'applicazione di metodi numerici approssimati.

Come vi sembra l'approccio? Può funzionare?

L'unico problema che vedo ora su due piedi è che se per sbaglio da qualche parte dell'elaborazione viene iniettato un Double, tutti i calcoli successivi vengono "infettati" e ridotti al double, cosa che magari l'utente che voleva un calcolo strettamente intero non voleva fare, però per risolverlo bisognerebbe stringere ancora di più la tipizzazione, con tutta la complessità di programmazione che non va bene per il target che si è stabilito...

Si, pensavo una roba tipo la RPI, ma non necessariamente quella macchina specifica. Comunque sì, vorrei avere a disposizione una macchina relativamente potente sotto le chiappe come requisito minimo. In questo momento il mio "gold standard" è la HP Prime. Vorrei poter fare qualcosa che sia non dico nella sua categoria (è troppo avanzata per le mie capacità), ma che sia quantomeno ispirata a questa macchina (ARM9 400Mhz, Ram mi pare 64 o forse 128MB, schermo a colori ad "alta" risoluzione, possibilità di avere un OS non banale sotto i piedi).

Magari la creazione di una calcolatrice custom potrebbe essere un successivo Non-Solo-Project. :P

Tags: