Monthly Archives: January 2014

Geiser and Scsh are Talking

../img/fractal-cheetah.jpg

In this post I’d like to announce an early version of scsh 1 support for Geiser 2. There’s plenty left to do, but enough of Geiser is working that you can write scsh with real completions provided by scsh itself! What’s more, if you want to you can hack on the Geiser support from the inside. :-}

Working features include:

  • Symbol and module completion
  • Module imports (mostly)
  • view macroexpansions in buffer
  • Talking to Geiser over its async protocol (the foundation of everything else)

Some features aren’t there yet:

  • Jumping to procedure definition in source
  • Show callers/callees of a procedure
  • Jumping to module source
  • Jumping to documentation for the thing at point (I’ve only gotten this to work sporadically for some reason)

Getting the Code

You can get the code here:

https://github.com/rmloveland/geiser-scsh

See the README and TODO.org files in the repo for more detailed information about project goals and what works and what doesn’t. Feel free to open issues on Github for any broken things (there are plenty).

You can also get a copy of the scsh manual in Texinfo here – please let me know if you can get the Geiser doc commands working with it, so far I haven’t had much success:

https://github.com/rmloveland/scsh-manual-texinfo

Getting Started

There are a few setup quirks:

  • First, set Emacs’ geiser-scheme-dir variable to wherever you’re working from; here’s what I do:
    (setq geiser-scheme-dir (expand-file-name "~/Code/geiser-scsh/scheme/"))  
    
  • Second, go ahead and load up geiser-scsh.el from the git repo.
  • Next, hop into Customize via M-x customize-group ENTER geiser ENTER, and set the following:
    Custom Variable Value Note
    Geiser Repl Skip Version Check P on You must set this, or else Emacs throws you into the debugger. This is a bug I need to fix.
    Geiser Active Implementations scsh
    Geiser Default Implementation scsh I do this since I’m mostly working in scsh, but it shouldn’t be necessary.

    (Note that you’ll need to set geiser-scheme-dir back to its original value if you want to go back to using Guile or Racket.)

At this point, you should be able to do M-x run-scsh and enjoy your scsh hacking with nice completions and whatnot. If you’re going to hack on the Geiser support, do a C-u M-x geiser-show-logs; a buffer will open where you can listen to scsh and Emacs talking. And of course, the source is your friend. :-}

(Image courtesy RayMorris1 under CC-BY-NC-ND license.)

SICP Exercises 1.1 through 1.4

../img/necker-cube.png

Some time ago, I got a copy of the first edition of SICP on eBay. It’s a fascinating book, for many reasons. I’ve been slowly working through it in fits and starts, but I’ve decided that this year I’m going to really focus on finishing this book and doing all of the exercises.

Therefore, for the sake of completeness, I’d like to backtrack a bit and record my work on SICP exercises 1.1 through 1.4. My goal is to be able to do every single exercise from SICP (1st ed.) and explain it here. (You can see all of the SICP-related posts here.)

For each of the exercises below, I’ll first provide the problem text from the book, and then my answer (or attempt at an answer).

Exercise 1.1

Below is a sequence of expressions. What is the result printed by
the interpreter in response to each expression? Assume that the
sequence is to be evaluated in the order in which it is presented.

Here are the expressions, followed by my answers.

Expression Result
10 10
(+ 5 3 4) 12
(- 9 1) 8
(/ 6 2) 3
(+ (* 2 4) (- 4 6)) 6
(define a 3) UNDEFINED
(define b (+ a 1)) 4
(+ a b (* a b)) 19
(= a b) #f
(if (and (> b a) (< b (* a b))) b a) 4
(cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) 16

Exercise 1.2

Define a procedure that takes three numbers as arguments and
returns the sum of the squares of the two larger numbers.

Here is the procedure definition, along with a couple of helpers.

(define (square x)
  (* x x))

(define (sos x y)
  (+ (square x) (square y)))

(define (sos-largest-two a b c)
  (let* ((sorted (sort (list a b c) >))
         (large (first sorted))
         (medium (second sorted)))
    (sos medium large)))

Exercise 1.3

Ben Bitdiddle has invented a test to determine whether the
interpreter he is faced with is using applicative-order evaluation
or normal-order evaluation. He defines the following two
procedures:

(define (p) (p))

(define (test x y)
  (if (= x 0)
      0
      y))

Then he evaluates the expression

(test 0 (p))   

What behavior will Ben observe with an interpreter that uses
applicative-order evaluation? What behavior will he observe with an
interpreter that uses normal-order evaluation? Explain your answer.
(Assume that the evaluation rule for the special form IF is the
same whether the interpreter is using normal or applicative order:
The predicate expression is evaluated first, and the result
determines whether to evaluate the consequent or the alternative
expression.)

An interpreter that uses applicative-order evaluation will enter an infinite recursion.

An interpreter that uses normal-order evaluation will return 0.

The reason for this is that an applicative-order interpreter follows the usual “evaluate arguments, then apply” recipe. I believe this is also known as “call-by-value”.

The normal-order interpreter never gets around to evaluating the second argument to test because it doesn’t need to (and of course, once inside test, the if form behaves as in the problem description).

Exercise 1.4

Alyssa P. Hacker doesn’t see why if needs to be provided as a
special form. “Why can’t I just define it as an ordinary
procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu
Ator claims this can indeed be done, and she defines a new version
of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

==> (new-if (= 2 3) 0 5)
5

==> (new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

What happens when Alyssa attempts to use this to compute square
roots? Explain.

Running this procedure exceeded MIT Scheme’s maximum recursion depth. I decided to trace the procedure to better see what was happening (note that I renamed the procedures to alyssa-sqrt-iter and alyssa/sqrt to differentiate them from the original versions).

(trace alyssa-sqrt-iter)
;Unspecified return value

(alyssa/sqrt 100)
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 1.
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 50.5
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 26.24009900990099
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 15.025530119986813
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.840434673026925
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.032578510960604
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.000052895642693
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.000000000139897
;;           100]
;; [Entering #[compound-procedure 12 alyssa-sqrt-iter]
;;     Args: 10.
;;           100]
;;  ... et cetera ...

;Quit!

The last line, where the arguments to alyssa/sqrt-iter are 10 and 100, repeats hundreds of times. Even though the call to good-enough? (shown again below) returns #t, new-if still ends up evaluating the `else-clause’ and causing the linear recursion instead of returning the current value of guess (as it should).

(new-if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x))

This problem illustrates the reason we need if to be a special form: we need it to exhibit “short-circuiting” behavior, i.e., we need it to avoid evaluating all of its arguments.