Scheme
a dialect of Lisp, the second-oldest high-level programming language still in use.
programs consist of expressions, which are either call expressions or special forms.
Expressions
may be:
Primitive expressions:
2, 3.3, true, +, quotient, ...
numbers are self evaluating, symbols are bound to values
Combinations:
(quotient 10, 2) - a call expression
Call expressions include an operator and 0 or more operands in parentheses.
A combination that is not a call expression is a special form:
if expression:
(if <predicate> <consequent> <alternative>)
binding symbols:
(define <symbol> <expression>)
new procedure (function):
(define (<symbol> <formal parameters>)
<body>)
Scheme List
is either nil
composed of a first element and the rest (cdr) of the Scheme list
(equal? e1 e2):check is e1 and e2 evaluate to equivalent values
(null? expr):is like (equal? expr nil)
(eq? e1 e2):checks if e1 and e2 evaluate to identical values
like
isin Python
the quote special form takes in a single argument and returns an unevaluated version of the argument
Tail Recursion
an expression in a tail context is evaluated as the last step of the function call
that means, nothing is evaluated/applied after it's evaluated
function calls in tail context are called tail calls
if all recursive calls are in a tail context, we say that the function is tail recursive
if a language supports tail call optimization, a tail recursive function will only ever open a constant amount of frames
an expression is in a tail context only if it's the last thing evaluated in every possible scenario
Writing tail recursive functions
identify recursive calls that are not in a tail context
tail context:
the last body subexpression in a lambda (function)
the consequent and alternative in a tail context if
all non-predicate subexpressions in a tail context cond
the last subexpression in a tail context - and, or, begin, let
create a helper function with arguments to accumulate the computation
Last updated
