Functional Problem Solving (CSC 151 2014F) : Outlines
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Held: Tuesday, 28 October 2014
Back to Outline 30 - Preconditions, Revisited. On to Outline 32 - Characters and Strings.
Summary
We explore why and how one writes local recursive procedures.
Related Pages
Overview
letrec
.Administrivia
let
and let*
.let
nor let*
works for recursive procedures.letrec
.let
called "named let".letrec
letrec
expression has the format(letrec ([*name1* *exp1*] [*name2* *exp2*] ... [*namen* *expn*]) *body*)
letrec
is evaluated using the following series
of steps.
*name<sub>1</sub>*
through
*name<sub>n</sub>*
into the binding table.
(Note that no corresponding values are entered.)*exp<sub>1</sub>*
through
*exp<sub>n</sub>*
, giving you results
*result<sub>1</sub>*
through
*result<sub>n</sub>*
.*name<sub>i</sub>*
and
*result<sub>i</sub>*
for each
reasonable i.let
, except
that the order of entry into the binding table is changed.let
let
is somewhat stranger, but is handy for
some problems.let
has the format(let *name* ((*param1* *exp1*) (*param2* *exp2*) ... (*paramn* *expn*)) *body*)
*param<sub>1</sub>*
...
*param<sub>n</sub>*
and body *body*
.*name*
.*exp<sub>1</sub>*
through
*exp<sub>n</sub>*
.(letrec ((*name* (lambda (*param1* ... *paramn *) *body*))) (*name* *val1* ... *valn*))
reverse
.(define reverse (lambda (lst) (reverse-kernel lst null))) (define reverse-kernel (lambda (remaining so-far) (if (null? remaining) so-far (reverse-kernel (cdr remaining) (cons (car remaining) so-far)))))
The principle of encapsulation suggests that we should make
reverse-kernel
a local procedure.
(define reverse (letrec [(kernel (lambda (remaining so-far) (if (null? remaining) so-far (kernel (cdr remaining) (cons (car remaining) so-far)))))] (lambda (lst) (kernel lst null))))
The pattern of "create a kernel and call it" is so common that the named let exists simply as a way to write that more concisely.
(define reverse (lambda (lst) (let kernel [(remaining lst) (so-far null)] (if (null? remaining) so-far (kernel (cdr remaining) (cons (car remaining) so-far))))))