'(scheme . info)

Hugh Williams invented the p+1 integer factorization method in 1982 based on John Pollard’s p-1 integer factorization method; the p+1 method finds a factor p when p is smooth with respect to a bound B. We noted in a previous exercise the similar structure of Pollard’s p-1 method and Lenstra’s elliptic curve method, and Williams’ p+1 method shares the same two-stage structure; Pollard’s p-1 method performs multiplications modulo p, Lenstra’s elliptic curve method performs multiplications over an elliptic curve, and Williams’ p+1 method performs multiplications over a quadratic field using Lucas sequences (similar to the Lucas chain in the Baillie-Wagstaff primality-testing exercise). A good description of Williams’ p+1 method is given at http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method.

Williams’ p+1 method uses the Lucas sequence V0 = 2, V1 = A, Vj = A · Vj−1 − Vj−2, with all operations modulo N, where A is an integer greater than 2. Multiplication by successive prime powers is done as in Pollard’s p-1 algorithm; when all the products to the bound B are accumulated, the greatest common divisor of N and the result VB − 2 may be a divisor of N if all the factors of p+1 are less than B. However, if A2 − 4 is a quadratic non-residue of p, the calculation will fail, so several attempts must be made with different values of A before concluding that p+1 is not B-smooth.

Given the addition formula Vm+n = Vm Vn − Vm−n and the doubling formula V2m = Vm × Vm − 2, multiplication is done by means of a Lucas sequence that computes two values at a time. Starting with the pair Vkn and V(k+1)n, and looking at the bits in the binary representation of the multiplier M, excluding the most significant bit (which is always 1) and working from most significant to least significant, calculate the pair V2kn, V(2k+1)n when the bit is zero and the pair V(2k+1)n, V2(k+1)n when the bit is one.

The second stage finds factors that are B1-smooth except for a single prime factor in the range B1 to B2. It can be done in a similar manner to the second stage of Pollard’s p-1 method, but a little bit of algebra gives us a better second stage. Assuming that Vn is the point that survives the first stage, multiply the products Vk − Vn for each k divisible by 6 between B1 and B2, then take the greatest common divisor of the product with n to reveal the factor.

Your task is to write a program that factors integers using Williams’ p+1 algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

This exercise appeared on Proggit a while ago. The task is to enumerate the elements of a matrix in spiral order. For instance, consider the matrix:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16
17 18 19 20

The spiral starts across the first row, yielding 1, 2, 3, and 4. Then the spiral turns right and runs down the right column, yielding 8, 12, 16, and 20. The spiral turns right again and runs across the bottom row, from right to left, yielding 19, 18, and 17. Then up the first column with 13, 9, 5, right with 6 and 7, down with 11 and 15, right to 14, and up to 10. Thus, unwrapping the given matrix in a spiral gives the list of elements 1, 2, 3, 4, 8, 12, 16, 20, 19, 18, 17, 13, 9, 5, 6, 7, 11, 15, 14, and 10.

Your task is to write a function to unwrap spirals. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here is an old but good presentation about Janestreet, with a discussion of why OCaml fits in the company.

When asked how they deal with the inevitable difficulty in hiring OCaml programmers, Yaron replied something to the effect that:

If you don’t hire bad programmers, many things become easier.

The OP asked how to set the background color in Slideshow as it is not obvious.

Matthew replied:

Locally, I’d superimpose a picture onto a color rectangle:

#lang slideshow 
 
 (define (add-bg p color) 
   (refocus (cc-superimpose 
             (colorize 
              (filled-rectangle (pict-width p) 
                                (pict-height p)) 
              color) 
             p) 
            p)) 
 
 (add-bg (bt "Hello") "green")

To globally set the background, I’d use that in an assembler:

#lang slideshow 
 
 (define (add-bg p color) 
   (refocus (cc-superimpose 
             (colorize 
              (filled-rectangle (pict-width p) 
                                (pict-height p)) 
              color) 
             p) 
            p)) 
 
 (current-slide-assembler 
  (let ([orig (current-slide-assembler)]) 
    (lambda (title sep body) 
      (ct-superimpose 
       (inset (add-bg (inset full-page margin) "green") 
              (- margin)) 
       (orig title sep body))))) 
 
 (slide #:title "Example" (bt "Hello"))

(via plt)

The OP asked:

Is there a way to evaluate something in a given evaluator without having anything displayed in the output?
Ie. I want to feed a couple of basic function definitions into the evaluator instance that I obtain with (make-base-eval).

Matthew shared the solution: interaction-eval.

(via plt)

The scribble/eval library provides utilities for evaluating code at document-build time and incorporating the results in the document, especially to show example uses of defined procedures and syntax.

Here is an example where the OP was:

trying to figure out a way to insert some text in between Scheme definitions: that is, have some definitions (@schemeblock or equivalent), with their explanations (text mode), and then an interaction, like @interaction, except that it should be aware of the preceeding definitions.

Here is the solution:

#lang scribble/manual 
@(require scribble/eval) 
 
@(define ex-eval (make-base-eval)) 
 
First, we define @scheme[x]: 
 
@interaction[ 
#:eval ex-eval 
(define x 1) 
] 
 
Next, we use it: 
 
@interaction[ 
#:eval ex-eval 
x 
] 
 
@(close-eval ex-eval)

(via plt)

You can use ‘code:hilite’ to highlight expressions in Scribble generated documentation like this:

@schemeblock[ 
  (+ 1 (code:hilite +inf.0)) 
 ]

It doesn’t work for multi-line expressions yet, however.

(via plt)

A frequent question on the PLT Scheme discussion list is how to implement new languages on top of PLT Scheme.

In the next release documentation explaining how to do so is included, and there is a preview here.

(via plt)

Here is it; thanks to Jay.

(via plt)

Here is how to get the current line number programmatically in PLT Scheme (via Jay):

#lang scheme 
(define-syntax (current-line-number stx) 
  (quasisyntax/loc stx 
    '#,(syntax-line stx))) 
 
(printf "~a: ~a~n" (current-line-number) 6) 
 
(printf "~a: ~a~n" (current-line-number) 8)

(via plt)

There is a good list of Scheme related lectures here.

The first release of my OpenCL binding is available.

http://planet.plt-scheme.org/display.ss?owner=jaymccarthy&package=opencl.plt

– Jay

(via PLT)

I am happy to announce that videos of all talks at ICFP and some of the associated workshops this year have made available online:

http://www.vimeo.com/user2191865/albums

I’m sure you’ll join me in thanking Malcolm Wallace for the time and effort he put into making this possible. Thank you Malcolm!

–Wouter

There are videos for the Erlang Workshop 2009, CUFP 2009, Haskell Symposium 2009, ICFP 2009, and Haskell Implementers Workshop 2009 events.

(via PLT)

bzlib/thread provides additional concurrency constructs by building on top of PLT Scheme’s concurrency primitives to help simplify programming in message passing style that Erlang has helped popularized.

(via PLT)

If anyone here is interested in genetic programming, the PLT implementation of my Push/PushGP system, for which several of you provided help over the last few weeks, is posted at http://hampshire.edu/lspector/schush.ss

–Lee

(via PLT)

A useful utility program is one that neatly prints a file or set of files, often a program listing, with each page labelled with filename and page number and each file starting on a new page.

That program turns out to be somewhat tricky to write. In ancient times, before laser printers, most output was to dot-matrix printers using fan-fold paper, and it was amusing to see programs that couldn’t count lines correctly, so the output drifted up and down on successive pages. Another common error of file printers is to print a useless blank page after a file that exactly fills the previous page.

Your task is to write a program that neatly prints a file or set of files. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

When you want to evaluate code inside of DrScheme, you hit the F5 key and the entire editor buffer gets evaluated inside of a new REPL. Unlike Emacs, the ability to send the current expression, region, or buffer to the REPL isn’t available. It might sound constricting, but in practice it is very nice because you are always working with the most up-to-date versions of your definitions. It might sound slow to start a new REPL on each run, but it isn’t; on my older desktop the new REPL comes up before my finger even comes off of the F5 key. This approach seemed like a nice to have for working with OCaml in Tuareg mode on Emacs, so I pieced together a function to do so against Tuareg 1.45.6:

(defun tuareg-eval-buffer-drscheme-style ()
  "Send the buffer to a brand new Tuareg Interactive process."
  (interactive)
  (tuareg-kill-caml)
  (sleep-for 0.25)
  (if (get-buffer tuareg-interactive-buffer-name)
      (kill-buffer tuareg-interactive-buffer-name))
  (tuareg-eval-buffer)
  (switch-to-buffer tuareg-interactive-buffer-name))

Out of the box Tuareg mode will ask you what program name to run to start OCaml each and every time you evaluate the buffer, even when the variable storing that name is defined. I didn’t find a way to avoid this prompt so I patched Tuareg such that it will not ask you if a value is already defined for the program name. Here is the patch.

Thus far it has been nice to have the option of evaluating the whole buffer in a new REPL in addition to the existing incremental evaluation options.

I have two collections and I need to see if one of them is a representation of the other. Since each kind of object has an Id, the two sets of Ids should match, but since collections are unordered, you can't just do a pairwise match.

The solution is to use the containsAll method to see if each collection contains all the elements of the other one. In Scheme this is trivial:

(let ((foo-ids (map foo-id (get-foos)))
      (bar-ids (map bar-id (get-bars))))
  (and (contains-all foo-ids bar-ids)
       (contains-all bar-ids foo-ids)))

in Java, not so easy:

Collection<Id> fooIds =
    Collections2.transform(getFoos(),
                           new Function<Foo, Id> () {
                             @Override
                             public Id apply (Foo foo) {
                               return foo.getId();
                             }
                           });
Collection<Id> barIds =
    Collections2.transform(getBars(),
                           new Function<Bar, Id> () {
                             @Override
                             public Id apply (Bar bar) {
                               return bar.getId();
                             }
                           });
return fooIds.containsAll(barIds) &&
       barIds.containsAll(fooIds);

I know that this is not Java's forte, but this isn't some obscure stratified monadic combinator, it's just map for heaven's sake! If future maintainers of this code can't handle map, maybe they should consider a career in the fast food industry.

Collection expectedIds =
    Collections2.transform(fooCollection,
                           new Function () {
                             @Override
                             public Id apply (Foo foo) {
                               return foo.getId();
                             }
                          });

Maintenance of the Tuareg mode for Emacs has been taken over by some Jane Street Capital folks and can be found here on OCamlCore.

(via caml-list)