Racket – Input e Output – 1

athena_postage_stamp

Oggi inizio un nuovo capitolo, qui: [doc]/guide/i_o.html.

Input e output

Un po’ di terminologia, sapete ognuno usa la sua e quelli di Racket (tutti über-nerds) ovviamente non fanno eccezione. Continuo a curiosare in PLT e ci sono davvero tante cose, per esempio qui :grin:

A Racket port corresponds to the Unix notion of a stream (not to be confused with racket/stream‘s streams).

A Racket port represents a source or sink of data, such as a file, a terminal, a TCP connection, or an in-memory string. Ports provide sequential access in which data can be read or written a piece of a time, without requiring the data to be consumed or produced all at once. More specifically, an input port represents a source from which a program can read data, and an output port represents a sink to which a program can write data.

Ecco, pronto a passare qui: [doc]/guide/ports.html.

Varietà di porte

Various functions create various kinds of ports. Here are a few examples:

Files: The open-output-file function opens a file for writing, and open-input-file opens a file for reading.

io0

e poi…

io1

If a file exists already, then open-output-file raises an exception by default. Supply an option like #:exists 'truncate or #:exists 'update to re-write or update the file:

io2

Nota: ho aggiunto newline (si poteva usare anche il solito “\n“) perché altrimenti il prompt del terminale è fuori posto :wink:

Instead of having to match open-input-file and open-output-file calls, most Racket programmers will instead use call-with-output-file, which takes a function to call with the output port; when the function returns, the port is closed. Questa è una cosa che viene direttamente dal Lisp, ne avevo parlato dettagliatamente quando studiavo l’ottimo Peter Seibel.

io3

Strings: The open-output-string function creates a port that accumulates data into a string, and get-output-string extracts the accumulated string. The open-input-string function creates a port to read from a string.

io4

TCP Connections: The tcp-connect function creates both an input port and an output port for the client side of a TCP communication. The tcp-listen function creates a server, which accepts connections via tcp-accept.

io5

Process Pipes: The subprocess function runs a new process at the OS level and returns ports that correspond to the subprocess’s stdin, stdout, and stderr. (The first three arguments can be certain kinds of existing ports to connect directly to the subprocess, instead of creating new ports.)

io6

esattamente come

io7

Internal Pipes: The make-pipe function returns two ports that are ends of a pipe. This kind of pipe is internal to Racket, and not related to OS-level pipes for communicating between different processes.

io8

OK, mi piace. Mi viene da fare il paragone con il (vecchio e più macchinoso) I/O del Common Lisp; deve aggiornasi, imho.

:mrgreen:

Ma i giovani conoscono i file di testo?

es0Un post estivo, anche se ormai l’estate sta finendo (cit. per chi se la ricorda). Pare questi post piacciano e allora ecco…

Capitato recentemente. Leggo la bozza quasi definitiva di una tesina (un compito delle vacanze) e prendo appunti. Io che sono vecchio uso un editor normale, Gedit –OK ci sono Emacs e vi ma ormai…– che, ovviamente, produce un file di testo, niente fronzoli tipo font, neretto, sottolineato, corsivo, colori e compagnia bella. Se mi ricordo metto anche l’estensione .txt. E ci sono anche i caratteri accentati, mica solo il set ASCII, tutto l’Unicode.

OK, fatto, salvato, copiato su una chiavetta USB e andato –a piedi, roba di pochi minuti– a casa dello studente.
Qui sono cominciati i fatti che rendono la vita interessante e mi permettono di scrivere questo post. Stavo per dire guai ma sarebbe eccessivo, troppo.
Occorre precisare che il computer del giovane studente (modello, davvero bravo come pochi) ha Windows 8 come sistema operativo. E un antivirus che gode di molta considerazione per via di spiacevoli episodi del recente passato, ma non voglio andare OT.

Il mio file, passato il controllo dell’Ufficio Immigrazione che ha preteso di scannare tutto il driver mobile, è finito, con altri millemila, sul desktop.

Doppio click per aprirlo e –sorpresa– non si vedono gli a-capo. Già Blocco note|Notepad pretende CR-LF invece del solito (per Linux) LF. Che fare?
Ovviamente è da escludere l’installazione di alcunché, anzi il web è considerato pericoloso.
La prima idea è stata quella di visualizzarlo nel browser, c’è Chrome, lo lancio, riduco in finestra e ci droppo sopra il mio file di testo.

browser

L’immagine è dal mio ‘puter, con Firefox, ma è simile a quella di cui sto raccontando.
Uhmmm… gli a-capo ci sono ma i caratteri fuori dal set ASCII non vengono visualizzati correttamente. Sì, si potrebbe dire al browser … ma così al volo, poi va a finire che ci faccio una figura barbina, già vengo visto come lunatico che uso Linux con tutte quelle diavolerie esotiche come i file di testo.

La soluzione, semplice e immediata, è di creare un documento tipo Word –in realtà LibreOffice, ormai usano quello anche loro–, aprirlo e incollarci dentro il testo del file di testo. È un’operazione immediata. Funziona. La dimensione del nuovo documento è di 22.5 kB, contro i 4.9 dell’originale.

doc

Però, questi giovani: sono molto più avanzati di me, sanno messaggiare con lo smartphone componendo i testi (brevi, sintetici) usando con una velocità che implica effetti relativistici i pollici, opponibili, quelli li avrei anch’io ma la sola idea mi spaventa da non dire.

Ma non conoscono gli elementi basilari, come il file di testo. E mettono tutto sul desktop. E usano un sacco sakko di maiuscole. E usano termini come “cartella”, “app”, “scaip”. Tutte cose che non so, a me nessuno dice mai niente :mrgreen:

Visto nel Web – 197

Finita la stagione delle ferie si torna alla solita routine –prossimamente. Intanto ecco cosa ho visto nel Web.

11935576_10206359150371376_2293463242272500239_n

Convert an Android Device to Linux
::: Linux Magazine

Documents Indicate Apple Is Building a Self-Driving Car
::: Slashdot

Mozilla Tests Improved Privacy Mode For Firefox
::: Slashdot

The Promise Of 5G
::: TechCrunch

Kjell – a refurbished Erlang shell with support for color profiles and extensions
::: karlll

IMG_5843

ACM Classic Books Series
intrigante assay; e al solito –OK :wink:
::: Lambda the Ultimate

Facebook Should Pay All of Us
::: The New Yorker

A graphic guide to algorithms
::: dlion92

Overheard at pool just now
::: extempore2

Meet Dash & Dot
Discover a new world of play, learning and adventure.
::: Make Wonder

evolution

Studente di Harvard scopre un difetto di Messenger, Facebook gli revoca lo stage
::: la Stampa

Bash Pitfalls
non nuovo ma …
::: Greg’s Wiki

ShareLaTeX has over 500,000 users!
::: sharelatex

Anti-Science Trolls are Starting Edit Wars on Wikipedia
::: Gizmodo

Rupert Murdoch Won’t Be Teaching Your Children To Code After All
::: Slashdot

Quotation-Steve-Wozniak-life-best-people-Meetville-Quotes-235195

IBM Launches Linux-Only Mainframes
::: Slashdot  ::: Amplify the Signal ::: Ubuntu Insights

State of the Haskell ecosystem – August 2015
::: Gabriel439

Lettera aperta sulla questione Office365 all’assessore alla sanità della Provincia di Bolzano
::: LibreItalia ::: Tech Economy

First feedback on my @university Scala-Java interop class today
::: travisbrown

batman

Comment atteindre Inbox Zero à la rentrée
::: CommitStrip

Using context managers in test setUp
::: Ned Batchelder

Debate Over Amazon Working Conditions Goes Back Years
::: Slashdot

Map of all Public Libraries in the USA
Jake & Python: miracoli resi ordinaria amministrazione
::: jakevdp

At 5,200 comments the Amazon story is now officially the most commented-upon story in NYT history
::: fmanjoo

0e63884d-e06a-4412-bec8-f692f0b409e1

Una storia di giornalismo: New York Times vs. Amazon
::: Giuseppe Granieri ::: Scott Berkun

Here’s what we know about the Ashley Madison hack
::: Fusion ::: Ars Technica ::: mikko ::: mikko ::: fabiochiusi

L’intelligenza artificiale contro il terrore dell’ISIS
::: Oggi Scienza

Intel: il software vocale di Stephen Hawking è ora gratuitamente scaricabile
::: Gravità Zero

Intel Promises ‘Optane’ SSDs Based On Technology Faster Than Flash In 2016
::: Slashdot

Łucja Goliasz

Łucja Goliasz

The Future Of The Web Is All About Context
::: TechCrunch

Facebook overtakes Google as referrer to news sites
::: nxthompson

Getting started with ‘The Little Prover’
sarebbe tutto un mondo nuovo da esplorare; solo che la vita è troppo breve
::: LambdaCat

Chinese police arrest 15,000 for Internet crimes
::: Reuters

Eric Lippert’s Sharp Regrets
conosco chi usa quasi solo C# anche se non ne parlo mai
::: Lambda the Ultimate

CMjouR-W8AANr7H

Smartphone, per innovare è meglio ascoltare i ragazzi
::: Wired

Com’è la sicurezza dei siti scolastici italiani? Imbarazzante
::: Il Disinformatico

For close to 90% of the #world population #LibreOffice is available in the own #language
::: libreoffice

Rural #Brazil will find alternatives to Internet.org
::: webwewant

stitchcounter-scm – Command line tool to help you with knitting and crocheting
It is a porting in Chicken Scheme of the same program I wrote in Clojure and in C
::: manuel-uberti

73153544-1b8e-4a77-a3fa-9c830645b1f9

Installare stampante multifunzione alla sister
per evitare il ritorno alla barbarie
::: dcavedon

Go 1.5 is released
::: The Go Programming Language

I nuovi analfabeti: usano Facebook, ma non sanno interpretare la realtà
::: Wired

Linus Torvalds Isn’t Looking 10 Years Ahead For Linux and That’s OK
concordo perfettamente :wink:
::: Slashdot

11095476_915321581854554_6266519450244667531_n

Une histoire de mot de passe
::: CommitStrip

Tutto l’openness che serve ai bambini in una chiavetta: Freestyle PC for Kids
::: Tech Economy

Ubuntu 15.10 To Ship With Gnome’s Overlay Scrollbars By Default, Ditching Unity’s Overlay Scrollbars
::: Web Upd8

Why Aren’t People Using Smalltalk?
::: Medium

Attacchi informatici in tempo reale
ipnotico
::: SIAMO GEEK

vr

Sergey Brin on Google Lens
::: Google+

L. Peter Deutsch invented the first interactive #Lisp REPL in 1963 when he was 17
::: RainerJoswig

Un obolo per Microsoft
::: Tech Economy

L’ #informatica nei film americani
::: Genjuro75

Annamo bene #Windows10
::: djnooz

Pinuccio

Pinuccio

Google’s feature or (wanted) bug?
::: Google+

Google integrates Twitter into its desktop search results
::: The Next Web

Meet Linux’s Newest File-System: Bcachefs
::: Slashdot

Perché Spotify vuole sapere tutto dei suoi utenti
::: Chiusi nella rete

Guida pratica al software libero… e gratuito
::: Gravità Zero

11873518_745554048904739_2378862926896776826_n

Canonical is letting the Ubuntu Software Center wither and die
::: PCWorld

I love it when I can write a single SQL
::: thomasfuchs

New recipe, HtMaB
::: jasonyeojs

casamonica

Racket – contratti – 11

ssContinuando da qui dovrei descrivere (o copiare) l’esempio che trovo qui: [doc]/guide/contracts-examples.html.

Un esempio completo

Ho un problema, grosso. Ci ho provato ma non sono riuscito a aggiungere niente di mio. L’esercizio è fattibile, chiaro ma conviene davvero vederlo di là.
Passo quindi al capitolo successivo, [doc]/guide/contracts-gotchas.html, i gotchas dei contratti. Uh! chissà come devo tradurre gotcha?

Contratti e eq?

As a general rule, adding a contract to a program should either leave the behavior of the program unchanged, or should signal a contract violation. And this is almost true for Racket contracts, with one exception: eq?.

The eq? procedure is designed to be fast and does not provide much in the way of guarantees, except that if it returns true, it means that the two values behave identically in all respects. Internally, this is implemented as pointer equality at a low-level so it exposes information about how Racket is implemented (and how contracts are implemented).

Contracts interact poorly with eq? because function contract checking is implemented internally as wrapper functions. For example, consider this module:

#lang racket
 
(define (make-adder x)
  (if (= 1 x)
      add1
      (lambda (y) (+ x y))))
(provide (contract-out
          [make-adder (-> number? (-> number? number?))]))

It exports the make-adder function that is the usual curried addition function, except that it returns Racket’s add1 when its input is 1.

You might expect that

(eq? (make-adder 1)
     (make-adder 1))

would return #t, but it does not. If the contract were changed to any/c (or even (-> number? any/c)), then the eq? call would return #t.

Moral: Do not use eq? on values that have contracts.

Confini di contratto e define/contract

The contract boundaries established by define/contract, which creates a nested contract boundary, are sometimes unintuitive. This is especially true when multiple functions or other values with contracts interact. For example, consider these two interacting functions:

c11

One might expect that the function g will be blamed for breaking the terms of its contract with f. Blaming g would be right if f and g were directly establishing contracts with each other. They aren’t, however. Instead, the access between f and g is mediated through the top-level of the enclosing module.

More precisely, f and the top-level of the module have the (-> integer? integer?) contract mediating their interaction; g and the top-level have (-> string?) mediating their interaction, but there is no contract directly between f and g. This means that the reference to f in the body of g is really the top-level of the module’s responsibility, not g‘s. In other words, the function f has been given to g with no contract between g and the top-level and thus the top-level is blamed.

If we wanted to add a contract between g and the top-level, we can use define/contract‘s #:freevar declaration and see the expected blame:

c12

Moral: if two values with contracts should interact, put them in separate modules with contracts at the module boundary or use #:freevar.

Contratti con #:exists e predicati

Much like the eq? example above, #:∃ contracts can change the behavior of a program.

Specifically, the null? predicate (and many other predicates) return #f for #:∃ contracts, and changing one of those contracts to any/c means that null? might now return #t instead, resulting in arbitrarily different behavior depending on how this boolean might flow around in the program.

To work around the above problem, the racket/exists library behaves just like racket, but predicates signal errors when given #:∃ contracts.

Moral: Do not use predicates on #:∃ contracts, but if you’re not sure, use racket/exists to be safe.

Definire contratti ricorsivi

When defining a self-referential contract, it is natural to use define. For example, one might try to write a contract on streams like this:

c13

Unfortunately, this does not work because the value of stream/c is needed before it is defined. Put another way, all of the combinators evaluate their arguments eagerly, even though the values that they accept do not.

Instead, use

c14

The use of recursive-contract delays the evaluation of the identifier stream/c until after the contract is first checked, long enough to ensure that stream/c is defined.

See also Checking Properties of Data Structures [Controllare le proprietà di strutture di dati].

Mescolare set! e contract-out

The contract library assumes that variables exported via contract-out are not assigned to, but does not enforce it. Accordingly, if you try to set! those variables, you may be surprised. Consider the following example:

c15

Both calls to print-latest print 0, even though the value of x has been incremented (and the change is visible inside the module x).

To work around this, export accessor functions, rather than exporting the variable directly, like this:

#lang racket
 
(define (get-x) x)
(define (inc-x!) (set! x (+ x 1)))
(define x 0)
(provide (contract-out [inc-x! (-> void?)]
                       [get-x (-> integer?)]))

Moral: This is a bug that we will address in a future release.

Basta con i contratti, prossimamente si cambia :mrgreen:

Racket – contratti – 10

pogo0

Sempre sui contratti, qui: [doc]/guide/contracts-general-functions.html, anzi qui: [doc]/guide/contracts-exists.html, continuando a copiare da qui.

Contratti astratti usando #:exists e #:∃

The contract system provides existential contracts that can protect abstractions, ensuring that clients of your module cannot depend on the precise representation choices you make for your data structures.

Note: You can type #:exists instead of #:∃ if you cannot easily type Unicode characters; in DrRacket, typing \exists followed by either alt-\ or control-\ (depending on your platform) will produce .
Uhmmm… con la tastiera italiana non funziona. E se proprio si vuole utilizzare si può ricorrere al solito metodo (con Linux) per i caratteri Unicode Shift-Ctrl-u e poi il codice che per exists è 2203, mentre per λ è 03bb. Inoltre con Ctrl-\ si ottiene λ in DrRacket.

The contract-out form allows you to write

#:∃ name-of-a-new-contract

as one of its clauses. This declaration introduces the variable name-of-a-new-contract, binding it to a new contract that hides information about the values it protects.

As an example, consider this (simple) implementation of a queue datastructure:

c9

This code implements a queue purely in terms of lists, meaning that clients of this data structure might use car and cdr directly on the data structure (perhaps accidentally) and thus any change in the representation (say to a more efficient representation that supports amortized constant time enqueue and dequeue operations) might break client code.

To ensure that the queue representation is abstract, we can use #:∃ in the contract-out expression, like this:

c10

Now, if clients of the data structure try to use car and cdr, they receive an error, rather than mucking about with the internals of the queues.

:roll:

Ah, vedere anche quello che seguirà prossimamente :mrgreen:

Racket – contratti – 9

fw

Oggi qui: [doc]/guide/contracts-general-functions.html, in particolare qui: [doc]/guide/contracts-struct.html continuando a raccontare (e copiare) da qui.

Contratti nelle strutture

Modules deal with structures in two ways. First they export struct definitions, i.e., the ability to create structs of a certain kind, to access their fields, to modify them, and to distinguish structs of this kind against every other kind of value in the world. Second, on occasion a module exports a specific struct and wishes to promise that its fields contain values of a certain kind. This section explains how to protect structs with contracts for both uses.

c8

Garanzie per un valore specifico

If your module defines a variable to be a structure, then you can specify the structure’s shape using struct/c:

#lang racket
(require lang/posn)
 
(define origin (make-posn 0 0))
 
(provide (contract-out
          [origin (struct/c posn zero? zero?)]))

In this example, the module imports a library for representing positions, which exports a posn structure. One of the posns it creates and exports stands for the origin, i.e., (0,0), of the grid.

Note: See also vector/c and similar contract combinators for (flat) compound data. Proprio come dicevo io :wink:

Garanzie per tutti i valori

How to Design Programs teaches that posns should contain only numbers in their two fields. With contracts we would enforce this informal data definition as follows:

#lang racket
(struct posn (x y))
 
(provide (contract-out
          [struct posn ((x number?) (y number?))]
          [p-okay posn?]
          [p-sick posn?]))
 
(define p-okay (posn 10 20))
(define p-sick (posn 'a 'b))

This module exports the entire structure definition: posn, posn?, posn-x, posn-y, set-posn-x!, and set-posn-y!. Each function enforces or promises that the two fields of a posn structure are numbers — when the values flow across the module boundary. Thus, if a client calls posn on 10 and 'a, the contract system signals a contract violation.

The creation of p-sick inside of the posn module, however, does not violate the contracts. The function posn is used internally, so 'a and 'b don’t cross the module boundary. Similarly, when p-sick crosses the boundary of posn, the contract promises a posn? and nothing else. In particular, this check does not require that the fields of p-sick are numbers.

The association of contract checking with module boundaries implies that p-okay and p-sick look alike from a client’s perspective until the client extracts the pieces:

#lang racket
(require lang/posn)
 
... (posn-x p-sick) ...

Using posn-x is the only way the client can find out what a posn contains in the x field. The application of posn-x sends p-sick back into the posn module and the result value – 'a here – back to the client, again across the module boundary. At this very point, the contract system discovers that a promise is broken. Specifically, posn-x doesn’t return a number but a symbol and is therefore blamed.

This specific example shows that the explanation for a contract violation doesn’t always pinpoint the source of the error. The good news is that the error is located in the posn module. The bad news is that the explanation is misleading. Although it is true that posn-x produced a symbol instead of a number, it is the fault of the programmer who created a posn from symbols, i.e., the programmer who added

(define p-sick (posn 'a 'b))

to the module. So, when you are looking for bugs based on contract violations, keep this example in mind.

If we want to fix the contract for p-sick so that the error is caught when sick is exported, a single change suffices:

(provide
 (contract-out
  ...
  [p-sick (struct/c posn number? number?)]))

That is, instead of exporting p-sick as a plain posn?, we use a struct/c contract to enforce constraints on its components.

Controllare le proprietà di strutture di dati

Contracts written using struct/c immediately check the fields of the data structure, but sometimes this can have disastrous effects on the performance of a program that does not, itself, inspect the entire data structure.

As an example, consider the binary search tree search algorithm. A binary search tree is like a binary tree, except that the numbers are organized in the tree to make searching the tree fast. In particular, for each interior node in the tree, all of the numbers in the left subtree are smaller than the number in the node, and all of the numbers in the right subtree are larger than the number in the node.

We can implement a search function in? that takes advantage of the structure of the binary search tree.

#lang racket
 
(struct node (val left right))
 
; determines if `n' is in the binary search tree `b',
; exploiting the binary search tree invariant
(define (in? n b)
  (cond
    [(null? b) #f]
    [else (cond
            [(= n (node-val b))
             #t]
            [( n (node-val b))
             (in? n (node-right b))])]))
 
; a predicate that identifies binary search trees
(define (bst-between? b low high)
  (or (null? b)
      (and ( . boolean?)]
          [in? (number? bst? . -> . boolean?)]))

In a full binary search tree, this means that the in? function only has to explore a logarithmic number of nodes.

The contract on in? guarantees that its input is a binary search tree. But a little careful thought reveals that this contract defeats the purpose of the binary search tree algorithm. In particular, consider the inner cond in the in? function. This is where the in? function gets its speed: it avoids searching an entire subtree at each recursive call. Now compare that to the bst-between? function. In the case that it returns #t, it traverses the entire tree, meaning that the speedup of in? is lost.

In order to fix that, we can employ a new strategy for checking the binary search tree contract. In particular, if we only checked the contract on the nodes that in? looks at, we can still guarantee that the tree is at least partially well-formed, but without changing the complexity.

To do that, we need to use struct/dc to define bst-between?. Like struct/c, struct/dc defines a contract for a structure. Unlike struct/c, it allows fields to be marked as lazy, so that the contracts are only checked when the matching selector is called. Also, it does not allow mutable fields to be marked as lazy.

The struct/dc form accepts a contract for each field of the struct and returns a contract on the struct. More interestingly, struct/dc allows us to write dependent contracts, i.e., contracts where some of the contracts on the fields depend on the values of other fields. We can use this to define the binary search tree contract:

#lang racket
 
(struct node (val left right))
 
; determines if `n' is in the binary search tree `b'
(define (in? n b) ... as before ...)
 
; bst-between : number number -> contract
; builds a contract for binary search trees
; whose values are between low and high
(define (bst-between/c low high)
  (or/c null?
        (struct/dc node [val (between/c low high)]
                        [left (val) #:lazy (bst-between/c low val)]
                        [right (val) #:lazy (bst-between/c val high)])))
 
(define bst/c (bst-between/c -inf.0 +inf.0))
 
(provide (struct-out node))
(provide (contract-out
          [bst/c contract?]
          [in? (number? bst/c . -> . boolean?)]))

In general, each use of struct/dc must name the fields and then specify contracts for each field. In the above, the val field is a contract that accepts values between low and high. The left and right fields are dependent on the value of the val field, indicated by their second sub-expressions. They are also marked with the #:lazy keyword to indicate that they should be checked only when the appropriate accessor is called on the struct instance. Their contracts are built by recursive calls to the bst-between/c function. Taken together, this contract ensures the same thing that the bst-between? function checked in the original example, but here the checking only happens as in? explores the tree.

Although this contract improves the performance of in?, restoring it to the logarithmic behavior that the contract-less version had, it is still imposes a fairly large constant overhead. So, the contract library also provides define-opt/c that brings down that constant factor by optimizing its body. Its shape is just like the define above. It expects its body to be a contract and then optimizes that contract.

(define-opt/c (bst-between/c low high)
  (or/c null?
        (struct/dc node [val (between/c low high)]
                        [left (val) #:lazy (bst-between/c low val)]
                        [right (val) #:lazy (bst-between/c val high)])))

:evil: Già detto panico? altrimenti panico! :evil:
Però –ora che ci penso– questo è già fatto, e si capisce, è OK. Basta sapere che c’è — e qui entra in campo la documentazione (ottima) :grin:

:mrgreen:

Racket – contratti – 8

t2

Continuo da qui a copiare qui [doc]/guide/contracts-general-functions.html, in particolare nella pagina [doc]/guide/contracts-first.html.

Un esempio  completo di contratto

This section develops several different flavors of contracts for one and the same example: Racket’s argmax function. According to its Racket documentation, the function consumes a procedure proc and a non-empty list of values, lst. It returns the first element in the list lst that maximizes the result of proc.

Esempi:

c7

Here is the simplest possible contract for this function (version 1):

(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax (-> (-> any/c real?) (and/c pair? list?) any/c)]))

This contract captures two essential conditions of the informal description of argmax:

  • the given function must produce numbers that are comparable according to <. In particular, the contract (-> any/c number?) would not do, because number? also recognizes complex numbers in Racket.
  • the given list must contain at least one item.

When combined with the name, the contract explains the behavior of argmax at the same level as an ML function type in a module signature (except for the non-empty list aspect).

Nota: ML function? da indagare.

Contracts may communicate significantly more than a type signature, however. Take a look at this second contract for argmax (version 2):

#lang racket
 
(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (define f@r (f r))
              (for/and ([v lov]) (>= f@r (f v))))))]))

It is a dependent contract that names the two arguments and uses the names to impose a predicate on the result. This predicate computes (f r) – where r is the result of argmax – and then validates that this value is greater than or equal to all values of f on the items of lov.

Is it possible that argmax could cheat by returning a random value that accidentally maximizes f over all elements of lov? With a contract, it is possible to rule out this possibility (version 2 rev. a):

#lang racket
 
(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (define f@r (f r))
              (and (memq r lov)
                   (for/and ([v lov]) (>= f@r (f v)))))))]))

The memq function ensures that r is intensionally equal (that is, “pointer equality” for those who prefer to think at the hardware level) to one of the members of lov. Of course, a moment’s worth of reflection shows that it is impossible to make up such a value. Functions are opaque values in Racket and without applying a function, it is impossible to determine whether some random input value produces an output value or triggers some exception. So we ignore this possibility from here on.

Version 2 formulates the overall sentiment of argmax‘s documentation, but it fails to bring across that the result is the first element of the given list that maximizes the given function f. Here is a version that communicates this second aspect of the informal documentation (version 3):

#lang racket
 
(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (define f@r (f r))
              (and (for/and ([v lov]) (>= f@r (f v)))
                   (eq? (first (memf (lambda (v) (= (f v) f@r)) lov))
                        r)))))]))

That is, the memf function determines the first element of lov whose value under f is equal to r‘s value under f. If this element is intensionally equal to r, the result of argmax is correct.

This second refinement step introduces two problems. First, both conditions recompute the values of f for all elements of lov. Second, the contract is now quite difficult to read. Contracts should have a concise formulation that a client can comprehend with a simple scan. Let us eliminate the readability problem with two auxiliary functions that have reasonably meaningful names (version 3 rev. a):

#lang racket
 
(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (define f@r (f r))
              (and (is-first-max? r f@r f lov)
                   (dominates-all f@r f lov)))))]))
 
; where
 
; f@r is greater or equal to all (f v) for v in lov
(define (dominates-all f@r f lov)
  (for/and ([v lov]) (>= f@r (f v))))
 
; r is eq? to the first element v of lov
for which (pred? v)
(define (is-first-max? r f@r f lov)
  (eq? (first (memf (lambda (v) (= (f v) f@r)) lov)) r))

The names of the two predicates express their functionality and, in principle, render it unnecessary to read their definitions.

This step leaves us with the problem of the newly introduced inefficiency. To avoid the recomputation of (f v) for all v on lov, we change the contract so that it computes these values and reuses them as needed (version 3 rev. b):

#lang racket
 
(define (argmax f lov) ...)
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (define f@r (f r))
              (define flov (map f lov))
              (and (is-first-max? r f@r (map list lov flov))
                   (dominates-all f@r flov)))))]))
 
; where
 
; f@r is greater or equal to all f@v in flov
(define (dominates-all f@r flov)
  (for/and ([f@v flov]) (>= f@r f@v)))
 
; r is (first x) for the first
x in lov+flov s.t. (= (second x) f@r)
(define (is-first-max? r f@r lov+flov)
  (define fst (first lov+flov))
  (if (= (second fst) f@r)
      (eq? (first fst) r)
      (is-first-max? r f@r (rest lov+flov))))

Now the predicate on the result once again computes all values of f for elements of lov once.

Note: The word “eager” comes from the literature on the linguistics of contracts.

Version 3 may still be too eager when it comes to calling f. While Racket’s argmax always calls f no matter how many items lov contains, let us imagine for illustrative purposes that our own implementation first checks whether the list is a singleton. If so, the first element would be the only element of lov and in that case there would be no need to compute (f r).
The argmax of Racket implicitly argues that it not only promises the first value that maximizes f over lov but also that f produces/produced a value for the result.
As a matter of fact, since f may diverge or raise an exception for some inputs, argmax should avoid calling f when possible.

The following contract demonstrates how a higher-order dependent contract needs to be adjusted so as to avoid being over-eager (version 4):

#lang racket
 
(define (argmax f lov)
  (if (empty? (rest lov))
      (first lov)
      ...))
 
(provide
 (contract-out
  [argmax
    (->i ([f (-> any/c real?)] [lov (and/c pair? list?)]) ()
         (r (f lov)
            (lambda (r)
              (cond
                [(empty? (rest lov)) (eq? (first lov) r)]
                [else
                 (define f@r (f r))
                 (define flov (map f lov))
                 (and (is-first-max? r f@r (map list lov flov))
                      (dominates-all f@r flov))]))))]))
 
; where
 
; f@r is greater or equal to all f@v in flov
(define (dominates-all f@r lov) ...)
 
; r is (first x) for the first
x in lov+flov s.t. (= (second x) f@r)
(define (is-first-max? r f@r lov+flov) ...)

Note that such considerations don’t apply to the world of first-order contracts. Only a higher-order (or lazy) language forces the programmer to express contracts with such precision.

The problem of diverging or exception-raising functions should alert the reader to the even more general problem of functions with side-effects. If the given function f has visible effects – say it logs its calls to a file – then the clients of argmax will be able to observe two sets of logs for each call to argmax. To be precise, if the list of values contains more than one element, the log will contain two calls of f per value on lov. If f is expensive to compute, doubling the calls imposes a high cost.

To avoid this cost and to signal problems with overly eager contracts, a contract system could record the i/o of contracted function arguments and use these hashtables in the dependency specification. This is a topic of on-going research in PLT. Stay tuned.

Panico :evil: Anche se a un esame più approfondito comincia a sembrare più sensato, essendo mooolto eager. Nota del giorno dopo: si può fare :grin:

:mrgreen:

E se … Windows 10

w10Un altro post estivo, risultano molto più graditi di quelli del meraviglioso Racket. Oggi racconto di un colloquio informale avvenuto la settimana scorsa, con una giovane amica che si sta laureando in una disciplina umanistica. La laureanda (candidata? così è definita nella bozza praticamente definitiva della tesi che attende solo l’esame e OK finale della relatrice) è un’amica di famiglia che a inizio anno mi aveva coinvolto, ho scritto un paio di pagine in formato ODF che poi lei ha corretto e inserito nella tesi senza nemmeno stravolgerle tanto. E voleva la conferma che fossero ancora come le avevo divisate (si dice vero?).

Nel frattempo per la stesura della tesi si è reso necessario l’acquisto di un nuovo ‘puter, anche perché l’altro è della sorella, anche lei alle prese con la tesi, questa di secondo livello (si dice vero?). Il ‘puter è particolare: un notebook piccolino, di HP, preso a un prezzo incredibilmente conveniente dal papà di un amico. Tutto OK :grin:

Ah! hai messo su Windows 10!” dico io, dopo un po’; sono perspicace ma non troppo e poi con LibreOffice a pieno schermo (OK, lo schermo è piccolo e dovevo solo leggere un paio di pagine dopo aver visto le parti indicatemi, e tutto senza mouse).
Sì! tando dovrò abituarmi” è la risposta, sensata, corretta, onesta.

A dire il vero sono dell’idea che con un sistema operativo più serio il notebook sarebbe più performante ma non era il caso di passare una volta ancora per ripetitivo e monomaniaco. E poi assolutamente non in questo momento con la tesi praticamente pronta.
Anche se, per dirne una, le immagini (non fanno parte della tesi ma sono servite per la stessa) con Linux un altro OS si potrebbero gestire meglio.
Già le immagini: vengono da due fonti: una reflex digitale dalle caratteristiche impressionanti, non le dico perché non so se mi credereste e lo smartphone.
Va a finire che spesso vengono dal telefono, sono più che buone anche quelle ed è molto più pratico, ce l’hai sempre con te.

Qui la vera sorpresa: “devo cambiarlo, questo è vecchio…“, sì certo, questi aggeggi hanno un’obsolescenza accelerata, mica come me che sono sempre attuale (entro certi limiti) con 60+ anni!
E lo voglio con Windows, ormai ce l’hanno tutti così“.
Questa non la sapevo. Anzi, sarà vero? O –come spero– vale solo per il suo ecosistema?
Anche perché proprio in questi giorni …
E poi anche ‘buntu, mi dicono, promette bene; magari non adesso ma presto, chissà. E c’è anche Jolla. Si anche un altro ma non mi viene il nome, sapete la memoria :wink:

Racket – contratti – 7

m5

Sempre sui contratti, qui: [doc]/guide/contracts-general-functions.html, continuando da qui.

Controllare i cambiamenti

The ->i contract combinator can also ensure that a function only modifies state according to certain constraints. For example, consider this contract (it is a slightly simplified version from the function preferences:add-panel in the framework):

(->i ([parent (is-a?/c area-container-window)])
      [_ (parent)
       (let ([old-children (send parent get-children)])
         (λ (child)
           (andmap eq?
                   (append old-children (list child))
                   (send parent get-children))))])

It says that the function accepts a single argument, named parent, and that parent must be an object matching the interface area-container-window<%>.

Nota: mystero –forse– per <%>.

The range contract ensures that the function only modifies the children of parent by adding a new child to the front of the list. It accomplishes this by using the _ instead of a normal identifier, which tells the contract library that the range contract does not depend on the values of any of the results, and thus the contract library evaluates the expression following the _ when the function is called, instead of when it returns. Therefore the call to the get-children method happens before the function under the contract is called. When the function under contract returns, its result is passed in as child, and the contract ensures that the children after the function return are the same as the children before the function called, but with one more child, at the front of the list.

Nota: _ uhmmm, c’è la guida :grin: Chissà se occorrerà usare roba così :roll:

To see the difference in a toy example that focuses on this point, consider this program

#lang racket
(define x '())
(define (get-x) x)
(define (f) (set! x (cons 'f x)))
(provide
 (contract-out
  [f (->i () [_ (begin (set! x (cons 'ctc x)) any/c)])]
  [get-x (-> (listof symbol?))]))

If you were to require this module, call f, then the result of get-x would be '(f ctc). In contrast, if the contract for f were

(->i () [res (begin (set! x (cons 'ctc x)) any/c)])

(only changing the underscore to res), then the result of get-x would be '(ctc f).

Risultati con valori multipli

The function split consumes a list of chars and delivers the string that occurs before the first occurrence of #\newline –if any– and the rest of the list:

(define (split l)
  (define (split l w)
    (cond
      [(null? l) (values (list->string (reverse w)) '())]
      [(char=? #\newline (car l))
       (values (list->string (reverse w)) (cdr l))]
      [else (split (cdr l) (cons (car l) w))]))
  (split l '()))

It is a typical multiple-value function, returning two values by traversing a single list.

The contract for such a function can use the ordinary function arrow ->, since -> treats values specially when it appears as the last result:

(provide (contract-out
          [split (-> (listof char?)
                     (values string? (listof char?)))]))

The contract for such a function can also be written using ->*:

(provide (contract-out
          [split (->* ((listof char?))
                      ()
                      (values string? (listof char?)))]))

As before, the contract for the argument with ->* is wrapped in an extra pair of parentheses (and must always be wrapped like that) and the empty pair of parentheses indicates that there are no optional arguments. The contracts for the results are inside values: a string and a list of characters.

Now, suppose that we also want to ensure that the first result of split is a prefix of the given word in list format. In that case, we need to use the ->i contract combinator:

(define (substring-of? s)
  (flat-named-contract
    (format "substring of ~s" s)
    (lambda (s2)
      (and (string? s2)
           (i ([fl (listof char?)])
              (values [s (fl) (substring-of? (list->string fl))]
                      [c (listof char?)]))]))

Like ->*, the ->i combinator uses a function over the argument to create the range contracts. Yes, it doesn’t just return one contract but as many as the function produces values: one contract per value. In this case, the second contract is the same as before, ensuring that the second result is a list of chars. In contrast, the first contract strengthens the old one so that the result is a prefix of the given word.

This contract is expensive to check, of course. Here is a slightly cheaper version:

(provide
 (contract-out
  [split (->i ([fl (listof char?)])
              (values [s (fl) (string-len/c (length fl))]
                      [c (listof char?)]))]))

:shock: :roll: :grin:

Arità fisse ma non note

Imagine yourself writing a contract for a function that accepts some other function and a list of numbers that eventually applies the former to the latter. Unless the arity of the given function matches the length of the given list, your procedure is in trouble.

Consider this n-step function:

c4

The argument of n-step is proc, a function proc whose results are either numbers or false, and a list. It then applies proc to the list inits. As long as proc returns a number, n-step treats that number as an increment for each of the numbers in inits and recurs. When proc returns false, the loop stops.

Here are two uses:

c5

and

c6

A contract for n-step must specify two aspects of proc‘s behavior: its arity must include the number of elements in inits, and it must return either a number or #f. The latter is easy, the former is difficult. At first glance, this appears to suggest a contract that assigns a variable-arity to proc:

(->* ()   ;; wrong!
     #:rest (listof any/c)
     (or/c number? false/c))

This contract, however, says that the function must accept any number of arguments, not a specific but undetermined number. Thus, applying n-step to (lambda (x) x) and (list 1) breaks the contract because the given function accepts only one argument.

The correct contract uses the unconstrained-domain-> combinator, which specifies only the range of a function, not its domain. It is then possible to combine this contract with an arity test to specify the correct contract for n-step:

(provide
 (contract-out
  [n-step
   (->i ([proc (inits)
          (and/c (unconstrained-domain->
                  (or/c false/c number?))
                 (λ (f) (procedure-arity-includes?
                         f
                         (length inits))))]
         [inits (listof number?)])
        ()
        any)]))

:mrgreen:

Niente è meglio della linea di comando del terminale

mmasUn post estivo e per chi inizia. Anche se è appena tornato utile a me.
Il guaio è che la mia memoria non è più quella di una volta (e com’era allora non lo ricordo). Per esempio mi sono trovato in difficoltà a valutare l’output di diff per un caso come questo (in realtà molto più lungo, il post di domani):

d0

La differenza tra i due files è minima: il carattere ' nel primo è sostituito con nel secondo.

A dire il vero c’è un tool con tanto di grafica che aiuta, meld:

d1

ma in casi come questo poi si deve andare a cercare l’ago nel pagliaio come con diff.

E, se lanciato da terminale ci sono le lamentele, solite, ormai mi sono abituato:

d2

Ma forse si può fare qualcosa. Una delle caratteristiche di Unix quando questo era giovane e una cosa che i programmatori che venivano da altri sistemi operativi trovavano –spesso– ostico erano le opzioni da dare ai comandi. E i comandi stessi erano criptici (cp invece di copy, per risparmiare? ci voleva tanto a scrivere “copy“?) e poi il minuscolo; ma questo ci porterebbe OT :wink:
Con il tempo il numero di opzioni è cresciuto, Linux è molto più ricco e user-friendly (sto parlando per chi lo usa senza finestre).

diff ha le sue opzioni che posso visualizzare con man diff.
Parlando ancora di una volta quando gli hard disks erano piccoli e sempre troppo pieni c’era chi aveva il vizio di cancellare i files di man, cosa abominevole :sad:
Però anche man può essere migliorato. Per esempio posso usarlo in combinazione con un tool che mi salva l’output in PDF. Cito solo man2pdf, da installare, funziona come si deve.

In alternativa si può usare un opzione di man, -t, come spiegato qui. Visto che le opzioni sono una cosa bella? E che invece non era bella la prassi di cancellare i files di man per fare spazio? :grin:

Ok, torno al mio caso. Qualche tentativo e sono giunto a:

d3

dove si vede chiaramente che ci sono righe lunghe che differiscono nei due files. Ma essendo lunghe cosa cambi non si vede. Entri grep:

d4

OK :grin:

Ah, momenti dimenticavo: ovviamente ho l’alias grep='grep --color=auto' altrimenti avrei dovuto inserirlo nel comando precedente, così: grep --color=auto "[^\ ]['|’]" c-7*

:mrgreen:

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 88 follower