UNB/ CS/ David Bremner/ tags/ cs3613

This feed contains pages with tag "cs3613".

The final exam, worth 50% of your mark, is tentatively scheduled for 2PM on April 19.

Details about topics will be added to this page closer to the date of the test.

Posted Wed 19 Apr 2017 03:00:00 PM ADT Tags: /tags/cs3613

The second midterm, worth 15% of your mark, will be held in class on March. 14, 2017.

Details about topics will be added to this page closer to the date of the test.

Posted Tue 14 Mar 2017 12:30:00 PM ADT Tags: /tags/cs3613

Background

We have seen several cases where the syntax supported by an interpreter can be modified by using some kind of preprocessor (e.g. converting with* into nested with. This tutorial is on macros, which are a way for the programmer to change the syntax of a language without changing the language interpreter / compiler.

All of the following should be in #lang plai-typed. You can use one source file for the whole tutorial; otherwise you may need to duplicate some definitions which are re-used.

Part 1. Adding FLANG syntax to racket

The first new tool is define-syntax-rule

The key idea here is a pattern. In the example below, the (with (id val) body) s-expression acts something like a type variant in type-case. The with is treated literally, and the other identifiers are bound to whatever s-expression is in that position. This is a bit analogous to a regular define, except notice the extra parens in the with syntax are no problem here.

#lang plai-typed
(define-syntax-rule (with (id val) body)
  (let [(id val)]
    body))

The body of the define-syntax-rule the racket code to replace the with form. Here is one test; add a couple more to convince yourself it is working.

(test (with (x 1) (+ x x)) 2)

Notice there is no quoting of the with in this test; it is now a Racket expression just like let.

Use define-syntax-rule to define syntax for fun and call so that the following tests (borrowed from the lectures) pass

  (test {with {add3 {fun {x} {+ x 3}}}
              {with {add1 {fun {x} {+ x 1}}}
                    {with {x 3}
                          {call add1 {call add3 x}}}}}
        7)

  (test {call {call {fun {x} {call x 1}}
                    {fun {x} {fun {y} {+ x y}}}}
              123}
        124))

Part 2. Short circuit

Some Racket forms like and and or look like function calls, but we know they are not because they support short-circuit evaluation. In this part we use define-syntax-rule to define And and Or, which are just like the lower case version except the short-circuit evaluation is from the right.

(define-syntax-rule (And a b)
  (if b a #f))

(define (die)
  (error 'die "don't run this"))

(test (And (die) #f) #f)
(test/exn (and (die) #f) "don't run this")

Define Or in a similar way to And.

(test (Or (die) #t) #t)
(test/exn (or (die) #t) "don't run this")

Part 3, multiple cases.

The (syntax-rules)[http://docs.racket-lang.org/guide/pattern-macros.html?q=syntax-rules#%28part.define-syntax_and_syntax-rules%29] form can be used test a sequence of patterns against a form starting with one identifier. The following code almost_ works to satisfy the tests. Thinking about cond, what small change do you need to make?

(define-syntax arghh
  (syntax-rules ()
    [(arghh) 0]
    [(arghh a) 1]
    [(arghh (a)) 2]))

(test (arghh) 0)
(test (arghh thptt) 1)
(test (arghh (die)) 2)

Part 4, with*, again.

Recall with* construct from Assignment 4. One of the ways to solve this was to convert with* into a nested set of with forms. It turns out this is fairly easy to do with syntax rules and recursion. A key ingredient is the ability to match sequences with syntax patterns.

Fill out the following syntax-rules in order to expand the with* into a with containing a with* (or if you prefer to skip a macro level, into a let containing a with*.

Note that ... is really valid racket syntax here, and you can place it in your expansion to mean "copy the matched sequence". Roughly speaking, (id val) ... matches a sequence of (id1 val1) (id2 val2) (id3 val3)

(define-syntax with*
  (syntax-rules ()
    [(with* () body) body]
    [(with* ((first-id first-val) (id val) ...) body)
        ]

(test {with* {{x 5} {y {- x 3}}} {+ y y}} 4)
(test {with* {{x 5} {y {- x 3}} {y x}} {* y y}} 25)
Posted Mon 27 Feb 2017 08:30:00 AM AST Tags: /tags/cs3613

Getting started

Open a new file in DrRacket and add the following definitions to the beginning. This makes available some definitions from racket in plai-typed.

#lang plai-typed

(module tutorial6 typed/racket/base
  (require racket/math)
  (require (prefix-in plot: plot))

  (provide plot sin cos pi)

  (define (plot [fn : (Real -> Real) ] [from : Real] [to : Real])
    (plot:plot
     (plot:function fn from to)))
)


(require (typed-in 'tutorial6
                   [plot : ((number -> number) number number -> void)]
                   [pi : number]
                   [sin : (number -> number)]
                   [cos : (number -> number)]))

For the rest of the tutorial, add various definitions discussed to your file. Make a note of the types of the functions discussed.

Derivatives and integrals

We can (crudely) approximate a derivative with the following higher order function.

(define dx 0.001)

;; compute the derivative of `f` at the given point `x`
(define (deriv f x)
  (/ (- (f (+ x dx)) (f x)) dx))

Similarly, we can approximate the integral of a function at a point (more precisely from 0 to the point):

;; compute an integral of `f' at the given point `x'
(define (integrate f x)
  (local
      [(define (loop y acc)
         (if (> y x)
             (* acc dx)
             (loop (+ y dx) (+ acc (f y)))))]
    (loop 0 0)))

And say that we want to try out various functions given some `plot' function that draws graphs of numeric functions, for example:

    (define -2pi (* -2 pi))
    (define 2pi (* 2 pi))
    (plot sin -2pi 2pi)

The problem is that plot expects a single (number -> number) function -- if we want to try it with a derivative, we can do this:

;; the derivative of sin

(define sin-deriv (lambda (x) (deriv sin x)))
(plot sin-deriv -2pi 2pi)

But this will get very tedious very fast -- it is much simpler to use an anonymous function:

(plot (lambda (x) (deriv sin x)) -2pi 2pi)

we can even verify that our derivative is correct by comparing a known function to its derivative. Fill in the blank in the following with the derivative of sin

(plot (lambda (x) (- (deriv sin x)         )) -2pi 2pi)

But it's still not completely natural to do these things -- you need to explicitly combine functions, which is not too convenient. What can you observe about the numerical error here?

Combinators

Instead of explicitely combining , we can write H.O. functions that will work with functional inputs and outputs. Such functions are called 'combinators. For example, we can write a function to subtract functions:

 (define (fsub f g)
    (lambda (x) (- (f x) (g x))))

Notice that the inferred type for fsub is a bit too general. Add type annotations to fix this.

We can similarly mamke a combinator to compute (indefinite) integrals.

 (define (fderiv f)
    (lambda (x) (deriv f x)))

Now we can try the same error calculation in a much easier way:

 (plot (fsub (fderiv sin) cos) -2pi 2pi)

More than that -- our fderiv could be created from deriv automatically:

  ;; convert a double-argument function to a curried one
  (define (currify f)
    (lambda (x) (lambda (y) (f x y))))

  ;; compute the derivative function of `f'
  (define fderiv2 (currify deriv))

Same principle with fsub: we can write a function that converts a binary arithmetical function into a function that operates on unary numeric function. But to make things more readable we can define new types for unary and binary numeric functions:

;; turns an arithmetic binary operator to a function operator
(define (binop->fbinop op)
  (lambda (f g)
    (lambda (x) (op (f x) (g x)))))

Use binop->fbinop to define a new version of fsub (e.g. calling it fsub2).

As a final exercise, define a combinator called "fintegrate" to make the following plot call work:

;; want to verify that `integrate' is the opposite of `deriv':
;;   take a function, subtract it from its derivative's integral

(plot (fsub sin (fintegrate (fderiv2 sin))) 0 2pi)

This is one line if you use currify.

Posted Mon 20 Feb 2017 08:30:00 AM AST Tags: /tags/cs3613

The first midterm, worth 15% of your mark, will be held in class on Feb. 7, 2017.

Details about topics will be added to this page closer to the date of the test.

Posted Tue 07 Feb 2017 11:30:00 AM AST Tags: /tags/cs3613

As practice for the midterm, try to do the following exercises on paper first, then check your answers.

Racket 101

For each of the following expressions, decide what the resulting value (or error) is in plai-typed

(if "true" 0 1)

(first (rest  (list 1 2)))

(cond
 [(> 3 1) 0]
 [(< 3 1)  1])

(and #f (= 0 (/ 1 0)))

(cons 3 (list 1 2))

(let ([ x -1])
  (let ([ x 10]
    [ y (+ x 1) ])
    (+ x y)))

(define (f n)
  (if (<= n 1)
      1
      (f (- n 1))))
(f 100)

(define (g l)
  (lambda (h)
    (cons h l)))

(g 100)
(g (list 1 2 3))
((g (list 1 2 3)) 100)

Higher order functions

Find the type of the functions a, b, and c

(define (a f n)
  (f n))

(define (b f n)
  (lambda (m)
     (f n m)))

(define (c f g h)
  (lambda (x y)
    (f (g x) (h y))))

Tail recursion

  • Write a tail recursive function to multiply two non-negative integers. Your function should use + but not *.

  • Write a tail recursive function to sum the elements of a list.

Grammars

Write a ragg format grammar that (given a suitable lexer) passes the following tests.

(test
 (string->sexpr "wow. such language. very tricky. wow.") 
 '(doge "wow" "." "such" (subject "language") "." "very" (adjective "tricky") "." "wow" "."))

(test
 (string->sexpr "wow. such course. very tricky. wow.") 
 '(doge "wow" "." "such" (subject "course") "." "very" (adjective "tricky") "." "wow" "."))

(test
 (string->sexpr "wow. such course. very difficult. wow.") 
 '(doge "wow" "." "such" (subject "course") "." "very" (adjective "difficult") "." "wow" "."))

(test
 (string->sexpr "wow. such prof. very mean. wow.") 
 '(doge "wow" "." "such" (subject "prof") "." "very" (adjective "mean") "." "wow" "."))

To test your answer you can use doge-lexer.rkt and doge-driver.rkt

Substitution

Consider an extended with syntax such that each with can have multiple bindings, but the named-expression refers to the outer scope, not the the previous bindings. In particular the following evaluates to 3, not 4. This is the same semantics as racket's let, so you can try more examples by replacing "with" with "let" in the code.

{with {{x 1}}
    {with {{x 2} {y x}} {+ x y}}}

Give English/pseudocode rules to perform the following substitution

{with { {x1 e1} ... {x_l e_k} } body}[E/y]=
  subst({with { {x1 e1} ... {x_l e_k} } body},E,y) =
Posted Mon 06 Feb 2017 08:30:00 AM AST Tags: /tags/cs3613

Introduction

In this assignment you will use the ragg parser toolkit to parse transcripts of encounters with dogs. These are represented as strings containing "wag", "growl", "bark", "slobber", and "bite", separated by whitespace. Each encounter is ended with a ’.’; an example input follows:

slobber slobber.
wag wag slobber. growl bark.
growl bark bite.

You should have help on ragg in drracket, under "Help -> Racket Documentation -> Miscellaneous Libraries".

Structure of solutions.

Unlike in your assignments, you will need to use multiple files for this tutorial. You can download the lexer

Write your parser in a second file starting with #lang ragg, and use the two of them from a third driver file like the following. Note that we're using plai, not plai-typed. Also notice you need to use some custom error handling code, rather than test/exn.

#lang plai

(require "grammar-1.rkt")
(require "lexer.rkt")

(define (string->sexpr str)
  (syntax->datum (parse (tokenize-string str))))

(define (catch-parse-error str)
  (with-handlers ([exn:fail? (lambda (v) 'fail)])
    (string->sexpr str)))

(test  
 (string->sexpr "bark bark.")
 '(dog (sentence (angry (before-bite "bark" "bark")) ".")))

(test (catch-parse-error "bite.") 'fail)

1. Happy Dog, Angry Dog

In this question you should construct BNF grammar that enforces the following rules:

  1. Every dog encountered is either happy or angry.
  2. A happy dog always slobbers at least once.
  3. A happy dog may wag several times before slobbering, but once it starts slobbering, it stops wagging.
  4. An angry dog may growl several times before barking, but once it starts barking, it stops growling.
  5. An angry dog does not necessarily bite, but it always growls or barks before biting.

The examples in the introduction are all valid for these rules. Here some examples of invalid encounters.

bite.
bark wag.
growl bark growl.

Here is the beginning of a solution

dog: sentence +

sentence: happy "." | angry "."

Add tests to your driver to test each of the 5 rules given above.

2. To every Slobber a Wag

As an extra challenge, modify your first grammar to enforce the additional rule that the number of wags and slobbers of any happy dog is exactly equal. For this question "wag wag slobber slobber." is valid, but "wag slobber slobber." and "wag wag slobber." are not.

Posted Mon 30 Jan 2017 08:30:00 AM AST Tags: /tags/cs3613

Types

Use pencil and paper to work out the type of the following function. Check your answer using DrRacket.

#lang plai-typed
(define (f a b c)
  (a (b c)))

Tail recursion

Complete the following tail recursive function to count the number of odd and even numbers in a list. You may use the built in functions odd? and even?. Use the racket debugger to test the stack usage of your function.

(define  (helper lst odds evens)
  (cond
    [(empty? lst) (list odds evens)]
        ;; missing two cases
    ))
(define (odds-evens lst)
    (helper lst 0 0))
    
(test (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
Posted Mon 23 Jan 2017 08:30:00 AM AST Tags: /tags/cs3613

Part 1

For each of the following code samples, add sufficient test forms to get full coverage

Sample 1

#lang plai-typed
(define (digit-num n)
  (cond [(<= n 9)    (some 1)]
        [(<= n 99)   (some 2)]
        [(<= n 999)  (some 3)]
        [(<= n 9999) (some 4)]
        [else        (none)]))

Sample 2

#lang plai-typed
(define (helper n acc)
  (if (zero? n)
    acc
    (helper (- n 1) (* acc n))))

(define (fact n)
  (helper n 1))

Sample 3

For the parser example, you'll need to peruse the documentation on expressions to figure out how to test for errors. You may also find the S-expression documentation helpful in constructing test input.

#lang plai-typed
(define-type AE
  [Num (n : number)]
  [Add (l : AE) (r : AE)]
  [Sub (l : AE) (r : AE)])
(define (parse [s : s-expression])
  (cond
     [(s-exp-number? s) (Num (s-exp->number s))]
     [(s-exp-list? s)
      (let* ([sl (s-exp->list s)]
             [op (s-exp->symbol (first sl))]
             [left (second sl)]
             [right (third sl)])
        (case op
          [(+) (Add (parse left) (parse right))]
          [(-) (Sub (parse left) (parse right))]))]
     [else (error 'parse-sexpr "bad syntax")]))

Part 2

Sample 3 has several bugs, namely syntax errors that crash the parser, rather than generate error messages about the input. Correct at least one of these bugs, and add a suitable test.

Posted Mon 16 Jan 2017 08:30:00 AM AST Tags: /tags/cs3613

Part 1

Follow the instructions at racket-setup to get racket set up for this course. If the system version of drracket is not available (e.g. in the menus) yet, then you can start drracket by opening a terminal and running

  % ~bremner/bin/drracket

Part 2

Do the Quick racket tutorial. Although you can just copy and paste the text into DrRacket, you will get more benefit from typing things in and more importantly from changing things and observing the results.

Posted Mon 09 Jan 2017 08:30:00 AM AST Tags: /tags/cs3613