skipped exercise

You can do if you are interested without extra background knowledge assumption

needs big changes to the overall program structure

4.12 See 0.b.

0.b.0.a. Again, wait implies we need to change the unify internal structure...
- Also see 4.18 TODO which also relates with delay/wait.

open-ended

2.14
- This is not easy.
- I tried to find one possible example to implement in https://martinfowler.com/dsl.html#:~:text=Domain%2Dspecific%20languages%20have%20been,strut's%20configuration%20file.... but only "ant" and "graphviz's dot language" seem to be implement as one demo. But the former is related with Java and the latter is related with drawing one graph.
- "salary calculation" in this doesn't have one general model.
- After all, this exercise is more about how we think about a domain and then program it. IMHO checkers and then manual implementation of chess are enough.
  - "domain model" as SDF_notes.md shows is about "abstract types".

needs knowledge beyond what SICP and SDF teach

3.22-b

on different terminals. beyond programming basic strategies.

related with complexity analysis (TODO after CRLS. Others: search CRLS here.)

3.6-c

unrelated with programming strategies since my goal is "A strong understanding of programming" said in mit_6-046j_2005

partially done exercises

4.13
- match:compile-pattern used in maybe-substitute
4.17
- not consider lazy evaluation ~~and set-car! etc~~.
  - But this is fine at least for the book demo since it also doesn't consider that.
  - "term project" may mean the above and other set! variants like set-car! etc.
- See TODO in codes
4.19
- a.
  
  look for a functional solution—but don't try too hard!

related with compiler

better to do with some basic compiler backgrounds which includes type-inference
- 4.14
  
  make it as general as you can
  - I even didn't know what to do for that "general case", more specifically I didn't know what problems will have for "procedures passed as arguments and returned as values" when we assume all procedures with generic arguments ~~(so "free variables" are )~~.
  - related
    - 4.16

related with complexity analysis: better done after CRLS

4.18

Notice

Sometimes, I only give one sample test since I didn't intend to learn how to write the safe tests.
I use naming with _ instead of - since words constructed with the former can be selected in VSCode with the double clicks.
solution comment also see codes.
Here I use the absolute path like (load "~/SICP_SDF/SDF_exercises/software/sdf/abstracting-a-domain/game-interpreter.scm") to make we can call scheme < foo.scm in any dir. You can use sed etc. to change this.
All exercise solutions will be given related tests. But obviously I won't ensure the test must promise the solution is correct since there is no such a test (Correctness should be proved by maths).

I won't dig into

checking whether it is appropriate to use eq? or equal? etc. for each case. (so same for memv, etc.)
tests of sample implementations.

miscs clipboard

SDF_exercises TODO
- SDF_exercises TODO when happens
- (codes not included by the book)
- IGNORE:
sci-42ver/SDF_exercise_solution
"Won't dig into" in SDF_notes.md

SDF_exercise_solution

exercise solution for Software Design for Flexibility (SDF)

@exercise solutions by 3 references (i.e. nbardiuk etc.) and 6.945_assignment_solution checked up to now (sometimes code base has sample implementations)

with check comments in codes.

For chapter 4 later, search in this repo by chebert*/**/*.rkt,6.945*/**/*.scm,sdf_mbillingr*/**/*.scm,sdf/**/*.scm ~~and code base by ignoring these~~. Ignore sdf-function-combinators.rkt,ps0[0-4]/,sdf/automatic-differentiation/*.scm,sdf/combining-arithmetics/*.scm which are all codes for former chapters and sdf/manager/*.scm which is about software manager.
- ~~Here 6.945*/**/*.scm can be 6.945*/**/*.scm~~ We can also ignore later chapters sdf/better-layering/*.scm
  - So sdf-function-combinators.rkt,ps0[0-4]/,sdf/automatic-differentiation/*.scm,sdf/combining-arithmetics/*.scm,sdf/manager/*.scm,sdf/better-layering/*.scm
    - we can add some sdf-function-combinators.rkt,ps0[0-4]/,sdf/automatic-differentiation/*.scm,sdf/combining-arithmetics/*.scm,sdf/manager/*.scm,sdf/better-layering/*.scm,sdf/layers/*.scm,sdf/pattern-matching-on-graphs/*.scm,sdf/propagation
- nbardiuk can be skipped.
2, 3, 4 (see "chapter 4" section where all exercises with reference search methods have been checked)

@%exercise tests finished (obviously not considering skipped exercises)

2, 3,
4 (4.12 skipped)
- 4.1~~7, 4.8 (see SDF_exercises/chapter_4/4_8_based_on_transformation.scm), 4.9~~4.11, 4.13~~17, 4.19~~21.

no need for tests

due to about complexity analysis

4.18

@TODO

I skipped checking the detailed implementation of the following since they are less related with what the book intends to teach
- make-predicate-template (not shown in the SDF book. There is no related funcs even by searching "template") So I skipped checking SDF_exercises/software/sdf/user-defined-types/vector-arith.scm (user-defined-types/vector-arith).
- define-generic-procedure-extractor (not shown in the SDF book. There is no related funcs even by searching "extractor")

@%review of "SDF_exercises TODO"

grep -v "IGNORE\|(cph)\|SKIPPED\|when happens\|(codes not included by the book)" -r ./**/*.scm | grep "SDF_exercises TODO" --color=always (notice here the piped results have esc color codes, so "SDF_exercises TODO when happens" won't work).

From cc09d5b919575d7a27d30d94100d2f12dd8248ef up to .

@%review of mere TODO

grep TODO --exclude="6.945_assignment_solution/ps[0-9]*/code/*.scm" -r ./**/*.scm | grep -v SDF_exercises | grep -v "IGNORE\|(cph)\|SKIPPED"

I didn't check for md/rkt but just for my written codes (mostly are with scm suffix).
Here IGNORE means that has been finished, SKIPPED means it hasn't been finished but skipped forever for some reason (e.g. it is not related with what this book intends to teach like weak-memq) and WAITED means it will be done in the future.
See this for how glob is used.
I skipped SICP related paths using this find . $ -type d \( -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -exec 'grep TODO --exclude="6.945_assignment_solution/ps[0-9]*/code/*.scm" | grep -v SDF_exercises | grep -v "IGNORE\|(cph)\|SKIPPED"' {} +

~~Use this to allow pipe~~ find . $ -type d \( -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f 2>&1 | grep TODO --exclude="6.945_assignment_solution/ps[0-9]*/code/*.scm" | grep -v SDF_exercises | grep -v "IGNORE\|(cph)\|SKIPPED"
Use this to allow pipe find . $ -type d \( -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -printf '"%p" ' | grep TODO --exclude="6.945_assignment_solution/ps[0-9]*/code/*.scm" | grep -v SDF_exercises | grep -v "IGNORE\|(cph)\|SKIPPED"
- better to allow filenames with spaces find . $ -type d \( -path ./.git -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -print0 | xargs -0 grep TODO --exclude={"6.945_assignment_solution/ps[0-9]*/code/*.scm",\*.{md,rkt,sample}} --color=always | grep -v "SDF_exercises TODO" | grep -v "IGNORE\|(cph)\|SKIPPED" (notice not to use the mere SDF_exercises since for grep'ing many files file path is also included in the output)
  - I also excludes ./.git and \*.{md,rkt,sample}.
  - https://unix.stackexchange.com/questions/493723/grep-exclude-dir-dont-work/493909?noredirect=1#comment1512591_493909 find . $ -type d \( -path ./.git -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -exec sh -c 'grep TODO --exclude={"6.945_assignment_solution/ps[0-9]*/code/*.scm",\*.{md,rkt,sample}} -v "$SDF_exercises TODO$\|IGNORE\|(cph)\|SKIPPED" "$@" --color=always' sh {} + (This won't work. Here I want to keep both color and pipe. But that may be in conflict). Use find . $ -type d \( -path ./.git -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -exec sh -c 'grep -v "$SDF_exercises TODO$\|IGNORE\|(cph)\|SKIPPED" --exclude={"6.945_assignment_solution/ps[0-9]*/code/*.scm",\*.{md,rkt,sample}} "$@" | grep TODO --color=always' sh {} + (not use find . $ -type d \( -path ./.git -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o -type f -exec sh -c 'grep TODO --exclude={"6.945_assignment_solution/ps[0-9]*/code/*.scm",\*.{md,rkt,sample}} "$@" | grep -v "$SDF_exercises TODO$\|IGNORE\|(cph)\|SKIPPED" --color=always' sh {} +)
    - see (notice || is used there for shor circuit so that "no issue" will return true without checking the latter and "issue" will check the latter. Using && will reject "no issue") and this for ! ({} won't work for -name for name) Here I skipped all sub-files in paths SDF_exercises/chapter_* since they are in homework which TODO won't be probably helped by reading the book further. Here * can match dir prefix like ./fubar3 in man. find . $ -type d \( -path ./SDF_exercises/chapter_\* -o -path \*/.git -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o $ -type f \( ! -path "./6.945_assignment_solution/ps[0-9]*/code/*.scm" -a ! -name "*.md" -a ! -name "*.rkt" -a ! -name "*.sample" $ \) -exec awk '/TODO/ && !/SDF_exercises TODO/ && !/IGNORE/ && !/IGNORE/ && !/$cph$/ && !/SKIPPED/ {match($0,/TODO/); printf "\033[1;31m" FILENAME "\033[0m: " substr($0,1,RSTART-1) "\033[1;31m" substr($0,RSTART,RLENGTH) "\033[0m: " substr($0,RSTART+RLENGTH) "\n"}' {} +
      - we need explicit print
      - match
      $ find . \ $ -type d \( -path ./SDF_exercises/chapter_\* \ -o -path \*/.git \ -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o \ $ -type f \( ! -path "./6.945_assignment_solution/ps[0-9]*/code/*.scm" \ -a ! -name "*.md" -a ! -name "*.rkt" -a ! -name "*.sample" $ \) \ -exec awk '/TODO/ && !/SDF_exercises TODO/ && !/IGNORE/ && !/$cph$/ && !/SKIPPED/ && !/code_base TODO/ {match($0,/TODO/); printf "\033[1;31m" FILENAME "\033[0m: " substr($0,1,RSTART-1) "\033[1;31m" substr($0,RSTART,RLENGTH) "\033[0m: " substr($0,RSTART+RLENGTH) "\n"}' {} +
      - most of codes in the code base uses "TODO:" instead of only "TODO".
      - Use this after many improvements (use gsub as Stéphane Chazelas shows )
        find . \ $ -type d \( -path ./SDF_exercises/chapter_\* \ -o -path \*/.git \ -o -path ./CS_61A_lab -o -path ./exercise_codes -o -path ./lecs $ -prune \) -o \ $ -type f \( ! -path "./6.945_assignment_solution/ps[0-9]*/code/*.scm" \ -a ! -name "*.md" -a ! -name "*.rkt" -a ! -name "*.sample" $ \) \ -exec awk '!/SDF_exercises TODO/ && !/IGNORE/ && !/$cph$/ && !/SKIPPED/ && !/code_base TODO/ && gsub(/TODO/,"\033[1;31m" "&" "\033[0m: ") {printf "\033[1;31m" FILENAME "\033[0m: " $0 "\n"}' {} +
        
        perl
        
        -p
        
        test: echo "TODO foo\nTODO TODO" | perl -pe 's/TODO(?! foo)/\e[31;1m$&\e[m/g' echo "TODO foo\nTODO TODO" | perl -pe 's/TODO/\e[31;1m$&\e[m/g unless /TODO foo/'
        
        To discard all the lines that contain foo bar and all that don't contain foo and highlight foo in the remaining ones: compared with To discard the lines that contain foo bar and highlight occurrences of foo in remaining lines, you could do:
        
        awk automatically print, so same.
        
        TODO IMHO -e '^' is redundant.
        
        https://unix.stackexchange.com/questions/788816/how-to-highlight-the-matched-regex-pattern-got-by-many-regex-exps-disjoined-with/788821?noredirect=1#comment1512739_788821
        
        printf '%s\n' foo 'foo bar' 'foo foo bar' 'bar foo' bar | perl -ne 'print if ! /foo bar/ && s/foo/\e[1;31m$&\e[m/g' or printf '%s\n' foo 'foo bar' 'foo foo bar' 'bar foo' bar | xargs -I{} echo {}
        
        ~~Here ?! may consume some string~~
        
        printf '%s\n' foo 'foo bar' 'foo foo bar' 'bar foo' bar | grep -v 'foo bar' | grep --color -e '^' -e foo Here -e '^' ~~may not~~ won't be colored since it matches with the starting empty string. It just keeps something like bar.
        
        printf '%s\n' foo 'foo bar' 'foo foo bar' 'bar foo' bar | grep -P --color 'foo(?! bar)' - won't remove "foo foo bar" since it has some sub-string matched although also with some sub-string un-matched.

nbardiuk solution comment

~~By https://github.com/search?q=repo%3Anbardiuk%2Fsoftware-design-for-flexibility%20exercise&type=code it probably only has 3 exercise solutions.~~ It only have solutions up to chapter 2 regular-expressions based on 5 filenames.

2.1

; (assert (= 2 (get-arity h))) this is too naive - does not allow to use 'list Not. Since if this holds, then (assert (= 1 f-arity)) also doesn't work.

2.2

(guarantee-procedure-of-arity h (make-procedure-arity 2) 'h) implies h can have more than 2 arguments.

2.3

totally independent from 2.1~2 without any assertion.

mbillingr solution comment

2.1

call-with-values

the continuation expects to receive the same number of values that procedure accepts as arguments. Thunk must return multiple values using the values procedure. Then procedure is called with the multiple values as its arguments. The result yielded by procedure is returned as the result of call-with-values This implies compose. Thunk is invoked with a continuation that expects to receive multiple values; i.e. what it does will "receive multiple values" as (apply g args) implies. See https://www.gnu.org/software/guile/manual/html_node/Continuations.html
TODO '"multiple-value" continuation'

2.2

The following is more general than mine since it allow the case where f has variable argument number and g has the fixed argument number.

    (assert (or (fixed-arity? arity-f)
                (fixed-arity? arity-g)))

2.3 (See codes)

lack

2.4

chebert solution comment

It seems to have no test files by searching "r:seq" with only 1 result file.

2.1 (See code comments in this repo)

2.2

combine-arities is a bit different due to arity-list.

2.3

without any assertion same as nbardiuk.

TODO

2.7
- (ere expr) or (bre expr) multiple references ...
- Emm... I have forgotten what I meant when I reviewed this while reading chapter4...

lack

MIT/GNU Scheme internal func description

Use ((lambda (x) x) (values 1 2)) to show what values returns.
reduce diff fold kw: "right identity"

Note that ridentity is used only in the empty-list case.
- you’d like to avoid the extra application incurred when fold applies f to the head of list and the identity value i.e. return (fold f (car list) (cdr list)). But this just decreases only one operation.

TODO

If multiple returns occur from map, the values returned by earlier returns are not mutated. https://www.gnu.org/software/mit-scheme/documentation/stable/mit-scheme-ref/Mapping-of-Lists.html Does it mean https://groups.google.com/g/comp.lang.scheme/c/ruhDvI9utVc/m/jS0DdIh2yKMJ? Then what does "earlier returns" mean?
However, in cases where this ambiguity can arise, you should use find-tail instead of find—find-tail has no such ambiguity: IMHO both "no such pair" and "doesn’t find such an element" will occur.
The following are both undefined in saved-total-index and MIT_Scheme_Reference.
- list-of-unique-symbols?
- list-of-type?
  - maybe mean a list of data whose type satisfies pred by (list-of-type? object change?).

@exercise comments

chapter 2

2.9
- POSIX_regex
  
  The string matched by a contained subexpression shall be within the string matched by the containing subexpression. If the containing subexpression does not match, or if there is no match for the contained subexpression within the string matched by the containing subexpression, then back-reference expressions corresponding to the contained subexpression shall not match. See "the expression "(a(b))\2" fails to match 'abab'" where b must correspond to "\2", then "aba" can be matched to "the containing subexpression". When a subexpression matches more than one string, a back-reference expression corresponding to the subexpression shall refer to the last matched string. See "the expression "^(ab*)*\1$" matches 'ababbabb', but fails to match 'ababbab'." where the last "abb" is matched to "\1".
2.10
- factor
2.12
- check the rules intuitively by manual playing for 2 players https://www.chessmultiplayer.com/
- Don't try to implement the castling rule. we need to check 3 conditions in wikipedia if to implement it. a. "must not have previously moved" ~~can be checked by flag.~~ b. "There must be no pieces between the king and the rook;" can be checked by inspecting position-info between them c. "The king may not currently be ..." i.e. call check for all related positions. d. "The castling must be kingside or queenside" since they are the only 2 possible cases.
- All rules are based on https://en.wikipedia.org/wiki/Rules_of_chess#Touch-move_rule
  - Here I won't check
    - "Competitive rules of play", i.e. FIDE rules.
    - "Touch-move rule" and "Resigning" since these depends on artifical interposition.
  - IGNORE
    - (see the following) ~~We need to check~~
      
      It is illegal to make a move that places or leaves one's king in check.
      - so also Checkmate
    - (see "castling".) ~~3. Check similar to require-jumps: If failure, then Checkmate~~
      - So we also won't check "stalemate", then combined with "Dead position" we won't check "draw".
    - due to the very hardness of implementation ~~Dead position~~ skipped due to the possible huge combination number (man_1_options * man_2_options * man_1_options_currect ... infinitely recursion) and we must check it after each iteration.
      
      by any sequence of legal moves. even if we don't consider the complexity overhead, the correct algorithm is not easy https://chess.stackexchange.com/a/22764.
      - https://chess.stackexchange.com/a/22557 doesn't say any valuable but just show possibility ...
        
        TODO I can't see such a comments for "in the comments user17439".
  - what to do beyond "Basic moves"
    1. Promotion is trivial by checking the type and position (similar to should-be-crowned?)
  - En passant: check adjacent piece "on the same rank" ~~whether with flag "advances two squares on its initial move"~~ (only on the move immediately following the pawn's advance) and type "pawn".
    - I won't check it since pawn can either advance one square twice or advance "two squares" once. "flag" is associated with pmove which won't be remembered for later usage. IMHO the best solution is to add flag with piece but the interface for piece will be all changed.
      - Here whether we can remember history steps is also needed in "castling" to test
        
        The king and rook involved in castling must not have previously moved
- notice after checking https://en.wikipedia.org/wiki/Rules_of_chess#Basic_moves preface
  
  The king can be put in check but cannot be captured (see below).
- chebert
  - check castling
    - by adding types. (also used for other special moves)

chapter 3

See 3_3.scm "(only nbardiuk repo is not included in this repo)" but it only have chapter 2 implementation.
mbillingr ~~only has automatic-differentiation.~~ has nothing.
by grep "generic" -r . chebert has nothing for chapter 3 after 3.2 (included). Then by searching keywords like vec-before-func in exercise 3.1~3.3, it also have no implementations for these.
6.945_assignment_solution
- ps03 has 3.2, 3.5, 3.6, 3.7, 4.0 although they are not same as 2024 version.
- ps04 only has one similar implementation of Exercise 3.16.
2
- vector vs list
11
- [111] reference
  - ~~TODO why (D (λy . x + y) 1) doesn't calculate derivative and gets 2.~~

@%chapter 4

1: search algebra-2 (no codes with explanation) 2: simplification 3: sort 4: algebra-3 5: print-all-matches (just codes in SICP_SDF/SDF_exercises/software/sdf/design-of-the-matcher/text-examples.scm without explanation) 6: ?:choice

7,9: ?:pletrec

See in SDF_notes.md

The above is different from SICP 4.79... Here binding is just var->value where value can't be also var. So we can just use the normal env mechanism.

Here the former 3 are related with define-syntax. The last is said in the above quote context.

# https://unix.stackexchange.com/a/721889/568529
$ grep "env" -r ~/SICP_SDF/SDF_exercises/software/sdf/(term-rewriting|unification) --files-with-matches | grep -oP "(?<=$HOME/).*"
SICP_SDF/SDF_exercises/software/sdf/term-rewriting/rule-implementation.scm
SICP_SDF/SDF_exercises/software/sdf/term-rewriting/test-rule-implementation.scm
SICP_SDF/SDF_exercises/software/sdf/term-rewriting/rule-utils.scm
SICP_SDF/SDF_exercises/software/sdf/unification/type-resolver.scm

8: match:vector (assuming following the naming convention) 10: match-args vector? (no use: SICP_SDF/SDF_exercises/software/sdf/combining-arithmetics/vector-arith.scm and SICP_SDF/SDF_exercises/software/sdf/common/pretty-printer.scm)

other possible type-inference extension

subtype etc

@%TODO

~~7,9 (Unification match may use env to implement)~~ 7 will be done implicitly when 9 is done. 9 is ~~similar to SICP 4.79 which needs implement rule based on unification with env~~.
~~11 to be done with 21.~~
~~See above TODO.~~

@% reference implementation checked

chapter 2~3 seems to not use the regex shown in "@exercise solutions..." (I forgot).

For chapter 4, 4.1~21 have been checked with include: chebert*/**/*.rkt,6.945*/**/*.scm,sdf_mbillingr*/**/*.scm,sdf/**/*.scm exclude: sdf-function-combinators.rkt,ps0[0-4]/,sdf/automatic-differentiation/*.scm,sdf/combining-arithmetics/*.scm,sdf/manager/*.scm,sdf/better-layering/*.scm,sdf/layers/*.scm,sdf/pattern-matching-on-graphs/*.scm,sdf/propagation

related helper files describing useful things

sc-macro-transformer
- capture-syntactic-environment.scm

Name		Name	Last commit message	Last commit date
Latest commit History 147 Commits
chapter_2		chapter_2
chapter_3		chapter_3
chapter_4		chapter_4
common-lib		common-lib
software/sdf		software/sdf
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md

License

sci-42ver/SDF_exercise_solution

Folders and files

Latest commit

History

Repository files navigation

skipped exercise

You can do if you are interested without extra background knowledge assumption

needs big changes to the overall program structure

open-ended

needs knowledge beyond what SICP and SDF teach

related with complexity analysis (TODO after CRLS. Others: search CRLS here.)

unrelated with programming strategies since my goal is "A strong understanding of programming" said in mit_6-046j_2005

partially done exercises

related with compiler

related with complexity analysis: better done after CRLS

Notice

I won't dig into

miscs clipboard

SDF_exercise_solution

other sdf solutions (by "Software Design for Flexibility exercise solution github")

different languages

@exercise solutions by 3 references (i.e. nbardiuk etc.) and 6.945_assignment_solution checked up to now (sometimes code base has sample implementations)

@%exercise tests finished (obviously not considering skipped exercises)

no need for tests

due to about complexity analysis

@TODO

@%review of "SDF_exercises TODO"

@%review of mere TODO

nbardiuk solution comment

2.1

2.2

2.3

mbillingr solution comment

2.1

2.2

2.3 (See codes)

lack

chebert solution comment

2.1 (See code comments in this repo)

2.2

2.3

TODO

lack

MIT/GNU Scheme internal func description

TODO

@exercise comments

chapter 2

chapter 3

@%chapter 4

other possible type-inference extension

@%TODO

@% reference implementation checked

related helper files describing useful things

About

Resources

License

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages