wiki:V2

Old is gold

Scheme

Scheme is a towering monument of unsurpassed programming language design. Scheme

  • everything is an expression (which evaluates to a value).
  • evaluation by recursive application of reduction rules (a model of evaluation of logical terms).
  • so-called Applicative Order (evaluates sub-expression first).
  • has nested block structure from Algol 60 (nesting is the major principle of mother Nature).
  • is mostly functional (bindings could be rebound, set-car! set-cdr! etc).
  • has type-tagged values (each value has a type, bindings instead of box-like variables).
  • lexical scooping by default (proper lexical closures).
  • procedures are values (every value is a first-class citizen).
  • is strongly typed (no implicit coersions, errors are trapped).
  • dynamically typed (types are checked at runtime, no annotations necessary).
  • because of the above has the numeric tower (+ and * are generics).
  • TCO
(define square (lambda (x) 
                   (* x x))

(define average (lambda (x y)
                     (/ (+ x y) 2.0))

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.00001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (iter guess)
    (if (good-enough? guess)
        guess
        (iter (improve guess))))
  (iter 1.0))

(sqrt 2)

There is some real gold of math and programming.

Notice, how there is no type clutter and no notion of what kinds of numbers we are dealing with, thanks to the numeric tower.

(define (fixed-point f x)
  (define (close-enough a b)
    (< (abs (- a b)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough guess next)
          next
          (try next))))
  (try x))

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))

This code will be the gold-standard for us to compare other languages.

This could be compiled into native code in at least 3 different implementations - mit-scheme, chezscheme and gambit-c.

(define dx 0.0001)

(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x)) 1.0))

(sqrt 2)

Erlang

The second greatest language after Scheme. Erlang

  • pure-functional (no mutation is possible).
  • immutable bindings (once bound symbols cannot be rebound. X stays for whatever it is forever).
  • procedures are values (every value is a first-class citizen).
  • strongly typed (no implicit coersions, errors are trapped - fail fast mantra).
  • dynamically typed (types are checked at runtime, no static annotations required).
  • pattern-matching on types and structures.
  • pure-message-passing language (the only way to communicate is by sending and receiving messages).
  • arity-based functions.
  • explicit exports from modules (modules are more powerful than nesting).
  • proper math with a numeric tower.
  • TCO

A tail-recursive factorial (accumulator pattern).

Fac  = fun(0, F) -> 1; 
          (N, F) -> N * F(N-1, F) end.

Fac(50,Fac).
Y = fun(Fn) ->
            F = fun(X) -> Fn(fun(A) -> (X(X))(A) end) end,
            F(F)
    end.

Fac = fun(F) ->
              fun(0) -> 1;
                 (N) -> N * F(N-1)
              end
      end.

(Y(Fac))(50).

Standard ML

  • everything, excepts declarations, is an expression (val bindings are declarations to a compiler).
  • evaluation by recursive application of reduction rules (a model of evaluation of logical terms).
  • each value has a type, (bindings instead of box-like variables).
  • functions are values just like any other value (first-class citizens).
  • fun is just syntactic sugar for the val = fn ... declaration (same as lambda in Scheme).
val tolerance = 0.00001;

fun fixed_point (f:real->real) (guess:real) = 
  let
    fun close_enough x y = abs (x - y) < tolerance
    fun try x =
      let 
        val next = f x 
      in
        if close_enough next x
        then next 
        else try next
      end
  in try guess end;

fun average x y = (x + y) / 2.0;

fun average_damp f:real->real =
  fn (x:real) => average x (f x);

fun sqrt x:real =
  fixed_point (average_damp (fn y:real => x / y)) 1.0;

val dx = 0.00001;

fun deriv (g) = fn x => (g(x + dx) - g(x)) / dx;

fun newton_transform g = fn x => x - g x / (deriv g) x;

fun newtons_method g guess =
  fixed_point (newton_transform g) guess;

fun sqrt x = 
  newtons_method (fn y:real => y * y - x) 1.0;

sqrt 2.0;

We have to specify types, we have to ensure type consistency of everything being real.

Miranda

  • pure functional
  • so-called Normal Order of evaluation (passing unevaluated expressions until value is needed).
  • no monads required

Haskell

  • everything is an expression (which evaluates to a value).
  • evaluation by recursive application of reduction rules (a model of evaluation of logical terms).
  • each value has a type (bindings instead of box-like variables).
  • functions are values just like any other value (first-class citizens).
  • Normal Order
  • Monadic IO

Ocaml

  • everything is an expression (which evaluates to a value).
  • evaluation by recursive application of reduction rules (a model of evaluation of logical terms).
  • each value has a type, (bindings instead of box-like variables).
  • functions are values just like any other value (first-class citizens).
  • Applicative Order.

Scala

Last modified 4 months ago Last modified on Oct 29, 2019, 6:51:11 AM
Note: See TracWiki for help on using the wiki.