? pr [Not everyone needs to program computers.]

Na početnu stranicu! Udruga Darovitih Informatičara Rijeke Na glavni izbornik!

.logo inicijalizacijski file za Berkeley Logo

Dragi moji hakeri, ovo vam je prilično teška građa! Samo naprijed!

U predgovoru knjizi Essentials of Programming Languages (D. Friedman, M. Wand, C. Haynes), Hal Abelson je napisao: "Ova knjiga vas dovodi licem u lice s najbitnijom idejom u programiranju: interpreter za kompjutorski jezik, zapravo je samo običan program!"

korni500.gif (1525 bytes)

Pišite na: logo@dir.hr

Zvuči očigledno, zar ne? Ipak, posljedice te tvrdnje su duboke. Ako ste kompjutorski teoretičar, interpreter ideja vas podsjeća na Godelovo otkriće granice formalnih logičkih sistema, Turingov koncept o univerzalnom kompjutoru i Von Neumannovu ideju o stroju koji radi na temelju spremljenih programa. Ako ste programer, prihvaćanje ideje interpretera je izvor velike moći. Ona vas dovodi do suštinskog pomaka u gledanju i razmišljanu o programiranju.

Prije nego sam naučio o interpreterima, dugo sam se  bavio programiranjem i proizveo nekoliko značajnih programa. Jedan od njih, na primjer,  bio je veliki data-entry i information-retrieval sistem napisan u PL/I. Kada sam programirao taj svoj sistem, gledao sam na PL/I kao na fiksnu kolekciju pravila postavljenih od neke nedohvatne grupe jezičnih dizajnera. Vidio sam svoj posao, ne kao mogućnost da modificiram ta pravila ili da ih čak i suštinski razumijem, već da neumorno listam kroz (veliki) manual i biram ovu ili onu jezičnu konstrukciju za upotrebu. Ideja da postoji neka osnovna struktura u načinu na koji je jezik organiziran i da bi ja mogao promijeniti neke od odluka dizajnera jezika, nikada mi nije sinula.

...

Ako ne razumijete interpretere, ipak možete pisati programe; možete čak biti i veoma kompetentan programer. Ipak, ne možete biti majstor.

...

Hal Abelson

 

 

Ovaj uvod (i diskusije sa Brianom Harvey-em) mi je poslužio kao motivacija da se uhvatim u koštac sa nekim od odluka dizajnera programskoj jezika Logo, koje me već neko vrijeme smetaju. Nemojte ovo shvatiti kao moju kritiku ucbloga, jer ako ništa drugo, ucblogo je daleko najjači Logo interpreter u onom bitnom - teoretskim osnovama. No, iako Brian nastoji ostati vjeran nepisanom standardu Logo jezika, ipak je, onima koji se slažu sa gore navedenim tekstom, ostavio mogućnost da uđu u ucblogo i bitno ga promijene. Time ne mislim na činjenicu da je ucblogo C source kod javno dostupan, već na mogućnosti koje postoje u samome Logo-u da ga se promijeni iznutra.

 

.logo Hrvatska uputstva

 

.logo file nije velik (svega oko 160 linija). No,  ipak ga ne kanim ovdje potpuno objasniti. Naime, može ga se promatrati i razumijevati na dva načina. Prvi način bi bio: kako radi to što već radi, odnosno kako je napisan? Na žalost, takovo objašnjenje nadilazi svrhu ovog teksta i bilo bi sigurno daleko kompliciranije od svih dosadašnjih objašnjenja na hrvatskom Logo Webu. Između ostaloga bi morao pretpostaviti da su oni koji ovo čitaju pročitali sve tri Brianove CSLS knjige??? Mislim da će biti dovoljna samo jedna sasvim teoretska primjedba: većina težih rješenja u .logu zasniva se na činjenici da su programske linije u Lispu (pa tako i u ucblogu) ništa drugo, nego obični podaci. To znači da ih program može obrađivati, mijenjati i sa njima rukovati na isti način kao što, recimo, obrađuje dva broja ili riječi.

Drugi pristup objašnjenju .loga je važniji, a to je: kako upotrijebiti to što .logo omogućuje.

Zamišljen je kao inicijalizacijski file koji se učita u Logo prije nego se počne bilo što drugo raditi. Morate imati ucblogo 4.6 ili noviji da bi to pokušali. To znači da oni koju upotrebljavaju ucblogo 640K DOS verziju (ona je smrznuta na 3.6) ne mogu ukrcati .logo. Expanded DOS verzija (1MB RAM), win/95/98/NT i UNIX verzije mogu raditi sa .logom. (ako imate spori kompjutor, krcanje će dugo trajati). Ne moram ni reći da niti jedna druga verzija Logo-a (uključujući i MSWlogo) ne može raditi sa .logom.

Za MS verzije startajte ucblogo te upišite: load "dotlogo.lg"

Za UNIX verzije startajte ucblogo iz emacs logo-moda (mora biti v2.0) i emacs će vas pitati da li želite da ukrca .logo (ako .logo file postoji u vašem home direktoriju). Ako nemate logo-mode v2.0 (još nije službeno postavljen na Berkeley serveru - čeka se izlazak ucbloga 5.0), .logo ukrcajte isto kao i za MS verziju: load ".logo"

.Logo mijenja standardno ponašanje Logo interpretera i čini ga više sličnim Lispu (u ovom slučaju Scheme-u).

Jedna od osnovnih razlika Logo-a i ostalih Lisp dijalekata, razlika koja bitno utječe na stil programiranja, je što Logo prihvaća za TRUE - istinu. Logo shvaća istinu jedino u obliku riječi "TRUE ("true). Isto tako neistina je samo riječ "FALSE. Ako se bilo kojoj Logo proceduri koja očekuje kao input istinu ili neistinu da bilo što osim te dvije riječi ("true "false) to će rezultirati sa greškom. Zato, osnovna promjena koju .logo donosi je: bilo koja vrijednost se smatra istinom, osim riječi "false. Riječ "true nema specijalnog značenja u ovom kontekstu. Logo procedure IF i IFELSE obje prihvaćaju ovu promjenu, ali TEST IFTRUE i IFFALSE nisu promijenjene -- ja ih jednostavno ne upotrebljavam.

Kada je ovo namješteno, logički primitivi mogu vratiti bilo koju vrijednost kao istinu, a samo riječ "false u slučaju neistine.

OR vraća ono što vraća prva uspješna evaluacija, ili riječ "false ukoliko su evaluacije svih inputa bile neuspješne. AND vraća vrijednost zadnjeg inputa, ako su evaluacije svih inputa bile uspješne, ili riječ "false. Najslobodnija je nova procedura .AND koja prihvaća bilo što, uključujući i ništa kao istinu, a samo riječ "false kao neistinu. .AND će vratiti vrijednost zadnjeg inputa (riječ "#unspecified ako nema vrijednosti), ako ni jedan od inputa nije vratio neistinu, odnosno riječ "false.

Evaluacija logičkih funkcija AND OR i .AND ne izvršava se nužno do zadnjeg inputa (što je slučaj u standardnom Logo-u).

OR vraća odmah kod prvog uspjeha. AND i .AND vraćaju odmah po prvom neuspjehu.

Drugi nivo promjena satoji se od dodavanja Lisp/Scheme specijalnih formi LETREC i COND. I LETREC i COND se ovdje ne ponašaju baš sasvim kao njihove Lisp verzije, ali ako zanemarite detalje, obje su dovoljno blizu. (Jedan od tih detalja je da LETREC upotrebljava *LET binding pravila, umjesto LET.) Druga razlika je da u Logo-u, one zapravo nisu specijalne forme, tako da ću ih dalje zvati procedure višeg reda.

Treći nivo promjena je compiler za procedure višeg reda.

 

Opis procedura višeg reda

 
LETREC prima jedan input, listu ovog oblika:

 LETREC [[[PROC-NAME1 [PROC-TEXT1]]
          [PROC-NAME2 [PROC-TEXT2]]
          [          ...          ]]
         [BODY-FORM1]
         [BODY-FORM2]
         [   ...    ]]
 

PROC-NAME je obična riječ (ime procedure). [PROC-TEXT] je lista od lista, u obliku koji outputira Logo procedura TEXT, odnosno koji DEFINE prihvaća kao input. [BODY-FORM] je instrukcijska lista (obična Logo instrukcijska linija). Blok BODY-FORMa djeluje kao instrukcijske linije u tijelu TO definicije, s tim da svaka linija mora biti lista. Nema nikakovih restrikcija što se može raditi sa BODY-FORM-ama (osim što ne mogu biti rekurzivne), ali njihova glavna svrha je da pozivaju procedure definirane kao PROC-NAME sa pripadajućim inputima.

LETREC outputira ako jedna od BODY-FORM-a outputira.

Sve procedure definirane na ovaj način su lokalne LETREC-u, a ne kontekstu iz kojeg je LETREC pozvan. To jest, nema načina da se pozove PROC-NAME izvan LETRECa. Redosljed po kojem su procedure definirane je važan. BODY-FORM-e mogu pozivati sve procedure bez ograničenja, ali da bi jedna procedura pozvala drugu iz [PROC-TEXT] ta druga procedura mora biti definirana prije. Znači PROC-NAME2 može pozvati PROC-NAME1, ali ne i obrnuto.

Imena u LETREC-u ne slijede Logo, nego Scheme pravila. Ne možete upotrijebiti istu riječ za ime procedure i za ime varijable. To jest, ako ste imali lokalnu ili globalnu varijablu neka-var definiranu prije LETREC-a, ne možete upotrijebiti neka-var za PROC-NAME. Zapravo možete, ali ćete time zasjeniti varijablu koja neće biti dostupna za vrijeme trajanja LETREC-a. Isto tako greška je upotrijebiti PROC-NAME za ime lokalne varijable, kasnije u tijelu LETRECa. Ipak, možete upotrijebiti ime prije definirane globalne procedure za PROC-NAME, ali to nije uputno. Ako to radite, morate biti jako pažljivi da ne stavite poziv te globalne procedure unutar zagrada. Ovo sve što sam do sada rekao o upotrebi imena, može se sumirati u par riječi: PROC-NAME zapravo nisu prave procedure, nego lokalne varijable. (No time zadiremo u onaj dio koji sam rekao da neću objašnjavati, a to je implementacija .loga.)

Specijalno sintaktičko pravilo prilikom poziva PROC-NAMEa iz BODY-FORMa ili PROC-TEXTa je da poziv mora biti u okruglim zagradama: (PROC-NAME input1 input2 ...). Nemojte se pouzdati u Logo tokenizaciju, što znači uvijek ostavite prostor prije ( (osim ako nije odmah iza uglate zagrade).

 

Ovo je u redu    : [(PROC-NAME ...
Ovo nije         : ((PROC-NAME ...      ==>     ( (PROC-NAME ...
                 :x+(PROC-NAME ...      ==>     :x+ (PROC-NAME ...

Evo jednog trivijalnog primjera upotrebe LETREC-a. Radi se o zadatku factoriel:

Logo rješenje (službeno rješenje na državnom 97):

to fact :n
if :n < 0 [op [krivi podatak]]
if :n = 0 [op 1]
op :n * fact :n-1
end

Ovo rješenje ima jedan problem: testira se na krivi (negativni) input pri svakom rekurzivnom pozivu. Ako je :n 100, tada će program 100 puta pitati dali je :n < 0 iako je samo jedno pitanje (prvi puta) dovoljno.

Logo bi tipično ovaj problem riješio ovako:

to fact :n
if :n < 0 [op [krivi podatak]]
op fact.h :n
end

to fact.h :n
if :n = 0 [op 1]
op :n * fact.h :n-1
end

Sada se pita samo jednom, a nakon toga procedura fact poziva helper proceduru fact.h, koja zapravo računa factoriel. Problem sa ovim načinom nije odmah očigledan, ali ipak postoji. Ako je fact dio velikog programa sa puno definiranih procedura, tada smo za ovako trivijalni problem upotrijebili dva globalna imena. Ako sličnih problema ima stotinjak, onda smo definirali stotinjak globalnih imena previše? Nije značajno, ali nije ni elegantno.

to fact :n
if :n < 0 [op [krivi podatak]]
op letrec [[
   [factoriel [[n]
               [if :n = 0 [op 1]]
               [op :n * (factoriel :n-1)]]]]
           [op (factoriel :n)]]
end

I sada pitamo samo jednom, a onda pozivamo lokalno definiranu proceduru factoriel, koja zapravo računa rezultat. Razlika od prijašnjeg rješenja je što ovdje imamo samo jedno globalno ime fact. Lokalna procedura factoriel prestaje postojati čim fact završi svoj posao.

Značajniji primjer upotrebe LETREC biti će prikazan kasnije.

 

Procedura COND prima jedan input, listu ovakovog formata:

 COND [
    [[CONDITIONAL1] [TRUE1a] [TRUE1b] ...]
    [[CONDITIONAL2] [TRUE2a]  ...        ]
    [    ...                      ]
    [else    [CATCH-ALL] ...      ]]

Sažeto. COND radi kao IFELSE sa mnogo else-ova i sa nekim dodacima. Svaki bi se clause u CONDu ([[CONDITIONAL1] [TRUE1a] [TRUE1b] ...])trebao satojati od dva dijela. Prvi je CONDITIONAL izraz. Ako CONDITIONAL izraz vrati istinu, onda se odgovarajući TRUE izrazi izvrše. Svaki clause može imati više od jednog TRUE izraza, a oni izgledaju i rade kao BODY-FORMe u LETRECu, što znači da su zapravo Logo instrukcijske linije. Svaki TRUE izraz mora biti lista. CONDITIONAL izraz može biti i riječ, ali samo jedna.

COND će probati sve CONDITIONAL izraze, dok ne nađe jednoga koji vraća istinitu vrijednost (sve osim "false). Tada će izvršiti pripadajuće TRUE izraze i vratiti vrijednost. Ako svi CONDITIONAL izrazi vrate "false, COND će izvršiti else dio. (Else je zapravo procedura koja vraća "true). CATCH-ALL je samo drugo ime za TRUE izraze, i ista pravila vrijede. Ako izostavite else clause, tada će COND vratiti riječ "#unspecified.

COND uvijek vraća vrijednost, te zato ako tu vrijednost ne trebate, morate output od COND predati proceduri IGNORE (ignore cond [...] ...) . Vrijednost koju COND vraća je ili OUTPUT od jednog od TRUE izraza, ili riječ ?#unspecified, ako TRUE izrazi ne vraćaju vrijednost. Očigledno je da ili svi TRUE izrazi ili nijedan, moraju vraćati vrijednost.

Izuzetno, COND clause može imati samo CONDITIONAL izraz bez TRUE izraza. U tome slučaju, ako CONDITIONAL vrati istinitu vrijednost, tu vrijednost vraća i COND, ili ako vrati "false, COND ide dalje do slijedećeg CONDITIONAL izraza.

 

Jedan jednostavni COND primjer:

 to cond.memberp :element :list
 op cond [
    [[emptyp :list] [op "false]]
    [[equalp first :list :element]]
    [else [op cond.memberp :element bf :list]]]
 end

Ovo bi se dalo jednostavno napistai i bez COND:

to memberp.1 :element :list
if emptyp :list [op "false]
op or equalp :element first :list ~
      memberp.1 :element bf :list
end

Ipak COND je veoma koristan kada ima više od dva ili tri izbora.

 

Sve ovo je napisano na način da i dalje možete izvržavati pa čak i pisati standardne Logo programe, tj. programe koji upotrebljavaju samo standardnu logo sintaksu. Da bi mogli iskoristiti promjene koje donosi .logo morate zapamtiti slijedeće:
Morate qvotirati (staviti u uglate zagrade) sve inpute logičkim funkcijama AND i OR. Na taj način ovaj program razlikuje da li se radi o standardnom ili novom obliku AND/OR funkcija. Mješana sintaksa za inpute AND i OR funkcijama nije dozvoljena, ili ćete qvotirati sve inpute ili ni jedan. Ipak možete mješati standardnu i novu sintaksu u jednome programu, pa čak i unutar jedne TO definicije.

Naravno, sve ovo ima i svoju cijenu. Programi će se izvršavati sporije nego u standardnom Logo-u.

 
Evo i jednog kratkog primjera programskog stila koji je moguć sa Logo-m inicijaliziranim na ovaj način. Odgovor na pitanje, da li je ovaj stil elegantan ili nije, morat ćete potražiti sami. Ono što je ovdje važno je da se čitava konstrukcija naslanja na AND i OR, i za donošenje odluka, i za vraćanje rezultata. Standardni Logo ne može funkcionirati na ovaj način. Kako je ovo usput, i primjer kako upotrijebiti LETREC, dodao sam nekoliko nepotrebnih linija, čija je jedina svrha objašnavanje pravila vidljivosti u LETREC konstrukciji.

 

Kraljice
 

Ovo je rješenje standardnog primjera za problem backtracking-a, tj. traženja rješenja unazad. Treba na šahovsku ploču postaviti 8 kraljica, ali tako da niti jedna ne može napasti drugu. (Zapravo rješenje dozvoljava šahovsku ploču raznih veličina).

;; Startaj kraljice sa queens 8, ako želiš samo prvi rezultat.
;; Da bi dobili sve rezultate startajte sa (queens 8 "false), i pripremite
;; se za dugo čekanje. (Možda bi prije trebali probati 6, ili 4?)

to queens :number [:one.only "true] 1
;; Iduće dvije linije su samo za provjeru vidljivosti
localmake "makeboard "makeboard
pr equalp :makeboard "makeboard
(foreach letrec [[
   ;; Definira lokalnu proceduru makeboard
   [makeboard [[n]
               [localmake "row cascade :n [[x] [op lput # :x]] []]
               [op cascade :n [[x] [op fput :row :x]] []]]]
   ;; Definira lokalnu proceduru shade
   [shade [[queen rest.board [offset 1] 2]
           [if emptyp :rest.board [op []]]
           [op (fput (filter [[x] [op not (or :x = (:queen - :offset)
                                              :x = :queen
                                              :x = (:queen + :offset))]]
                             first :rest.board)
                     (shade :queen bf :rest.board :offset + 1))]]]
   ;; Definira lokalnu proceduru put.queen
   [put.queen [[board result]
               ;; Kada je ploča prazna, gotovi smo
               [if emptyp :board [push "stack :result op :one.only]]
               [localmake "row first :board]
               [localmake "queen and [not emptyp :row] [first :row]]
               ;; Ako kraljica nije postavljena, backtrack-iraj odmah
               [op (and [:queen]
                    [or
                       ;; Idemo naprijed, pokušaj postaviti slijedeću
                       [(put.queen (shade :queen bf :board)
                                   lput :queen :result)]
                       ;; Nema mjesta za slijedeću, pokušaj pomaknuti
                       ;; ovu kraljicu na slijedeće slobodno polje
                       [(put.queen fput bf :row bf :board :result)]])]]]]
                 ;; Početak letrec BODY-FORM-a
                 [localmake "stack []]
                 ;; Provjeri što je u lokalnoj variabli makeboard
                 [pr equalp :makeboard "makeboard]
                 [pr []]
                 ;; Pokreni program i odbaci output (true/false)
                 [ignore (put.queen (makeboard :number) [])]
                 ;; Outputiraj sve pozicije -- letrec ovdje završava
                 [op reverse :stack]]
         ;; Template za foreach
         [[x] [(show "position # :x)]])
;; Procedura put.queen se nemože pozvati odavdje
;; Contents će pokazati da put.queen više ne postoji
pr []
show contents
pr []
;; Lokalna variabla makeboard je opet vidljiva
pr equalp :makeboard "makeboard
end
 

Vjerovatno ste primijetili da ovdje upotrebljavam oba stila za AND/OR . OR u SHADE je standardni Logo OR. Svi AND/OR u PUT.QUEEN su novi. Potpuno je nevažno koji OR je upotrijebljen u SHADE, ali PUT.QUEEN neće raditi ako upotrijebimo standardni stil.

 

Ako promatrate pažljivo što se događa kada pokrenete queens program, vidjeti ćete popriličnu pauzu između prvog "true i prvog ?false ispisa. Nakon toga dolazi još duže čekanje na ispis pozicija. Ne mogu ništa napraviti da se skrati vrijeme koje je potrebno Logu da izračuna pozicije, ali prvi period čekanja je druga priča. Za to vrijeme Logo zapravo ne izvršava queens program, nego prevodi LETREC strukturu u oblik koji standardni interpreter razumije.

Ako ste pokušali pokrenuti COND primjer, situacija je bila još gora. Cond.memberp je rekurzivna procedura, i Logo je prevodio COND strukturu u svakom rekurzivnom pozivu, što čini cond.memberp praktično neupotrebljivim.

Odgovor na ovo -- je naravno, Compiler za procedure višeg reda.

 

.LOGO.COMPILER prima jedan input, listu imena procedura, ili ime jedne procedure. Ako želite compilirati cijeli workspace (sve procedure u radnom prostoru), pozovite ga bez inputa:

.logo.compiler [ proc1 proc2 ...]

.logo.compiler "proc

(.logo.compiler)

 
Kako bi ga provjerili, napišite: .logo.compiler "queens -- i Logo će odgovoriti sa:

compiling queens ...
compilation completed

Sad ponovo pokrenite queens. Oba "true i "false će sada biti ispisana bez čekanja. Compiliran cond.memberp primjer bi također morao raditi normalnom brzinom. Ako želite spremiti compilirane verzije napišite: save.compiled "filename

 
.LOGO.COMPILER može raditi sa veoma kompliciranim strukturama, zato se ne bojte eksperimentiranja. Možete definirati LETREC unutar druge LETREC definicije, COND unutar LETREC, LETREC unutar COND itd itd ... do dubine koja se vama sviđa. Limit je naravno veličina RAMa vašeg kompjutora i njegova brzina. Ista pravila vidljivosti vrijede i za takove ugniježdene strukture, ne možete pozvati unutrašnje PROC-NAME iz vanjskoga. Imajte na umu prije spomenuta posebna pravila sintakse i tokenizacije za LETREC.

Jedan detalj u vezi .logo.compiler-a ipak moram objasniti, jer znam iz iskustva da ljudi, kada čuju riječ compiler odmah pomisle na machine code compiler. Ako ste pomislili da će vam nakon ovoga ucblogo raditi brzinom C compilera, varate se. .logo.compiler prevodi sa .logo jezika visokog nivoa (posebnog interpretera) na standardni logo jezik (standardni interpreter). Rezultirajući kod će raditi istom brzinom (gotovo istom) kao da je napisan u standardnom Logu. Kako taj kod izgleda, možete provjeriti tako da spremite neku compiliranu proceduru,   recimo queens sa save.compiled u file i onda taj file otvorite u editoru. Naravno, nemojte očekivati da će biti lagan za čitanje.

 

Compiler Capabilities (mogućnosti compilera)

Capabilities imaju ovaj format: property   = ime procedure višeg reda
                                               vrijednost = minimalna dubina inputa ? 1

Možete dodati svoje vlastite capabilities (to zapravo znači da ćete napisati nešto slično LETREC ili COND), ako slijedite ova pravila: Procedura višeg reda koju ste napisali mora imati samo jedan input, listu. I naravno, mora biti macro, jer ako nije macro, compiler nema što raditi. Nakon što ste definirali (i testirali) svoju proceduru višeg reda, dodajte jednu pprop liniju u .logo, i to je sve.

Capabilities koje sam ja dao compileru izgledaju ovako:

pprop "compiler.cap "letrec 4
pprop "compiler.cap "cond 2

Ovaj program (.logo) je samo vježba, moj projekt tipa "kućni mezimac".

Ne sugeriram nikome da bi Logo zapravo morao ovako izgledati (ova opaska je samo zbog Briana) ali priznajem da je lijepo napisati program u, recimo Scheme-u i onda ga gotovo doslovno prebaciti u Logo.

.logo nije detaljno testiran. Upotrijebite na vlastitu odgovornost!

**************                                             .logo file                                                    **************
************** selektirajte sve ispod linije i spremite u file sa imenom dotlogo.lg ili .logo **************
;;; -*- logo -*-
;;;
;;; .logo  --  Logo initialization file        Hrvoje Blazevic
;;;
;;; Altering standard Logo behavior - making it more Lisp-like (Scheme
;;; in this case). ;;; This file is just a short example of what can be done with .logo
;;; initialization file, and with the powerful version of Logo
;;; interpreter -- that Berkeley Logo is.

;;; One of the differences between Logo and other Lisp dialects,
;;; and the one that affects programming style, is what Logo accepts
;;; as true. Logo's idea of truth is only the word "true. Likewise,
;;; false is only the word "false -- anything else is error.
;;; Therefore the base change introduced in .logo is: All returned
;;; values are considered true, except the word "false. Word "true has
;;; no special meaning in this context. Both IF and IFELSE accept
;;; this, but TEST IFTRUE and IFFALSE, have not been altered -- I
;;; simply do not use those.
;;;
;;; With this in place, logical primitives can return any value as true,
;;; and only word "false on failure.
;;;
;;; OR returns whatever is returned by the first successful
;;; evaluation, or the word "false if all clauses fail.
;;; AND returns value of the last clause, if all clauses have
;;; evaluated successfully, or the word "false.  The most permissive
;;; is .AND which accepts anything including nothing, as true, and
;;; only word "false as false. .AND will return the value of the last
;;; clause (word "#unspecified if nothing), if none of the clauses
;;; returned false, or word "false.
;;;
;;; Evaluation of logicals AND, OR and .AND is not necessarily carried
;;; to the last clause.
;;;
;;; OR returns immediately on first success.
;;; AND and .AND return immediately on first failure.
;;;
;;; The second level of changes is addition of Lisp/Scheme special forms
;;; LETREC and COND. Both LETREC and COND here do not behave exactly as
;;; their Lisp counterparts, but if you disregard technicalities, they
;;; are close enough. (One of those technicalities is that LETREC applies
;;; LET* binding rules, instead of LET.) Another difference is that in
;;; Logo, they are actually not special forms, so I will call them high
;;; level procedures.
;;;
;;; The third level of changes is compiler for High Level Procedures.
 

;;; Description of High Level Procedures LETREC and COND
;;;
;;; LETREC takes one input, a list of this format:
;;;
;;; LETREC [[[PROC-NAME1 [PROC-TEXT1]]
;;;          [PROC-NAME2 [PROC-TEXT2]]
;;;          [          ...          ]]
;;;         [BODY-FORM1]
;;;         [BODY-FORM2]
;;;         [   ...    ]]
;;;
;;; PROC-NAME is an ordinary word. [PROC-TEXT] is a list of lists in the
;;; form that Logo's TEXT outputs, or that DEFINE accepts as input.
;;; [BODY-FORM] is instruction list (ordinary Logo instruction line).
;;; Block of BODY-FORMs functions as instruction lines in the body of TO
;;; definition, except that each line must be a list.  There are no
;;; restrictions as to what can be done with BODY-FORMs (except that they
;;; can't be recursive), but their main task is to call procedures
;;; defined as PROC-NAMEs with their corresponding inputs.
;;;
;;; LETREC outputs if one of the BODY-FORMs outputs.
;;;
;;; All procedures defined this way are local to LETREC, and not to the
;;; context from where LETREC was invoked. That is, there is no way to
;;; invoke PROC-NAME outside of LETREC. Order in which procedures are
;;; defined is important. BODY-FORMs can call all procedures without
;;; restrictions, but for one procedure to call the other from PROC-TEXT,
;;; that other procedure had better be defined before. That is,
;;; PROC-NAME2 can call PROC-NAME1, but not vice-versa.
;;;
;;; Names in LETREC do not follow Logo, but Scheme rules. You can not use
;;; the same word for variable and procedure name. That is if you had a
;;; local (or global) variable `some-var' defined before LETREC, you can
;;; not use the name `some-var' for PROC-NAME. Actually, you can, but the
;;; variable will be shadowed during the life-span of LETREC. Likewise, it
;;; is an error to use PROC-NAME as a name of a local variable, later in
;;; the body of LETREC. However you can use the name of a previously
;;; defined global procedure as a name for PROC-NAME, but that is not
;;; advisable. If you do that, you should be very carefull not to place
;;; a call to global pocedure in parentheses. All that I have said
;;; here can be summed up with this: PROC-NAMEs are actually not real
;;; procedures, but local variables.
;;;
;;; Special syntax rule when calling PROC-NAME within BODY-FORMs or
;;; PROC-TEXT is that call *must* be enclosed in parenthesis:
;;; (PROC-NAME :input1 :input2 ...). Do *not* rely on Logo tokenization,
;;; which means *always* leave a space before `(' unless it is preceded by
;;; square bracket.
;;; This is OK: [(PROC-NAME ...
;;; These are not: ((PROC-NAME ...        ==>  ( (PROC-NAME ...
;;;                :x+(PROC-NAME ...      ==>  :x+ (PROC-NAME ...
 

;;; COND takes one input, a list of this format:
;;;
;;; COND [
;;;    [[CONDITIONAL1] [TRUE1a] [TRUE1b] ...]
;;;    [[CONDITIONAL2] [TRUE2a]  ...        ]
;;;    [    ...                      ]
;;;    [else    [CATCH-ALL] ...      ]]
;;;
;;; Briefly, COND works like IFELSE with many else-s, and with some
;;; refinements. Each clause in COND should consist of two parts. First
;;; is CONDITIONAL expression. If CONDITIONAL expression evaluates to
;;; true, the corresponding TRUE forms are executed. Each clause can have
;;; more than one TRUE form, and they look and function like body forms
;;; in LETREC, which means that they are Logo instruction lines. Each
;;; TRUE form *must* be a list. CONDITIONAL expression can be a word, but
;;; only one word.
;;;
;;; COND will try all CONDITIONAL expressions until it finds one that
;;; returns true value. Then it will execute it's TRUE forms and
;;; return. If all CONDITIONAL expressions evaluate to "false, else part
;;; is executed. (ELSE is just a procedure returning "true.) CATCH-ALL
;;; forms are just another name for TRUE forms, and the same rules
;;; apply. If you omit ELSE clause, then word "#unspecified is returned.
;;;
;;; COND *always* returns a value, therefore if you do not need this
;;; value, you should pipe the output into IGNORE (... ignore cond [...]
;;; ...). Value returned by COND is either the output of one of TRUE
;;; forms, or word "#unspecified, if your TRUE forms are not returning
;;; any values. It stands to reason that all of your TRUE forms should
;;; output, or none.
;;;
;;; Exceptionally, any COND clause can consist only of CONDITIONAL
;;; expression without TRUE form. In that case, if CONDITIONAL evaluates
;;; to true value, that value is returned by COND, or if "false, COND
;;; moves on to the next clause.
;;;
;;; One simple COND example:
;;;
;;; to cond.memberp :element :list
;;; op cond [
;;;    [[emptyp :list] [op "false]]
;;;    [[equalp first :list :element]]
;;;    [else [op cond.memberp :element bf :list]]]
;;; end
 

;;; I have tried to make this as safe as I could. You should still be able
;;; to run and test standard Logo programs, and even write new programs
;;; that will behave in a standard way. To benefit from changes introduced
;;; here, you *have*to*quote* all inputs to logical functions AND and OR.
;;; That is how this program distinguishes whether to use standard
;;; AND/OR or new versions. Mixed input syntax to one call of AND/OR
;;; is not allowed -- either you quote all inputs or none. However you can
;;; mix old/new syntax in one program, or even one TO definition.
;;;
;;; Unfortunately, all this is expensive. Programs will run slower than with
;;; standard Logo.
;;;
;;; Here is one short example of programming style that is possible with
;;; Logo initialized this way. Whether this style is elegant, or not is
;;; irrelevant here. What is important is that the whole construction
;;; relies heavily on AND and OR -- both for decision making, and result
;;; returning. Standard Logo can not function this way. This is also an
;;; example how to use LETREC, and therefore I have added several
;;; unnecessary instruction lines. Most of these lines serve the
;;; purpose of explaining visibility rules in LETREC.
 

;; 8 queens
;;
;; ;; Start queens with queens 8, if you want only the first result
;; ;; To get all results use (queens 8 "false), and be prepared for
;; ;; a long wait. (Maybe you should try 6, or 4 first?)
;; to queens :number [:one.only "true] 1
;;
;; ;; This one is to check visibility rules
;; localmake "makeboard "makeboard
;; pr equalp :makeboard "makeboard
;;
;; (foreach letrec [[
;;
;;    ;; Define local procedure makeboard
;;    [makeboard [[n]
;;                [localmake "row cascade :n [[x] [op lput # :x]] []]
;;                [op cascade :n [[x] [op fput :row :x]] []]]]
;;
;;    ;; Define local procedure shade
;;    [shade [[queen rest.board [offset 1] 2]
;;            [if emptyp :rest.board [op []]]
;;            [op (fput (filter [[x] [op not (or :x = (:queen - :offset)
;;                                               :x = :queen
;;                                               :x = (:queen + :offset))]]
;;                              first :rest.board)
;;                      (shade :queen bf :rest.board :offset + 1))]]]
;;
;;    ;; Define local procedure put.queen
;;    [put.queen [[board result]
;;
;;                ;; When the board is empty, we're done
;;                [if emptyp :board [push "stack :result op :one.only]]
;;                [localmake "row first :board]
;;                [localmake "queen and [not emptyp :row] [first :row]]
;;
;;                ;; If queen not placed -- backtrack right away
;;                [op (and [:queen]
;;                         [or
;;
;;                            ;; Go ahead -- try to place next queen
;;                            [(put.queen (shade :queen bf :board)
;;                                        lput :queen :result)]
;;
;;                            ;; Nowhere to put next queen -- try to move
;;                            ;; this queen to next available square
;;                            [(put.queen fput bf :row bf :board :result)]])]]]]
;;
;;                  ;; Start of letrec body forms
;;                  [localmake "stack []]
;;
;;                  ;; Check what is in local variable makeboard
;;                  [pr equalp :makeboard "makeboard]
;;                  [pr []]
;;
;;                  ;; Run program and discard the output (true/false)
;;                  [ignore (put.queen (makeboard :number) [])]
;;
;;                  ;; Output positions -- letrec ends here
;;                  [op reverse :stack]]
;;
;;          ;; Template for foreach
;;          [[x] [(show "position # :x)]])
;;
;; ;; There is no way to invoke procedure put.queen here.
;; ;; Contents will show that put.queen does not exist any more
;; pr []
;; show contents
;; pr []
;;
;; ;; Local variable makeboard is visible again
;; pr equalp :makeboard "makeboard
;; end
 

;;; You will have noticed that I use both styles for AND/OR here. OR in SHADE
;;; is standard Logo OR. All AND/ORs in PUT.QUEEN are new. What kind of OR is
;;; used in SHADE is irrelevant -- however PUT.QUEEN will not function if
;;; standard style is used.
;;;
;;; If you observe closely what happens when queens program is run, you
;;; will notice that there is a considerable waiting period between
;;; first "true and first "false printouts. Then comes the long wait
;;; for positions to print out. There is nothing I can do about
;;; waiting for Logo to find positions, but the first waiting period
;;; is another story. During this time interpreter is not actually
;;; running queens, but rather interpreting letrec structure into a
;;; usable form.

;;; If you tried to run COND example, the situation was even worse.
;;; Cond.memberp is a recursive procedure, and Logo interpreted COND
;;; structure in every invocation of cond.memberp. That is
;;; prohibitive.

;;; The answer to this is, of-course, High Level Procedure Compiler.
;;;
;;; .LOGO.COMPILER takes one input, a list of procedure names, or one
;;; procedure name. If you want to compile the whole workspace, call it
;;; without inputs:
;;; .logo.compiler [ proc1 proc2 ...]
;;; .logo.compiler "proc
;;; (.logo.compiler)
;;;
;;; To try it out do: .logo.compiler "queens -- Logo should respond with:
;;; compiling queens ...
;;; compilation completed
;;;
;;; Now run queens again. Both "true and "false should print out without
;;; waiting this time. Compiled cond.memberp example should likewise
;;; give reasonable performance. If you want to save compiled version
;;; do: save.compiled "filename.
;;;
;;;
;;; .LOGO.COMPILER can handle very complex structures, so don't be afraid
;;; to experiment -- with nested letrec, for instance. You can define
;;; letrec within another letrec definition, or within cond, or
;;; vice-versa. The same rules of visibility apply -- you can not call
;;; inner PROC-NAMEs from outer. Pay attention, however, to the
;;; syntax/tokenization rules mentioned before.
;;;
;;; When you first load .logo file, .logo.compiler will automatically
;;; run on itself and cond, to speed up further compilations.
;;;
;;;
;;; This program (.logo) is just an exercise -- a pet project of mine.
;;; I do not suggest that this is how Logo should look like, although it is
;;; nice to be able to write a simple program in Scheme, and practically
;;; bodily transfer it to Logo.
;;;
;;; .logo is *not* thoroughly tested! Use at your own peril.
 

;; Allowing changes to Logo primitives

make "redefp "true

;; Preserving original definitions

copydef "if.tf "if
copydef "ifelse.tf "ifelse
copydef "not.tf "not
copydef "and.tf "and
copydef "or.tf "or

;; Freeing names

erase [if ifelse not and or]
 

;;; New definitions

to if :tf.val :run.true [:run.false []] 2
.maybeoutput (if.tf equalp :tf.val "false [run :run.false] [run :run.true])
end

to ifelse :tf.val :run.true :run.false
.maybeoutput (if.tf equalp :tf.val "false [run :run.false] [run :run.true])
end

to not :thing.not
op (if.tf equalp :thing.not "false ["true] ["false])
end

to true
op "true
end

copydef "else "true
copydef "t "true

to and [:form.and ["true]] [:forms.and] 2
if.tf wordp :form.and [op apply "and.tf fput :form.and :forms.and]
op and.helper fput :form.and :forms.and
end

to and.helper :forms.and
if.tf emptyp bf :forms.and [op run first :forms.and]
if.tf not run first :forms.and [op "false]
op and.helper bf :forms.and
end

to or [:form.or ["false]] [:forms.or] 2
if.tf wordp :form.or [op apply "or.tf fput :form.or :forms.or]
op or.helper fput :form.or :forms.or
end

to or.helper :forms.or
if.tf emptyp bf :forms.or [op run first :forms.or]
local "found.or
make "found.or run first :forms.or
if :found.or [op :found.or]
op or.helper bf :forms.or
end

to .and [:form.and ["true]] [:forms.and] 2
if.tf emptyp :forms.and [op first lput "#unspecified runresult :form.and]
if.tf not first lput "#unspecified runresult :form.and [op "false]
op apply ".and :forms.and
end
 

;;; Cleaning up

;; Prohibit further changes of primitives
ern "redefp

bury [if ifelse not true else or and or.helper and.helper .and]
 

;;; Defining High Level Procedures

;; Letrec

to insert.invoke :name :text
if emptyp :text [op []]
if wordp first :text [
   op (or [and [or.tf equalp first :text word "\( :name
                      equalp first :text (word "\( :name "\))]
               [(se word "\( "invoke word ": bf first :text
                    insert.invoke :name bf :text)]]
          [(and [equalp first :text "\(]
                [equalp first bf :text :name]
                [(se word first :text "invoke word ": first bf :text
                     insert.invoke :name bf bf :text)])]
          [se first :text insert.invoke :name bf :text])]
op (if listp first :text [fput insert.invoke :name first :text
                               insert.invoke :name bf :text]
       [fput first :text insert.invoke :name bf :text])
end

.macro letrec :in.letrec
localmake "body.letrec fput "dummy.letrec (list fput [] bf :in.letrec)
op letrec.helper lput :body.letrec first :in.letrec [(dummy.letrec)]
end

to letrec.helper :clauses.letrec :form.letrec
if emptyp :clauses.letrec [op (list "run :form.letrec)]
localmake "name.letrec first first :clauses.letrec
localmake "parsed.clauses insert.invoke :name.letrec :clauses.letrec
op (se "local (word "" :name.letrec) "make (word "" :name.letrec)
       bf first :parsed.clauses letrec.helper bf :parsed.clauses
       insert.invoke :name.letrec :form.letrec)
end
 

;; Cond

.macro cond :cond.clauses
op letrec [[
   [words [[clauses]
           [if.tf emptyp :clauses [op []]]
           [op fput (fput (or [and [wordp first first :clauses]
                                   [(list first first :clauses)]]
                              [first first :clauses])
                          bf first :clauses)
                    (words bf :clauses)]]]
   [progn [[forms]
           [if.tf emptyp :forms [op []]]
           [if.tf emptyp bf first :forms [op fput first :forms
                                             (progn bf :forms)]]
           [op fput (list first first :forms
                          letrec.helper
                          (list (list "dummy.cond fput [] bf first :forms))
                          [(dummy.cond)])
                    (progn bf :forms)]]]
   [do.and [[clauses]
            [if.tf emptyp :clauses [op [[(and.cludge)]]]]
            [op fput (se "\( "and.cludge first :clauses "\))
                     (do.and bf :clauses)]]]]
           [op (se "invoke [[[x] [op (if.tf .eq :x "#false ["false] [:x])]]]
                   "\( "or (do.and (progn (words :cond.clauses))) "\))]]
end
 

to and.cludge [:form.first ["#unspecified]] [:form.second []] 2
local "and.result
make "and.result run :form.first
if.tf or not :and.result emptyp :form.second [op :and.result]
make "and.result lput "#unspecified runresult :form.second
op (if.tf not first :and.result ["#false] [first :and.result])
end
 

;; Compiler

to .logo.compiler [:proc procedures] 1
letrec [[
   [input.depth [[lst]
                 [if emptyp :lst [op 1]]
                 [if or.tf wordp :lst arrayp :lst [op 0]]
                 [op max sum 1 (input.depth first :lst)
                               (input.depth bf :lst)]]]
   [compile.proc [[proc]
                  [if emptyp :proc [op []]]
                  [local "struct.min]
                  [op ifelse
                      (.and [wordp first :proc]
                            [macrop first :proc]
                            [make "struct.min
                                  gprop "compiler.cap first :proc]
                            [not.tf emptyp :struct.min]
                            [not.tf emptyp bf :proc]
                            [:struct.min < (input.depth first bf :proc)])
                      [se (list "run macroexpand list first :proc
                                (compile.proc first bf :proc))
                          (compile.proc bf bf :proc)]
                      [or [and [listp first :proc]
                               [fput (compile.proc first :proc)
                                     (compile.proc bf :proc)]]
                          [fput first :proc (compile.proc bf :proc)]]]]]
   [compile.ws [[proc.lst]
                [if.tf emptyp :proc.lst [stop]]
                [(pr "compiling first :proc.lst "...)]
                [(invoke (or [and [macrop first :proc.lst]
                                  [".defmacro]]
                             ["define])
                         first :proc.lst (compile.proc text first :proc.lst))]
                [(compile.ws bf :proc.lst)]]]]
        [ifelse listp :proc [(compile.ws filter "procedurep :proc)]
                [(compile.ws filter "procedurep (list :proc))]]
        [pr [compilation completed]]]
end

;; Saving compiled procedures

to save.compiled [:filename .and
                            [type "|Enter file name to save to: |]
                            [rw]] 1
if equalp first :filename "" [make "filename bf :filename]
local "oldwriter
make "oldwriter writer
openwrite :filename
setwrite :filename
foreach procedures [[x] [(pr (if macrop :x [".defmacro] ["define])
                             word "" :x (list text :x)) pr []]]
setwrite :oldwriter
close :filename
end
 

;;; Compiler Capabilities
;;;
;;; Capabilities have this format: property = name of High Level Procedure
;;;                                value    = minimum depth of input - 1
;;;
;;; You can add your own compiler capabilities, providing you follow
;;; these rules: High level procedure (structure) you define must have
;;; one input only - a list. And, of-course it must be a macro --
;;; otherwise there is nothing for compiler to do. After you have
;;; defined (and tested) your procedure add your pprop line to lines
;;; below. That is all.

pprop "compiler.cap "letrec 4
pprop "compiler.cap "cond 2
 

bury [insert.invoke letrec letrec.helper cond and.cludge .logo.compiler
                    save.compiled]
bury [[] [] [compiler.cap]]
 

;;; End of interpreter changes
;;;
;;; Addition to library -- without `max' .logo.compiler will not work

to before [:first.wd "] [:rest.wds] 2
op reduce [[x y] [op ifelse beforep :x :y [:x] [:y]]] fput :first.wd :rest.wds
end

to max :first.num [:rest.nums] 2
op reduce [[x y] [op ifelse :x > :y [:x] [:y]]] fput :first.num :rest.nums
end

to min :first.num [:rest.nums] 2
op reduce [[x y] [op ifelse :x < :y [:x] [:y]]] fput :first.num :rest.nums
end

to evenp :number
op zerop remainder :number 2
end

to oddp :number
op not evenp :number
end

to zerop :number
op equalp :number 0
end

to identity :stuff
op :stuff
end

bury [before max min evenp oddp zerop identity]
 

;;; Compile the COMPILER and COND on startup
;;; Add your own High Order Structures here.

.logo.compiler [.logo.compiler cond]

pr [... initialization completed.]

;;; End of .logo
 

Ja idem na vrh stranice, a Vi?