Παρασκευή 4 Δεκεμβρίου 2020

Αναθεώρηση 12, Έκδοση 10 και ένα πρόγραμμα!

Μια μικρή διόρθωση στην αναθεώρηση 12. Όταν έβαλα το xmldata αντικείμενο, άλλαξα ένα εσωτερικό αντικείμενο mHandler, να μπορεί να βγει στη Μ2000, όχι όμως όλη η λειτουργικότητά του. Αυτό το τελευταίο επιτυγχάνεται με δηλώσεις τύπου Friend στις μεθόδους-ιδιότητες. Όταν λοιπόν εσωτερικά πρέπει να χρησιμοποιήσω αυτές τις ιδιότητες, τότε το αντικείμενο πρέπει να είναι mHandler, και όχι ένα Object που να είναι mHandler (επειδή το object έχει το dispatch interface, και αυτό εμφανίζει μόνο τις Public ιδιότητες). To mHandler είναι φορέας άλλων αντικειμένων, σε μια ιδιότητα objref, και αυτή είναι friend. Έτσι όπου χρησιμοποιούσα το mHandler ως οbject (το γενικό αντικείμενο που παίρνει τα πάντα), απλά το έγραψα σε μια μεταβλητή τύπου mHandler, οπότε αυτή χρησιμοποιεί το mHandler interface, άρα βλέπει τις Friend). Τα enumarators, λειτουργούν με φορέα το mHander, οπότε κάπου ξέχασα στη μετατροπή και άφησα ένα  objref το οποίο δεν έπρεπε να ήταν εκεί. Το module που χτύπησε στο info, ήταν το H1 το οποίο τώρα τρέχει!  Το ίδιο module (τμήμα) υπάρχει εδώ: https://georgekarras.blogspot.com/2018/11/oop-group-as-enumaration-variable-with.html


Χθες έγραψα σε ένα task στο rosetta.org, στο http://rosettacode.org/wiki/Amb

Δεν το έχω βρει το θέμα του Amb, που βγαίνει από τη λέξη ambiguous, αμφίσημος. Στο task (έργο) καλούμαστε να φτιάξουμε το χειριστή Amb ή κάποια συνάρτηση που να κάνει την ίδια δουλειά. Πραγματικά μου είναι δύσκολο να το περιγράψω στα ελληνικά!

Ένας ψευδοκώδικας δείχνει την λειτουργία του:

let x = Amb(1, 2, 3)
let y = Amb(7, 6, 4, 5)
Amb(x * y = 8)
print x, y

Το Amb πρέπει να βρει τα x και y που ικανοποιούν την συνθήκη x*y=8.

Το συγκεκριμένο έργο ζητάει από τα τέσσερα παρακάτω (δηλαδή σαν να έχουμε τέσσερις λίστες, ή πίνακες), να βρεθούν οι τέσσερις λέξεις που δίνουν "that thing grows slowly" και η συνθήκη λέει ότι κάθε λέξη με τις διπλανές τις θα έχει το ίδιο γράμμα, έτσι το thing ξεκινάει με t όπως τελειώνει το that, και τελειώνει σε g όπως ξεκινάει το grows.

  1. "the" "that" "a"
  2. "frog" "elephant" "thing"
  3. "walked" "treaded" "grows"
  4. "slowly" "quickly"

Το ενδιαφέρον εδώ δεν είναι να δώσουμε ένα πρόγραμμα με προκαθορισμένες επαναλήψεις. Για το λόγο αυτό λέγεται και ανήκει στο "non-deterministic finite automaton". Εδώ τα δεδομένα πρέπει να καθορίσουν τον αριθμό ελέγχων, ή ακόμα και επαναλήψεων.

Υπάρχουν λύσεις σε διάφορες γλώσσες. Μια ενδιαφέρουσα λύση είναι με την διαδικασία της συνέχειας, η continuation, όπου κάθε φορά που προκύπτει μια νέα απαίτηση για έλεγχο, φτιάχνεται ένα παράλληλο περιβάλλον εκτέλεσης, ένα νήμα εκτέλεσης με όλο το περιβάλλον μαζί. Στη Μ2000 δεν θα ασχοληθούμε με αυτό! Έδωσα δυο λύσεις που και οι δυο έχουν για βάση τους τη δυνατότητα της Μ2000 να χρησιμοποιεί λάμδα συναρτήσεις, ως πολίτες πρώτης τάξης.

Ειδικότερα από τις λάμδα συναρτήσεις μας ενδιαφέρουν δυο δυνατότητες στη Μ2000. Η πρώτη μας λέει ότι μια λάμδα συνάρτηση μπορεί να γραφτεί σε μια μεταβλητή. Η δεύτερη μας λέει ότι κάθε λάμδα συνάρτηση μπορεί να έχει μια λίστα συλλήψεων (captures) άλλων μεταβλητών. Στη Μ2000 οι συλλήψεις γίνονται με αντιγραφή (εκτός και αν έχουμε αντικείμενο, όπου έχουμε αντίγραφο του δείκτη). Εδώ βάζουμε σε λάμδα να συλλάβουν άλλες λάμδα, και με αυτόν τον τρόπο κατασκευάζουμε μια λάμδα να περιέχει σειρά άλλων. Αυτό γίνεται κατά την εκτέλεση. Έτσι η τελική λάμδα είναι ένα κατασκεύασμα, που δημιουργείται κατά απαίτηση, βάσει των δεδομένων, και αυτό υλοποιεί την απροσδιόριστη (κατά την συγγραφή του κώδικα) αλλά που τερματίζει, αυτόματη μηχανή.

Τα δυο προγράμματα λύσεις, ξεχωρίζουν: Το μεν πρώτο δέχεται συνθήκες δυο μεταβλητών (πινάκων),  για οποιοδήποτε αριθμό πινάκων (έτσι το παράδειγμα με τους τέσσερις πίνακες το λύνει) και επιστρέφει μια λύση. Αυτό είναι και το πιο γρήγορο με την έννοια ότι αν μια συνθήκη δεν βγαίνει δεν κοιτάμε για τα παρακάτω. Το δεύτερο παίρνει ότι του δίνουμε και φτιάχνει στην ουσία έναν απαριθμητή, που αντί για ψηφία, έχει τις τιμές του κάθε πίνακα στη θέση που τα δίνουμε. Κάθε φορά μας δίνει σειρά, και ρίχνουμε τα στοιχεία στην συνθήκη (για όλα), και αν είναι μια ζητούμενη σειρά τότε μπαίνει σε μια λίστα σειρών (ένα πίνακα που περιέχει άλλους πίνακες), και γυρνάει όλες τις λύσεις. Αυτό σημαίνει ότι θα τρέξει όλους τους συνδυασμούς!

Επειδή στη Μ2000 οι αριθμητικές με τις αλφαριθμητικές μεταβλητές ξεχωρίζουν, με συνέπεια σε μια παράμετρο μιας συνάρτησης αν δώσουμε μια Αλφαριθμητική τιμή αυτή θα πρέπει να έχει όνομα με $ στο τέλος, και εδώ θέλουμε να δουλεύουμε με οποιαδήποτε τιμή, κάνουμε το λεγόμενο boxing, δηλαδή όταν θέλουμε να πάρουμε μια τιμή από έναν πίνακα (οι πίνακες μπορούν να έχουν οποιεσδήποτε τιμές εσωτερικά, ανεξάρτητα από το όνομά τους), την βάζουμε ως αντίγραφο σε έναν πίνακα ενός στοιχείου. Η συνάρτηση Cons() ή Ένωση() ενώνει πίνακες, οπότε με αυτό το τρόπο αδιαφορούμε για το τι έχουν μέσα οι πίνακες. Μας ενδιαφέρει όμως να έρθουν τα στοιχεία σε αυτό που είναι, αριθμοί ή αλφαριθμητικά στον έλεγχο της συνθήκης.

Στο πρώτο πρόγραμμα ο έλεγχος γίνεται σε μια λάμδα που ζητάει πίνακες (ενός στοιχείου) οπότε μέσα στη λάμδα αυτή έχουμε δώσει το τρόπο που θα διαβαστούν οι τιμές με τις συνοδευτικές συναρτήσεις #Val() ή #Val$() αντίστοιχα. Το # στο όνομα δηλώνει ότι αυτές εφαρμόζονται στον αυτόματο πίνακα, ή tuple, (είναι ένα είδος linq στην Μ2000, δηλαδή σαν μια ενσωματωμένη γλώσσα ερωτημάτων, και υπάρχουν αρκετές, μερικές από τις οποίες δίνουν νέα tuple, και έτσι μπορούμε να έχουμε μια σειρά από αυτές τις "συνοδευτικές" συναρτήσεις, και να εξάγουμε στοιχεία υπό κάποια διαμόρφωση).

Στο δεύτερο πρόγραμμα επειδή η συνάρτηση ελέγχου βρίσκεται έξω από τις λάμδα, που εκτελούν το επόμενο βήμα, δηλαδή από αυτές που δίνουν τον επόμενο συνδυασμό, και έχουμε όλο το πίνακα για έλεγχο, απλά αντιγράφουμε το πίνακα σε ένα σωρό τιμών και τον εφαρμόζουμε ως τιμές κλήσης. Έτσι στη συνάρτηση μπαίνουν απευθείας οι τιμές και εκεί δουλεύουμε με μεταβλητές.

Module AmbFunction {
      Function Amb (failure) {
            // get an array of s items, return an array of 1 item
            // we do this so we forget the type of element
            getitem=lambda (n, c) -> {
                  dim z(1) :link c to c()
                  stock c(n) keep 1, z(0) // copy from c(n) to z(0) one item
                  =z()
            }
            read a
            c1=lambda a, getitem (i, &any, &ret) ->{
                  any=getitem(i, a)
                  ret=any
                  =true
            }
            m=stack.size
            if m=0 then Error "At least two arrays needed"
            c=c1
            while m>1 {
                  read b
                  c1=lambda c2=c, j=0, m=len(a), b, failure, getitem (i, &any, &ret) ->{
                        any=getitem(i, b)
                        ret=(,) : ok=false : anyother=(,)
                        do
                              if c2(j, &anyother, &ret) then
                                    if not failure(any, anyother) then
                                          ok=true
                                          ret=cons(ret, any)
                                    end if
                              end if
                              j++
                        until ok or j=m
                        if j=m then j=0
                        =ok
                  }
                  c=c1 : a=b : m--
            }
            read b
            amb1=lambda c2=c, j=0, m=len(a), b, failure, getitem (&ret) ->{
                  ret=(,) : ok=false: anyother=(,)
                  k=each(b)
                  while k
                        any=getitem(k^, b)
                        do
                              if c2(j, &anyother, &ret) then
                                    if not failure(any, anyother) then
                                          ok=true
                                          ret=cons(ret, any)
                                    end if
                              end if
                              j++
                        until ok or j=m
                        if j=m then j=0
                        if ok then exit
                  end while
                  =ok
            }
            ret=(,) 
            if amb1(&ret) then =ret else =(,) ' default return value if nothing found
      }

      a=(1, 2, 3)
      b=(7, 6, 4, 5)
      failure=lambda (a,b)->{
            =a#val(0)*b#val(0)<>8
      }
      Print amb(failure, a, b)#str$()
      a=("the", "that", "a")
      b=("frog", "elephant", "thing")
      c=("walked", "treaded", "grows")
      d=("slowly", "quickly")
      failure=lambda (a,b)->{
            =left$(a#val$(0),1)<>right$(b#val$(0),1)
      }
      Print amb(failure, a, b, c, d)#str$()
}
AmbFunction


2 4
that thing grows slowly


Η δεύτερη λύση

Module AmbFunction {
      Enum Solution {First, Any=-1}
      Function Amb(way as Solution, failure) {
            // get an array of s items, return an array of 1 item
            // we do this so we forget the type of element
            getitem=lambda (n, c) -> {
                  dim z(1) :link c to c()
                  stock c(n) keep 1, z(0) // copy from c(n) to z(0) one item
                  =z()
            }
            read a
            c1=lambda i=0, a, getitem (&any, &ret) ->{
                  any=getitem(i, a)
                  ret=any
                  i++
                  ok=i=len(a)
                  if ok then i=0
                  =ok
            }
            m=stack.size
            if m=0 then Error "At least two arrays needed"
            c=c1
            while m>0 {
                  read a
                  c1=lambda c2=c, i=0, a, getitem (&any, &ret) ->{
                        any=getitem(i, a)
                        ret=(,) : ok=false : anyother=(,)
                        ok=c2(&anyother, &ret)
                        ret=cons(ret, any)
                        if ok then i++
                        ok=i=len(a)
                        if ok then i=0
                        =ok
                  }
                  c=c1 : m--
            }
            ok=false
            any=(,)
            flush
            while not ok
                  ret=(,)
                  ok=c(&any, &ret)
                  s=stack(ret)
                  if not failure(! s) then data ret : if way>0 then ok=true
            End While
            if empty then
                   ret=(("",),)
             else
                    ret=array([])
             end if
             =ret
      }

      a=(1, 2, 3)
      b=(7, 6, 4, 5)
      failure=lambda (a,b)->{
            =a*b<>8
      }
      Print Amb(First, failure, a, b)#val(0)#str$()
      a=("the", "that", "a")
      b=("frog", "elephant", "thing")
      c=("walked", "treaded", "grows")
      d=("slowly", "quickly")
      failure=lambda (a$, b$, c$, d$)->{
            def amb(x$, y$)=right$(x$,1)<>left$(y$,1)
            =amb(a$,b$) or amb(b$,c$) or amb(c$, d$)
      }
      Print amb(First, failure, a, b, c, d)#Val(0)#str$()
      Range=lambda (a, f) ->{
            for i=a to f-1: data i: next
            =array([])
      }
      Print "Small Pythagorean triples problem:"
      a=range(1,11)
      b=a
      z=a
      failure=lambda (a, b, z)->{
            =not (a^2+b^2=z^2)
      }
      all=amb(Anyfailure, a, b, z)
      k=each(all)
      while k
            z=array(k)
            Print z#str$()
      end while

}
AmbFunction

2 4
that thing grows slowly
Small Pythagorean triples problem:
4 3 5
3 4 5
8 6 10
6 8 10



Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.