Difference between revisions of "Thunks and Streams Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(51 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
=Motivation=
 +
It is all too easy to make a simple mistake on the [[Streams_Assignment|Streams Lab]] and have it burn way to much of ones time.  We will build some utility functions that will hopefully make our code more clear, as well as raise better errors sooner, alerting us if we make a mistake.
 +
 
=Code To Use=
 
=Code To Use=
−
[https://docs.racket-lang.org/reference/define.html#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._define-syntax%29%29 define-syntax]
+
* [https://docs.racket-lang.org/reference/booleans.html #t] true
 +
* [https://docs.racket-lang.org/reference/booleans.html #f] false
 +
* [https://docs.racket-lang.org/reference/define.html#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._define-syntax%29%29 define-syntax]
 +
* [https://docs.racket-lang.org/reference/lambda.html?q=lambda#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._lambda%29%29 lambda]
 +
* [https://docs.racket-lang.org/reference/procedures.html#%28def._%28%28quote._~23~25kernel%29._procedure~3f%29%29 procedure?]
 +
* [https://docs.racket-lang.org/reference/procedures.html?q=procedure-arity#%28def._%28%28quote._~23~25kernel%29._procedure-arity%29%29 procedure-arity] number of arguments a function takes [https://en.wikipedia.org/wiki/Arity Arity on Wikipedia]
 +
* [https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._pair~3f%29%29 pair?]
 +
* [https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons]
 +
* [https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._car%29%29 car]
 +
* [https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._cdr%29%29 cdr]
 +
* [https://docs.racket-lang.org/reference/values.html#%28def._%28%28quote._~23~25kernel%29._values%29%29 values]
 +
* [https://docs.racket-lang.org/reference/exns.html?q=raise#%28def._%28%28quote._~23~25kernel%29._raise-argument-error%29%29 raise-argument-error]
 +
* [https://docs.racket-lang.org/reference/exns.html?q=raise#%28def._%28%28quote._~23~25kernel%29._raise-result-error%29%29 raise-result-error]
  
−
[https://docs.racket-lang.org/reference/lambda.html?q=lambda#%28form._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._lambda%29%29 lambda]
+
=Code To Implement=
 +
{{RacketToImplement|uw4|thunk?<br>thunk-that<br>dethunk-that<br>value-next-stream-pair-from-stream<br>stream-cons-ensuring-stream-prime-is-thunk|uw4}}
 +
==Thunk Utilities==
 +
A [https://en.wikipedia.org/wiki/Thunk thunk] is a 0 argument function. We will write functions to check if an expression is a thunk, a '''MACRO''' to create a thunk from an expression, and a function to evaluate a thunk.
  
−
[https://docs.racket-lang.org/reference/procedures.html#%28def._%28%28quote._~23~25kernel%29._procedure~3f%29%29 procedure?]
+
===thunk?===
 +
define a function <code>thunk?</code> which returns whether the specified parameter is a thunk or not.
  
−
[https://docs.racket-lang.org/reference/procedures.html?q=procedure-arity#%28def._%28%28quote._~23~25kernel%29._procedure-arity%29%29 procedure-arity]
+
<nowiki>(define (thunk? th)
 +
    (error 'not-yet-implemented))</nowiki>
  
−
[https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._pair~3f%29%29 pair?]
+
===thunk-that===
 +
define a '''MACRO''' <code>thunk-that</code> which takes a parameter <code>e</code> creates thunk. that is: wraps <code>e</code> in a zero argument function.
  
−
[https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons]
+
(define-syntax-rule (thunk-that e)
 +
    (error 'not-yet-implemented))
  
−
[https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._car%29%29 car]
+
Thunks are useful for delaying the evaluation of expressions.  As such <code>thunk-that</code> must be declared as a macro and not a function.  Unlike [https://www.haskell.org/ Haskell] which has lazy evaluation, Racket (and most other languages) [https://en.wikipedia.org/wiki/Eager_evaluation eagerly evaluates] function arguments.
  
−
[https://docs.racket-lang.org/reference/pairs.html?q=cons#%28def._%28%28quote._~23~25kernel%29._cdr%29%29 cdr]
+
===dethunk-that===
 +
define a function <code>dethunk</code> which takes a thunk parameter <code>e</code> and returns the result of invoking <code>e</code>.
  
−
=Code To Implement=
+
(define (dethunk-that thunk)
−
{{RacketToImplement|hw4|thunk?<br>thunk-that<br>dethunk-that<br>...|hw4}}
+
    (error 'not-yet-implemented))
−
==Thunk Utilities==
+
 
−
===thunk?===
+
If thunking and expression wraps an expression in a single argument function, then de-thunking is simply calling that function.
−
define a function <code>thunk?</code> which returns #t if the specified parameter is a thunk, #f otherwise.
 
  
−
===thunk MACRO===
+
If the parameter <code>thunk</code> is not a <code>thunk?</code> then <code>dethunk-that</code> should [https://docs.racket-lang.org/reference/exns.html#%28def._%28%28quote._~23~25kernel%29._raise-argument-error%29%29 raise an argument error].
−
define a macro <code>thunk</code> which creates thunk
 
  
−
===dethunk===
+
NOTE: It may seem unnecessary to use <code>dethunk-that</code> when implementing Lab4, when you could simply (thunk)... that is "call the thunk".  Still, you are encouraged to use <code>dethunk-that</code> as a bit of verbosity can sometimes help in debugging a sea already full of parentheses.
−
define a function <code>dethunk</code> which takes a thunk parameter <code>th</code> and returns the result of invoking <code>th</code>.
 
  
 
==Stream Utilities==
 
==Stream Utilities==
 +
===destream===
 +
define a function <code>destream</code> which takes a <code>stream</code> parameter and evaluates to the resulting dethunked pair.
 +
 +
(define (destream stream)
 +
    (error 'not-yet-implemented))
 +
 +
A critical value of this utility function is to provide early error detection.  As such, exceptions should be raised if either
 +
 +
* the parameter <code>stream</code> is not a thunk (this can be handled by <code>dethunk-that</code>)
 +
* the result of de-thunking the <code>stream</code> is not a pair
 +
* next-stream of the pair is not thunk
 +
<!--
 +
Example use of  [https://docs.racket-lang.org/reference/values.html#%28def._%28%28quote._~23~25kernel%29._values%29%29 values] and [https://docs.racket-lang.org/reference/define.html?q=define-values#%28form._%28%28quote._~23~25kernel%29._define-values%29%29 define-values]:
 +
 +
<youtube>iWCcL049dOg</youtube>
 +
 +
<nowiki>(define (div-mod-values n d)
 +
  (values (quotient n d) (modulo n d)))
  
−
===plausible-stream?===
+
(define (printf-div-mod-values n d)
−
define a function <code>plausible-stream?</code> which returns #t if the specified parameter is a thunk which when invoked returns a pair whose cdr is a thunk, #f otherwise.
+
  (local [(define-values (q r) (div-mod-values n d))]
 +
    (printf "~a/~a => ~a w/ remainder ~a\n" n d q r)))
  
−
WARNING: what could happen if you called <code>plausible-stream?</code> recursively on the <code>cdr</code>?
+
(printf-div-mod-values 425 231)</nowiki>
  
−
===next-value-from-stream===
+
produces the output:
−
define a function <code>next-value-from-stream</code> which takes a stream parameter and returns the next value of that stream.
 
  
−
===next-stream-from-stream===
+
<nowiki>425/231 => 1 w/ remainder 194</nowiki>
−
define a function <code>next-stream-from-stream</code> which takes a stream parameter and returns the next stream of that stream.
+
-->
  
−
===stream-next===
+
===stream-cons-ensuring-stream-prime-is-thunk===
−
BONUS method not officially part of the studio but a good idea.
+
Define a function <code>cons-with-thunk-check-on-next-stream</code> which takes two parameters <code>value</code> and <code>next-stream</code>.
  
−
define a function <code>stream-next</code> which takes a stream parameter and returns a pair of values for the next value and the next stream.
+
((define (cons-with-thunk-check-on-next-stream element next-stream)
 +
  (error 'not-yet-implemented))
  
−
===stream-cons===
+
If the specified <code>next-stream</code> parameter is not a thunk then an error should be raised:
−
define a function <code>stream-cons</code> which takes two parameters <code>value</code> and <code>stream-prime</code>.  if the specified <code>stream-prime</code> parameter is not a thunk then an error should be raised:
 
  
−
  <code>(raise (error "not a thunk" stream-prime))</code>
+
  <code>(raise-argument-error "next-stream" "thunk?" next-stream)</code>
  
−
If <code>stream-prime</code> is a thunk it should simply [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons] <code>value</code> and <code>stream-prime</code>.  Do '''NOT''' create a thunk.
+
Do '''NOT''' create a thunk.  If <code>next-stream</code> is a thunk it should simply [https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cons%29%29 cons] <code>value</code> and <code>next-stream</code>.
  
−
WARNING: what could happen if you called <code>plausible-stream?</code> on <code>stream-prime</code>?
+
=Test=
 +
==thunk==
 +
{{RacketUnitTest|thunk_test|uw4}}
  
−
==Stream App==
+
==stream==
−
===flip-flop-stream===
+
{{RacketUnitTest|stream_test|uw4}}
−
define <code>flip-flop-stream</code> which produces #t #f #t #f #t #f #t #f...
 

Latest revision as of 18:35, 24 October 2024

Motivation

It is all too easy to make a simple mistake on the Streams Lab and have it burn way to much of ones time. We will build some utility functions that will hopefully make our code more clear, as well as raise better errors sooner, alerting us if we make a mistake.

Code To Use

Code To Implement

file: src/main/racket/uw4/uw4.rkt Racket-logo.svg
functions: thunk?
thunk-that
dethunk-that
value-next-stream-pair-from-stream
stream-cons-ensuring-stream-prime-is-thunk

Thunk Utilities

A thunk is a 0 argument function. We will write functions to check if an expression is a thunk, a MACRO to create a thunk from an expression, and a function to evaluate a thunk.

thunk?

define a function thunk? which returns whether the specified parameter is a thunk or not. 

(define (thunk? th)
    (error 'not-yet-implemented))

thunk-that

define a MACRO thunk-that which takes a parameter e creates thunk. that is: wraps e in a zero argument function. 

(define-syntax-rule (thunk-that e)
   (error 'not-yet-implemented))

Thunks are useful for delaying the evaluation of expressions. As such thunk-that must be declared as a macro and not a function. Unlike Haskell which has lazy evaluation, Racket (and most other languages) eagerly evaluates function arguments.

dethunk-that

define a function dethunk which takes a thunk parameter e and returns the result of invoking e. 

(define (dethunk-that thunk)
   (error 'not-yet-implemented))

If thunking and expression wraps an expression in a single argument function, then de-thunking is simply calling that function.

If the parameter thunk is not a thunk? then dethunk-that should raise an argument error.

NOTE: It may seem unnecessary to use dethunk-that when implementing Lab4, when you could simply (thunk)... that is "call the thunk". Still, you are encouraged to use dethunk-that as a bit of verbosity can sometimes help in debugging a sea already full of parentheses.

Stream Utilities

destream

define a function destream which takes a stream parameter and evaluates to the resulting dethunked pair. 

(define (destream stream)
   (error 'not-yet-implemented))

A critical value of this utility function is to provide early error detection. As such, exceptions should be raised if either

  • the parameter stream is not a thunk (this can be handled by dethunk-that)
  • the result of de-thunking the stream is not a pair
  • next-stream of the pair is not thunk

stream-cons-ensuring-stream-prime-is-thunk

Define a function cons-with-thunk-check-on-next-stream which takes two parameters value and next-stream. 

((define (cons-with-thunk-check-on-next-stream element next-stream)
  (error 'not-yet-implemented))

If the specified next-stream parameter is not a thunk then an error should be raised: 

(raise-argument-error "next-stream" "thunk?" next-stream)

Do NOT create a thunk. If next-stream is a thunk it should simply cons value and next-stream.

Test

thunk

file: thunk_test.rkt Racket-logo.svg Test
source folder: src/test/racket/uw4

note: ensure that you have removed all printing to receive credit for any assignment.

stream

file: stream_test.rkt Racket-logo.svg Test
source folder: src/test/racket/uw4

note: ensure that you have removed all printing to receive credit for any assignment.

Retrieved from "http://classes.engineering.wustl.edu/cse425s/index.php?title=Thunks_and_Streams_Assignment&oldid=2350"