💾 Archived View for michal_atlas.srht.site › posts › post-ppa.gmi captured on 2024-05-26 at 14:39:46. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-02-05)
-=-=-=-=-=-=-
This is quite a specific document for quite specific people My UNI teaches a course on Programming Paradigms, which is great and all, however it focuses solely on those, even though it teaches Racket and Prolog as a byproduct. Sadly omitting some crucial general programming concepts in the languages, for Scheme at least that I hope to introduce here.
I warn that I’m no expert this is just a student’s random knowledge and experiences
Most of this is going to be general Scheme, if a part is Racket specific then it’ll be marked with a 🚀
;=> Marks the return value of an expression
Enough blabbering let’s go
In general any functions:
Functions defined on alternate types usually put that type before a dash, and leave it out if the type is a list.
Comparators often omit the dash and just use the symbol right away i.e.:
Anything in Scheme is usually considered true, unless explicitly #f.
(if "a" 2 3) ;=> 2 (filter identity '(1 #f #f 2 #f)) ;=> '(1 2)
Explicitly sets the value of some variable to a value: scheme (set! <variable> <value>) This should basically be avoided as much as possible, some implementations even have significant slowdowns when this is used.
Once upon a time circa 1958 there was Lisp, a specific language in of itself, quite different from what you see today, although based on many of the same principles. Some time after that Sussman was teaching at MIT and in 1975 published “Scheme: An Interpreter For Extended Lambda Calculus”, which is as far back as I can trace it, and it was designed for teaching students. Lisp itself went through many changes, even evolving new versions with major differences. From Lisp 2 came Common Lisp, an ANSI standardized massively widespread specification, which is basically what most people think of when one simply says Lisp, as the original language seems to have effectively disappeared, replaced by these modern descendants that have sine been called Lisps.
Ever since the original paper, there have been many revisions, and standardisation efforts. A committee oversees the creation of rⁿrs standards, the name of which is based on the original “Revised Report on the Algorithmic Language Scheme”, which was succeded by the “Revised Revised Report”, and then they decided to just mark it with an exponent “Revised³ Report”.
The most commonly used one today is r5rs, even though r6rs and r7rs do exist. The standards are remarkably short (10s of pages) and I encourage you wholeheartedly to give them a read, as they introduce basically the entire language in a very nice manner. The fact that these exist doesn’t in any way mean that implementations abide by them, however, they usually include a “differences from r5rs” section. And implement basically everything there is and some more.
The “Scheme Requests for Implementation” are a sort of standard library for Scheme. It functions basically the same as RFCs and submits and discusses various modules, features and libraries, that would benefit most programmers. So you won’t find any networking or graphical libraries, rather list tranformers, advanced macros and syntax, standardized ways to approach some features such as structs or loading libraries themselves, alternate whitespace syntax, curried functions, and so much more.
You are already familiar with SRFI-1 (List Library), which introduces fold, take, first, filter, partition, memq, etc., etc. Many SRFIs (and in fact most below 100) made it directly into implementations and are either already part of the language, or need to be imported as a library.
(require <lib>) (require <lib1> <lib2> ...)
SRFIs are in the srfi/# namespace:
(require srfi/1 srfi/26)
Acquiring new libraries in Racket is done through raco:
raco pkg install <lib-name>
#\a #\^ #\newline #\space
\# initiates a character constant, after which follows either a character or the name of one. Most implementations allow a way to specify the character by codepoint (🚀 #\u65).
Useful functions are:
As these are separate types, one cannot just use them as numbers as in C, but this conversions allows for those kinds of shenanigans.
In addition to classic comparators, there’s also case-insensitive versions
And predicates on the subject of the type of character:
We already know the syntax so let’s mention the functions right away:
Also has case-insensitive comparator variants as char.
(string-append "a" "hello" " another") ;=> "ahello another"
Lisps have a very convenient system for working with numbers, basically mostly that you don’t have to care at all.
In essence Lisp only has one numeric type, that is accepted by almost any mathematical operation. These “Numbers” may hold integers, bigints, fractions, complex numbers or floats, which each interop with all others. And since they’re engrained in the language, methods have no problem simply returning any of them such as sqrt a complex result or / a fraction.
Numbers are always written without any whitespace so 1+5i is valid but 1+ 5i is not. Most are written as you’d expect:
Scheme also has a notion of precise and imprecise numbers. Everything except floats is precise (Imaginaries depend on if the implementation allows fractions in them), and doing an operation on precise numbers, will always yield precise results. However a precise and imprecise argument have an imprecise result:
(+ 3/4 5/6) ;=> 19/12 (+ 3/4 5/6 1.0) ;=> 2.583333333333333
We defined a list as a series of cons cells, where the last one holds the empty list, in its cdr. These are called proper lists. A dot is used to denote an improper list, which has the element after the dot as the last element instead of the empty list.
'(1 2 3) = (cons 1 (cons 2 (cons 3 '()))) '(1 2 . 3) = (cons 1 (cons 2 3))
This is mostly useful to either understand the output of a command that went wrong, or to create cons pairs.
'(3 . 4)
This sort of pair is often used when we need to associate two items, so it’s good to know about them.
Or association lists, use cons pairs to associate data.
(define x '((a . 4)
(b . 5)
(c . "axe")))
An Alist is simply a list of cons pairs, where each car is the key to the cdr. It’s accessed through functions assq and assoc, which do the same but, the key has to be equal through eq? and equal? respectively.
(assq 'a x) ;=> (a . 2) (assq 'c x) ;=> (c . "axe") (assq 'd x) ;=> #f
It is not strictly required to have cons pairs in an alist however, it’s a convention and many other non-core functions that are common such as acons or assq-ref, or the Racket hashmaps, basically expect that to be the case.
These are what we’ve been using all along, we just didn’t know about them. Any string of characters, you see just lying around is a symbol, most of them get evaluated as code, some are quoted, all are still symbols.
They’re very useful as a sort-of enum.
Funtions: - symbol->string - string->symbol - eq? - this is basically one of the main uses for them, they’re fast to compare
SRFI-9 defines a syntax and approach to basically structs that isn’t too powerful, but is basically universally implemented everywhere and good enough for 90% of applications, that aren’t heavy OOP.
The following syntax defines a new record:
(define-record-type <name>
(<constructor> <arg1> <args> ...)
<predicate?>
(<slot-name> <getter> [<setter>])
(<slot-name> <getter>)
...)
(define-record-type <post>
(make-post title body)
post?
(title post-title)
(body post-body))
Yes, you might be used to calling records structs and slots properties, but this is the name that is used and it’s not just a Scheme thing.
The name of a struct is usually surrounded by <>. The predicate is usually just the name itself with a ?. And getters often follow the pattern <record-name>-<slot-name>.
Yeah, it looks to have some redundancy, make a macro if you wanna
Use the constructor to create a record, it takes arguments that equate to the slot names those arguments are assigned to. So, since above we declared make-post to take title and body then those are the two arguments, and they’ll bind to those slots in order: ```scheme (define my-p (make-post “Great Title” “Dumb body”))
(display my-p) ;; prints: #<<post> title: “Great Title” body: “Dumb body”> ```
The getter takes a record and returns the slot’s value: scheme (post-title my-p) ;=> "Great Title"
The predicate behaves as any other, telling you if the given variable holds a variable, that is a record of that given type.
Setters are left as an excerise for the reader
Defines can basically occur anywhere they bloody please, and it’s useful for functions that require some parameter, but which would be the same for every use.
(define (foo file)
(define (log message)
(display message file))
(log "A")
(log "Another")
...)
log captured file from its context and so there’s no need to pass it again.
There are ofc hygienic macros that work like define-macro and allow arbitrary changes, since they have to carry around context information and such, they’re slightly more difficult to use and I won’t be covering them.
(define-syntax-rule <input-pattern> <output-pattern>)
(define-syntax-rule (foo a b c)
(b a c))
(foo 2 + 3) ;=> 5
These basically perform a pattern matching rewrite of what you’d expect the arguments to be, into a new form. Any bound variables are rewritten, everything else is left as it is.
(define-syntax-rule (foo a b c)
(+ 3 4))
(foo 2 + 3) ;=> 7
It can have an almost arbitrary structure:
(define-syntax-rule (foo (a b) () c)
(b a c))
(foo (2 +) () 3) ;=> 5
(foo (2 +) 3) ;=> error, doesn't match
An ellipsis (…) marks a repeated pattern, the ellipsis has to occur in the output for every pattern that contains a repetition in the input: ```scheme (define-syntax-rule (foo a b …) ‘(b … a))
(foo a b c d) ;=> (b c d a)
(define-syntax-rule (foo a b …) ‘((a b) …))
(foo a b c d) ;=> ((a b) (a c) (a d))
(define-syntax-rule (foo (a b) …) ‘((b a) …))
(foo (a b) (c d)) ;=> ((b a) (d c)) ```
There is also a more universal version called syntax-rules, which define-syntax-rule is just a shorthand for.
(define-syntax <name>
(syntax-rules (<literals...>)
([<input-pattern> <output-pattern>]
[<input-pattern> <output-pattern>]
[<input-pattern> <output-pattern>]
...)))
This introduces a macro that is named <name> which is the symbol that has to occur, at the start of an expression if it’s to be transformed by this. syntax-rules then goes rule-by-rule and transforms using the first one that matches.
Literals are uninterpreted symbols, for example if they contain =, then any use of = in any input pattern will never bind a variable, and only match the literal symbol =.
Scheme is not a purely functional language, so it may be useful to evaluate some expressions in sequence.
(begin
<expr 1>
<expr 2>
...
<expr last>)
This simply evaluates the expressions one by one, from left to right, and returns the value returned by the last expression.
This may be useful for example since, if only expects one expression, and you might want to do multiple things.
(if some-cond
(begin
(display "It was true")
(+ 5 5))
(+ 2 3))
Takes a procedure and a list, and “splices” them as arguments to the procedure.
(apply + '(3 4 5 6)) ;=> 18 ;=> rewrites to: (+ 3 4 5 6)
The “spliced” argument is only the last one, any previous ones are given as normal:
(apply map list '((1 2) (3 4))) ;=> ((1 3) (2 4)) ;=> rewrites to: (map list '(1 2) '(3 4))
These are two useful macros, that allow for quick ifs with only one branch. scheme (when #t <do stuff ...>) (when #t (display 2) (display 5)) (unless #t <do stuff ...>)
Unless executes only if given a #f.
Let loops are among the most useful iteration concepts in the language in my humble opinion. They are basically syntax sugar for, first creating a procedure named <name> with the arguments being the list of bound variables and then invoking it with those binds:
(let <name> ([a 2] [b 4]) <body>)
;; equivalent:
(letrec ([<name> (lambda (a b) <body>)])
(<name> 2 4))
This allows us to reference that name and give it different arguments:
(let loop ([in 7][out '()])
(if (zero? in)
out
(loop (- in 1) (cons in out)))) ;=> '(1 2 3 4 5 6 7)
As this use is tail recursive, it basically translates to simply starting over, but with different arguments and returning the value of that.
This is often implemented through external libraries, but Racket decided to have it in the core language.
(for ([<bind> <iterable>]
[x '(1 2 3 4)]
[y #(1 2 3 4)]
[z "1234"]
[a (in-range 1 6)])
<body>)
This syntax allows basically anything that has some values inside it, to be traversed and the body called with the <bind> bound to each value in turn. And if there are multiple binds, then they are run in parallel: ```scheme (for ([x #(a b c)] [y ‘(1 2 3)]) (display (list x y)))
;; prints: (a 1)(b 2)(c 3) ```
If you want to iterate over a cartesian product, then add a * after the for.
(for* ([x #(a b c)]
[y '(1 2 3)])
(display (list x y)))
;; prints: (a 1)(a 2)(a 3)(b 1)(b 2)...
If you want to accumulate the result then add the target type after a slash in the for
(for/list ([x #(1 2 3)]
[y '(1 2 3)])
(+ x y))
;=> '(2 4 6)
This works for many operations:
Procedures can often benefit from allowing the caller to specify only some arguments, and leaving the rest as defaults.
There are two types of such ommited arguments, optional and keyword.
Optional work similar to C++, where you can add defaults to arguments from the end: scheme int foo(int a, int b = 4, int c = 6); where foo takes, 1 obligatory argument and two optional ones. You can’t specify c without specifying b and just invoke it by passing 1 to 3 arguments.
In general there’s always a macro that implements it one way or another in every Scheme, but this is how 🚀 specifies it in their core
(define (foo a [b 4] [c 6])
...)
(foo 1)
(foo 1 2)
(foo 1 2 3)
;; all valid
At times when this is not enough, keyword arguments come into play. For these there’s new syntax, a #: followed by some characters: scheme ##:keyword ##:whatever
You can now specify a function to take the specific argument this keyword references: scheme (define (foo #:bar b #:go [c 4]) (list b c)) Even keyword arguments can be optional, here I must specify #:bar as it binds b that has no default and may or may not specify #:go to change the value of c.
(foo) ;; error (foo 4) ;; also error (foo #:bar 4) ;=> '(4 4) (foo #:bar 4 #:go 2) ;=> '(4 2) (foo #:go 2 #:bar 4) ;=> '(4 2)
One of the ways keyword and optional arguments are sometimes implemented, is through rest arguments, which are even useful all on their own. They simply accept everything as rest arguments and then analyze that list.
If you precede a dot before the last argument in a lambda’s arguments list then, any arguments beyond that point will get accumulated as a list under the name that comes after.
(define (foo . x)
(display x))
(foo 1 2 3 4)
;; prints: '(1 2 3 4)
However the previous arguments must still be provided and bound and they don’t count to the final rest argument list:
(define (foo a b . c)
(display a)
(display b)
(display c))
(foo 1) ;=> errors since b is missing
(foo 1 2)
;; prints:
1
2
()
(foo 1 2 3 4 5)
;; prints:
1
2
(3 4 5)
Schemes have an alternative to C’s printf, the syntax of which came mostly from Common Lisp. Basically everything you need to know is that unlike C, Lisp knows the type so instead of “%d”/”%f”/”%s”/etc. you just have “~a”.
“~a” displays a value and “~s” writes it (the difference is discussed later).
There is often just one function named format, that takes a port or a bool (#t to display to stdout and #f to generate a string), and does a lot more, such as allowing styling of floats with “~0.2f”, or specifying padding, uppercasing and such.
It came from Common Lisp so it’s one function that does a boatload of stuff in one
Racket it seems chose to just implement “~a” and “~s”. And split format and printf as two functions to generate strings and print:
(format "Hello ~a." 4) ;=> "Hello 4." (printf "~a + ~a = ~a" 2 3 (+ 2 3)) ;; prints: 2 + 3 = 5
This difference here is very interesting, too much so for this post, so probably to be continued …