Object vs Procedure
In imperative programming we use statements to change the state of the program and consecutive statements describe the control flow (do something, then do something else).
Declarative programming paradigm focuses on the logic and not on the control flow. In declarative programming we describe how the result should look like but not how it needs to be accomplished.
Declarative languages include logic languages (e.g. Prolog), functional languages (e.g. Haskell, Scheme), template-based (XSLT) and database (SQL).
Imperative languages include scripting languages (Perl, Python, PHP,…) and object-oriented (C++, Java, C#,…)
Scheme and Java belong to different programming paradigms.
| Scheme features: | Java features: |
|---|---|
| Variables in Scheme are dynamically typed (no need to declare the type of the variable when you define it) | Variables in Java are statically typed (the type must be declared when variable is defined) |
| Recursion (no loop statements) | Iterative loops |
| Scheme is rule-based and uses pattern matching, high-order functions, some lazy evaluation (data is evaluated when it is used) | Java uses abstract data types, inheritance overriding, polymorphism |
| lexical-scope (the interpreter searches in lexically surrounding definitions (lambdas and lets)) | dynamic scope (the interpreter searches for a local definition of a variable in the frame of function. If it isn't found, the interpreter searches up the calling stack for a definition.) |
Java is object oriented and Scheme is procedure oriented.
Procedures are fundamental blocks of Scheme programs. Recursion is also a procedure in Scheme on contrast with java implementations of recursion as an iterative method.
Consider a function which adds two numbers
Java recursive implementation may look like:
static int add (int x, int y)
{if(y==0)
return x;
else
return (1+add (x, y-1));
}
Scheme as a functional language supports optimized tail recursion as it allows to pass a function as an argument and return as a value.
Consider the same function which adds two numbers implemented with tail recursion in Scheme:
(define (succ x)(+ x 1))
(define (prev x)(- x 1))
(define (add x y)
(if (eq? y 0) x (succ (add x (prev y)))))
What’s the difference? Lets add 2 and 3
If we look at the steps of the java recursive implementation, we’ll see:
add (2 3)
add (3 2)
add (4 1)
add (5 0)
If we look at the steps of Scheme function, we’ll see something like this:
(add 2 3)
(succ (add 2 2))
(succ (succ (add 2 1)))
(succ (succ (succ (add 2 0))))
(succ (succ (succ 3)))
(succ (succ 4))
(succ 5)
Though the result is the same the process of computation is different as Scheme tail recursion optimization uses memory differently and allows to prevent stack overflow.