From 334e29bf1792e3b3df3b3046f9860069303ffde9 Mon Sep 17 00:00:00 2001 From: jim Date: Tue, 7 Apr 2015 09:59:19 -0400 Subject: [PATCH 1/1] create page --- rosetta3.mdwn | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 101 insertions(+) create mode 100644 rosetta3.mdwn diff --git a/rosetta3.mdwn b/rosetta3.mdwn new file mode 100644 index 00000000..49d7255e --- /dev/null +++ b/rosetta3.mdwn @@ -0,0 +1,101 @@ +## Scheme and OCaml ## + +* You can [try Scheme in your web browser](http://tryscheme.sourceforge.net/). This is useful if you don't have Racket or another Scheme implementation installed---but don't expect it to have all the bells and whistles of a mature implementation! + +* **Type Variants and Pattern Matching** If you want to reproduce this kind of OCaml code: + + # type lambda_expression = Var of char | Lam of char * lambda_expression | App of lambda_expression * lambda_expression;; + + # let rec free_vars (expr : lambda_expression) : char list = + match expr with + | Var label -> [label] + | Lam (label, body) -> remove label (free_vars body) + | App (left, right) -> merge (free_vars left) (free_vars right);; + + # free_vars (Lam ('x', (App (Var 'x', Var 'y'))));; + - : char list = ['y'] + + in Scheme, you have two choices. First, the quick hack: + + ; we use the symbols 'var and 'lam as tags, and assume + ; that an expression will always be a pair of one of these forms: + ; (cons 'var symbol) + ; (cons (cons 'lam symbol) expression) + ; (cons expression expression) + + (define (free-vars expr) + (cond + [(eq? (car expr) 'var) (list (cdr expr))] + [(and? (pair? (car expr)) (eq? (car (car expr)) 'lam)) + (remove (cdr (car expr)) (free-vars (cdr expr)))] + [else (merge (free-vars (car expr)) (free-vars (cdr expr)))])) + + Second, you can create real datatypes and pattern-match on them. There are several tools for doing this. I'll describe the `define-datatype` and `cases` forms developed for the book *Essentials of Programming Languages* (EoPL) by Friedman and Wand. + + (Alternatives include [the `struct` form in Racket](http://docs.racket-lang.org/guide/define-struct.html). Also `define-record-type` from srfi-9 and srfi-57; see also [the r6rs libs](http://docs.racket-lang.org/r6rs-lib-std/r6rs-lib-Z-H-7.html).) + + Here is how the tools from EoPL work. You must begin your file either with `#lang eopl` or with the first two lines below: + + #lang racket + (require eopl/eopl) + + (define-datatype lambda-expression lambda-expression? + (var (label symbol?)) + (lam (label symbol?) (body lambda-expression?)) + (app (left lambda-expression?) (right lambda-expression?))) + + (define (free-vars expr) + (cases lambda-expression expr + (var (label) (list label)) + (lam (label body) (remove label (free-vars body))) + (app (left right) (remove-duplicates (append (free-vars left) (free-vars right)))))) + + (free-vars (lam 'x (app (var 'x) (var 'y)))) + ; evaluates to '(y) + +* Scheme has excellent support for working with implicit or "first-class" **continuations**, using either `call/cc` or any of various delimited continuation operators. See [the Racket docs](http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29). + + In Scheme you can use these forms by default (they're equivalent): + + (call/cc (lambda (k) ...)) + (let/cc k ...) + + If your program declares `(require racket/control)`, you can also use: + + (begin ... (reset ... (shift k ...) ...) ...) + + (begin ... (prompt ... (control k ...) ...) ...) + + (begin ... (prompt ... (abort value) ...) ...) + + These last three forms are also available in OCaml, but to use them you'll need to compile and install Oleg Kiselyov's "delimcc" or "caml-shift" library (these names refer to the same library), which you can find [here](http://okmij.org/ftp/continuations/implementations.html#caml-shift). You'll already need to have OCaml installed. It also helps if you already have the findlib package installed, too, [as we discuss here](http://lambda.jimpryor.net/how_to_get_the_programming_languages_running_on_your_computer/). If you're not familiar with how to compile software on your computer, this might be beyond your reach for the time being. + + But assuming you do manage to compile and install Oleg's library, here's how you'd use it in an OCaml session: + + #require "delimcc";; (* loading Oleg's library this way requires the findlib package *) + (* if you don't have findlib, you'll need to start ocaml like + * this instead: ocaml -I /path/to/directory/containing/delimcc delimcc.cma + *) + open Delimcc;; (* this lets you say e.g. new_prompt instead of Delimcc.new_prompt *) + let p = new_prompt ();; + let prompt thunk = push_prompt p thunk;; + let foo = + ... + prompt (fun () -> + ... + shift p (fun k -> ...) + ... + (* or *) + control p (fun k -> ...) + ... + (* or *) + abort p value + ... + ) + ... + + There is also a library for using *undelimited* continuations in OCaml, but it's shakier than Oleg's delimited continuation library. + + -- 2.11.0