[SOLVED] Csce625: programming assignment 1 : search, bfs, and lazy evaluation

Consider the following puzzle. It is in the vein of Russell and Norvig’s toy problem on
page 73, that they attribute to Donald Knuth.You are given a pair of numbers: the first is the seed, x0, and the second the target xf .
You are provided, additionally, with two functions f : R → R and g : R → R.
Puzzle: Write a program to give either the minimal number of function applications
(of f and g) needed to reach xf from x0, or state that one cannot reach xf from x0.This problem is from https://nmattia.com/posts/2016-07-31-bfs-tree.html
In that blog post Nicolas Mattia considers the two functions f and g defined as follows:
f(x) = 2x + 1 and g(x) = 3x + 1.
The author provides code to solve exactly this problem on that page. Actually, that
page is code, written in Haskell. (Look up literate programming if you’ve never heard
of it.)Convert his solution, for those two particular f and g functions, to Scheme. His approach is not quite the same as the straightforward stack-based method given in Russell
and Norvig. Instead, it uses Haskell’s lazy evaluation to provide a sort of infinite data
structure. You are to do the same thing: implement the search using lazy evaluation.
1
We have Gambit Scheme installed on the compute.cs.tamu.edu server. The
page at http://www.iro.umontreal.ca/˜gambit/doc/gambit.html provides some
information that you might find useful in getting up and running with the interpreter
and compiler.By default Scheme uses eager evaluation. You have to make use of the delay
and force keywords. Details on this can be found here: http://www.shido.info/
lisp/scheme_lazy_e.html
(Note that the text in that guide uses Guile, not Gambit Scheme, so the promise?
type checking function isn’t available for us. The other functionality is supported,
however.)Reflect on these things:
• Consider Knuth’s original problem. That requires more than just an f and g. Can
you pose his problem with a modification of your code?
• What properties are needed to ensure that your program is guaranteed to give a
solution to the puzzle?
2