BioNotes.Org

ML, vim, biology, math, and more

General Lisp Notes

BP Learning

12/27/2024

  • 6:23 - comparison with other languages. Page count of how long each language specification is for Scheme, vs. C, C++, Java, C#, JS.
    • Most of those specs do not include libraries. Closest is C at 176 pages
    • Scheme comes in under 50 pages, which includes the standard libraries
  • 8:30 Two models for programming: Turing Machines and Lambda Calculus.
    • They can accomplish all the sam things, but operate very differently.
  • 9:15 A lot of people think of Scheme as a functional programming language. That’s technically not true because functional programming languages do not allow assignments but Scheme does.
    • Most Scheme programmers try to mostly avoid using assignments but it is not completely forbidden.
  • Scheme is standardized through RnRS where n refers to an integer. Full name is Revisedn Report on the Algorithmic Language Scheme.
    • For more, see the Standardization section of the wiki page on the history of Scheme.
    • The latest large standard is R6RS, ratified in 2007.
    • The latest small revision is called R7RS from 2022. The R7RS website contains PDF and html versions for the R7RS spec.
    • As of 2018, most people use and know R5RS from the mid 1990s. This talk is based on R5.
  • 10:20 Originally, Brendan Eich planned to use Scheme as the programming language for the web browser. That’s why JavaScript borrows a lot from Scheme.
    • Originally, Eich was hired by Netscape to implement Scheme, but b/c of Netscape’s biz dev deal with Sun / Java, they rebranded and changed the syntax what eventually became ECAMScript to resemble Java.
  • 11:15 Why should we learn scheme?
    • Some of the best books ever published on programming use Scheme
    • Scheme expands one’s imaginatin on relationship between code and data, how does programming really work, what is the purpose of syntax, how do you make something powerful without too much clutter, how does one pare down features to a minimal set?

Scheme Syntax

  • 13:08
  • Goal of Scheme is to have as minimal syntax as possible.
  • Basic procedure call uses prefix’d function followed by n number of arguments.
    • Procedures can have dashes inside
    • There are no in-fix operators like simple math operators +, -, x, /, etc. Or more accurately, these operators exist but only as prefix operators that come first before the arguments
    • Benefit is that this is that Polish Notation means that one can have unary, binary, ternary, or arbitrarily large number of arguments without getting tangeled up with how does one wrangle with the syntax of binary operators like +.

If statements (15:03)

(if
  condition-check-procedure
  then-procedure
  else-procedure
)

Example

(if (< x 3)
  (display "I am a number less than 3")
  (display "I am a number that is 3 or greater")
)
  • Note: < is a procedure call, it is not an infix operator, followed by arguments x 3

12/29/2024

Basic Syntax: Lists of Values

  • 15:18 Everything in Scheme is a list, even the code.
  • Use a single quote in front of a group of values to specify that it is a list instead of a procedure call.
    • Note that Scheme refers exclusively to functions as procedures. For more on this plus similarities/differences with Haskell, see ChatGPT
  • 17:30 Try some REPLs at this online Scheme playground:
(define x '(1 2 3))
(car x) ;; output: 1
(cdr x) ;; output: (2 3)
  • Legacies of developing LISP on the IBM 704
  • car = Contents of Address part of the Register
  • cdr = Contents of Decrement of the Register
  • cons used to construct lists, e.g. this single line (cons 1 (cons 2 (cons 3 '()))) outputs this: (1 2 3).
    • Note that one must first create an empty list with (), and then add elements (starting with 3, then 2, then 1) to that empty list.
  • Local variables are generated with the let command.
  • 18:10 There are many types of let commmands, the most common is let*
    • Other variants: vanilla let, letrec, etc.

Basic Syntax: Creating a function with Lambda

(lambda
  parameter-list
  function-body
  more-function-body
  ...
)
  • The last expression evaluated is the return value of the function.
  • Lamdbda functions are ‘born anonymous, but can be assigned names using let, set!, or define.
  • Examples of procedures that multiply by 2x, using define, let`+ local variable, etc.

Misc Syntax

  • Empty list '()
  • Booleans #t for true; #f for false
  • Functions that yield side-effects are marked with a !, e.g,. set! modifies a variable.
  • single line comments begins and goes through EOL using the semicolon ;.

Recursion

  • 20:35 Scheme really wants you to use recursion instead of iteration.
    • All routines can be written nested of the same procedure (aka recursively) or using the while loop (aka iteratively/procedurely)
    • Maybe better way of thinking about recursion is saying a function calls itself.
  • Procedural routines talk about the method of how something is done
  • In contrast, recursive routines talk about the logic of how something is done
  • Scheme emphasizes the focus on logic and makes everything recursive.
  • 21:20 A Scheme program usually does 3 things:
    1. Check to see if you are done
    2. Perform a single task well
    3. Narrow a bigger task to a smaller task
  • 22:00 By encapsulating into a recursive programs, we can:
    1. Eliminate problems with variables that we left or forgot to set
    2. Explicitly mark control-handling vs. task-handling even for non-standard flows
    3. Create a function which is more easily proven to be correct, since all in-flows and out-flows are marked
  • 22:37 Example of a program that eats 100 apples. Comparison of procedural vs. recursive implementation
  • 24:33 Tail Call elimination and why recursion in Scheme is not expensive
    • scheme was the first programming language to introduce tail-call elimination
    • TC-elimination does not eat stack space. Stops the explosion in the call stack that comes from repeated resursive calls. The recursive version of the 100 apples program has a constant stack size
    • eliminates many tradeoffs between writing elegant code (well-structured, easy to understand) versus optimized code (performant/efficient)
  • 26:06 Poorly formatted table that shows programming languages that support tail calls (scheme, scala, f#, lua, JS after ES6 and for Safari only), those that don’t (C#, Java, Python, JS before ES6). And it depends for Lisp overall, C, and Obj-C.

Closures

  • 27:30 Closures allow for function-generating functions
  • If a function is created in a local context, all calls (present and future) to that function will be performed in the same local context
    • this is true even if that context has been returned from!
  • Essentially, a function retains a pointer to the stack frame that originally created it
  • 28:40 Example: Counter
(define make-counter
  (lambda (starting-number)
    (let (
           (next-value
             (lambda ()
               (set! starting-number (+ starting-number 1))
               starting-number
             )
           )
         )
         next-value
    )
  )
)
  • And some sample commands:
(define counter1 (make-counter 10))
(define counter2 (make-counter 100))
(counter1)    ; output 11
(counter2)    ; output 101
(counter2)    ; output 102
(counter1)    ; output 12

Objects

  • 31:16 Objects are just advanced closures.
(define make-counter-object
  (lambda (starting-number)
    (let* (
            (original-value starting-number)
            (next-value
              (lambda ()
                (set! starting-number (+ starting-number 1))
                starting-number
              )
            )
            (reset-value
              (lambda ()
                (set! starting-number original-value)
              )
            )
          )  
          (list (list 'next next-value) (list 'reset reset-value))
    )
  )
)

Macros

  • 33:00

Video: Continuations

  • Also by BP Learning, Jonathan Bartlett
  • URL: https://www.youtube.com/watch?v=Ju3KKu_mthg
  • Introduction to the Stack and Stack Frames starts at 8:22