Skip to content

Commit 6a53e51

Browse files
BowenFuBowenFu
authored
Macro. (#16)
Co-authored-by: Bowen Fu <missing>
1 parent 9a4c3dc commit 6a53e51

File tree

6 files changed

+166
-35
lines changed

6 files changed

+166
-35
lines changed

‎include/lisp/evaluator.h

Lines changed: 127 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -289,6 +289,8 @@ class Assignment final : public Expr
289289
}
290290
};
291291

292+
class Macro;
293+
292294
class Definition final : public Expr
293295
{
294296
std::string mVariableName;
@@ -299,6 +301,7 @@ class Definition final : public Expr
299301
, mValue{value}
300302
{
301303
}
304+
bool isMacroDefinition() const;
302305
ExprPtr eval(std::shared_ptr<Env> const& env) override;
303306
std::string toString() const override
304307
{
@@ -310,7 +313,7 @@ inline bool isTrue(ExprPtr expr)
310313
{
311314
using T = Literal<bool>;
312315
T const* v = dynamic_cast<T const*>(expr.get());
313-
return v != nullptr && v->get();
316+
return v == nullptr || v->get();
314317
}
315318

316319
class If final : public Expr
@@ -391,25 +394,41 @@ class Or final : public Expr
391394
}
392395
};
393396

394-
class Lambda final : public Expr
397+
class LambdaBase : public Expr
395398
{
396399
std::vector<std::string> mParameters;
397400
bool mVariadic;
398401
std::shared_ptr<Sequence> mBody;
399402
public:
400-
Lambda(std::vector<std::string> const& params, bool variadic, std::shared_ptr<Sequence> body)
403+
LambdaBase(std::vector<std::string> const& params, bool variadic, std::shared_ptr<Sequence> body)
401404
: mParameters{params}
402405
, mVariadic{variadic}
403406
, mBody{body}
404407
{
405408
}
406409
ExprPtr eval(std::shared_ptr<Env> const& env) override;
410+
};
411+
412+
class Lambda final : public LambdaBase
413+
{
414+
public:
415+
using LambdaBase::LambdaBase;
407416
std::string toString() const override
408417
{
409418
return "Lambda";
410419
}
411420
};
412421

422+
class Macro final : public LambdaBase
423+
{
424+
public:
425+
using LambdaBase::LambdaBase;
426+
std::string toString() const override
427+
{
428+
return "Macro";
429+
}
430+
};
431+
413432
class Cond final : public Expr
414433
{
415434
std::vector<std::pair<ExprPtr, ExprPtr>> mClauses;
@@ -473,50 +492,71 @@ class PrimitiveProcedure : public Procedure
473492
}
474493
};
475494

476-
class CompoundProcedure : public Procedure
495+
class CompoundProcedureBase : public Procedure, public std::enable_shared_from_this<CompoundProcedureBase>
477496
{
478497
std::shared_ptr<Sequence> mBody;
479498
std::vector<std::string> mParameters;
480499
bool mVariadic;
481500
std::shared_ptr<Env> mEnvironment;
501+
virtual std::string getClassName() const = 0;
482502
public:
483-
CompoundProcedure(std::shared_ptr<Sequence> body, std::vector<std::string> parameters, bool variadic, std::shared_ptr<Env> const& environment)
503+
CompoundProcedureBase(std::shared_ptr<Sequence> body, std::vector<std::string> parameters, bool variadic, std::shared_ptr<Env> const& environment)
484504
: mBody{body}
485505
, mParameters{parameters}
486506
, mVariadic{variadic}
487507
, mEnvironment{environment}
488508
{}
489509
ExprPtr eval(std::shared_ptr<Env> const& /* env */) override
490510
{
491-
return ExprPtr{new CompoundProcedure{mBody, mParameters, mVariadic, mEnvironment}};
511+
return shared_from_this();
492512
}
493513
std::shared_ptr<Expr> apply(std::vector<std::shared_ptr<Expr>> const& args) override
494514
{
495515
return mBody->eval(mEnvironment->extend(mParameters, args, mVariadic));
496516
}
497517
std::string toString() const override
498518
{
499-
std::ostringstream o;
500-
o << "CompoundProcedure (";
501-
if (!mParameters.empty())
502-
{
503-
for (auto i = mParameters.begin(); i != std::prev(mParameters.end()); ++i)
504-
{
505-
o << *i << " ";
506-
}
507-
if (mVariadic)
508-
{
509-
o << ". ";
510-
}
511-
if (mParameters.size() >= 1)
519+
std::ostringstream o;
520+
o << getClassName() << " (";
521+
if (!mParameters.empty())
512522
{
513-
o << mParameters.back();
523+
for (auto i = mParameters.begin(); i != std::prev(mParameters.end()); ++i)
524+
{
525+
o << *i << " ";
526+
}
527+
if (mVariadic)
528+
{
529+
o << ". ";
530+
}
531+
if (mParameters.size() >= 1)
532+
{
533+
o << mParameters.back();
534+
}
535+
o << ", ";
514536
}
515-
o << ", ";
537+
o << "<procedure-env>)";
538+
return o.str();
516539
}
517-
o << "<procedure-env>)";
518-
return o.str();
540+
};
541+
542+
class CompoundProcedure final : public CompoundProcedureBase
543+
{
544+
std::string getClassName() const override
545+
{
546+
return "CompoundProcedure";
519547
}
548+
public:
549+
using CompoundProcedureBase::CompoundProcedureBase;
550+
};
551+
552+
class MacroProcedure final : public CompoundProcedureBase
553+
{
554+
std::string getClassName() const override
555+
{
556+
return "MacroProcedure";
557+
}
558+
public:
559+
using CompoundProcedureBase::CompoundProcedureBase;
520560
};
521561

522562
class Application final : public Expr
@@ -528,6 +568,10 @@ class Application final : public Expr
528568
: mOperator{op}
529569
, mOperands{params}
530570
{}
571+
bool isMacroCall() const
572+
{
573+
return dynamic_cast<MacroProcedure const*>(mOperator.get());
574+
}
531575
ExprPtr eval(std::shared_ptr<Env> const& env) override
532576
{
533577
auto op = mOperator->eval(env);
@@ -536,8 +580,67 @@ class Application final : public Expr
536580
}
537581
std::string toString() const override
538582
{
539-
return "Application (" + mOperator->toString() + ")";
583+
std::ostringstream o;
584+
o << "Application (" << mOperator->toString();
585+
for (auto const& e: mOperands)
586+
{
587+
o << " " << e->toString();
588+
}
589+
o << ")";
590+
return o.str();
540591
}
541592
};
542593

594+
template <typename Func>
595+
void forEach(ExprPtr const& expr, Func func)
596+
{
597+
if (auto e = dynamic_cast<Cons const*>(expr.get()))
598+
{
599+
forEach(e->car(), func);
600+
forEach(e->cdr(), func);
601+
}
602+
func(expr);
603+
}
604+
605+
template <typename Func>
606+
ExprPtr transform(ExprPtr const& expr, Func func)
607+
{
608+
if (auto e = dynamic_cast<Cons const*>(expr.get()))
609+
{
610+
return ExprPtr{new Cons{transform(e->car(), func), transform(e->cdr(), func)}};
611+
}
612+
return func(expr);
613+
}
614+
615+
inline ExprPtr expandMacros(ExprPtr const& expr, std::shared_ptr<Env> const& env)
616+
{
617+
auto func = [&env](auto const& expr)
618+
{
619+
if (auto a = dynamic_cast<Application*>(expr.get()))
620+
{
621+
if (a->isMacroCall())
622+
{
623+
return a->eval(env);
624+
}
625+
}
626+
return expr;
627+
};
628+
return transform(expr, func);
629+
}
630+
631+
inline void defineMacros(ExprPtr const& expr, std::shared_ptr<Env> const& env)
632+
{
633+
auto func = [&env](auto const& expr)
634+
{
635+
if (auto d = dynamic_cast<Definition*>(expr.get()))
636+
{
637+
if (d->isMacroDefinition())
638+
{
639+
d->eval(env);
640+
}
641+
}
642+
};
643+
forEach(expr, func);
644+
}
645+
543646
#endif // LISP_EVALUATOR_H

‎include/lisp/parser.h

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -148,12 +148,23 @@ inline ExprPtr assignment(MExprPtr const& mexpr)
148148
return ExprPtr{new Assignment(var, value)};
149149
}
150150

151-
inline ExprPtr lambda(MExprPtr const& mexpr)
151+
template <typename LambdaT>
152+
inline ExprPtr lambdaBase(MExprPtr const& mexpr)
152153
{
153154
auto [car, cdr] = deCons(mexpr);
154155
auto params = parseParams(car);
155156
auto body = sequence(cdr);
156-
return ExprPtr{new Lambda(params.first, params.second, body)};
157+
return ExprPtr{new LambdaT(params.first, params.second, body)};
158+
}
159+
160+
inline ExprPtr lambda(MExprPtr const& mexpr)
161+
{
162+
return lambdaBase<Lambda>(mexpr);
163+
}
164+
165+
inline ExprPtr macro(MExprPtr const& mexpr)
166+
{
167+
return lambdaBase<Macro>(mexpr);
157168
}
158169

159170
inline ExprPtr if_(MExprPtr const& mexpr)
@@ -261,6 +272,10 @@ inline auto tryMCons(MExprPtr const& mexpr) -> ExprPtr
261272
{
262273
return lambda(cdr);
263274
}
275+
else if (carStr == "macro")
276+
{
277+
return macro(cdr);
278+
}
264279
else if (carStr == "if")
265280
{
266281
return if_(cdr);

‎sample/CMakeLists.txt

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -125,4 +125,7 @@ do_test(test_quasiquote_unquote_lst "`,(+ 1 2)" "3")
125125
do_test(test_quasiquote_lst_unquote_lst "`(,(+ 1 2))" "(3)")
126126
do_test(test_quasiquote_pair_unquote_lst "`(1 . ,(+ 1 2))" "(1 . 3)")
127127

128-
do_test(test_quasiquote_nested_unquote "\`(1 \`,(+ 1 ,(+ 2 3)) 4)" "\\\\(1 \\\\(\'quasiquote \\\\(\'unquote \\\\(\'\\\\+ 1 5\\\\)\\\\)\\\\) 4\\\\)")
128+
do_test(test_quasiquote_nested_unquote "\`(1 \`,(+ 1 ,(+ 2 3)) 4)" "\\\\(1 \\\\(\'quasiquote \\\\(\'unquote \\\\(\'\\\\+ 1 5\\\\)\\\\)\\\\) 4\\\\)")
129+
130+
do_test(test_macro_and "(define myAnd (macro (x y) (if x y #f))) (myAnd (+ 1 2) (+ 3 4))" "7")
131+
do_test(test_macro_or "(define myOr (macro (x y) (if x x y))) (myOr (+ 1 2) (+ 3 4))" "3")

‎sample/loop.cpp

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -141,11 +141,15 @@ auto eval(std::string const& input, std::shared_ptr<Env> const& env)
141141
Lexer lex(input);
142142
MetaParser p(lex);
143143
std::string result;
144+
auto macroEnv = std::make_shared<Env>();
144145
do
145146
{
146147
auto me = p.sexpr();
147148
auto e = parse(me);
148-
result = e->eval(env)->toString();
149+
// define macros
150+
defineMacros(e, macroEnv);
151+
auto ee = expandMacros(e, macroEnv);
152+
result = ee->eval(env)->toString();
149153
} while (!p.eof());
150154
return result;
151155
}

‎src/evaluator.cpp

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
11
#include "lisp/evaluator.h"
2+
#include "lisp/parser.h"
23

34
ExprPtr true_()
45
{
@@ -18,7 +19,7 @@ ExprPtr nil()
1819
return n;
1920
}
2021

21-
ExprPtr Lambda::eval(std::shared_ptr<Env> const& env)
22+
ExprPtr LambdaBase::eval(std::shared_ptr<Env> const& env)
2223
{
2324
CompoundProcedure proc{mBody, mParameters, mVariadic, env};
2425
return std::shared_ptr<Expr>(new CompoundProcedure(proc));
@@ -28,3 +29,8 @@ ExprPtr Definition::eval(std::shared_ptr<Env> const& env)
2829
{
2930
return env->defineVariable(mVariableName, mValue->eval(env));
3031
}
32+
33+
bool Definition::isMacroDefinition() const
34+
{
35+
return dynamic_cast<Macro const*>(mValue.get());
36+
}

‎test/lisp/test.cpp

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@ TEST(Lexer, 1)
2020

2121
TEST(Parser, 1)
2222
{
23-
std::initializer_list<std::pair<std::string, std::string>> expected = {{"Definition ( square : Lambda )", "CompoundProcedure (y, <procedure-env>)"}, {"Application (square)", "49"}};
23+
std::initializer_list<std::pair<std::string, std::string>> expected = {{"Definition ( square : Lambda )", "CompoundProcedure (y, <procedure-env>)"}, {"Application (square 7)", "49"}};
2424

2525
Lexer lex("(define square (lambda (y) (* y y))) (square 7)");
2626
MetaParser p(lex);
@@ -55,7 +55,7 @@ TEST(Parser, 2)
5555
{
5656
std::initializer_list<std::pair<std::string, std::string> > expected =
5757
{{"Definition ( factorial : Lambda )", "CompoundProcedure (y, <procedure-env>)"},
58-
{"Application (factorial)", "120"}};
58+
{"Application (factorial 5)", "120"}};
5959

6060
Lexer lex("(define factorial (lambda (y) (if (= y 0) 1 (* y (factorial (- y 1)))))) (factorial 5)");
6161
MetaParser p(lex);
@@ -119,7 +119,7 @@ TEST(Parser, 2)
119119

120120
TEST(Parser, begin)
121121
{
122-
std::initializer_list<std::pair<std::string, std::string>> expected = {{"Definition ( square : Lambda )", "CompoundProcedure (y, <procedure-env>)"}, {"Application (square)", "49"}};
122+
std::initializer_list<std::pair<std::string, std::string>> expected = {{"Definition ( square : Lambda )", "CompoundProcedure (y, <procedure-env>)"}, {"Application (square 7)", "49"}};
123123

124124
Lexer lex("(define square (lambda (y) (* (begin 1 y) y))) (square 7)");
125125
MetaParser p(lex);
@@ -367,7 +367,7 @@ TEST(Parser, Variadic)
367367
{
368368
std::initializer_list<std::pair<std::string, std::string> > expected =
369369
{{"Definition ( to-list : Lambda )", "CompoundProcedure (. y, <procedure-env>)"},
370-
{"Application (to-list)", "(1)"}};
370+
{"Application (to-list 1)", "(1)"}};
371371

372372
Lexer lex("(define (to-list . y) y) (to-list 1)");
373373
MetaParser p(lex);
@@ -390,7 +390,7 @@ TEST(Parser, Variadic2)
390390
{
391391
std::initializer_list<std::pair<std::string, std::string> > expected =
392392
{{"Definition ( rest : Lambda )", "CompoundProcedure (_ . y, <procedure-env>)"},
393-
{"Application (rest)", "(2 3)"}};
393+
{"Application (rest 1 2 3)", "(2 3)"}};
394394

395395
Lexer lex("(define rest (lambda (_ . y) y)) (rest 1 2 3)");
396396
MetaParser p(lex);
@@ -473,7 +473,7 @@ TEST(Parser, Application)
473473
TEST(Parser, Application2)
474474
{
475475
std::initializer_list<std::pair<std::string, std::string> > expected = {{"Definition ( i : Lambda )", "CompoundProcedure (x, <procedure-env>)"},
476-
{"Application (i)", "."}};
476+
{"Application (i .)", "."}};
477477

478478
Lexer lex("(define i (lambda (x) x)) (i \".\")");
479479
MetaParser p(lex);

0 commit comments

Comments
 (0)