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 be 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 StringOrFalse)

(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-of-Number (one-of EmptyList (ConsOf Number List-of-Number)))

Available in: all student languages.

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

Available in: all student languages.

A type constructor describes the values that some function builds. (ConsOf Number EmptyList), for instance, describes the values (cons n '()) with n a number. Checking a value against such a type never calls the function: it takes the value apart instead. So a type constructor is defined by recognizer, which recognizes the values the function builds, together with one selector per parameter, which recovers the corresponding component. A value belongs to (name S1 ... Sn) exactly when recognizer accepts it and each selector maps it into the corresponding S.

(define-type-constructor (Cons* first-sig rest-sig) cons? (first rest))

(define-type NumList (one-of EmptyList (Cons* Number NumList)))

(: sum-nums (NumList -> Number))

(define (sum-nums xs)

(cond

[(empty? xs) 0]

[else (+ (first xs) (sum-nums (rest xs)))]))

There must be exactly one selector per parameter. recognizer and the selectors are names of functions, which may be ordinary first-order functions even in BSL and BSL+.

A correct type constructor definition has two requirements:

1. recognizer must accept exactly the values the selectors can take apart.

2. In a recursive type, recognizer must make the selectors strictly decreasing, so that the recursion terminates upon reaching a base case.

Since an unconstrained lift of add1 would break the second requirement, Add1 restricts its recognizer to positive exact integers.

Checking a lifted type is eager: a violation is reported when the signature is applied, rather than when a selector is later called.

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.

A function lifted to a type constructor keeps its name, capitalized, as add1 becomes Add1. Cons is that name for cons, and unlike Add1 it is a faithful lift: it describes every value cons builds.

(define-type NumList (one-of EmptyList (Cons Number NumList)))

Cons and ConsOf are the same function, and the two spellings may be used interchangeably, including within one definition.

Available in: all student languages.

With Add1, the natural numbers can be described as a recursive type:

(define-type Natural (one-of (enum 0) (Add1 Natural)))

Add1 is add1 with its domain restricted to the nonnegative exact integers: the recognizer accepts a value above zero, so the predecessor handed to sig is nonnegative, and the values Add1 describes are the positive exact integers.

Add1 is not a faithful lift of add1 the way Cons is of cons: add1 also accepts -5 and 1.5. The restriction is necessary because (Add1 T) checks its predecessor against T, and this recursive check needs a base case to terminate.

Add1 still works for any recursive definition with a base case at or above zero, such as (one-of (enum 1) (Add1 Pos)) and the nested (one-of (enum 0) (Add1 (Add1 Even))). A negative base case does not: (one-of (enum -5) (Add1 T)) accepts only -5, and rejects -4, -1, 0 and 3. For a range like that, use integer-from or integer-from-to, or build a constructor with the floor you need using define-type-constructor.

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.