Question

Consider the following puzzle. It is in the vein of Russell and Norvigs toy problem on page 73, that they attribute to Donald Knuth.

You are given a pair of numbers: the first is the seed, x₀, and the second the target x_f. You are provided, additionally, with two functions f : RR and g : RR.

Puzzle: Write a program to give either the minimal number of function applications (of f and g) needed to reach x_f from x₀, or state that one cannot reach x_f from x₀.

Approach

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 youve never heard

of it.)

Task1

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 Haskells 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 isnt available for us. The other functionality is supported, however.)

Task2

Reflect on these things:

• Consider Knuths 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