Christoph Schwarzweller: Scheme

Zadania (Scheme)

Jakie są wartości następujących wyrażeń?

==> 10 


==> (+ 5 3 4) 


==> (- 9 1) 


==> (/ 6 2) 


==> (+ ( * 2 4) (- 4 6)) 


==> (define a 3) 


==> (define b (+ a 1)) 


==> (+ a b ((* a b)) 


==> (= a b) 


==> (if (and (> b a) (< b (* a b))) 
        b 
        a) 


==> (cond ((= a 4) 6) 
          ((= b 4) (+ 6 7 a))
          (else    25))

Proszę napisać funkcję (new.< x y), (new.> x y), (new.= x y), (new.<= x y), (new.>= x y) oraz (new.<> x y). Należy z wbudowanych funkcji używać wyłącznie funckcję < (oraz predykaty oczywiście).
Proszę napisać funkcję (call-with-5 p), której wartość jest wartością funkcji p dla argumentu 5.
```
Przykład: ==> (call-with-5 square)
          25
```
Jaka jest wartość wyrażenia (call-with-5 call-with-5)?
Proszę napisać funkcję (same-values? p1 p2 x y), której wartość jest #t, jeżeli (p1 x y) i (p2 x y) mają tą samą wartość i #f w przecziwnym przypadku.
```
Przykłady: ==> (same-values? = new.= 3 1)
           #t
           ==> (same-values? < > 2 3)
           #f
```
Proszę napisać funkcję (sum-of-squares-of-maxima a b c), której wartość jest sumą kwadratów dwóch większych argumentów.
Używając model środowiska, proszę pokazywać jak wyrażenie (sum-of-squares-of-maxima 5 7 6) zostaje ewaluowane.
Proszę napisać funkcje (odd? n) oraz (even? n), które sprawdzają, czy liczba naturalna n jest nieparzysta względnie parzysta. Należy używać wyłącznie funkcje #t, #f, zero? oraz "-1".
Proszę napisać rekurencyjną oraz iteracyną funkcję (fib n), która obliczy n-tą liczbę Fibonacci.
Proszę napisać funkcję (hanoi n), która rozwiązuje problem Wieży Hanoi dla n krążków.
Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2. Proszę napisać rekurencyjną oraz iteracyjną funkcję (exp b e) na podstawie tej właściwości. Używając model środowiska, proszę pokazywać, jak wyrażenie (exp 2 6) zostaje ewaluowane.

Niech będą dane następujące definicje funkcji.

(define m 1)             (define n 1)
(define (p m)            (define (q n)
   (pp 5))                  (define (qq x)
(define (pp x)                 (+ x n))
   (+ x m))                 (qq 5))

Jakie są wartości wyrazień (p 11) w lewym i (q 11) w prawym przypadku? Proszę wytłumaczyć wyniki używając model środowiska.

Dlaczego wyrażenie if nie można sam definiować w następujący sposób?

(define (new-if warunek alternatywa1 alternatywa2)
   (cond (warunek alternatywa1)
         (else    alternatywa2)))

Proszę napisać funkcję (product term a next b) analogicznie do funkcji sum z wykładu. Proszę pokazywać, jak używając product można definiować funkcję silnia oraz przybliżać p na podstawie formuły p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .
Proszę napisać funkcję (accumulate combiner null-value term a next b), która jest uogólnieniem funkcji sum i prod. Argumenty term, next, a i b zachowują to same znaczenie niż w funkcjach sum i prod. combiner jest dwuargumentową funkcją, która opisuja, jak (term a) zostaje dodane do akkumulacji dalszych termów. null-value jest wartością inicjalną do używania w końcowym przypadku.
Proszę pokazywać, jak można definiować funkcje sum i prod używając accumulate. Proszę też napisać iteracyjną wersję funkcji accumulate.
Nawet funkcję accumulate można dalej uogólnić. Proszę napisać funkcję filter-accumulate, która ma dodatkowy argument pred. pred jest (jednoargumentowym) predykatem a filter-accumulate dodaje (term a) do wynika tylko, jeżeli a spełnie predykat pred.
Używając filter-accumulate proszę obliczyć sumę kwadratów liczb pierwszych w interwale [a,b] oraz produkt wszystkich liczb naturalnych i mniejsze niż n, takie że nwd(i,n) = 1.
Niech będzie dana następująca definicja funkcji (comb f g).
```
(define (comb f g)
   (lambda (x) (f (g x))))
```
Używając model śdowiska, proszę pokazywać jak wyrażenie ((comb square double) 5) zostajy ewaluowane.
Proszę napisać funkcję (deriv f dx), którą wartość jest funkcją, która przybliża funkcję f' używając formułę
```
 Df(x) = (f(x+dx) - f(x)) / dx.
```
```
Przykład:  ==> ((derive cube .001) 5)
           75.015
```

Dla dowolnych funkcji g(x) i h(x,z) schematy rekursji (prymitywnej) i minimalizacji są dane przez

Rek(x,0)   = g(x)                         μh(x) = min{ i | h(x,i) = 0 }, jeżeli minimum to istnieje
Rek(x,y+1) = h(x,Rek(x,y))                μh(x)↑,                       w przeciwnym przypadku.

Proszę napisać funkcje (Rek g h) i (mu h), których wartości są funkcjami realizując te schematy.

W Scheme też można pisać funkcje z dowolną ilością argumentów:
```
 (define (f x y z . l) (...))
```
oznacza, że funkcja f ma conajmniej trzy argumenty (x,y i z). Jeżeli f dostaje wię niż trzy argumenty, są one pisane do listy l .

a) Proszę napisać funkcję plus, która podsumuje dowolną ilość liczb.

b) Proszę napisać funkcję par dla dowolniej ilości (jednoargumentowych) funkcji f_i. Wartość funkcji par jest (jednoargumentową) funkcją, która dla argumenta x obliczy listę wszystkich
wartości f_i(x).
```
  Przykłady: ==> ((par id square cube) 3)
             (3 9 27) 
             ==> ((par double double) 5)
             (10 10)
```
Proszę napisać następujące funkcje dla list:

a) (append l m), która konkatenuje listy l i m.

b) (reverse l), która obróci listę l.

c) (last l), która znajduje ostatni element w liscie l.

d) (delete x l), która skasuje element x z listy l.
Proszę napisać funkcję (square-list l), której wartość jest listą kwadratów elementów listy l.
Proszę napisać funkcję (mapcar f l), której wartością jest lista wartości f(e) dla wszystkich elementów e w liscie l.
Obiekty nie będące parami nazywają się atomy. Proszę napisać funkcję, która

a) sprawdza, czy w liscie l znajdują się wyłącznie atomy.

b) obliczy, ile jest atomów w liscie l.

Proszę napisać funkcję (member2 x l), któ sprawdza, czy gdzieś w liscie l znajduje się x.

Przykłady: ==> (member2 'a '(b (c a) b))
           #t
           ==> (member2 '(a) '(b (c (a) d) e))
           #t
           ==> (member2 '(a) '(b c a))
           #f

Proszę implementować arytmetykę liczb zespolonych

a) używając metodę "mainfest types".

b) używając metodę "data-directed programming". Implementacja tablic można znaleść tutaj.

c) używając metodę "message passing".
Proszę napisać funkcję (ewal wyrażenie wartości), która oblicy wynik dla wyrażeń boolowskich. wyrażenie jest listą, której pierwszym elementem jest "typ" wyrażenia, a następne
elementy tej listy, to podwyrażenia; na przykład lista '(and x (not y)) reprezentuje wyrażenie x∧¬y. wartości jest listą, w której znadują się wartości zmiennych.
```
Przykłady: ==> (define w '((x . #f) (y . #t) (z . #f)))
           w
           ==> (ewal '(and y (not x)) w)
           #t
           ==> (ewal '(and y (and (not x) z))) w)
           #f
           ==> (ewal '(and y 1) w)
           #t
```
Niech a₁, a₂, ... będą wyrażenami. Reguła jest dana w formie {a_i₁,...a_{i_n}} → a_i. Reguła jest faktem, jeżeli n = 0.
Niech R będzie zbiorem reguł. Wyrażenie a jest prawdziwe w R, jeżeli

(i) a jest faktem lub

(ii) istnieje reguła {a_i₁,...a_{i_n}} → a_i w R, taka że a_i = a oraz a_i₁,... a_{i_n} są prawdziwe w R.

Proszę napisać funkcję (valid a R), która sprawdza, czy wyrażenie a jest prawdziwe w R. Proszę użyć przy tym reprezentacje (fact a_i) dla faktu oraz (rule (a_i₁ ... a_{i_n}) a_i)
dla reguły {a_i₁,...a_{i_n}} → a_i.
```
 Przykład:
 ==> (define R '((fact a₁)
                 (rule (a₁) a₂)
                 (rule (a₁ a₅) a₃)
                 (rule (a₂) a₅)
                 (rule (a₂ a₆) a₄)))
 R
 ==> (valid 'a1 R)
 #t
 ==> (valid 'a3 R)
 #t
 ==> (valid 'a4 R)
 #f 
```

Proszę napisać destruktywną wersję append! funkcji append. Jakie są wartości następujących wyrażeń?

==> (define x '(a b)) 

==> (define y '(c d)) 

==> (append x y) 

==> (cdr x) 

==> (append! x y) 

==> (cdr x)

Co robi następująca funkcja?

 (define (coś x)
    (define (loop x y)
       (if (null? x)
           y
           (let ((temp (cdr x)))
              (set-cdr! x y)
              (loop temp x))))
    (loop x '()))

Proszę narysować diagramy dla wyrażeń (define v '(a b c d)) i (define w (coś v))i po ich wykonywaniu.

a) Proszę napisać funkcję (make-konto balance), która generuje nowe konto z balance złotymi. Na koncie mają być możliwie następujące operacje: Podjęcie, wpłacenie oraz
informacje, ile jest na koncie.

b) Proszę modifykować funkcję make-konto z cięci a), taka że ona generuje konta z hasłami, tzn. operacje zostają wykonywane tylko, jeżeli użytkownik używa prawdziwe hasło.
```
 Przykład: ==> (define konto (make-konto 100 'hasło))
           konto
           ==> ((konto 'hasło 'withdraw) 40)
           60
           ==> ((konto 'inne-hasło 'withdraw) 20)
           złe hasło
```

Proszę napisać funkcję (counting-version f), która ma jedonargumentową funkcję f jako argument. Wartość tej funkcji jest nową jednoargumentową funkcję, która liczy, ile razy
funkcja f została używana.

 Przykład: ==> (define sq (counting-version square))
           sq
           ==> (sq 5)
           25
           ==> (sq 7)
           49
           ==> (sq 'ile)
           2
           ==> (sq 'reset)
           0
           ==> (sq 'ile)
           0

a) Niech będą dane nastepujące definicje.

 (define n 3)
 (define p (lambda (x)
              (set! n (+ x n))
              (* 2 n)))
 (define q (lambda (n proc)
              (set! n (proc n))
              (if (< n 41)
                  (set! n (q (+ 1 n) p))
                  '())
              (p n)))

Używając model środowiska, proszę pokazywać jak wyrażenie (q 1 p) zostaje wykonywane. Wartość wyrażenia, to 2160. Jaką ma wartśż zmienna n po wykoniwaniu?

b) Niech będą dane nastepujące definicje.

 (define n 3)
 (define p (lambda (x)
              (set! n (+ x n))
              (* 2 n)))
 (define q (lambda (n proc)
              (define p (lambda (x)
                            (set! n (+ x n))
                            (* 2 n)))
              (set! n (proc n))
              (if (< n 41)
                  (set! n (q (+ 1 n) p))
                  '())
              (p n)))

Używając model środowiska, proszę pokazywać jak wyrażenie (q 1 p) zostaje wykonywane. Wartość wyrażenia, to 8832. Jaką ma wartśż zmienna n po wykoniwaniu?

Uwaga: Rysunki będą ogromne!

Wyniki programu Queue z wykładu wyglądają trochę dziwne:

 ==> (define q (make-queue))
 q
 ==> (insert-queue! q 'a)
 ((a) a)
 ==> (insert-queue! q 'b)
 ((a b) b)
 ==> (delete-queue! q)
 ((b) b)
 ==> (delete-queue! q)
 (() b)

Proszę wyjaśnić te wyniki oraz napisać funkcję (print-queue q), która "prawdziwie" pisuje kolejkę q.

Proszę napisać funkcję (count-boxes l), która obliczy, ile jest par w liscie l.

 Przykład:  ==> (define x '(a b c))
            x
            ==> (define z (cons x x))
            z
            ==> (count-boxes x)
            3
            ==> (count-boxes (append x x))
            6
            ==> (count-boxes z)
            4

Proszę napisać (niedestruktywną) funkcję (cykle? l), która sprawdza, czy l jest listą cykliczną. Lista l jest cykliczna, jeżeli na L możliwie jest wyknoywanie nieskończonej ilości
operacji cdr.
Na wykładzie został podyskutowany simulator układów logicznych.

a) Proszę napisać funkcję (or-gate o1 o2 output), która generuje bramkę or.

b) Proszę napisać funkcję (full-adder a b c-in sum c-out), która generuje (pełny) sumator.

c) Ripple-carry-adder, to układ, który sumuje dwie liczbe binarne a_n ... a₁ i b_n ... b₁. Wynik sumacji, to n bitów s_n ... s₁ oraz jeden bit c (carry).
Proszę napisać funkcję (ripple-carry-adder A B S c), która generuje takiego sumatora. Argumenty A, B i S są listami kablów a_i, b_i i s_i, a c kablem carry.
Proszę wygenerować ripple-carry-adder dla n = 4 bity i z nim obliczyć 1011 + 0011 oraz 1011 + 0110.