Sludges: Extensions to Signatures for HtDP Student Languages🔗ℹ

1 Signatures🔗ℹ

A signature denotes a data type (a set of values) and is specified as a signature form, a special syntax that can only used in : signature declarations, inside signature expressions, or in sludges’s define-type definitions.

In a signature form, any name starting with % is a signature variable that stands for any signature data type. Signature variables are not enforced: they accept any value without checking, behaving like Any. Their purpose is documentation only. For example, the following code does not raise any signature violation.

(: same (%T -> %T))

(define (same x) #false)

(check-expect (same 7) #false)

2 Named Type Definitions🔗ℹ

The first form binds name to the signature described by signature-form:

(define-type StringOrFalse (one-of String False))

(: X PossiblyString)

(define X "hello")

The second form defines name as a function that takes signature parameters and returns a new signature:

(define-type (Either A B) (one-of A B))

(: string->number/maybe (String -> (Either Number String)))

define-type can also describe recursive types:

(define-type List<Number> (one-of Empty (ConsOf Number NumberList)))

Available in: all student languages.

(define-type NumberOrBool (one-of Number Boolean))

Available in: all student languages.

3 Typed Struct Definitions🔗ℹ

All field specifications must use the same style: either all typed or all untyped. Square brackets and parentheses are interchangeable.

Typed form. When every field is written as a (field-name sig-form) pair, sludges adds signature checking to all generated procedures:

(define-struct person [(first String) (last String)])

(make-person "Homer" "Simpson")   ; OK

(make-person "Marge" 'Simpson)    ; signature violation: expected a String

This defines:

• make-person as a constructor with signature String String -> Person. Passing a wrong-typed argument reports a signature violation.

• person? as a predicate with signature Any -> Boolean.

• person-first, person-last as selectors with signatures Person -> String.

• Person as a signature matching any valid instance of struct person.

• PersonOf as a parametric signature constructor: (PersonOf Sig1 Sig2) matches person values whose fields satisfy Sig1 and Sig2 respectively.

Untyped form. When each field is a plain identifier, define-struct behaves as the built-in define-struct.

(define-struct Pair [a b])

(make-pair 3 4)       ; OK

(make-pair 3 "four")  ; OK

This defines:

• make-pair as a constructor with signature Any Any -> Pair.

• pair? as a predicate with signature Any -> Boolean.

• pair-a, pair-b as selectors with signatures Pair -> Any.

• Pair as a signature matching any valid instance of struct pair.

• PairOf as a parametric signature constructor: (PairOf Sig1 Sig2) matches pair instances whose fields satisfy Sig1 and Sig2 respectively.

Violations of signatures involving untyped structs are actually detected by the student languages’ regular runtime error checking, not by signature checking. For example, evaluating (pair-first 3) gives the error pair-first: expects a pair, given 3, which is not a signature violation.

Naming convention. The generated signature names use TitleCase with hyphens removed. That is, the struct name is capitalized, hyphens are removed, and the first letter following an hyphen is capitalized. For example, a struct called foo-bar-3baz produces signatures FooBar3Baz and FooBar3BazOf.

Available in: all student languages. In BSL and BSL+, constructors and selectors are first-order. In ASL, fields are mutable.

Available in: all student languages.

4 Predefined Signatures🔗ℹ

(: BACKGROUND Image)

(define BACKGROUND (empty-scene 400 300))

Available in: all student languages.

(: ORIGIN Posn)

(define ORIGIN (make-posn 0 0))

Available in: all student languages.

(: move/x (Integer (PosnOf Integer Integer) -> (PosnOf Integer Integer)))

(define (move/x dx p)

(make-posn (+ dx (posn-x p)) (posn-y p)))

Available in: all student languages.

Available in: all student languages.

Available in: all student languages.

(: STUFF List)

(define STUFF (list 1 "two" #true))

Available in: all student languages.

(: find (String (ListOf String) -> (Maybe Natural)))

Available in: all student languages.

Available in: ASL.

(: GRADES (VectorOf Number))

(define GRADES (vector 7.0 8.5 9.5))

Available in: ASL.

(: reset! (-> Void))

(define (reset!) (set! COUNTER 0))

Available in: ASL.

5 Intervals🔗ℹ

Intervals describe numeric ranges. A < in the name indicates an open (exclusive) endpoint; absence of < means closed (inclusive).

For technical reasons of how signatures are implemented in the student languages, interval signatures are currently only usable within define-type.

(define-type Int-3-5 (integer-from-to 3 5))

(: M Int-3-5)

(define M 4)

(: N (integer-from-to 3 5))

(define N 4)

6 Design Recipe Helpers🔗ℹ

The design of a function fun according to the HtDP design recipe follows an incremental process, which produces successive versions of fun that add details in steps. The three main artifacts are:

1. The header: a stub implementation of fun that does nothing other than returning a default value of the expected type.

2. The template: an incomplete implementation of fun that captures the structure of the input types.

3. The implementation: a complete implementation of fun, obtained by filling in the template’s missing parts and rearranging its elements.

Since all three artifacts are definitions for the same function fun, one has to comment out the header before being able to define the template, and to comment out the template before being able to define the implementation.

The helpers define-header and define-template simply allow one to leave headers and templates in the code without commenting them out, as demonstrated in this example.

(: count (List -> Natural))

; effectively ignored

(define-header (count lst) 0)

; effectively ignored

(define-template (count lst)

(cond

[(empty? lst) ...]

[else (... (first lst) (count (rest lst)) ...)]))

(define-template (count lst)

(cond

[(empty? lst) 0]

[else (+ 1 (count (rest lst)))]))

Available in: all student languages.

Available in: all student languages.

7 Student Language Signatures🔗ℹ

Signature declarations and signature forms are part of the HtDP student languages: see their documentation in BSL, BSL+, ISL, ISL+, and ASL. Their main features are repeated here for reference, since sludges extends them.

8 Configuration🔗ℹ

Module sludges includes two parameters that control how signature violations are reported. They are documented in this section.

Signature violations are logged during execution, and reported at the end together with test outcomes. Since it is common that several violations have the same root cause, sludges does not report all signature violations by default. Instead, it groups them into buckets according to the criterion signature-violation-dedup, and only reports the first max-signature-violations in each bucket.

• 1 (the default): only the first violation per bucket is shown.

• A positive integer n: up to n violations per bucket.

• #f: no limit; all violations are shown. This is the original behavior in the student languages.

• 'signature (the default): one bucket per (signature name, signature object) pair.

• 'type-name: one bucket per signature name. This is the most coarse grouping criterion.

• 'object: one bucket per (signature name, violating object) pair.

Here is an example of how different grouping modes work:

(max-signature-violations 1)

(define-type StringOrFalse (one-of String False))

(: S1 StringOrFalse)

(define S1 1)

(: S2 StringOrFalse)

(define S2 2)

(: S3 StringOrFalse)

(define S3 1)

• If signature-violation-dedup is 'type-name, one signature violation (the first one, involving S1) is reported, because all violations are of the same StringOrFalse.

• If signature-violation-dedup is 'signature, all three signature violations are reported, because each violates a different signature (defined with :).

• If signature-violation-dedup is 'object, two signature violations are reported. The third one (involving S3) is ignored because the value/object that violates S3’s signature is 1, the same as the one that violates S1’s signature.