BackgroundS-ExpressionsS-Expressions --- ExamplesS-Expressions as TreesS-Expressions as Function CallsS-Expressions as FunctionsFunction ApplicationFunction Application --- ExamplesAtoms --- NumbersAtoms --- Numbersldots Atoms --- Numbersldots Atoms --- StringsAtoms --- BooleansIdentifiersDefining VariablesDefining FunctionsDefining Helper FunctionsPreventing EvaluationDr SchemeDr SchemeDr Scheme --- Using TeachPacksDr Scheme --- Using the StepperReferencesReferencesldots Scheme so FarScheme so Farldots520 —Spring 2008 — 34CSc 520Principles of ProgrammingLanguages34 : Scheme — IntroductionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 34BackgroundScheme is based on LISP which was developed byJohn McCarthy in the mid 50s.LISP stands for LISt Processing, not Lots of IrritatingSilly Parentheses.Functions and data share the same representation:S-Expressions.A basic LISP implementation needs six functionscons, car, cdr, equal, atom, cond.Scheme was developed by Sussman and Steele in1975.[2]520 —Spring 2008 — 34S-ExpressionsAn S-Expression is a balanced list of parentheses.More formally, an S-expression is1. a literal (i.e., number, boolean, symbol, character,string, or empty list).2. a list of s-expressions.Literals are sometimes called atoms.[3]520 —Spring 2008 — 34S-Expressions — ExamplesLegal Illegal66()(4 5)((5))(()())((4 5) (6 (7)))((5))()()(4 (5))([4]520 —Spring 2008 — 34S-Expressions as TreesAn S-expression can be seen as a linear representationof tree-structure:(3 4)2634263457(2 (3 4) (5 (6) 7))2(6)[5]520 —Spring 2008 — 34S-Expressions as Function CallsA special case of an S-expression is when the firstelement of a list is afunction name.Such an expression can be evaluated.> (+ 4 5)9> (add-five-to-my-argument 20)25> (draw-a-circle 20 45)#t[6]520 —Spring 2008 — 34S-Expressions as FunctionsAs we will see, function definitions are alsoS-expressions:( define ( farenheit− 2− celsius f )(∗ (− f 32) 5/9)) So, Scheme really only has one syntactic structure, theS-expression, and that is used as a data-structure (torepresent lists, trees, etc), as function definitions, andas function calls.[7]520 —Spring 2008 — 34Function ApplicationIn general, a function application is written like this:(operator arg1arg2. . . argn)The evaluation proceeds as follows:1. Evaluate operator. The result should be a functionF.2. Evaluatearg1, arg2, . . . argnto getval1, val2, . . . valn3. Apply F to val1, val2, . . . valn.[8]520 —Spring 2008 — 34Function Application — Examples> (+ 4 5)9> (+ (+ 5 6) 3)14> 77> (4 5 6)eval: 4 is not a function> #t#t[9]520 —Spring 2008 — 34Atoms — NumbersScheme hasFractions (5/9)Integers (5435)Complex numbers (5+2i)Inexact reals (#i3.14159265)> (+ 5 4)9> (+ (*5 4) 3)23> (+ 5/9 4/6)1.2> 5/90.5[10]520 —Spring 2008 — 34Atoms — Numbers...> (+ 5/9 8/18)1> 5+2i5+2i> (+ 5+2i 3-i)8+1i> (*236542164521634 3746573426573425643)886222587860913289285513763860662> pi#i3.141592653589793> e#i2.718281828459045> (*2 pi)#i6.283185307179586[11]520 —Spring 2008 — 34Atoms — Numbers...Scheme tries to do arithmetic exactly, as much aspossible.Any computations that depend on an inexact valuebecomes inexact.Scheme has many builtin mathematical functions:> (sqrt 16)4> (sqrt 2)#i1.4142135623730951> (sin 45)#i0.8509035245341184> (sin (/ pi 2))#i1.0[12]520 —Spring 2008 — 34Atoms — StringsA string is enclosed in double quotes.> (display "hello")hello> "hello""hello"> (string-length "hello")5> (string-append "hello" " " "world!")"hello world!"[13]520 —Spring 2008 — 34Atoms — Booleanstrue is written #t.false is written #f.> #ttrue> #ffalse> (display #t)#t> (not #t)false[14]520 —Spring 2008 — 34IdentifiersUnlike languages like C and Java, Scheme allowsidentifiers to contain special characters, such as! $ % &*+ - . / : < = > ? @ ˆ ˜ .Identifiers should not begin with a character that canbegin a number.This is a consequence of Scheme’s simple syntax.You couldn’t do this in Java because then there wouldbe many ways to interpret the expression X-5+Y.LegalIllegalh-e-l-l-ogive-me!WTF?3some-stance[15]520 —Spring 2008 — 34Defining Variablesdefine binds an expression to a global name:(define name expression)(define PI 3.14)> PI3.14(define High-School-PI (/ 22 7))> High-School-PI3.142857[16]520 —Spring 2008 — 34Defining Functionsdefine binds an expression to a global name:(define (name arg1arg2...) expression)arg1arg2... are formal function parameters.(define (f) ’hello)> (f)hello(define (square x) (*x x))> (square 3)9[17]520 —Spring 2008 — 34Defining Helper FunctionsA Scheme program consists of a large number offunctions.A function typically is defined by calling other functions,so calledhelper or auxiliary functions.(define (square x) (*x x))(define (cube x) (*x (square x)))> (cube 3)27[18]520 —Spring 2008 — 34Preventing EvaluationSometimes you don’t want an expression to beevaluated.For example, you may want to think of (+ 4 5) as a listof three elements +, 4, and 5, rather than as thecomputed value 9.(quote (+ 4 5)) prevents (+ 4 5) from beingevaluated. You can also write’(+ 4 5).> (display (+ 4 5))9> (display (quote (+ 4 5)))(+ 4 5)> (display ’(+ 4 5))(+ 4 5)[19]520 —Spring 2008 — 34Dr SchemeDownload DrScheme from here: http://www.drscheme.org.It has already been installed for you in lectura and theWindows machines in the lab.Start DrScheme under unix (on lectura) by saying> drschemeOn Windows and MacOS it may be enough to click onthe DrScheme logo to start it up.[20]520 —Spring 2008 — 34Dr SchemeDefinitionswindowInteractionwindowLanguagelevelSelect languagelevelAddteachpacksSavedefinitions[21]520 —Spring 2008 — 34Dr Scheme — Using TeachPacks[22]520 —Spring 2008 — 34Dr Scheme — Using the Stepper[23]520 —Spring 2008 — 34ReferencesRead Scott, pp. 523-527, 528-539.Free interpreter: http://www.drscheme.org.Manual:http://www.swiss.ai.mit.edu/projects/scheme/documentation/scheme.htmlTutorials:http://ai.uwaterloo.ca/˜dale/cs486/s99/scheme-tutorial.htmlhttp://cs.wwc.edu/%7Ecs_dept/KU/PR/Scheme.htmlhttp://www.cis.upenn.edu/%7Eungar/CIS520/scheme-tutorial.htmlhttp://dmoz.org/Computers/Programming/Languages/Lisp/Scheme[24]520 —Spring 2008 — 34References...Language reference manual:http://www.swiss.ai.mit.edu/ftpdir/scheme-reports/r5rs.ps.Some of this material is taken
View Full Document
Unlocking...