Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Using let in Scheme

Name: Anonymous 2013-01-17 2:23

I remember a post a while back where the author said that it's better to avoid using binding constructs like let in languages like Scheme. I was wondering how you'd rewrite something like this:
(let ((s (find (lambda (a) (char=? x (first a))) *translation-list*)))
 (if s (second s) x))

Name: Anonymous 2013-01-17 2:43

Scheme let is okay though let* is understood to be preferred in most implementations. Some style guides prefer a bunch of defines nested in a scope container but thats only a styling choice, I don't like this style personally.

Name: LISPPER 2013-01-17 2:43

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

((lambda (s) (if s (second s) x))
 (find (lambda (a) (char=? x (first a))) *translation-list*))
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iF4EAREKAAYFAlD3q30ACgkQGRQwWY30ng3VUQD/fZ+N+f+w75LVaOvYvpVbzgdd
tJCesQNtn3eNQ6iPoC8A/0XPtyxx63gBK4divRG3ZxwSVaIrMfUtrj9N2DONm8el
=h5wx
-----END PGP SIGNATURE-----

Name: Anonymous 2013-01-17 2:48

>>3
That's pretty neat. Tanks!

Name: Anonymous 2013-01-17 2:58

One does not truly understand let until one invents it.

Name: Anonymous 2013-01-17 4:05

Ordinary let is not much different from a lambda.  let*, if I remember correctly, behaves just like a chain of lambdas.  However, letrec is both more useful and more tricky to translate into lambdas and defines.

Name: Anonymous 2013-01-19 23:58

restoring...

Name: Anonymous 2013-01-20 3:02

>>6

Here's a start if you want to implement letrec. You can express recursion without recursion by passing the function as a parameter to itself. I think think of a way to do it in a macro that doesn't require recursive substitution of variable names though.


(define fact-helper (lambda (f n)
  (if (= n 0)
    1
    (* n (f f (- n 1))))))

(define factorial (lambda (n) (fact-helper fact-helper n)))

Name: Anonymous 2013-01-20 3:04

>>8
letrec is very easy to express in terms of let and set!.

Name: Anonymous 2013-01-20 3:06

>>9
set!

disgusting

Name: Anonymous 2013-01-20 3:22

Here it is!

https://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator

Name: Anonymous 2013-01-20 3:58

I'm having trouble expressing the fix function in scheme without recursion. I'm not sure if it is possible. A shame.

Name: Anonymous 2013-01-20 4:06

Here's what I have though. The only recursive function you need:


(define (fix f)
  (lambda args
    (apply f (cons (fix f) args))))

(define factorial (fix (lambda (f n)
  (if (= n 0)
    1
    (* n (f (- n 1)))))))

Name: Anonymous 2013-01-20 4:49

Oh, nevermind. I could just define fix in the same way done in >>8


(define fix-helper (lambda (self f)
  (lambda args
    (apply f (cons (self self f) args)))))

(define fix (lambda (f) (fix-helper fix-helper f)))

(define factorial (fix (lambda (f n)
  (if (= n 0)
    1
    (* n (f (- n 1)))))))

Name: Anonymous 2013-01-20 7:51

Now do it for two mutually recursive functions.

Name: Anonymous 2013-01-20 8:14

>>15
This works to some degree, although it isn't ideal.


(define fix2-helper1 (lambda (curry-f1 curry-f2 f1 f2)
  (lambda args
    (apply f1 (append (list (curry-f1 curry-f1 curry-f2 f1 f2)
                            (curry-f2 curry-f1 curry-f2 f1 f2))
                      args)))))

(define fix2-helper2 (lambda (curry-f1 curry-f2 f1 f2)
  (lambda args
    (apply f2 (append (list (curry-f1 curry-f1 curry-f2 f1 f2)
                            (curry-f2 curry-f1 curry-f2 f1 f2))
                      args)))))


(define fix2 (lambda (f1 f2) (fix2-helper1 fix2-helper1 fix2-helper2 f1 f2)))

(define is-odd (fix2 (lambda (is-odd is-even n)
                       (if (= n 0)
                         #f
                        (is-even (- n 1))))
                     (lambda (is-odd is-even n)
                       (if (= n 0)
                         #t
                        (is-odd (- n 1))))))

Name: Anonymous 2013-01-20 10:16

>>8
function fact_helper(f, n) {
  if (n === 0) {
    return 1;
  } else {
    return n * f(f, n - 1);
  }
}

function factorial(n) {
  return fact_helper(fact_helper, n);
}

>>14

function fix_helper(self, f) {
  return function() {
    var args = Array.prototype.slice.call(arguments);
    return f.apply(null, [ self(self, f) ].concat(args));
  }
}

function fix(f) {
  return fix_helper(fix_helper, f);
}

function factorial() {
  return fix(function(f, n) {
    if (n === 0) {
      return 1;
    } else {
      return n * f(n - 1);
    }
  });
}

Name: Anonymous 2013-01-20 10:51

>>17
Holy fuck, JavaShit is ugly as a kike.

Name: Anonymous 2013-01-20 12:09

>>18
Your anti-semitism only makes us stronger.

Name: Anonymous 2013-01-20 14:30

>>17
That's a stack overflow waiting to happen.
% node
(function (x) { x(x); })(function (x) { x(x); });
RangeError: Maximum call stack size exceeded

Name: Anonymous 2013-01-20 15:07

>>20
Well, I did the port in >>17 knowing nothing about Scheme. Contributions are welcome if you would like to improve on it.

Name: 16 2013-01-20 16:44

>>21
No, that's a good direct translation. The only problem is that javascript doesn't ensure tail call optimization (or does it now?).

>>15
I'm reinventing loeb aren't I?

Name: Anonymous 2013-01-20 17:24

>>19
Good to know, kike.

Name: Anonymous 2013-01-20 18:45

I think I'm loebing. Am I doing it right?


(define fix-helper (lambda (self f)
  (lambda args
    (apply f (cons (self self f) args)))))

(define fix (lambda (f) (fix-helper fix-helper f)))

(define rev (fix (lambda (f lis acc)
  (if (null? lis)
    acc
    (f (cdr lis) (cons (car lis) acc))))))

(define rev-map1 (fix (lambda (f fn lis acc)
  (if (null? lis)
    acc
    (f fn (cdr lis) (cons (fn (car lis)) acc))))))

(define map1 (lambda (fn lis)
  (rev (rev-map1 fn lis '()) '())))

(define loeb (fix (lambda (f fns)
  (map1 (lambda (fn)
          (lambda args
            (apply fn (cons (f fns) args))))
        fns))))

(define is-even_ (lambda (fs n)
  (apply (lambda (is-even is-odd)
           (if (= n 0)
             #t
             (is-odd (- n 1))))
         fs)))

(define is-odd_ (lambda (fs n)
  (apply (lambda (is-even is-odd)
           (if (= n 0)
             #f
             (is-even (- n 1))))
         fs)))

(define functions (loeb (list is-even_ is-odd_)))

(define is-even (car functions))
(define is-odd (cadr functions))

Name: Anonymous 2013-01-20 18:50

Good to see the Special Olympics of CS back.

Name: Anonymous 2013-01-20 18:51

>>18
Then you've never seen Java or C++.

>>18,23
illogical racist cretin, die in a fire

>>24
Wow.

Name: Anonymous 2013-01-20 19:01

>>25
You're such a jerk, kodak-kun.

Name: Anonymous 2013-01-20 20:08

>>25
Yeah, >>17 won.

Name: Anonymous 2013-01-20 21:10

>>22
Nope, efficient tailcalls are not guaranteed. ECMAScript 6 is supposedly going to fix this… whenever browser/runtime vendors decide to implement it, that is.

Name: Anonymous 2013-01-20 23:51

Here's an implementation of labels from lisp using loeb.


(defmacro (labels fns . body)
  (let* ((fn-names-list (map1 car fns))
         (fn-names-list-name (gentemp))
         (lambdas (map1 (lambda (fn-expr)
                          (apply (lambda (fn-name fn-args . fn-body)
                                   `(lambda ,(cons fn-names-list-name fn-args)
                                      (apply (lambda ,fn-names-list
                                                ,@fn-body)
                                             ,fn-names-list-name)))
                                 fn-expr))
                        fns)))
   `(apply (lambda ,fn-names-list
             ,@body)
           (loeb (list ,@lambdas)))))

Example usage:


(labels ((is-even (n) (if (= n 0) #t (is-odd (- n 1))))
         (is-odd (n) (if (= n 0) #f (is-even (- n 1)))))
 (display (is-even 7))
 (display (is-odd 7)))

Name: Anonymous 2013-01-21 0:06

And then once you have labels, you can easily create named-lambda, and a recursive version of define.


(defmacro (named-lambda name args . body)
  `(labels ((,name ,args ,@body))
     ,name))


(defmacro (rec-define name args . body)
  `(define ,name (named-lambda ,name ,args ,@body)))

Ex:


(rec-define factorial (n)
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

(factorial 25)
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -