From HtDP to Racket. Racket (1): #lang, local definitions, minor tweaks

TOC of the series

1. ISBN Extraction in ISL+ with regular expressions
2. Racket: #lang, local definitions
3. Racket: only-in, rackunit, test submodules
4. Racket: for, match, sequences
5. Racket: provide, contracts
6. Racket: I/O, optional and keyword arguments, point-free style
7. Racket: exception handling, http requests, JSON

The very first thing we need to do in order to change from ISL to Racket is to select the appropriate language via the DrRacket's menu 'Language:Choose Language'.

We will choose #lang racket/base. You can also select #lang racket. The first option loads the base of Racket, and everything else has to be required on demand. The second option loads the core and many other libraries.

With this addition the racket/base requirement of our previous version is, of course, no longer needed.

Before trying to run the code, please comment out all tests. We will look into them in the next post.

If you run the code now you will get a syntax error. This is expected. ISL+ is not Racket.

A first quick fix is to require racket/list, which provides functions like range, empty?, and first used in our prior implementation.

Another simple fix has to do with symbol=?. symbol=? is provided by racket/bool. You could require that module. Or, as we are going to do, use the more generic equal?. In general, though, it is better to use a specific function like symbol=?.

explode is another function only available in teaching languages. You have two options here: implementing your own version of explode or refactoring the function that uses explode, isbn-string->numbers. We choose the second approach, that iterates now on Char's instead of on 1String's.

A more serious modification has to do with local definitions. This is an *SL construct. Most of the time you should use a simple define instead, but you may need let forms in other special cases.

The resulting transformation looks as follows:

; ----------------------------------------------------------
; isbn-racket.v1.rkt
; - local -> define
; - require racket/list
; - isbn-string->numbers refactored
; - symbol=? -> equal? [or require racket/bool]
; ----------------------------------------------------------

#lang racket/base

(require racket/list)   ;empty?, first, range
(require racket/string) ;string-normalize-spaces
                        ;string-replace
                        ;string-split
;(require racket/file) ;file->string (for tests)

; ----------------------------------------------------------
; Data Types

; An ISBN is one of:
; - ISBN-13
; - ISBN-10

; An ISBN-String is one of:
; - ISBN-13-String
; - ISBN-10-String

; An ISBN-13 is an valid ISBN-13-String
; An ISBN-10 is an valid ISBN-10-String
; where valid means that the numbers in that string
; fullfil a certain mathematical computation. (See
; ISBN User Manual for information about this computation)
(define isbn-13-ex "9781593274917")
(define isbn-10-ex "0262062186")

; An ISBN-13-String is a String consisting of 13 digits,
; where a digit is one of '0', '1', ..., '9'.
(define isbn-13-str-ex "1234567890123")

; An ISBN-10-String is a String consisting of 9 digits,
; and a last letter that can be a digit or 'X'.
(define isbn-10-str-ex-1 "1234567890")
(define isbn-10-str-ex-2 "123456789X")

; An ISBN-Format is one of:
; - 'isbn-13
; - 'isbn-10

; ----------------------------------------------------------
; Patterns and Regexes
; [See ISBN International User Manual 7e. Sect. 5]

; - Pattern Components
(define pat-isbn-sep "[ -]")
(define pat-isbn-id "ISBN(-1[03])?:? ")
(define pat-isbn-13-id "(?:ISBN(?:-13)?:? )?")
(define pat-isbn-10-id "(?:ISBN(?:-10)?:? )?")
(define pat-isbn-prefix "97[89][ -]")
(define pat-isbn-registration "\\d{1,5}[ -]")
(define pat-isbn-registrant "\\d{1,7}[ -]")
(define pat-isbn-publication "\\d{1,6}[ -]")
(define pat-isbn-13-check "\\d")
(define pat-isbn-10-check "[X\\d]")

; - Look ahead to ISBN groups
(define pat-isbn-13-look-ahead
  (string-append "(?=" pat-isbn-prefix pat-isbn-registration ")"))

(define pat-isbn-10-look-ahead
  (string-append "(?=" pat-isbn-registration ")")) 

; - Main patterns
(define pat-isbn-13/groups
  (string-append pat-isbn-13-id
                 pat-isbn-13-look-ahead
                 pat-isbn-prefix
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-13-check))

(define pat-isbn-10/groups
  (string-append pat-isbn-10-id
                 pat-isbn-10-look-ahead
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-10-check))

(define pat-isbn-13/prefix
  (string-append pat-isbn-13-id pat-isbn-prefix "\\d{10}"))

(define pat-isbn-13-norm "\\d{13}")

(define pat-isbn-10-norm "\\d{9}[X\\d]")

(define pat-isbn-13
  (string-append pat-isbn-13-norm "|"
                 pat-isbn-13/prefix "|"
                 pat-isbn-13/groups))

(define pat-isbn-10
  (string-append pat-isbn-10-norm "|"
                 pat-isbn-10/groups))

(define pat-isbn
  (string-append pat-isbn-13 "|"
                 pat-isbn-10))

; - Regexes
(define re-isbn-id (regexp pat-isbn-id))
(define re-isbn-sep (regexp pat-isbn-sep))
(define re-isbn-13 (pregexp pat-isbn-13))
(define re-isbn-10 (pregexp pat-isbn-10))
(define re-isbn-13-norm (pregexp pat-isbn-13-norm))
(define re-isbn-10-norm (pregexp pat-isbn-10-norm))
(define re-isbn (pregexp pat-isbn))

; ----------------------------------------------------------
; Predicates
#|
(check-expect (isbn? "9781593274917") #t)
(check-expect (isbn? "0262062186") #t)
(check-expect (isbn? #f) #f)
  
(check-expect (isbn-13? "9781593274917") #t)
(check-expect (isbn-13? "0262062186") #f)
(check-expect (isbn-13? "") #f)
  
(check-expect (isbn-10? "9781593274917") #f)
(check-expect (isbn-10? "0262062186") #t)
(check-expect (isbn-10? 1) #f)
  
(check-expect (isbn-string? "9781593274912") #t)
(check-expect (isbn-string? "026206218X") #t)
(check-expect (isbn-string? "97815932749122") #f) ;too long
(check-expect (isbn-string? "978159327491") #f)   ;too short
(check-expect (isbn-string? "0262062189X") #f)    ;too long
(check-expect (isbn-string? "026206218") #f)      ;too short
(check-expect (isbn-string? "0-262-06218-6") #f)
  
(check-expect (isbn-13-string? "9781593274912") #t)
(check-expect (isbn-13-string? "97815932749122") #f) ;too long
(check-expect (isbn-13-string? "978159327491") #f)   ;too short
(check-expect (isbn-13-string? #f) #f)
  
(check-expect (isbn-10-string? "026206218X") #t)
(check-expect (isbn-10-string? "0262062189X") #f) ;too long
(check-expect (isbn-10-string? "026206218") #f)   ;too short
(check-expect (isbn-10-string? #f) #f)
  
(check-expect (isbn-format? 'isbn-13) #t)
(check-expect (isbn-format? 'isbn-10) #t)
(check-expect (isbn-format? "isbn-10") #f)
|#  
(define (isbn? v)
  (or (isbn-13? v) (isbn-10? v)))

(define (isbn-13? v)
  (and (isbn-13-string? v) (isbn-13-valid? v)))

(define (isbn-10? v)
  (and (isbn-10-string? v) (isbn-10-valid? v)))

(define (isbn-string? v)
  (or (isbn-13-string? v) (isbn-10-string? v)))

(define (isbn-13-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-13-norm v)))

(define (isbn-10-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-10-norm v)))

(define (isbn-format? v)
  (or (equal? v 'isbn-13) (equal? v 'isbn-10)))

; ----------------------------------------------------------
; ISBN Validation

; ISBN-13-String -> Boolean
; is the given isbn-13 string a valid isbn-13
#|
(check-expect (isbn-13-valid? "9781593274917") #t)
(check-expect (isbn-13-valid? "9780201896831") #t)
(check-expect (isbn-13-valid? "9781593274912") #f)
(check-expect (isbn-13-valid? "9780201896834") #f)
|#
(define (isbn-13-valid? isbn-str)
  (isbn-checksumf (isbn-string->numbers isbn-str)
                  '(1 3 1 3 1 3 1 3 1 3 1 3 1)
                  10))

; ISBN-10-String -> Boolean
; is the given isbn-10 string a valid isbn-10
#|
(check-expect (isbn-10-valid? "0262062186") #t)
(check-expect (isbn-10-valid? "026256114X") #t)
(check-expect (isbn-10-valid? "026206218X") #f)
(check-expect (isbn-10-valid? "0262561141") #f)
|#
(define (isbn-10-valid? isbn-str)
  (isbn-checksumf (isbn-string->numbers isbn-str)
                  (range 10 0 -1)
                  11))

; [List-of N] [List-of N] N -> Boolean
; abstract checksum algorithm for isbn validation
#|
(check-expect (isbn-checksumf '(9 7 8 1 5 9 3 2 7 4 9 1 7)
                              '(1 3 1 3 1 3 1 3 1 3 1 3 1)
                              10) #t)
(check-expect (isbn-checksumf '(0 2 6 2 0 6 2 1 8 10)
                              (range 10 0 -1)
                              11) #f)
|#
(define (isbn-checksumf multiplicands multipliers mod)
  (define sum (foldl + 0 (map * multiplicands multipliers)))
  (zero? (modulo sum mod)))

; ISBN-String -> [List-of N]
; translates str into the numbers their isbn letters represent
#|
(check-expect (isbn-string->numbers "026256114X")
              '(0 2 6 2 5 6 1 1 4 10))
|#
(define (isbn-string->numbers str)
  (define (isbn-digit->number char)
    (cond
      [(char=? char #\X) 10]
      [else (string char)]))
  (map isbn-digit->number (string->list str)))

; ----------------------------------------------------------
; ISBN Extraction

; String -> [List-of ISBN]
; extracts all isbns from str
#|  
(check-expect (isbn-find/list "") '())
(check-expect (isbn-find/list "none") '())
(check-expect
 (isbn-find/list (file->string "test-isbn-examples"))
 (list
  ;isbn normalized
  "0262062186" "026256114X" "1593274912"
  "9781593274917" "0201896834" "9780201896831"
  ;isbn w/ several id's a sep's
  "0262062186" "026256114X" "0262062186" "0201896834"
  "9780201896831" "026256114X" "9780201896831"))
|#
(define (isbn-find/list str)
  (define candidates
    (foldr append '()
           (map isbn-match* (string-split str "\n"))))
  (filter isbn? (map isbn-normalize candidates)))

; String ISBN-Format -> [Maybe ISBN]
; extracts the first isbn of given format from str, if any
#|
(check-expect (isbn-find "" 'isbn-13) #f)
(check-expect (isbn-find "" 'isbn-10) #f)
(check-expect (isbn-find "0262062186" 'isbn-13) #f)
(check-expect (isbn-find "9781593274917" 'isbn-10) #f)
(check-expect (isbn-find (file->string "test-isbn-examples")
                         'isbn-13)
              "9781593274917")
(check-expect (isbn-find (file->string "test-isbn-examples")
                         'isbn-10)
              "0262062186")
|#
(define (isbn-find str format)
  (define p?
    (cond [(equal? format 'isbn-13) isbn-13?]
          [(equal? format 'isbn-10) isbn-10?]))
  (define isbns
    (filter p? (isbn-find/list str)))
  (cond
    [(empty? isbns) #f]
    [else (first isbns)]))
    
; ----------------------------------------------------------
; Helpers

; String -> [List-of String]
; matches substrings in the given string looking like isbn tags
#|
(check-expect (isbn-match* "") '())
(check-expect (isbn-match* "abc\nd") '())
(check-expect
 (isbn-match* (file->string "test-isbn-examples"))
 (list
  ;isbn normalized (all matched)
  "0262062186" "026256114X" "1593274912"
  "9781593274917" "0201896834" "9780201896831"
  ;isbn w/ several id's and sep's (all matched)
  "ISBN 0-262-06218-6"
  "ISBN: 0 262 56114 X"
  "ISBN-10 0 262 06218-6"
  "ISBN-10: 0-201-89683-4"
  "ISBN-13: 978-0-201-89683-1"
  "ISBN-10: 0 262 56114 X"
  "ISBN-13: 978-0201896831"
  ;not isbn strings (usually impossible in real-world)
  "026206218X" "0262561141" "9780201896834" ;partially matched
  ;isbn strings, but isbn invalid (all matched)
  "026206218X" "0262561141" "1593274913"
  "9781593274912" "0201896833" "9780201896834"))
|#
(define (isbn-match* str)
  (regexp-match* re-isbn (string-normalize-spaces str)))

; String -> String
; removes the isbn-id and, then, the isbn separators from str
#|
(check-expect (isbn-normalize "123-45 67") "1234567")
(check-expect (isbn-normalize "ISBN 123") "123")
(check-expect (isbn-normalize "ISBN: 123") "123")
(check-expect (isbn-normalize "ISBN-10 123") "123")
(check-expect (isbn-normalize "ISBN-10: 123") "123")
(check-expect (isbn-normalize "ISBN-13 123") "123")
(check-expect (isbn-normalize "ISBN-13: 123") "123")
(check-expect (isbn-normalize "ISBN-14: hi") "ISBN14:hi")
|#
(define (isbn-normalize str)
  (string-replace
   (string-replace str re-isbn-id "") re-isbn-sep ""))

Next article in the series: Racket: only-in, rackunit, test submodules

From HtDP to Racket. ISBN extraction in ISL+

WARNING: This series is deprecated. The up-to-date version can be found here

TOC of the series

1. ISBN Extraction in ISL+ with regular expressions
2. Racket: #lang, local definitions
3. Racket: only-in, rackunit, test submodules
4. Racket: for, match, sequences
5. Racket: provide, contracts
6. Racket: I/O, optional and keyword arguments, point-free style
7. Racket: exception handling, http requests, JSON

If you have read the book How to Design Programs (HtDP) you already know some parts of Racket, the language on which BSL, ISL, etc. are built. And you may wish to get more stuff about Racket itself and find out how to translate your HtDP skills into full Racket.

You could read the book Realm of Racket, where Racket is introduced as needed in a friendly setting familiar to HtDP readers. You could even try The Racket Guide, a gently and complete introduction to the language. But you may miss something in the middle, something not so terse as The Guide, written from (professional) programmers to (professional) programmers, but more systematic than the Realm.

That's the intent of this series of posts. Its purpose is to show by means of an example how to start the transition from HtDP languages (in particular, ISL+) to Racket. At least, what new things to consider when working directly in Racket.

An example cannot be complete at all, though. Racket is a very rich language, and sooner than later you'll need to go deeply into The Guide and The Racket Reference. So take them as a first step into Racket for whom already masters HtDP.

A public repository for the code presented in this series is available at FromHtDPtoRacket (git repo)

The sample problem we are going to tackle says as follows:

Create a program to obtain bibliographic information about pdf books. It is assumed that those pdfs are readable (meaning that they are not made of photos of pages) and, for simplicity, unencrypted.

This task can be naturally designed as a composition of the following sub-tasks:

1. Read the text contained in the pdf pages.
2. Search for the ISBN on those pages.
3. Retrieve from a remote provider information about the book with that ISBN.
4. Parse the response to represent it as a Racket data type.

The second sub-task will be implemented entirely in ISL+, with the aid of a few Racket batteries. From the ISL+ implementation a Racket version will be derived. How to go from the ISL version to the Racket version is the main subject of these posts.

For completeness, an initial solution to the rest of the steps will be given directly in Racket.

Regarding the exposition I don't want to be verbose in describing all Racket constructs presented. The aim is not to explain Racket. Instead, I'll introduce those constructs when needed, and point to places in the Racket documentation that explain them.

Let's get started with the second step, the extraction of the ISBN, if any, from an input string.

This involves, of course, domain knowledge. See https://www.isbn-international.org/content/isbn-users-manual for more information (specifically, Section 5).

In summary, an ISBN can be of two types (formats): ISBN-10 and ISBN-13. The number itself is a string of 13 or 10 digits (from '0' to '9'), respectively. ISBN-10 accepts 'X' as last digit, too. An ISBN-10 number consists of four groups of digits, three of them of variable length (the first group can have up to 5 digits; the second up to 7 digits; the third up to 6 digits), the last group is a single digit. In turn, an ISBN-13 has one more group, a prefix of 3 digits, currently: 978 or 979. Groups may appear separated by hyphens or spaces. So we could see forms like the following:

0262062186 
0-262-06218-6 
0 262 06218 6 
9780201896831 
978-0-201-89683-1 
978 0 201 89683 1 
978-0201896831

In printed books, that number is typically preceded by an identifier that can appear under different guises:

ISBN 
ISBN: 
ISBN-10 
ISBN-13 
ISBN-10: 
ISBN-13:

followed by a space before the number itself.

Additionally, a string matching that format is an actual ISBN if it passes a validity check, that involves an arithmetic operation. See the ISBN User Manual cited above for a description of the algorithm.

Although it is possible to devise a pure ISL+ implementation, it is better to resort to Racket regular expressions support, if only because the resulting Racket version will share the very same design with the ISL-with-regexes version. Otherwise, the ISL code would be quite different, and the translation into Racket not so seamless.

Regular expressions support is in the core of Racket, so we need to require racket/base to use it. A warning, though: don't require racket/base in your ISL projects. if you really need it, just get into full Racket.

We will also require a couple of libraries to apply a few functions: file->string from racket/file for some test cases (you could use in place the function read-file from 2htdp/batch-io), and, for brevity, three string functions, that you could design on your own by following the HtDP recipe (string-split, string-replace, and string-normalize-spaces).

The first section of the code is, as HtDP mandates, a description of the data types we will use to represent the information at hand.

Next, patterns and regular expressions embedding the description of ISBN forms described above are created.

For details about regular expressions patterns and the functions regexp-match-exact? and regexp-match* see Regular Expressions [Racket Guide], and Regular Expressions [Racket Reference]

The next part contains predicates concerning all the data types of the first section. In fact, those predicates should be enough for any programmer as a precise description of the data types involved.

The rest proposes an implementation. It begins with functions to validate isbn-string's according to the required mathematical algorithm. (Note, by the way, that isbn-checksumf is an abstract function obtained by following the design recipe explained in HtDP/2e (Part III))

The main functions are isbn-find/list and isbn-find, which produce a list of all isbn's found in a string, or the first isbn of a given isbn-format found in a string, respectively. The basic strategy is to search for sub-strings in all the lines of the input that look like an ISBN, and select from the candidates those that, previously normalized, are actual ISBNs.

This is the code:

; ----------------------------------------------------------
; isbn-isl-with-batteries.rkt
; ----------------------------------------------------------

(require racket/base) ;for regexes support
(require racket/string) ;string-normalize-spaces
                        ;string-replace
                        ;string-split
(require racket/file) ;file->string (for tests)

; ----------------------------------------------------------
; Data Types

; An ISBN is one of:
; - ISBN-13
; - ISBN-10

; An ISBN-String is one of:
; - ISBN-13-String
; - ISBN-10-String

; An ISBN-13 is an valid ISBN-13-String
; An ISBN-10 is an valid ISBN-10-String
; where valid means that the numbers in that string
; fullfil a certain mathematical computation. (See
; ISBN User Manual for information about this computation)
(define isbn-13-ex "9781593274917")
(define isbn-10-ex "0262062186")

; An ISBN-13-String is a String consisting of 13 digits,
; where a digit is one of '0', '1', ..., '9'.
(define isbn-13-str-ex "1234567890123")

; An ISBN-10-String is a String consisting of 9 digits,
; and a last letter that can be a digit or 'X'.
(define isbn-10-str-ex-1 "1234567890")
(define isbn-10-str-ex-2 "123456789X")

; An ISBN-Format is one of:
; - 'isbn-13
; - 'isbn-10

; ----------------------------------------------------------
; Patterns and Regexes
; [See ISBN International User Manual 7e. Sect. 5]

; - Pattern Components
(define pat-isbn-sep "[ -]")
(define pat-isbn-id "ISBN(-1[03])?:? ")
(define pat-isbn-13-id "(?:ISBN(?:-13)?:? )?")
(define pat-isbn-10-id "(?:ISBN(?:-10)?:? )?")
(define pat-isbn-prefix "97[89][ -]")
(define pat-isbn-registration "\\d{1,5}[ -]")
(define pat-isbn-registrant "\\d{1,7}[ -]")
(define pat-isbn-publication "\\d{1,6}[ -]")
(define pat-isbn-13-check "\\d")
(define pat-isbn-10-check "[X\\d]")

; - Look ahead to ISBN groups
(define pat-isbn-13-look-ahead
  (string-append "(?=" pat-isbn-prefix pat-isbn-registration ")"))

(define pat-isbn-10-look-ahead
  (string-append "(?=" pat-isbn-registration ")")) 

; - Main patterns
(define pat-isbn-13/groups
  (string-append pat-isbn-13-id
                 pat-isbn-13-look-ahead
                 pat-isbn-prefix
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-13-check))

(define pat-isbn-10/groups
  (string-append pat-isbn-10-id
                 pat-isbn-10-look-ahead
                 pat-isbn-registration
                 pat-isbn-registrant
                 pat-isbn-publication
                 pat-isbn-10-check))

(define pat-isbn-13/prefix
  (string-append pat-isbn-13-id pat-isbn-prefix "\\d{10}"))

(define pat-isbn-13-norm "\\d{13}")

(define pat-isbn-10-norm "\\d{9}[X\\d]")

(define pat-isbn-13
  (string-append pat-isbn-13-norm "|"
                 pat-isbn-13/prefix "|"
                 pat-isbn-13/groups))

(define pat-isbn-10
  (string-append pat-isbn-10-norm "|"
                 pat-isbn-10/groups))

(define pat-isbn
  (string-append pat-isbn-13 "|"
                 pat-isbn-10))

; - Regexes
(define re-isbn-id (regexp pat-isbn-id))
(define re-isbn-sep (regexp pat-isbn-sep))
(define re-isbn-13 (pregexp pat-isbn-13))
(define re-isbn-10 (pregexp pat-isbn-10))
(define re-isbn-13-norm (pregexp pat-isbn-13-norm))
(define re-isbn-10-norm (pregexp pat-isbn-10-norm))
(define re-isbn (pregexp pat-isbn))

; ----------------------------------------------------------
; Predicates

(check-expect (isbn? "9781593274917") #t)
(check-expect (isbn? "0262062186") #t)
(check-expect (isbn? #f) #f)
  
(check-expect (isbn-13? "9781593274917") #t)
(check-expect (isbn-13? "0262062186") #f)
(check-expect (isbn-13? "") #f)
  
(check-expect (isbn-10? "9781593274917") #f)
(check-expect (isbn-10? "0262062186") #t)
(check-expect (isbn-10? 1) #f)
  
(check-expect (isbn-string? "9781593274912") #t)
(check-expect (isbn-string? "026206218X") #t)
(check-expect (isbn-string? "97815932749122") #f) ;too long
(check-expect (isbn-string? "978159327491") #f)   ;too short
(check-expect (isbn-string? "0262062189X") #f)    ;too long
(check-expect (isbn-string? "026206218") #f)      ;too short
(check-expect (isbn-string? "0-262-06218-6") #f)
  
(check-expect (isbn-13-string? "9781593274912") #t)
(check-expect (isbn-13-string? "97815932749122") #f) ;too long
(check-expect (isbn-13-string? "978159327491") #f)   ;too short
(check-expect (isbn-13-string? #f) #f)
  
(check-expect (isbn-10-string? "026206218X") #t)
(check-expect (isbn-10-string? "0262062189X") #f) ;too long
(check-expect (isbn-10-string? "026206218") #f)   ;too short
(check-expect (isbn-10-string? #f) #f)
  
(check-expect (isbn-format? 'isbn-13) #t)
(check-expect (isbn-format? 'isbn-10) #t)
(check-expect (isbn-format? "isbn-10") #f)
  
(define (isbn? v)
  (or (isbn-13? v) (isbn-10? v)))

(define (isbn-13? v)
  (and (isbn-13-string? v) (isbn-13-valid? v)))

(define (isbn-10? v)
  (and (isbn-10-string? v) (isbn-10-valid? v)))

(define (isbn-string? v)
  (or (isbn-13-string? v) (isbn-10-string? v)))

(define (isbn-13-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-13-norm v)))

(define (isbn-10-string? v)
  (and (string? v) (regexp-match-exact? re-isbn-10-norm v)))

(define (isbn-format? v)
  (or (equal? v 'isbn-13) (equal? v 'isbn-10)))

; ----------------------------------------------------------
; ISBN Validation

; ISBN-13-String -> Boolean
; is the given isbn-13 string a valid isbn-13

(check-expect (isbn-13-valid? "9781593274917") #t)
(check-expect (isbn-13-valid? "9780201896831") #t)
(check-expect (isbn-13-valid? "9781593274912") #f)
(check-expect (isbn-13-valid? "9780201896834") #f)

(define (isbn-13-valid? isbn-str)
  (isbn-checksumf (isbn-string->numbers isbn-str)
                  '(1 3 1 3 1 3 1 3 1 3 1 3 1)
                  10))

; ISBN-10-String -> Boolean
; is the given isbn-10 string a valid isbn-10

(check-expect (isbn-10-valid? "0262062186") #t)
(check-expect (isbn-10-valid? "026256114X") #t)
(check-expect (isbn-10-valid? "026206218X") #f)
(check-expect (isbn-10-valid? "0262561141") #f)

(define (isbn-10-valid? isbn-str)
  (isbn-checksumf (isbn-string->numbers isbn-str)
                  (range 10 0 -1)
                  11))

; [List-of N] [List-of N] N -> Boolean
; abstract checksum algorithm for isbn validation

(check-expect (isbn-checksumf '(9 7 8 1 5 9 3 2 7 4 9 1 7)
                              '(1 3 1 3 1 3 1 3 1 3 1 3 1)
                              10) #t)
(check-expect (isbn-checksumf '(0 2 6 2 0 6 2 1 8 10)
                              (range 10 0 -1)
                              11) #f)

(define (isbn-checksumf multiplicands multipliers mod)
  (local [(define sum
            (foldl + 0 (map * multiplicands multipliers)))]
    (zero? (modulo sum mod))))

; ISBN-String -> [List-of N]
; translates str into the numbers their isbn letters represent

(check-expect (isbn-string->numbers "026256114X")
              '(0 2 6 2 5 6 1 1 4 10))

(define (isbn-string->numbers str)
  (local [(define (isbn-digit->number d)
            (cond
              [(string=? d "X") 10]
              [else (string->number d)]))]
    (map isbn-digit->number (explode str))))

; ----------------------------------------------------------
; ISBN Extraction

; String -> [List-of ISBN]
; extracts all isbns from str
  
(check-expect (isbn-find/list "") '())
(check-expect (isbn-find/list "none") '())
(check-expect
 (isbn-find/list (file->string "test-isbn-examples"))
 (list
  ;isbn normalized
  "0262062186" "026256114X" "1593274912"
  "9781593274917" "0201896834" "9780201896831"
  ;isbn w/ several id's a sep's
  "0262062186" "026256114X" "0262062186" "0201896834"
  "9780201896831" "026256114X" "9780201896831"))

(define (isbn-find/list str)
  (local [(define candidates
            (foldr append '()
                   (map isbn-match* (string-split str "\n"))))]
    (filter isbn? (map isbn-normalize candidates))))

; String ISBN-Format -> [Maybe ISBN]
; extracts the first isbn of given format from str, if any

(check-expect (isbn-find "" 'isbn-13) #f)
(check-expect (isbn-find "" 'isbn-10) #f)
(check-expect (isbn-find "0262062186" 'isbn-13) #f)
(check-expect (isbn-find "9781593274917" 'isbn-10) #f)
(check-expect (isbn-find (file->string "test-isbn-examples")
                         'isbn-13)
              "9781593274917")
(check-expect (isbn-find (file->string "test-isbn-examples")
                         'isbn-10)
              "0262062186")

(define (isbn-find str format)
  (local [(define p?
            (cond [(symbol=? format 'isbn-13) isbn-13?]
                  [(symbol=? format 'isbn-10) isbn-10?]))
          (define isbns
            (filter p? (isbn-find/list str)))]
    (cond
      [(empty? isbns) #f]
      [else (first isbns)])))
    
; ----------------------------------------------------------
; Helpers

; String -> [List-of String]
; matches substrings in the given string looking like isbn tags

(check-expect (isbn-match* "") '())
(check-expect (isbn-match* "abc\nd") '())
(check-expect
 (isbn-match* (file->string "test-isbn-examples"))
 (list
  ;isbn normalized (all matched)
  "0262062186" "026256114X" "1593274912"
  "9781593274917" "0201896834" "9780201896831"
  ;isbn w/ several id's and sep's (all matched)
  "ISBN 0-262-06218-6"
  "ISBN: 0 262 56114 X"
  "ISBN-10 0 262 06218-6"
  "ISBN-10: 0-201-89683-4"
  "ISBN-13: 978-0-201-89683-1"
  "ISBN-10: 0 262 56114 X"
  "ISBN-13: 978-0201896831"
  ;not isbn strings (usually impossible in real-world)
  "026206218X" "0262561141" "9780201896834" ;partially matched
  ;isbn strings, but isbn invalid (all matched)
  "026206218X" "0262561141" "1593274913"
  "9781593274912" "0201896833" "9780201896834"))

(define (isbn-match* str)
  (regexp-match* re-isbn (string-normalize-spaces str)))

; String -> String
; removes the isbn-id and, then, the isbn separators from str

(check-expect (isbn-normalize "123-45 67") "1234567")
(check-expect (isbn-normalize "ISBN 123") "123")
(check-expect (isbn-normalize "ISBN: 123") "123")
(check-expect (isbn-normalize "ISBN-10 123") "123")
(check-expect (isbn-normalize "ISBN-10: 123") "123")
(check-expect (isbn-normalize "ISBN-13 123") "123")
(check-expect (isbn-normalize "ISBN-13: 123") "123")
(check-expect (isbn-normalize "ISBN-14: hi") "ISBN14:hi")

(define (isbn-normalize str)
  (string-replace
   (string-replace str re-isbn-id "") re-isbn-sep ""))

Next article in the series: Racket: #lang, local definitions

Algunos juegos de entrenamiento auditivo en Scratch

Durante las últimas semanas he estado echándole un vistazo al "lenguaje" de programación Scratch. El objetivo de Scratch es que el principiante en programación (se piensa principalmente en niños) no tenga que vérselas con la sintaxis del lenguaje de turno y disponga de un entorno amigable y visual. Así, en lugar de escribir código, el niño manipula bloques visuales, como piezas de lego, con los que se montan los "códigos" (llamados "bloques" en terminología de Scratch).

No tengo claro si esto realmente puede facilitar el aprendizaje a los más pequeños. En todo caso, Scratch para un programador resulta cuando menos problemático. A veces cosas sencillas de hacer en cualquier lenguaje, en Scratch resultan cosas engorrosas de hacer o enrevesadas. Hay, además, un buen número de limitaciones: no es posible realizar baterías de tests, no hay forma eficaz de construir imágenes mediante código, y un largo etcétera.

Me resulta particularmente irritante que los procedimientos no sean realmente funciones, el hecho de que no puedan devolver valores, y en su lugar haya que modificar variables de estado, que en muchas ocasiones tienen que ser inevitablemente globales. No es una buena forma de aprender principios esenciales de programación.

No obstante, por hablar de alguna cosa buena, siempre desde el punto de vista de un programador, Scratch, a diferencia de App Inventor, otro sistema parecido a Scratch, sí proporciona ciertas opciones de orientación a objetos gracias a la idea de "clonación" (se pueden crear objetos a partir de prototipos) y a través de un sistema de paso de "mensajes" (los objetos pueden pasar y recibir cierta clase elemental de mensajes). Eso sí parece bueno en cuanto a presentar al niño ciertos fundamentos serios de programación.

Pero, sin duda, la mayor ventaja de Scratch es que con él va incluida una plataforma que permite subir a la nube las aplicaciones que se van construyendo y ejecutarlas desde el navegador. Esto libera al programador de buscarse la vida con JavaScript o similares, al menos hasta el momento en que WebAssembly sea lo suficientemente maduro como para cubrir esta imperiosa necesidad independientemente del lenguaje. Eso sí, Scratch desgraciadamente require Flash, una tecnología obsoleta, pero es de esperar que esta situación sea temporal.

Pero basta de introducciones, el objetivo de esta entrada no era hablar de Scratch, sino simplemente informar de que he creado algunos pequeños juegos en Scratch que tal vez sean útiles para los estudiantes de música. No están bien verificados, y están hechos algunos con prisa y todos sin especial atención al atractivo visual, pero ahí van por si a alguien le interesa entrenarse en un contexto más o menos lúdico:

• Entrenamiento en el reconocimiento de intervalos
• Entrenamiento en el reconocimiento de acordes de séptima
• Entrenamiento en el reconocimiento y memorización de secuencias melódicas dentro de la tonalidad
• Entrenamiento en la lectura musical para guitarristas (en inglés)

Algunos comentarios a estas aplicaciones, por orden de importancia.

La segunda aplicación, la del reconocimiento de acordes, es un tanto problemática. La mediocre calidad (midi inevitablemente) de la salida hace el reconocimiento de acordes bastante más difícil de lo que realmente es y debería ser; la ausencia de un sonido real, con todos sus armónicos, aquí es una importante desventaja.

La tercera aplicación sobre memoria dentro de la tonalidad genera secuencias melódicas aleatorias. Aunque dentro de la tonalidad, éstas pueden ser en ocasiones forzadas, y además no hay variación métrica alguna. Esto es artificial, pero un programa con secuencias melódicas más naturales y con métricas variadas es totalmente otro cantar, nada que se pueda hacer en unas horas y con Scratch, requeriría inteligencia artificial, sin duda, y un lenguaje de programación de verdad. En todo caso, tal como está, creo que sigue sirviendo, al menos como puro y duro entrenamiento de la memoria y el reconocimiento auditivo.

Las tres primeras aplicaciones poseen su interfaz en castellano, pero el código está, salvo mínimas excepciones necesarias, en inglés, ya que son meras copias de las versiones inglesas que hice en primer lugar.

The Game of Life implemented in functional style (Racket) and with complex numbers

If you're reading this you probably know what The Game of Life is. If not, visit the Wikipedia for more information:

https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

You may want to just recall the rules governing those aggregates of live cells called polyominos. They are very simple:

• a live cell with more than 3 live neighbors (where neighbors of a cell are those cells adjacent to it in every direction) dies (over-population).

• a live cell with less than 2 live neighbors dies (under-population).

• a dead cell with exactly 3 live neighbors becomes live.

The following diagrams clarify the rules and serve as the preliminary analysis of the problem domain.

And now the code. It is written in a language based on Racket called "Intermediate Student Language with lambda". It can be run on DrRacket (https://download.racket-lang.org/) by setting "Language" to that. ISL+ is a purely functional language that, additionally, allows the use of anonymous functions via lambda expressions. I have also included the Racket module for working with sets (require racket/set). You can, of course, define your own implementation of the set functions applied, instead. They are easy to define. For supporting graphics and interactivity two more modules are required: 2htdp/image and 2htdp/universe.

Regarding the kind of data to represent the domain information I have chosen complex numbers, which are well supported by Racket, to represent a cell. The advantage of using complex numbers instead of, say, a structure of x and y coordinates is mainly performance. A functional implementation without any kind of mutation will be typically slow. At least resorting to a plain data type should improve things in that regard. That choice doesn't compromise readability, though, I think. Besides, the implementation of functions, in particular neighbors, is really neat with such a data type.

On the other hand, I have represented polyominos as sets of cells. Actually lists of cells but treated as immutable sets. That, I hope, produces an elegant and pretty understandable implementation. It also allows an arbitrary number of cells in the grid. I'm aware that clever algorithms could improve efficiency, but I preferred to write first the most natural and readable version.

One last thing, the animation tends to be sluggish after certain point, depending on the clock rate specified and the number of cells involved in that moment. To avoid that annoyance from the very beginning, freezeing the image of the grid is absolutely indispensable.

If you want to change the number of rows and columns of the grid, modify COLS# and ROWS# as you wish.

To play the game, run the program with (main START) from the Interactions Window within DrRacket. Select cells to construct a polyomino by clicking on them on the initial grid. To clear the grid, press 'Escape', to (re)start the animation press 'Enter', to stop the animation, press any key except 'Enter' or 'Escape'.

;; ===============================================
;; CONSTANTS

;; -----------------------------------------------
;; Game rules
(define OVER-POPULATION-THRESHOLD 3)
(define UNDER-POPULATION-THRESHOLD 2)
(define PROCREATION-FACTOR 3)

;; -----------------------------------------------
;; Graphics - Dimensions
; number of rows and columns in the grid
(define ROWS# 81)
(define COLS# 81)

; length of each cell side (in pixels)
(define SIDE 10)

; x and y positions of the middle of, roughly, the grid's center tile
(define CTR-X
  (if (odd? COLS#)
      (quotient (* COLS# SIDE) 2)
      (- (quotient (* COLS# SIDE) 2) (quotient SIDE 2))))

(define CTR-Y
  (if (odd? ROWS#)
      (quotient (* ROWS# SIDE) 2)
      (- (quotient (* ROWS# SIDE) 2) (quotient SIDE 2))))

;; -----------------------------------------------
;; Graphics - Images
(define LIVE-CELL (color-frame "transparent"
                               (square (sub1 SIDE) "solid" "red")))
(define DEAD-CELL (square SIDE "outline" "black"))
(define GRID
  (local [(define col-img
            (foldr above
                   empty-image
                   (build-list ROWS# (lambda (_) DEAD-CELL))))]
    (freeze
     (foldr beside
            empty-image
            (build-list COLS# (lambda (_) col-img))))))

;; ===============================================
;; DATA DEFINITIONS

;; -----------------------------------------------
;; Cell is Complex
;; interp. a cell in a game of life, where its real and imaginary
;;         parts represent, respectively, its positions on the x and
;;         y axis of the complex plane of the game.
;; remark: actual values for those parts are chosen in such a way
;;         that the 0+0i cell in cell patterns is, roughly, at the
;;         center of the pattern, which makes easier to design
;;         drawing functions
(define C0 (make-rectangular 0 0)) ;0+0i

;; -----------------------------------------------
;; Life is (listof Cell)
;; interp. a set of living cells in a game of life
(define I-TROMINO
  (list (make-rectangular 0 1)
        (make-rectangular 0 0)
        (make-rectangular 0 -1)))

(define P-PENTOMINO
  (list (make-rectangular 0 1)
        (make-rectangular 1 1)
        (make-rectangular 0 0)
        (make-rectangular 1 0)
        (make-rectangular 0 -1)))

(define R-PENTOMINO
  (list (make-rectangular 0 1)
        (make-rectangular 1 1)
        (make-rectangular -1 0)
        (make-rectangular 0 0)
        (make-rectangular 0 -1)))

;; -----------------------------------------------
;; Direction is one of:
(define E (make-rectangular 1 0))
(define NE (make-rectangular 1 1))
(define N (make-rectangular 0 1))
(define NW (make-rectangular -1 1))
(define W (make-rectangular -1 0))
(define SW (make-rectangular -1 -1))
(define S (make-rectangular 0 -1))
(define SE (make-rectangular 1 -1))

;; interp. the eight cardinal points

(define DIRECTIONS (list E NE N NW W SW S SE))

;; -----------------------------------------------
(define-struct gol (life running?))
;; GoL is (make-gol Life Boolean)
;; interp. a game of life with its life and a
;;         state, running or stopped
(define STOPPED #f)
(define RUNNING #t)
(define START (make-gol '() STOPPED))

;; ===============================================
;; FUNCTIONS

;; -----------------------------------------------
;; GoL -> GoL
;; start main with (main START)
(define (main gol)
  (big-bang gol
            (on-tick next .5)
            (to-draw render)
            (on-mouse add-cell)
            (on-key handle-key)))

;; -----------------------------------------------
;; GoL -> GoL
;; produce the next gol from the given one
(define (next gol)
  (cond [(gol-running? gol)
         (make-gol (evolve (gol-life gol)) RUNNING)]
        [else gol]))

;; -----------------------------------------------
;; Life -> Life
;; produce the next evolutive step of the given life
(define (evolve l)
  (local [;; Cell -> (listof Cell)
          ;; produce the neighbors of the given cell
          (define (neighbors c)
            (map (lambda (d) (+ c d)) DIRECTIONS))

          ;; Cell -> Natural
          ;; produce the number of the living neighbors of given cell 
          (define (alive-neighbors# c)
            (set-count (set-intersect (neighbors c) l)))

          ;; Cell -> Boolean
          ;; determine whether the given cell is going to survive
          (define (survive? c)
            (<= UNDER-POPULATION-THRESHOLD
                (alive-neighbors# c)
                OVER-POPULATION-THRESHOLD))

          ;; Cell -> Boolean
          ;; determine whether the given cell is going to rise
          (define (rise? c)
            (= (alive-neighbors# c) PROCREATION-FACTOR))

          ;; surviving cells in the given life
          (define surviving
            (filter survive? l))

          ;; surrounding cells around the given life
          (define environ
            (set-subtract (foldr set-union '() (map neighbors l)) l))

          ;; cells going to live in the environment of the given life
          (define rising
            (filter rise? environ))]

    (set-union surviving rising)))

;; -----------------------------------------------
;; GoL -> Image
;; render the given gol life on the grid
(define (render gol)
  (local [;; Cell -> Posn
          ;; produce the position on the grid corresponding
          ;; to the given cell
          (define (cell->pos c)
            (make-posn (+ CTR-X (* (real-part c) SIDE))
                       (- CTR-Y (* (imag-part c) SIDE))))

          ;; Cell Image -> Image
          ;; draw the given the cell onto the given image
          (define (draw-cell c img)
            (local [(define p (cell->pos c))]
              (place-image LIVE-CELL (posn-x p) (posn-y p) img)))]
    
    (foldr draw-cell GRID (gol-life gol))))

;; -----------------------------------------------
;; GoL Integer Integer MouseEvent -> GoL
;; add the cell clicked on to the given gol's life
(define (add-cell gol x y me)
  (local [(define (xy->cell x y)
            (local [(define ctr-delta
                      (make-posn (ceiling (sub1 (/ COLS# 2)))
                                 (ceiling (sub1 (/ ROWS# 2)))))]
              (make-rectangular (- (quotient x SIDE)
                                   (posn-x ctr-delta))
                                (+ (- (quotient y SIDE))
                                   (posn-y ctr-delta)))))]
    (cond [(mouse=? me "button-down")
           (make-gol (cons (xy->cell x y) (gol-life gol))
                     (gol-running? gol))]
          [else gol])))

;; -----------------------------------------------
;; GoL KeyEvent -> GoL
;; handle keys as follows
;; - 'Enter'  - starts the animation
;; - 'Escape' - clear all cells and stops the animation
;; - any other key - stops the animation
(define (handle-key l ke)
  (cond [(key=? ke "\r")
         (make-gol (gol-life l) RUNNING)]
        [(key=? ke "escape")
         (make-gol '() STOPPED)]
        [else
         (make-gol (gol-life l) STOPPED)]))